[Haskell-cafe] Re: Properties of optimizer rule application?

[Simon Peyton-Jones]

| Ok, this was a bad example. Try this one:
|    project . project . foo
|  with the rules
|    project (project x) = project x
|    project (foo     x) = projectFoo x
|
| Both rules can be applied to the expression, but you get one fusion more,
| if you use the first one first. Let me guess, in order to solve that, I
| should restrict the first rule to an earlier phase than the second rule.

As you point out, this set of rules is not confluent:
        project (project foo)
can reduce to
        --->  project (projectFoo x)
or to
        ---> projectFoo x
depending on the order of application.

The conventional solution is not to apply the rules very carefully (which is extremely hard in general), but rather to "complete" the rules, by adding
        project (projectFoo x) = projectFoo x

Now it doesn't matter which order you apply them in.

You can do this by hand, although it'd be quite a nice thing to automate it in GHC.


| To give a precise example: If I have a sequence of 'map's
|   map f0 . map f1 . ... . map fn
|  then there is some length where this is no longer collapsed to a single
| 'map'?

(a) GHC tries to do as much as possible in a single iteration of the simplifer; I think it uses an outermost-first strategy for this.

(b) For each phase it runs the simplifier until nothing changes, or a maximum of N times, where N is settable by a command-line-flag -fmax-simplifier-iterations.  After N it stops running that phase, even if the simplification has not terminated.

| However then I wonder, how it is possible to make the compiler to
| go into an infinite loop by the rule
|
|    "loop"   forall x,y.  f x y = f y x

Yes, it's possible.  Remember (a) does "as much as possible", which in your rule means rather a lot.


In this thread Roman and I have described stuff that isn't in the manual.  Henning, would you feel like elaborating the Wiki page
        http://haskell.org/haskellwiki/GHC/Using_rules
(which already has a lot of info) to reflect what you've learned?  That way it's preserved for others.

thanks

Simon