Pattern Matching

Overview

Matching (of all kinds) is used for

inferencing (if A implies B, and C matches A, then 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)

What can be matched?

patterns -- can match many different instances or, with matchers called unifiers, can match other patterns
instances (or constants) -- can match other instances, albeit often only partially

Graham gives a simple unifier and backward chainer in Chapter 15. The simplicity of the unifier makes the backward chainer a bit messy. I recommend on the simple deductive data retrieval instead.

Here we're talking about pattern matching. 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., ?X or ?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 match

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 matches S

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

The multiple bindings problem: Multiple binding lists arise as soon as we add more powerful forms to patterns. We'll see many of them in the extensible pattern matcher below, but here's just one example. The pattern ?* inside a list pattern can match zero or more elements in a list. 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 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.

Extended Pattern Matching

The pattern matcher described above is useful, but too limited for serious applications, such as the Lisp Critic. The Lisp Critic uses a similar but somewhat more complicated pattern matcher that supports a number of additional pattern forms, including :

Pattern	Matches
`(... ?* ...)`	matches any list where `?` matches zero or more intermediate elements; note that `?` does not itself bind to anything
`(?and pat1 pat2 ...)`	matches anything that matches all of the patterns
`(?or pat1 pat2 ...)`	matches anything that matches any of the patterns
`(?not pat)`	matches anything that does not match the pattern

The extensible matcher uses a question mark to mark pattern matching operators, such as ?and and ?*. New operators can be defined by users as described here. This however raises a potential issue with how to interpret ?FOO. Is it a variable or is it an extension like ?AND? If ?FOO is not an extension when we wrote some code with a pattern, but later we defines ?FOO to be an extension, the pattern that used to work will now behave differently, with no warning.

To avoid this ambiguity, we drop the convenient simple ?X syntax for pattern variables. Instead we write (? X), or, in general, (? variable-name). Now there is no ambiguity.

?FOO is a pattern extension.
(? FOO) is a pattern variable.

The implementation of an extensible matcher is described here.