Building a stack machine

A stack machine is arguably the simplest model for mechanical computation, and as such is still in wide use to this day under the hood of many programming languages, such as Java.

Fundamentally, a stack machine consists of a tape of instructions, and a stack of values. A stack machine simply reads the next instruction from the tape, executes the instruction against the stack of values, and steps to the next instruction on the tape until it reaches some "halt" instruction which stops the machine's progress.

Fig 1. A simple stack machine Example

                  +————————+
                  | push 1 |
                  | push 2 |
    +——————+      | add    |
   —+——————+——————+———–————+
     stack          tape

This code will first push the value 1 onto the stack, then push the value 2 onto the stack, then run the add instruction which pops the top two elements of the stack, and pushes the result.

Using machines like this, we can easily represent arithmetic operations and many programming constructs. Given an arithmetic expression such as (1 + 2 + 3 / (4 * 5)), we can write the S expression

(+ 1 2
    (/ 3
       (* 4 5)))

Which we can translate into the stack machine program

push 4
push 5
multiply
push 3
divide
push 2
push 1
add
add

Now there's a problem here, how can we produce a copy of a value on the stack? With this instruction set (being only push and arithmetic) we cannot. However, we can easily invent some use case where the destruction of instruction operands is not acceptable. For this we need a "copy" instruction which does exactly what its name suggest and duplicates the top element of the stack.

Another problem arises: what do we do if the elements of the stack are in the wrong order? All of our instructions depend entirely upon the order of values in the stack. If we ever let things get out of order, we can't recover! To solve this stack machines will have the "exchange" operation which pops the top two elements and puts them back in the reverse order.

"But what if I want to get at a value farther down the stack" I hear you say. Well then we need to extend the "copy" instruction to be able to look back down the stack and copy a value to the top of the stack. To do this we'll make copy parametric on the top of the stack, so the index of the copied value is the top of the stack and is popped off.

Now for some Clojure

Now this machine isn't too hard to simulate in software, so I'll present a simple simulator in Clojure. So given an object with an initial stack state, an instruction tape we can define the transition from one state to the next..

1
2
3
4
5
6
7
8
9
10
11
12
13
(defn step
  "Function of a stack-processor-state to a stack-processor-state.
  Takes a state, fetches one instruction, performs whatever
  transforms on the stack and PC are specified by the instruction
  definition and returns the new state."
  [state]
  (let [{:keys [stack tape pc]} state
               instr (get tape pc)]
    (if (keyword? instr)
    ((get @icode-map instr) state)
      (-> "Tried to invoke %s!"
    (format instr)
    (Exception.)))))

running a program in general is then trivial, we simply step from one cycle to the next checking that the machine has not entered a halted state.

1
2
3
4
5
(defn run [state]
  (loop [state state]
     (if-not (halted? state)
         (recur (step state))
         state)))

Now we just need to define some instructions for our processor. We will do this by registering state transforms representing an opcode's effects in a simple map. Because Clojure uses immutable data structures and I'm going to construct this map incrementally this means I have to use an atom to wrap the mutators map and we get this.

1
2
3
4
def icode-map (atom {}))

(defmacro deficode [kwd fn]
  `(swap! icode-map assoc ~kwd ~fn))

Now to complete the processor we just need to add a bunch of instructions. Because the instructions themselves are obvious I'll simply present the addition instruction...

1
2
3
4
5
6
7
8
(deficode :add
  (fn [s]
      (let [{:keys [pc stack tape]} s
           [a b & tail] stack]
    {:tape   tape
     :stack  (cons (+ a b) tail)
     :pc     (inc pc)
     :halted false})))

Now just for grins lets run a test program:

user=> (run {:tape   {0 [:push 1]
                      1 [:push 2]
                      2 [:add]
                      3 [:halt]}
             :pc     0
             :stack  []
             :halted false})
{:tape   {0 [:push 1]
          1 [:push 2]
          2 [:add]
          3 [:halt]}
 :pc     3
 :stack  [3]
 :halted true}
 

While it isn't hard to write a stack machine simulator, or build a hardware stack machine, neither is either especially good or fast. In my next post, I'll discuss why and introduce the basis for most modern computing: the register machine.

^d

Tags