From 09abed1ece463b6f50770aa31c747317983e974f Mon Sep 17 00:00:00 2001
From: "U-tackya-PC\\tackya" <yammouch@users.sourceforge.jp>
Date: Mon, 22 Nov 2010 21:28:02 +0900
Subject: [PATCH] [1] Functions were rewritten so those do not only use cl
 functions. 	modified:   unified-matcher.lisp 	modified:  
 ../test/test-unified-matcher.lisp

---
 src/unified-matcher.lisp       | 31 +++++++++++++++++++++++++------
 test/test-unified-matcher.lisp | 17 +++++++++++++++--
 2 files changed, 40 insertions(+), 8 deletions(-)

diff --git a/src/unified-matcher.lisp b/src/unified-matcher.lisp
index 63995f3..cb0315b 100755
--- a/src/unified-matcher.lisp
+++ b/src/unified-matcher.lisp
@@ -1,15 +1,34 @@
 ; a unified matcher
 
-; (load "utils")
-
 (defpackage :unified-matcher
   (:nicknames :um)
-  (:use :cl :utils)
-  (:export))
+  (:use :cl)
+  (:export :unify :fail))
 (in-package um)
 
 (defconstant fail (gensym "FAIL"))
 
 (defun var? (symb)
-  (eql (char (symbol-name symb) 0)
-       #\?))
+  (and (symbolp symb)
+       (eql (char (symbol-name symb) 0)
+            #\?)))
+
+; from `Paradigms of Artificial Intelligence Programming'
+(defun unify (x y &optional binds)
+  "See if x and y match with given bindings."
+  (cond ((eql binds fail) fail)
+        ((eql x y) binds)
+        ((var? x) (unify-variable x y binds))
+        ((var? y) (unify-variable y x binds))
+        ((and (consp x) (consp y))
+         (unify (cdr x) (cdr y)
+                (unify (car x) (car y) binds)))
+        (t fail)))
+
+(defun unify-variable (var x binds)
+  "Unify var with x, using (and maybe extending) bindings."
+  (let ((bind (assoc var binds)))
+    (if bind
+      (unify (cdr bind) x binds)
+      (cons (cons var x) binds))))
+
diff --git a/test/test-unified-matcher.lisp b/test/test-unified-matcher.lisp
index 5457cba..8e8cfc5 100755
--- a/test/test-unified-matcher.lisp
+++ b/test/test-unified-matcher.lisp
@@ -1,6 +1,19 @@
-(load #P"../src/utils")
 (load #P"../src/unified-matcher.lisp")
-(use-package :utils)
+(use-package :um)
 
 (assert (um::var? '?x))
 (assert (not (um::var? 'y)))
+(assert (not (um::var? 3)))
+
+(assert (eql (unify 'a 'a) nil))
+(assert (eql (unify 'a 'b) um:fail))
+(assert (equal (unify '?x 'a)
+               '((?x . a))))
+(assert (equal (unify '(?x ?y) '(a b))
+               '((?y . b) (?x . a))))
+(assert (equal (unify '(?x . ?y) '(a b c))
+               '((?y b c) (?x . a))))
+(assert (equal (unify '(?x a ?z) '(b ?y ?x))
+               '((?z . ?x) (?y . a) (?x . b))))
+(assert (equal (unify '(?x a ?y) '(b ?y ?x))
+               um:fail))
-- 
2.11.0