Jump to content

User:Thepigdog/Lambda lifting

From Wikipedia, the free encyclopedia

Lambda lifting or closure conversion is the process of eliminating free variables from a lambda expression within a larger lambda expression. The elimination of free variables allows expression to be moved (lifted) out of its local context to become an outer level definition of the expression.

Lambda lifting allows a lambda expression to be converted to a collection of functions defined without lambda expressions. A strict implementation of the functions may be provided using the usual stack based approach used in implementing imperative languages such as C++. However a strict implementation may not be that useful, and it is computationally expensive to do the conversion.

Lambda lifting demonstrates the equivalence of lambda expressions and functions. The eta-redex is the basis for the equivalence of lambda expressions and functions. However it may not be applied directly. Lambda lifting performs the restructuring needed to allow the eta-redex to be applied.

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

The reverse operation is called Lambda dropping.[1]

Lambda Lifting

[edit]

This section describes lambda lifting in detail. Lambda lifting may be used to convert a program written in Lambda Calculus into a functional program, without lambdas. This demonstrates the equivalence of programs written in Lambda Calculus and programs written as functions.[2]

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. The process is similar to refactoring out code and putting it in a function. Lambda Lifts may be repeated until the expression has no lambda abstractions.

The purpose of lambda lifting

[edit]

Lambda lifting converts a program with lambda expressions into a program with function calls only. Function calls may be implemented using a stack based implementation, which is simple and efficient.

However a stack based implementation must be strict. A functional language is normally implemented using a lazy strategy, which delays calculation until the value is needed. The lazy implementation strategy gives flexibility to the programmer.

Also Lamba lifting is expensive on processing time for the compiler.

Lambda lifting gives a direct translation of a Lambda calculus program into a functional program. At first site this would indicate the soundness of Lambda calculus as a deductive system. However this is not the case 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.

Lambda lifting is useful in understanding lambda expressions.

Lamba-Lift transform of a lambda expression to functions

[edit]

This section describes a meta-function called lambda-lift-tran that transforms any lambda expression into a set of functions defined without lambda abstractions. For example,

The algorithm described here regards every abstraction as an anonymous function. This transformation names the anonymous function and lifts. Alternative approaches are possible. A lambda abstractions applied to an expression may be regarded as a local function function definition.

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.
  • will be used for equals in the meta program.

Calling lambda-lift-tran on a lambda expression gives you a functional program in the form,

  • let M in N

where M is a series of function definitions, and N is the expression representing the value returned.

The processing of transforming the lambda expression is a series of lifts. Each lift has,

  1. A sub expression chosen for it by the function candidate-prefix-lambda. The sub expression should be chosen so that it may be converted into an equation with no lambdas.
  2. The lift is performed by a call to the lambda-lift meta function, described in the next section,

Rules for Lambda lifting

[edit]

The lambda-lift meta function performs a single lambda lift, which takes an expression and replaces it with a function call.

The lift is given a sub-expression (called S) to be lifted. For S;

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

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

The new lambda expression has S substituted for G. Note that L[S:=G] 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,

where H is the function name. It must be a new variable, i.e. a name not already used in the lambda expression,

where is a meta function that returns the set of variables used in E.

For example,

gives,

Constructing the call

[edit]

The function call G is constructed by adding parameters for each variable in the free variable set (represented by V), to the function H,

For example,

Eta reductions to remove lambda abstractions in lifted expressions

[edit]

An eta reduction is ,

If you assume that the eta-redex of an expression equals the expression, this can be rearranged as,

The de-lambda meta function applies eta-reductions to remove lambda abstractions. It is defined by,

if E is not a lamba abstraction

For example,

Candidate prefix lambda for lifting

[edit]

The candidate-prefix-lambda is a meta function that returns a lambda abstraction within an expression whose body does not contain any lambda abstractions. The lambda abstraction may have a number of parameters, as they can be removed by the de-lambda meta function defined previously.

The rules are described below,

  • where x is a variable.

Example

[edit]

For example the Y combinator,

Lambda Expression Function From To Variables
1 true
2
3
4
5

The first sub expression to be chosen for lifting is . This transforms the lambda expression into and creates the equation .

The second sub expression to be chosen for lifting is . This transforms the lambda expression into and creates the equation .

And the result is,

Because is a global function, the result could also have been written,

This would be generated if there was a change to make-call so that only free variables that are not global are added as parameters.

Execution

[edit]

Apply function to,

So,

or

The Y-Combinator calls its parameter (function) repeatedly on itself. The value is defined if the function has a fixed point. But the function will never terminate.

Lambda dropping

[edit]

Lambda dropping is making the scope of functions smaller and using the context from the reduced scope to reduce the number of variables. Reducing the number of variables makes functions easier to comprehend.

Lambda dropping also 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 Lambda dropping also 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.

In the Lambda Lifting section, a meta function for first lifting and then converting the resulting lambda expression into recursive equation was described. The Lamda Drop meta function performs the reverse by first converting recursive equations to lambda abstractions, and then dropping the resulting lambda expression, into the smallest scope which covers all references to the lambda abstraction.

Rules used in Lambda dropping

[edit]

A let expression may be converted back into a lambda expression by repeated application of the lambda-param and the lambda-equiv law,

Name Law
lambda-param
lambda-equiv (where f is a variable name).

