The call stack

Calling functions

When the CPU runs code it fetches instructions and executes them.

Code can change the flow of control using jump instructions that change the program counter.

This is enough to implement basic control constructs such as if and while.

But what about calling functions/methods?

Simple calls

public void main() {
  foo(10, 20);
}
public void foo(int a, int b) {
  bar(a * 10, b);
}
public void bar(int a, int b) {
}

Local variables

public void main() {
  int x = 1;
  foo(x);
}
public void foo(int a) {
  int b = a * 2;
  b = b + 1;
}

Return values

public void main() {
  int x = add(10, 20);
}
public int add(int a, int b) {
  int sum = a + b;
  return sum;
}

Assigning a result

public void main() {
  int x = 0;
  x = square(5);
}
public int square(int n) {
  return n * n;
}

Nested calls

public void main() {
  int y = square(add(1, 2));
}
public int add(int a, int b) {
  return a + b;
}
public int square(int n) {
  return n * n;
}

Recursion

public void main() {
  int x = factorial(3);
}
public int factorial(int n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

Fibonacci

public int fib(int n) {
  if (n < 2) {
    return n;
  }
  return fib(n - 1) + fib(n - 2);
}

Fibonacci, iteratively

public void main() {
  int x = fib(4);
}
public int fib(int n) {
  return fibHelper(n, 0, 1);
}
public int fibHelper(int n, int a, int b) {
  if (n == 0) {
    return a;
  }
  return fibHelper(n - 1, b, a + b);
}

Tail call optimization

public void main() {
  int x = fib(4);
}
public int fib(int n) {
  return fibHelper(n, 0, 1);
}
public int fibHelper(int n, int a, int b) {
  if (n == 0) {
    return a;
  }
  return fibHelper(n - 1, b, a + b);
}

Tail call optimization is a way the compiler can optimize calls that occur in the tail position meaning that there is no more computation to do after they return—whatever value the callee returns will be returned by the caller.

This is a simplified model.

In particular, we are ignoring the registers.

When one function calls another, there are probably values in registers that that function is using but the new function may also need to use those same registers.

So what actually happens is the values of registers are copied to the stack as part of the function calling machinery.

The exact details are determined by a combination of things dictated by the CPU architecture and the operating system.

Some registers are saved by code a function before it calls another (caller-saved registers) and restored after the call returns and others are saved by the callee (callee-saved registers) and restored by the callee before returning.