Closure

A closure is a function value together with the environment in which it was created: the bindings of the free variables that its body refers to. Closures are what make functions first-class values in a lexically scoped language, since a function can be returned from the scope that defined it and still refer to that scope's variables. Compilers implement them by closure conversion, which turns each function into a pair of a code pointer and a record of the captured values.

§ 01

Overview

In $λ x . k \cdot x + b$ the variable $x$ is bound by the lambda, and $k$ and $b$ are free: their meaning comes from outside. A function like this only makes sense together with values for $k$ and $b$ , and a closure is that combination. Each call to a function that returns a function creates a new closure, with its own copy of the environment:

Lexical scope, and functions that return functions.

(* Lexical scope: f sees the x that was in scope where f was written. *)
let x = 1
let f () = x
let result = let x = 2 in ignore x; f ()   (* dynamic scope would give 2 *)
 
(* Functions that return functions: each result remembers its own n. *)
let adder n = fun k -> k + n
let add5 = adder 5
let add10 = adder 10

Running it.

f () under a new x = 2  ->  1
add5 1, add10 1         ->  6, 11

f refers to the x that was in scope where f was written, not the one in scope where it is called; under dynamic scope the call would return 2. adder returns a different closure for each argument, and each remembers its own n.

§ 02

Definition

The free variables of a term are the variables it uses without binding:

FV (x) = {x} FV (λ x . e) = FV (e) ∖ {x} FV (e_{1} e_{2}) = FV (e_{1}) \cup FV (e_{2})

In an environment-based semantics a closure is a triple of the parameter, the body, and an environment $ρ$ giving values to at least the free variables of $λ x . e$ . Evaluating a lambda captures the current environment; applying a closure evaluates the body in the captured environment extended with the argument:

ρ ⊢ λ x . e ⇓ ⟨ x, e, ρ ⟩ \frac{ρ ⊢ e _{1} ⇓ ⟨ x , e , ρ ^{'} ⟩ ρ ⊢ e _{2} ⇓ v ρ ^{'} [ x \mapsto v ] ⊢ e ⇓ w}{ρ ⊢ e _{1} e _{2} ⇓ w}

