next up previous
Next: 3.2 変数のバインディングが循環する場合 Up: 3 変数を含むパターン同士のマッチングUnifyの定義 Previous: 3 変数を含むパターン同士のマッチングUnifyの定義

3.1 同一変数のバインディングが起こる場合

<cl> (unify '(?x ?x) '(?y ?y))
((?Y . ?Y) (?X . ?Y)) 
<cl> (unify '(?x ?x ?x) '(?y ?y ?y))
Error: Received signal number 2 (Keyboard interrupt)

Restart actions (select using :continue):
 0: continue computation
[1c] <cl>
これは,?yが自分自身とマッチしてしまうという(?y . ?y)というバインディ ング情報があるために,unify-variableの中で無限ループになってしまうから である.そこで,
(defun unify-variable (p d bindings)
  (cond
   ((eql p d) bindings)
   ((get-binding p bindings)
    (unify (lookup p bindings) d bindings))
   (t (add-binding p d bindings))))
という具合にp と dが同じであればunifyしないようにすると,
<cl> (unify '(?x ?x) '(?y ?y))
((?X . ?Y)) 
<cl> (unify '(?x ?x ?x) '(?y ?y ?y))
((?X . ?Y)) 
<cl> (unify '(?x ?x ?x a) '(?y ?y ?y ?y))
((?Y . A) (?X . ?Y))
という具合に無限ループにならなくなる.

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