THE CEK MACHINE three registers — Control, Environment, Kontinuation — and no call stack
The CEK machine evaluates the lambda calculus with three explicit components: Control (the expression being evaluated), Environment (what the free variables mean), and Kontinuation (what to do with the result — the rest of the computation, made into a data structure). Its magic is that the continuation replaces the call stack: instead of the runtime's hidden stack of return addresses, “what happens next” is an ordinary value you can inspect, save, or resume. Felleisen & Friedman derived it from Landin's SECD by making control explicit. It is the machine behind exceptions, generators, and call/cc.
THE TECHNIQUE C=expr, E=env, K=continuation (the rest, as data)
Evaluating (λx. x+x) 5 as CEK transitions. The demo steps through Control/Env/Kont and counts the transitions to a value: live demo
HISTORY & CREDIT Felleisen & Friedman, 1986
“The call stack is part of the hardware, not the program.” — the CEK machine turns it into a value: the continuation. Once “what happens next” is data, you can save it (generators), abandon it (exceptions), or invoke it twice (call/cc). cited
1986 · Matthias Felleisen & Daniel Friedman — the CEK machine, derived from Landin's SECD by making control (the continuation) explicit. 1987 · extended to CESK (dart 268) with a store. now · the semantics behind exceptions, generators, coroutines, and first-class continuations.
Make the rest of the computation a value and the call stack disappears into ordinary data — which is why one machine explains exceptions, generators, and call/cc at once. Felleisen-Friedman 1986
RECOMMEND FOR I-13 CEK transitions, computed
On the canonical compiler, evaluating (λx. x+x) 5 reaches 10 in a few CEK transitions (call depth 1 — i13 uses its own stack, not a reified continuation):
$ i13 run m_cek.i13 # (\x. x+x) 5, control/env/kont
RUN OK . 11 step(s) . peak stack 2 . call depth 1
result = 10
cek_steps = 3
Recommend: here i13 and the CEK machine diverge sharply. i13 keeps its continuation implicit — a real call stack, bounded at 4096 frames (E0503), never a first-class value. That is a deliberate floor: no call/cc, no reified continuations, so control can never be captured, saved, or resumed — which is precisely what lets i13 prove control-structure pairing in a single pass (the COVERED half of its ledger, dart 259). The CEK machine buys exceptions and generators by making the continuation data; i13 forgoes all of them to keep control analyzable. A clean trade, and i13's side of it is the conservative one.