Rewriting and the Call Stack

In this note we will look a bit closer at the computational model behind functional programming.

In simplest terms, the computational model of functional programming is equational reasoning as we know it from high-school algebra: variables are immutable and a computation step is simply replacing equals by equals.

Rewriting is a special kind of equational reasoning in which we apply equations only from left to right.

The call stack is a device to make such computations more efficient.

Let us look at an example. (We start with a review, jump here to skip.)

Recall the Definition of

$fib$

$$\begin{array}{rl}fib(0)& =0\\ fib(1)& =1\\ fib(n+2)& =fib(n)+fib(n+1)\end{array}$$

One difference to high-school algebra is that we are only allowed to apply these equations from left to right. This helps us not to get trapped in an infinite loop.

To see that this definition can be run on a machine head over to replit for a Haskell implementation.

The purpose of this note is to learn how to run a virtual machine executing the Haskell code using a pen-and-paper computation.

Computing

$fib(6)$ via Rewriting Equations

Justify each of the equations below.

$$\begin{array}{rl}fib(6)& =fib(4)+fib(5)\\ & =fib(2)+fib(3)+fib(5)\\ & =fib(0)+fib(1)+fib(3)+fib(5)\\ & =0+fib(1)+fib(3)+fib(5)\\ & =fib(1)+fib(3)+fib(5)\\ & =1+fib(3)+fib(5)\\ & =1+fib(1)+fib(2)+fib(5)\\ & =1+1+fib(2)+fib(5)\\ & =2+fib(2)+fib(5)\\ & =2+fib(0)+fib(1)+fib(5)\\ & =2+0+fib(1)+fib(5)\\ & =2+fib(1)+fib(5)\\ & =2+1+fib(5)\\ & =3+fib(5)\\ & =3+fib(3)+fib(4)\\ & =3+fib(1)+fib(2)+fib(4)\\ & =3+1+fib(2)+fib(4)\\ & =4+fib(2)+fib(4)\\ & =4+fib(0)+fib(1)+fib(4)\\ & =4+0+fib(1)+fib(4)\\ & =4+fib(1)+fib(4)\\ & =4+1+fib(4)\\ & =5+fib(4)\\ & =5+fib(0)+fib(1)+fib(3)\\ & =5+0+fib(1)+fib(3)\\ & =5+fib(1)+fib(3)\\ & =5+1+fib(3)\\ & =6+fib(3)\\ & =6+fib(1)+fib(2)\\ & =6+1+fib(2)\\ & =7+fib(2)\\ & =7+fib(0)+fib(1)\\ & =7+0+fib(1)\\ & =7+fib(1)\\ & =7+1\\ & =8\end{array}$$

Ok, this is extremely boring … but it doesn't matter, we have a computer to do this for us. You should do this pen-and-paper only a few times to get a feel for it … or to debug your programs.

Rewriting via a Call Stack

In the computation above, we do a lot of copying. For example,

$fib(5)$ is copied 13 times. This is clearly redundant. To implement such computations on a machine we want to avoid such obvious redundancies.

How can we do this?

While our model of computation^[1] for functional programming is based on rewriting expressions instead of on modifying memory, it can be (and actually is) implemented on a conventional von Neumann architecture such as the one you have on your laptop.

We thus can use memory to maintain a data structure called a stack and use the stack to store only the part of the data we actually need to keep continuing with the computation.

In these notes, I draw my stacks growing top-down^[2] so that we see more clearly how the data stored on the stack aligns with the call tree

​​​​                    fib(6)
​​​​                   /      \
​​​​             fib(4)        fib(5)
​​​​              / \           / \
​​​​         fib(2) fib(3) fib(3) fib(4)
​​​​          ...    ...    ...    ...

Go back and look at the equational reasoning above.

We start with the first line

$fib(6)=fib(4)+fib(5)$ and put it on the stack.

​​​​fib 6 = fib 4 + fib 5

Next, we need to compute

$fib(4)$, so we put a new equation on the top of the stack (recall that I write the top of the stack at the bottom as I grow stacks downwards):

​​​​fib 6 = fib 4 + fib 5
​​​​fib 4 = fib 2 + fib 3

Note that, even though I rewrote fib 4 I didn't copy fib 5. Instead I remember fib 5 by "putting fib 4 on top of the stack".

Next I choose to rewrite fib 2, so we keep growing the stack:

​​​​fib 6 = fib 4 + fib 5
​​​​fib 4 = fib 2 + fib 3
​​​​fib 2 = fib 0 + fib 1

At this point we know the values of fib 0 and fib 1

​​​​fib 6 = fib 4 + fib 5
​​​​fib 4 = fib 2 + fib 3
​​​​fib 2 = 0 + 1

and can do the computation

​​​​fib 6 = fib 4 + fib 5
​​​​fib 4 = fib 2 + fib 3
​​​​fib 2 = 1

Now we reached an important point. So far we only increased the depth of the stack. But now we can "go back up in the call tree", or, in other words, return from our computation of fib 2. That is, in the line starting with fib 4 we replace fib 2 by its value:

​​​​fib 6 = fib 4 + fib 5
​​​​fib 4 = 1 + fib 3

Let me repeat that the last step made the stack smaller. We also say that we popped the equation fib(2) = ... (in technical lingo this is called popping the current stack frame).

From now on we just keep on following the same procedure. Our current aim is to complete the computation of fib 4. To this end, we call fib 3 and put its definition on the top of the stack:

​​​​fib 6 = fib 4 + fib 5
​​​​fib 4 = 1 + fib 3
​​​​fib 3 = fib 1 + fib 2

And so on it goes.

Exercise/Activity: Finish the computation using the call stack.

(It is called a call stack because it stacks the calls to the function fib.)

Notice how at each point in time the stack contains (a part of) one of the branches of the call tree.

Exercise: In which order does the call stack traverse (= go through) the call tree?

Recall that in the equational reasoning we copied

$fib(5)$ many times. Note how, using a call stack, we do not copy fib 5 at all. I agree, on the page it looks as if we did copy fib 6, fib5, etc. But this is only because I am showing you a stop-motion animation of the stack. All of the seven snapshots show the same stack through time and equations such as fib 6 = fib 4 + fib 5 are not actually copied.

Computing with a call stack works well on a blackboard (or in an editor) as one can pop elements from the stack simply by using the eraser (or using cut/copy/paste).

Important Remark:

• The time complexity of
  $fib$ is exponential because the size of the call tree of
  $fib(n)$ is exponential in
  $n$. This suggests that space complexity might also be exponential. The call stack is a way to keep the space complexity linear. We see here a typical example of a situation where the time complexity is exponentially larger than the space complexity. (If you took Algorithm Analysis this should sound familiar.)
• Fibonacci, like many recursive programs, can be made more efficient using memoization (aka dynamic programming). See here for a Haskell example.

---

1. We could call this model of computation the Haskell Virtual Machine (HVM), but this is not official terminology. ↩︎

2. It might be more apt to call this data structure a cellar instead of astack (and that was the terminology I learned back in Germany in the 1990ies as and undergrad). ↩︎