Continuation Passing Style

Continuation-passing style (CPS) is a programming technique where control flow is made explicit by threading the “rest of the computation” as a function — the continuation — through every step.

In a direct-style factorial, you nest recursive calls and the runtime manages the return chain. In CPS, every call ends by invoking its continuation, building an explicit chain of closures on the heap rather than frames on the stack.

mk-cps — a CPS factory

The function mk-cps is a higher-order constructor that builds CPS factorial generators:

(defn mk-cps [accept? kend kont]
  (fn [n]
    ((fn [n k]
       (let [cont (fn [v] (k (kont v n)))]
         (if (accept? n)
           (k 1)
           (recur (dec n) cont))))
     n kend)))

Three parameters control the generated function:

We instantiate mk-cps to build the factorial function:

(def fac-mk-cps
  (mk-cps zero? identity #(* %1 %2)))

(fac-mk-cps 10)
;; => 3628800

Phase 1 — Tail-recursive descent (building the chain)

recur targets the inner (fn [n k] ...), so the recursion is tail-call optimized — no stack frames grow. Instead, each iteration allocates a new closure that captures the previous continuation.

Every step:

1. Creates a new continuation: contₙ = (fn [v] (kₙ₋₁ (* v n)))
2. If not at the base case, recurs with (dec n) and the new continuation as k

Call 1:  n=10  k₀=identity
         cont₁ = (fn [v] (k₀ (* v 10)))   ;; capture: k₀, n=10
         (zero? 10) → false
         recur with (dec n)=9, k=cont₁

Call 2:  n=9   k₁=cont₁
         cont₂ = (fn [v] (k₁ (* v 9)))    ;; capture: cont₁, n=9
         (zero? 9) → false
         recur with (dec n)=8, k=cont₂

   ↓              ↓                  ↓
   ⋮              ⋮                  ⋮

Call 10: n=1   k₉=cont₉
         cont₁₀ = (fn [v] (k₉ (* v 1)))  ;; capture: cont₉, n=1
         (zero? 1) → false
         recur with (dec n)=0, k=cont₁₀

Call 11: n=0   k₁₀=cont₁₀
         cont₁₁ = (fn [v] (k₁₀ (* v 0))) ;; capture: cont₁₀, n=0
         (zero? 0) → true!
         → (k₁₀ 1)                       ;; base case → value 1 enters the chain

After the descent, the heap holds a linked list of closures:

k₀ = identity
k₁ = cont₁ ⟦v⟧ → k₀(  v * 10)
k₂ = cont₂ ⟦v⟧ → k₁(  v *  9)
k₃ = cont₃ ⟦v⟧ → k₂(  v *  8)
k₄ = cont₄ ⟦v⟧ → k₃(  v *  7)
k₅ = cont₅ ⟦v⟧ → k₄(  v *  6)
k₆ = cont₆ ⟦v⟧ → k₅(  v *  5)
k₇ = cont₇ ⟦v⟧ → k₆(  v *  4)
k₈ = cont₈ ⟦v⟧ → k₇(  v *  3)
k₉ = cont₉ ⟦v⟧ → k₈(  v *  2)
k₁₀= cont₁₀⟦v⟧ → k₉(  v *  1)

Each closure holds a reference to the previous one plus the captured n — a singly linked list on the heap that encodes the entire “return sequence.”

Phase 2 — Continuation unfolding (value propagation)

When (k₁₀ 1) fires (the base case), the chain unwinds — each step applies (* v n) and passes the product forward:

(k₁₀ 1)
  → (k₉  (* 1 1))     = (k₉  1)
  → (k₈  (* 1 2))     = (k₈  2)
  → (k₇  (* 2 3))     = (k₇  6)
  → (k₆  (* 6 4))     = (k₆  24)
  → (k₅  (* 24 5))    = (k₅  120)
  → (k₄  (* 120 6))   = (k₄  720)
  → (k₃  (* 720 7))   = (k₃  5040)
  → (k₂  (* 5040 8))  = (k₂  40320)
  → (k₁  (* 40320 9)) = (k₁  362880)
  → (k₀  (* 362880 10))
  → (identity 3628800)
  → 3628800

The intermediate results grow exactly like a textbook recursive factorial, but every step is a tail call — the “stack” is the linked list of closures already allocated.

Visual diagram

The SVG source is also available in the site repository.

The diagram shows both phases side by side:

Top half (blue arrows) — the tail-recursive descent building the linked list of closures. Each contₙ captures its n and a reference to the previous continuation. The amber box marks the base case trigger (cont₁₁) where (zero? 0) returns true.

Bottom half (green arrows) — the unfolding: value 1 enters the chain and each step applies (kont v n) = (* v n), growing the result from 1 → 1 → 2 → 6 → 24 → 120 → 720 → 5040 → 40320 → 362880 → 3628800, until it reaches k₀ = identity which returns the final 3628800.

Key insight

This CPS construction demonstrates a fundamental technique in functional programming:

The stack is reified as data.

Every continuation contₙ = (fn [v] (kₙ₋₁ (* v n))) is a delimited continuation delimited by kend = identity. The chain between kend and the current k represents “everything that remains to be done” with the result.

This pattern generalises to all of CPS — async callbacks, effect handlers, and many compiler intermediate representations (e.g., Scheme compilers, Clojure’s own clojure.core/trampoline) use the same idea of reifying control flow as data.

Also in this series

• Concurrency — Clojure’s identity/value concurrency model
• Private Functions — conventions for encapsulation
• Protocols & Multimethods — ad-hoc polymorphism