Rewriting as a practical optimization technique in GHC: Is it really needed?

Question

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)

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

   Hence map g [] = [].

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

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

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

3. map g xs unifies with map f (x:xs) = f x : map f xs.

   Hence 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) 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?

Answer 1

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.