Lesson 11.8 — Closure conversion and lambda lifting (overview)¶

Techniques: closure conversion — a function value that refers to variables of an enclosing function becomes a pair of code (a top-level function taking an explicit environment parameter) and an environment record holding the captured variables (Landin 1964; Appel & Jim 1989; typed: Minamide, Morrisett & Harper 1996); lambda lifting — a local function that does not escape becomes a top-level function whose free variables are passed as extra parameters, so no environment is allocated at all (Johnsson 1985) · Pebble implements: none — Pebble functions are top-level and not values (spec §4.3 rule 2); this lesson prepares the Ch 24 extension "closures for Pebble" and explains what other front ends emit before their code reaches LLVM · Prerequisites: Lesson 11.5 (passing records); scopes (Ch 5) · Time: 3 hours

LLVM IR has no nested functions: every define is at the top level and sees only its parameters and globals. A language with nested functions that refer to their enclosing function's variables (OCaml, Rust closures, Java lambdas, Swift, C++ lambdas, Go function literals) must remove those references before emitting LLVM IR. The two classic transformations do it in different ways. The running example, in a small functional syntax with Pebble's arithmetic:

fn outer(a, b) {
    fn f(x) = x + a              // free variable: a
    fn g(y) = f(y) * b           // free variables: b, and those of f
    return g(1) + f(2)
}
fn make_adder(k) = fun x -> x + k   // escapes: returned as a value

1. Problem and motivation¶

Closure conversion¶

Landin's SECD machine represented a function value as a closure: the code together with the environment in which it was defined [Lan64]. A compiler makes this explicit: every function becomes closed (no free variables) by taking its environment as an extra parameter, and every function value becomes a record holding a code pointer and the captured values. Appel and Jim formulated it as a source-to-source transformation in a CPS compiler [AJ89], and Minamide, Morrisett and Harper showed how to type it, with the environment as an existential type [MMH96]. OCaml's closure.ml [OCAML-Closure], Rust's closures (a struct of the captures implementing Fn), C++ lambdas (a class with operator()) and Swift closures are all closure-converted before code generation. It is the only option when a function value escapes — is returned, stored, or passed to unknown code — because its environment must outlive the call that created it.

Lambda lifting¶

Johnsson observed that a local function that is only called (never used as a value) needs no closure: pass its free variables as additional arguments and move it to the top level [Joh85]. The result is a set of first-order recursive equations — no environment allocation, and the free variables travel in registers. Java compiles lambda bodies this way (lambda$main$0 methods with the captures as leading parameters), leaving only the capture to a small object [JAVAC-Lambda]; Go rewrites a directly called function literal into a call with the captured variables as arguments (directClosureCall) [GO-Closure]; GHC lambda-lifts late in its pipeline. The price: every call site must pass all the extra arguments, and functions that call each other need the union of their free variables.

2. Definitions and algorithms¶

Definition 11.8.1 (Free variables, escaping function)

$\mathrm{FV}(e)$, the free variables of $e$, are the variables $e$ uses that are not bound inside $e$ (parameters and local bindings of $e$ itself). A local function escapes if it is used other than in the function position of a call: returned, stored, passed as an argument, or captured by an escaping function.

Algorithm 11.8.2 (Closure conversion)

Input: a program with nested functions and function values.
Output: a program of closed top-level functions and explicit closure records.
Precondition: names are unique (alpha-renamed) and $\mathrm{FV}$ is computed for every function.
Postcondition: every top-level function is closed; the program computes the same values (Theorem 11.8.3).
Invariant: inside the converted code of a function $f$, the variable env holds a record with one field per variable of $\mathrm{FV}(f)$, whose values are those at the time the closure was created.

