在什么情况下公共子表达式消除会影响 Haskell 程序的惰性？

Question

来自wiki.haskell.org：

First of all, common subexpression elimination (CSE) means that if an expression appears in several places, the code is rearranged so that the value of that expression is computed only once. For example:
foo x = (bar x) * (bar x)
might be transformed into
foo x = let x' = bar x in x' * x'
thus, the bar function is only called once. (And if bar is a particularly expensive function, this might save quite a lot of work.) GHC doesn't actually perform CSE as often as you might expect. The trouble is, performing CSE can affect the strictness/laziness of the program. So GHC does do CSE, but only in specific circumstances --- see the GHC manual. (Section??)

Long story short: "If you care about CSE, do it by hand."

想知道在什么情况下CSE "affects" 程序的strictness/laziness 会有什么样的效果。

Answer 1

天真的 CSE 规则是

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

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

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

通常是 O(1) space 在像 Haskell 这样的惰性函数式编程语言中的用法（因为 sum 和 prod 会尾递归等等等等blah)，但当幼稚的 CSE 规则生效时会变成 O(n)。当 n 很高时，这对程序来说可能很糟糕！

方法是让这条规则更具体，将其限制在我们知道不会的一小部分情况下。我们可以从更具体地列举朴素规则的问题开始，这将形成一组优先级，供我们开发更好的 CSE：

e 的两次出现可能 在 e' 中相距很远 ，导致 [=25] 的生命周期很长=]绑定.
let 绑定必须始终分配一个闭包，而以前可能没有闭包。
这可以创建无限数量的闭包。
有些情况下闭包可能永远不会解除分配。

更好的东西

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

这是一个更保守的规则，但更安全。这里我们认识到 e 出现了两次，但第一次出现 在语法上支配 第二个表达式，这意味着程序员已经引入了 let-binding。我们可以安全地重用那个 let-binding 并将第二次出现的 e 替换为 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]
}

这些规则都利用程序中现有的结构来确保space使用的动力学在转换前后保持不变。它们比原来的 CSE 更保守，但也更安全。

另见

要在惰性 FPL 中完整讨论 CSE，请阅读 Chitil's (very accessible) 1997 paper. For a full treatment of how CSE works in a production compiler, see GHC's CSE.hs module，由于 GHC 编写长脚注的传统，它的文档非常详尽。该模块中的注释代码比超出了图表。还要注意该文件的年龄（1993 年）！

在什么情况下公共子表达式消除会影响 Haskell 程序的惰性？

Under what circumstances could Common Subexpression Elimination affect the laziness of a Haskell program?

haskell

ghc

更好的东西

另见