Stack Machines

mini CAML part 1
October 2026

This is the first in a series on implementing a simple CAML language.

Code for this post is available on my GitHub.

Introduction

In this post, we'll introduce the concept of stack machines with two simple examples.

You can skip straight to the simple arithmetic demo, or the arithmetic with variables demo.

Stacks

A stack is a very simple data structure. Despite their simplicity, they are ubiquitous in computer science. A stack is just a container of data with two operations, push and pop. Pushing adds a value to the stack, and popping removes a value. The key behavior that makes stacks so useful is that the value you get from a pop is always the most recently pushed value. This is sometimes described as last-in, first-out or LIFO. The last pushed value is called the top of the stack.

For example, let's say I push 1, push 2, then push 3. Now, if I pop, I get 3. If I pop again, I get 2, and if I pop a final time, I get 1. If I try to pop again, I'd be trying to pop from an empty stack, which is considered invalid. In practice, this means our program crashes or some other bad thing happens. Try adding an extra pop to the following example and see what happens.


                

                

The First Machine

Let's look at a really simple language. The only expressions are integers and (binary) addition. So we have expressions like 1 and ((2 + 3) + 4).

Now we'll define a very simple corresponding stack machine. In this case, this means we are defining a set of instructions, and later we'll define how to execute those instructions.

For now, we have just two instructions Push(n), where Push takes a single integer argument, and add. All of our “programs” will just look like sequences of instructions. Push(3); Push(4); add.

Now we define a compilation scheme. This tells us how to translate expressions into a sequence of instructions.

1. [[    n    ]] = Push(n)
2. [[ E1 + E2 ]] = [[ E1 ]]; [[ E2 ]]; add

In words, this says

  1. if we see an integer, add a Push instruction for that number
  2. if we see addition, compile the left, then the right, and then an add instruction

The idea here is to define rules that tell us how to turn an expression on the left, into concrete instructions on the right.

Now we can define how our machine will actually carry out these instructions. Our machine has a stack of numbers which is initially empty. It then reads through the instructions one at a time, manipulating the stack according to the current instruction. Hopefully the Push instruction is self-explanatory, it just pushes that number onto the stack. The add instruction pops two values from the stack, and pushes their sum. In other words, it's shorthand for pop; pop; push (something + something).

With just these two rules, we can already compile simple expressions.

[[ 1 + 2 ]]
[[ 1 ]]; [[ 2 ]]; add  // rule 2
Push(1); [[ 2 ]]; add  // rule 1
Push(1); Push(2); add  // rule 1
[[ (1 + 2) + 3 ]]
[[ (1 + 2) ]];         [[ 3 ]]; add  // rule 2
[[ 1 ]]; [[ 2 ]]; add; [[ 3 ]]; add  // rule 2
Push(1); [[ 2 ]]; add; [[ 3 ]]; add  // rule 1
Push(1); Push(2); add; [[ 3 ]]; add  // rule 1
Push(1); Push(2); add; Push(3); add  // rule 1

If we were to use more familiar notation, writing just 3 instead of Push(3) and + instead of add, we would get 1 2 + 3 +. You might be more familiar with this as reverse-Polish notation (RPN).

If you're familiar with tree traversals or RPN, you might recognize this as a post-order traversal of the expression, and the stack is what lets the machine keep track of the intermediate results along the way.

Let's add some more rules for subtraction and multiplication. In fact, let's just add a single Prim instruction (short for “primitive operation”) which takes the specific operation as an argument.

2. [[ E1 + E2 ]] = [[ E1 ]]; [[ E2 ]]; Prim(add)
3. [[ E1 - E2 ]] = [[ E1 ]]; [[ E2 ]]; Prim(sub)
4. [[ E1 * E2 ]] = [[ E1 ]]; [[ E2 ]]; Prim(mul)

These instructions are interpreted in straightforward ways as well. Prim(add) still just pops two values from the stack and pushes their sum. Similarly Prim(sub) pops two values from the stack and pushes their difference. However, we have to be careful here. Since subtraction is non-commutative, we need to know which value we are subtracting from. In our case, we read the instructions for the left hand side before the right hand side, which means the right hand value will be the top of the stack, and the left below that. So Push(1); Push(2); Prim(sub) should pop (getting 2), then pop again (getting 1) and then push (1 - 2) instead of (2 - 1).

Let's also add a unary operator, negation.

5. [[ - E ]] = [[ E ]]; Prim(negate)

Unlike our previous operations, this instruction will pop just a single value, and then push the negation of that value.

So our final machine still has only two instructions, Push and Prim, each taking a single argument, with behavior defined for each primitive operation.

Let's walk through a slightly more complex example with this updated set of instructions.

