Fare-matcher was superseded by optima according to optima's CLiki page. However, the discussion below is of general interest and importance. Lots of it is relevant for libraries that had superseded fare-matcher as they inherited some of its design. Note also the Lisp-2 vs Lisp-1 bit.
This language extension uses Lisp-2 style, which means that instead of writing
you'd write
Lisp-2 style means that instead of writing (destructuring-bind (a b (c d ()) . e) foo (bar a b c d e)) You'd write (match1 (list* a b (list c d 'nil) e) foo (bar a b c d e)) This might look heavier, but then, the fact that the head of a pattern is a designator for an arbitrary pattern instead of having patterns always be lists except for possible "magic" values like &rest and other keywords allows patterns to be clearer, and *extensible*. Thus you can trust that any symbol in head position is a pattern name, while any symbol in parameter position is a variable name, except if it is a special symbol, or if the head is a pattern macro, in which case it controls the meaning of the parameters.
The only predefined special symbol is _ that matches everything. I used to have T match anything (top) and NIL match nothing (bottom), but nobody liked it, so instead they are considered (together with keywords) as literals that match the constants T and NIL. Predefine functional patterns are CONS, LIST, LIST*, VECTOR, that match corresponding objects with a known arity. Predefined macro patterns are QUOTE, VALUE, LIKE-WHEN, AND, WHEN, OF-TYPE, SLOT*, ACCESSOR*, that respectively match a literal constant, the value of an expression, a pattern with a guard condition, the conjunction of several patterns, just a guard condition, any value of given type, any object with slots as specified, and object with accessors as specified. In fare-clos, it is also possible to match against an INSTANCE of a class with slots specified by initargs.
IFMATCH tries to match a pattern with an expression, and conditionally executes either the success form in a properly extended lexical environment, or the failure form in the original lexical environment, depending on whether the match succeeded (with freshly bound variables) or not. MATCH (that I won't rename to COND-MATCH) tries to match a given expression with several patterns, and executes the body of the matching clause if found. EMATCH is like MATCH except that when no match is found, it raises an error instead of returning NIL.
With this paradigm, matching patterns are thus dual from normal forms. I like to think of all forms as patterns, with some patterns being in "deconstruction position" (left-hand side of a match clause), and other patterns being in "construction position" (right-hand side of a match clause). Although the current implementation follows Erlang (or ML-like) semantics for matching, this paradigm can generalize to non-deterministic settings, where you'd obtain something much like Mercury, unifying functional and logic programming -- however, I haven't even attempted to implement non-determinism (maybe this could be done using Screamer).
NB: Actually, I had first thought about this pattern-matcher when I was more of a Lisp-1 fan, and the fact that Lisp-2 was much more natural for the pattern matcher finished to turn me into a Lisp-2 fan.
With fare-matcher, you can use these macros in your code:
ifmatch <pattern> <form> <then-clause> <else-clause>
ematch <form> <case-clauses> match <form> <case-clauses>
letm <pattern> <form> <lexical-scoped-body>
Patterns are lisp forms. Symbol in patterns match anything creating a binding to what they match, except * or _ will match anything but are not bound. Literals are matched using eq.
The core pattern matching forms are look like the forms for consing up things and match what otherwise they would create: list, list*, values, cons, and vector. Quite concise is that for most common lisp implementations you may use back-quoted forms.
Two forms slot*, accessor* allow you to match CLOS objects using the slot-names or the accessors respectively. By example:
Finally a few pattern forms provide for special cases: and, or, of-type, like-when.Some samples pulled from a test case:
(ifmatch (cons * (cons x y)) '(1 (2 3) 4) (list x y)) ==> ((2 3) (4)) (ifmatch (like-when (cons x y) (eql x y)) '(2 . 2) x) ==> 2 (ifmatch (and (cons x y) (when (eql x y))) '(2 . 2) x) ==> 2 (ifmatch (and (cons a 1) (cons 2 b)) '(2 . 1) (list a b)) ==> (2 1) (ifmatch (list a b) '(1 2) (list b a)) ==> (2 1) (ifmatch (list* a b c) '(1 2 3 4) (list a b c)) ==> (1 2 (3 4)) (ifmatch (and x (cons (of-type integer) *)) '(2) x) => (2)
(my-length '(1 2 3)) ==> 3
Finally, from the source code:
This is my attempt at a pattern matcher.
Semantic Design goals:
- ML- or Erlang-like semantics for pattern matching.
- Integration to the lexical environment: Variables in a match pattern are bound lexically around the form's body.
- Unlike destructuring-bind, follow the same Lisp-2 paradigm of source-level lists specifying a generic pattern to call and its arguments. This also allows to trivially distinguish between variables and pattern names by a simple syntactic positional criterion.
- Extensibility through definition of new generic patterns, either functions or macros, by defining new names or having algebraic designators.
- No backtracking or unification, but leaving possibility for such thing as an extension.
Implementation goals:
- macro-expansion-time transformation of pattern into recognizing code.
- This first version is no frills: no attempt at algorithmic efficiency, optimization or backtracking.
- Optimized for human simplicity.
- Highly-factored using higher-order functions and macros.
- Underlying control structures are to be abstract enough so that backtracking could be added by replacing them.
- the (ifmatch pattern form body...) macro expands into a (let (,@vars) (when (funcall ,matcher ,form) ,@body)) where (pattern-matcher pattern) returns (values matcher vars)
- matching code uses matcher-passing style - that's good.
- macro-expansion code uses a direct synthesis technique - that's bad. It means that all bindings for the match are common to all the matching forms, which requires a bit of discipline from writers of LIKE-WHEN clauses so that nothing evil should happen. Instead, we should use a monadic lexical-environment-passing-style that would create bindings as the match progresses.
- not much of any error detection is done, and when there is, error reporting is minimal.
- not any pattern optimization is done by the matching macros (however, since patterns are expanded into lisp code at macro-expansion time, the compiler might still do a few optimizations and produce reasonable code).
- add a special case for (values) at the top level (???)
- add better patterns for matching structures and classes
- add macros for defining simple patterns of patterns, both in matching and in building.
- add lots of error checking
- make for a better propagation of bindings within internal clauses of the pattern matcher (due to like-when). -- binding-passing style(?)
- add non-linearity???
- add backtracking, based on a CPS transform??? Or use Screamer?
- add first-class patterns (?)
- add pattern merging and optimization (!?) or maybe declarations? Factor the matching of identical initial patterns.
- add better documentation about the pattern matcher (???)
- add support for documentation strings in pattern defining forms
- add support for optional, rest and keyword arguments in defining forms
- add reader-macros for very common cases, if needed.
- have the equivalent of compiler-macros so as to define patterns to use when the patterns match a known pattern. E.g. when appending something to a list of known length (before or after), the matching procedure is simple.
- convert everything for use with some kind of first-class environments.