Added to Favorites

Related Searches

Lambda lifting or closure conversion is the process of eliminating free variables from local function definitions from a computer program. The elimination of free variables allows the compiler to hoist local definitions out of their surrounding context into a fixed set of closed global functions (or rewriting rules). This removes the need for implicit scope for executing the program. Many functional programming language implementations use lambda lifting during compilation.## Algorithm

The following algorithm is one way to lambda-lift an arbitrary program in a language which doesn't support closures as first-class objects:## Example

Consider the following OCaml program that computes the sum of the integers from 1 to 100:## External links

The term lambda lifting was first introduced by Thomas Johnsson around 1982.

- Rename the functions so that each function has a unique name.
- Replace each free variable with an additional argument to the enclosing function, and pass that argument to every use of the function.
- Replace every local function definition that has no free variables with an identical global function.
- Repeat steps 2 and 3 until all free variables and local functions are eliminated.

If the language has closures as first-class objects that can be passed as arguments or returned from other functions (closures), the closure will need to be represented by a data structure that captures the bindings of the free variables.

if n = 1 then

1

else

let f x =

n + x in

f (sum (n - 1)) insum 100

(The word `let rec`

declares `sum`

as a function that may call itself.) The function f, which adds sum's argument to the sum of the numbers less than the argument, is a local function. Within the definition of f, n is a free variable. Start by converting the free variable to an argument:

if n = 1 then

1

else

let f w x =

w + x in

f n (sum (n - 1)) insum 100

Next, lift f into a global function:

w + xand sum n =

if n = 1 then

1

else

f n (sum (n - 1)) insum 100

Finally, convert the functions into rewriting rules:

f w x → w + x

sum 1 → 1

sum n → f n (sum (n - 1)) when n ≠ 1

The expression "sum 100" rewrites as:

sum 100 → f 100 (sum 99)

→ 100 + (sum 99)

→ 100 + (f 99 (sum 98))

→ 100 + (99 + (sum 98)

. . .

→ 100 + (99 + (98 + (... + 1 ...)))

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday August 25, 2008 at 20:24:52 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday August 25, 2008 at 20:24:52 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.