23

我正在为超级组合器是什么而苦苦挣扎:

超级组合子要么是一个常数,要么是一个仅包含超级组合子作为子表达式的组合子。

还有什么是常量应用形式

任何不是 lambda 抽象的超级组合器。这包括真正的常量表达式,例如 12、((+) 1 2)、[1,2,3] 以及部分应用的函数,例如 ((+) 4)。请注意,最后一个示例在 eta 抽象下等效于 \x -> (+) 4 x,后者不是 CAF。

这对我来说没有任何意义!不((+) 4)就像 12 一样“真正恒定”吗?在我简单的头脑中,CAF 听起来像是价值观。

4

2 回答 2

31

您引用的这些 Haskell wiki 页面很旧,我认为不幸的是。特别不幸的是,它们混淆了 CAF 和超级组合子。超级组合子很有趣,但与 GHC 无关。CAF 仍然是 GHC 的重要组成部分,无需参考超级组合子即可理解。


所以让我们从超级组合器开始。组合器派生自组合逻辑,并且在此处的使用中,由仅将传入的值以一种或另一种形式相互应用的函数组成——即它们组合它们的参数。最著名的组合子集是S、K 和 I,它们合在一起是图灵完备的。在这种情况下,超级组合器是仅由传入的值、组合器和其他超级组合器构建的函数。因此,任何超级组合子都可以通过替换扩展为普通的旧组合子。

一些函数式语言的编译器(不是 GHC!)使用组合子和超级组合子作为编译的中间步骤。与任何类似的编译器技术一样,这样做的原因是允许使用这种简化的最小语言更容易执行优化分析。Edwin Brady 的史诗就是这样一种基于超级组合器的核心语言。


常量应用形式完全是另外一回事。它们有点微妙,并且有一些陷阱。将它们视为编译器实现的一个方面,没有单独的语义含义,但对运行时性能具有潜在的深远影响。以下可能不是对 CAF 的完美描述,但它会尝试传达我对 CAF 是什么的直觉,因为我还没有在其他任何地方看到一个非常好的描述供我参考。GHC Commentary Wiki中干净的“权威”描述如下:

常量应用形式,或简称 CAF,是在程序中定义的顶级值。本质上,它们是不是在运行时动态分配的对象,而是程序静态数据的一部分。

这是一个好的开始。纯粹的、函数式的、惰性的语言在某种意义上可以被认为是一种图形缩减机器。第一次要求节点的值时,会强制对其进行评估,这反过来又会要求子节点的值等。一个节点被评估,结果值会一直存在(尽管它不必一直存在——因为这是一种纯语言,所以我们可以始终保持子节点处于活动状态并在没有语义影响的情况下重新计算)。CAF 确实只是一个值。但是,在上下文中,一种特殊的值——编译器可以确定的值完全取决于它的子节点。也就是说:

foo x = ...
  where thisIsACaf = [1..10::Int]

        thisIsNotACaf = [1..x::Int]
        thisIsAlsoNotACaf :: Num a => [a]
        thisIsAlsoNotACaf = [1..10] -- oops, polymorphic! the "num" dictionary is implicitly a parameter.

        thisCouldBeACaf = const [1..10::Int] x -- requires a sufficiently smart compiler
        thisAlsoCouldBeACaf _ = [1..10::Int] -- also requires a sufficiently smart compiler

那么我们为什么要关心事物是否是 CAF 呢?基本上是因为有时我们真的不想重新计算某些东西(例如,一个 memotable!),所以想确保它被正确共享。其他时候我们真的想要重新计算一些东西(例如一个巨大的、很容易生成的列表——比如我们刚刚走过的自然列表),而不是让它永远留在内存中。命名事物并在 let 下绑定它们或将它们写入内联等的组合通常可以让我们以自然、直观的方式指定这些事物。然而,有时编译器比我们预期的更聪明或更笨,我们认为应该只计算一次的东西总是被重新计算,或者我们不想挂在上面的东西被作为 CAF 取出。然后,我们需要更仔细地考虑问题。请参阅此讨论以了解所涉及的一些技巧:避免“共享”的好方法?

[顺便说一句,我觉得不合适,但是任何想要的人都应该随意接受这个答案,因为他们想尝试将它与现有的 Haskell Wiki 页面集成并改进/更新它们]

于 2011-11-30T18:13:48.267 回答
3

马特是对的,因为定义令人困惑。甚至是矛盾的。CAF 定义为:

任何不是 lambda 抽象的超级组合器。这包括真正的常量表达式,例如12, ((+) 1 2)[1,2,3]以及部分应用的函数,例如((+) 4).

因此,((+) 4)被视为 CAF。但在接下来的句子中,我们被告知它等同于不是 CAF 的东西:

最后一个示例在 eta 抽象下等效于\ x -> (+) 4 x不是 CAF。

排除部分应用的函数会更清晰,因为它们等同于 lambda 抽象。

于 2011-12-01T10:14:59.780 回答