The (call) stack

It’s not uncommon to hear programmers talk about ’the stack’ when they’re referring to functions or variables. One of, if not the, most popular sites for programmers, stackoverflow, is even named after a common error involving ’the stack'.

What is ’the stack'?

For starters, it’s a stack data structure just like the name implies: a last-in, first-out (LIFO), data store that has two key operations: push and pop.

The stack API could look like this if called from Javascript:

var s = new Stack();

s.push("a");
s.push("b");
s.push("c");

s.pop(); //=> "c"
s.pop(); //=> "b"
s.pop(); //=> "a"

Where is ’the stack'?

When a program runs, the operating system gives the program a large amount of addressable memory to work with. The program can’t use this memory arbitrarily, but this does serve as the landscape that the program will operate in.

‘The stack’ is just a stack that the operating system sets up for us in this landscape (usually at one end of the landscape). However, since ’the stack’ lives in addressable memory, it has one more special property: we can look at an item at any position on ’the stack’.

Stack and Frame pointers

When the program starts executing, the operating system also sets up two special variables for us, the stack pointer and the base pointer (sometimes referred to as the frame pointer).

The stack pointer is the only variable needed to implement push and pop; the frame pointer is used to make some calculations easier, but we’ll cover that in detail elsewhere.

When do we use ’the stack'?

So we know that ’the stack’ supports push and pop, but when do we push and pop?

Simply speaking, we push whenever we call a function (hence, call stack), and we pop whenever a function returns.

Say we have the following javascript:

function a() { return 1; }
function b() { a(); return 2; }

b();

Our program starts, and the stack is empty (we’ll tag the outermost item for clarity):

*program*

The first function call we see is b(); at the bottom of the program, so we push *b*, now the stack looks like:

*program*
*b*

Now we’re executing b, and in the body of b, we see a call to a(), so we push *a*:

*program*
*b*
*a*

a doesn’t call a function, but does return, so we pop *a*:

*program*
*b*

After a() has finished, we continue inside of b and return, so we pop *b*:

*program*

This illustrates the key purpose of the stack: it’s a way for the computer to keep track of where it should go when it’s done with a function (e.g. when a finished, the computer looked at the stack after pop-ping and saw that it should go back into b.

The stack can be used for additional purposes, but the reason it exists at all is to keep track of which function should be active when the current function returns.

Digression: stack overflow errors

Now that we know what the stack does, what exactly is a stack overflow? As the name may imply, it’s an error that happens when the stack gets too big and consumes more memory than our program has available.

Generally, this happens when there are too many items pushed onto the stack (i.e. it becomes too deep). This is almost always because of a recursive call (either individual, i.e. a function a calling itself; or mutual, i.e. a function a calls function b which calls function a).

For example:

function a() { a(); }
a();

This will run and cause the stack to look like:

*program*
*a*
*a*
.
.
.
*a*

Eventually, this will exhaust the memory that the operating system has set aside for the program, and it will get terminated.

Digression: Implementing a stack with only one variable

I mentioned above that the only variable we need to implement the stack is the stack pointer. This is fasible because the beginning location of the stack is set up for us by the OS.

When the program is started, the operating system thoughtfully sets up the stack pointer to contain the address of memory where the next item in the stack should go (sidenote: accessing memory addresses and getting an item at an index of an array are functionally equivalent, so I usually think of the memory given to us by the OS as a big, empty array, and the stack pointer as an index in that array).

When we start, our stack and stack pointer look like:

    Stack:
    ---------------------------------------------------------
    |     |     |     |     |     |     |     |     |     |  ...
    ---------------------------------------------------------
       0     1     2     3     4     5     6     7     8      
       ^
   
   Stack Pointer: 0

When we push, we write whatever we’re pushing to the location pointed to by stack pointer, and we increment stack pointer

For example, push("a"):

    Stack:
    ---------------------------------------------------------
    | "a" |     |     |     |     |     |     |     |     |  ...
    ---------------------------------------------------------
       0     1     2     3     4     5     6     7     8      
             ^
   
   Stack Pointer: 1 // Incremented from 0

push("b"):

    Stack:
    ---------------------------------------------------------
    | "a" | "b"  |     |     |     |     |     |     |     |  ...
    ---------------------------------------------------------
       0     1     2     3     4     5     6     7     8      
                   ^
   
   Stack Pointer: 2 // Incremented from 1

To pop, we first decrement the stack pointer, and then we remove whatever is in the location pointed at by stack pointer. E.g. pop():

    Stack pointer: 1 // Decremented from 2

    Stack:
    ---------------------------------------------------------
    | "a" |     |     |     |     |     |     |     |     |  ...
    ---------------------------------------------------------
       0     1     2     3     4     5     6     7     8      
             ^

    Return "b"

If you found this interesting or if I could have stated something more clearly, let me know on twitter or shoot me an email.