4.16 Function-Call Stack

To understand how Python performs function calls, consider a data structure (that is, a collection of related data items) known as a stack, which is like a pile of dishes. When you add a dish to the pile, you place it on the top. Similarly, when you remove a dish from the pile, you take it from the top. Stacks are known as last-in, first-out (LIFO) data structures—the last item pushed (that is, placed) onto the stack is the first item popped (that, is removed) from the stack.

Stacks and Your Web Browser’s Back Button

A stack is working for you when you visit websites with your web browser. A stack of web-page addresses supports a browser’s back button. For each new web page you visit, the browser pushes the address of the page you were viewing onto the back button’s stack. This allows the browser to “remember” the web page you came from if you decide to go back to it later. Pushing onto the back button’s stack may happen many times before you decide to go back to a previous web page. When you press the browser’s back button, the browser pops the top stack element to get the prior web page’s address, then displays that web page. Each time you press the back button the browser pops the top stack element and displays that page. This continues until the stack is empty, meaning that there are no more pages for you to go back to via the back button.

Stack Frames

Similarly, the function-call stack supports the function call/return mechanism. Eventually, each function must return program control to the point at which it was called. For each function call, the interpreter pushes an entry called a stack frame (or an activation record) onto the stack. This entry contains the return location that the called function needs so it can return control to its caller. When the function finishes executing, the interpreter pops the function’s stack frame, and control transfers to the return location that was popped.

The top stack frame always contains the information the currently executing function needs to return control to its caller. If before a function returns it makes a call to another function, the interpreter pushes a stack frame for that function call onto the stack. Thus, the return address required by the newly called function to return to its caller is now on top of the stack.

Local Variables and Stack Frames

Most functions have one or more parameters and possibly local variables that need to:

• exist while the function is executing,

• remain active if the function makes calls to other functions, and

• “go away” when the function returns to its caller.

A called function’s stack frame is the perfect place to reserve memory for the function’s local variables. That stack frame is pushed when the function is called and exists while the function is executing. When that function returns, it no longer needs its local variables, so its stack frame is popped from the stack, and its local variables no longer exist.

Stack Overflow

Of course, the amount of memory in a computer is finite, so only a certain amount of memory can be used to store stack frames on the function-call stack. If the function-call stack runs out of memory as a result of too many function calls, a fatal error known as stack overflow occurs.⁵ Stack overflows actually are rare unless you have a logic error that keeps calling functions that never return.

5. This is how the website stackoverflow.com got its name—a good website for getting answers to your programming questions.

Principle of Least Privilege

The principle of least privilege is fundamental to good software engineering. It states that code should be granted only the amount of privilege and access that it needs to accomplish its designated task, but no more. An example of this is the scope of a local variable, which should not be visible when it’s not needed. This is why a function’s local variables are placed in stack frames on the function-call stack, so they can be used by that function while it executes and go away when it returns. Once the stack frame is popped, the memory that was occupied by it can be reused for new stack frames. Also, there is no access between stack frames, so functions cannot see each other’s local variables. The principle of least privilege makes your programs more robust by preventing code from accidentally (or maliciously) modifying variable values that should not be accessible to it.

Self Check

1. (Fill-In) The stack operations for adding an item to a stack and removing an item from a stack are known as       and      , respectively.
   Answer: push, pop.

2. (Fill-In) A stack’s items are removed in       order.
   Answer: last-in, first-out (LIFO).