如何对函数进行curried？

Question

我理解currying的概念，并知道如何使用它。这些不是我的问题，而是我很好奇这是如何在比Haskell代码更低的级别上实现的。

例如，当(+) 2 4是curried时，是否会保留指向2的指针，直到传入4为止？甘道夫会弯曲时空吗？这是什么魔法？

Answer 1

简短的回答:是的，在传入4之前，都会维护一个指向2的指针。

答案比必要的长：

从概念上讲，您应该考虑使用lambda演算和术语重写来定义Haskell。假设您有以下定义：

f x y = x + y

在lambda演算中，f的定义如下所示，其中我显式地用括号将lambda主体括起来：

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

如果你不熟悉lambda演算，这基本上就是“一个返回参数x的函数(一个返回(x + y)的参数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的引用)。

关键的一点是，如果我们实现这样的函数，每个函数只有一个参数，但是一些返回函数(以及一些返回函数的返回函数...)。每次我们应用一个函数时，我们都会创建一个新的术语，将第一个参数“硬编码”到函数体中(包括这个函数返回的任何函数体)。这就是你得到currying和闭包的方法。

显然，这不是Haskell直接实现的方式。很久以前，Haskell (或者可能是它的前身之一；我不太清楚历史)是由Graph reduction实现的。这是一种相当于我上面描述的术语缩减的技术，它自动带来懒惰的评估和大量的数据共享。

在图缩减中，一切都是对图中节点的引用。我不会深入讨论太多细节，但是当求值引擎将函数的应用减少为一个值时，它将复制与函数体对应的子图，并对函数参数的参数值进行必要的替换(但在不受替换影响的情况下共享对图形节点的引用)。因此，从本质上讲，部分应用函数会在内存中创建一个新结构，该结构具有对所提供参数的引用(即“指向2的指针”)，并且您的程序可以传递对该结构的引用(甚至可以多次共享和应用该结构)，直到提供了更多的参数并且实际上可以减少它为止。然而，这并不是简单地记住函数并累积参数，直到它获得所有参数；每次应用于新参数时，求值引擎实际上都会做一些工作。事实上，图形缩减引擎甚至不能区分返回函数并仍然需要更多参数的应用程序和刚刚获得最后一个参数的应用程序之间的区别。

关于Haskell的当前实现，我不能告诉您更多。我相信它是图形简化的一个遥远的变异后代，有很多聪明的捷径和更快的条纹。但我可能错了；也许他们已经找到了一种完全不同的执行策略，完全不再像图缩减那样。但我有90%的把握，它最终仍然会传递包含对部分参数的引用的数据结构，而且它可能仍然会做一些等同于部分分解参数的事情，因为它似乎对惰性计算的工作方式非常重要。我也相当肯定它会做很多优化和捷径，所以如果你直接调用一个像f 1 2 3 4 5这样有5个参数的函数，它就不会经历复制f的主体5次的麻烦，而且还会有更多的“硬编码”。

Answer 2

尝试使用GHC：

ghc -C Test.hs

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

我写了以下函数：

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-Machine”。There is a really good paper on it, by Simon Peyton-Jones。如果您对Haskell运行时是如何实现的感到好奇，请先去阅读它。