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.
Manuel Simoni's blog about programming (languages).
Have you looked at the Pure programming language? It's a nice language based around term rewriting.
ReplyDeleteThanks for the tip. I looked at it, but it's too complicated for my intentions. I'm looking at term rewriting, so I can implement a small TRS in C, saving me from the hassle of implementing the algorithms in C. So I need an extremely minimal TRS.
ReplyDelete