2014-05-23 48 views
3

我很关心哈斯克尔懒惰评价的效率。 考虑下面的代码我很困惑哈斯克尔的懒惰评价

main = print $ x + x 
    where x = head [1..] 

这里,x第一持有head [1..]而不是结果1表达,由于懒惰, 但后来当我打电话x + x,将表达head [1..]执行两次?

我发现haskell.org下面的描述中

懒惰评价,另一方面,意味着只有需要它的结果时,计算表达式(注意,从“还原”转向“评价”) 。因此,当评估引擎看到一个表达式时,它会构建一个thunk数据结构,其中包含评估表达式所需的任何值以及指向表达式本身的指针。当实际需要结果时,评估引擎调用表达式,然后用结果替换thunk以备将来参考。

那么,这是否意味着,在x + x,称第一x时,head [1..]执行和x被重新分配给1,第二x只是调用它的参考?

我理解这个权利吗?

回答

10

这是关于特定Haskell实现的问题,而不是关于Haskell本身的问题,因为语言对于如何评估事物没有特别的保证。

但是在GHC(以及大多数其他实现中,据我所知):是的,当thunk被评估时,它们被内部结果取代,所以其他引用同样的thunk从评估它的工作中受益第一次。

需要注意的是,对于哪些表达式最终实现为对同一个thunk的引用没有真正的保证。一般情况下,只要结果相同,编译器就可以对您喜欢的代码进行任何转换。当然,在编译器中实现代码转换的原因通常是为了加快代码的速度,所以希望不会重写某些东西,使其变得更糟,但它永远不会是完美的。在实践中,假设每当你给一个表达式一个名字(如在where x = head [1..]中),那么你通常很安全,那么该名字的所有用法(在绑定范围内)将是对单个thunk的引用。

3

有两种方法来评估的表达式:

  1. 懒惰(评价最外侧的第一)。
  2. 严格(评估最里面的第一个)。

考虑下面的函数:

select x y z = if x > z then x else y 

现在,让我们把它叫做:

select (2 + 3) (3 + 4) (1 + 2) 

这将如何进行评估?

严格评价:评价最里面的第一个。

select (2 + 3) (3 + 4) (1 + 2) 

select 5 (3 + 4) (1 + 2) 

select 5 7 (1 + 2) 

select 5 7 3 

if 5 > 3 then 5 else 7 

if True then 5 else 7 

5 

严格的评估花了6个减少。要评估select我们首先必须评估它的论点。在严格评估中,函数的参数总是被充分评估。因此功能是“按价值调用”。因此没有额外的簿记。

懒惰评价:评价最外面的第一个。

select (2 + 3) (3 + 4) (1 + 2) 

if (2 + 3) > (1 + 2) then (2 + 3) else (3 + 4) 

if 5 > (1 + 2) then 5 else (3 + 4) 

if 5 > 3 then 5 else (3 + 4) 

if True then 5 else (3 + 4) 

5 

懒惰评价只需要5减少。我们从未使用过(3 + 4),因此我们从未评估过它。在懒惰评估中,我们可以评估一个函数而不用评估它的参数。参数只在需要时才被评估。因此功能是“按需呼叫”。

然而,“按需呼叫”评估策略需要额外的簿记 - 您需要跟踪是否评估了表达式。在上述表达式中,当我们评估x = (2 + 3)时,我们不需要再次评估它。但是,我们确实需要跟踪它是否得到评估。


Haskell支持严格和懒惰的评估。但是它默认支持懒评估。要启用严格的评估,您必须使用特殊功能seqdeepSeq

同样,您可以在JavaScript等严格语言中进行懒惰评估。但是,您需要跟踪表达式是否已经过评估。你可以研究用JavaScript或类似语言实现thunk。

9

起初,x只是一个thunk。你可以看到如下:

λ Prelude> let x = head [1..] 
λ Prelude> :sprint x 
x = _ 

这里_表明x尚未评估。它的纯粹定义被记录下来。

然后,您可以了解如何构建x + x只是意识到x是一个指向此thunk的指针:这两个x将指向相同的thunk。一旦被评估,另一个是,因为它是相同的thunk。

你可以看到,ghc-vis

λ Prelude> :vis 
λ Prelude> :view x 
λ Prelude> :view x + x 

应该表现出你的线沿线的东西:

thunk

在这里你可以看到x + x thunk的实际指向两次向x咚。

现在,如果你评估x,通过打印出来,例如:

λ Prelude> print x 

你会获得:

evaluated

您可以在这里看到的是,x thunk是不再thunk:值为1.