Loweringtypical

Lambda Lifting

The other way to remove a nested function: turn its free variables into extra parameters and lift it to the top level. No environment, no allocation — and it only works when the function does not escape.

The question

If I can pass captured variables as extra arguments, why does anyone build an environment record?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

Before: a nested function with free variables. After: a top-level function whose parameter list is its original parameters *plus one per free variable*, and call sites rewritten to supply them. Unlike closure conversion, the output contains no record, no closure value and no indirect call — the program is a set of ordinary top-level functions called directly, which is the representation a first-order back end wants and the representation a whole-program optimizer can analyse hardest.

What this phase may assume or do

Lifting preserves observable behavior only if every call site can supply the free variables' current values at the moment of the call. That holds when the function is called directly from a scope where those variables are live, and fails the moment the function *value* is passed somewhere else, returned, or stored, because then the call happens where the variables are not in scope. For a mutable free variable, lifting by value additionally requires that no write through one path must be visible through another — otherwise the parameter and the original become separate variables.

Key points

  • Lambda lifting removes a nested function by turning its free variables into extra parameters and moving it to the top level.
  • The result is a first-order program: no environments, no closure values, no indirect calls, no allocation.
  • It is legal exactly when every call site can supply the free variables, which means the function is called and never used as a value.
  • Deep nesting makes it expensive: intermediate functions acquire parameters they never use, purely to pass them through.
  • Sharing of a mutable captured variable is lost unless a pointer is passed, which needs the same non-escape proof anyway.
  • Real compilers lift where they can and convert where they must; the two are not competing designs but two cases of one decision.
  • The inverse transformation — lambda dropping — is sometimes the right direction, which is why neither is a default.

Parameters instead of a record

Take the same helper that reads n from its enclosing function. Closure conversion builds a record holding n and passes a pointer to it. Lambda lifting does the obvious cheaper thing: add n as a parameter, and make every call pass it.

The result is a first-order program. There are no closures, no environments, no indirect calls and no allocations — just top-level functions with slightly longer parameter lists. Every subsequent phase gets simpler, and a whole-program optimizer gets much better information, because a direct call to a known function is the easiest thing in the world to inline.

This is not a niche technique. It is how compilers for functional languages traditionally removed higher-order structure — Johnsson's lambda lifting, producing *supercombinators*, was the standard route for lazy functional languages, and it is still what a compiler does to a local helper function that never escapes. Most C and C++ compilers effectively do it for static local helpers, and it is a routine step in bytecode compilers that want a flat function table.

Lifting a non-escaping local function
Before
fn outer(n: int) -> int {
    fn helper(x: int) -> int { return x + n }   // n is free
    return helper(1) + helper(2)
}
After
fn helper(n: int, x: int) -> int { return x + n }   // n is now a parameter

fn outer(n: int) -> int {
    return helper(n, 1) + helper(n, 2)
}
Legal only when

Only if every call to helper occurs at a program point where n is in scope and holds the value the original would have read. That is guaranteed when helper is called directly and never used as a value. If n is mutable, lifting it by value is legal only where no call sequence could observe a write made through the other name — otherwise the parameter must be a pointer to n, which reintroduces the aliasing that lifting was avoiding.

Illegal when

If helper is returned, stored in a data structure, or passed to a function that keeps it. Then the call happens somewhere n is not in scope, and there is no call site left that could supply it — this is exactly the case closure conversion exists for. It is also wrong for a recursive nest where the free variable set is not stable: lifting a mutually recursive group requires lifting all of them together with the union of their free variables, or one of them will be called without a value it needs.

The escape condition is the whole story

Lifting works precisely when the function is *called* rather than *passed*. If every use of helper is a direct call, the compiler can find every call site and add the argument at each one. If helper is used as a value — returned, stored in a list, handed to a callback registry — then somewhere in the future there will be a call at a point where n no longer exists, and no amount of argument-passing helps. That is the boundary, and it is the same escape question that decides whether a closure environment can live on the stack.

Note what this makes lambda lifting: not a competitor to closure conversion so much as the specialisation of it for the non-escaping case. A compiler with escape analysis converts the escaping closures and lifts the rest, and the lifted ones are then indistinguishable from ordinary functions.

