Matching (of all kinds) is used for

What can be matched?

Graham gives a simple but not very well-designed unifier. For our purposes, we use a simpler pattern matcher that doesn't support matching patterns to patterns, a facility that adds great complexity and is not needed for our application.


You (i.e., your code) matches patterns against S-expressions (symbolic expressions -- a term in Lisp used to denote atoms and lists).

A pattern can be

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:

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

A variable P can be "bound" to S if

The matcher returns

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:

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, but that looks like the match failed.

The multiple bindings problem: Multiple binding lists can't arise in our simple matcher, but they arise as soon as we make any extensions. For example, a common extension is to allow "segment" variables, often marked with an asterisk, as in ?*x, which can match zero or more items in a list, e.g.,

(like ?*x) (like mary jon) Yes, and ?*x is (mary jon)
(like ?*x jon) (like mary jon) Yes, and ?*x is (mary)
(like ?*x mary jon) (like mary jon) Yes, and ?*x is ()

Consider, however, what happens when we match

(like ?*x ?*y)


(like jon mary)

There are three different answers:

Our matcher (when extended) simply returns a list of those three binding lists, i.e.,

(((?*x . ()) (?*y . (jon mary)))
 ((?*x . (jon)) (?*y . (mary)))
 ((?*x . (jon mary)) (?*y . ())))

[Well, actually Lisp prints the above like this:]

(((?*x) (?*y jon mary))
 ((?*x jon) (?*y mary))
 ((?*x jon mary) (?*y)))

Other 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. The simple recursive calling pattern found in pat-match.lisp is lost when you do this. Furthermore, it doesn't handle multiple binding 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.

Our matcher, while less intuitive at first glance, has a very simple semantics for its 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.

Faculty: Chris Riesbeck
Time: Monday, Wednesday, Friday: 1pm - 2pm
Location:Annenberg G15


Important Links