Continuations and CPS

Stop in the middle of evaluating an expression — say you have just computed the 2 \times 4 inside 1 + (2 \times 4) — and ask: what happens next? The answer is "add 1, then report the result." That leftover work, "everything the program will still do with the value I am about to produce," is the continuation. It is usually invisible, living implicitly in the call stack. Continuation-passing style makes it a first-class value: an ordinary function you can name, store, pass around, and — most powerfully — call more than once or not at all.

Reifying the rest of the computation is the master key to control flow. Exceptions, generators, coroutines, async/await, backtracking search, and the exotic call/cc operator are all just continuations, captured and used in different disciplines. This lesson defines continuations precisely, presents the CPS transformation that rewrites any program so that control flow is completely explicit, shows why every call in CPS is a tail call, and meets call/cc — whose type, astonishingly, is a law of classical logic.

A continuation is "the rest of the computation"

Focus on a subexpression — the redex about to be reduced. Everything the program will do with its result, up to producing the final answer, is a function from that result to the answer. That function is the continuation. Watch it made explicit for 1 + (2 \times 4):

The continuation of 2 \times 4 is k = \lambda v.\ \mathsf{report}(1 + v). Evaluate the redex to 8, hand it to k, and the rest unfolds: k(8) = \mathsf{report}(9). In direct-style code this k is implicit — it is the pending stack frames. CPS drags it into the open and passes it as an argument, so a function no longer "returns" a value; it calls its continuation with that value. The stack becomes data.

The CPS transformation

The CPS transform is a source-to-source rewrite. Write \llbracket e \rrbracket\,k for "evaluate e and pass its value to the continuation k." A constant just feeds itself to k; a compound expression threads a chain of continuations, one per subexpression, fixing evaluation order as it goes:

\llbracket n \rrbracket\,k \;=\; k\,n \qquad\qquad \llbracket e_1 + e_2 \rrbracket\,k \;=\; \llbracket e_1 \rrbracket\,\big(\lambda v_1.\ \llbracket e_2 \rrbracket\,(\lambda v_2.\ k\,(v_1 + v_2))\big)

Read the sum rule aloud: "evaluate e_1; with its value v_1, evaluate e_2; with its value v_2, hand v_1 + v_2 to k." The nesting of the lambdas is the evaluation order, now written down explicitly instead of left to the runtime. Functions transform too: a source function \lambda x.\,e becomes a function taking an extra continuation argument, and its type gains an answer type \mathsf{Ans}:

\dfrac{}{\;\overline{A \to B} \;=\; A \to (B \to \mathsf{Ans}) \to \mathsf{Ans}\;} \qquad\qquad \dfrac{\Gamma \vdash e : T}{\Gamma \vdash \llbracket e \rrbracket : (T \to \mathsf{Ans}) \to \mathsf{Ans}}

A continuation accepting a T has type T \to \mathsf{Ans}. A CPS-transformed expression is a function waiting for its continuation. Two facts fall out immediately: no CPS function ever returns (it only calls its continuation), and — because the continuation call is always the last thing done — every call is in tail position.

Every call becomes a tail call

In direct style, 1 + f(x) is not a tail call: after f returns, there is still an addition to do, so the caller's frame must be kept alive. That pending "+1" is exactly what CPS captures in the continuation. Once the continuation is explicit, the recursive call to f is the last action — a genuine tail call — and needs no stack frame of its own.

The deep space is not saved, only moved: the pending work now lives in the heap-allocated continuation instead of the control stack. But making it explicit is precisely what lets a compiler analyse, optimise, and reify it — and what lets a program reach in and grab it.

call/cc and a runnable CPS interpreter

Once continuations are values, give the program a way to capture the current one: call/cc ("call with current continuation") reifies k at its call site and hands it to a function as a first-class escape procedure. Invoke that escape later and control leaps back to where call/cc was, abandoning whatever it was doing — a non-local jump strictly more general than an exception. Below is a metacircular CPS interpreter for a tiny language: evalK never returns, it always calls k; CallCC binds the current k as a continuation value; Throw invokes a captured continuation, discarding the current one. Press Run:

