Closures

A function in the previous chapter ran its body in the environment it captured, and the examples called functions that were defined at the top of the program, whose environment lasts as long as the program does. A function can also be made inside another call and handed back as its result:

fn make_adder(k: Int) -> fn(Int) -> Int = |x: Int| x + k;

fn make_counter() -> fn() -> Int {
    ref n = 0;
    || { n := deref n + 1; deref n }
}

fn main() {
    let add5 = make_adder(5);
    println(add5(10));                  // 15

    let c1 = make_counter();
    let c2 = make_counter();
    c1(); c1();
    println(c1());                      // 3
    println(c2());                      // 1
}

By the time add5(10) runs, the call make_adder(5) is over. Its parameter k was bound when the call began, and nothing in main can name it; yet the body x + k finds k and finds it bound to 5. make_counter goes further. Each call makes a cell and returns a function that updates it, and the cell goes on counting across calls of that function, long after the call that made it has returned. c1 and c2 each have a count of their own.

Both programs depend on a binding lasting longer than the call that created it. In most early compiled languages, a call’s bindings ended when the call did.

Bindings on a stack

Algol 60 let procedures be declared inside blocks and inside other procedures, and let a body refer to the variables of the blocks around it. The usual implementation keeps each call’s variables in an activation record on a stack: entering a block or procedure pushes a record, and leaving it pops the record, so the storage for a call’s bindings is reclaimed the moment the call returns. The Wheeler jump of the first chapter of this part kept one return address per routine; a stack keeps one record per active call, which is what lets a procedure call itself.

A stack makes a binding’s lifetime and its scope line up. A name declared in a block can be read only from the text inside that block, and while that text runs the block’s record is on the stack. As first-class functions observed, the one kind of function value Algol 60 allowed, a procedure passed down as an argument, fits the stack: the procedure is called while the routine that received it is running, which is while its defining block’s record is still in place. make_adder does not fit. It returns |x: Int| x + k upward, past the end of its own call, and a stack would pop k at exactly that moment.

Peter Landin’s “The mechanical evaluation of expressions” (1964) described a machine for evaluating expressions written in Church’s λ-notation, where functions are produced by expressions and returned like any other value. Its state has four components — a stack, an environment, a control, and a dump — and it is often called the SECD machine after them. The environment is “a list-structure made up of name/value pairs”, the same kind of object the machine computes with, so a value can hold one:

Also we represent the value of a λ-expression by a bundle of information called a “closure,” comprising the λ-expression and the environment relative to which it was evaluated.

Landin gives the closure an environment part and a control part, and notes that the environment part “would be unnecessary if λ-expressions containing free variables were prohibited.” The word closure in this book, and E-Lam’s pair of a lambda and an environment, come from this paper.

Scope and extent

The scope of a binding, as Part III defined it, is a region of program text: the part of the program where the name refers to that binding. The extent of a binding is a span of time: how long, while the program runs, the binding exists. Scope is settled by reading the program; extent is a fact about one run.

On a stack, a binding’s extent is the activation of its block — from the moment the block is entered until it is left — and since a block’s text runs only while it is active, extent and scope never disagree. A closure separates them. The body of |x: Int| x + k lies inside make_adder, so k is in scope there; but it runs when add5 is called, after make_adder’s activation has ended. For that body to find k, the binding’s extent has to reach as far as add5 can be called, and a function value can be kept, passed along, and called at any later time. Common Lisp the Language calls this indefinite extent: “The entity continues to exist as long as the possibility of reference remains.” It calls the other kind, a binding that exists from when it is established until it is explicitly disestablished, dynamic extent.

The rules of Part V already give bindings that extent, because no rule ever discards an environment. In the judgment $\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨v,{\sigma }^{\prime }⟩$, an environment is a mathematical map, and E-Lam puts one inside a value. Follow make_adder(5) and then add5(10) through the rules:

