Tue Aug 25 08:00:05 CEST 2009

rewriting -> Factor list

Hello list,

I guess this is mostly for Daniel, but anyone else of course feel free 
to chime in...

I'm trying to get a better idea about rewriting systems for
concatenative languages, particularly in the area of specification of
peephole optimizations.  It's been on my mind for a while, but I've
always side-stepped any non-deterministic computations.  I.e. in
Staapl[1], the PIC18 code generator[2] is written using an eager
pattern matching approach, essentiall re-interpreting already
generated machine code as stack machine code that can then be
partially evaluated together with the currently compiling primitive
operation.  (Explained here[3] in some detail).

I've always been suspicious that this formulation, while it works well
in practice and has a certain elegance, is a special case of a more
general, non-confluent rewriting system.  

It seems to me that if there are any interesting optimizations to
make, they are not going to be unique and depend on which path through
the reduction rules is used to get to a particular irreducible

And then it stops.

I have some intuition about reduction machines, as long as they
compute a unique solution (lambda calculus w. strict eval (CEK
machine) and lazy eval using graph reduction, ...) but I'm not sure
how to view the other cases where you have a bunch of rewrite rules
and you ask the compiler to pick a sequence of reduction rule
applications that leads to the ``most optimal'' reduction under some
kind of cost function (for PIC18 this would be the machine code

I hope this makes some sense..
Any ideas on this welcome.


[1] http://zwizwa.be/staapl
[2] http://zwizwa.be/darcs/staapl/staapl/pic18/pic18-unit.ss
[3] http://zwizwa.be/archive/staapl.html