Mon Aug 24 19:59:35 CEST 2009

Eager rewriting vs. ``something more general''

In the light of peephole optimizations and the Joy machine in [1].

How can you keep a rewriting system managable, if you don't pin it
down manually by performing only eager substitutions?

I guess what I'm looking for is confluence[2].

And I have this hunch that _interesting_ rewriting systems for
optimizations are _not_ going to be confluent: they probably lead to a
large number of possible irreducable forms which need extra
constraints to isolate a single solution.

I read in Muchnick[3] (Chapter 6: Producing Code Generators
Automatically, 6.2.1 p.140) that the standard peephole rewriting
techniques are essentially SLR(1) parsers.  Does this have anything to
do with that?

[1] http://zwizwa.be/darcs/libprim/pf/joy.ml
[2] http://en.wikipedia.org/wiki/Confluence_%28abstract_rewriting%29
[3] isbn://1558603204