什么是“Lambda Lifting”？

Question

我在查看Erlang编译器源代码时遇到了这个问题。

我真的不太明白它（想象一下；）），因为我刚刚5分钟前才意识到有这样一件事情存在。

请原谅我在没有理解其存在原因之前先问一个问题。

关于此事，有一个维基百科文章，但是它相当晦涩难懂。

- deepblue

---

首先阅读有关闭包的内容 -- http://en.wikipedia.org/wiki/Closure_(computer_science) - dirkgently

这可能会有用：http://matt.might.net/articles/closure-conversion/ - ceving

Answer 1

Lambda lifting 用于将闭包转化为纯函数。通过向函数传递额外的参数，您可以减少其自由变量的数量。当您将 lambda 提升到更高的作用域时，您会添加参数以适应在该作用域中声明的局部变量（否则会成为自由变量）。一旦 lambda 没有自由变量，它就是一个纯粹的“顶层”函数。

当然，只有在您知道所有 lambda 的调用点时才能这样做；换句话说，只有当 lambda 不逃逸时才能这样做。

在编译器优化器中的好处是可以消除闭包（函数环境）。这可能使得可以通过寄存器传递参数而不是堆栈（或堆）分配它们作为自由变量。

- Doug Currie

---

闭包中的自由变量是指来自其词法环境（定义范围）的变量。 顶层函数是指（在 Erlang 中）模块函数？ 那么，如果一个未绑定的变量已经在模块级别函数中，它也是自由的吗？ 感谢详细的回答。 - deepblue

你需要知道所有的函数调用点，因为你需要通过添加额外的参数（在我的 JavaScript 示例中是 x）来更新对该函数的所有调用。 - Tom Lokhorst

"Escapes down" 的意思是它被传递到已知函数，并且该函数不允许它向上逃逸。因此，闭包的生命周期小于封闭函数的生命周期，因此可以进行堆栈分配。 - Doug Currie

逃逸意味着闭包的生命周期超出了它被创建的环境。它可以存储在向上逃逸的数据结构中，也可以传递给可能让它逃逸的函数，或者由创建它的函数返回。因此，该环境必须在堆上。 - Doug Currie

Lambda Lifting 的反义词是什么？Functorization？ - MathuSum Mut

Answer 2

Lambda lifting是一种将lambda函数提升到更高层次(主要是顶层)的技术。

Doug Currie解释了为什么会想这样做。

这里有一些示例代码（使用JavaScript），展示如何手动完成此操作：

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

  return addX(nr);
}

现在，如果你不想让函数addX嵌套在addFive的定义中，你可以将其提升到顶层：

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

function addFive(nr)
{
  var x = 5;

  return addX(nr);
}

不过这样是行不通的，因为addX函数的上下文中已经不存在变量x。 修复这个问题的方法是在函数中添加一个额外的形式参数：

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

function addFive(nr)
{
  var x = 5;

  return addX(nr, x);
}

---

补充：这里有一个非常牵强附会的lambda“逃逸”示例，您将无法像我描述的那样轻松进行lambda提取。

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

  return addX;
}

现在，如果有人调用getAddFiveFunc函数，他们将得到一个函数作为返回值。这个函数可以在各种场合下使用。如果您确实想提升addX函数，那么您将不得不更新所有这些调用点。

- Tom Lokhorst

---

非常简单的例子，我现在明白了:)谢谢。 所以自由变量被认为是从闭包的周围词法环境中“拉出来”的变量？啊啊，提升加速的方式是不再为每个闭包携带词法环境。 - deepblue

我刚想问你当闭包从其容器函数返回时会发生什么。所以说，如果我仍然想提升它，我该如何将容器函数的局部变量暴露给闭包的外部调用者（以便将它们作为参数传递）？ - deepblue

如果您的编译器在编译时可以访问完整的程序，它将能够更新所有调用站点。然而，大多数编译器允许单独编译每个模块。在这种情况下，如果 lambda 跨越模块边界，lambda lifting 将不可能实现。 - Tom Lokhorst

明白了。Erlang不跨模块边界提升是有道理的，因为它允许动态重新加载模块而无需重新编译其余部分，并且只要导出函数签名保持不变，其余部分就可以更改。感谢您提供这些好例子。 - deepblue

如果函数与包含其环境的数据结构一起存储，那么 Lambda 提升仍然是可能的。然后每个调用者都必须传递环境。 - MauganRa

Answer 3

警告：我的答案实际上描述的是捕获变量，这与Lambda提升不同。我读错了问题（需要睡觉）。但我花了一些时间编写它，所以不想删除它。将其保留为社区WIKI。

Lambda提升，通常称为闭包，是一种无缝地允许从嵌套的Lambda表达式中访问范围内变量的方法。

在没有选择特定语言的情况下深入细节会很难理解闭包。在任何语言中，Lambda提升的一个副作用是它倾向于将变量的生命周期从本地短暂的范围延长到更长的范围。通常，这是通过编译器将变量从堆栈转移到堆中来实现的。这是一种非常特定于语言的操作，因此基于语言产生非常不同的实现。

我将重点放在C#上，因为这可能是Stack Overflow读者最常见的语言。让我们从以下代码开始。

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

在这个例子中，我们创建了2个lambda表达式。在两种情况下，它都被分配给Func类型的委托实例。在.Net中，所有委托都要求在某处支持它们的真实函数。因此，在C#中，所有lambda表达式/匿名函数都被转换为方法定义。为lambda2生成函数非常简单。它是一个独立的函数，只返回一个常量值。

public static int RealLambda2() { 
  return 42;
}

生成lambda1要困难得多。一个字面上的定义看起来像下面这样。

public static int RealLambda1() {
  return x;
}

这段代码显然无法编译，因为x是不可访问的。为了使其工作，C#编译器必须将变量x提升为闭包。然后它可以返回指向闭包内函数的指针来满足委托表达式。

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

这是一个相当简单的例子，但希望能详细说明提取技巧。不幸的是，魔鬼就在于细节，情景变得更加复杂。

- JaredPar

---

您说的是捕获变量，而不是Lambda抬升。 - leppie

你所写的定义被微软广泛使用。例如，请参见http://msdn.microsoft.com/en-us/magazine/cc163362.aspx。 - Neal Gafter

Answer 4

lambda提升基本上消除了变量并将它们放入纯函数中，简化了执行过程。

- Jweede

---

为什么这会简化执行？抱歉问题有点直接。维基百科文章也提到了同样的事情，即提升的目的是为了加速事情的进行。每一件小事都指引着我走向正确的方向。谢谢。 - deepblue

@deepblue（+4年后），因为没有必要维护承载自由变量值的环境；所有自由变量都被转换为参数，因此我们只需要处理参数，以便评估/执行函数。保持环境长时间存活，即使在创建闭包的范围退出之后，可能是一个复杂的任务，这取决于语言。例如，在Scheme中，这非常复杂。 - Will Ness