<cl> (unify '(?x ?y ?z a) '(?y ?z ?x ?y)) Error: Received signal number 2 (Keyboard interrupt) Restart actions (select using :continue): 0: continue computation [1c] <cl> :resetのように,変数を仲立ちにして循環する場合にも同じ無限ループの問題が 起こってしまう. 実際にどのようなことが起こっているかを知るために, デバッグ用の組み込みマクロtraceを使ってみる.
<cl> (trace unify) ; Fast loading /usr/local/lib/acl/code/trace.fasl. (UNIFY) <cl> (unify '(?x ?y a) '(?y ?x ?x)) 0: (UNIFY (?X ?Y A) (?Y ?X ?X)) 1: (UNIFY ?X ?Y NIL) 1: returned ((?X . ?Y)) 1: (UNIFY (?Y A) (?X ?X) ((?X . ?Y))) 2: (UNIFY ?Y ?X ((?X . ?Y))) 2: returned ((?Y . ?X) (?X . ?Y)) 2: (UNIFY (A) (?X) ((?Y . ?X) (?X . ?Y))) 3: (UNIFY A ?X ((?Y . ?X) (?X . ?Y))) 4: (UNIFY ?Y A ((?Y . ?X) (?X . ?Y))) 5: (UNIFY ?X A ((?Y . ?X) (?X . ?Y))) 6: (UNIFY ?Y A ((?Y . ?X) (?X . ?Y))) 7: (UNIFY ?X A ((?Y . ?X) (?X . ?Y))) ....あと同じように,交互に続く.ここで問題となるのは,2:のバインディング情報に,
((?Y . ?X) (?X . ?Y))が入っていることである.このような循環をバインディングリストへ登録してし まわないようにしなければならない. つまり,
2: (UNIFY ?Y ?X ((?X . ?Y)))のところで,(?y . ?x)をバインドさせてはいけない. これは,すでに,?xがバインディングリストに入っているので, ?xの値をとってきたものとUNIFYさせなければならない. つまり,
(UNIFY ?Y ?Y ((?X . ?Y)))という具合になるわけである. そこで,
(defun unify-variable (p d bindings) (cond ((eql p d) bindings) ((get-binding p bindings) (unify (lookup p bindings) d bindings)) ((and (variable-p d) ;;; ここを (get-binding d bindings)) ;;; 追加 (unify p (lookup d bindings) bindings)) (t (add-binding p d bindings))))というように,dも変数の時で,bindingsにその変数の値がある場合には, その値とマッチングをとる. これにより,
<cl> (unify '(?x ?y a) '(?y ?x ?x)) 0: (UNIFY (?X ?Y A) (?Y ?X ?X)) 1: (UNIFY ?X ?Y NIL) 1: returned ((?X . ?Y)) 1: (UNIFY (?Y A) (?X ?X) ((?X . ?Y))) 2: (UNIFY ?Y ?X ((?X . ?Y))) 3: (UNIFY ?Y ?Y ((?X . ?Y))) 3: returned ((?X . ?Y)) 2: returned ((?X . ?Y)) 2: (UNIFY (A) (?X) ((?X . ?Y))) 3: (UNIFY A ?X ((?X . ?Y))) 4: (UNIFY ?Y A ((?X . ?Y))) 4: returned ((?Y . A) (?X . ?Y)) 3: returned ((?Y . A) (?X . ?Y)) 3: (UNIFY NIL NIL ((?Y . A) (?X . ?Y))) 3: returned ((?Y . A) (?X . ?Y)) 2: returned ((?Y . A) (?X . ?Y)) 1: returned ((?Y . A) (?X . ?Y)) 0: returned ((?Y . A) (?X . ?Y)) ((?Y . A) (?X . ?Y))このような結果になる. では,最初の3つの変数による循環ではどうなるかを 調べてみると,
<cl> (unify '(?x ?y ?z a) '(?y ?z ?x ?x)) 0: (UNIFY (?X ?Y ?Z A) (?Y ?Z ?X ?X)) 1: (UNIFY ?X ?Y NIL) 1: returned ((?X . ?Y)) 1: (UNIFY (?Y ?Z A) (?Z ?X ?X) ((?X . ?Y))) 2: (UNIFY ?Y ?Z ((?X . ?Y))) 2: returned ((?Y . ?Z) (?X . ?Y)) 2: (UNIFY (?Z A) (?X ?X) ((?Y . ?Z) (?X . ?Y))) 3: (UNIFY ?Z ?X ((?Y . ?Z) (?X . ?Y))) 4: (UNIFY ?Z ?Y ((?Y . ?Z) (?X . ?Y))) 5: (UNIFY ?Z ?Z ((?Y . ?Z) (?X . ?Y))) 5: returned ((?Y . ?Z) (?X . ?Y)) 4: returned ((?Y . ?Z) (?X . ?Y)) 3: returned ((?Y . ?Z) (?X . ?Y)) 3: (UNIFY (A) (?X) ((?Y . ?Z) (?X . ?Y))) 4: (UNIFY A ?X ((?Y . ?Z) (?X . ?Y))) 5: (UNIFY ?Y A ((?Y . ?Z) (?X . ?Y))) 6: (UNIFY ?Z A ((?Y . ?Z) (?X . ?Y))) 6: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) 5: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) 4: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) 4: (UNIFY NIL NIL ((?Z . A) (?Y . ?Z) (?X . ?Y))) 4: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) 3: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) 2: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) 1: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) 0: returned ((?Z . A) (?Y . ?Z) (?X . ?Y)) ((?Z . A) (?Y . ?Z) (?X . ?Y))となる. トレースモードを止めるのは,untraceである.
<cl> (untrace unify) (UNIFY) <cl> (unify '(?x ?y ?z a) '(?y ?z ?x ?x)) ((?Z . A) (?Y . ?Z) (?X . ?Y))