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:
- pop value from stack (call this 'A')
- pop value from stack (call this 'B')
- add A + B
- 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:
- pop value
- pop location
- store value in location
- swap - opcode: (has effect of swapping the two to elements)
- pop value (call T)
- pop value (call B)
- push T
- push B
- label: - a label, program counter spot
- &label - the location of a label
- goto - opcode:
- pop destination
- set program counter to location
- gosub - opcode:
- push current location on stack
- swap top two elements of stack (see swap above)
- pop destination
- set program counter to destination
- ifthen
- pop 'then' destination
- pop 'value'
- if 'value' is true, goto then destination
- ifthenelse
- pop 'else' destination
- pop 'then' destination
- pop 'value'
- 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