There is a middle case worth naming. Some compilers lift *and* leave a closure behind — the lifted function is used at direct call sites, and a small wrapper that builds an environment is created only where the function is used as a value. This gets the cheap path where it applies without giving up the feature, at the cost of emitting two versions of the same function.

Where the values have to be available
  1. b0outer entryentry
    n = param
call helper(n, 1)
call helper(n, 2)
    Both calls are inside the scope where n is live: lifting is available.
  2. b1helper (lifted)
    return x + n
    Now an ordinary top-level function. No environment, no indirect call.
  3. b2outer returns helper
    return helper
    The function value escapes. There is no future call site inside outer.
  4. b3caller, much later
    f = outer(5)
f(1)
    This call must supply n = 5 and cannot: n died with outer's frame. Lifting is impossible here.
Edges
  • b0→b1direct call
  • b2→b3value escapes

Read it asThe two paths differ in one property: whether a call site exists inside the scope that owns the free variable. The upper path can pass n as an argument. The lower path cannot, so the value must have been captured into something that outlives the frame — which is [[closure-conversion]]. Deciding which path a given function is on is [[escape-analysis]].

Comparing them honestly

typicalReal compilers do not choose one strategy globally. A typical middle end lifts local functions whose uses are all direct calls, converts the rest, and then relies on inlining to erase the difference at hot call sites. GHC additionally runs a late lambda-lifting pass with a heuristic that declines to lift when the parameter count would grow past the machine's argument registers — the threshold is target-dependent, so the same source can be lifted on one architecture and not another.

Lifting is cheaper at run time and worse at scale. Every free variable becomes a parameter, so a deeply nested function that reaches five levels up gets five extra parameters, and every call site — including the ones inside intermediate functions that do not use those variables — has to thread them through. The classic failure is a nest where an inner function needs a variable from the outermost scope: every function between them acquires a parameter it does not use, purely to pass it along.

That is not merely ugly. It costs registers and stack space at every intermediate call, and it can be worse than one pointer to a shared record. Closure conversion pays one indirection to reach any captured variable regardless of depth; lifting pays argument-passing proportional to depth times call frequency. Which is cheaper genuinely depends on the shape of the program, which is why real compilers do both.

Lifting also loses sharing. If two lifted functions both take n by value and one of them assigns to it, the other never sees the write. Closure conversion with cells preserves the sharing at the cost of the indirection. A language with immutable captured variables — or a compiler operating on SSA, where the question does not arise — can lift freely; one with mutable shared captures cannot lift those variables at all without passing pointers, and passing a pointer to a stack slot is only sound under the same non-escape condition.

Lambda lifting against closure conversiontypical
AxisLambda liftingClosure conversion
Runtime allocationNoneOne environment record per closure creation, unless escape analysis removes it
Call shapeDirect call to a known function — easy to inlineIndirect call through a code pointer, unless the target is known
Access to a captured variableA register or stack argumentOne indirection, or two if the variable is in a shared cell
Cost of deep nestingParameters accumulate through every intermediate functionConstant: one pointer, regardless of depth
Escaping functionsNot possible — there is no call site to supply the argumentsThe case it exists for
Mutable shared variablesLost unless a pointer is passed, which needs the same non-escape proofPreserved by a shared cell
Where it is usedLocal helpers, supercombinator compilation, whole-program compilersAny language where function values escape

Lambda dropping, and why the direction is not obvious

The inverse transformation exists and has a name: lambda dropping, or block sinking — taking a top-level function with a long parameter list and re-nesting it inside its only caller so that the parameters become free variables again. It sounds perverse and it is occasionally exactly right, because a nested function can see its enclosing scope for free while a lifted one must be passed everything on every call.

The existence of the inverse is the honest summary of this lesson. Neither direction is universally better. Lifting is better when the arguments are few and the calls are direct; dropping is better when a function is called in a loop with the same five values, where re-nesting turns five arguments per call into zero. A compiler that only knows one direction is leaving a real amount on the table, and a compiler that applies either aggressively without a cost model will make the program worse in a way that is hard to attribute.

