Pattern Matching

(defun equal (pat inp)
  (if (consp pat)          ; interior node?
      (and (consp inp)
           (equal (car pat) (car inp))
           (equal (cdr pat) (cdr inp)))
      (eql pat inp) ) )    ; leaf node

(defun match (pat inp) (matchb pat inp '((t . t))))
(defun matchb (pat inp bindings)
  (and bindings
    (if (consp pat)           ; interior node?
        (and (consp inp)
             (matchb (cdr pat) 
                     (cdr inp)
                     (matchb (car pat)
                             (car inp) bindings)))
        (if (varp pat)        ; leaf: variable?
            (let ((binding (assoc pat bindings)))
              (if binding
                  (and (equal inp (cdr binding))
                       bindings)
                  (cons (cons pat inp) bindings)))
            (and (eql pat inp) bindings)) ) ) )