The result has the lift restructure, but the restructure is within the Lambda Calculus. The lambda-drop-tran applies these rules in the conversion of recursive functions to lambda abstractions and in reducing the scope of the resulting lambda abstraction.

Converting equations to lambda expressions

[edit]

This meta-function lambda-abstract-tran transforms an expression defined using functions with a let expression to a lambda expression. The transformation works when the let condition is structured like a series of functions, but does not work for arbitrary expressions.

The lambda-lift-tran meta function described earlier creates "let" expressions where each function definition has no free variables. lambda-abstract needs functions with no free variables to work correctly.

For example,

lambda-abstract-tran is defined as,

Lambda abstract performs three separate processing steps; pre-process, process, and convert. These steps are described below,

Pre-process - Split into separate lets,

After lambda-preprocess the result for the example is,,

Process - Turn functions into lambdas,

  • - E is not a let expression.

After lambda-process,

Convert - Turn lets into lambdas,

  • - E is not a let expression.

Then after lambda-abstract-tran,

The abstract meta function removes parameters from functions using lambda abstractions. It is defined by,

if K is a variable.

For example,

Abstraction Sinking

[edit]

Lambda-drop-tran converts recursive equations to lambda expression, and then drops the resulting abstractions into the smallest scope necessary to include all references to the abstraction.

sink-tran sinks each abstraction, starting from the innermost,

Sinking is moving a lambda abstraction inwards as far as possible such that it is still outside all references to the variable.

Application - 4 cases.

Abstraction. Use canonical renaming to insure that the variable names are all distinct.

Variable - 2 cases.

For the example above, sinking,

Sinking a second time,

Parameter Dropping

[edit]

Parameter dropping is optimizing a function for its position in the function. Lambda lifting added parameters that were necessary so that a function can be moved out of its context. In dropping, this process is reversed, and extra parameters that contain variables that are free may be removed.

Dropping a parameter is removing an unnecessary parameter from a function, where the actual parameter being passed in is always the same expression. The free variables of the expression must also be free where the function is defined. In this case the parameter that is dropped is replaced by the expression in the body of the function definition. This makes the parameter unnecessary.

For example, consider,

In this example the actual parameter for the formal parameter o is always p. As p is a free variable in the whole expression, the parameter may be dropped. The actual parameter for the formal parameter y is always n. However n is bound in a lambda abstraction. So this parameter may not be dropped.

The result of dropping the parameter is,

For the main example,

The definition of drop-params-tran is,

where,

Build parameter lists

[edit]

For each abstraction that defines a function, build the information required to make decisions on dropping names. This information consists of information about each parameter; the parameter name, the expression for the actual value, and an indication that all the expressions have the same value.

For example in,

the parameters to the function g are,

Formal Parameter All Same Value Actual parameter expression
x false _
o true p
y true n

Each abstraction is renamed with a unique name, and the parameter list is associated with the name of the abstraction. For example, g there is parameter list.

build-param-lists builds all the lists for an expression, by traversing the expression.

Abstraction - A lambda expression of the form is analyzed to extract the names of parameters for the function.

Locate the name and start building the parameter list for the name, filling in the formal parameter names. Also receive any actual parameter list from the body of the expression, and return it as the actual parameter list from this expression

Variable - A call to a function.

For a function name or parameter start populating actual parameter list by outputting the parameter list for this name.

Application - An application (function call) is processed to extract

Retrieve the parameter lists for the expression, and the parameter. Retrieve a parameter record from the parameter list from the expression, and check that the current parameter value matches this parameter. Record the value for the parameter name for use later in checking.

... if N is a variable.
... otherwise.

The above logic is quite subtle in the way that it works. The same value indicator is never set to true. It is only set to false if all the values cannot be matched. The value is retrieved by using S to build a set of the Boolean values allowed for S. If true is a member then all the values for this parameter are equal, and the parameter may be dropped.

The logic for equate is used in this more difficult example,

has the parameter x dropped to become,

function param 1 param 2
Abstract p p x
Application 1 p p f
Application 2 q q x

q in the second call has the value of p. For the second parameter, f and x are the same value.

Drop parameters

[edit]

Abstraction - .

where,

Variable - .

For a function name or parameter start populating actual parameter list by outputting the parameter list for this name.

Application - An application (function call) is processed to extract

Drop formal parameters
[edit]

drop-formal removes formal parameters, based on the contents of the drop lists. Its parameters are,

  • The drop list,
  • The function definition (lambda abstraction).
  • The free variables from the function definition.

drop-formal is defined as,

Which can be explained as,

  1. If all the actual parameters have the same value, and all the free variables of that value are available for definition of the function then drop the parameter, and replace the old parameter with it's value.
  2. else do not drop the parameter.
  3. else return the body of the function.

For example,

Condition Expression
)

Example

[edit]

Starting with the function definition of the Y-combinator,

Transformation Expression
abstract * 4
lambda-abstract-tran
sink-tran
sink-tran
drop-param
beta-redex

Which gives back the Y combinator,

[edit]

References

[edit]
  1. ^ Danvy, O.; Schultz, U. P. (1997). "Lambda-dropping". ACM SIGPLAN Notices. 32 (12): 90. doi:10.1145/258994.259007.
  2. ^ Johnsson, Thomas (1985), "Lambda Lifting: Transforming Programs to Recursive Equations", Conf. on Func. Prog. Languages and Computer Architecture., ACM Press

See also

[edit]
[edit]

Category:Implementation of functional programming languages Category:Lambda calculus