Misplaced Pages

Latest revision as of 02:56, 2 October 2024

Lambda lifting is a meta-process that restructures a computer program so that functions are defined independently of each other in a global scope. An individual "lift" transforms a local function into a global function. It is a two step process, consisting of;

• Eliminating free variables in the function by adding parameters.
• Moving functions from a restricted scope to broader or global scope.

The term "lambda lifting" was first introduced by Thomas Johnsson around 1982 and was historically considered as a mechanism for implementing functional programming languages. It is used in conjunction with other techniques in some modern compilers.

Lambda lifting is not the same as closure conversion. It requires all call sites to be adjusted (adding extra arguments to calls) and does not introduce a closure for the lifted lambda expression. In contrast, closure conversion does not require call sites to be adjusted but does introduce a closure for the lambda expression mapping free variables to values.

The technique may be used on individual functions, in code refactoring, to make a function usable outside the scope in which it was written. Lambda lifts may also be repeated, in order to transform the program. Repeated lifts may be used to convert a program written in lambda calculus into a set of recursive functions, without lambdas. This demonstrates the equivalence of programs written in lambda calculus and programs written as functions. However it does not demonstrate the soundness of lambda calculus for deduction, as the eta reduction used in lambda lifting is the step that introduces cardinality problems into the lambda calculus, because it removes the value from the variable, without first checking that there is only one value that satisfies the conditions on the variable (see Curry's paradox).

Lambda lifting is expensive on processing time for the compiler. An efficient implementation of lambda lifting is ${\displaystyle O(n^{2})}$ on processing time for the compiler.

In the untyped lambda calculus, where the basic types are functions, lifting may change the result of beta reduction of a lambda expression. The resulting functions will have the same meaning, in a mathematical sense, but are not regarded as the same function in the untyped lambda calculus. See also intensional versus extensional equality.

The reverse operation to lambda lifting is lambda dropping.

Lambda dropping may make the compilation of programs quicker for the compiler, and may also increase the efficiency of the resulting program, by reducing the number of parameters, and reducing the size of stack frames. However it makes a function harder to re-use. A dropped function is tied to its context, and can only be used in a different context if it is first lifted.

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, the closure will need to be represented by a data structure that captures the bindings of the free variables.

Example

The following OCaml program 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 a parameter:

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

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

// Initial version
function sum(n) {
    function f(x) {
        return n + x;
    }
    if (n == 1)
        return 1;
    else
        return f(sum(n - 1));
}
// After converting the free variable n to a formal parameter w
function sum(n) {
    function f(w, x) {
        return w + x;
    }
    if (n == 1)
        return 1;
    else
        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));
}

Lambda lifting versus closures

Lambda lifting and closure are both methods for implementing block structured programs. It implements block structure by eliminating it. All functions are lifted to the global level. Closure conversion provides a "closure" which links the current frame to other frames. Closure conversion takes less compile time.

Recursive functions, and block structured programs, with or without lifting, may be implemented using a stack based implementation, which is simple and efficient. However a stack frame based implementation must be strict (eager). The stack frame based implementation requires that the life of functions be last-in, first-out (LIFO). That is, the most recent function to start its calculation must be the first to end.

Some functional languages (such as Haskell) are implemented using lazy evaluation, which delays calculation until the value is needed. The lazy implementation strategy gives flexibility to the programmer. Lazy evaluation requires delaying the call to a function until a request is made to the value calculated by the function. One implementation is to record a reference to a "frame" of data describing the calculation, in place of the value. Later when the value is required, the frame is used to calculate the value, just in time for when it is needed. The calculated value then replaces the reference.

The "frame" is similar to a stack frame, the difference being that it is not stored on the stack. Lazy evaluation requires that all the data required for the calculation be saved in the frame. If the function is "lifted", then the frame needs only record the function pointer, and the parameters to the function. Some modern languages use garbage collection in place of stack based allocation to manage the life of variables. In a managed, garbage collected environment, a closure records references to the frames from which values may be obtained. In contrast a lifted function has parameters for each value needed in the calculation.

Let expressions and lambda calculus

