The Call Stack - Hidden Foundation of Functional Programming

In computer science, the stack is an important concept. In reality also, the stack is a crucial part of the execution of an assembly program written in a higher-level language. From clicking a button on screen to sending a payload to space, the concept of a stack plays a major part. Pioneered and popularized by brilliant minds like Edsger Dijkstra in the mid-20th century, it provided a robust and efficient way for compilers to handle memory and control.

Let's start with the concept of a stack. Imagine a stack of plates in your house: you can only add a new plate to the top, and you can only take the top plate off. This "Last-In, First-Out" (LIFO) principle is how the stack works. In your computer, a similar thing happens every time you call a new function, declare a variable, or return from a function.

A stack of plates [AI generated]

We can visualize the memory as a tall shelf with thousands of tiny drawers that can hold a 'byte' of data. Now, it is important to manage this memory efficiently to take the best out of the system and to mitigate mistakes. This is where memory management comes into play.

A stack of drawers [AI generated]

The Stack, in the sense of computer memory management, is one such strategy. Now think of the plate analogy we discussed before, and the assign the same ruleset to the tall 'memory' shelf. You have to start from the bottom most drawer. You can only put a 'byte' into the drawer above the one last filled. And you can only take the topmost one at a time.

Typical SRAM structure of the ARM memory

Just like that, the memory allocated to the stack is only accessible in the above discussed way. Think of the stack as a dedicated workspace for managing critical information. The stack is crucial to handle:

• Function Calls: Every time a function is called, its details are 'pushed' onto the stack. When the function finishes, its information is 'popped' off.

• Local Variables: The temporary data a function needs to do its job is stored right there on the stack.

• Program Flow: It's the stack that ensures your program returns to the exact spot it left off after completing a task or jumping to a different part of the code.

Now we will see how the Stack works. In real memory, the stack starts from the highest available memory address and move down. To further understand how the stack behaves, we will use a sample C code as an example.

int square(int num) {
    int result = num * num;
    return result;
}

int main() {
    int x = 2;
    square(x);
}

The compiled x86-64 Clang Assembly code is as below.

square:
    push rbp
    mov rbp, rsp
    mov dword ptr [rbp - 4], edi
    mov eax, dword ptr [rbp - 4]
    imul eax, dword ptr [rbp - 4]
    mov dword ptr [rbp - 8], eax
    mov eax, dword ptr [rbp - 8]
    pop rbp
    ret

main:
    push rbp
    mov rbp, rsp
    sub rsp, 16
    mov dword ptr [rbp - 4], 2
    mov edi, dword ptr [rbp - 4]
    call square
    xor eax, eax
    add rsp, 16
    pop rbp
    ret

If you analyse the code, every time we switch functions, we're pushing the Base Pointer (RBP) onto the stack. Then we change the RBP to the current Stack Pointer (RSP). This way, we know where to return to after the function executes and returns. On the other hand, we create space for all the local variables of that function within the stack as soon as we're done with it. After execution, the stack pops all of that data and move back to where we started.

This is better visualized in the below animation.

From the simplest script to the most complex operating system, the stack is silently working behind the scenes, ensuring that our digital world runs smoothly and predictably. It's a testament to how some of the most powerful and enduring ideas in computing are rooted in simple, yet effective, abstractions.

Reference:

• Wikipedia article on the Stack data type: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

• Wikipedia article on the Call Stack: https://en.wikipedia.org/wiki/Call_stack

• Code sample on Compiler Explorer: https://godbolt.org/z/1vddacPM3