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 but not very well-designed unifier. A better version is covered in the reading on deductive data retrieval.
Here we're talking about a simpler pattern matcher that takes one pattern and one 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
- 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:
|Yes, they're equal|
|Yes, they're equal|
|No, they're not equal|
|Yes, and |
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
NILif the match fails
- a list of the list of bindings if the match succeeds
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
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 can't
arise in our simple matcher, but they arise as soon as we make any
extensions, such as "match ?x to A or B". Or, for a more complex
example, assume the pattern
(A ?* C) matches
any list that starts with A and ends with C, where
matches zero or more intermediate elements. Here are some
different examples of using
The last case is the important one. There are two equally valid bindings.
Many authors treat the "success but no bindings" case specially
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
T, or a list. The
simple recursive calling pattern found in
is lost when you do this. Furthermore, it doesn't handle multiple
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.