The Let expression is useful in describing lifting and dropping, and in describing the relationship between recursive equations and lambda expressions. Most functional languages have let expressions. Also, block structured programming languages like ALGOL and Pascal are similar in that they too allow the local definition of a function for use in a restricted scope.

The let expression used here is a fully mutually recursive version of let rec, as implemented in many functional languages.

Let expressions are related to Lambda calculus. Lambda calculus has a simple syntax and semantics, and is good for describing Lambda lifting. It is convenient to describe lambda lifting as a translations from lambda to a let expression, and lambda dropping as the reverse. This is because let expressions allow mutual recursion, which is, in a sense, more lifted than is supported in lambda calculus. Lambda calculus does not support mutual recursion and only one function may be defined at the outermost global scope.

Conversion rules which describe translation without lifting are given in the Let expression article.

The following rules describe the equivalence of lambda and let expressions,

Name	Law
Eta-reduction equivalence	${\displaystyle f\ x=y\equiv f=\lambda x.y}$
Let-Lambda equivalence	${\displaystyle f\notin FV(E)\to (\operatorname {let} f:f=E\operatorname {in} L\equiv (\lambda f.L)\ E)\ {\text{(where }}f{\text{ is a variable name.)}}}$
Let combination	${\displaystyle x\notin FV(E)\to (\operatorname {let} v,\dots ,w,x:E\land F\operatorname {in} L\equiv \operatorname {let} v,\dots ,w:E\operatorname {in} \operatorname {let} x:F\operatorname {in} L)}$

Meta-functions will be given that describe lambda lifting and dropping. A meta-function is a function that takes a program as a parameter. The program is data for the meta-program. The program and the meta program are at different meta-levels.

The following conventions will be used to distinguish program from the meta program,

• Square brackets will be used to represent function application in the meta program.
• Capital letters will be used for variables in the meta program. Lower case letters represent variables in the program.
• ${\displaystyle \equiv }$ will be used for equals in the meta program.
• ${\displaystyle \_}$ represents a dummy variable, or an unknown value.

For simplicity the first rule given that matches will be applied. The rules also assume that the lambda expressions have been pre-processed so that each lambda abstraction has a unique name.

The substitution operator is used extensively. The expression ${\displaystyle L}$ means substitute every occurrence of G in L by S and return the expression. The definition used is extended to cover the substitution of expressions, from the definition given on the Lambda calculus page. The matching of expressions should compare expressions for alpha equivalence (renaming of variables).

Lambda lifting in lambda calculus

Each lambda lift takes a lambda abstraction which is a sub expression of a lambda expression and replaces it by a function call (application) to a function that it creates. The free variables in the sub expression are the parameters to the function call.

Lambda lifts may be used on individual functions, in code refactoring, to make a function usable outside the scope in which it was written. Such lifts may also be repeated, until the expression has no lambda abstractions, in order to transform the program.

Lambda lift

A lift is given a sub-expression within an expression to lift to the top of that expression. The expression may be part of a larger program. This allows control of where the sub-expression is lifted to. The lambda lift operation used to perform a lift within a program is,

${\displaystyle \operatorname {lambda-lift-op} =P]}$

The sub expression may be either a lambda abstraction, or a lambda abstraction applied to a parameter.

Two types of lift are possible.

• Anonymous lift
• Named lift

An anonymous lift has a lift expression which is a lambda abstraction only. It is regarded as defining an anonymous function. A name must be created for the function.

A named lift expression has a lambda abstraction applied to an expression. This lift is regarded as a named definition of a function.

Anonymous lift

An anonymous lift takes a lambda abstraction (called S). For S;

• Create a name for the function that will replace S (called V). Make sure that the name identified by V has not been used.
• Add parameters to V, for all the free variables in S, to create an expression G (see make-call).

The lambda lift is the substitution of the lambda abstraction S for a function application, along with the addition of a definition for the function.

${\displaystyle \operatorname {lambda-lift} \equiv \operatorname {let} V:\operatorname {de-lambda} \operatorname {in} L}$

The new lambda expression has S substituted for G. Note that L means substitution of S for G in L. The function definitions has the function definition G = S added.

In the above rule G is the function application that is substituted for the expression S. It is defined by,

${\displaystyle G=\operatorname {make-call} ]}$