Closure

A function value together with the environment it was defined in: the values of the free variables its body refers to. Closures are what make functions first-class in a lexically scoped language, and closure conversion is the compiler pass that turns them into ordinary data: a code pointer and a record of captured values.

In $\lambda x.k\cdot x+m$ the variables $k$ and $m$ are free. The function means something only together with their values at the point where it was created, and a closure is that pair: code and environment.

(* make_counter returns a function that closes over a fresh reference. *)
let make_counter () =
  let n = ref 0 in
  fun () -> incr n; !n
 
(* A for loop binds a new i each iteration, and each closure keeps the
   value it saw. A shared reference is one location, and every closure
   sees its final contents. *)
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)
 
(* Closure conversion by hand: the free variables become an explicit
   environment passed to code that has none of its own. *)
type env = { k : int; m : int }
let code env x = (env.k * x) + env.m
let make_affine k m = (code, { k; m })
let apply (f, env) x = f env x

c1 (), c1 (), c2 ()            ->  1, 2, 1
by_value closures              ->  0, 1, 2
by_reference closures          ->  2, 2, 2
apply (make_affine 3 4) 5      ->  19

Each call to make_counter creates a new reference and a new closure over it, so c1 and c2 count independently. The loop's closures each capture the i of their own iteration. The last three capture one reference between them, and all read its final contents. Closures capture variables, and OCaml variables are immutable, so the surprise in other languages, loop closures all seeing the last index, happens here only through an explicit ref.

Closure conversion makes the environment explicit. Each function with free variables $y_1,\dots ,y_n$ becomes a closed piece of code taking the environment as an extra argument, paired with a record of the captured values:

and application unpacks the pair, as apply does above. After it, no function refers to a variable it does not bind, and functions can be compiled to plain code. The environment is heap-allocated, which is why closures cost an allocation and why capturing a large structure keeps it alive.

Landin introduced closures to give an evaluation model for Lisp and ALGOL-like languages with first-class functions.^[1] Lambda lifting is the alternative to closure conversion: instead of an environment record, the free variables become extra parameters, which works only when every call site can supply them.

• CurryingTurning a function of several arguments into a function of the first argument that returns a function of the rest: f : A * B -> C becomes curry f : A -> (B -> C). In OCaml and Haskell every function is curried, so applying it to fewer arguments than it takes, partial application, is ordinary.
• CPSContinuation-passing style: instead of returning, a function takes an extra continuation argument and calls it with the result. Every call becomes a tail call, which is what lets a CPS-transformed program run in constant stack space wherever tail calls are eliminated, and it makes control flow a value that can be stored and resumed.
• Tail callA call whose result is returned directly, with nothing left for the caller to do. The caller's frame can be reused for it, so a loop written as tail recursion runs in constant stack space. OCaml guarantees this, and the [@tailcall] attribute makes the compiler warn when a call marked with it is not one.
• Generational GCA garbage collector that splits the heap by age, because most objects die young: new objects go to a small nursery collected often by copying, and survivors are promoted to a larger heap collected rarely. A write barrier records old-to-young pointers so that a minor collection need not scan the old heap.

1. [1]P. J. Landin, “The mechanical evaluation of expressions”, The Computer Journal 6 (1964).
2. [2]A. W. Appel, Compiling with Continuations, Cambridge University Press (1992).
3. [3]T. Johnsson, “Lambda lifting: transforming programs to recursive equations”, FPCA (1985).