type Ans = number; type Value = | { tag: "num"; n: number } | { tag: "cont"; k: Cont }; // a reified continuation, as a first-class value type Cont = (v: Value) => Ans; type Expr = | { tag: "Num"; n: number } | { tag: "Add"; l: Expr; r: Expr } | { tag: "Mul"; l: Expr; r: Expr } | { tag: "Var"; name: string } | { tag: "CallCC"; param: string; body: Expr } // call/cc (λparam. body) | { tag: "Throw"; kExpr: Expr; arg: Expr }; // invoke captured continuation type Env = Record<string, Value>; const numV = (n: number): Value => ({ tag: "num", n }); // CPS evaluator: control flow is EXPLICIT in the continuation k. Every call is a tail call. function evalK(e: Expr, env: Env, k: Cont): Ans { switch (e.tag) { case "Num": return k(numV(e.n)); case "Var": return k(env[e.name]); case "Add": return evalK(e.l, env, (lv) => evalK(e.r, env, (rv) => k(numV((lv as { n: number }).n + (rv as { n: number }).n)))); case "Mul": return evalK(e.l, env, (lv) => evalK(e.r, env, (rv) => k(numV((lv as { n: number }).n * (rv as { n: number }).n)))); case "CallCC": // Bind the CURRENT continuation k as a value, then run the body with continuation k. return evalK(e.body, { ...env, [e.param]: { tag: "cont", k } }, k); case "Throw": // Evaluate the continuation value and the argument, then JUMP: call the captured k, // ignoring the current continuation entirely — a non-local escape. return evalK(e.kExpr, env, (kv) => evalK(e.arg, env, (av) => (kv as { k: Cont }).k(av))); } } const run = (e: Expr): number => evalK(e, {}, (v) => (v as { n: number }).n); const N = (n: number): Expr => ({ tag: "Num", n }); // 10 + call/cc(λesc. 1 + 2) — esc never used, ordinary result 10 + 3 = 13 console.log("no escape:", run({ tag: "Add", l: N(10), r: { tag: "CallCC", param: "esc", body: { tag: "Add", l: N(1), r: N(2) } }, })); // 10 + call/cc(λesc. 1 + throw esc 100) // throw esc 100 JUMPS to the continuation of call/cc (which is "add 10"), // abandoning the "1 + ·". Result = 10 + 100 = 110, NOT 10 + (1 + 100). console.log("escape: ", run({ tag: "Add", l: N(10), r: { tag: "CallCC", param: "esc", body: { tag: "Add", l: N(1), r: { tag: "Throw", kExpr: { tag: "Var", name: "esc" }, arg: N(100) } }, }, }));

The second result is 110, not 111. Invoking esc discarded the pending "1 + ·" and resumed at call/cc's own continuation. That is the whole power of first-class continuations: you can bottle up a point in the computation and teleport back to it on demand.

Read types as propositions and programs as proofs — the Curry–Howard correspondence — and something jaw- dropping appears. The type of call/cc is ((A \to B) \to A) \to A, which is exactly Peirce's law, a classical tautology that is not provable in intuitionistic logic. In 1990 Timothy Griffin noticed this is no coincidence: adding first-class control to a typed language corresponds precisely to moving from intuitionistic to classical logic. The law of excluded middle, double-negation elimination — all the "non-constructive" reasoning banned from constructive maths — becomes computable once you can capture and invoke continuations. Control operators are, quite literally, the computational content of classical proof. Andrzej Filinski went further and showed continuations are "the mother of all monads": exceptions, state, generators, and async can all be built from call/cc plus a single mutable cell.

The CPS transform is not evaluation-order-neutral. Writing \llbracket e_1 + e_2 \rrbracket\,k = \llbracket e_1 \rrbracket(\lambda v_1.\ \llbracket e_2 \rrbracket(\lambda v_2.\ k(v_1+v_2))) commits to evaluating e_1 before e_2. A right-to-left transform is equally valid and gives a different order — which matters the instant your subexpressions have side effects. CPS makes evaluation order explicit precisely because you must choose one; direct-style code that quietly relied on an unspecified order will change behaviour under the "wrong" transform.

A second hazard: a captured continuation is multi-shot. Unlike an exception (one-shot, gone after it fires), a call/cc continuation can be invoked again and again, each time re-running the rest of the computation. Combine that with mutable state and reasoning gets genuinely hard — the same continuation invoked twice sees the store in whatever condition the first invocation left it. This is why most mainstream languages expose only the tamed, one-shot forms (exceptions, generators, async) rather than raw call/cc.