Nonlocal Data and Closures

A procedure's own parameters and locals live in its activation record, at fixed offsets from the frame pointer — easy. But nested procedures can also read variables that belong to an enclosing procedure: variables that are neither local nor global, but nonlocal. Finding those variables at run time is a genuine puzzle, because the enclosing procedure's frame is somewhere down the stack — but which frame, and how far down, depends on the program's lexical nesting, not on who called whom. Solving this puzzle leads straight to one of the most important ideas in all of programming: the closure.

Access links: a chain up the lexical nesting

When procedure inner is lexically nested inside outer, a use of outer's variable x from within inner must reach outer's frame. The standard mechanism gives each frame an access link (also called a static link): a pointer to the frame of the procedure that lexically encloses it. To read a nonlocal variable k levels out, the code follows the access link k times, then loads at the known offset.

This is where a beginner's intuition fails, so look closely. Every frame has two links, and they point at different frames:

The control link (dynamic link) points to the caller — it follows the runtime call history. The access link (static link) points to the lexically enclosing procedure's most recent frame — it follows the source-code nesting. When outer calls a sibling helper which in turn calls the nested inner, inner's control link points back to helper (its caller) but its access link jumps over helper straight to outer (its lexical parent). The two arrows genuinely diverge.

Displays: trading the walk for an array

Chasing k access links for a deeply nested reference costs k memory loads. A display removes the walk. It is a small array d indexed by nesting depth, where d[i] always holds a pointer to the current frame at lexical level i. A nonlocal at level i is then reached in one step: d[i] plus the offset — no chain to climb.

Access link — one pointer per frame to the lexical parent's frame; a level-k nonlocal costs k pointer hops. Simple, no global state.
Display — one array d[\,] indexed by depth; any nonlocal costs a single indexed load. Faster access, but the display must be saved and restored around calls.

Both encode the same fact — "the level-i frame currently in scope is this one" — the access link as a linked list, the display as a random-access array. They are the classic space/time and simplicity/speed trade for nonlocal access.

A closure = code pointer + captured environment

Now the payoff. Suppose a function does not just read a nonlocal variable but is returned or stored, to be called later — after its defining procedure has already returned. The enclosing frame it needs would, on a plain stack, be gone. The solution is to bundle the function with the environment it captured. That bundle is a closure:

a code pointer — the address of the function's body;
an environment — the captured bindings of the nonlocal variables the body refers to (its free variables).

A closure "closes over" its free variables: it carries their storage with it. This model — a function value is code + environment — is what makes first-class functions, callbacks, iterators and currying work. The makeCounter below returns a function that keeps incrementing a private count that lives on after makeCounter has returned:

// makeCounter returns a closure capturing its own private `count`. function makeCounter(start: number): () => number { let count = start; // a nonlocal, captured by the returned function return () => { count = count + 1; // mutates the CAPTURED binding, not a fresh copy return count; }; } const a = makeCounter(0); const b = makeCounter(100); // an INDEPENDENT capture — its own count console.log(`a: ${a()} ${a()} ${a()}`); // 1 2 3 console.log(`b: ${b()} ${b()}`); // 101 102 console.log(`a again: ${a()}`); // 4 — a's count survived and kept going

Each call to makeCounter creates a separate environment, so a and b count independently. The variable count outlives the call that created it — which is precisely why it cannot live on the stack.

The funarg problem: why closures escape to the heap

A pure stack works only while lifetimes nest. Closures break that assumption. When a function that captured local variables is returned upward — out of the procedure that created it — those captured variables must outlive the frame that held them. This is the upward funarg problem ("funarg" = functional argument), and it is fatal to naïve stack allocation: the frame is popped, but the closure still needs its contents.

The fix is to allocate the captured environment on the heap, not the stack. The closure holds a pointer to a heap-allocated environment record that lives as long as the closure does, reclaimed only when the closure itself becomes garbage. This is exactly why languages with first-class functions and closures — Lisp, ML, JavaScript, Python — all require a garbage-collected heap: the neat "pop on return" discipline of the stack simply cannot express a value that escapes its creator.

(The downward funarg problem — passing a nested function into a call, where the enclosing frame still exists — is milder: an access link suffices, since the environment is still on the stack. It is the upward direction, escaping outward, that forces the heap.)

They capture the variable (the binding), not a snapshot of its value — which is why count above keeps changing between calls. This surprises people in loops: closures created inside a loop that all capture the same loop variable will, when later invoked, all see its final value, not the value at creation time. (The classic JavaScript var-in-a-loop bug; let fixes it by giving each iteration a fresh binding to capture.) Capturing the binding is the powerful, correct default — it is what lets two closures over the same variable communicate — but it means you must think about which binding is shared.

The commonest confusion in this whole topic is conflating the two per-frame links. The control (dynamic) link points to the caller — it answers "where do I return to?" and follows the runtime call chain. The access (static) link points to the lexically enclosing procedure — it answers "where do I find my nonlocal variables?" and follows the source nesting. When a nested function is called from far away, these point at completely different frames. Using the dynamic link to resolve a nonlocal name gives you dynamic scoping — you would read whatever variable the caller happened to have, not the one the source text names. Modern lexically-scoped languages always resolve nonlocals through the access link. And once closures can escape, even the access-link stack discipline breaks — the captured environment must move to the heap, because the frame it pointed at is gone.