Closures

In a language with lexical scoping (also called static scoping), the meaning of a variable reference is determined by where it appears textually in the source code, not by the dynamic call chain that leads to it. When a function `f` is defined inside another function `g`, and `f`'s body refers to a variable `x` that is a parameter or local of `g`, that reference to `x` is called a free variable of `f`: free because `f` does not bind it itself, it merely uses it, relying on the enclosing scope to supply its meaning. A closure is the runtime realization of this idea: a value consisting of (1) a pointer to the code of the function and (2) an environment, which supplies bindings for all of `f`'s free variables. Formally, if `f`'s code has free variables $x_1, \dots, x_n$, then a closure for `f` is a pair

where $\rho$ is an environment mapping each $x_i$ to a location (or value) — precisely the bindings that were in scope at the point `f` was defined. Calling the closure means executing $\text{code}_f$ with $\rho$ extended by bindings for the actual parameters. This is what distinguishes closures from plain function pointers in C: a C function pointer is just the code address, because C has no nested functions with free variables to capture — every name a C function uses is either global or one of its own locals/parameters, resolved at compile time with no runtime environment needed. The key subtlety, and the source of most closure bugs, is that environments bind variables (mutable storage locations), not values. If a closure captures a variable `x` and later, before the closure is called, some other code mutates `x`, the closure sees the new value — because it holds a reference to the location, not a frozen snapshot. This is by design: it is what makes counters, accumulators, and mutable-state encapsulation with closures work at all. It also means closures interact deeply with variable lifetime: because a closure can be called long after its defining function returns, any variable it captures must be kept alive on the heap rather than reclaimed when the stack frame pops — this is the central implementation challenge discussed below, and it is the reason languages that support closures generally require automatic memory management or some substitute (Rust captures by move/borrow and uses ownership rules instead).

An interpreter or compiler must do two things: (1) at the point a function-valued expression (a lambda, `def`, or `function` literal) is evaluated, construct a closure value by capturing the current environment; (2) at the point a closure is called, extend the captured environment with parameter bindings and evaluate the body in it. Free-variable analysis, done once (statically, ahead of time) rather than repeated on every call, tells the implementation exactly which names must be captured, which is the key optimization over naively capturing "everything visible."

Step 1 — static free-variable analysis. For each function definition, compute the set of free variables: names referenced in the body that are not parameters and not locally bound (by `let`, inner `def`, etc.) within that body. This is a straightforward recursive syntax traversal.

Step 2 — closure creation at definition time. When the enclosing code reaches the lambda expression during evaluation, allocate a closure record on the heap containing a pointer to the compiled code and an environment that supplies bindings for exactly the free variables computed in Step 1 (in efficient implementations, only those, not the whole enclosing scope).

Step 3 — application. When the closure is called with arguments, build a new environment frame binding the formal parameters to the argument values, with that frame's parent (for further free-variable lookups) being the closure's captured environment — not the caller's environment. This is the defining feature of lexical scoping: variable lookup follows the chain of definition sites, never the chain of call sites (which would be dynamic scoping). ```text // Free-variable computation (syntax-directed) function FreeVars(expr, bound): match expr: case Var(x): if x in bound: return {} else: return {x} case Lambda(params, body): return FreeVars(body, bound ∪ params) case Apply(fn, args): return FreeVars(fn, bound) ∪ (∪ FreeVars(a, bound) for a in args) case Let(x, rhs, body): return FreeVars(rhs, bound) ∪ FreeVars(body, bound ∪ {x}) case Literal(_): return {} // Evaluation with closure creation and application function Eval(expr, env): match expr: case Literal(v): return v case Var(x): return env.lookup(x) // walk the environment chain case Lambda(params, body): fv = FreeVars(Lambda(params, body), {}) captured = env.restrict(fv) // only what's actually free — key optimization return Closure(code = body, params = params, env = captured) case Apply(fnExpr, argExprs): closure = Eval(fnExpr, env) args = [Eval(a, env) for a in argExprs] newEnv = Environment(parent = closure.env) for (p, a) in zip(closure.params, args): newEnv.bind(p, a) return Eval(closure.code, newEnv) case Let(x, rhs, body): v = Eval(rhs, env) newEnv = Environment(parent = env) newEnv.bind(x, v) return Eval(body, newEnv) ``` The crucial line is `newEnv = Environment(parent = closure.env)` inside `Apply` — the new call frame's parent is the environment stored in the closure, not `env` (the caller's environment). This single design choice is what makes scoping lexical rather than dynamic: a free variable inside the closure body always resolves relative to where the closure was written, regardless of who calls it or from where.

Time. Constructing a closure takes $O(k)$ time and space, where $k$ is the number of free variables it captures (not the size of the whole enclosing environment) — this is why free-variable analysis, precomputed once per lambda at compile time, matters: naively copying the entire enclosing environment on every closure creation would be far more expensive and unbounded in size. Calling a closure costs $O(1)$ to build the new argument frame plus whatever the variable-lookup discipline costs. Variable lookup cost depends on the environment representation:

• Environment as a linked chain of frames (as in the pseudocode above): looking up a variable defined $d$ scopes outward costs $O(d)$ in the worst case, since you may walk $d$ parent pointers. This is simple and correct but can be slow for deeply nested closures.
• Flattened/array-based environments with compile-time slot resolution: a compiler pass (lexical addressing) computes, for every variable reference, a pair (depth, index) once, ahead of time, so lookup at runtime is $O(1)$ array indexing regardless of nesting depth. This is the technique used by efficient interpreters and compilers (e.g., the "De Bruijn index"–style compilation used in many functional-language implementations).

Space. Each closure occupies $O(k)$ heap space for its captured environment plus a constant for the code pointer. If closures are created in a loop of length $m$ each capturing $O(k)$ variables, total space is $O(mk)$. Because closures can outlive the stack frame that created them, captured variables must be heap-allocated, not stack-allocated: a compiler doing escape analysis determines which locals are captured by an escaping closure and allocates only those on the heap (a well-known optimization — locals never captured by an escaping closure can stay on the stack, since they provably die when the frame pops).

Correctness — the escaping-reference invariant. The correctness property closures must satisfy is: > If a closure $C = \langle \text{code}, \rho \rangle$ is created while a binding $x \mapsto \ell$ (variable $x$ at storage location $\ell$) is in scope, then every subsequent read of $x$ inside a later call to $C$ must observe the value currently stored at $\ell$, exactly as if the enclosing scope's frame were still alive. The implementation obligation this imposes is: the storage location $\ell$ must not be reclaimed or reused while any live closure's environment still references it. This is exactly a reachability condition, which is why a tracing garbage collector (mark-and-sweep, generational, etc.) is a natural and common solution — a captured variable is reachable from a live closure, hence never collected while that closure exists, hence the invariant holds automatically as a corollary of GC correctness (an object is collected only when unreachable from any root). Languages without GC (C++, Rust) instead enforce the invariant at compile time: Rust's borrow checker statically rejects a closure that would outlive a captured reference, forcing you to capture by move (ownership transfer) instead, trading runtime cost for a compile-time proof of the same invariant.

Correctness of "capture the variable, not the value." Because $\rho$ maps $x$ to a location $\ell$ rather than a frozen value, two closures created in the same scope that both capture $x$ observe the same mutations to $x$ — this is exactly the semantics required to implement shared mutable state via closures (e.g., a counter's `increment` and `read` closures sharing one counter cell). This is not a bug; it is the whole reason closures can encapsulate private mutable state without any language-level "object" construct.

Tradeoff. The convenience of implicit capture has a cost: it is easy to accidentally capture a loop variable by reference when you meant to capture its value at a particular iteration (the classic bug below), and it is easy to accidentally keep a large object alive far longer than intended, simply because some long-lived closure captured a reference to it (a real cause of memory leaks in JavaScript event-handler code, for instance).

Trace this program, in a JavaScript-like syntax with `let` (block-scoped, fresh binding per loop iteration — contrast with `var`, discussed in pitfalls): ```text function makeCounters() { let counters = []; for (let i = 0; i < 3; i = i + 1) { let count = 0; counters.push(function() { count = count + i; return count; }); } return counters; } let cs = makeCounters(); print(cs[1]()); // ? print(cs[1]()); // ? print(cs[0]()); // ? ``` Step through closure creation and calls explicitly:

