Fibonacci laziness

In this example, we will examine the lazy behaviour of the zipWith implementation for the fibonacci sequence. You can also open this for yourself in the simulator.

Note: Figures 6 and 7 are not marked in the simulator, but are 1 step further than figures 4 and 5, respectively.

The basic idea of the implementation is using zipWith to traverse the sequence and generate the next element when necessary. In the STG language, this could be implemented like this:

zero = CON(Num 0)
one = CON(Num 1)
-- let main = 0 : 1 : zipwith (+) fib (tail fib)
main = THUNK(letrec	fib0 = CON(Cons zero fib1)
					fib1 = CON(Cons one fib2)
					fib2 = THUNK(zipWith plusInt fib0 fib1)
			in fib0)

Initial state

As main is entered, the initial list is created, and a thunk is created for the zipWith call.

Expanding the sequence

When the tail of 0x7 is entered, zipWith executes and allocates thunks on the heap, corresponding to the next element (0x9) and the spine (0xa) of the sequence.

Expanding it further

Note that at this point, the calculation of the next element still hasn’t been performed. In fact, as long as we are following the spine of the sequence, no element will be calculated.

Triggering the calculations

When we stop following the spine and enter one of the elements, the calculation(s) will finally be performed, and the thunk(s) will be updated. Entering an element is effectively calling the plusInt function:

plusInt = FUN(x y -> 
	case x of {
	Num i -> case y of {
			Num j -> case  i +# j of {
						x -> let result = CON(Num x)
							in result;
					};
			};
	}
)

Now we can check out what is happening with the stack. When we entered 0xf an update frame was pushed on, and plusInt started executing with x=0x9 and y=0xc.
Before plusInt starts to scrutinize x, it must save any other locals it still needs, and pushes them onto the stack alongside the case continuation (figure 4).
A similar thing happens when y becomes the scrutinee; i must be saved with the case continuation, and y is entered (figure 5).