haskell 共享无点函数,但计算两次

3bygqnnd  于 2022-11-14  发布在  其他
关注(0)|答案(1)|浏览(150)

我一直试图理解共享计算在Haskell中是如何工作的。根据我的理解,无点共享计算应该只计算一次(由CSE提供)。
(A)例如,请考虑以下代码及其输出:

*Main> let foo = trace "eval foo" 5 in foo + foo
eval foo
10

*Main> let foo' = \x -> trace "eval foo'" x in (foo' 5) + (foo' 5)
eval foo'
eval foo'
10

正如预期的那样,foo只被计算一次(CSE可能会起作用),而foo'被惰性地计算两次。这很好。我使用GHCi 7.6.3版尝试了上面的代码。接下来,我在GHCi 8.6.5版中尝试了相同的代码,得到了以下结果:

*Main> let foo = trace "eval foo" 5 in foo + foo
eval foo
eval foo
10

请注意,foo现在计算了两次。
(B)同样,对于GHCi 7.6.3版:

*Main> let goo = const (trace "eval goo" 5) in goo () + goo ()
eval goo
10

但是,GHCi版本8.6.5对goo求值两次:

*Main> let goo = const (trace "eval goo" 5) in goo () + goo ()
eval goo
eval goo
10

(C)最后,两个版本对以下项产生相同的结果:

*Main> let foo_wrapper x = let foo = trace "eval foo" x in foo + foo
*Main> foo_wrapper 5
eval foo
10

我想知道在GHCi-8中是否默认关闭了一些优化,或者trace的副作用是否强制foo被计算两次?或者GHCi-7中是否存在问题?GHCi应该如何处理像(A)和(B)这样的表达式?

(更新1)

对于场景(C),考虑GHCi-8中的以下运行(主要差异在于trace的第二个参数):

*Main> let foo_wrapper x = let foo = trace "eval foo" x in foo + foo 
*Main> foo_wrapper 5
eval foo
10
*Main> :t (foo_wrapper 5)
(foo_wrapper 5) :: Num a => a

*Main> let foo_wrapper' x = let foo = trace "eval foo" 5 in foo + foo 
*Main> foo_wrapper' ()
eval foo
eval foo
10
*Main> :t (foo_wrapper' ())
(foo_wrapper' ()) :: Num a => a
7y4bm7vi

7y4bm7vi1#

正如预期的那样,foo只计算一次(CSE可能会启动)
不,这与CSE无关,这只是惰性求值(aka call by need)的工作方式:foo是一个constant applicative form,因此它只需要计算一次(从thunk强制到WHNF),然后就可以简单地重用,而不需要任何进一步的计算。这在GHCi-8中不再起作用的原因是7.8已经删除了GHCi中的monomorphism restriction。为什么这是相关的呢?trace "eval foo" 5Num a => a类型的多态表达式。多态表达式 * 不能 * 是CAF。因此,您将获得 call-by-name 语义,而不是 call-by-need
再次获得共享的最简单方法是通过添加显式签名使类型单态化来强制CAF:

Prelude Debug.Trace> let foo = trace "eval foo" 5 :: Int in foo + foo
    eval foo
    10

相关问题