Common Lisp Package: SHADCHEN

README:

Shadchen: A pattern matching library

shadchen: Noun  
  matchmaker  
from Yiddish 

(note: there is an emacs lisp port of this library here) (note: if you are reading this README for the emacs version of the library, keep in mind that emacs symbols are case sensitive. Symbols are all lowercase in this library.)

I love pattern-matching, which I find to be a great way to combine destructuring data with type-checking when used in dynamic languages. If you aren't familiar with how pattern matching works, here is an example:

(defun second (lst)  
 (match lst  
  ((cons _ (cons x rest)) x))) 

MATCH introduces a pattern matching expression, which takes a value, in this case LST and a series of lists, whose first elements are descriptions of a data structure and whose subsequent elements are code to execute if the match succeeds. Pattern matching takes the description of the data and binds the variables that appear therein to the parts of the data structure they indicate. Above, we match _ to the car of a list, x to the car of that list's cdr, and rest to the cdr of that list.

If we don't pass in a list, the match fails. (Because of the behavior of CL's car and cdr, which return NIL on NIL, the form cons doesn't enforce a length requirement on the input list, and will return NIL for an empty list. This corresponds with the fact that in Common Lisp (car nil) is nil and (cdr nil) is nil.)

We might instead write:

(defun second-of-two (lst)  
  (match lst  
    ((list _ x) x))) 

Which returns the second element of a list only when a two element list is passed in. MATCH can take multiple pattern/body sets, in which case patterns are tried in order until one pattern matches, and the result of evaluating the associated forms is returned. If no patterns match, an error is raised.

Built-in Patterns

Shadchen supports the following built-in patterns.

_ 

Matches anything, but no bindings are made.

<SYMBOL>

Matches anything, binding <SYMBOL> to that value in the body expressions.

<KEYwORD-LITERAL>

Matches only when the value is the same keyword.

<NUMBER-LITERAL>

Matches only when the value is the same number.

<STRING-LITERAL>

Matches only when the value is string= is the same string.

(CONS <PATTERN1><PATTERN2>) 

Matches any CONS cell, or NIL, then matches &lt;PATTERN1&gt; and &lt;PATTERN2&gt;, executing the body in a context where their matches are bound. If the match value is NIL, then each PATTERN matches against NIL.

(LIST <P1> ... <PN>) 

Matches a list of length N, then matches each pattern &lt;PN&gt; to the elements of that list.

(LIST-REST <P1> ... <PN><REST-PATTERN) 

Matches <P1> - <PN> to elements in at list, as in the LIST pattern. The final &lt;REST-PATTERN&gt; is matched against the rest of the list.

(QUOTE DATUM) 

Only succeeds when DATUM is EQUALP to the match-value. Binds no values.

 (AND <P1> .. <PN>) 

Tests all &lt;PN&gt; against the same value, succeeding only when all patterns match, and binding all variables in all patterns.

 (OR <P1> .. <PN>) 

Tries each &lt;PN&gt; in turn, and succeeds if any &lt;PN&gt; succeeds. The body of the matched expression is then executed with that &lt;PN&gt;'s bindings. Each sub-pattern in an OR must bind an identical set of symbols or an error will be raised at compile time.

 (? PREDICATE <PATTERN>) 

Succeeds when (FUNCALL PREDICATE MATCH-VALUE) is true and when &lt;PATTERN&gt; matches the value. Body has the bindings of &lt;PATTERN&gt;.

 (FUNCALL FUN <PATTERN>) 

Applies FUN to the match value, then matches &lt;PATTERN&gt; against the result.

 (BQ EXPR) 

Matches as if by BACKQUOTE. If EXPR is an atom, then this is equivalent to QUOTE. If EXPR is a list, each element is matches as in QUOTE, unless it is an (UQ &lt;PATTERN&gt;) form, in which case it is matched as a pattern. Eg:

(match (list 1 2 3)  
  ((BQ (1 (UQ x) 2)) x)) 

Will succeed, binding X to 2.

(match (list 10 2 20)  
   ((BQ (1 (UQ x) 2)) x)) 

Will fail, since 10 and 1 don't match.

(values <P1> ... <PN>) 

Will match multiple values produced by a (values ...) form.

(let (n1 v1) (n2 v2) ... (nn vn)) 

Not a pattern matching pattern, per se. let always succeeds and produces a context where the bindings are active. This can be used to provide default alternatives, as in:

(defun non-nil (x) x)  
 