• make_adder evaluates by E-Var to its closure $⟨\lambda k.e_{add},{\rho }_0⟩$, where ${\rho }_0$ is the program environment and $e_{add}$ is the lambda |x: Int| x + k.
• E-App evaluates the body $e_{add}$ in ${\rho }_0[k\mapsto 5]$. The body is a lambda, and E-Lam turns it into the closure $⟨\lambda x.x+k,{\rho }_0[k\mapsto 5]⟩$ without evaluating anything. That closure is the call’s value, and let binds add5 to it.
• add5(10) is E-App again. The operator’s closure carries ${\rho }_0[k\mapsto 5]$, so the body x + k runs in ${\rho }_0[k\mapsto 5][x\mapsto 10]$, where $k$ is $5$, and the result is 15.

The binding $k\mapsto 5$ was made by the first call and used by the second. Between them it lived in a value — the closure bound to add5 — and the rules have no step at which a value’s contents go away. Nothing in the semantics corresponds to popping a stack. An interpreter that reclaims a scope when its block or call ends departs from the rules whenever a closure made inside that block or call is still reachable.

A call is not needed to see this. A block’s value can be a lambda that mentions the block’s own bindings:

let f = {
    let k = 3;
    |x: Int| x + k
};
f(4)                                // 7

k’s scope is the block, and the block has ended by the time f(4) runs; k’s extent is as long as f’s.

State in a captured cell

make_counter adds mutation. Its first line, ref n = 0;, is let n = ref 0;: E-Ref picks a fresh location $\ell$, puts 0 in it, and let binds n to $\ell$. The lambda on the next line captures an environment in which $n\mapsto \ell$. Each call of that lambda looks n up, finds $\ell$, reads the cell with E-Deref, and writes it with E-Assign.

The binding $n\mapsto \ell$ never changes; the store’s entry for $\ell$ does. The closure keeps the location, and the location’s contents persist in the store between calls, so the count survives. Each call to make_counter runs ref 0 again, and E-Ref’s side condition $\ell \notin \mathrm{dom}(\sigma )$ makes every run allocate a location no other cell uses. c1 and c2 are two closures over two scopes, each binding n to a different location:

The environment side of the figure is never written after it is built; every change happens in the store. Several closures can capture the same scope, and then they share its cells:

fn make_account(start: Int) -> (fn(Int) -> (), fn() -> Int) {
    ref balance = start;
    let deposit = |amt: Int| { balance := deref balance + amt; };
    let current = || deref balance;
    (deposit, current)
}

Both lambdas are evaluated in environments that bind balance to one location, so a deposit is visible to the current returned beside it: after deposit(25) and deposit(5) on an account opened with 100, current() is 130. No other code can reach that cell. balance is out of scope everywhere except the two lambda bodies, and the location travels only inside the two closures; whatever reads or changes the balance goes through one of them. A cell whose only access is through a fixed set of functions is the arrangement the objects of Part IX give a name and a syntax.

What the capture holds

A closure holds the bindings of its environment, and a binding may hold a location. Which of those the closure’s body reads at its call decides what it sees. These two loops each build a list of three functions that take no arguments:

ref fs: [fn() -> Int] = [];
for i in range(0, 3) {
    fs := (|| i) :: deref fs;
}
map(deref fs, |g: fn() -> Int| g())         // [2, 1, 0]

ref gs: [fn() -> Int] = [];
ref j = 0;
while deref j < 3 {
    gs := (|| deref j) :: deref gs;
    j := deref j + 1;
}
map(deref gs, |g: fn() -> Int| g())         // [3, 3, 3]

The for loop’s rule, E-For-Cons, evaluates the body once per element in $\rho [x\mapsto v_h]$: a fresh binding of i for each element. Each || i captures a different binding, holding 0, 1, or 2, and calling it later returns that number. The list comes out in reverse because each new function is consed on the front.

The while loop has one binding, j bound to one location, and all three || deref j capture it. None of them reads the cell until it is called, and by then the loop has left 3 there. To keep the value the cell held on a given turn, the body has to read it on that turn and bind the result:

    let v = deref j;
    gs := (|| v) :: deref gs;

and the list becomes [2, 1, 0]. In both loops the closure captured exactly its environment. The difference is whether the name it reads is bound to a number or to a cell.

Building it

There is no new arm. The Lambda arm from first-class functions stores the environment it was handed in a Closure::Bridger, and the Call arm from the previous chapter extends that environment with the parameters. Those two arms already run every program in this chapter. What remains is why the environment they share survives the call that built it.

