haskell 为什么一个带有严格字段的数据结构不能立即被WHNF评估?

mwg9r5ms  于 2023-03-08  发布在  其他
关注(0)|答案(2)|浏览(153)

我一直在学习strict vs lazy数据结构,也一直在玩ghci中的:sprint命令,我对:sprint的理解是它显示了所选变量的求值状态,我遇到了下面这个我无法理解的好奇。

ghci> data Foo = Foo{i::Int,j::String}
ghci> data Bar = Bar{i:: !Int, j::String}
ghci> 
ghci> 
ghci> a = Foo (3+2) "abc"
ghci> b = Bar (3+2) "abc"
ghci> 
ghci> :sprint a
a = <Foo> _ _
ghci> :sprint b
b = _

我的问题是:为什么a在默认情况下被计算为WHNF,而b仍然是thunk?
我希望b的输出是b = <Bar> 5 _,我可以通过运行seq b ()来强制输出。

ghci> seq a ()
()
ghci> seq b ()
()
ghci> :sprint a
a = <Foo> _ _
ghci> :sprint b
b = <Bar> 5 _
txu3uszq

txu3uszq1#

我相信这是因为strict字段只是语法上的糖衣,告诉编译器在某些地方自动插入对seq的调用。
所以Bar上的strictness注解意味着b = Bar (3+2) "abc"实际上编译为类似b = let x = 3+2 in seq x (Bar x "abc")的东西。
a = Foo (3+2) "abc"之后,a是对构造函数Foo的应用的引用;构造函数被特殊处理,因此GHCi的:sprint可以识别出a引用了构造函数应用程序,并将其显示为a = <Foo> _ _
但是在b = Bar (3+2) "abc"之后,b是对seq的应用程序的引用,而不是直接对构造函数Bar的应用程序的引用。seq只是一个函数;它的特殊之处在于它的实现方式,而不是像构造函数那样在内存中被特殊地表示。对(非构造函数)函数应用程序的引用只是一个thunk,所以GHCi将它显示为任何其他thunk:b = _.

  • 强制 * b引用的thunk将强制3 + 2,然后导致对Bar构造函数的应用程序的引用。但是绑定变量不会自动强制赋给它的表达式。
yyyllmsg

yyyllmsg2#

在GHC(或GHCi)中,表达式Foo (3+2) "abc"不产生thunk,而是执行优化以直接产生Foo堆对象,其字段指向thunk:

|------------------------|
| Foo                    |
|------------------------|
| pointer to thunk (3+2) |
|------------------------|
| pointer to thunk "abc" |
|------------------------|

不生成thunk的原因是这将是浪费时间。无论是否创建thunk,语义都是相同的,并且直接创建对象并不比创建thunk更昂贵,所以无论是否强制对象使用WHNF都是一种胜利。(好吧,从技术上讲,它可能会稍微贵一点,但在实际代码中,大多数对象最终都会被使用,避免这些中间thunk是一个巨大的胜利。)
现在,你可能认为表达式Bar (3+2) "abc"应该有同样的行为,但这里有个问题:首先,GHC不能直接创建heap对象,并将strict字段强制为WHNF,就像你假设的那样:

|------------------------|
| Bar                    |
|------------------------|
| 5                      |
|------------------------|
| pointer to thunk "abc" |
|------------------------|

因为那样会改变语义。
具体来说,下面的代码不应该是bottom:

test = let f = Foo undefined undefined
           b = Bar undefined undefined
       in ()

main = print test

虽然b的第一个字段是strict,但是b本身并没有被强制为WHNF,所以它的strict字段还不需要求值,如果GHC直接用WHNF中的strict字段创建Bar对象,那么它需要创建一个对象:

|----------------------------|
| Bar                        |
|----------------------------|
| BOTTOM                     |
|----------------------------|
| pointer to thunk undefined |
|----------------------------|

并且在对象创建过程中会遇到bottom。(一般情况下,“bottom”可能是一个无限循环,所以GHC不可能构建这个对象并在第一个字段中放置一个特殊的“bottom”值--在对象创建之前,求值本身会以一种不可预知的方式中断。)现在,您可能 * 还 * 认为GHC可以构造一个部分求值的对象:

|----------------------------|
| Bar                        |
|----------------------------|
| pointer to thunk undefined |
|----------------------------|
| pointer to thunk undefined |
|----------------------------|

“注意”下一次这个对象实际上被强制为WHNF时,第一个字段--严格的--也将被强制为WHNF。不幸的是,GHC运行时不能支持这一点。GHC强制对象为WHNF的方法是通过检查对象的头部来查看它是否是构造函数。如果它不是构造函数,则需要进一步求值;如果它是一个构造函数(比如这里的Bar),它已经在WHNF中了。因此,这个部分求值的对象将破坏GHC的区间,因为它“看起来”已经被强制为WHNF,即使它的strict字段还没有被强制。
由于这个原因,GHC不能执行与Foo相同的优化,表达式Bar (3+2) "abc"必须保留为thunk:

|----------------------------------|
| pointer to thunk Bar (3+2) "abc" |
|----------------------------------|

当它被强制为WHNF时,这将触发第一个字段被强制为WHNF,并且结果对象将被放置在堆中,替换以下thunk:

|------------------------|
| Bar                    |
|------------------------|
| 5                      |
|------------------------|
| pointer to thunk "abc" |
|------------------------|

相关问题