The body runs in $ρ^{'}$ , the environment of the definition, not $ρ$ , the environment of the call. That single choice is lexical scoping. Landin introduced the term closure for this pairing in his SECD machine^[1].

§ 03

Scope and the funarg problem

Early Lisps used dynamic scope: a free variable meant whatever binding was most recent at run time. Passing functions as arguments or returning them then gave results that depended on where the function was called from, the "funarg problem"^[2]. Returning a function from the scope that defines its free variables, the upward funarg case, is the harder half, because those variables must outlive the stack frame that created them. The answer is to capture the environment when the function is created and keep it on the heap for as long as the function is reachable. Scheme made lexical scope with closures the rule for a Lisp in 1975^[3], and nearly every language with first-class functions has followed.

§ 04

Capture

A closure captures variables, not the values of expressions, and what that means depends on whether variables can be reassigned. In OCaml a variable is immutable, so capturing it and capturing its value are the same thing. Mutable state lives in explicit references, and closures that capture the same reference share it:

Several closures sharing one hidden reference, and capture in a loop.

(* Several closures over one hidden reference: an object without a class. *)
type account = { deposit : int -> unit; withdraw : int -> bool; balance : unit -> int }
 
let make_account initial =
  let total = ref initial in
  { deposit = (fun n -> total := !total + n);
    withdraw = (fun n -> if n <= !total then (total := !total - n; true) else false);
    balance = (fun () -> !total) }
 
(* A loop binds a fresh i each iteration; a ref is one shared location. *)
let by_value = List.init 3 (fun i -> fun () -> i)
let by_reference = let r = ref 0 in List.init 3 (fun i -> r := i; fun () -> !r)

Running it.

a.balance, b.balance        ->  120, 5   (withdrawals: true, false)
closures over the loop's i  ->  0, 1, 2
closures over one ref       ->  2, 2, 2

The account is an object built from closures: three functions sharing private state that nothing else can reach. The loop shows the difference between the two kinds of capture. Each iteration binds a new i, so each closure keeps its own; the last three closures all capture one reference, and all read its final contents.

Languages where variables are mutable have to choose. Python and JavaScript capture the variable itself, so closures created in a loop over a single variable all see its last value; JavaScript's let gives each iteration a fresh binding for that reason, and C# changed its foreach loop to do the same. Java requires captured local variables to be effectively final, which makes the question disappear. C++ lambdas list their captures explicitly, by value ([=]) or by reference ([&]); capturing a local by reference in a lambda that outlives the function is undefined behaviour.

§ 05

Implementation

Closure conversion

Compilers eliminate free variables before generating code. Closure conversion turns each function with free variables $y_{1}, \dots, y_{n}$ into closed code that takes the environment as an extra argument, paired with a record of the captured values^[6]:

[[λ x . e]] = ⟨ λ (ρ, x) . [[e]] [ρ .1/ y_{1}, \dots, ρ . n / y_{n}], (y_{1}, \dots, y_{n}) ⟩ [[e_{1} e_{2}]] = let ⟨ c, ρ ⟩ = [[e_{1}]] in c (ρ, [[e_{2}]])

Closure conversion by hand. The existential type lets closures with different environments share one type.

(* Closure conversion by hand. The source program:
     let compose f g = fun x -> f (g x)
     let scale k = fun x -> k * x
     let offset b = fun x -> x + b
   After conversion no function has free variables: each closure is a
   code pointer paired with an environment record, and application
   passes the environment explicitly. *)
type closure = Clo : ('env -> int -> int) * 'env -> closure
 
let apply (Clo (code, env)) x = code env x
 
let scale_code k x = k * x
let offset_code b x = x + b
let compose_code (f, g) x = apply f (apply g x)
 
let scale k = Clo (scale_code, k)
let offset b = Clo (offset_code, b)
let compose f g = Clo (compose_code, (f, g))
 
(* The same program with OCaml's own closures, for comparison. *)
let compose' f g = fun x -> f (g x)
let scale' k = fun x -> k * x
let offset' b = fun x -> x + b

Running it.

converted: apply (compose (scale 3) (offset 4)) 5  ->  27
native:    (compose (scale 3) (offset 4)) 5        ->  27

In a typed language the environment's type differs between closures of the same function type, so the converted program needs an existential type to hide it; typed closure conversion formalises this^[8].

Representation

A flat closure copies every captured value into one record, so accessing a variable is one load but creating the closure copies them all. A linked closure points to the enclosing function's environment instead, which is cheap to create but slower to access and can keep a whole chain of environments alive. Shao and Appel showed that some choices make a program use asymptotically more space than necessary, and gave a representation that is safe for space^[7]. OCaml's native compiler uses flat closures: a code pointer, arity information, and the captured values.

Lambda lifting and defunctionalization

Two other transformations remove closures. Lambda lifting turns free variables into extra parameters and moves the function to the top level, which works when every call site can supply them^[5]. Defunctionalization replaces every function value the program can create by a constructor of a data type, and every application by a call to one apply function that matches on it^[4]:

Lambda lifting, and a defunctionalized pipeline of arithmetic functions.

(* Lambda lifting: instead of capturing k, the inner function takes it as
   an extra parameter and becomes a top-level function. *)
let sum_scaled k xs = List.fold_left (fun acc x -> acc + (k * x)) 0 xs
 
let step k acc x = acc + (k * x)                       (* lifted, closed *)
let sum_scaled_lifted k xs = List.fold_left (step k) 0 xs
 
(* Defunctionalization: every function value the program can create
   becomes a constructor, and one apply function interprets them. *)
type fn = Scale of int | Offset of int | Compose of fn * fn
 
let rec apply f x =
  match f with
  | Scale k -> k * x
  | Offset b -> x + b
  | Compose (f, g) -> apply f (apply g x)
 
(* A pipeline described as data can be printed, compared or serialised. *)
let rec show = function
  | Scale k -> Printf.sprintf "(* %d)" k
  | Offset b -> Printf.sprintf "(+ %d)" b
  | Compose (f, g) -> show f ^ " . " ^ show g

Running it.

sum_scaled 3 [1; 2; 3], lifted  ->  18, 18
apply ((* 3) . (+ 4)) 5  ->  27

After defunctionalization the program is first-order: a pipeline is data, and can be printed, compared or sent over a network. Reynolds introduced the transformation to relate higher-order interpreters to first-order ones.

§ 06

Memory

A closure keeps everything it captures alive for as long as the closure is reachable, which in a garbage-collected language is the source of a common leak: a small callback stored in a long-lived table that happens to capture a large structure. Closure creation is a heap allocation, cheap in a language with a generational collector, where short-lived closures die in the minor heap. A function with no free variables needs no environment, and compilers allocate its closure once, statically.

§ 07

Related ideas

Currying produces a closure on every partial application: applying a two-argument function to one argument returns a function that has captured the first. Continuation-passing style represents "the rest of the computation" as a closure. Objects and closures can each simulate the other: an object is a record of closures over shared state, as with the account above, and a closure is an object with one method.

§ 08

History

Landin defined closures in 1964 as part of the SECD machine, an abstract machine for evaluating lambda expressions^[1]. Moses described the funarg problem in Lisp in 1970^[2]. Scheme adopted lexical scope and closures in 1975^[3], and Common Lisp followed; ML, Haskell and the functional languages had them from the start. In mainstream languages they arrived as anonymous functions: Smalltalk blocks, JavaScript functions, C# anonymous methods in 2005, C++ lambdas in 2011 and Java lambdas in 2014.