Match Practice for Quarter 1 Test

(defun match (p s)           TRACE THE FOLLOWING CALL TO MATCH:                       
  (cond           -->(match '(is (* x) work (? y) the way)  '(is this going to work by the way))
    ((handle-both-null p s))		Label the values of P and S on each recursive call.
    ((handle-normal-recursion p s))		Count the total number of calls to match.
    ((atom (first p)) nil)  ;;(match ______  ______) new P = ______________   new S =______________
    ((handle-? p s))              _______________________________________________________________
    ((handle-* p s))             ________________________________________________________________
    (t nil) ) )                     _____________________________________________________________
                                    _____________________________________________________________
(defun 1st-pattern-op (p)                 _________________________________________________
 "Return the *, ? in the first pattern construct of P."  ___________________________________________
  (first (first p)) ) ; same as (CAAR P)     _______________________________________________
                                             _______________________________________________
(defun 1st-pattern-variable (p)             _______________________________________________
"Return the variable in the first pattern construct of P."   _______________________________________
  (first (rest (first p))) ) ; same as (CADAR P)     _______________________________________
                                                     ________________________________________
(defun handle-both-null (p s)                        ________________________________________
"Test for and handle case when both P and S are null." ________________________________________
  (if (and (null p)(null s))               Hint: First return value: Return ((:yes . :yes)) 
      '((:yes . :yes)) ) )              You should have a "Return" for each of your calls
                                                    to match.
(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)) ) ) )

(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) ) ) ) ) )

(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) ) ) ) )