Let's Take Control of Continuations

You drew first blood on continuations last time. Now it's time to finish them. It's time to take control of control flow.


What is a continuation? A continuation is a function that represents what to do next. When you transform a program into continuation-passing style you add an explicit argument to every function that represents the continuation. Instead of returning normally you can call the continuation on the value you want to return. The continuation represents what to do next with the value.

A function can also recursively call itself in CPS, but you can't build more control flow context. Instead you have to directly call the function recursively with a more complicated continuation.

In other words for a function f you can't do a recursive call like 1 + f(n - 1) since that would build context. Instead you build up the context in the explicit continuation you pass in the recursive call to f.

Context as data structure

One big advantage of making the control flow explicit in the continuation function is that it becomes regular data rather than data on a stack. Last time we saw some more tricks with thunks and trampolining that let us use this fact to transcend the limitation of JavaScript stack sizes.

This time we'll see even more uses. By making control flow into regular data, we can start playing tricks on the control flow. We'll see tricks like stopping and starting however we want, arbitrarily moving the point of execution wherever we want, and implementing multiple virtual threads of execution.

Single step interpreter

Let's start by trying to construct an interpreter that can single step through the execution of a program. To make single stepping work we would like to have some sort of data structure that keeps track of the current state of the program and a function step that advances the evaluation of the state by one step. The step function should update the state and return a value that indicates whether the program is finished or not.