On Thu, 22 Apr 1999, Simon Peyton-Jones wrote:
> This might be a good time to tell GHC users what I've been up to
> recently. I'm dreadfully embarassed that GHC doesn't do fusion,
> and, partly as a result, has rotten array performance. Motivated
> by this, and some other ideas, I have finally bitten the bullet
> and added a fairly general mechanism that allows the programmer
> to specify rewrite rules. For example:
>
> {-# RULES
> "map/map" forall f,g,x. map f (map g x) = map (f.g) x
> #-}
>
> The compiler applies the rules left -> right, in the expectation
> that each is an optimisation of some kind.
>
WOW!
This is REALLY cool!
I wonder what can be expressed using the RULES pragma. I am currently
experimenting with an optimisation that generates fusion-rules using a
"free theorem" [1]. These rules are on the form (a bit simplified):
forall f,g,g'. f.g = g'.F => f(g x) = g' x
According to the examples you give it would not be possible to have rules
like this where there is a new function (g' in my example) introduced by
the rule. (F is known, the lhs of the arrow can be though of as defining
of the meaning of g'.) What are the limitations?
[a lot of examples]
> Making all this work takes some care. In particular, I have
> to be jolly careful about when to inline things. It's just
> about working, but I want to make sure list fusion works well
> and arrays are a lot more efficient than they were before I
> commit it into the repository.
>
Will this machinery replace other transformations in GHC. How big impact
will it have on the structure of the compiler.
I hope you will release this soon. It's a very interesting addition.
> I'd be very interested if anyone can think of useful applications
> for this kind of thing. Of course you can shoot yourself in the
> foot pretty badly -- I think of it as a library-writer's facility
> not a programmer's facilty. (Like weak pointers and other such.)
> Curiously, I don't know of a *compiler* for any language that
> supports this ability.
>
This is (I believe) exactly the compiler support needed for systems which
reason about programs and try to improve them. There has been some work on
achieving this in the Clean environment. For more information:
http://www.cs.kun.nl/~maartenm/CleanProverSystem/
/Josef
[1] L. Fegaras. Using the Parametricity Theorem for Program Fusion. Oregon
Graduate Institute Technical Report 96-001.
----------------------------------------------------------
|Josef Svenningsson|http://www.dtek.chalmers.se/~d95josef|
|Rubingatan 39 | email: [EMAIL PROTECTED] |
|421 62 G�teborg | tel: 031-7090774 |
----------------------------------------------------------
What is a magician but a practising theorist?
-- Obi-Wan Kenobi
