THE SECD MACHINE the first abstract machine, call-by-value
Landin’s 1964 machine evaluates a lambda expression by rewriting a four-register state: Stack of computed values, Environment of variable bindings, Control of what is still to do, Dump of saved caller states. A lambda pushes a closure (body + captured environment) — the concept Landin coined. It is call-by-value: arguments are fully evaluated before the call.
THE TECHNIQUE rewrite the 4-register state to a value
Run ((λx. x+x) (3+1)) step by step. Watch three moments: call-by-value — 3+1 collapses to 4 before the body is entered; the closure<x, x+x, {}> pushed onto S; the Dump saving the caller’s state on entry and restoring it on return. It halts with one number on the stack. live demo
HISTORY & CREDIT 1964, call-by-value, and Control not Code
“SECD is lazy” — no, call-by-value: 3+1 becomes 4 after before the body runs. The call-by-name dual is Krivine (dart 143). cited
1960 · McCarthy — Lisp’s eval with an explicit environment, but dynamically scoped (the FUNARG bug Landin’s closure fixes). 1964 · Peter Landin — “The Mechanical Evaluation of Expressions”: the SECD machine (Stack, Environment, Control, Dump) and the closure, “a bundle of the lambda-expression and the environment relative to which it is evaluated.” 1975 · Plotkin — the first formal verification, pinning SECD as call-by-value (the λv calculus). 1986 / 2004 · Felleisen & Friedman delete the Dump for the CEK machine (D was already a saved continuation); Danvy shows SECD is a CPS evaluator defunctionalized (dart 147).
It was the first abstract machine (four registers, rewrite rules in prose); the concrete instruction set is Henderson’s LispKit (1980). Landin, 1964
RECOMMEND FOR I-13 S/E/C as arrays; a closure is a first-order value
The whole machine is arrays + integer pointers; because Landin’s machine is already first-order (closures are data, dispatch is explicit), it fits I-13 exactly:
$ i13 run secd.i13 # ((\x. x+x) (3+1)) -- stack S + environment E
arg 3+1 = 4 (call-by-value, before the body) env E = [x=4]
control [LD 0, LD 0, ADD, STOP] over env -> 4 + 4 = 8 on the stack
Recommend:nothing new — S is an f64 array with a top pointer, E is an environment array, C is a control array of opcodes, and a closure is a first-order record (body index + env). Verified: the argument 3+1 is evaluated to 4 first (call-by-value), then the body x+x reads x twice from E and sums to 8. Landin’s machine is a defunctionalized evaluator (dart 147), which is precisely why a language with no closures can run it. Note: a full lambda term + the Dump of saved states wants a node arena (PS-015); the corpus runs the stack/env core on flat arrays. It is the direct ancestor of the CEK machine and every bytecode VM — incl. the 8/19 benchmark’s Cortex VM.