How it works

The steps, in the order the compiler takes them.

  • Compute the free variables of the nested function, including those free in any function nested inside it, transitively.
  • Check that every use of the function is a direct call and not a use as a value; if any use escapes, the function is not liftable.
  • For mutually recursive nests, lift the whole group at once with the union of the group's free variables, or the recursive calls will be missing arguments.
  • Extend the parameter list with one parameter per free variable, rewrite the body to use the parameters, and move the function to the top level with a fresh unambiguous name.
  • Rewrite every call site to pass the current values, threading them through any intermediate function that lies between the definition and the call.
  • Where a lifted function is also used as a value somewhere, emit a small closure wrapper for that use rather than abandoning the lift.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A parameter list grows past the target's argument registers and every call starts spilling to the stack, so a transformation intended to remove an allocation makes the hot path slower.
  • A mutable variable is lifted by value into two functions, and a write in one is invisible in the other — the program computes with a stale value and nothing indicates a variable was duplicated.
  • A stack trace becomes unreadable: functions the author wrote as nested helpers appear as top-level symbols with generated names and unfamiliar arities.
  • A mutually recursive nest is lifted one function at a time, and a recursive call is emitted without a free variable it needs, producing either a compile failure deep in the back end or a garbage read.
  • A profile attributes time to a lifted function that no longer corresponds to any source function, so the hot code cannot be located in the file.
  • A refactor stores a previously-local helper in a map; the lift silently stops applying, an environment allocation appears in the loop, and the regression has no obvious cause in the diff.

When it helps

  • Local helper functions that exist only to name a piece of logic and are called directly — the overwhelmingly common case.
  • Compilation targets with no way to express nesting or closures: WebAssembly before reference types, C as a target language, flat bytecode formats with a function table.
  • Whole-program compilers, where a first-order program with direct calls gives the strongest possible information to inlining and interprocedural analysis.
  • Lazy functional language compilation, where supercombinator conversion was the historical route from a higher-order source to a machine.

When it hurts

  • Deep lexical nesting where a variable from the outermost scope is used innermost, and every function between them gains a pass-through parameter.
  • Functions called very frequently with many free variables, where argument setup on every call exceeds the cost of one environment pointer.
  • Any function used as a value, where the transformation simply does not apply and pretending otherwise produces a miscompile.
  • Languages with mutable shared captures, where lifting by value changes the meaning and lifting by pointer reintroduces the aliasing problem.

What it costs

Every one of these is paid by something.

  • Removing the environment buys the allocation and the indirection, and pays argument-passing cost at every call site — proportional to the number of free variables times the call frequency, which can exceed what it saved.
  • A first-order output buys direct calls that inlining and interprocedural analysis can see through, and pays in parameter pressure: past the target's argument-register count the extra parameters go on the stack.
  • Lifting by value buys register-allocatable parameters and pays the loss of sharing for mutable variables, which is a change in meaning rather than a change in cost.
  • Threading parameters through intermediate functions buys the ability to lift deeply nested helpers and pays in every intermediate signature: functions acquire parameters unrelated to what they do, which shows up in stack traces, profiles and debug information.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Closure conversion, which handles every case including escape at the cost of an allocation and an indirection — see [[closure-conversion]].
  • Inline the nested function into its caller entirely, which removes the question. Best when the function is small and called once, and it is what most optimizers try first.
  • Lambda dropping — re-nest a top-level function inside its caller so its parameters become free variables again. Wins where a function is called repeatedly with the same values.
  • Defunctionalization, which replaces all function values with tagged data and one dispatcher; a whole-program technique that removes indirect calls even for escaping functions.

See it for yourself

