Practice Tracings of Match

Here's the main function for match:

(defun match (p s)
  "Attempt to find a correspondence between P and S, utilizing
   any special constructs appearing in P.  Return an association
   list of bindings if successful; NIL otherwise."
  (cond
    ((handle-both-null p s))        ;;;Match type #1: (match '() '()) 
    ((handle-normal-recursion p s)) ;;;Match type #2: (match '(a b c) '(a b c))
    ((atom (first p)) nil)     ;;;First element of p should not be an atom here 
    ((handle-? p s))           ;;;Match type #3: (match '((? x) b..) '(a b..)))
    ((handle-* p s))         ;;;Match type #4: (match '((* x) c..) '(a b c..))) 
    ((handle-restrict-pred p s)) ;;;Match type #5: (match '((numberp x) a b)
    (t nil) ) )                  ;;;                       '(17 a b))



The 3 special forms are: (? x) match x with 1 wild card element
                         (* x) match x with a sequence of wild card elements
                         (predicate x)  check the element against a predicate

Some sample matches:
1. Match type #1:  P and S are both null.  Return the single element
   association list ((:YES . YES))

2. Match type #2:  The first element of the current P is a "normal" element.
   (match '(a b c d) '(a b c d)) --> returns ((:YES . :YES))

   Recursive rule:  (match (rest p) (rest s))  until nil lists are reached.

(defun handle-normal-recursion (p s)
  "Test for and handle case when the first
   elements of P and S are EQL."
  (if (atom (first p))
      (if (eql (first p)(first s))
          (match (rest p)(rest s)) ) ) )



3. Match type #3: The first element of the current P is the special form (? x)
   (match '((? x) b c) '(a b c))  
    --> returns  an association list ((X . A) (:YES . :YES))
        Variable X is bound to the single match element A in list S

   Recursive rule:  1. (match (rest p) (rest s)) --> rest-match
                    2. (acons Variable (first s) rest-match) 

 (defun handle-? (p s)
  "Test for and handle the case when (FIRST P) is of
   the form (? X)."
  (if s ; S must not be null
      (if (eql (1st-pattern-op p) '?)
          (let ((rest-match
                  (match (rest p)(rest s)) ))
            (if rest-match
                (acons 
                  (1st-pattern-variable p)
                  (first s)
                  rest-match) ) ) ) ) )
    
4. Match type #4: The first element of the current P is the special form (* x)
   (match '((* x) e) '(b c d e))
   --> returns an association list  ((X b c d) (:YES . :YES))
       where the variable x is associated with the sequence b c d

   There are 3 subcases:
    Subcase 1 - (* x) matches with a single element in the current S
                 Recursive call: (match (rest p) (rest s))
        >(match '((* x) b c d) '(a b c d))
               Returns ((X A) (:YES . :YES))
 
    Subcase 2 - (* x) matches with no elements in the current S
                 Recursive call: (match (rest p) s)
        >(match '((* x) b c d) '(b c d))
                 Returns ((X) (:YES . :YES))

    Subcase 3 - (* x) matches with more than 1 element in the current S
                 Recursive call: (match p (rest s))
        >(match '((* x) e) '(b c d e))
                 Returns ((X B C D) (:YES . :YES))

(defun handle-* (p s)
  "Test for and handle the case when (FIRST P) is of
   the form (* X)."
  (if (eql (1st-pattern-op p) '*)
      (let ((pattern-variable
              (1st-pattern-variable p) )
            (rest-match nil) )
        (cond ; subcase 1 --match 1 element of S:
              ((and s
                    (setf rest-match
                          (match (rest p)
                                 (rest s) ) ) )
               (acons pattern-variable
                      (list (first s))
                      rest-match) )

              ; subcase 2 --match no elements of S:
              ((setf rest-match (match (rest p) s))
               (acons pattern-variable
                      nil
                      rest-match) )

              ; subcase 3 --match more than 1 elt of S:
              ((and s
                    (setf rest-match
                          (match p (rest s)) ) )
               (acons pattern-variable
                      (cons (first s)
                            (val pattern-variable
                                 rest-match) )
                      (rest rest-match)) )
              (t nil) ) ) ) )

5. Special form (handle-restrict-pred p s)    (predicate x)
   >(match '((numberp x) b c d) '(17 b c d))
   Returns  ((X . 17) (:YES . :YES))
     apply the predicate on the first element of S, then
     recursively call (match (rest p) (rest s)) --> rest-match, then
     acons  variable with (first s) with rest-match 

(defun handle-restrict-pred (p s)
  "Handle case when (FIRST P) is of the form
   (PREDICATE X)."
  (if s ; S must not be null
    (if (member (1st-pattern-op p)
                '(? *) ) ; Don't apply '? or '*.
        nil
      (if (apply (1st-pattern-op p)
                 (list (first s)) )
          (let ((rest-match
                  (match (rest p) (rest s)) )
                (pattern-variable
                  (1st-pattern-variable p) ) )
            (if rest-match
                (acons pattern-variable
                       (first s)
                       rest-match) ) ) ) ) ) )