Matching templates against a tree - any ideas?

[Tim Peters]

[Ian Clarke, wants to do tree pattern-matching]

[John Skaller, suggests a parsing approach]

Note that John Aycock's "Compiling Little Languages" Python framework (see
DejaNews) is built on an Earley parser, constructing a parse tree from input
that matches an arbitrary context-free grammar.  In its latest version it
carries that one more step, exactly as John Skaller suggests, using the
Earley parser again to support pattern-based covering of the parse tree,
where "Patterns are just trees linearized into prefix form, which use
parentheses to denote subtrees".  Elegant!  Very easy to use once you get
the hang of it.  Slow.

Note that algebraic simplification (which appears to be your real thrust) is
a field unto itself; general pattern-based approaches aren't going to beat
focused domain-specific knowledge.

factoring-by-patterns-is-like-doing-arithmetic-in-base-1-ly y'rs  - tim