3 ms·

> the formerly free variables, which have now been lifted to the scope of the caller. This risks obscuring the basic reason why the operation is called lambda

by theoh 8y ago

> the formerly free variables, which have now been lifted to the scope of the caller. 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 http://wiki.c2.com/?LambdaLifting

nils-m-holm 8y ago
Unfortunate choice of words. 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.
- theoh 8y ago
  The paper that introduced the term makes this very clear: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4346 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4... "The process of flattening out a program involving local function definitions, possibly with free variables, into a program consisting only of global function definitions, 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.
  - nils-m-holm 8y ago
    Locations of variables do not move, but references to variables do: (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) ...)
    - theoh 8y ago
      You seem to be quite keen on the notion of lambda lifting a function "in place", so maybe you can explain why one would want to do that. 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).
      - nils-m-holm 8y ago
        > You seem to be quite keen on the notion of lambda lifting a function "in place", so maybe you can explain why one would want to do that. 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.

by theoh 8y ago

nils-m-holm 8y ago

Unfortunate choice of words. 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.

theoh 8y ago
The paper that introduced the term makes this very clear: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4346 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.4... "The process of flattening out a program involving local function definitions, possibly with free variables, into a program consisting only of global function definitions, 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.
- nils-m-holm 8y ago
  Locations of variables do not move, but references to variables do: (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) ...)
  - theoh 8y ago
    You seem to be quite keen on the notion of lambda lifting a function "in place", so maybe you can explain why one would want to do that. 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).
    - nils-m-holm 8y ago
      > You seem to be quite keen on the notion of lambda lifting a function "in place", so maybe you can explain why one would want to do that. 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.