Overview
Matching (of all kinds) is used for
- pattern-directed inference (if you see something that matches A then do B)
- classification (A matches B therefore A is a kind of B)
- similarity judgment (A partially matches B, so A is similar to B)
- case-based reasoning (A is the best partial match to B that can be found in memory, so use the information attached to A when processing B)
The examples below are based on the pattern matcher defined in match.lisp, which can be loaded in the CS325 package with
(ql:quickload :exmatch)
A pattern matcher takes a pattern and an object that is not a pattern. A pattern can be
- an atom, like 12 or A
- a variable, which is any symbol beginning with a question
mark, e.g.,
?Xor ?PERSON - a list of patterns
Note the recursive nature of this definition. Here are some patterns:
(like mary jon) (like ?x ?y) (?fn ?arg1 ?arg2) (?fn (null ?x))
Here's what matches what and why:
| Pattern | Input | Matches? |
|---|---|---|
mary
| mary
| Yes, they're equal |
(like mary jon)
| (like mary jon)
| Yes, they're equal |
(like mary jon)
| (like jon mary)
| No, they're not equal |
(like ?x ?y)
| (like jon mary)
| Yes, and ?x is jon and
?y is mary
|
(like ?x ?x)
| (like jon mary)
| No, ?x can't be jon and
mary at the same time
|
(like ?x ?x)
| (like jon jon)
| Yes, ?x is jon
|
(like ?x ?y)
| (like jon jon)
| Yes, ?x and ?y are both
jon
|
Basic Pattern Match Rules
The basic rule for pattern matching is simple. Given a pattern P and an S-expression S, P matches S if
- P is equal to S, or
- P is a variable that can be "bound" to S
- P and S are both lists and their corresponding CAR's and CDR's are equal
A variable P can be "bound" to S if
- P has never been matched against anything before, or
- P was previously matched against something that equals S
The anonymous variable ? is treated specially. It matches anything but is never bound.
The matcher returns a list of binding lists. NIL
means there are no binding lists, i.e., the
match failed
Binding Lists
A binding list is simply a list of the variables in a pattern, paired with the items those variables matched in the input S-expression. For example, the binding list
((?x . jon) (?y . mary))
says that the variable ?x is bound to
jon and the variable ?y is bound to
mary.
Why does the pattern matcher return a list of binding lists? For two reasons:
- to distinguish successful matches with no bindings from failure to match in a simple fashion
- to allow pattern matches to return more than one binding list
The "success but no bindings" problem: Consider matching
(likes mary jon)with (likes mary jon). This
clearly matches but equally clearly generates no bindings. If our
matcher returned just a binding list, it would return
NIL in this case which looks like the match failed.
The multiple bindings problem: Multiple binding lists arise
as soon as we add more powerful forms to patterns. For example,
the pattern variable ?* inside
a list
can match zero or more elements. Here are some examples:
| Pattern | Input | Bindings |
|---|---|---|
(like ?* ?x) |
(like mary jon) |
?x is bound to jon |
(like ?x ?*) |
(like mary jon) |
?x is bound to mary |
(like ?* ?x ?*) |
(like mary jon) |
?x is bound to mary OR?x is bound to jon
|
The last case is the important one. There are two equally
valid bindings, depending on how many elements ?*
skips.
Other binding list approaches
Many authors treat the "success but no bindings" case specially
and return T. While intuitive, this means that every
function that calls the pattern matcher, including the internal
recursive calls of the matcher itself, have to check for three
possible values: NIL, T, or a list. This
leads to code cluttered with conditionals, and doesn't handle
multiple biniding lists.
Other authors, including Graham in Chapter 15, return multiple values: the binding list and a flag indicating whether the match succeeded or failed. Again, you lose the simple recursive calling pattern and you still don't handle multiple binding lists.
Using multiple binding lists from the start, while less intuitive at first glance, leads to simpler but more powerful code with a clean single return value:
Matching returns a list of all possible binding lists.
If the list is NIL, there were no possible binding
lists and the match must have failed.
If the list is (NIL), that's the list of one binding
list which happens to be the empty binding list.
There are no special cases with this approach. All code that calls the matcher can simply iterate through the list returned (which will usually have 0 or 1 lists in it) to process each binding list. No special checks.
Matcher extensions
Pattern matchers typically need a way to define more specialized matchers, for example, a way to say "match any number greater than 10". One or two such cases could be handled in the match-p function's conditional, but that quickly becomes unwieldy. A better approach is to use data-driven programming. The matcher has one branch that checks for a list that begins with a function whose name begins with a question mark. If found, the matcher calls that function with three arguments:
- the parameters, if any, that follow the pattern function name in the list
- the object being matched against
- the bindings lists
For example, the matcher code defines a pattern extension named ??.
(defun ?? (x y lsts) (and (apply (car x) y (cdr x)) lsts))
If we call matcher like this
(match-p '(?? > 10) 25)
then ?? will be called with (> 10),
25, and the default initial list of bindings lists
(nil). The body of ?? will
evaluate (> 25 10). Since that is true, (nil)
will be returned, indicating that the match succeeded. If object was 5,
the match would fail.
The matcher defines another extension, ?and, like this:
(defun ?and (x y lsts)
(cond ((null lsts) nil)
((null x) lsts)
(t (?and (cdr x) y (match-p (car x) y lsts)))))
This matches if all the parameters passed to ?and match the object. So the pattern
(?and (?? > 10) ?x)
will match anything greater than 10 and bind that number to ?x.
Finally, the matcher code defines ?* like this:
(defun ?* (x y lsts)
(append (match-p x y lsts)
(and (consp y)
(?* x (cdr y) lsts))))
This means pattern
(?* pat1 pat2 ...) will try matching
the list (pat1 pat2 ...) against an object,
the CDR of the object, the CDR
of that, and so on. All matches that work are kept. This is how
?* matches zero or more elements.