Are we stack machines? Link to heading

A rhetorical question, maybe. But considering that an “action” could be construed as operator, however simple or complex it may be, the indefinite space that is our environment may be seen as stacking. (Readers not familiar with the concept of stack may think of it as shelves or layers.) Actions not only modify it, they shape our perception of objects. Actions are the building blocks of reality.

In the following I will give a rather technical example of stack computation. But if you have the patience to follow it through, you might find the intuition that it provides - not so strange anymore. And from there we can take it further, viewing our everyday experience in a similar manner and discussing the implications.

This idea came to me, back then, when I played with a HP-28S scientific pocket calculator, which was my first programming device. Hewlett-Packard’s Bill Wickes and team developed its RPL¹ operating system which unites Lisp structures with the Forth Programming Language². It operates on a stack in postfix or Reverse Polish Notation (RPN). Each command is an operation that modifies the stack levels and pushes the result back on it. I’ve been fascinated by the beauty and simplicity of this approach to computing which is at the core of the Forth Language³.

To illustrate the working of a stack machine we are going to discuss a simple program of three operations, two of them are just reshuffling the stack and one is arithmetic:

• OVER copies the second level of the stack: ( n1 n2 – n2 n1 n2)
• + is arithmetic addition and consumes two levels, leaving the sum at top: ( n1 n2 – n1+n2)
• SWAP swaps the last two levels of the stack: ( n1 n2 – n2 n1)

On the HP-28S with RPL the above is simply coded (with storing the program as F) as

« OVER + SWAP ENTER 'F STO

A Forth definition of F could thus be written as

: F ( n n -- n n) OVER + SWAP ; \ implements F

For illustrating the effect of these three operations, let’s place two numbers, 2 and 1, on the stack⁴

2 1 .s \ plug in numbers and show stack
2 1 <-Top  ok

Applying the operator OVER copies the second level to top (now we have three objects on the stack):

OVER .s 
2 1 2 <-Top  ok

The arithmetic + consumes the top and second levels and adds them up

+ .s 
2 3 <-Top  ok

Next SWAP reverses the two stack levels

SWAP .s
3 2 <-Top  ok

We have completed the sequence of OVER + SWAP once and find a new pair on the stack! We can start over and repeat the sequence (our program) and find next

F .s \ run `OVER + SWAP` again
5 3 <-Top  ok

And from now on we can continue these iterations ad infinitum …

As you have certainly realized by now, these simple stack operations implement the generalized Fibonacci series⁵ for arbitrary numbers $x$ by the recurrence relation

$$x_{n} \leftarrow x_{n-1}+x_{n-2}$$

But instead of the usual mathematical infix notation we let our operator, the compound OVER + SWAP, act on the stack in postfix, ie. operator after operands. RPN makes this distinction between operator and operand explicit. The stack with the two numbers represents the “environment” for the operator, and (the application of) the operator is the “action”. What numbers we put on the stack is unimportant, they are just tokens in this game. Our particular sequence of stack operations takes two numbers from the stack and its effect also leaves two numbers on the stack, and so ensures that we can repeat the action indefinitely.