函数柯里化是如何实现的？

Question

我理解什么是柯里化，并且知道如何使用它。这不是我的问题，我只是好奇在比如说 Haskell 代码的低层次是如何实现的。

例如，当 (+) 2 4 被柯里化时，指向 2 的指针是否一直保持到传递 4？甘道夫弯曲了时空吗？这是什么魔法？

- providence

---

显然，具体细节将取决于具体情况、优化等等，但一般来说，你可以创建一个闭包来保存柯里化的值，这些值在不再使用时会被垃圾回收。我相信一个Haskeller可以给你一个更深入的答案。参见：http://en.wikipedia.org/wiki/Closure_(computer_science) - Peter Alexander

Answer 1

简短回答：是的，指针会在传入4之前一直指向2。

---

需要解释的回答：

从概念上讲，你应该把Haskell定义为基于lambda演算和术语重写。假设你有以下定义：

更长而不必要的回答：

从概念上讲，您应该考虑Haskell是基于λ演算和术语重写来定义的。假设您有以下定义：

f x y = x + y

这里是关于f的lambda演算定义，如下所示，其中我已经在lambda主体周围显式地放置了括号：

\x -> (\y -> (x + y))

如果您不熟悉Lambda演算，这基本上表示“一个以参数x为输入并返回（一个以参数y为输入并返回（x + y）的函数）的函数”。在Lambda演算中，当我们将这样的函数应用于某个值时，我们可以通过将该函数的应用替换为该函数主体的副本，并将该值代替函数的参数来进行替换。

因此，表达式f 1 2通过以下重写序列进行评估：

(\x -> (\y -> (x + y))) 1 2
(\y -> (1 + y)) 2                 # substituted 1 for x
(1 + 2)                           # substituted 2 for y
3

因此，您可以看到，如果我们只向f提供了一个参数，我们将停止于\y -> (1 + y)。因此，我们有一个完整的术语，它只是一个将1添加到某些东西的函数，与我们原始的术语完全分开，可能仍然在某个地方使用（用于对f的其他引用）。

关键点是，如果我们实现这样的函数，每个函数只有一个参数，但有些返回函数（以及一些返回函数的函数，以及返回...的函数）。每次应用函数时，我们创建一个新术语，将第一个参数“硬编码”到函数体中（包括该函数返回的任何函数的主体）。这就是如何获得柯里化和闭包。

现在，显然，Haskell并不是直接实现的。曾经，Haskell（或可能是其前身之一；我对历史不太确定）通过Graph reduction实现。这是一种执行等效于我上面描述的术语缩减的技术，自动带来惰性评估和相当数量的数据共享。

在图形缩减中，所有内容都是对图形中节点的引用。我不会详细介绍，但当评估引擎将函数应用于值时，它会复制与函数体相应的子图，必要时用参数值替换函数的参数（但在不受替换影响的情况下共享对图形节点的引用）。因此，部分应用函数实际上创建了一个新的内存结构，其中包含对提供的参数的引用（即“指向2的指针”），您的程序可以传递该结构的引用（甚至共享它并多次应用它），直到提供更多参数并实际缩减为止。但是，它并不像只是记住函数并积累参数直到获取所有参数；每次将其应用于新参数时，评估引擎实际上会执行一些工作。事实上，图形缩减引擎甚至无法区分返回函数并仍需要更多参数的应用和已经获得最后一个参数的应用之间的区别。

我对Haskell的当前实现了解不多。我认为它是图缩减的远亲后代，有很多聪明的捷径和加速条纹。但我可能错了；也许他们已经找到了一种完全不像图缩减的执行策略。但我90%确定它仍然会传递保存对部分参数的引用的数据结构，并且它可能仍然会做类似于部分因子分解的事情，因为这似乎对惰性求值的工作方式非常重要。我也相当确定它会做很多优化和捷径，因此如果您直接调用一个带有5个参数的函数，如f 1 2 3 4 5，它不会通过五次复制f的主体并逐步“硬编码”来增加麻烦。

- Ben

---

谢谢，我总是觉得这些事情背后的数学非常有趣，也非常精妙。 - providence

Answer 2

在GHC上试一下：

ghc -C Test.hs

这将生成C代码在Test.hc中。

我编写了以下函数：

f = (+) 16777217

然后GHC生成了这个：

R1.p[1] = (W_)Hp-4;
*R1.p = (W_)&stg_IND_STATIC_info;
Sp[-2] = (W_)&stg_upd_frame_info;
Sp[-1] = (W_)Hp-4;
R1.w = (W_)&integerzmgmp_GHCziInteger_smallInteger_closure;
Sp[-3] = 0x1000001U;
Sp=Sp-3;
JMP_((W_)&stg_ap_n_fast);

请记住，在Haskell中，部分应用不是不寻常的情况。从技术上讲，没有任何函数的“最后一个参数”。正如您在此处看到的，Haskell正在跳转到stg_ap_n_fast，它将期望在Sp中提供一个参数。stg代表“无脊椎标记G机器”。Simon Peyton-Jones有一篇关于它的非常好的论文。如果您想了解Haskell运行时的实现方式，请先阅读该论文。

- Apocalisp

---

哇，那看起来是一篇不错的论文！感谢提供参考。是否有某种（免费）Haskell论文库？我渴望大学时代，那时我可以访问几乎所有存在的学术论文... - providence