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
Context as data structure
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.