What is "Lambda Lifting"?

Question

I just ran into this while going through the Erlang compiler source.

I'm not really getting it. (go figure ;)), considering that I just realized that there is such a thing 5 minutes ago).

Forgive me for asking first without first trying to understand reasons for its existence.

There is a wikipedia article about it, but it is pretty cryptic.

Answer 1

Lambda lifting is used to turn a closure into a pure function. By passing extra arguments to the function, you reduce the number of its free variables. As you "lift" the lambda into higher and higher scopes, you add arguments to accommodate the local variables declared in that scope (which would be free variables otherwise). Once the lambda has no free variables it is a pure "top level" function.

Of course you can only do this if you know all the lambda's call sites; in other words, only if the lambda does not escape.

The benefit in a compiler optimizer is that closures (function environments) can be eliminated. This might make it possible to pass the arguments in registers rather than stack (or heap) allocating them as free variables.

Answer 2

Lambda lifting is a technique to `lift' lambdas to a higher level (mostly to the top level).

Doug Currie describes why you would want to do this.

Here's some example code (in JavaScript) of how you could do this manually:

function addFive(nr)
{
  var x = 5;
  function addX(y)
  {
    return x + y;
  }

  return addX(nr);
}

Now if you don't want this addX function inside the definition of addFive you could `lift' it to the top level like so:

function addX(y)
{
  return x + y;
}

function addFive(nr)
{
  var x = 5;

  return addX(nr);
}

However, this won't work, since the x variable isn't available anymore in the context of the addX function. The way to fix this is to add an extra formal parameter to the function:

function addX(y, x)
{
  return x + y;
}

function addFive(nr)
{
  var x = 5;

  return addX(nr, x);
}

---

Addition: Here's a very contrived example of a lambda `escaping'. Where you won't be able to do the lambda lifting as easily as I've described.

function getAddFiveFunc()
{
  var x = 5;
  function addX(y)
  {
    return x + y;
  }

  return addX;
}

Now if someone calls the getAddFiveFunc function, they will get a function back. This function could be used at all sorts of places, Now, if you do want to lift the addX function, you will have to update all those callsites.

Answer 3

Warning: My answer actually describes captured variables which is different than lambda lifting. Misread the question (need sleep). But I spent a bit of time writing this up so I'm loathe to delete it. Left it up as a community WIKI.

Lambda lifting, often referred to as closures, is a way of seamlessly allowing access of in scope variables from within a nested lambda expression.

It's hard to get into the nitty gritty details of closures without picking a particular language. One of the side effects of lambda lifting, in any langauge, is that it tends to extend the lifetime of a variable from a local, short lived scope, to a much longer lived scope. Usually this occurs in the form of transferring a variable from the stack to the heap within the compiler. This is a very language specific action and therefore produces very different implementations based on the language.

I'll focus on C# since that's probably the language most common to the readers of stack overflow. Lets start with the following code.

public Func<int> GetAFunction() {
  var x = 42;
  Func<int> lambda1 = () => x;
  Func<int> lambda2 = () => 42;
  ...
  return lambda1;
}

In this example we've created 2 lambda expressions. In both cases it's assigned to a delegate instance of type Func. All delegates in .Net require that a real function be backing them somewhere. So under the hood, all lambda expressions/ anonymous functions in C# are translated into a method definition.

Generating a function for lambda2 is pretty straight forward. It's an isolated function that just returns a constant value.

public static int RealLambda2() { 
  return 42;
}

Generating lambda1 is quite a bit harder. A literal definition would look like the following

public static int RealLambda1() {
  return x;
}

This obviously won't compile because x is not accessible. In order to make this work, the C# compiler must lift the variable x into a closure. It can then return a pointer to a function within the closure to satisfy the delegate expression

class Closure1 {
  int x;
  public int RealLambda1() {
    return x;
  }
}

This is a pretty simple example but should hopefully detail the art of lifting. The devil is unfortunately in the details and gets much more complex with the scenario.