Lambda lifting
A program transformation to remove free variables.
An expression containing a free variable is replaced by a function applied to that variable.
E.g.
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.
