Call stack #

During the execution of a program, the call stack keeps track of ongoing function/method calls:

when a function/method is called, a frame is pushed on top of the stack: the frame stores information about the execution of the function/method (current value of variables, …),

when the execution of the call terminates, the frame is popped from the stack, and control is passed back to the calling function/method (whose frame is now on top of the stack).

Hint. A debugger provides a representation of the successive states of a call stack, with references to the source code. This gives the illusion of source code being interpreted verbatim.

In Haskell #

Warning. We assume here a simplified call stack, for a naive execution.

The Haskell compiler may produce a program that applies a lazy evaluation strategy, which can be more complex. We will not cover this in detail.

Example. Consider the following program:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
main :: IO ()
main = print $
  function1 5 +
  function3 3

function1 :: Int -> Int
function1 x = 2 * function2 x

function2 :: Int -> Int
function2 x = x - 1

function3 :: Int -> Int
function3 x = 4 * x
When the function main is called, it is added (a.k.a. pushed) to the (previously empty) call stack. This can be represented as:
main
When execution “reaches” Line 3, function1 is called (with argument 5) and added to the stack:
function1 5
main : 3          # 3 is a line number here
Then Line 7, function1 calls function2 (with the argument 5 still):
function2 5
function1 5 : 7
main : 3
When the call function2 5 terminates, it returns the value 4 and passes control back to the previous call in the stack (namely function1 5), which can resume its execution:
function1 5
main : 3
When this call terminates, it returns the value 8 and passes control back to the function main, which resumes its execution where it left off:
main
When execution “reaches” Line 4, function3 is called (with argument 3) and added to the stack:
function3 3
main : 4
After the call function3 3 terminates, it returns the value 12, and passes control back to the function main, which can now sum the two values that it received (8 and 12), and print the result.

Recursion and stack overflow #

Note. If a function/method is recursive (i.e. if it calls itself, directly or indirectly), then it may appear multiple times in the call stack. E.g.:
method1
method2 : 16
method1 : 8
<rest of the call stack>

Definition. A stack overflow occurs when the size of the call stack exceeds the capacity allowed by the execution environment. This is usually due to a non-terminating recursive method.