Term rewriting ftw!

I spent yesterday BBQing in the sun with a friend who's deep into term rewriting, and between too many sesame teriyaki skewers, beers, coffees, and spliffs of highest grade, he explained to me the basics of term rewriting systems (TRS's), and I must say I'm hooked.

IIUC there's a lot of variation between TRS's, and no standard syntax and/or semantics. But basically, many TRS's seem to be equivalent to first-order code, like basic Haskell without higher-order functions. TRS's use different strategies to rewrite terms (basically s-expressions). One strategy would be to always reduce the left-most terms first, until no more rules match.

Today I found Oleg's applicative-order term rewriting system for code generation. It gives a good taste of what can be achieved by term rewriting in the context of compilation, and also intuition about how to implement a TRS.