3 ms·
Stealing JS example from another comment... function adder (x) { return function (y) { return x + y; } } How would your implementa
by 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 agoYes, 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 agoThanks 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?
- nils-m-holm 8y agoYes, I view lambda lifting as an optimization and my implementations provide both, closures and combinators. I guess that a global program transformation could eliminate all closures from a purely functional program, but I'm not attempting to do this -- mostly because lambda lifting cannot be applied to many closures that mutate free variables. For instance, the lambda functions created in the expansion of Scheme's LETREC cannot be lambda-lifted.
- twtw 8y agoAwesome, that makes a lot of sense. Thanks for helping me understand these things better.