Next: 3.3 同一変数を内部に含むパターンとのバインディングの場合
Up: 3 変数を含むパターン同士のマッチングUnifyの定義
Previous: 3.1 同一変数のバインディングが起こる場合
しかし，
<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))
このような結果になる．
では，最初の３つの変数による循環ではどうなるかを
調べてみると，
<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))
generated through LaTeX2HTML. M.Inaba 平成18年5月7日