rules

[skaller]

I'm curious when and how GHC applies rewrite rules,
and how expensive it is.

Felix also has rewrite rules. It uses a woefully expensive
algorithm to apply them:

1) elide rules that refer to functions that have
themselves been elided since they can't be applied.

2) For each rule in turn

    For each subexpression going down and up 
    the subexpression tree, try to match the rule

    If there is a match perform a rewrite and set 
    a 'modified' flag

If the expression was modified, clear the flag
and goto step 2.

This process is 'more or less' applied before and after every 
other term rewriting (eg inlining) because reductions
can create inlining opportunities, reduce the amount
of inlining, but inlining also exposes new instances
of rule patterns.

AFAICS my algorithm is exponential or worse, however
I assume it is still efficient simply because not
many rule patterns turn up, and the ones that do
get reduced away quickly.

Felix allows these reductions in typeclasses,
but it doesn't selectively apply them to functions
using those classes -- the reductions are all
performed globally (all rules on all code).


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net