next up previous
Next: 3.3 同一変数を内部に含むパターンとのバインディングの場合 Up: 3 変数を含むパターン同士のマッチングUnifyの定義 Previous: 3.1 同一変数のバインディングが起こる場合

3.2 変数のバインディングが循環する場合

しかし,
<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))


generated through LaTeX2HTML. M.Inaba 平成18年5月7日