;;;; -*- mode:Scheme -*- ;;;;

;;;; MATCHER
;;; Derives from an implementation by Patrick Winston. 
;;; Modified by Tomas Lozano-Perez.

(define (match p d) (do-match p d *no-bindings*))

;;Arguments:	Pattern, datum, optional bindings.
;;Returns:	A list of bindings or #f
;;Remarks:	Pattern variables are indicated by ?<variable name>

(define (do-match p d bindings)
  (cond ((eq? p d) 
	 bindings)
        ((variable? p)
         (match-variable p d bindings))
        ((pair? p)
         (match-pair p d bindings))
	(else
	 *fail*)))

(define (match-variable var d bindings)
  (let ((binding (get-binding var bindings)))
    ;;Is the pattern variable on the list of bindings:
    (if binding 
        ;;If it is, substitute its value and try again:
        (do-match (binding-val binding) d bindings)      
        ;;Otherwise, add new binding:
        (extend-bindings var d bindings))))

(define (match-pair p d bindings)
  (let ((result (do-match (first p) (first d) bindings)))
    ;;See if the FIRST parts match producing new bindings:
    (if (eq? result *fail*)
	;;If they do not match, fail.
	*fail*
	;;If they do match, try the REST parts using the resulting bindings:
	(do-match (rest p) (rest d) result)
	)))