On the last two pages we made data explicit — a function became a closure over an environment instead of borrowing the host's functions. The last of Reynolds' three leaks remains: control. A direct-style interpreter still borrows the host's call stack and its "return" mechanism — it never says, in its own terms, what happens next. To compile a language faithfully, especially one with exceptions, generators, or proper tail calls, we must make "what happens next" a value we can name, pass, and store. That value is a continuation, and rewriting a program so every continuation is explicit is continuation-passing style (CPS).

CPS is not merely a curiosity — it is one of the great intermediate representations of compiler back ends. Guy Steele's 1978 RABBIT compiler for Scheme showed that if you transform the whole program into CPS, then "lambda is the ultimate GOTO": every jump, every return, every loop is a tail call to a continuation, and code generation becomes almost mechanical because control flow is already spelled out. Modern compilers — SML/NJ, and via CPS's cousin ANF, GHC and many others — are built on exactly this move. This page shows what a continuation is, how CPS makes control explicit, why "administrative redexes" are its main nuisance, and how ANF is the tidier sibling most real compilers prefer.

A continuation is "the rest of the computation"

Fix a spot inside an evaluating expression. Everything that will still happen after the value at that spot is produced — that whole pending remainder, as a function of the value — is its continuation. In 1 + (2 \times 3), once 2 \times 3 yields 6, the rest is "add 1 to it": the continuation of the subexpression 2\times 3 is \kappa = \lambda v.\;1 + v. CPS turns this implicit "rest" into an explicit extra argument that every function and primitive receives and calls instead of returning:

Read it aloud: to compute e_1 + e_2 and then do \kappa with the sum, first compute e_1 and hand its value a to a continuation that computes e_2, hands its value b to a continuation that finally calls \kappa on a+b. Two consequences fall out at once, and they are why compilers love CPS: evaluation order is now written down (left before right, because that is the nesting of the continuations), and every call is in tail position — nothing ever waits on the stack for a call to return, because there are no returns.

CPS linearises control into a chain of tail calls

The direct-style expression (a + b) \times c hides its control flow in the tree structure — "do the inner add, then the multiply" is implicit. CPS makes it a straight chain: compute the sum, pass it forward; compute the product, pass it forward; hand the result to the halt continuation. Each arrow is a tail call — a jump, not a call-that-returns. Reveal the chain:

That straight chain is the point. A code generator can walk it and emit one basic block after another, each ending in a jump to the next — which is precisely what machine code looks like. Control flow that was structural (nested subtrees, implicit returns) is now syntactic (a sequence of named steps), and that is what "compiling with continuations" buys you.

The CPS converter, running

Here is a real (if small) CPS transformer for an arithmetic-and-let language, plus a CPS evaluator that threads an explicit continuation and never returns a value the ordinary way — it always calls its continuation. The transformer emits the nested-lambda CPS text so you can see the structure; the evaluator proves it computes the right answer. Press Run:

The printed CPS form — let v0 = a + b in let v1 = v0 * c in v1 — has named every intermediate and fixed the order. The evaluator never writes return someValue to its caller; it calls k. The final answer arrives at the halt continuation. Control has become data.

Administrative redexes, and why ANF is the practical cousin

The naïve CPS transform sprinkles in extra \lambdas and immediately applies them — (\lambda a.\,\ldots)\,e_1. These administrative redexes are bookkeeping artefacts of the transform, not part of the source program's meaning, and if you leave them in, the CPS code is bloated and slow. Plotkin (1975) identified them; the fix is either a one-pass "higher-order" CPS transform that reduces them as it goes (the trick in Danvy & Filinski's compact converters), or to skip CPS's redundancy altogether and target A-Normal Form (ANF).

Whichever you pick, the deliverable to the code generator is the same: a program where every operation is named, every argument is trivial, and control flows as an explicit sequence of steps — a shape that maps almost one-to-one onto basic blocks and jumps.

Why tail calls fall out for free

In CPS there are no non-tail calls — every call is the last thing its function does, because the "what to do with the result" was passed along as \kappa rather than waited for. So a function call compiles to a jump that reuses the current stack frame, and a loop written as tail recursion runs in constant space with no special "tail-call optimisation" pass — the CPS form is the optimisation.

Look at the call f\;v\;\kappa: the function receives the argument and the continuation, and it is in tail position in the continuation lambda. There is nothing after it to come back to. This is the technical content of Steele's slogan "lambda is the ultimate GOTO": once control is explicit, a procedure call and a goto are the same instruction, and the compiler stops treating them differently. That single uniformity is why a CPS-based back end can generate tight, loop-friendly code without a separate control-flow analysis.