在什么情况下,Common Subexpression Elimination会影响Haskell程序的懒惰？

Question

来自wiki.haskell.org:

首先,公共子表达式消除(CSE)意味着如果表达式出现在多个位置,则重新排列代码,以便仅计算该表达式的值一次.例如:

foo x = (bar x) * (bar x)

可能会变成

foo x = let x' = bar x in x' * x'

因此,bar函数只被调用一次.(如果bar是一个特别昂贵的功能,这可能会节省很多工作.)GHC实际上并不像你期望的那样经常执行CSE.问题是,执行CSE会影响程序的严格性/懒惰性.所以GHC确实做了CSE,但仅在特定情况下---参见GHC手册.(部分？？)

长话短说:"如果你关心CSE,那就亲手做吧."

我想知道在什么情况下CSE"影响"程序的严格/懒惰以及可能产生什么样的影响.

Answer 1

天真的CSE规则将是

e'[e, e]  ~>  let x = e in e'[x, x].

也就是说,每当子表达式e在表达式中出现两次时e',我们就使用let-binding来计算e一次.然而,这导致一些微不足道的空间泄漏.例如

sum [1..n] + prod [1..n]

通常是O(1)像Haskell这样的惰性函数式编程语言中的空间使用(因为sum并且prod会拖尾并且等等等等),但是O(n)当天真的CSE规则颁布时会成为空间.这对于程序来说非常糟糕n!

然后,方法是使此规则更具体,将其限制为我们知道不会出现问题的一小组案例.我们可以从更具体地列举天真规则的问题开始,这将形成我们开发更好的CSE的一系列优先事项:

• 两个事件e可能是相距甚远的e',导致了长寿命的let x = e结合.

• let-binding必须始终分配一个先前可能没有的闭包.

• 这可以创建未绑定数量的闭包.

• 有些情况下,关闭可能永远不会解除分配.

更好的东西

let x = e in e'[e]  ~>  let x = e in e'[x]

这是一个更保守的规则,但更安全.在这里,我们认识到e出现了两次,但第一次出现在语法上支配第二个表达式,这意味着程序员已经引入了一个let-binding.我们可以安全地重用let-binding并替换第二次出现的ewith x.没有分配新的闭包.

句法统治的另一个例子:

case e of { x -> e'[e] }  ~> case e of { x -> e'[x] }

而另一个:

case e of {
   Constructor x0 x1 ... xn ->
     e'[e]
}

~>

case e of {
   Constructor x0 x1 ... xn ->
     e'[Constructor x0 x1 ... xn]
}

这些规则都利用了程序中的现有结构,以确保在转换之前和之后空间使用的动力学保持不变.它们比最初的CSE更保守,但它们也更安全.

也可以看看

有关懒惰FPL中CSE的完整讨论,请阅读Chitil(非常容易获得)1997年的论文.有关CSE如何在生产编译器中工作的完整处理,请参阅GHC的CSE.hs模块,由于GHC编写长脚注的传统,该模块已经过充分记录.该模块中的注释与代码比率不在图表中.还要注意那个文件有多大(1993)!