;; Copyright 1994, Brown University, Providence, RI
;; See end of file for full copyright information

;; (in-package 'user)

;; Matching from the logic chapter.

(defun is-VAR (x) (and (consp x) (eq (first x) '?)))

;; Determine if a constant and a pattern match.
(defun match (const pat)
  (aux-match const pat '((match t))))

;; Keep track of the bindings established so far.
(defun aux-match (const pat bdgs)
  (cond ((not bdgs) nil)
        ((atom pat) (if (eq pat const) bdgs nil))
        ;; If the pattern is a bound variable, match the
        ;; constant and whatever the variable is bound to.
        ;; If the pattern is a variable and not bound, 
        ;; then bind the variable to the constant.
        ((is-VAR pat)
         (let ((bdg (assoc pat bdgs :test #'equal)))
           (cond (bdg (aux-match const (second bdg) bdgs))
                 (t (cons (list pat const) bdgs)))))
        ((or (atom const) (null const)) nil)
        (t (aux-match (first const) 
                      (first pat) 
                      (aux-match (rest const)
                                 (rest pat) bdgs)))))

;; Test MATCH
(defun test () 
  (and (match '(loves (dog fred) fred) '(loves (? x) (? y)))
       (match '(loves (dog fred) mary) '(loves (dog (? x)) (? y)))
       (not (match '(loves (dog fred) fred) '(loves (? x) (? x))))
       (not (match '(loves (dog fred) mary) '(loves (dog (? x)) (? x))))))


;; Copyright 1994, Brown University, Providence, RI
;; Permission to use and modify this software and its documentation
;; for any purpose other than its incorporation into a commercial
;; product is hereby granted without fee.  Permission to copy and
;; distribute this software and its documentation only for
;; non-commercial use is also granted without fee, provided, however
;; that the above copyright notice appear in all copies, that both
;; that copyright notice and this permission notice appear in
;; supporting documentation, that the name of Brown University not
;; be used in advertising or publicity pertaining to distribution
;; of the software without specific, written prior permission, and
;; that the person doing the distribution notify Brown University
;; of such distributions outside of his or her organization. Brown
;; University makes no representations about the suitability of this
;; software for any purpose. It is provided "as is" without express
;; or implied warranty.  Brown University requests notification of
;; any modifications to this software or its documentation.
;;
;; Send the following redistribution information
;;
;;   Name:
;;   Organization:
;;   Address (postal and/or electronic):
;;
;; To:
;;   Software Librarian
;;   Computer Science Department, Box 1910
;;   Brown University
;;   Providence, RI 02912
;;
;;     or
;;
;;   brusd@cs.brown.edu
;;
;; We will acknowledge all electronic notifications.