Lambda lifting
en.wikipedia.org
en.wikipedia.org
((lambda <vars> <body>) <args>)
==lift==>
((lambda <vars+free> <body>) <args> <free>)
<Vars+free> is a new argument list also containing the free variables of the function (which are hence no longer free) and <free> denotes the formerly free variables, which have now been lifted to the scope of the caller.
For instance:
((lambda (x y) (F (G x y))) A B)
==lift==>
((lambda (x y F G) (F (G x y))) A B F G)
The constraint of modifying all applications is trivially fulfilled when a lambda function is applied immediately, as above.
This risks obscuring the basic reason why the operation is called lambda lifting, which is that the lambda is "lifted" out of its local scope, to become a global function. I'm not really sure what you meant by that sentence. The free variables have always been in scope at the point where the function is called.
Here's a briefer description: http://wiki.c2.com/?LambdaLifting
However, I do not think that the description of "making a function global" is helpful, either. By lambda lifting, a closure becomes a combinator, a function without any free variables. It does not necessarily make that function "global".
The free variables, OTOH, move from the closure environment to the argument list of the function being lifted. That is, they are indeed "lifted" from the environment of the callee to the environment of the caller (where they may be bound or free).
Yes, that's not what the "lifting" in lambda lifting refers to. I apologize for the ambiguity.
"The process of flattening out a program involving local function de finitions, possibly with free variables, into a program consisting only of global function de finitions, we call lambda lifting"
I can't say I support your attempts to link "lifting" with some kind of motion of free variables. Variables, which were free in the function to be lifted, got their values from some enclosing scope. They still do, it's just that the binding is now explicit rather than lexical. The variables haven't moved, the plumbing has just changed.
(lambda (F)
((lambda (x) (F x)) A))
^--- F in inner scope
of (lambda (x) ...)
(lambda (F)
((lambda (x F*) (F* x)) A F))
^--- F in outer scope
of (lambda (x) ...)From where I'm standing, the lifting is about actually displacing the functions out of their current enclosing scope and into the global scope, possibly just out into an enclosing scope. But if you want to transform an anonymous function and then leave it in situ, that doesn't seem like lifting at all.
Closures explicitly don't come into the calculation, and it obviously only works in an immutable data setting (otherwise it might change the semantics of the code).
Have a look at lots of expanded LISP macros, there are nested lambdas all over the place, most of them applied in situ. Converting those applications as described above avoids the cost of closure creation and all that is left is a function call or, in case of tail application, a jump. It is a rather essential optimization in LISP.
Also: in situ application is useful for illustrating the principle. I have described the more general case somewhere else in this discussion.
Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.
On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/m...
You can see this in action very clearly in Julia's compiler. If you write
f(x) = y -> x + y
struct Lambda{T} <: Function
x::T
end
(l::Lambda)(y) = l.x + y
f(x) = Lambda(x)
> 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.
You might get the idea that the article is talking about getting rid of closures, i.e. an implicit data structure containing the closed over environment that lambdas have access to when called, and turning the captured variables into explicit arguments. But most interesting languages that have lambdas support closures as first class values, so you end up with explicit data carriers throughout even with lambda lifting. You just switch from whatever your existing closure representation was, to data structures containing a function pointer and a closure structure - which is often your existing closure representation already.
I would be surprised if other LISP implementations would handle this differently.
((lambda (x) (F x)) a) ==> ((lambda (x F) (F x)) a F)
^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^
closure, F is free combinator
function adder (x) {
return function (y) {
return x + y;
}
}
Please allow me to use more familiar notation:
(define (adder x) (lambda (y) (+ x y)))
(adder 1) ==> (lambda (y) (+ x y) [x=1])
((adder 1) 5) ==> ((lambda (y) (+ x y) [x=1]) 5)
==> ((lambda (y x) (+ x y)) 5 1)
(lambda (y x) (+ x y))
Of course things are complicated by functions that are not applied immediately, like your example suggests. In this case the compiler has to keep track of all values returned by ADDER and find the corresponding call sites. Once this problem is solved, above transformation works even in this case. When not all call sites can be found (for example in compilation of separate files), it is still possible to create two versions of (ADDER x), one that uses lambda lifting and one that does not.
E.g.:
F = (adder 1) creates F_1 = (lambda (y) (+ x y) [x=1])
and F_1* = (lambda (y x) (+ x y)) ; x=1
> When not all call sites can be found (for example in compilation of separate files), it is still possible to create two versions of (ADDER x), one that uses lambda lifting and one that does not.
I'm starting to suspect we interpreted the original comment ("getting rid of closures") differently. I understood that as completely eliminating all closures from a source program via lambda lifting, such that an implementation needs no alternative method of implementing closures. It sounds like maybe you understood that as getting rid of a specific occurrence of a closure in certain special cases, more like an optimization. Does that sound accurate?
I can imagine several scenarios when it seems like you could have have a closure that could not be eliminated via lambda lifting (like maybe if the identity of the returned function is nondeterministic, or where the closure includes some mutable state called from multiple sites).
Put another way, does your implementation have lambda lifting in addition to a runtime implementation of closures, or instead of one. Can lambda lifting completely obviate the need for passing around an environment in all cases, or just optimize it away in certain cases?
The two transformations are fairly closely related, actually. You can view lambda lifting as closure conversion plus flattening, in the case where the code pointer is unnecessary.
function adder (x) {
return function (y) {
return x + y;
}
}
Pretty much every modern KS library has tons of functions whose definitions look like `const foo = a => b => c => junk(a,b,c)`, and is that really better than just writing a normal foo method like it was 1996?