Stacks and reverse Polish notation

The stack is the Forth analog of a pile of cards with numbers written on them. The numbers are always added to the top of the pile, and removed from the top of the pile. FlashForth incorporates two stacks: the parameter stack and the return stack, each consisting of a number of cells that can hold 16-bit numbers.

The Forth input line


decimal 2 5 73 -16 ok<#,ram>


leaves the parameter stack in the state

cell #	contents	comment
0		TOS (Top Of Stack)
1		NOS (Next On Stack)
2
3

We will usually employ zero-based relative numbering in Forth data structures such as stacks, arrays and tables. Note that, when a sequence of numbers is entered like this, the right-most number becomes TOS and the left-most number sits at the bottom of the stack.

Suppose that we followed the original input line with the line


+ - * . xxx ok<#,ram>


What would the xxx be? The operations would produce the successive stacks:

word executed			+	-	*	.
stack result	TOS NOS	-16   73    5    2	57    5    2	-52    2	-104

After both lines, the gtkterm console shows

decimal 2 5 73 -16  ok<#,ram>2 5 73 65520 
+ - * . -104  ok<#,ram>

Note that FlashForth conveniently displays the stack elements on interpreting each line and that the value of -16 is displayed as the 16-bit unsigned integer 65520. Also, the word ``.'' consumes the -104 data value, leaving the stack empty. If we execute ``.'' on the now-empty stack, the outer interpreter aborts with a stack pointer error (SP ?).

The programming notation where the operands appear first, followed by the operator(s) is called reverse Polish notation (RPN). It will be familiar to students who own RPN calculators made by Hewlett-Packard.