Stack frames and the call stack

Return addresses, parameters and local variables: what a subroutine call pushes, and what a return pops.

A2.1Recursion and computational thinkingA level20 min

At GCSE you wrote subroutines, passed them parameters and used their return values (F4.2), and you saw that a local variable exists only while its subroutine runs (F4.3). You never had to ask how the computer manages that. When patrol calls leg, and leg finishes, how does the processor know where in patrol to carry on? Where do leg's parameters and local variables live, and why do they vanish when it returns? The answer is the call stack, and it is also what makes recursion possible, which is the subject of the next two lessons.

What has to be remembered

When a subroutine is called, three things must be kept somewhere:

• the return address: the place in the calling code to go back to when the subroutine ends;
• the parameters: the values passed in for this call;
• the local variables: the subroutine's own working values, separate from any other call's.

These are stored together in a stack frame (also called an activation record). The frames are kept on a stack, a last in, first out structure, so the frame pushed most recently is always the one on top.

Pushing and popping frames

• A call pushes a new frame onto the stack, holding the return address, the parameters and space for the local variables. Control then jumps to the start of the subroutine.
• While the subroutine runs, it uses the frame on top of the stack. That is why a local variable called total in one subroutine never clashes with a total in another.
• A return pops the top frame. The return address from that frame tells the processor where to continue, and a return value is handed back to the caller. The popped frame's parameters and locals are gone.

Because the most recent call is always the first to finish, a stack is exactly the right structure: the order subroutines end in is the reverse of the order they started.

def leg(cm):
    steps = cm // 5
    return steps

def patrol(laps):
    total = 0
    for i in range(laps):
        total = total + leg(20)
    return total

count = patrol(2)
print(count)

Run this in the simulator

Here is the stack at the moment leg(20) is running for the first time:

When leg returns 4, its frame is popped. Execution goes back to the line in patrol that the return address points to, total becomes 4, and the loop calls leg again, which pushes a brand new frame. When patrol returns 8, its frame is popped and the main program assigns count.

Each call has its own locals

Two frames for two calls mean two separate copies of every local variable, even when the names match:

def inner():
    total = 100
    print("inner total:", total)

def outer():
    total = 5
    inner()
    print("outer total after the call:", total)

outer()

Run this in the simulator

outer's total is still 5 after inner returns, because inner's total lived in a different frame, which has now been popped.

Modelling the stack yourself

A Python list with append and pop behaves as a stack. You can make the hidden call stack visible by pushing your own frame record at the start of each subroutine and popping it at the end:

stack = []

def show(event):
    names = [frame["name"] for frame in stack]
    print(event.ljust(14), names)

def square(x):
    stack.append({"name": "square", "params": {"x": x}, "return_to": "hypot2"})
    show("call square")
    result = x * x
    stack.pop()
    show("return square")
    return result

def hypot2(a, b):
    stack.append({"name": "hypot2", "params": {"a": a, "b": b}, "return_to": "main"})
    show("call hypot2")
    result = square(a) + square(b)
    stack.pop()
    show("return hypot2")
    return result

print(hypot2(3, 4))

Run this in the simulator

The deepest the stack gets is two frames, while square runs inside hypot2. The real call stack has one more frame at the bottom for the main program.

When the stack runs out

The call stack lives in a fixed area of memory. Each call that has not yet returned holds a frame, so a chain of calls that goes too deep uses up that memory. This is a stack overflow, and the program crashes. Ordinary programs rarely get close, but a recursive subroutine with a mistake in it can make thousands of nested calls in a fraction of a second. Python guards against this by stopping any program that goes more than about 1,000 calls deep with a RecursionError, before the real stack is exhausted.

Task: watch the call stack

The starter drives the robot through lap(10), which calls corner twice, and each corner calls beep. Make the call stack visible.

• Keep a list called stack. At the start of every subroutine, push a frame onto it: a dictionary with the keys "name", "params" (a dictionary of parameter name to value) and "return_to" (the name of the caller, or "main" for the call from the main program). Then print push <name> <parameter>=<value>, return to <caller>, depth <d>, where <d> is the number of frames on stack after the push.
• At the end of every subroutine, pop the top frame and print pop <name>, depth <d>, where <d> is the number of frames left.
• Keep track of the deepest the stack gets, and after lap(10) has finished print deepest: <n>.

The first line is push lap size=10, return to main, depth 1 and the last before deepest is pop lap, depth 0. The robot still drives and beeps as before.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

stack = []

def beep(freq):
    tone(freq, 0.2)

def corner(cm):
    forward(50, distance=cm)
    beep(880)

def lap(size):
    corner(size)
    corner(size)

lap(10)

Challenges

1. Draw the stack, frame by frame, at the moment the second beep starts. Which return address is on top?
2. Change lap so it calls corner four times. Does the deepest depth change? Explain why.
3. A subroutine can return before its last line with an early return. What goes wrong with your model if it does, and how would you fix it?