The flag, dump or tool that shows you this directly.

  • GHC: -ddump-simpl shows the Core after the simplifier, where lifted functions appear as top-level bindings with extended argument lists; the late lambda-lifting pass is controlled by -fstg-lift-lams and its threshold flags.
  • Any C compiler: write a static helper that uses only its arguments and one enclosing constant, compile with -S, and observe that no closure machinery is generated. Compare with GCC's nested-function extension, which does generate a trampoline.
  • Rust and C++: nm or objdump -t on the object file shows lifted helpers as real symbols with mangled names; a closure that was converted instead shows a generated type in the symbol.
  • Python: nested functions are never lifted — f.__code__.co_freevars on the inner function is non-empty and LOAD_DEREF appears in dis.dis, which is what a compiler that always converts looks like.
  • Compiler Explorer with -O0 versus -O2 on a nested helper: the difference between an emitted function and an inlined body is the third option this lesson competes with.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Lifting is strictly better than closure conversion because it does not allocate." It does not allocate and it cannot handle escaping functions, and its parameter cost can exceed the allocation it saved.
  • "Any nested function can be lifted." Only those whose every use is a direct call. One use as a value anywhere defeats it.
  • "The extra parameters are free because they are in registers." Only while there are registers. Past the target's argument-register count they are stack traffic on every call.
  • "Lifting and inlining are the same thing." Inlining removes the call; lifting keeps the call and removes the nesting. A lifted function is still a function, and often still called from several places.

Misconceptions

The claim, and what is actually true.

Lambda lifting is what closures are.
It is the alternative to building a closure, applicable only when no function value escapes. The two coexist in real compilers and handle different cases.
A lifted function is an inlined function.
Lifting moves the definition and keeps the call. Inlining removes the call and keeps no definition at that site.
Since lifting avoids the heap, a compiler should always prefer it.
Parameter threading through deep nests can cost more than the pointer it replaced, which is why compilers apply a cost model and sometimes apply the inverse transformation.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

If a small helper function inside another function uses one of the outer function's variables, the compiler has two ways to deal with it. It can build a little record of the variables and hand it over — a closure — or it can simply add those variables to the helper's parameter list and move the helper out. The second is cheaper and only works when the helper is always called directly, never handed around as a value.

practical

The practical signal is whether your helper is ever used as a value. If it is only ever called, most compilers will lift it and you will pay nothing; if you store it in a map, pass it to a registry or return it, an environment appears. This is why an innocuous refactor — "let us put these handlers in a lookup table" — can add allocation to a hot path with nothing in the diff that looks like an allocation. When reading a profile or a stack trace, expect lifted helpers to appear under names that do not match the source, with more parameters than you wrote.

advanced

Lifting, conversion, inlining and dropping are four points in one design space, and the right one depends on facts a compiler can only get from analysis: does the function escape, how many free variables does it have, how deeply is it nested, how often is it called, and how many argument registers does the target have. Historically, compilers for functional languages lifted everything into supercombinators because the back ends were first-order; modern ones convert by default and lift selectively late, after inlining has already removed most of the small cases. The late placement matters — lifting early destroys the nesting that tells the inliner which functions belong together, so a pass that looks free can measurably degrade the code by removing information the next pass needed. That is [[phase-ordering]] with a concrete cost attached.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalMainstream optimizers lift local functions with all-direct uses and convert the rest, then rely on inlining to erase most of the remaining difference. This is a convention rather than a specified behaviour, and the threshold at which a compiler declines to lift — usually related to the number of argument registers the target provides — differs between GHC, LLVM-based front ends and bytecode compilers.
targetThe point at which extra parameters stop being free is a calling-convention property: x86-64 System V passes six integer arguments in registers, AArch64 AAPCS passes eight, and Windows x64 passes four. A lift that adds three parameters is nearly free on AArch64 and pushes a five-argument function onto the stack on Windows x64, so the same transformation has different value per target.
implementationStandard C has no nested functions; GCC supports them as an extension and implements an escaping one with an executable trampoline written onto the stack, which interacts badly with non-executable stack protections. Clang declines to support the extension for that reason. A claim about how nested functions are compiled in C is a claim about one compiler and one extension.

If you were asked this in an interview

  • When can a nested function be lifted to the top level, and how do you decide?
  • Give me a program where lambda lifting would be slower than building a closure.
  • What breaks if you lift a mutually recursive group of nested functions one at a time?

Connections

Computer Architectureregisters
OS & Networkingstack-framesstack-vs-heap