(in-package "USER")

(defparameter *grammar*
  '((S NP VP)
    (NP Det N)
    (VP V) (VP V NP) (VP V NP NP)
    (Det ein) (Det eines) (Det einem) (Det einen)
    (Det der) (Det des) (Det dem) (Det den) (Det die)
    (N berg) (N berges) (N berge) (N bergen) (N mann)
    (V schnarchen) (V schnarcht)
    (V sehen) (V sieht)
    (V geben) (V gibt)))

(defparameter *bottom* (quote %fail%))

(defmacro bottomp (foo) `(eq ,foo *bottom*))

(defun unify (fs-1 fs-2)
  (cond ((null fs-1) fs-2)
        ((null fs-2) fs-1)
        ((eq fs-1 fs-2) fs-1)
        ((or (atom fs-1) (atom fs-2)) *bottom*)
        (t
         ;;(let (result)
           #||
	   (dolist (fvp-1 fs-1 
                     (append result (set-difference fs-2 result :key #'first)))
             (let* ((key (first fvp-1))
                    (fvp-2 (assoc key fs-2))
                    (unify (if fvp-2 
                             (unify (rest fvp-1) (rest fvp-2))
                             (rest fvp-1))))
               (if (bottom unify)
                 (return *bottom*)
                 (push (cons key unify) result))))
	   ||#
	   (loop for (key . value-1) in fs-1
		 for fvp-2 = (assoc key fs-2)
		 for value-2 = (cdr fvp-2)
		 for unify = (if fvp-2
				 (unify value-1 value-2)
			       value-1)
		 if (bottomp unify)
		 return *bottom*
		 else collect (cons key unify) into result				      
		 finally (return (append result (set-difference fs-2 result :key #'first)))
		 )
	   ;;)
	)))

(defstruct fs
  fvps
  bindings)