An Env is a handle to a scope chain, and cloning one clones an Rc:

pub struct Env(Rc<Scope>);   // cheap to clone: one more holder

enum Scope {
    Frame { name: Name, val: Value, parent: Env },
    // … the root scope, built by provided setup
}

Trace make_adder(5) through the arms. The Call arm calls extend to bind k to 5, building a new scope $S$ whose parent is the root, and holds it in a local variable while the body runs: one holder. The body is a lambda, so the Lambda arm builds a closure whose env is a clone of that handle: two holders. The body’s value goes back to the Call arm, which returns it and drops its local: one holder, the closure. $S$ stays alive because the closure still points to it, and let add5 keeps the closure. When add5 is no longer reachable, the closure is dropped, $S$’s count reaches zero, and $S$ is freed, which in turn drops one holder of the root. A scope lives as long as the last closure or evaluation that can reach it, which is the extent the rules require.

Rust’s own closures meet the same problem, and the compiler reports it. The adder, written in Rust with a closure that borrows its free variable:

fn make_adder(k: i32) -> impl Fn(i32) -> i32 {
    |x| x + k
}

is rejected:

error[E0373]: closure may outlive the current function, but it borrows `k`,
              which is owned by the current function
 --> r1.rs:2:5
  |
2 |     |x| x + k
  |     ^^^     - `k` is borrowed here
  |     |
  |     may outlive borrowed value `k`
  …
help: to force the closure to take ownership of `k` (and any other referenced
      variables), use the `move` keyword

A borrow of k is a pointer into make_adder’s activation, and the activation ends at the return. Writing move |x| x + k copies k into the closure, and the program compiles. An interpreter whose Closure held a borrowed &Env would run into the same kind of error for the same reason, at the first lambda returned from a call. Holding an Rc gives the closure a share in the scope’s ownership, so the scope’s lifetime is set by the count of its holders.

The scope chain needs no RefCell for this. Bindings are immutable, and cells live in the store, whose Loc handles are plain indices; a captured scope is read, never written, so a shared read-only Rc is enough. (The root is the exception, and provided setup handles it: every top-level fn is a closure that captures the root, and the root holds every top-level fn, which is how they can call one another. That circle of Rcs is never freed, and does not need to be, since the root is in use for the whole run.)

The design space

Every language with closures decides what a closure captures when a captured variable can change, and where captured environments are kept.

Capturing variables and capturing values

In Scheme and JavaScript a closure captures the variable itself. An assignment made to the variable after the closure is created is seen by the closure, and an assignment made by the closure is seen outside it. Python closures capture the variable too, though an assignment inside a closure makes a new local unless the name is declared nonlocal. The bank account of Structure and Interpretation of Computer Programs (§3.2.3) is make-withdraw, a procedure whose returned lambda assigns to its own parameter balance with set!; the parameter is the account’s state, with no separate cell.

C++ asks the programmer to decide, one variable at a time. A lambda’s capture list takes a variable by copy ([=], or the bare name) or by reference ([&], or &name). A copy is made when the lambda is created and is unaffected by later assignments. A reference follows the variable, and cppreference states what happens when the variable is gone: calling the closure after the captured entity’s lifetime has ended is undefined behaviour, and “C++ closures do not extend the lifetimes of objects captured by reference.” Rust makes the same choice with borrowing and move, and the borrow checker rejects a borrowing closure that would outlive what it borrows, as E0373 showed.

Java removes the question. The Java Language Specification (§15.27.2) requires that “any local variable, formal parameter, or exception parameter used but not declared in a lambda expression must either be final or effectively final” — never assigned after its initialization — and gives the reason: the restriction “prohibits access to dynamically-changing local variables, whose capture would likely introduce concurrency problems.” When the variable cannot change, a copy and the variable are indistinguishable, and the implementation copies.

ML and Bridger arrive at Java’s position from the other side. No binding is ever assigned, so every capture behaves as a copy, and state that a closure shares with anything else lives in a ref cell, created by a visible ref and reached through deref and :=. Scheme’s make-withdraw and Bridger’s make_account keep their state the same way; in Bridger the shared state is marked where it is made.

