Lambda lifting is a program transformation to remove free variables where an expression containing a free variable is replaced by a function applied to that variable. This is useful for the compilation of programs in a
FunctionalProgrammingLanguage because it allows you to transform a functional program with local function definitions into a program consisting only of global function definitions. The reverse transformation is called
LambdaDropping.
An example:
Here is a function
sum that returns the sum of two variables,
x and
y, which are defined outside the function:
(defun sum () (+ x y))
Note that, since neither
x nor
y is a parameter of
sum, each is a
FreeVariable in
sum.
If we apply
LambdaLifting to
sum, we get a slightly different function:
(defun sum (x y) (+ x y))
Now, since
x and
y are parameters of
sum, they are no longer free variables in it.
Of course, all instances of
sum in the original program now need to supply
x and
y as arguments:
(sum)
becomes:
(sum x y)
Lambda lifting is somewhat similar to the
MoveField-refactoring used to transform programs in an
ObjectOrientedProgrammingLanguage.
CategoryRefactoring