stack machine

A middle of the road compromise between an accumulator machine and a register machine. The 8087 math co-processor and its descendents are stack-based; however, most modern microprocessors are register machines because they are more flexible and easy to program.

Mathematical formulae for stack machines are often written in reverse polish notation or RPN.

The primary interest in RPN for computing revolves around its nature as a stack machine.

Stack machines are very easy to write and involve a very small number of data structures. The most important one of these is the stack.

When a RPN language encounters a token that is not an operator, it simply pushes that token onto the stack. Consider the first three statements of the following program:

2 3 1 + -         top
    ^           +-----+
                |  1  |
                +-----+
                |  3  |
                +-----+
                |  2  |
                +-----+

The parser/interpreter read a '2'. The '2' is not part of the known set of operators (+ - * /) and thus it pushed it on to the stack. It next read a '3'. Likewise, this was not part of the known set of operators and so it pushed it onto the stack also. Each 'push' is done by placing the new value on the top of the stack. This forms a LIFO or FILO structure (they mean the same thing). The same is true for the '1'.

Next, the parser/interpreter reads the '+':

2 3 1 + -         top
      ^         +-----+
                |  1  |
                +-----+
                |  3  |
                +-----+
                |  2  |
                +-----+

'+' is a known operator and thus it preforms the following operation:

1. pop value from stack (call this 'A')
2. pop value from stack (call this 'B')
3. add A + B
4. push result onto stack

Thus, the '+' will take the '1' and the '3' from the stack, add them together (giving 4) and then push the value back onto the stack:

2 3 1 + -         top
      ^         +-----+
                |  4  |
                +-----+
                |  2  |
                +-----+

It is rather simple to extend this idea to objects beyond numbers. Other data types useful for programming languages are strings, program counter locations (thus allowing goto, gosub, and return commands), and variable names.

What follows is a purely hypothetical RPN based language that uses some perl-ish constructs in some places. To properly understand the code at the end, the following language has been defined:

• $var - the location of the variable itself
• store - opcode:
  1. pop value
  2. pop location
  3. store value in location
• swap - opcode: (has effect of swapping the two to elements)
  1. pop value (call T)
  2. pop value (call B)
  3. push T
  4. push B
• label: - a label, program counter spot
• &label - the location of a label
• goto - opcode:
  1. pop destination
  2. set program counter to location
• gosub - opcode:
  1. push current location on stack
  2. swap top two elements of stack (see swap above)
  3. pop destination
  4. set program counter to destination
• ifthen
  1. pop 'then' destination
  2. pop 'value'
  3. if 'value' is true, goto then destination
• ifthenelse
  1. pop 'else' destination
  2. pop 'then' destination
  3. pop 'value'
  4. if 'value' is true, goto 'then' destination, else goto 'else' destination

The code that follows computes the value of 'e'

main:
 $i 0 store     # $i is the location of variable 'i'.
loop:
 $e e 1 i &factorial gosub / + store
 # &location pushes the current address on the stack
 # then pushes &location on the stack, and then calls goto
 i 10 > &done &loop ifthenelse # if (test) then goto &done else goto
done:
 e print
 exit

factorial:
 $l swap store # swap the top two items on the stack (address of return)
               # and store the location in $l
 $j i store
 $r 1 store
facloop:
 $r j r * store
 $j j 1 - store
 j 1 < &facloop ifthen

 r l goto
 # push r on the stack, push l on the stack, l is popped in the gosub
 # and thus 'r' is on the top of the stack at the end - a return value