4 ms·

Note the important caveat: > If the language has closures as first-class objects that can be passed as arguments or returned from other functions, the closure

Note the important caveat: > 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.

nils-m-holm 8y ago
At least in my implementations, lambda-lifting transforms a closure to a combinator, so it is a means to getting rid of closures. A lambda function without any free variables does not need to carry an environment around. I would be surprised if other LISP implementations would handle this differently.
- wtetzner 8y ago
  Can you explain what you mean by transforming a closure to a combinator?
  - nils-m-holm 8y ago
    This is basically what lambda lifting does. A combinator is a function without any free variables. The transformation ((lambda (x) (F x)) a) ==> ((lambda (x F) (F x)) a F) ^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^ closure, F is free combinator transforms the applied function into a combinator.
- twtw 8y ago
  Stealing JS example from another comment... function adder (x) { return function (y) { return x + y; } } How would your implementation handle this? Something like lambda lift + curry lifted function + partial application in adder1? I don't see how that could work, because the way I think about currying involves creating more closures?
  - nils-m-holm 8y ago
    Yes, currying creates more closures. Please allow me to use more familiar notation: (define (adder x) (lambda (y) (+ x y))) Then (adder 1) ==> (lambda (y) (+ x y) [x=1]) where [x=1] is the environment of the resulting closure, binding x to 1. An application of (adder 1) can then be transformed as follows: ((adder 1) 5) ==> ((lambda (y) (+ x y) [x=1]) 5) ==> ((lambda (y x) (+ x y)) 5 1) The argument x is thus lifted from the closure environment to the scope of the caller. The function (lambda (y x) (+ x y)) is now a combinator, if we are willing to ignore + (my actual implementation would either handle + as a special operator or lift it as well). A combinator does not carry a closure environment. 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 and turns (F 5) either into (F_1 5) or (F_1* 5 1).
    - twtw 8y ago
      Thanks for your response. > 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?
gsg 8y ago
Lambda lifting is an alternative to closure conversion, so it doesn't get rid of closures so much as obviate introducing them at all. 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.

nils-m-holm 8y ago

At least in my implementations, lambda-lifting transforms a closure to a combinator, so it is a means to getting rid of closures. A lambda function without any free variables does not need to carry an environment around. I would be surprised if other LISP implementations would handle this differently.

wtetzner 8y ago
Can you explain what you mean by transforming a closure to a combinator?
- nils-m-holm 8y ago
  This is basically what lambda lifting does. A combinator is a function without any free variables. The transformation ((lambda (x) (F x)) a) ==> ((lambda (x F) (F x)) a F) ^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^ closure, F is free combinator transforms the applied function into a combinator.
twtw 8y ago
Stealing JS example from another comment... function adder (x) { return function (y) { return x + y; } } How would your implementation handle this? Something like lambda lift + curry lifted function + partial application in adder1? I don't see how that could work, because the way I think about currying involves creating more closures?
- nils-m-holm 8y ago
  Yes, currying creates more closures. Please allow me to use more familiar notation: (define (adder x) (lambda (y) (+ x y))) Then (adder 1) ==> (lambda (y) (+ x y) [x=1]) where [x=1] is the environment of the resulting closure, binding x to 1. An application of (adder 1) can then be transformed as follows: ((adder 1) 5) ==> ((lambda (y) (+ x y) [x=1]) 5) ==> ((lambda (y x) (+ x y)) 5 1) The argument x is thus lifted from the closure environment to the scope of the caller. The function (lambda (y x) (+ x y)) is now a combinator, if we are willing to ignore + (my actual implementation would either handle + as a special operator or lift it as well). A combinator does not carry a closure environment. 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 and turns (F 5) either into (F_1 5) or (F_1* 5 1).
  - twtw 8y ago
    Thanks for your response. > 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?

gsg 8y ago

Lambda lifting is an alternative to closure conversion, so it doesn't get rid of closures so much as obviate introducing them at all. 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.