Closure Conversion: Flat Closures, Displays, and Boxed Upvalues

A function that refers to a variable declared outside it cannot be compiled to a plain code pointer. The code needs the variable’s location at call time, and the location is not an argument the caller supplies. Closure conversion is the rewrite that makes the dependency explicit: the function becomes a pair of code and environment, and the environment’s layout becomes a decision the compiler must make, with consequences for allocation, call overhead, and mutation semantics.

The problem in one example

(define (make-counter)
  (let ((n 0))
    (lambda () (set! n (+ n 1)) n)))

The inner lambda refers to n, which is a local of make-counter. After make-counter returns, its stack frame is gone, but the closure must still be able to read and write n, and two closures created by two separate calls to make-counter must have independent ns. The compiler has to answer three questions: where does n live, how does the closure find it, and how is the answer represented in the closure’s layout.

Flat closures copy the free variables

The simplest answer is to copy every free variable into the closure at creation time. The closure becomes a heap object with a code pointer followed by the values of the variables it references:

+-------------------+
| code pointer      |
| free var 0        |   <- value of n, copied
| free var 1        |
+-------------------+

Calling the closure passes a pointer to this object as an implicit argument, and the function body accesses its free variables by offset from that pointer. The call convention is now uniform: a closure is a pointer, and the code’s first parameter is the closure itself.

Copying is correct only if the captured variable is never assigned after capture, or if the language semantics say the closure sees a snapshot. For mutable variables, copying breaks the shared state: the inner lambda above does set! n, and a copy would increment a private field, so the closure would still be a counter but the enclosing scope would not see the change. Languages that allow mutation of captured variables must box the variable instead.

The other cost of flat closures is duplication. A closure nested two levels deep that references a variable from the outermost function copies that variable at every level, so the closure’s size grows with the number of free variables transitively referenced. Each copy is a store at closure creation time. For a closure created in a loop, that is a store per iteration per free variable, and it is the reason implementations with flat closures try to keep the number of captured variables small.

Linked environments and the display

The alternative is to keep the environment as a chain. Each function’s frame has a pointer to its lexical parent’s frame, and a closure stores a pointer to the frame in which it was created. Access to a variable at lexical depth d follows d parent pointers.

frame of make-counter        frame of inner lambda
+-------------+              +-------------+
| parent: nil | <-----------+ parent -----+
| n: 0        |              | ...         |
+-------------+              +-------------+

The chain representation makes closure creation cheap, since the closure stores one pointer regardless of how many variables it captures, and it preserves mutation naturally because the closure points at the variable’s actual storage. The cost is on access: every reference to a non-local variable walks the chain, and the walk is a sequence of dependent loads, each of which can miss in cache. For code that reads an outer variable inside a hot loop, the walk is the loop’s inner cost.

A display collapses the walk. It is an array indexed by lexical depth, holding a pointer to the frame at each level, so access to depth d is one indexed load. Maintaining it requires work at every call and every return: entering a function at depth d saves the current display entry for d and installs the new frame; returning restores it. The save and restore are two memory operations per call, which is cheap relative to the call itself but not free, and the display’s size is bounded by the maximum lexical nesting depth, which is a static property.

Displays come from the implementation of block-structured languages with nested procedures, where they were used to reach non-local variables in languages without closures. Their weakness in a language with first-class functions is that the display is per-activation, so a closure that outlives its creating frame cannot simply keep the display: the frame is gone and the display slot has been reused. Implementations that use displays for closures must copy the relevant frames to the heap on escape, which turns the display into a cache over heap frames rather than a direct view of the stack.

Boxed variables and the assignment problem

The representation that handles mutation without copying is the box. A variable that is captured and assigned is allocated on the heap as a one-field cell, and both the enclosing scope and the closure refer to the cell rather than to a stack slot.

typedef struct { Value value; } Cell;

/* The closure's environment holds the cell, not the value. */
typedef struct {
    Code fn;
    Cell *n;          /* shared with the enclosing frame */
} CounterClosure;

static Value counter_call(CounterClosure *self) {
    self->n->value = int_add(self->n->value, 1);   /* mutation is visible to both */
    return self->n->value;
}

The allocation happens once, at the point where the variable comes into scope, not once per closure. Two closures created in the same activation share the same cell, which is what makes the language’s aliasing semantics work: incrementing through one closure is visible through the other. Two activations get two cells, which is what makes separate counters independent.

Boxing has a cost on the enclosing function too. Every read and write of the variable now goes through a pointer, even inside the function that owns it, because the compiler cannot know whether a closure will be created later in the same scope. An optimization pass can prove that a variable is never captured, or that it is captured but never assigned and the closure does not escape the activation, and unbox it in those cases. The analysis is escape analysis, and its precision determines how much of the boxing cost a program pays.

The interaction with tail calls is worth noting: a tail call that reuses the caller’s frame is unaffected by boxing, because a boxed variable lives on the heap and its cell is independent of the frame’s address. What a frame-reusing call must not do is keep a pointer to the reused frame in a place that outlives it, which is why a compiler that performs proper tail calls and also hands out addresses of locals has to reconcile the two. Implementations either keep every captured variable in a heap cell and reuse the frame freely, or decline to reuse a frame while any variable that is addressed rather than copied is still live. A stack frame that must be preserved for a closure’s sake also cannot be reclaimed on return, which is one reason runtimes with first-class closures and movable stacks have to describe captured frames precisely, as the safepoint metadata does.

Choosing a representation by cost profile

The three representations have different cost profiles, and the right choice depends on which operation dominates.

Flat closures make creation proportional to the number of free variables and access constant-time. They suit code that creates many short-lived closures with few captures, which is the common shape in chained collection code, and they suit compilers that want the closure to be a fixed-size object whose size is known statically.

Linked environments make creation a single store and access proportional to lexical depth. They suit code that creates closures rarely and calls them in hot loops, provided the depth is shallow. They also make the environment a natural target for a copying collector, since the chain is a heap graph the collector already understands.

Boxes make mutation semantics exact and access constant-time, at the cost of an allocation per captured-and-assigned variable. They suit languages where assignment to captured variables is idiomatic, and they are the representation that a compiler for a language with set! almost has to use unless it can prove the assignment does not cross the closure boundary.

Real implementations mix them. A compiler may use flat closures for immutable captures and boxes for mutable ones in the same function, choosing per variable rather than per closure. The closure’s layout then records, for each free variable, whether the slot holds a value or a pointer to a cell, and the generated access code differs accordingly. The cost of that flexibility is a slightly larger closure and a more complex access path, which is why the decision is usually made by the optimizer after escape analysis rather than by the programmer.

What the calling convention must carry

Once closures exist, every indirect call needs the environment pointer. In a uniform representation, the callee’s first argument is the closure object, and the code reads its free variables through it. That costs one register in the calling convention, and it means a closure call cannot be a direct call even when the target is statically known, unless the compiler devirtualizes it.

Devirtualization is the standard optimization: if the compiler can prove that a particular call site always invokes the same closure, it can emit a direct call and pass the environment explicitly, which allows inlining and removes the indirect branch. This is the same mechanism that inline caches provide for method dispatch, applied to a different kind of target. The difference is that method dispatch has a receiver whose shape can be checked cheaply, while a closure has only its identity, so the check is a pointer comparison against the last-seen closure.

A final wrinkle: a closure that captures nothing needs no environment. Implementations special-case it, storing only the code pointer, so a capture-free closure is the same size as a plain function pointer. The special case is worth having because it makes higher-order code that passes stateless functions around as cheap as passing function pointers, and it removes an allocation from a path that can be hot in code that builds callbacks.