Loops

Closures made inside a loop show the difference between one variable per loop and one per turn. The Python FAQ has an entry, “Why do lambdas defined in a loop with different values all return the same result?”: a loop variable is a single variable, “accessed when the lambda is called — not when it is defined,” so every lambda sees its last value. The fix it gives is lambda n=x: n**2, a default argument evaluated when the lambda is made — the let v = deref j of the while example above.

Several languages have changed their loops so that each turn gets a fresh variable. ECMAScript 2015 gave a for loop whose variable is declared with let a new binding for each iteration, copied from the previous one (the abstract operation CreatePerIterationEnvironment, §13.7.4.9 of the 6th edition); a loop variable declared with the older var is still one variable for the whole loop. C# 5 made the variable of a foreach loop fresh on each iteration and left the for loop alone; Eric Lippert’s “Closing over the loop variable considered harmful” (2009) set out the case, and an update at its head records the decision. Go 1.22, released in February 2024, did the same for the variables declared by every for loop. Its release notes say: “Previously, the variables declared by a ‘for’ loop were created once and updated by each iteration. In Go 1.22, each iteration of the loop creates new variables, to avoid accidental sharing bugs.”

The C# and Go changes altered the meaning of existing programs, made after the one-variable loop had been in use for years. ECMAScript’s did not: let was new in the same edition, and a var loop kept its meaning. Bridger’s for rule binds the loop variable afresh for each element from the start, and since no binding can be assigned, a closure that captures a loop variable sees one value. The shared behaviour can still be written, with a while loop over a cell, and then the cell is in the program text.

Where environments live

A language can keep environments on a stack only if no closure outlives the activation it captured. Algol 60 and Pascal guarantee that by letting a procedure be passed down and nowhere else. GNU C allows a function to be defined inside another as an extension, and a pointer to the inner function can be stored or returned like any function pointer; the inner function’s free variables are the outer function’s locals, which live on the stack. The GCC manual says the technique “works only so long as the containing function … does not exit”, and: “If you try to call the nested function through its address after the containing function exits, all hell breaks loose.” The language leaves the extent of the environment to the stack and the burden of respecting it to the programmer.

Languages with unrestricted closures keep captured environments in the heap and reclaim them when nothing refers to them. Bridger’s interpreter counts references with Rc. A tracing garbage collector — Scheme’s, ML’s, JavaScript’s, Java’s — instead periodically finds everything reachable from the running program and frees the rest. Reference counting frees a scope the moment its last holder goes, and cannot free a cycle, like the root’s; tracing collects cycles, and does its work in periodic passes over everything still in use.

A closure also need not hold its whole environment. Bridger’s closure holds a pointer to the scope chain, which keeps every binding along the chain alive, including ones the body never mentions. An implementation can instead build a flat closure, copying into it the values of just the free variables of the body, so the body reads them without a walk and nothing else is kept alive. The copy is correct only if the captured variables cannot change afterwards — the condition Java imposes, and the one Bridger’s immutable bindings meet everywhere. When a language lets captured variables be assigned, its compiler first moves each such variable into a heap cell and copies the cell’s location, which is the arrangement a Bridger program writes out by hand with ref.

Further reading

The closure and the machine: Landin’s “The mechanical evaluation of expressions” (1964) defines closures and the four-part machine that evaluates with them, together with the treatment of expressions in λ-notation that the machine runs.

Scope and extent: chapter 3 of Guy Steele’s Common Lisp the Language, 2nd edition (1990) defines lexical and indefinite scope, dynamic and indefinite extent, and shows which Common Lisp constructs have which, including a compose whose parameter bindings outlive its call.

Local state in closures: §3.2 of Abelson and Sussman’s Structure and Interpretation of Computer Programs draws environments as linked frames and follows make-withdraw through them, showing where each account’s balance lives.

Loops and captured variables: Eric Lippert’s two posts, “Closing over the loop variable considered harmful” and its part two (2009), lay out the arguments for and against changing the meaning of C#’s foreach, from a member of the team that made the change.

Concept checks