Sat Jan 9 21:07:57 CET 2010

A simple pattern matcher

This seems to be the essence of bootstrapping: make sure syntax
translation doesn't become a pain.

What is the simplest form of pattern matcher that's easy to implement?
I guess one that just uses:

  - cons quote '()
  - variables

Essentially quasiquote can be re-used to convert an expression into
nested constructors, which can then be easily matched.

This is the "match in match" idea.

Match seems simplest to implement in CPS: every failure continues with
the next pattern.

(cons a b)
(if (pair? expr)
   (let ((a (car expr))
         (b (cdr expr)))

For an implementation check "The implementation of functional
programming languages" by Simon Peyton Jones.

It looks like that algorithm isn't what I'm looking for (it compiles
pattern matches to case expressions, avoiding multiple matches of the
same expression).

Some duplication of computation is probably OK, since most cases
useful atm are all head-tagged.

[1] http://www.cs.tufts.edu/~nr/pubs/match-abstract.html