(in-package :cs325-user)

(define-test match-p
  (assert-true (match-p '(?x b ?y) '(a b c)))
  (assert-false (match-p '(?x b ?y) '(a d c)))
  (assert-false (match-p '(?x b ?y) '(a b)))
  (assert-true (match-p '?x 'a))
  (assert-true (match-p '?x '(a b c)))
  (assert-true (match-p '?x nil))
  (assert-false (match-p '(?x) nil))
  (assert-true (match-p '(a b c) '(a b c)))
  (assert-false (match-p '(?x b ?x) '(a b c)))
  (assert-true (match-p '(?x b ?x) '(a b a)))
  )

(defun match-p (x y &optional (blists '(nil)))
  (cond ((null blists) nil)
        ((eql x y) blists)
        ((var-p x) (var-match x y blists))
        (t
         (and (consp x)
              (consp y)
              (match-p (cdr x) (cdr y)
                       (match-p (car x) (car y) blists))))))

(defun var-p (x)
  (and (symbolp x)
       (eql (char (symbol-name x) 0) #\?)))

(defun var-match (x y blists)
  (and blists
       (let* ((blist (car blists))
              (binding (assoc x blist)))
         (cond ((null binding)
                (list (cons (list x y) blist)))
               ((eql y (cadr binding)) blists)
               (t nil)))))