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.