我理解什么是柯里化,并且知道如何使用它。这不是我的问题,我只是好奇在比如说 Haskell 代码的低层次是如何实现的。
例如,当 (+) 2 4
被柯里化时,指向 2
的指针是否一直保持到传递 4
?甘道夫弯曲了时空吗?这是什么魔法?
我理解什么是柯里化,并且知道如何使用它。这不是我的问题,我只是好奇在比如说 Haskell 代码的低层次是如何实现的。
例如,当 (+) 2 4
被柯里化时,指向 2
的指针是否一直保持到传递 4
?甘道夫弯曲了时空吗?这是什么魔法?
简短回答:是的,指针会在传入4
之前一直指向2
。
需要解释的回答:
从概念上讲,你应该把Haskell定义为基于lambda演算和术语重写。假设你有以下定义:
更长而不必要的回答:
从概念上讲,您应该考虑Haskell是基于λ演算和术语重写来定义的。假设您有以下定义:
f x y = x + y
f
的lambda演算定义,如下所示,其中我已经在lambda主体周围显式地放置了括号:\x -> (\y -> (x + y))
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
的其他引用)。2
的指针”),您的程序可以传递该结构的引用(甚至共享它并多次应用它),直到提供更多参数并实际缩减为止。但是,它并不像只是记住函数并积累参数直到获取所有参数;每次将其应用于新参数时,评估引擎实际上会执行一些工作。事实上,图形缩减引擎甚至无法区分返回函数并仍需要更多参数的应用和已经获得最后一个参数的应用之间的区别。f 1 2 3 4 5
,它不会通过五次复制f的主体并逐步“硬编码”来增加麻烦。在GHC上试一下:
ghc -C Test.hs
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);
stg_ap_n_fast
,它将期望在Sp
中提供一个参数。stg
代表“无脊椎标记G机器”。Simon Peyton-Jones有一篇关于它的非常好的论文。如果您想了解Haskell运行时的实现方式,请先阅读该论文。