Lambda lifting

A program transformation to remove free variables.

An expression containing a free variable is replaced by a function applied to that variable.


f x = g 3

where g y = y + x

x is a free variable of g so it is added as an extra argument:

f x = g 3 x

where g y x = y + x

Functions like this with no free variables are known as supercombinators and are traditionally given upper-case names beginning with "$".

This transformation tends to produce many supercombinators of the form f x = g x which can be eliminated by eta reduction and substitution.

Changing the order of the parameters may also allow more optimisations.

References to global (top-level) constants and functions are not transformed to function parameters though they are technically free variables.

A closely related technique is closure conversion.

See also Full laziness.

< Previous Terms Terms Containing lambda lifting Next Terms >
lambda abstraction
lambda expression
closure conversion
free variable
full laziness
fully lazy lambda lifting
Lambda Prolog
lamp-post error