在GHC中重写为实用的优化技术：它真的需要吗？
我正在阅读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)
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) = fx : map f xs统一。
因此， map g (x:xs) = gx : map g xs 。
map f (map g (x:xs)) = map f (gx : map g xs) 。
map f (gx : map g xs)与map f (x:xs) = fx : map f xs 。
因此， map f (map g (x:xs)) = f (gx) : map f (map g xs) 。
因此我们现在有规则：
map f (map g []) = []
map f (map g (x:xs)) = f (g x) : map f (map g xs)
正如你所看到f (gx)只是(f . g)和map f (map g xs)被递归调用。 这正是map (f . g) xs的定义。 这种自动转换的算法似乎很简单。 那么为什么不实施这个而不是重写规则呢？
激进的内联可以导出许多重写规则是短期的平等。 不同之处在于内联是“盲目”的，所以你不能预先知道结果会好还是差，或者即使终止。
但是，重写规则可以根据关于该程序的更高级别的事实来完成非显而易见的事情。 将重写规则想象为向优化器添加新公理。 通过添加这些，您可以应用更丰富的规则，从而使复杂的优化更加容易实施。
例如，流融合会更改数据类型表示。 这不能通过内联来表示，因为它涉及表示类型的改变（我们根据Stream ADT重新构建优化问题）。 易于在重写规则中声明，单独内联不可能。
这个方向的东西在我的一个学生Johannes Bader的学士论文中进行了调查：在功能程序中查找方程式（PDF文件）。
在某种程度上它肯定是可能的，但是
然而，在其他转换如内联和各种形式的融合之后进行清理是有用的。
这可以被看作是在特定情况下平衡预期和在一般情况下平衡它们之间的平衡。 这种平衡可以产生有趣的情况，在这种情况下你可以知道如何更快地做出某些事情，但是如果你不这样做的话，它对一般的语言来说更好。
在您提供的结构中的特定地图中，计算机可以找到优化。 但是，相关结构呢？ 如果函数不是map，该怎么办？ 如果有一个额外的间接层，如返回地图的函数会怎样。 在这些情况下，编译器无法轻松进行优化。 这是一般情况下的问题。
如果您优化特殊情况，将会发生两种结果之一
鉴于开发人员在一般情况下需要考虑这种优化，我们希望开发人员在简单情况下执行这些优化，从而减少首先进行优化的需求！
现在，如果事实证明，您感兴趣的特定案例占据了Haskell世界代码库的2％这样的重大事件，那么应用您的特例优化将会有更强大的争论。
链接地址: http://www.djcxy.com/p/43181.html上一篇: Rewriting as a practical optimization technique in GHC: Is it really needed?