This assigment involves pattern matching. Recall that we discussed the equal function in class. A generalization of equality is computing the "similarity" of two objects. This we call pattern matching. Here is a basic pattern matching function that "drives" the real pattern matcher (rpm). The inputs being matched are pattern p and data d:
(defun match (p d)
(rpm p d nil))
Note that match is called by
users without specifying a third argument.
However, the real matcher,rpm,
requires an association list as its third argument. The
association list encodes the "pattern variables and their bindings".
Recall that data can be ANY LISP s-expression including atoms. Patterns may include pattern-variables (symbols that have been defined by some means to be variables) and Kleene star represented by the symbol "*". In a nutshell, rather than simply allowing simple wild card matching with ("?"), we would also like to use variables (we will use ?symbol for variables) to match data objects and be bound to them. These pattern variables are stored in an "association list" that we cart around through the recursion.
The real pattern matcher function returns "nil" if it fails to match, "t" if it succeeds but finds NO VARIABLES in the pattern, and "an association list of variable bindings" in the case where it succeeds, but only by replacing variables in the pattern. The association list contains the necessary substitutions.
Recall that an association list. is a list of pairs. Each pair is a list of two LISP values. The first LISP value is a symbol, the name of a pattern variable in this case. The second LISP value is the data element found to match the variable during the course of pattern matching. This bound value can be any LISP value. For example:
(match '(a ? ?x b ) '(a 1 2 b))matches and the returned value would be
( (?x 2) )That is, the second input matches the pattern if the variable ?x is bound to 2. Note that a ? matches anything (a single unit (atom or list)) without binding data to a variable.
Here is the real pattern matcher:
(defun rpm (p d a)
(cond
((and (null p) (null d)) ;we've exhausted both the pattern p and data d
(if a a t)) ; successfully matched, so return association list or T
((or (null p) (null d)) ;we've exhausted one and not the other
nil ) ;return failure
((is-vbl (first p)) ;we've encountered a pattern variable
(if
(and (assoc (first p) a) ;if it is bound to a value in the assoc list
((eql (first d) (assoc (first p) a)))) ;and that value is equal to the first data element
(rpm (rest p)(rest d) a) ; return the pattern match of the rest of the pattern with the rest of the data
(t nil))) ; else we have failed
(t ;else we have an unbound variable in the pattern
;bind it on the association list and similarly call rpm recursively.
(rpm (rest p)(rest d) (cons (list (first p) (first d)) a)))))
Here is Kleene Star (for free!) You can also include ?if preceeding this if you like.
...
((eq '* (first p)) ;Kleene Star matches 0 or more elements, so...
(let
((newa (rpm (rest p) d a))) ;See if * matches 0 elements
;Note how this is accomplished. We advance
;p to the cdr of p in the recursion BUT DO NOT ADVANCE d.
(if newa ;if we get a match
newa ;return the new association list
(rpm p (rest d) a)))) ;otherwise try to match one data element
;Note how this is accomplished. p is NOT
;ADVANCED, but d is. That is, in the recursive call
;p will still have kleene star as its head
;but d will be its cdr. Think about that! (Boy, is LISP cool!)
Note, the entire "let" can be simply replaced!
HOW?
(or
(rpm (rest p) d a)
(rpm p (rest d) a))
I won't say it...
Now that we have taken of Kleene Star, let's check to see if p starts with a symbol that is not a variable, nor a a Kleene Star.
...
((atom (first p)) ;if p starts with a nonvariable,
(if (eql (first p)(first d)) ;check to see if it is equal to the first element of the data
(rpm (rest p)(rest d) a) ;if it does, continue matching
(t nil))) ;otherwise we failed
If we have gotten to this case, we know we have a list
at the head of p.
This case is a little tricky.
...
(t
(let ((newa (rpm (first p)(first d) a))) ;pattern match the sublists
(cond
((null newa) nil) ;if that fails, then we fail
((listp newa) ;if here, we succeeded, but newa could be "t" or
;a binding list, if a binding list, continue with
; the newa
(rpm (rest p)(rest d) newa))
(rpm (rest p)(rest d) nil))));here newa is "t" so rpm with the
;association list of nil
That's it.
Lastly we have to define our variable definition functions. That is, we need to define variables so our pattern matcher will know when its encountered a pattern variable as opposed to an ordinary symbol. Well, that's left to you as an exercise. Hint: Look of the symbol-name and char functions.
(defun is-vbl (x) ( ... ) )
(A $listp B)matches (A (b c) B), since the predicate #'listp is applied to the sublist (b c) and succeeds, but it fails to match (A b B) since "b" is not a list.
Define a collection of predicates you will provide in your pattern matching language (for example, #listp, #numberp, #null) and implement these predicates in your extended version of the pattern matcher.
(! < ?x)means that the variable (in this case ?x) when encountered in a pattern will successfully match a data element ONLY IF the value of the data element is less than the value already bound to the variable ?x. So
(A ?x b ( ! < ?x))matches
(A 2 b 1)but it does not match
(A 2 b 34).Why? Because initially the ?x matched and was bound to the number 2. When the ( ! < ?x) is encountered, the datum item 34 is NOT less than 2. Define predicate variables with the convention
( ! predicate-name variable-name)The "shreak" (or "bang") symbol represents that this pattern object contains a predicate to apply followed by the name of a previously bound variable. If the variable name is missing, then only a predicate name is supplied. (You can tell the difference by counting the number of symbols following the exclamation point (shreak)).
Define a collection of predicates that you will use in your predicate variables and implement them accordingly. You don't need to do too many. But you should do a sufficient number to ensure your implementation works.
One very important predicate (for use in predicate variables) that you MUST include is the predicate similar. The "similar" predicate decides whether two Lisp symbols are deemed similar. For example, the symbol red might be defined as similar to the symbol maroon and when both are encountered and matched using similar in a predicate variable, the pattern matcher will accept them. For example
(A red b ( ! similar ?x))matches
(A red b maroon)but it does not match
(A red b duck)where we have red and maroon previously defined as "similar".
This is the ONLY thinking part of the assignment: How do you represent similar symbols? For example, given the following, the pattern matcher should return a match:
pattern: ( ?object (color (! similar red )) (taste horrible) (size ?) )
data: ( football (color brown) (taste horrible) (size football-size))
where we have red and brown previously defined as simliar.
(match '() '()) =>T (match '(ai) '(ai)) =>T (match '(ai cs) '(ai cs)) =>T (match '(cs ai) '(ai cs)) =>NIL (match '(1 2 3 0) '(1 2 3 4 0)) => NIL (match '(? mudd) '(seely mudd)) =>T (match '(?first ?middle mudd) '(seely w mudd)) => ((?MIDDLE W) (?FIRST SEELY)) (match '(? ?x ? ?y ?) '(Bill Gates Is A Good Man)) => NIL (match '(School Of Engineering and Applied Science) '(School Of Engineering)) => NIL (match '(* School Of Engineering and Applied Science) '(The Fu Foundation School Of Engineering and Applied Science)) => T (match '(The * School Of Engineering and Applied Science) '(The Fu Foundation School Of Engineering and Applied Science)) => T (match '(The * School Of Engineering and Applied Science) '(The School Of Engineering and Applied Science)) => T (match '(* 3 ?x 4 *) '(3 5 4)) => T (match '(we ?er $numberp ?er $listp e t) '(we gh 7 gh (5 6 7) e t)) => ((?ER GH)) (match '(df $null 67 $null t y) '(df () 67 nil t y)) => T (match '($listp) '((2))) => T (match '(?y e (! < 23) c 4) '(98 e 6 c 4)) => ((?Y 98)) (match '(?x 4 (! < 20) 4 ?y $numberp) '(10 4 3 4 5 256)) => ((?Y 5) (?X 10)) (match '(?z $numberp (! > ?z) *) '(13 1024 7)) => NIL (match '(er (! numberp) c 4) '(er 6 c 4)) => T (similar 'orange 'mango) => ((ORANGE MANGO)) (similar 'mango 'strawberry) => ((MANGO STRAWBERRY) (ORANGE MANGO)) (similar 'lewinsky 'jones) => ((LEWINSKY JONES) (MANGO STRAWBERRY) (ORANGE MANGO)) (match '(?president (! $similar jones)) '(clinton lewinsky)) => ((?PRESIDENT CLINTON)) (match '((! similar orange)) '(strawberry)) => NIL (match '((! similar orange)) '(mango)) => T (match '( ?x (1 2) ?y (4 5)) '(c (1 2) d (4 5))) => ((?Y D) (?X C)) (match '(?y ?z (c v)) '(8 gh (c v) )) => ((?Z GH) (?Y 8)) (match '(((get) me) out) '(get (me (out)))) => NIL