(match (list 1)  
 ((cons hd (or (? #'non-nil tl)  
               (let (tl '(2 3)))))  
  (list hd tl))) 

Will result in (1 (2 3)) but

(match (list 1 4)  
 ((cons hd (or (? #'non-nil tl)  
               (let (tl '(2 3)))))  
  (list hd tl))) 

Will produce (1 (4)). Note that a similar functionality can be provided with funcall.

Extending shadchen

Users can define their own patterns using the defpattern form. For instance, the behavior of CONS, which matches the empty list, may not be desired. We can define a match which doesn't have this behavior as:

(defun non-nil (x) x)  
(defpattern cons* (car cdr)  
 `(? #'non-nil (cons ,car ,cdr))) 

A pattern is a function which takes the arguments passed into the custom pattern, and expands them into a new pattern in the language of the built-in pattern-matching.

We can now say:

(match (cons 10 11)  
 ((cons* a b) a)) 

Which will produce 10, but:

(match nil  
 ((cons* a b) a)) 

Will raise a no-match error.

Judicious application of the matchers AND, FUNCALL, and ? allow the definition of arbitrary matchers without exposing the guts of the matching system.


Copyright 2012, Vincent Toups  
This program is distributed under the terms of the GNU Lesser  
General Public License (see license.txt). 

FUNCTION

Public

STRING (X)

Coerces X into a string. If X is a string, X is returned. If X is a symbol, X's pname is returned. If X is a character then a one element string containing that character is returned. If X cannot be coerced into a string, an error occurs.

Private

CALC-BACKQUOTE-BINDINGS (EXPR)

Calculate the bindings for a backquote expression.

CALC-PATTERN-BINDINGS (EXPR)

Given a shadchen pattern EXPR return a list of symbols bound by that expression.

CALC-PATTERN-BINDINGS-EXTENDED (EXPR)

Calculate the bound symbols of a user defined pattern.

EXTENDED-PATTERNP (PATTERN-HEAD)

Return T if PATTERN-HEAD indicates a user provided pattern.

LENGTH=1 (LST)

Returns T when LST has one element.

Undocumented

BQ->REGULAR-MATCH (BQ-EXPRESSION)

CALC-PATTERN-BINDINGS-LIST (EXPR &OPTIONAL ACC)

CANONICAL-BINDING-LIST (L)

COPY-MATCH-FAIL-STRUCT (INSTANCE)

EQUAL-BY-BINDING (&REST PATTERNS)

EQUAL-BY-BINDING2 (P1 P2)

EXTEND-DEFUN-MATCH-TABLE (NAME LEXPR)

HTBL-FETCHER (KEY)

MAKE-MATCH-FAIL-STRUCT (&KEY)

MAPCAT (F LST)

MATCH-?-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-AND-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-AND-EXPANDER* (SUB-EXPRESSIONS MATCH-NAME BODY)

MATCH-BACKQUOTE-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-CONS-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-EXTENDED-PATTERN-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-FAIL-STRUCT-P (OBJECT)

MATCH-FUNCALL-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-LET-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-LIST-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-LIST-EXPANDER* (SUB-EXPRESSIONS MATCH-VALUE BODY)

MATCH-LITERAL-CHARACTER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-LITERAL-KEYWORD (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-LITERAL-NUMBER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-LITERAL-STRING (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-MUST-MATCH-EXPANDER (MATCH-EXPR VAL-EXPR BODY)

MATCH-OR-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-OR-EXPANDER-UNSAFE (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-QUOTE-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MATCH-VALUES-EXPANDER (MATCH-EXPRESSION MATCH-VALUE BODY)

MUST-MATCH-CASE (MATCH-EXPR)

NON-KEYWORD-SYMBOL (O)

PACKAGE-NAME* (P)

SYMBOL< (S1 S2)

UQ? (E)

MACRO

Public

MATCH (VALUE &BODY FORMS)

Attempt to match VALUE against each of the patterns in the CAR of FORMS. When a match is detected, its subsequent forms are executed as in a PROGN where the bindings implied by the match are in effect. An error is thrown when no matches are found.

MATCH-LAMBDA (&BODY FORMS)

Like MATCH except the VALUE is curried.

MATCH-LET (BINDINGS &BODY BODY)

Just like let* but each symbol part of each binding can be a match expression of arbitrary complexity.

MATCH-LET* (BINDINGS &BODY BODY)

Just like let* but each symbol part of each binding can be a match expression of arbitrary complexity.

MATCH-LOOP (RECUR-POINT BINDINGS &BODY BODY)

Like match-let but the binding form can be re-entered by calling a local function indicated by `recur-point` with the same number of arguments as bindings expressions in BINDINGS.

Undocumented

DEFPATTERN (NAME ARGS &BODY BODY)

DEFUN-MATCH (NAME PATTERNS &BODY BODY)

DEFUN-MATCH- (NAME PATTERNS &BODY BODY)

Private

Undocumented

MATCH-HELPER (VALUE &BODY FORMS)

MATCH1 (MATCH-EXPRESSION MATCH-VALUE &BODY BODY)

NAMED-LET (NAME BINDERS &BODY BODY)

VARIABLE

Private

*EXTENDED-PATTERNS*

Holds user declared patterns.

Undocumented

*MATCH-FAIL*

*MATCH-FUNCTION-TABLE*

CLASS

Public

Undocumented

HASH-TABLE

NUMBER

STRING (X)

SYMBOL

Private

Undocumented

MATCH-FAIL-STRUCT