CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Oct 12, 1998)

"Pattern Matching and Conversational Agents"

Motivation: Pattern matching for condition testing in production systems


 

Various Pattern Matching Constructs

 

 
 
 
 
 

1. Comparing two expressions for equality.

2. Matching one list against another for correspondence of elements, but not equality.

3. List equality with wild card items.

4. Wild cards with assignment.

5. List equality with predicate tests on individual elements.

6. List equality with wild-sequence items.

7. "Unification" where both pattern and subject may contain variables, and almost any term may be substituted for a variable.
 
 


 

Pattern Matching as a Predicate

 

 
 
 
 
 

(matchp  pattern  subject)   returns True if the subject matches the pattern.

The returned value may be T to indicate a match,

Or it may be anything other than NIL to indicate a match.

A value of NIL indicates no match  (failure to match).
 


 

Pattern Matching as an Association Process

Elements of the subject are paired with elements of the pattern.

If the match is successful, the pairings are returned.

A list of pairings is often called an "association list"

               (match '( (?  x) (?  y))         '(hello  world) )

                ;  returns   ((X  .  HELLO) (Y  .  WORLD))

What about the case when there is a match but no associations of interest?

To return ( )  would suggest a failure to match  since ( ) = NIL.

Therefore, we had better return some kind of dummy association list.

Let's use  (( :YES  .  :YES ))

To permit recursive construction of the association list, let's assume that whenever a match is successful, the resulting ALIST will contain a final entry of ( :YES . :YES).

For example, ((X  .  HELLO) (Y  .  WORLD) ( :YES  .  :YES)).
 
 
 


 

Matching with strict equality

(defun match1 (p  s)
  (equalp  p  s) )

(setq s (read))
(if (match1 'hello  s)
    '(you said hello)
    '(I dont know what you said) )

;;; We need a matching function with more flexibility...
 


 

Matching structure but not "contents"

Assume we are dealing with lists and all atomic elements are considered as matching.

(defun  match2 (p  s)
  (cond ((atom p) (atom s))
            ((atom p) nil)
            ((match (car p) (car s))  (match (cdr p) (cdr s)))
            (t nil) ) )

(match2 '(i am happy) (we were sad))
T

;;;  But this is too flexible.
 
 


 

Matching as list equality with wild cards

(defun match3 (p  s)
  (cond ((null p)(null s))
            ((or (atom p)(atom s)) nil)
            ((equalp (car p) (car s))  (match3 (cdr p)(cdr s)) )
            ((eql (car p) '?) (match3 (cdr p)(cdr s)) )
            (t nil) ) )

(match3 '(today is ?)  '(today is monday))
T
(match3 '(today is ?)  '(yesterday was sunday))
NIL
 
 


 

Incorporating association lists

ACONS adds a new pair to an existing (association) list.

> (setq a (acons :yes :yes nil))
((:YES  :YES))
> (setq a (acons 'x 1 a))
((X . 1)(:YES . :YES))

To retrieve the association for X, use ASSOC.
> (assoc 'x a)
(X . 1)

To get the value associated with X, use CDR.

> (cdr (assoc 'x a))
1

(defun match4 (p  s)
  (cond ((and (null p)(null s)) '(:yes . :yes)) ; differs from match3
            ((or (atom p)(atom s)) nil)
            ((equalp (car p) (car s))  (match4 (cdr p)(cdr s)) )

            ((and (= (length (car p)) 2) ; differs from match3...
                     (eql (caar p) '?)
                     (let ((rest-match (match4 (cdr p)(cdr s))))
                       (if rest-match
                          (acons (cadar p) (car s) rest-match)
                       ) ) ))

           (t nil) ) )
 
 

MATCH = MATCH6

Features:
-- List equality with wild cards, wild sequences, restrictive functions, association lists.

Implementation uses "handler" functions for each clause of the COND.

Each handler takes care of both the Condition and the Action for one COND clause.

If the condition fails, then execution proceeds to the next CLAUSE. as with OR.
 


 

Examples with MATCH

(match '(hello (* w))  '(hello world and all that))
((W . WORLD AND ALL THAT) (:YES . :YES))
 

(match '(i am (numberp x) years (* y))
             '(i am 79 years of age) )
((X . 79) (Y OF AGE) (:YES . :YES))
 
 


 

Rule-based Conversational Agents

(defun converse ( )
 (print 'hello)
 (loop
  (setq user-input (read))
  (cond ((condition1)  (action1))
            ((condition2)  (action2))
            ...
            ((conditionk)  (actionk))  )

  ) ) )
 
 
 


 
 
 
 
 

Last modified: October 12, 1998

Steve Tanimoto

tanimoto@cs.washington.edu