当前位置：文江博客话题详情

函数是如何柯里化的？

发布于 2024-12-15 16:32:01 字数 182 浏览 3 评论 0原文

我了解柯里化的概念是什么，并且知道如何使用它。这些不是我的问题，而是我很好奇这是如何在比 Haskell 代码更低的级别上实际实现的。

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

猫弦 2024-12-22 16:32:02

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

比必要的答案更长：

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

f x y = x + y

f 的定义在 lambda 演算中如下所示，其中我在 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 的其他引用）。

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

显然，这不是 Haskell 直接实现的方式。曾几何时，Haskell（或者可能是它的前身之一；我不太确定历史）是由

在图简化中，一切都是对图中节点的引用。我不会讲太多细节，但是当评估引擎将函数的应用减少为值时，它会复制与函数主体相对应的子图，并进行必要的替换函数参数的参数值（但共享对不受替换影响的图节点的引用）。所以本质上，是的，部分应用函数会在内存中创建一个新结构，该结构具有对所提供参数的引用（即“指向 2 的指针”），并且您的程序可以传递对该结构的引用（甚至共享它并多次应用它），直到提供更多参数并且实际上可以减少它，但这并不像它只是记住函数并累积参数直到评估引擎实际上执行了一些操作；每次将其应用于新的工作时事实上，图形缩减引擎甚至无法区分返回函数且仍需要更多参数的应用程序与刚刚获得最后一个参数的应用程序之间的区别，

我无法告诉您有关当前实现的更多信息。我相信它是图简化的一个遥远的突变体，有很多聪明的捷径和更快的条纹，但我可能是错的；也许他们已经找到了一个完全不同的执行策略。不再像图形简化那样了。但我 90% 确信它最终仍会传递保留对部分参数的引用的数据结构，并且它可能仍然会执行相当于部分分解参数的操作，因为这对于惰性求值似乎非常重要作品。我也相当确定它会做很多优化和捷径，所以如果你直接调用一个有 5 个参数的函数，比如 f 1 2 3 4 5 ，它不会经历所有的麻烦复制 f 的主体 5 次并连续进行更多“硬编码”。

Short answer: yes a pointer is maintained to the 2 until the 4 is passed in.

Longer than necessary answer:

Conceptually, you're supposed to think about Haskell being defined in terms of the lambda calculus and term rewriting. Lets say you have the following definition:

f x y = x + y

This definition for f comes out in lambda calculus as something like the following, where I've explicitly put parentheses around the lambda bodies:

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

If you're not familiar with the lambda calculus, this basically says "a function of an argument x that returns (a function of an argument y that returns (x + y))". In the lambda calculus, when we apply a function like this to some value, we can replace the application of the function by a copy of the body of the function with the value substituted for the function's parameter.

So then the expression f 1 2 is evaluated by the following sequence of rewrites:

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

So you can see here that if we'd only supplied a single argument to f, we would have stopped at \y -> (1 + y). So we've got a whole term that is just a function for adding 1 to something, entirely separate from our original term, which may still be in use somewhere (for other references to f).

The key point is that if we implement functions like this, every function has only one argument but some return functions (and some return functions which return functions which return ...). Every time we apply a function we create a new term that "hard-codes" the first argument into the body of the function (including the bodies of any functions this one returns). This is how you get currying and closures.

Now, that's not how Haskell is directly implemented, obviously. Once upon a time, Haskell (or possibly one of its predecessors; I'm not exactly sure on the history) was implemented by Graph reduction. This is a technique for doing something equivalent to the term reduction I described above, that automatically brings along lazy evaluation and a fair amount of data sharing.

In graph reduction, everything is references to nodes in a graph. I won't go into too much detail, but when the evaluation engine reduces the application of a function to a value, it copies the sub-graph corresponding to the body of the function, with the necessary substitution of the argument value for the function's parameter (but shares references to graph nodes where they are unaffected by the substitution). So essentially, yes partially applying a function creates a new structure in memory that has a reference to the supplied argument (i.e. "a pointer to the 2), and your program can pass around references to that structure (and even share it and apply it multiple times), until more arguments are supplied and it can actually be reduced. However it's not like it's just remembering the function and accumulating arguments until it gets all of them; the evaluation engine actually does some of the work each time it's applied to a new argument. In fact the graph reduction engine can't even tell the difference between an application that returns a function and still needs more arguments, and one that has just got its last argument.

I can't tell you much more about the current implementation of Haskell. I believe it's a distant mutant descendant of graph reduction, with loads of clever short-cuts and go-faster stripes. But I might be wrong about that; maybe they've found a completely different execution strategy that isn't anything at all like graph reduction anymore. But I'm 90% sure it'll still end up passing around data structures that hold on to references to the partial arguments, and it probably still does something equivalent to factoring in the arguments partially, as it seems pretty essential to how lazy evaluation works. I'm also fairly sure it'll do lots of optimisations and short cuts, so if you straightforwardly call a function of 5 arguments like f 1 2 3 4 5 it won't go through all the hassle of copying the body of f 5 times with successively more "hard-coding".

回复收藏 0 原文

莫言歌 2024-12-22 16:32:02

使用 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 代表“Spineless Tagless G-Machine”。 Simon Peyton-Jones 写了一篇非常好的论文< /a>.如果您对 Haskell 运行时的实现方式感到好奇，请先阅读该内容。

Try it out with GHC:

ghc -C Test.hs

This will generate C code in Test.hc

I wrote the following function:

f = (+) 16777217

And GHC generated this:

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);

The thing to remember is that in Haskell, partially applying is not an unusual case. There's technically no "last argument" to any function. As you can see here, Haskell is jumping to stg_ap_n_fast which will expect an argument to be available in Sp.

The stg here stands for "Spineless Tagless G-Machine". There is a really good paper on it, by Simon Peyton-Jones. If you're curious about how the Haskell runtime is implemented, go read that first.

回复收藏 0 原文

~没有更多了~