<p><a href="http://www.geocities.jp/m_hiroi/xyzzy_lisp/abclisp23.html">http://www.geocities.jp/m_hiroi/xyzzy_lisp/abclisp23.html</a></p> <p>変数のユニフィケーションについてリンク先で勉強。</p> <p>リンク先コードで私が理解できた範囲のコメントを記述。</p> <p>変数の統合は色々なパタンを考えると意外と難しそう。</p> <p> </p> <p> </p> <div>; unify.l : ユニフィケーション</div> <div>;</div> <div>; Copyright (C) 2003 Makoto Hiroi</div> <div>;</div> <div> </div> <div>;</div> <div>; 要素はパターン変数か</div> <div>; </div> <div>(defun variablep (pattern)</div> <div> (and (symbolp pattern)</div> <div> (char= #\? (char (string pattern) 0))));束縛変数だった</div> <div>variablep</div> <div> </div> <div>(defun add-binding (var value binding)</div> <div> (cons (cons var value) binding));束縛変数のkeyとvalueを追加</div> <div>add-binding</div> <div> </div> <div>;</div> <div>; ユニフィケーション</div> <div>;</div> <div>(defun unify (pattern datum binding)</div> <div> (cond ((variablep pattern);束縛変数一つだったら</div> <div> (unify-variable pattern datum binding));束縛変数がいままで出てきたものだったらvalueにしてからこの関数に帰ってくる</div> <div> ((variablep datum)</div> <div> (unify-variable datum pattern binding));同じく束縛変数をvalueにしてからこの関数に帰ってくる</div> <div> ((and (atom pattern) (atom datum))</div> <div> (unify-atoms pattern datum binding));アトムになったので普通に変数として比較</div> <div> ((and (consp pattern) (consp datum))</div> <div> (unify-pieces pattern datum binding));まだリストなのでアトムになるまで分解していく</div> <div> (t 'fail)))</div> <div>unify</div> <div> </div> <div> </div> <div>;</div> <div>; アトムとのユニフィケーション</div> <div>;</div> <div>(defun unify-atoms (pattern datum binding)</div> <div> (if (equal pattern datum) binding 'fail));比較したアトムが同じなら駄目</div> <div>unify-atoms</div> <div> </div> <div> </div> <div>;</div> <div>; リストのユニフィケーション</div> <div>;</div> <div>(defun unify-pieces (pattern datum binding)</div> <div> (let ((result (unify (car pattern) (car datum) binding)));ここでcar patternとcar datumで一つのアトムにまで分解する作業を続ける</div> <div> (if (eq result 'fail)</div> <div> 'fail</div> <div> (unify (cdr pattern) (cdr datum) result))));アトムの分解が終わったのでリストの次へ移動する</div> <div>unify-pieces</div> <div> </div> <div> </div> <div>;</div> <div>; 変数とのユニフィケーション</div> <div>;</div> <div>(defun unify-variable (pattern datum binding);関数の呼び出し場所でこの関数のpatternは束縛変数一個になることが保証</div> <div> (let ((value (assoc pattern binding)));でてきた束縛変数が今まで出てきたものと同じか調べる</div> <div> (if (and value</div> <div> (not (eq pattern (cdr value))));今まで出てきた束縛変数と同じだった</div> <div> (unify (cdr value) datum binding);束縛変数を具体的な値にして再度unifyを実行</div> <div> (if (insidep pattern datum binding);束縛変数が残りのリストで出てこないことをチェック</div> <div> 'fail</div> <div> (add-binding pattern datum binding)))));出てこなかったので追加</div> <div>unify-variable</div> <div> </div> <div> </div> <div>;</div> <div>; datum の中に var があるか</div> <div>;</div> <div>(defun insidep (var datum binding)</div> <div> (unless (eq var datum);変数の統合が目的なので同じ束縛変数は無視する</div> <div> (inside-sub-p var datum binding)))</div> <div>insidep</div> <div> </div> <div> </div> <div>;</div> <div>; insidep 本体</div> <div>;</div> <div>(defun inside-sub-p (var datum binding);この関数はチェックしか行わなわず他の関数と関係を持たない</div> <div> (cond ((eq var datum) t);同じ変数ならユニフィケーションする意味がない</div> <div> ((atom datum) nil);nilまで分解したのでnilを返す</div> <div> ((variablep datum);datumがアトムにまで分解されこれが束縛変数だった</div> <div> (let ((value (assoc datum binding)));datumは束縛変数になっているので探す</div> <div> (if value</div> <div> (inside-sub-p var (cdr value) binding))));束縛変数に対応するvalueを返す</div> <div> (t</div> <div> (or (inside-sub-p var (car datum) binding);datumをアトムになるまで分解しリストの残り全部と変数を照合する</div> <div> (inside-sub-p var (cdr datum) binding)))))</div> <div>inside-sub-p</div> <div> </div>