5 ms·
Lambda lifting
- one-more-minute 8y agoThe venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures." 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/msg03277.html 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 You can do some reflection on the returned closure and see that it's exactly equivalent to the closure converted version: struct Lambda{T} <: Function x::T end (l::Lambda)(y) = l.x + y f(x) = Lambda(x) In fact, Julia doesn't even really have functions at all; `f(x) = ...` is just syntax sugar for an (empty) object with a call method! (Or maybe it doesn't have objects, and `struct` is just sugar for a closure; I'm not sure any more.)
- nils-m-holm 8y agoFor those who find Wikipedia a bit long-winded and enjoy LISPy syntax, lambda lifting performs the transformation: ((lambda <vars> <body>) <args>) ==lift==> ((lambda <vars+free> <body>) <args> <free>) where <vars> are the variables (formal arguments) of the lambda function, <body> is its body, which contains some free variables, and <args> is the (actual) arguments in the application of the lambda function. <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) Because new actual arguments have to be passed to the transformed function, each place where the function is called has to be modified. Hence lambda lifting is a global program transformation. The constraint of modifying all applications is trivially fulfilled when a lambda function is applied immediately, as above.
- 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 agoUnfortunate 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.
- barrkel 8y agoNote 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 agoAt 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 agoCan you explain what you mean by transforming a closure to a combinator?
- nils-m-holm 8y agoThis 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 agoStealing 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?
- joeframbach 8y agoEvery "FP 101 for JavaScripters" tutorial on the web starts with this same example: function adder (x) { return function (y) { return x + y; } } Is this somehow a bad thing to do now, and how would I "lift" it? I don't quite understand. 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?
- wtetzner 8y agoLambda lifting is usually just a technique used by compilers.
- tuespetre 8y agoLambda lifting is crucial to writing a LINQ query provider in .NET languages. Most typically it will need to deal with any closure right around where the query is written and used, but if you get into having other objects adding to or modifying the query, those objects (and/or their closures) need to be dealt with as well.