A pattern matching library for Emacs Lisp
One of the things I like most about Racket (and other functional programming languages) is that they have good support for pattern matching, which is a great way to simultaneously dispatch on structure type, enforce constraints on values held in a data structure, and bind variables. A tremendous amount of code is devoted to these activities, and pattern matching combines them all in a succinct, easy to read form.
It's been my intent for some time to write a complete pattern matching library for Emacs Lisp, since it is a Lisp which I use very frequently. Shadchen is the first time any attempt to do so has resulted in a reasonable product. Shadchen is a Yiddish word for matchmaker, in case you were wondering about the title. The library is available in my elisp repository. Even though it comes in a giant directory full of junk, it runs standalone.[EDIT: Here it is in a standalone repo.]
How it Works
Shadchen's interface consists of just three forms.
match is the
work horse - it actually performs a pattern match.
match has the
(match <VALUE> (<PATTERN1> FORMS ...) (<PATTERN2> FORMS ...) ... (<PATTERNN> FORMS ...))
<VALUE> expression is evaluated, and then each pattern attempts
to match against it. If a pattern succeeds, it's associated FORMS are
evaluated, in a context where the environment has been extended by the
pattern's bindings. If a match fails, the next pattern is tried. If
no patterns succeed, an error occurs.
Here is an example:
(match (list 1 2 3) ((list x y z) (+ x y z)))
(list x y z) is the pattern in the above expression.
Patterns are such that they resemble the code which creates the data
structure in question, in this case a three element list. The pattern
(list x y z) basically specifies that a match occurs when the input
value is a three element list. When a match occurs,
x is bound to the
y to the second and so on. Hence this form evaluates
Here is another example: summing a list:
(defun* dummy-sum (lst &optional (acc 0)) (match lst (nil acc) ((cons hd tl) (dummy-sum tl (+ acc hd)))))
First we specify the pattern
nil, which matches only
the input is
nil, we return the accumulator. Then we match against
(cons hd tl) which matches a cons
hd to the
tl to the
cdr. We then recur, adding to the accumulator.
The pattern matching language is rich. There are patterns for matching against literals, applying functions to values, matching against arbitrary conditions, matching against structs.
(defstruct a-struct f1 f2)
With this struct defined, the pattern:
(struct a-struct (f1 (? #'numberp x)) (f2 (? #'stringp y)))
Matches only a struct whose field
f1 is a number, and whose field
f2 is a string. When that is true,
y are bound.
The pattern matcher is user extensible using
Defpattern defines a function which receives the pattern's
arguments, and returns a new pattern which effects the desired match.
For instance, the
struct pattern is defined thusly:
(defun cl-struct-prepend (s) (intern (format "cl-struct-%s" s))) (defun make-cl-struct-accessor (struct-name slot) (intern (format "%s-%s" struct-name slot))) (defpattern struct (struct-name &rest fields) `(and (? #'vectorp) (? #'(lambda (x) (> (length x) 0))) (? #'(lambda (o) (eq (elt o 0) ',(cl-struct-prepend struct-name)))) ,@(loop for f in fields collect `(funcall #',(make-cl-struct-accessor struct-name (car f)) ,(cadr f)))))
Note that the
defpattern body must return a valid pattern in terms
of previously defined patterns (or itself, patterns can be
recursive). In this case we use the patterns
funcall to create a new matcher.
Shadchen supports the following patterns:
Shadchen supports the following built-in patterns.
Matches anything, binding
Matches only when the value is the same keyword.
Matches only when the value is the same number.
Matches only when the value is
string= is the same string.
(CONS <PATTERN1> <PATTERN2>)
CONS cell, or
NIL, then matches
<PATTERN2>, executing the body in a context where their matches are
bound. If the match value is NIL, then each
PATTERN matches against
(LIST <P1> ... <PN>)
Matches a list of length N, then matches each pattern
<PN> to the
elements of that list.
(LIST-REST <P1> ... <PN> <REST-PATTERN)
<REST-PATTERN> is matched against the rest of the list.
Only succeeds when
EQUALP to the match-value. Binds no
(AND <P1> .. <PN>)
<PN> against the same value, succeeding only when all
patterns match, and binding all variables in all patterns.
(? PREDICATE <PATTERN>)
(FUNCALL PREDICATE MATCH-VALUE) is true and when
<PATTERN> matches the value. Body has the bindings of
(FUNCALL FUN <PATTERN>)
FUN to the match value, then matches
<PATTERN> against the
Matches as if by
EXPR is an atom, then this is
EXPR is a list, each element is matches
QUOTE, unless it is an
(UQ <PATTERN>) 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
1 don't match.
(values <P1> ... <PN>)
Will match multiple values produced by a
(values ...) form.
(struct struct-name (field-name <P1>) (field-name <P2>) ... (field-name <P3>))
Which matches when the input is a struct of type
If you are an elisp hacker like me, now you don't have to envy those snooty Racket, ML and Haskell programmers. Happy Hacking!
(PS - the library is also available in Common Lisp, check my github).
(PPS - I love Racket, ML and Haskell programmers and they aren't at all snooty.