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 contexts into a fixed set of top-level functions with an extra parameter replacing each local variable. By eliminating the need for run-time access-links, this may reduce the run-time cost of handling implicit scope
Scope (programming)
In computer programming, scope is an enclosing context where values and expressions are associated. Various programming languages have various types of scopes. The type of scope determines what kind of entities it can contain and how it affects them—or semantics...
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
language implementations use lambda lifting during compilation.
The term lambda lifting was first introduced by Thomas Johnsson around 1982.
Algorithm
The following algorithm is one way to lambda-lift an arbitrary program in a language which doesn't support closures as first-class object
First-class object
In programming language design, a first-class citizen , in the context of a particular programming language, is an entity that can be constructed at run-time, passed as a parameter, returned from a subroutine, or assigned into a variable...
s:
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.
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
s 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.
Example
Consider the following OCaml program that computes the sum of the integers from 1 to 100:
let rec sum n =
if n = 1 then
1
else
let f x =
n + x in
f (sum (n - 1)) in
sum 100
(The 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:
let rec sum n =
if n = 1 then
1
else
let f w x =
w + x in
f n (sum (n - 1)) in
sum 100
Next, lift f into a global function:
let rec f w x =
w + x
and sum n =
if n = 1 then
1
else
f n (sum (n - 1)) in
sum 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 following is the same example, this time written in JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....
:
// Initial version
function sum(n) {
if(n
1) {
return 1;
}
else {
function f(x) {
return n + x;
};
return f( sum(n - 1) );
}
}
// After converting the free variable n to a formal parameter w
function sum(n) {
if(n
1) {
return 1;
}
else {
function f(w, x) {
return w + x;
};
return f( n, sum(n - 1) );
}
}
// After lifting function f into the global scope
