Match6 - The Complete Matching Program
Tracing Exercises
The match6 function is a complex program. It handles pattern
matching of two lists, p and s, that may contain 3 types of special
forms. The 3 special forms are:
(? x), (* x), or (predicate x)
The special symbols ?, *, and predicate functions are each paired
with a variable. In this case the variable is x, but the
variable can be any name.
(? x) is a "wildcard" form that matches any single object in s
and binds the matched object with the variable x.
(* x) is a wildcard form that matches any sequence of objects
in s and binds the matched sequence with x.
(predicate x) applies the predicate to a matched object in s and
returns T or NIL
Running Match.lsp on lists p and s returns values based on
p and s having the following attributes.
1. If p and s are both empty, the form returned is
((:YES . :YES))
This type of form is called an association list, with this
format: ((key1 . value1) (key2 . value2) ...)
Therefore, if p and s are both empty, an association list with
one sublist is returned.
2. If the lists p and s have no special forms
(? x), (* x), or (predicate x),
then normal recursive matching is used, matching the first of
each list and recursing down the rest of each list until either
a mismatch is found or the end of the lists is reached.
Example: >(match '(a b c) '(a b c)) --> ((:YES . :YES))
The lists match each element until each list
becomes null and the value ((:YES . :YES)) is returned.
3. If there are no special forms and the lists are different
lengths, then NIL is returned.
4. If a special form of the type (? x) is encountered, the
following takes place:
1. Assign to "rest-match" the value of recursively matching
the rests of both lists following (? x).
2. Call the function "acons" on the three arguments:
- the variable paired with ?
- the list of the current first element in s
- the value of "rest-match"
LIST P LIST S
Example: (match '(a (? x) c (? z) e) '(a b c d e))
--> ((X . B) (Z . D) (:YES . :YES))
Whenever a match of two regular elements occurs, for instance
the "a" and the "c", nothing is added onto the final
result list. The only time a form is added to the result
list is either when the end of the lists are reached -
and ((:YES . :YES)) is returned, or when a special form
such as (? x) is matched.
In the above example, first the (:YES . :YES) is added,
then the (Z . D) and lastly the (X . B). This process
works in reverse order because of the recursive backtracking.
5. If a special form of the type (* x) is encountered, the
variable x can match a sequence of elements in list s.
LIST P LIST S
Example: (match '((* x) a b) '(1 2 3 a b))
--> ((X 1 2 3) (:YES . :YES))
The variable x is bound to the sequence 1 2 3 after the elements
a and b match from both lists with the regular recursive
check.
This match for sequences has three subcases:
- Subcase 1, matching one element in S.
When the (* x) is encountered, try to match the rest
of P - (a b) with the rest of S - (2 3 a b). In this
case there is no match because the sequence is longer
than one element.
- Subcase 2, matching no elements in S.
When the (* x) is encountered, try to match the rest
of P - (a b) with S - (1 2 3 a b). Again, there is
no match.
- Subcase 3, matching more than one element in S.
When the (* x) is encountered, try to match
P - ((* x) a b) with the rest of S - (2 3 a b).
This is handled recursively until the (a b) is reached
in both lists. At this point, the normal recursive
condition holds until the end of each list, where
((:YES . :YES)) is returned. Backtracking through
Subcase 3, "acons" the following three arguments into
an association list:
1. the pattern variable (X in this case)
2. the list of the current first element in S
3. the current associated value of X (first (3),
and then (2 3)
6. If the special form of the type (predicate x) is encountered
The predicate form in P is matched with the corresponding
object in S, if True the match continues.
Example: (match '(a (numberp x) c) '(a 17 c))
--> ((X . 17) (:YES . :YES))
The evaluation of this form follows:
- The a's match in each list,
- The special form (numberp x) matches with 17,
and "(apply numberp '(17))" is called. The result
is "acons"ed with the variable (X . 17)