haskell - 理解 Haskell 中的求值顺序

Question

我试图了解 Haskell 中 where 子句的评估方式。假设我们得到了这个玩具示例，其中 bar、baz 和 bat 是在某处定义的函数:

func x = foo i j k
  where
    foo i j k = i + j + k
    k = bat x
    j = baz k
    i = bar j

线路如何 func x = foo i j k扩张？它的评估结果是否类似于 func x = foo(i(j(k)), j(k), k)或 func x = foo(i, j, k) ?

Answer 1

介绍

我假设您打算编写此代码:

func :: Int -> Int
func x = foo
  where
    foo = i + j + k
    k = bat x
    j = baz k
    i = bar j

这样，它将键入 check 和您在 where 中定义的所有三个函数。条款最终会被调用。如果这不是您的意思，请继续阅读，因为我不仅会向您描述代码评估的方式，还会提供您自己确定答案的方法。这可能是一个有点长的故事，但我希望它值得你花时间。

核

代码的评估绝对取决于您选择的编译器，但我想您将使用 GHC，如果是这样，它会多次转换您的代码，然后将其简化为机器代码。

首先，“ where 条款”将替换为“ let 条款”。这样做是为了将 Haskell 语法简化为更简单的 Core 语法。 Core 与称为 lambda 演算的数学理论非常相似，因为它的最终评估是根据这个坚实的基础进行的。此时你的代码看起来有点像这样:

func = λx ->
      let { k = bat x } in
      let { j = baz k } in
      +
        (+ (bar j) j)
        k

如您所见，来自 where 的函数定义之一你的 Haskell 代码的子句在它到达 Core 阶段时完全消失了(实际上，它被内联了)，其他的被重写为 let符号。二元运算 (+) 被重写为波兰符号以使其明确(现在很清楚应该首先计算 i + j)。所有这些转换都是在不改变代码含义的情况下执行的。

图机

然后，生成的 lambda 表达式将简化为有向图并由 Spineless Tagless Graph 机器执行。从某种意义上说，Core 到 STG 机器就像汇编器之于图灵机，虽然前者是一个 lambda 表达式，而后者是一个命令式指令序列。 (正如您现在可能看到的，函数式语言和命令式语言之间的区别相当深。)STG 机器将通过严格定义的操作语义将您提供的表达式转换为可在传统计算机上执行的命令式指令——即也就是说，对于 Core 的每个句法特征(其中只有大约 4 个)，都有一条命令式汇编指令执行相同的操作，并且一个 Core 程序将被转换为这些部分的组合。

Core 操作语义的关键特征是它的惰性。众所周知，Haskell 是一种惰性语言。这意味着要计算的函数和该函数的值看起来相同:作为 RAM 中的字节序列。当程序开始时，一切都被布置为函数(准确地说是闭包)，但是一旦计算出函数的返回值，它将被放置在闭包的位置，以便对内存中该位置的所有进一步访问都将立即接收值。换句话说，一个值只在需要时计算，而且只计算一次。

正如我所说，Core 中的表达式将变成相互依赖的计算的有向图。例如:



如果你仔细观察，我希望这张图能让你想起我们开始的程序。请注意关于它的两个细节:

所有的箭头最终都指向 x ，这与我们提供 x 的想法是一致的。足以评价func .

有时两个箭头指向同一个盒子。这意味着这个盒子的值(value)将被评估一次，第二次我们将免费获得值(value)。

因此，STG 机器将采用一些核心代码并创建一个可执行文件，该可执行文件计算与图片中的图形或多或少相似的图形的值。

执行

现在，当我们制作图形时，很容易看到计算将这样进行:

如 func被调用，x的值收到并放入相应的盒子中。

bat x被计算并放入一个盒子中。

k设置为与 bat x 相同. (这一步可能会被 GHC 在代码上运行的一些优化删除，但实际上 let 子句要求单独存储其值。)

baz k被计算并放入一个盒子中。

j设置为与 baz k 相同，与 k 相同在第 6 步中。bar j被计算并放入一个盒子中。

与第 3 步和第 5 步的预期相反，i未设置任何内容。正如我们在程序的 Core 列表中看到的那样，它被优化掉了。

+ (bar j) j被计算。 j已经计算，所以 baz k这次不会被调用，感谢懒惰。

计算最高值。同样，无需计算 bat x这一次，因为它是先前计算的并存储在正确的框中。

现在，func x 的值本身就是一个盒子，随时可供调用者使用任意次数。

我要强调的是，这就是您执行程序时将要发生的事情，而不是编译它。

结语

据我所知，这就是故事。如需进一步说明，请读者参阅 Simon Peyton Jones 的作品: the book on the design of Haskell和 the article on the design of Graph machine ，一起描述 GHC 的所有内部工作到最小的特性。

要查看 GHC 生成的 Core，只需传递标志 -ddump-simpl当你编译一些东西时。一开始它会伤害你的眼睛，但习惯了。

享受!

后记

正如@DanielWagner 在评论中指出的那样，Haskell 的懒惰会产生一些进一步的后果，如果我们剖析一个不那么做作的案例，我们应该需要考虑这些后果。具体来说:计算可能不需要评估它指向的某些框，甚至根本不需要评估这些框中的任何一个。在这种情况下，这些框将保持不变和未评估，而计算完成并交付其结果实际上与从属框无关。此类函数的示例: f x = 3 .这会产生深远的影响:比如说，如果 x不可能像在“无限循环”中那样计算不使用 x 的函数首先根本不会进入那个循环。因此，有时需要详细了解哪些子计算必须从给定的计算中启动，哪些可能不会。这种错综复杂的情况比我准备在此答案中描述的要远一些，因此在此警告说明中我将结束。