function CC(e, env):                                   # env: variable → how to reach it
    x (a variable):          return env[x]             # a parameter, or env.x
    λx. body:                ys ← FV(λx. body)  (sorted)
                             code ← NewTopLevel(params = (envp, x),
                                                body = CC(body, {x ↦ x} ∪ {y ↦ envp.y | y ∈ ys}))
                             return MakeRecord(code, [CC(y, env) for y in ys])     # the closure
    e1(e2):                  c ← CC(e1, env)
                             return c.code(c, CC(e2, env))                        # pass the closure as envp
    other forms:             recurse structurally

Theorem 11.8.3 (Closure conversion preserves meaning)

For every closed program $p$, $\mathrm{CC}(p)$ evaluates to the same result as $p$ (for results of base type), under call-by-value evaluation with captures by value.

Proof sketch (full proof: [MMH96])

By a simulation between the source's environment semantics and the target: a source closure $\langle \lambda x.\,\mathit{body}, \rho \rangle$ corresponds to the record $\langle \mathit{code}, \rho(y_1), \dots, \rho(y_k) \rangle$ with $\{y_1, \dots, y_k\} = \mathrm{FV}(\lambda x.\,\mathit{body})$. Applying the source closure evaluates $\mathit{body}$ in $\rho[x \mapsto v]$; the target evaluates the converted body with $x \mapsto v$ and each $y_i$ read from the record, which holds $\rho(y_i)$ by the invariant; variables outside $\mathrm{FV} \cup \{x\}$ are not used by $\mathit{body}$, so the two evaluations agree step for step (induction on the evaluation derivation). Minamide, Morrisett and Harper prove the typed version by a logical relation; with mutable captured variables the record must hold references (boxes) instead of values, which is what Rust's by-reference captures and OCaml's ref cells are.

Algorithm 11.8.4 (Lambda lifting, after Johnsson)

Input: a function with local functions $f_1, \dots, f_m$ that do not escape (Definition 11.8.1).
Output: top-level functions $f_i'$ with extra parameters, and rewritten calls.
Precondition: no $f_i$ escapes; names are unique.
Postcondition: every $f_i'$ is closed; each call $f_i(\vec{a})$ becomes $f_i'(\vec{E_i}, \vec{a})$ with $E_i$ the extra variables of $f_i$ (Theorem 11.8.5).
Invariant: after iteration $t$ of the loop, $E_i^{(t)} \subseteq E_i$ (the least solution).

