在GHC中重写为实用的优化技术：它真的需要吗？ [英] Rewriting as a practical optimization technique in GHC: Is it really needed?

问题描述

我正在阅读西蒙佩顿琼斯等人撰写的论文。命名为按规则演奏：重写为GHC中的实用优化技术< / A>。在第二部分中，即基本思想他们写道：

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

  map f [] = [] 
 map f（x：xs）= fx：map f xs 
  

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

  map f（map g xs）
  

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

  
 
 $ block $ 
 $ p $（其中ldquo ;是函数组成），并且我们知道后者表达式比前者更有效，因为没有中间列表。但编译器没有这方面的知识。
 
 
一种可能的反应是编译器应该更聪明 - 但程序员总是知道编译器无法弄清楚的东西。另一个建议是：允许程序员直接将这些知识传递给编译器。这是我们在这里探索的方向。
 
 
我的问题是，为什么我们不能让编译器更聪明？作者说，但程序员总是会知道编译器无法想象的东西。然而，这不是一个有效的答案，因为编译器确实可以知道 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 []  $ b $ p $  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） code> map f（x：xs）= fx：map f xs 。
 
 
因此 map f （地图g（x：xs）） = f（gx）：map f（map g xs）。
 
 
 
现在有规则： 
 
 
  map f（map g []）= [] 
 map f（map g（ x：xs））= f（gx）：map f（map g xs）
  
见 f（gx）就是（f。 g）和 map f（map g xs）被递归调用。这正是 map（f。g）xs 的定义。这种自动转换的算法似乎很简单。那么为什么不实施这个而不是重写规则？
解决方案
激进的内联可以获得很多平等，重写规则是短暂的对于。 
不同之处在于内联是盲目的，所以你不能预先知道结果会好还是坏，或者即使它会终止。 
 
然而，重写规则可以根据关于该程序的更高层次的事实完成非完全不明显的事情。将重写规则想象为向优化器添加新公理。通过添加这些设置，您可以应用更丰富的规则，从而使复杂的优化变得更加容易。 
 
 
 流聚变，例如，改变数据类型表示。这不能通过内联来表示，因为它涉及表示类型的变化（我们根据 Stream  ADT重构优化问题）。易于在重写规则中声明，单独内联不可能。
 
I was reading the paper authored by Simon Peyton Jones, et al. named “Playing by the Rules: Rewriting as a practical optimization technique in GHC”. In the second section, namely “The basic idea” they write:

  
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.
My question is, why can't we make the compiler smarter? The authors say that “but the programmer will always know things that the compiler cannot figure out”. However, that's not a valid answer because the compiler can indeed figure out that map f (map g xs) is equivalent to map (f . g) xs, and here is how:
map f (map g xs)



map g xs unifies with map f [] = [].

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

map f [] unifies with map f [] = [].

Hence map f (map g []) = [].
map g xs unifies with map f (x:xs) = f x : map f xs.

Hence 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) unifies with map f (x:xs) = f x : map f xs.

Hence map f (map g (x:xs)) = f (g x) : map f (map g xs).
Hence we now have the rules:
map f (map g [])     = []
map f (map g (x:xs)) = f (g x) : map f (map g xs)
As you can see f (g x) is just (f . g) and map f (map g xs) is being called recursively. This is exactly the definition of map (f . g) xs. The algorithm for this automatic conversion seems to be pretty simple. So why not implement this instead of rewriting rules?
解决方案
Aggressive inlining can derive many of the equalities that rewrite rules are short-hand for.
The differences is that inlining is "blind", so you don't know in advance if the result will be better or worse, or even if it will terminate.

Rewrite rules, however, can do completely non-obvious things, based on much higher level facts about the program. Think of rewrite rules as adding new axioms to the optimizer. By adding these you have a richer rule set to apply, making complicated optimizations easier to apply.

Stream fusion, for example, changes the data type representation. This cannot be expressed through inlining, as it involves a representation type change (we reframe the optimization problem in terms of the Stream ADT). Easy to state in rewrite rules, impossible with inlining alone.

                        
这篇关于在GHC中重写为实用的优化技术：它真的需要吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！