重写为GHC中的实用优化技术:它真的需要吗？

Question

我正在阅读Simon Peyton Jones等人撰写的论文.命名为"遵循规则:重写为GHC中的实用优化技术".在第二部分,即他们写的"基本思想":

考虑熟悉的map函数,它将函数应用于列表的每个元素.写在Haskell中,map看起来像这样:

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

现在假设编译器遇到以下调用map:

map f (map g xs)

我们知道这个表达式相当于

map (f . g) xs

(其中"."是函数组合),我们知道后一个表达式比前者更有效,因为没有中间列表.但是编译器没有这样的知识.

一个可能的反驳是编译器应该更聪明---但程序员总是会知道编译器无法弄清楚的事情.另一个建议是:允许程序员将这些知识直接传递给编译器.这是我们在这里探索的方向.

我的问题是,为什么我们不能让编译器变得更聪明？作者说"但程序员总是会知道编译器无法弄清楚的东西".但是,这不是一个有效的答案,因为编译器确实可以找出map f (map g xs)相当于的map (f . g) xs,这里是如何:

map f (map g xs)

1. map g xs与...结合map f [] = [].

   因此map g [] = [].

2. map f (map g []) = map f [].

   map f []与...结合map f [] = [].

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

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

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

4. 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

积极的内联可以得出许多重写规则是短手的等同.不同之处在于内联是"盲目的",因此您事先并不知道结果是好还是坏,或者即使它会终止.

然而,根据关于程序的更高级别的事实,重写规则可以完成非显而易见的事情.将重写规则想象为向优化器添加新公理.通过添加这些,您可以应用更丰富的规则集,从而使复杂的优化更容易应用.

例如,流融合改变了数据类型表示.这不能通过内联来表达,因为它涉及表示类型更改(我们根据StreamADT 重新构建优化问题).容易在重写规则中陈述,单独内联是不可能的.

Answer 2

在我的学生Johannes Bader的学士论文中调查了那个方向的东西:在功能程序中找到方程式(PDF文件).

在某种程度上它肯定是可能的,但是

• 这很棘手.找到这样的方程在某种意义上就像在定理证明器中找到证明一样困难,并且
• 它通常不是很有用,因为它倾向于找到程序员很少直接写的方程式.

然而,在其他变换(例如内联和各种形式的融合)之后进行清理是有用的.