Chapter 6 Continuations and the CPS transformation

Different Notions of Continuation

1. Continuation of a program point: It is the sequence of steps left to be performed once execution reaches that program point.
2. Continuation of a subexpression: In functional programming languages, all programs are expressions and so a program point is the end of evaluation of a subexpression. The continuation of a subexpression takes the value of the subexpression and feeds it into the rest of the program. Continuation of subexpression $e$ of a program $p$ is a function that maps value of $e\to$ value of $p$ .

The CPS transformation

Functions that are written in continuation passing style (CPS) take a function (continuation) as one of the arguments and end with calling the continuation with a value. The result of the continuation then becomes the result of the function. We can get a value from such a function by passing it the identity function as continuation i.e. $\lambda x.x$

The CPS transformation takes an expression $e$ and converts it to a function in continuation-passsing-style $\lambda k\dots$ where:

• $k$ is the continuation
• The body computes the result of $e$ and then calls $k$ with the result

We’ll see the CPS transformation for call by value programming languages. Here, expressions are evaluated to a value before passing them to a function as arguments. $C$ is the CPS transformation and it is defined on a case-by-case basis

$C(c)=\lambda k.kc$ $C(x)=\lambda k.kx$ The transformation of a constant and a variable is just applying the continuation to the value. $C(\lambda x.e)=\lambda k.k(\lambda x.C(e))$ The transformation of a function is more interesting. To start with it takes a continuation and supplies it with a function. The supplied function then takes a variable and returns an expression, but in the continuation passing style. This is done because a program written in continuation passing style will expect expressions in the same style.

What happens if we don’t transform the body of function to CPS style? Suppose we had a function $\lambda x.(x+1)$ which we transform to CPS style as $\lambda k.k(\lambda x.(x+1))$ . When a caller calls it with a continuation it expects a function to which it can pass a continuation, but here it gets $\lambda x.(x+1)$ instead. If we transformed the expression also, we’d have gotten $\lambda x.\lambda k.k(x+1)$ and the caller can pass a continuation to this! $C(e_1{e}_2)=\lambda k.C(e_1)(\lambda v_1.C(e_2)(\lambda v_2.k(v_1{v}_2)))$ This is the transformation of function application. It looks complicated but read it like this: Firstly the result is a function that takes in a continuation. In the body, you first transform $e_1$ to CPS style and pass it a continuation. This continuation will be passed the value of $e_1$ which is $v_1$. Similarly we evaluate $e_2$ by transforming it to CPS style and passing it a lambda. Finally we do the function application and pass the result to the top-level continuation $k$.

$C(\text{if }{e}_1\text{ then }{e}_2\text{ else }{e}_3)=\lambda k.C(e_1)(\lambda v_1.\text{if }{v}_1\text{ then }C(e_2)k\text{ else }C(e_3)k))$ Similar to function application, we first transform $e_1$ to CPS style and pass in a continuation that has a conditional on $v_1$ and supplies $k$ to the appropriate branch.