Notice two things the trace makes explicit. First, each closure has its own environment record because `let` creates a fresh binding per iteration — this is why `cs[0]`, `cs[1]`, `cs[2]` don't interfere with each other, even though they were all created by the "same" lambda expression. Second, within one closure, state genuinely persists and mutates across calls: `cs[1]()` called twice returns `1` then `2`, because both calls share the same captured cell $c_1$ — this is the "shared mutable location, not copied value" behavior proven correct above. Now contrast with the classic bug: replace `let i` with `var i` (function-scoped, one shared binding for the entire loop, as in pre-ES6 JavaScript, or as if you'd hoisted a single mutable variable outside the loop in any language). Then there is only one cell $c_i$ for `i`, shared by all three closures:

This is not an implementation bug — it is the correct, faithfully-implemented consequence of variable capture-by-reference applied to a single shared binding. The fix (`let` instead of `var`, or in languages without per-iteration `let`, an explicit inner function to force a fresh binding per iteration) works precisely because it gives each closure a distinct location to capture, restoring the intended semantics.

The concept of lexical scoping and the closure as its implementation mechanism emerged from the confluence of the lambda calculus as a model of computation and the practical need, in the 1960s, to implement functions as first-class values in real interpreters.

Landin's SECD machine (Stack, Environment, Control, Dump) was the first formal computational model to make the environment component of a closure an explicit, first-class part of the machine state, rather than an informal side condition — this is the direct ancestor of every environment-based interpreter and virtual machine used to teach or implement closures today, including the pseudocode presented in this article.

Closures are the backbone of asynchronous and event-driven programming: JavaScript callbacks, Promise `.then()` handlers, and React component hooks (`useState`, `useEffect`) all rely on closures to remember which specific piece of state or context they belong to across asynchronous gaps in execution. Python's decorators, generators, and `functools.partial`-style currying are implemented via closures capturing the function or arguments being wrapped. In compilers themselves, closure conversion (the process of turning nested functions with free variables into flat top-level functions plus explicit environment structs) is a standard, load-bearing compilation pass for every functional language implementation — OCaml, Haskell (GHC), Scheme, Racket, and Erlang/Elixir's BEAM VM all perform it. In systems languages, Rust's closures (`Fn`, `FnMut`, `FnOnce` traits) make the capture-by-reference-versus-by-value distinction explicit and statically checked, showing that the closure/environment model generalizes even to languages built around manual memory safety rather than garbage collection. Closures also underlie memoization caches (a closure capturing a hash table alongside the function it wraps), iterator and generator protocols (a closure capturing "where I am" in a sequence), and are the conceptual stepping stone toward lazy evaluation (a thunk is essentially a closure that defers a computation) and toward monads (many monadic combinators, like `bind` for the state monad, are implemented as closures threading hidden state through a computation).

Ask the tutor: Can you show how closure conversion would rewrite `makeAdder` into flat, closure-free pseudocode with an explicit environment struct?