奇怪的GHCi懒惰的评价

Question

我在ghci中为偶数和奇数定义了两个相互递归的列表,如下所示:

> let evens = 0:map (+1) odds; odds = map (+1) evens

然后我使用了咨询thunk :sp

> :sp evens
evens = _
> :sp odds
odds = _
> take 5 evens
[0,2,4,6,8]
> :sp evens
evens = 0 : 2 : 4 : 6 : 8 : _
:sp odds
odds = _

注意odds虽然evens已经评估了第5个元素,但是如何评估thunk .我可以想到一个直观的解释.odds必须显式调用才能进行评估:

> take 5 odds
[1,3,5,7,9]
>:sp odds
odds = 1 : 3 : 5 : 7 : 9 : _

但是,现在当我这样做时:

> take 10 evens
[0,2,4,6,8,10,12,14,16,18]
> :sp evens
evens = 0 : 2 : 4 : 6 : 8 : 10 : 12 : 14 : 16 : 18 : _
> :sp odds
odds = 1 : 3 : 5 : 7 : 9 : 11 : 13 : 15 : 17 : _

请注意在odds评估时如何评估thunk evens？为什么odds第一次没有评估,第二次评估以及随后的评估？发生了什么？

Answer 1

这与GHC如何编译相互递归绑定有关(并且绑定是否具有显式类型签名存在差异).

让我们编写下面的简单程序,它暴露了同样的问题,但删除了对整数重载或单态限制可能发挥作用的所有怀疑:

module MutRec where

ft = False : map not tf
tf = map not ft

加载到GHCi(我使用7.6.3)产生:

*MutRec> take 5 ft
[False,False,False,False,False]
*MutRec> :sp ft
ft = False : False : False : False : False : _
*MutRec> :sp tf
tf = _

我们来看看这个模块的核心代码

$ ghc -O0 MutRec -fforce-recomp -ddump-simpl -dsuppress-all
[1 of 1] Compiling MutRec           ( MutRec.hs, MutRec.o )

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 28, types: 42, coercions: 0}

Rec {
ft1_rkA
ft1_rkA = : False a_rkC

tf1_rkB
tf1_rkB = map not ft1_rkA

a_rkC
a_rkC = map not tf1_rkB
end Rec }

ds_rkD
ds_rkD = (ft1_rkA, tf1_rkB)

ft
ft = case ds_rkD of _ { (ft2_Xkp, tf2_Xkr) -> ft2_Xkp }

tf
tf = case ds_rkD of _ { (ft2_Xkq, tf2_Xks) -> tf2_Xks }

这解释了一切.相互递归的定义最终在一个Rec块中,直接相互引用.但是GHC正在构建一对ds_rkD并从该对中重新提取组件.这是一个额外的间接.它解释了为什么在ft对GHCi 进行部分评估之后tf,即使在评估之下,仍会显示为顶部.事实上,我们可以验证只做最小的评估就tf足以暴露这个:

*MutRec> take 5 ft
[False,False,False,False,False]
*MutRec> :sp ft
ft = False : False : False : False : False : _
*MutRec> :sp tf
tf = _
Prelude MutRec> seq tf ()
()
Prelude MutRec> :sp tf
tf = True : True : True : True : _

如果再加上明确的类型sigantures到ft和tf或启用优化,元组结构不会发生:

$ ghc -O MutRec -fforce-recomp -ddump-simpl -dsuppress-all
[1 of 1] Compiling MutRec           ( MutRec.hs, MutRec.o )

==================== Tidy Core ====================
Result size of Tidy Core = {terms: 12, types: 11, coercions: 0}

Rec {
ft1
ft1 = map not tf

ft
ft = : False ft1

tf
tf = map not ft
end Rec }

现在GHCi会表现得更自然.

编辑

我查看了GHC来源,试图找出行为差异的原因.这似乎是类型推断如何适用于多态绑定的副作用.

如果绑定是多态的但没有类型签名,那么它的递归用法是单态的.这是GHC也实施的Hindley-Milner的限制.如果您想要多态递归,则需要一个额外的类型签名.

为了在Core语言中忠实地建模,desugarer对每个未注释的递归函数进行单形复制.这种单态版本用于递归调用,通用版本用于外部调用.你甚至可以看到这个小功能,例如rep(这是一个重新实现repeat).脱毒的核心

rep x = x : rep x

是

rep
rep =
  \ (@ a_aeM) ->
    letrec {
      rep_aeJ
      rep_aeJ =
        \ (x_aeH :: a_aeM) -> : @ a_aeM x_aeH (rep_aeJ x_aeH); } in
    rep_aeJ

外部rep是多态的,因此\ (@ a_aeM) ->在开始时是类型抽象.内部rep_aeJ是单态的,用于递归调用.

如果添加显式类型注释 rep

rep :: a -> [a]
rep x = x : rep x

然后递归调用是多态版本,生成的Core变得更简单:

Rec {
rep
rep = \ (@ a_b) (x_aeH :: a_b) -> : @ a_b x_aeH (rep @ a_b x_aeH)
end Rec }

您可以看到类型参数@ a_b在开始时是如何获取的,并rep在每次递归调用中重新应用.

我们看到的用于相互递归绑定的元组结构只是这个原理的概括.您构建了相互递归函数的内部单态版本,然后在元组中将它们一般化,并从元组中提取多态版本.

所有这些都与绑定是否实际上是多态的无关.它们足以让它们递归.我认为GHC的这种行为是完全正确和可行的,特别是因为优化可以解决性能问题.