haskell - 重写作为 GHC : Is it really needed? 中的实用优化技术

Question

我正在阅读 Simon Peyton Jones 等人撰写的论文。命名为 “Playing by the Rules: Rewriting as a practical optimization technique in GHC” .在第二部分，即“基本思想”中，他们写道:

Consider the familiar map function, that applies a function to each element of a list. Written in Haskell, map looks like this:

map f []     = []
map f (x:xs) = f x : map f xs

Now suppose that the compiler encounters the following call of map:

map f (map g xs)

We know that this expression is equivalent to

map (f . g) xs

(where “.” is function composition), and we know that the latter expression is more efficient than the former because there is no intermediate list. But the compiler has no such knowledge.

One possible rejoinder is that the compiler should be smarter --- but the programmer will always know things that the compiler cannot figure out. Another suggestion is this: allow the programmer to communicate such knowledge directly to the compiler. That is the direction we explore here.

我的问题是，为什么我们不能让编译器更智能？作者说“但程序员总是知道编译器无法弄清楚的事情”。但是，这不是一个有效的答案，因为编译器确实可以计算出 map f (map g xs)相当于map (f . g) xs ，方法如下:

map f (map g xs)

map g xs与 map f [] = [] 合并.

因此map g [] = [] .

map f (map g []) = map f [] .
map f []与 map f [] = [] 合并.

因此map f (map g []) = [] .

map g xs与 map f (x:xs) = f x : map f xs 合并.

因此map g (x:xs) = g x : map g xs .

map f (map g (x:xs)) = map f (g x : map g xs) .
map f (g x : map g xs)与 map f (x:xs) = f x : map f xs 合并.

因此map f (map g (x:xs)) = f (g x) : map f (map g xs) .

因此，我们现在有规则:

map f (map g [])     = []
map f (map g (x:xs)) = f (g x) : map f (map g xs)

如您所见f (g x)只是 (f . g)和 map f (map g xs)被递归调用。这正是 map (f . g) xs 的定义。 .这种自动转换的算法似乎很简单。那么为什么不实现这个而不是重写规则呢？

Answer 1

激进的内联可以得出许多重写规则是简写的等式。
不同之处在于内联是“盲目的”，因此您事先不知道结果是更好还是更差，甚至不知道它是否会终止。

然而，重写规则可以做完全不明显的事情，基于关于程序的更高级别的事实。将重写规则视为向优化器添加新公理。通过添加这些，您可以应用更丰富的规则集，从而更容易应用复杂的优化。

Stream fusion ，例如，更改数据类型表示。这不能通过内联来表达，因为它涉及表示类型的更改(我们根据 Stream ADT 重新构建优化问题)。易于在重写规则中声明，仅靠内联是不可能的。