Lambda lifting

Lambda lifting

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. Many functional programming language implementations use lambda lifting during compilation.

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

Contents

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:

  1. Rename the functions so that each function has a unique name.
  2. Replace each free variable with an additional argument to the enclosing function, and pass that argument to every use of the function.
  3. Replace every local function definition that has no free variables with an identical global function.
  4. 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.

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 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 ...)))

The following is the same example, this time written in JavaScript:

// 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
 
function f(w, x) {
        return w + x;
};
 
function sum(n) {
        if(n == 1) {
                return 1;
        }
        else {
                return f( n, sum(n - 1) );
        }
}

See also

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Lifting En Ondelettes — Un lifting en ondelettes est, en mathématiques, un schéma d’implantation d’une transformation en ondelettes un peu différent de celui plus habituel réalisé par les bancs de filtres. Le lifting en ondelettes est l’expression retenue pour désigner… …   Wikipédia en Français

  • Lifting en ondelettes — Un lifting en ondelettes est, en mathématiques, un schéma d’implantation d’une transformation en ondelettes un peu différent de celui plus habituel réalisé par les bancs de filtres. Le lifting en ondelettes est l’expression retenue pour désigner… …   Wikipédia en Français

  • Lambda Phi Epsilon — Infobox Fraternity letters=ΛΦΕ name=Lambda Phi Epsilon colors=Royal Blue and White flower= symbol= motto= To be Leaders Among Men ΗΓΕΜΟΝΕΣ ΕΝ ΑΝΘΡΩΠΟΙΣ ΕΙΝΑΙ crest= founded=birth date and age|1981|2|25 birthplace=UCLA type= Social scope=National… …   Wikipedia

  • Closure (computer science) — In computer science, a closure (also lexical closure, function closure, function value or functional value) is a function together with a referencing environment for the non local variables of that function.[1] A closure allows a function to… …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Free variables and bound variables — In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place. The idea is related to …   Wikipedia

  • Nested function — definitions can be compared to how a Matryoshka doll nests within larger versions of itself, in several levels. In computer programming, a nested function (or nested procedure/subroutine) is a function which is lexically (textually) encapsulated… …   Wikipedia

  • Defunctionalization — In programming languages, defunctionalization refers to a compile time transformation which eliminates higher order functions, replacing them by a single first order apply function. The technique was first described by John C. Reynolds in his… …   Wikipedia

  • Second generation wavelet transform — In signal processing, the second generation wavelet transform (SGWT) is a wavelet transform where the filters (or even the represented wavelets) are not designed explicitly, but the transform consists of the application of the Lifting… …   Wikipedia

  • Sexual orientation and military service —   Homosexuals and bisexuals allowed to serve in the military …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”