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 expression. 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 length). I hope this makes some sense.. Any ideas on this welcome. Cheers, Tom [1] http://zwizwa.be/staapl [2] http://zwizwa.be/darcs/staapl/staapl/pic18/pic18-unit.ss [3] http://zwizwa.be/archive/staapl.html ------------------------------------------------------------------------------ Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day trial. Simplify your report design, integration and deployment - and focus on what you do best, core application coding. Discover what's new with Crystal Reports now. http://p.sf.net/sfu/bobj-july _______________________________________________ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk