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中的表示方式.

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如何从实现thunks的一种方式切换到另一种实际上既简单又快速的方式:http: //research.microsoft.com/en-us/um/people/simonpj/papers/eval-apply/

Answer 2

通常,Haskell中的原始值(例如Int和Float类型)甚至由thunk表示.这确实是非严格语义所要求的; 考虑以下片段:

bottom :: Int
bottom = div 1 0

只有在检查bottom的值时,此定义才会生成div-by-zero异常,但如果从未使用过该值,则不会生成div-by-zero异常.

现在考虑添加功能:

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

add的朴素实现必须强制thunk为x,强制thunk为y,添加值并为结果创建(评估)thunk.与严格的函数语言(更不用说命令式语言)相比,这是算术的巨大开销.

但是,GHC等优化编译器可以避免这种开销; 这是GHC如何翻译添加功能的简化视图:

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

在内部,像Int这样的基本类型被视为具有单个构造函数的数据类型.Int#类型是整数的"原始"机器类型,+#是原始类型的原始添加.原始类型的操作直接在位模式(例如寄存器)上实现 - 而不是thunks.然后将装箱和拆箱翻译为构造函数应用程序和模式匹配.

这种方法的优点(在这个简单的例子中不可见)是编译器通常能够内联这样的定义并删除中间装箱/拆箱操作,只留下最外层的操作.

Answer 3

将每个值包装在thunk中是绝对正确的.但由于Haskell不严格,编译器可以选择何时评估thunk /表达式.特别是,如果表达式产生更好的代码,编译器可以选择比严格必要的更早地评估表达式.

优化Haskell编译器(GHC)执行严格性分析以确定将始终计算哪些值.

在开始时,编译器必须假定,没有使用任何函数的参数.然后它会在函数体,并试图发现1)被称为是(至少部分)他们的论据严谨和2)总是要进行评估,以计算函数的结果功能的应用.

在您的示例中,我们(+)在其两个参数中都具有严格的函数.因此编译器知道这两个x和y总是需要在这一点上进行评估.现在,它只是恰巧,该表达式x+y总是需要计算函数的结果,因此编译器可以存储信息的功能,add在两个严格x和y.

因此,为add*生成的代码将期望整数值作为参数而不是thunks.当涉及递归时(固定点问题),算法变得复杂得多,但基本思想保持不变.

另一个例子:

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

此函数将采用x评估形式(作为布尔值)和ythunk.表达式x需要在每个可能的执行路径中进行评估mkList,因此我们可以让调用者对其进行评估.y另一方面,表达式从未在任何对其参数严格的函数应用程序中使用.cons-function :从不看y它只是将它存储在列表中.因此y需要作为thunk传递以满足惰性Haskell语义.

mkList False undefined -- absolutely legal

*:add当然是多态的,确切的类型x和y取决于实例化.

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的变体,出于同样的原因,它必须是惰性的.

所有这些都说,有可能强制编译器使某些值严格,但这超出了这个问题的范围.