Closures and Environments

A definitional interpreter represented a function value as a closure — the code of a \lambda together with the environment captured where it was written — and promised to explain why. This page pays that debt. The question is deceptively simple: when a function mentions a variable it did not define, which value does it see? The answer forces us to be precise about two runtime structures the semantics only sketched — the environment, a chain of frames binding names to values, and the closure, the object that pins a function to the exact environment it was born in.

Get this right and you have lexical (static) scope, the discipline every modern language uses: a variable refers to the binding textually enclosing it, decided once, at definition time. Get it subtly wrong — look the variable up in the environment active at the call instead — and you have dynamic scope, a different language with famously slippery behaviour. The whole difference is a single choice about which environment a closure carries, and this page makes that choice concrete, drawable, and runnable.

Environments as a chain of frames

An environment answers "what is the value of this name, here?". The clean representation is a linked list of frames: each frame is a small table of name\,\mapsto\,value bindings introduced by one scope (a let, a function's parameters), plus a pointer to its parent frame — the enclosing scope. Looking up a name walks the chain from the innermost frame outward until it finds the name; the first hit wins, which is exactly how inner bindings shadow outer ones.

\text{lookup}(x, \rho) \;=\; \begin{cases} \rho.\mathrm{binds}[x] & \text{if } x \in \rho.\mathrm{binds} \\[4pt] \text{lookup}(x, \rho.\mathrm{parent}) & \text{otherwise} \end{cases}

Extending the environment — what let x = v or "bind parameter to argument" does — never mutates an existing frame. It pushes a new frame whose parent is the current one: \rho' = \langle [x \mapsto v],\ \rho \rangle. Because the old frames are untouched, two computations can share a parent chain while each has its own tip. That persistence is precisely what lets closures created at different times capture different-but-overlapping environments.

A closure captures its birthplace

Here is the whole idea in one picture. We evaluate let x = 10 in let f = (λy. x + y) in let x = 99 in f 5. When \lambda y.\,x+y is evaluated it becomes a closure — a pair of (its code) and (a pointer to the frame where x = 10). Later we rebind x = 99 in a new frame and call f 5. The closure ignores the new x entirely: it looks x up along the parent chain it captured, finds 10, and returns 15. Reveal the frames and the capture pointer:

The dashed arrow from the closure to F1 is the entire concept. A closure is not just code — it is code plus that arrow. Change where the arrow points and you change the language's scope rule. The call frame C makes its parent the captured frame, never the caller's frame, and that is what makes the scope lexical: the answer was fixed by the program's text, not by who called whom.

Static vs dynamic scope, side by side

The two disciplines differ in a single line of the interpreter — the parent of the call frame:

Below, one evaluator, one flag. Flip DYNAMIC and the very same program changes its answer, because the free x in \lambda y.\,x+y resolves differently. Press Run:

type Expr = | { kind: "lit"; n: number } | { kind: "var"; name: string } | { kind: "add"; left: Expr; right: Expr } | { kind: "let"; name: string; value: Expr; body: Expr } | { kind: "lam"; param: string; body: Expr } | { kind: "app"; fn: Expr; arg: Expr }; // An environment is a FRAME: its own bindings + a pointer to its parent frame (or null). interface Frame { binds: Record<string, Value>; parent: Frame | null; } type Value = | { tag: "num"; n: number } | { tag: "clo"; param: string; body: Expr; captured: Frame }; // code + captured frame // Walk the parent chain: first frame that binds the name wins (inner shadows outer). function lookup(name: string, f: Frame | null): Value { for (let cur = f; cur; cur = cur.parent) { if (name in cur.binds) return cur.binds[name]; } throw new Error("unbound variable " + name); } const push = (binds: Record<string, Value>, parent: Frame | null): Frame => ({ binds, parent }); const DYNAMIC = false; // ← flip to true for dynamic scope function evaluate(e: Expr, env: Frame): Value { switch (e.kind) { case "lit": return { tag: "num", n: e.n }; case "var": return lookup(e.name, env); case "add": { const l = evaluate(e.left, env) as Value & { tag: "num" }; const r = evaluate(e.right, env) as Value & { tag: "num" }; return { tag: "num", n: l.n + r.n }; } case "let": return evaluate(e.body, push({ [e.name]: evaluate(e.value, env) }, env)); case "lam": // Capture the CURRENT env — this is the closure's birthplace. return { tag: "clo", param: e.param, body: e.body, captured: env }; case "app": { const fn = evaluate(e.fn, env) as Value & { tag: "clo" }; const arg = evaluate(e.arg, env); // THE ONE LINE: lexical uses the captured frame; dynamic uses the caller's env. const parent = DYNAMIC ? env : fn.captured; return evaluate(fn.body, push({ [fn.param]: arg }, parent)); } } } const G: Frame = { binds: {}, parent: null }; // let x = 10 in let f = (λy. x + y) in let x = 99 in f 5 const prog: Expr = { kind: "let", name: "x", value: { kind: "lit", n: 10 }, body: { kind: "let", name: "f", value: { kind: "lam", param: "y", body: { kind: "add", left: { kind: "var", name: "x" }, right: { kind: "var", name: "y" } } }, body: { kind: "let", name: "x", value: { kind: "lit", n: 99 }, body: { kind: "app", fn: { kind: "var", name: "f" }, arg: { kind: "lit", n: 5 } } } }, }; const out = evaluate(prog, G) as Value & { tag: "num" }; console.log("DYNAMIC =", DYNAMIC, " → f 5 =", out.n); console.log(DYNAMIC ? "dynamic: x resolves to 99 → 99 + 5 = 104" : "lexical: x resolves to the CAPTURED 10 → 10 + 5 = 15");

Lexical scope returns 15; dynamic returns 104. Same source, same closure object — only the parent of the call frame moved. This is why almost every language chose lexical scope: the meaning of \lambda y.\,x+y is fixed by where it is written, and a reader (or a compiler) can resolve x without knowing anything about the call site.

Why closures are exactly right

A closure is the minimal object that makes a first-class function behave like the \lambda-term it came from. Consider a function factory:

const adder = (k: number) => (n: number) => n + k; // returns a closure over k const add10 = adder(10); // captures k = 10 const add20 = adder(20); // captures k = 20 — a DIFFERENT frame add10(5); // 15 add20(5); // 25

add10 and add20 run identical code yet give different answers, because each captured a different frame binding k. The frame outlives the call to adder that created it — it cannot live on the stack, because the stack frame for adder is long gone. So captured environments are heap-allocated, and their lifetime is exactly "as long as some reachable closure still points at them". That last sentence is the bridge to garbage collection: a closure's captured frame is a live edge in the heap object graph, and it keeps everything the function can still see alive.

Peter Landin coined the term in his 1964 paper The Mechanical Evaluation of Expressions, which introduced the SECD machine — Stack, Environment, Control, Dump — the first abstract machine designed to evaluate \lambda-expressions. A function value in SECD is a "closure" because it closes over its free variables: the open term \lambda y.\,x + y has a free x, and pairing it with an environment binding x closes it, leaving nothing dangling. Landin's environment was, exactly as here, a chain of frames. Sixty years on, every "lambda" in Java, Swift, Rust, Python and JavaScript is a Landin closure — code plus captured environment — and the SECD's four registers still echo through every bytecode VM. The vocabulary you are learning is the original vocabulary.