haskell - Haskell 中的所有内容是否都存储在 thunk 中，甚至是简单的值？

Question

Haskell 堆中以下值/表达式/函数的 thunk 是什么样的？

val = 5                -- is `val` a pointer to a box containing 5?
add x y = x + y        
result = add 2 val     
main = print $ result

考虑到 Haskell 的惰性评估模式，如果能了解这些在 Haskell 中是如何表示的，那就太好了。

Answer 1

官方回答

这不关你的事。编译器的严格实现细节。

简短的回答

是的。

更长的答案

对于 Haskell 程序本身，答案总是肯定的，但是如果编译器发现它可以摆脱它，出于性能原因，它可以并且将会做不同的事情。

例如，对于 '''add xy = x + y'''，编译器可能会生成与 x 和 y 的 thunk 一起工作的代码，并因此构造一个 thunk。但请考虑以下几点：

foo :: Int -> Int -> Int
foo x y = x * x + y * y

在这里，优化编译器将生成代码，首先从盒子中取出 x 和 y，然后执行所有算术运算，然后将结果存储在盒子中。

高级答案

本文描述了 GHC 如何从一种实现 thunk 的方式切换到另一种更简单、更快捷的方式： http ://research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/

Answer 2

通常，即使是 Haskell 中的原始值（例如 Int 和 Float 类型）也由 thunk 表示。这确实是非严格语义所要求的；考虑以下片段：

bottom :: Int
bottom = div 1 0

仅当检查底部的值时，此定义才会生成 div-by-zero 异常，但如果从未使用过该值则不会。

现在考虑 add 函数：

add :: Int -> Int -> Int
add x y = x+y

一个简单的 add 实现必须强制 x 的 thunk，强制 y 的 thunk，添加值并为结果创建（评估的）thunk。与严格的函数式语言（更不用说命令式语言）相比，这对于算术来说是一个巨大的开销。

然而，像 GHC 这样的优化编译器可以在很大程度上避免这种开销。这是 GHC 如何翻译 add 函数的简化视图：

add :: Int -> Int -> Int
add (I# x) (I# y) = case# (x +# y) of z -> I# z 

在内部，像 Int 这样的基本类型被视为具有单个构造函数的数据类型。Int# 类型是整数的“原始”机器类型，而 +# 是原始类型的原始加法。对原始类型的操作直接在位模式（例如寄存器）上实现——而不是 thunk。然后将装箱和拆箱转换为构造函数应用程序和模式匹配。

这种方法的优点（在这个简单的示例中不可见）是编译器通常能够内联此类定义并删除中间的装箱/拆箱操作，只留下最外面的那些。

Answer 3

It would be absolutely correct to wrap every value in a thunk. But since Haskell is non-strict, compilers can choose when to evaluate thunks/expressions. In particular, compilers can choose to evaluate an expression earlier than strictly necessary, if it results in better code.

Optimizing Haskell compilers (GHC) perform Strictness analysis to figure out, which values will always be computed.

In the beginning, the compiler has to assume, that none of a function's arguments are ever used. Then it goes over the body of the function and tries to find functions applications that 1) are known to be strict in (at least some of) their arguments and 2) always have to be evaluated to compute the function's result.

In your example, we have the function (+) that is strict in both it's arguments. Thus the compiler knows that both x and y are always required to be evaluated at this point. Now it just so happens, that the expression x+y is always necessary to compute the function's result, therefore the compiler can store the information that the function add is strict in both x and y.

The generated code for add* will thus expect integer values as parameters and not thunks. The algorithm becomes much more complicated when recursion is involved (a fixed point problem), but the basic idea remains the same.

Another example:

mkList x y = 
    if x then y : []
         else []

This function will take x in evaluated form (as a boolean) and y as a thunk. The expression x needs to be evaluated in every possible execution path through mkList, thus we can have the caller evaluate it. The expression y, on the other hand, is never used in any function application that is strict in it's arguments. The cons-function : never looks at y it just stores it in a list. Thus y needs to be passed as a thunk in order to satisfy the lazy Haskell semantics.

mkList False undefined -- absolutely legal

*: add is of course polymorphic and the exact type of x and y depends on the instantiation.

Answer 4

简短的回答：是的。

长答案：

val = 5

这必须存储在一个 thunk 中，因为想象一下，如果我们在代码中的任何地方（例如，在我们导入的库或其他东西中）写这个：

val = undefined

如果必须在我们的程序启动时对其进行评估，它会崩溃，对吗？如果我们真的将这个值用于某事，那将是我们想要的，但如果我们不使用它，它不应该能够如此灾难性地影响我们的程序。

对于您的第二个示例，让我对其进行一些更改：

div x y = x / y

这个值也必须存储在一个 thunk 中，因为想象一下这样的代码：

average list =
  if null list
     then 0
     else div (sum list) (length list)

如果div这里是严格的，即使列表为null（又名空）也会被评估，这意味着像这样编写函数是行不通的，因为0当给定空列表时它没有机会返回，即使这就是我们在这种情况下想要的。

您的最后一个示例只是示例 1 的变体，出于同样的原因，它必须是惰性的。

话虽如此，可以强制编译器使某些值变得严格，但这超出了这个问题的范围。

Answer 5

我认为其他人很好地回答了您的问题，但为了完整起见，让我补充一点，GHC 也为您提供了直接使用未装箱值的可能性。这就是Haskell Wiki 所说的：

当您真的非常渴望速度并且想要直接进入“原始位”时。有关使用未装箱类型的一些信息，请参阅 GHC Primitives。

然而，这应该是最后的手段，因为未装箱的类型和原语是不可移植的。幸运的是，通常没有必要使用显式的拆箱类型和原语，因为 GHC 的优化器可以通过内联它知道的操作和拆箱严格的函数参数来为您完成工作。严格和未打包的构造函数字段也有很大帮助。有时 GHC 需要一些帮助来生成正确的代码，因此您可能需要查看 Core 输出以查看您的调整是否真的产生了预期的效果。

使用未装箱类型和原语可以说的一件事是，您知道自己正在编写高效的代码，而不是依赖 GHC 的优化器来做正确的事情，并且受制于 GHC 优化器的变化。这对你来说可能很重要，在这种情况下就去做吧。

如前所述，它是不可移植的，因此您需要一个 GHC 语言扩展。有关他们的文档，请参见此处。