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.
Nearby terms:
lambda abstraction « lambda-calculus « lambda
expression «
lambda lifting » LambdaMOO » Lambda Prolog »
lamer
|