[[ (1 + ((- 2) * 3)) - 4 ]]
[[ 1 + ((- 2) * 3) ]];                                         [[ 4 ]]; Prim(sub)  // rule 3
[[ 1 ]]; [[ (- 2) * 3 ]];                           Prim(add); [[ 4 ]]; Prim(sub)  // rule 2
Push(1); [[ (- 2) * 3 ]];                           Prim(add); [[ 4 ]]; Prim(sub)  // rule 1
Push(1); [[ - 2 ]];             [[ 3 ]]; Prim(mul); Prim(add); [[ 4 ]]; Prim(sub)  // rule 4
Push(1); [[ 2 ]]; Prim(negate); [[ 3 ]]; Prim(mul); Prim(add); [[ 4 ]]; Prim(sub)  // rule 5
Push(1); Push(2); Prim(negate); [[ 3 ]]; Prim(mul); Prim(add); [[ 4 ]]; Prim(sub)  // rule 1
Push(1); Push(2); Prim(negate); Push(3); Prim(mul); Prim(add); [[ 4 ]]; Prim(sub)  // rule 1
Push(1); Push(2); Prim(negate); Push(3); Prim(mul); Prim(add); Push(4); Prim(sub)  // rule 1

Below is a demo which lets you enter an expression and see the stack machine calculate the final answer.

Demo


            

            

            

The Second Machine

One issue with our previous calculator machine is that we can't store and reuse intermediate answers. And this is a shame because every intermediate value is computed on the stack, but we lose it once we encounter the next operation.

For example (1 + 2) * (1 + 2), we recompute the expression 1 + 2 twice. It would be nice if we could say “compute 1 + 2, then reuse that answer twice”. To accomplish this, we'll add a new kind of expression to our language called a let expression.

let x = 1 + 2 in
    x * x

The let x = part is called a let binding, since it binds a value (in this case 1 + 2) to a variable (x).

But how do we actually do this? We're clearly going to need some more instructions, but what exactly?

As we noted before, intermediate calculations are available on the stack. The problem is that they get lost once we encounter the next operation. So we'll need to be able to copy that value “somewhere else”, and read it again later.

But where should we put it?

Scope

Consider the following examples.

1. let x = 1 in x + ( let y = 2 in x + y ) + x

Notice that the scope of y, that is, the region where a reference to y is valid, starts after the scope of x, but also ends before it. This is true in general, the last scope we entered will always be the first one we leave. In other words, scope is always last-in, first-out. Which is exactly how a stack behaves! So, we'll store intermediate values into another stack, called the environment. When we enter a let, we push a value onto the environment, and when we leave it, we pop that value off. This means the environment always holds the variables that are currently in scope.

But how do we actually refer to the values in the environment? We could just associate the name directly to a value somehow. But this doesn't take advantage of the stack-like behavior of scopes, and introduces other complexity, for instance the problem of shadowing. In let x = 1 in (let x = 2 in x), we have two variables called x, but they are bound to different values in different scopes. Instead we'll use an old trick.

de Bruijn indices

The trick we'll use is called a de Bruijn index, named for the Dutch mathematician Nicolaas G. de Bruijn.

The de Bruijn index of a variable is the number of let bindings we have to move back through to reach the definition of that variable. In other words, how many scopes ago was I introduced? This sounds confusing but is fairly straightforward.

In let x = 1 in x, the variable x is referenced in the scope it was introduced, So it has an index of 0.

    ┌──────────┐
    │         ─┴
    ▼         #0
let x = ... in x

Now consider nested let expressions.

    ┌──────────┐         ┌──────────┐
    │         ─┴         │         ─┴
    ▼         #0         ▼         #0
let x = ... in x + ( let y = ... in y + x )
    ▲                                  #1
    │                                  ─┬
    └───────────────────────────────────┘

The first x still has an index of 0, for the same reason as the previous example. As does the use of y. But the second use of x has an index of 1, since it is being referenced inside of the inner scope.

This also makes references completely unambiguous, since we no longer care about the names of variables at all!

Since we push a value onto the environment whenever we enter a new scope, the index of a variable corresponds exactly to the how far the value of that variable is from the top of the environment. An index of 0 means that value is on top, while an index of 1 means 1 below the top, and so on.

So, we need three new instructions. Bind will mean pop from the stack, and push that value into the environment. This represents entering a new scope. Drop will mean pop from the environment, and representing leaving a scope. And finally Access will take a single argument, an index, and will mean copy a value from the environment and push that onto the stack. This represents reading the value of a variable.

Despite the increase in expressive power this gives us, we only need to add 2 new rules for compilation.

6. [[ x ]]                = Access(i)  // where i is the de Bruijn index of x
7. [[ let x = E1 in E2 ]] = [[ E1 ]]; Bind; [[ E2 ]]; Drop

Let's walk through compiling the example from before.

[[ let x = 1 + 2 in (x * x) ]]
[[ 1 + 2 ]];                 Bind; [[ x * x ]];                     Drop  // rule 7
[[ 1 ]]; [[ 2 ]]; Prim(add); Bind; [[ x * x ]];                     Drop  // rule 2
Push(1); [[ 2 ]]; Prim(add); Bind; [[ x * x ]];                     Drop  // rule 1
Push(1); Push(2); Prim(add); Bind; [[ x * x ]];                     Drop  // rule 1
Push(1); Push(2); Prim(add); Bind; [[ x * x ]];                     Drop  // rule 4
Push(1); Push(2); Prim(add); Bind; [[ x ]];   [[ x ]];   Prim(mul); Drop  // rule 4
Push(1); Push(2); Prim(add); Bind; Access(0); [[ x ]];   Prim(mul); Drop  // rule 6
Push(1); Push(2); Prim(add); Bind; Access(0); Access(0); Prim(mul); Drop  // rule 6

Try playing with the demo below, and notice how the second stack lets us reuse calculations.

Demo