function LambdaLift(f_1 .. f_m):
    for each i: E_i ← FV(f_i) \ {f_1, …, f_m}              # direct free variables
    repeat                                                 # least fixed point
        changed ← false
        for each i, for each f_j called by f_i:
            if E_j ⊄ E_i: E_i ← E_i ∪ E_j; changed ← true
    until not changed
    for each i: f_i' ← top-level function with parameters (E_i sorted, original params)
    rewrite every call f_i(a…) (in the f's and in the enclosing function) to f_i'(E_i…, a…)

Theorem 11.8.5 (Lambda lifting is correct for non-escaping functions)

If no $f_i$ escapes, the lifted program computes the same values, and the loop terminates after at most $m \cdot \lvert V \rvert$ changes, $V$ the variables of the enclosing function.

Proof

Termination: each change adds a variable of $V$ to some $E_i$, and the sets only grow, so there are at most $m \lvert V \rvert$ changes. Fixed point: at the end, $E_i \supseteq E_j$ whenever $f_i$ calls $f_j$, so every variable $f_j'$ needs is available in $f_i'$ as a parameter of the same name. Correctness: inside the enclosing function every variable in $E_i$ has one value at a call of $f_i$ (names are unique, and if captured variables are mutable they are passed by reference, as Go's &byref parameters are); passing it explicitly gives $f_i'$ the same value its body read from the enclosing scope, so by induction on the call depth every call returns the same value. The precondition matters: an escaping $f_i$ could be called after the enclosing function returns, or by code that does not know the extra parameters.

3. Worked example¶

Closure conversion¶

make_adder(k) = fun x -> x + k escapes (it is returned). $\mathrm{FV}(\texttt{fun } x \to x + k) = \{k\}$, so Algorithm 11.8.2 creates adder_code(envp, x) = x + envp.k and returns the record ⟨adder_code, k⟩. The call make_adder(3)(4) becomes: c ← ⟨adder_code, 3⟩; c.code(c, 4) = 4 + c.k = 7. OCaml does exactly this for the partial application make_adder k (box in §7): a closure whose field 2 holds k, read back by (field 2 env).

Lambda lifting¶

outer's local functions do not escape. The fixed point of Algorithm 11.8.4:

iteration	$E_f$	$E_g$	change
init	{a}	{b}	direct free variables
1	{a}	{a, b}	$g$ calls $f$: add $E_f$ to $E_g$
2	{a}	{a, b}	no change: fixed point

Lifted: f'(a, x) = x + a; g'(a, b, y) = f'(a, y) * b; outer(a, b) = g'(a, b, 1) + f'(a, 2). No record is allocated; a and b travel as arguments. Java's lambda$makeAdder$0(int, int) in §7 is the same transformation applied to a lambda body, with the capture k as the first parameter.

4. Invariants and correctness¶

Closure conversion¶

Theorem 11.8.3. The invariant — the record holds the captured values from creation time — is also what makes the choice between capture by value and by reference observable: C++ [=] vs [&], Rust move vs borrowing closures (the rustc box in §7 captures by reference: the record holds two pointers). With by-reference capture the variable must outlive the closure, which Rust's borrow checker enforces and C++ leaves to the programmer.

Lambda lifting¶

Theorem 11.8.5; the precondition "does not escape" is checked by an escape analysis. A function that escapes can still be partially lifted: lift its code and build a closure only for the escaping uses (the variant OCaml uses when it uncurries make_adder's definition into a two-argument function).

5. Complexity¶

$n$ = program size, $m$ = local functions, $\lvert V \rvert$ = variables of an enclosing function, $k$ = captured variables of a closure.

Technique	Compile time	Run-time cost	Justification
Closure conversion	$O(n + \sum_f \lvert \mathrm{FV}(f) \rvert)$	allocate a record of $k + 1$ words per closure creation; one indirect call per application	FV computed once per function; each creation copies $k$ values
Lambda lifting	$O(m^2 \lvert V \rvert)$ with the naive fixed point; $O(n^2)$ with Danvy and Schultz's graph method [DS02]	0 allocation; $\lvert E_i \rvert$ extra arguments per call	Algorithm 11.8.4: at most $m \lvert V \rvert$ changes, each scanning $O(m)$ call edges

Pathological family (lambda lifting). A chain of $m$ local functions $f_1 \to f_2 \to \dots \to f_m$ where $f_m$ uses $\lvert V \rvert$ variables: every $f_i$ receives all $\lvert V \rvert$ extra parameters, so each call passes $\lvert V \rvert$ arguments and the code size of calls grows by $\Theta(m \lvert V \rvert)$ — the reason compilers lift selectively (GHC lifts only when the argument count stays small). Closure conversion with a closure created inside a loop of $n$ iterations allocates $n$ records unless escape analysis proves the closure does not outlive the iteration.

Closure conversion¶

Flat vs linked environments: flat records copy every captured variable (fast access, $O(k)$ creation); linked records point to the parent's environment (cheap creation, access by chains). Appel's safe-for-space conditions favor flat closures [AJ89].
Defunctionalization (Reynolds): replace function values by a tag and one apply function with a switch — first-order code, used by whole-program compilers such as MLton; trade-off: needs the whole program.

Lambda lifting¶

Selective lifting (GHC's -fstg-lift-lams): lift only when it does not increase allocation or argument counts beyond a threshold.
Lambda dropping (Danvy and Schultz): the inverse, re-nesting functions to remove parameters that are always the same [DS02]; useful after inlining.

7. In real compilers¶

Closure conversion¶

OCaml: close_functions in middle_end/closure/closure.ml (OCaml 4.14) builds closures and their environments [OCAML-Closure]. rustc: a closure is a struct of its captures passed as the first argument of its body function (the body is …::{closure#0}). Clang: a C++ lambda is a class built by Sema::BuildLambdaExpr (clang/lib/Sema/SemaLambda.cpp) [CLANG-Lambda].

OCaml's closures in its Clambda intermediate language

Reproduce (ocamlopt 4.14.1):

cat > adder.ml <<'EOF'
let make_adder k = fun x -> x + k
let apply_all k l = List.map (make_adder k) l
EOF
ocamlopt -c -dclambda adder.ml 2>&1 | sed -n '/apply_all\/271/,$p' | head -13

Output:

    (apply_all/271
       (closure 
         (fun camlAdder__apply_all_271 2  k/273[int] l/274
           (apply* camlStdlib__List__map_482 
             (let (arg/342 k/273 funct/344 (field 0 (read_symbol camlAdder)))
               (closure 
                 (fun camlAdder__fun_345 1  arg/343 env/348
                   (let (k/349 (field 2 env/348)) (+ arg/343 k/349))) 
                 arg/342 funct/344))
             l/274)) ))
    (setfield_ptr(root-init) 1 (read_symbol camlAdder) apply_all/271))
  0)

What to notice: the partial application make_adder k escapes (it is passed to List.map), so it becomes a closure record built with k (arg/342); its code camlAdder__fun_345 takes the argument and the environment env/348 and reads k back from (field 2 env) — Algorithm 11.8.2's envp.k. Top-level functions are closed code (fun … 2 k l: an arity-2 function with no environment).

rustc: a closure is a record of captured pointers

Reproduce (rustc 1.94.1):

cat > clo.rs <<'EOF'
#[inline(never)]
fn apply<F: Fn(i64) -> i64>(f: &F, v: i64) -> i64 { f(v) }
#[no_mangle]
pub fn shift_all(k: i64, m: i64, v: i64) -> i64 {
    let add = |x: i64| x.wrapping_add(k).wrapping_mul(m);
    apply(&add, v)
}
EOF
rustc --crate-type=lib -C opt-level=1 --emit=llvm-ir clo.rs -o clo.ll
sed -n '/^define noundef i64 @shift_all/,/call fastcc/p' clo.ll

Output:

define noundef i64 @shift_all(i64 noundef %0, i64 noundef %1, i64 noundef %v) unnamed_addr #1 {
start:
  %add = alloca [16 x i8], align 8
  %m = alloca [8 x i8], align 8
  %k = alloca [8 x i8], align 8
  store i64 %0, ptr %k, align 8
  store i64 %1, ptr %m, align 8
  call void @llvm.lifetime.start.p0(i64 16, ptr nonnull %add)
  store ptr %k, ptr %add, align 8
  %2 = getelementptr inbounds nuw i8, ptr %add, i64 8
  store ptr %m, ptr %2, align 8
; call clo::apply
  %_0 = call fastcc noundef i64 @_ZN3clo5apply17hbd3f482903603213E(ptr noalias noundef readonly align 8 captures(address, read_provenance) dereferenceable(16) %add, i64 noundef %v) #4

What to notice: the closure add is a 16-byte record holding pointers to k and m (capture by reference: k and m had to move to memory, Lesson 11.1); apply receives the record — the environment — and, after inlining the closure's body, loads k and m through it. The code pointer is not stored: Rust closures have a unique type, so the call is static (monomorphization makes apply specific to it).

Lambda lifting¶

javac: LambdaToMethod (src/jdk.compiler/share/classes/com/sun/tools/javac/comp/LambdaToMethod.java) moves each lambda body into a synthetic lambda$… method with the captured variables as leading parameters [JAVAC-Lambda]. Go: directClosureCall in src/cmd/compile/internal/walk/closure.go [GO-Closure].

javac lifts a lambda body into a static method

Reproduce (javac 21.0.10):

mkdir -p j && cat > j/Adder.java <<'EOF'
import java.util.function.IntUnaryOperator;
class Adder {
    static IntUnaryOperator makeAdder(int k) {
        return x -> x + k;
    }
}
EOF
cd j && javac Adder.java 2>/dev/null && javap -p -c Adder 2>/dev/null | sed -n '/makeAdder(int)/,$p' | grep -v '^\s*$'

Output:

  static java.util.function.IntUnaryOperator makeAdder(int);
    Code:
       0: iload_0
       1: invokedynamic #7,  0              // InvokeDynamic #0:applyAsInt:(I)Ljava/util/function/IntUnaryOperator;
       6: areturn
  private static int lambda$makeAdder$0(int, int);
    Code:
       0: iload_1
       1: iload_0
       2: iadd
       3: ireturn
}

What to notice: the lambda body became the closed method lambda$makeAdder$0(int k, int x) — lambda lifting, with the captured k as the first parameter (Algorithm 11.8.4). Because the lambda escapes (it is returned), invokedynamic still builds a small object holding k: lifting the code and closure-converting only the escaping value (§4).

Find where Go does it. In src/cmd/compile/internal/walk/closure.go, which function turns a directly called function literal into a plain call with the captured variables as arguments, and how does it pass a variable captured by reference? (Quiz go-where-direct-closure.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Closure conversion	Any function value, including escaping ones	one allocation per closure creation + indirect calls · escape analysis can stack-allocate	Explicit environments; debuggers show captured fields	Medium (FV, records, calling convention for code pointers)	OCaml, Rust/C++/Swift closures, Scheme, JavaScript engines
Lambda lifting	Only non-escaping local functions (or the code part of escaping ones)	no allocation; more arguments per call	First-order code; argument lists grow	Low–medium (a fixed point over the call graph)	javac lambda bodies, Go direct closure calls, GHC late lifting

Choose closure conversion when functions are first-class and may escape; choose lambda lifting when a local function is only called — or lift the code and convert only the escaping value, as javac does.

9. Assessment¶

Quiz (./course quiz 11): cc-free-vars, cc-env-field (tag closure-conversion); ll-fixpoint, go-where-direct-closure (tag lambda-lifting).
Drill: none: both transformations are determined by free-variable sets, which the quiz asks for on new instances (cc-free-vars, ll-fixpoint); Chapter 5's resolve-scopes drill trains the scope reasoning that computing $\mathrm{FV}$ needs.
Flashcards: tags closure-conversion, lambda-lifting.
Exercises: none: Pebble has no nested functions.

References¶

See the chapter references.

Technique	Compile time	Run-time cost	Justification
Closure conversion	\(O(n + \sum_f \lvert \mathrm{FV}(f) \rvert)\)	allocate a record of \(k + 1\) words per closure creation; one indirect call per application	FV computed once per function; each creation copies \(k\) values
Lambda lifting	\(O(m^2 \lvert V \rvert)\) with the naive fixed point; \(O(n^2)\) with Danvy and Schultz's graph method [DS02]	0 allocation; \(\lvert E_i \rvert\) extra arguments per call	Algorithm 11.8.4: at most \(m \lvert V \rvert\) changes, each scanning \(O(m)\) call edges

Lesson 11.8 — Closure conversion and lambda lifting (overview)¶

1. Problem and motivation¶

Closure conversion¶

Lambda lifting¶

2. Definitions and algorithms¶

3. Worked example¶

Closure conversion¶

Lambda lifting¶

4. Invariants and correctness¶

Closure conversion¶

Lambda lifting¶

5. Complexity¶

6. Variants and refinements¶

Closure conversion¶

Lambda lifting¶

7. In real compilers¶

Closure conversion¶

Lambda lifting¶

8. Comparison¶

9. Assessment¶

References¶