<cl> (unify '?x '(f ?x)) ((?X F ?X)) <cl> (unify '(?x ?x) '(?y (f ?y))) ((?Y F ?Y) (?X . ?Y))という場合も問題で,FAILを返す必要があります. そこで,データの中にその変数が入っているかどうかを 調べる occur-check を行なう.
(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)) ((occurs-check p d bindings) 'fail) (t (add-binding p d bindings)))) (defun occurs-check (v x bindings) (cond ((eq v x) t) ((and (variable-p x) (get-binding x bindings)) (occurs-check v (lookup x bindings) bindings)) ((consp x) (or (occurs-check v (car x) bindings) (occurs-check v (cdr x) bindings))) (t nil)))これを用いると,
<cl> (unify '?x '(f ?x)) FAIL <cl> (unify '(?x ?x) '(?y (f ?y))) FAILのようにマッチングされなくなる.