Lambda Lifting

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


EditText of this page (last edited December 18, 2004) or FindPage with title or text search