Hacker News Reader

Comment by barrkel | Hacker News Reader

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.

View on HN

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.

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.

Can you explain what you mean by transforming a closure to a combinator?

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.

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?

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).

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?

Yes, 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.

Awesome, that makes a lot of sense. Thanks for helping me understand these things better.

Reply on news.ycombinator.com