Continuations and CPS

A continuation is "the rest of the computation, as a function." Every expression has a context — what's waiting to be done with its result — and continuation-passing style (CPS) is a program rewriting where you make that context an explicit argument. Continuations are the universal control abstraction: they implement exceptions, generators, coroutines, backtracking, async/await, and algebraic effects.

Direct style vs CPS

In direct style, you write (+ 1 (* 2 3)) and the language figures out what to do with the result. In CPS, every function takes an extra parameter k — "the continuation" — and passes its result to it:

;; direct
(defn square [x] (* x x))
(square 4)               ;; → 16

;; CPS
(defn square-cps [x k] (k (* x x)))
(square-cps 4 println)   ;; prints 16

A whole program is CPS-converted by threading k:

;; direct
(defn pyth [a b] (+ (* a a) (* b b)))

;; CPS
(defn pyth-cps [a b k]
  (k (+ (* a a) (* b b))))

;; Nested calls become nested k's:
(defn pyth-cps' [a b k]
  (* a a)
  (fn [aa]
    (* b b)
    (fn [bb]
      (k (+ aa bb)))))

CPS makes the order of evaluation explicit and makes "the rest of the program" a first-class value.

What you can do with first-class continuations

Languages like Scheme expose continuations as values via call/cc ("call with current continuation"). Once k is in your hand, you can:

;; Scheme
(+ 1 (call/cc (λ (k) (k 10) 999)))   ;; → 11
;; the (k 10) jumps out; the 999 is unreachable

That's a non-local return implemented purely. Throw/catch is the restricted form: throw escapes out of a delimited scope; catch is the handler.

Delimited continuations (shift/reset)

Plain call/cc captures the entire rest of the program — to the end of main. That's hard to compose. Delimited continuations (Felleisen, Danvy, Filinski) capture only up to a marker:

(reset (+ 1 (shift k (k (k 10)))))   ;; → 12
;; k is "λx. 1 + x", captured up to the reset.
;; (k (k 10)) = (+ 1 (+ 1 10)) = 12

reset plants the marker; shift captures the continuation up to it. This is the primitive behind:

• Algebraic effect handlers (see previous topic — handlers are reset-bracketed contexts where operations shift to the handler).
• Async/await (await is shift, the surrounding async fn is reset).
• Generators (yield is shift returning to the consumer's reset).

Once you see shift/reset, all these "advanced" features collapse into one idea.

CPS as a compiler intermediate form

Compilers love CPS because it makes control flow uniform: everything is a tail call. SML/NJ, Scheme48, and modern OCaml's flambda use CPS or A-Normal Form (a sibling). Tail-call optimization is trivial in CPS — there are no non-tail calls to optimize.

The cost: CPS allocates closures for every continuation. ANF and SSA are compromises that keep some benefits with less allocation.

A tiny CPS interpreter

The interpreter for the lambda calculus, written in CPS, is famously clean:

The k argument is what every recursive call does next. Compare to a direct-style version — same structure, but k replaces the implicit "return."

Continuations vs monads

Every monadic program can be CPS-transformed; every CPS program can be read as a monadic program in the continuation monad Cont r a = (a → r) → r. The two views are equivalent. CPS is monads with the syntax pushed back into the program; monads are CPS with the plumbing hidden in bind.

Real-world: continuations in production

If you've ever wondered why so many "advanced" features (async, generators, exceptions, fibers, algebraic effects) look like cousins — they are. The unifying primitive is "the continuation."

Check yourself

Exercise

Take this direct-style program:

(if (> x 0)
  (* 2 (factorial (- x 1)))
  1)

Convert it to CPS (assume factorial-cps has signature (x, k)). Verify that every call is in tail position — i.e. its result flows directly to a continuation, not back to the caller.