2013-07-08: What is a Stack?

It is common for programming language implementations to use stacks to implement function call and return. It is also common for novice programmers to misunderstanding the meaning of stacks in this context. This post explains how they are used and what the common misunderstanding is.

-

1 A Language without Functions

Our programming languages are implemented by compilation to low-level CPU languages that lack almost all forms of abstraction including functions. Functions encapsulate many forms of abstraction, but the main one is control-flow. The code (begin (f) (g)) abstracts executing the code of f followed by g, as opposed to directly inserting that code into the begin block.

In order to demonstrate this better, let’s use a little interpreter for a CPU-like language. In this language, we’ll have a small number of instructions and a bunch of registers.

This program performs two additions and returns the result:

The LOAD instruction has a destination register first and a value second. The ADD instruction has the destination register and then the source registers. EXIT has a status source register as its argument.

This program has no control-flow other than "execute the next instruction after this one". If we had GOTO and labels, then we could write a program like this:

2 A Language with Functions

However, GOTOs like this aren’t really like function calls, because the first block directly calls the second block. We really want code more like:

What’s the difference between CALL and GOTO? A CALL is a GOTO that records its next instruction on a stack. In the interpreter, it runs

before it jumps to the given label. In contrast, RETURN rather than jumping to (add1 PC) jumps to

which was previously pushed by the CALL.

3 The Misunderstanding

In our example program, when the code for first is running, the stack contains a program address from the main block. main called first so it may seem that the stack contains an abstraction of the past of the computation.

This idea inspires many novice programmers to believe that stack traces (read-outs of the stack) are useful tools for determining how the currently running code started executing, i.e. its history.

However, this is incorrect.

The stack does not record the past of the computation, it only records its future. The address that CALL pushes on to the stack has never been executed and will only execute when RETURN runs. If the past of the computation contains any branches that have already returned, then the stack will hide these, such as in the code for second.

We can change our interpreter to remember the exact program history and allow us to export it (along with the stack) to compare them.

As you can see, in the history of the second export, you can see that first (PC 6–11) is recorded, but the stack only contains main (PC 12–14).

4 The Understanding

Once we realize that stacks are future and not history, tail-call optimization becomes much more clear: if a computation adds nothing to the future, it doesn’t need to add anything to the stack.

For example, in this program, first calls second and does nothing with the result:

It is trivial to recognize this situation, because it corresponds to a computation that contains the sequence (CALL label) (RETURN). We can just change it to (GOTO label).

We can see that in the history of the second version, it doesn’t execute PC 9 after 12, but more important it doesn’t allocate any stack space for the call inside first.

5 Yo! It’s almost time to go!

But first let’s remember what we learned today!

CPUs don’t give you functions, but they do give you instructions like CALL and RETURN which can be used to implement functions.

The stack (as used by CALL/RETURN) records the future of your computation. Stack traces are, therefore, a reading of a potential future (only potential because of real-world features like exceptions and continuations) and have nothing to do with the past of the computation.

If you want to know the history of your computation, you have to get it some other way—the stack doesn’t provide it.

If you’d like to run this exact code at home, you should put it in this order: