「lisp勉強１０日目ユニフィケーション」の編集履歴（バックアップ）一覧はこちら

「lisp勉強１０日目ユニフィケーション」(2012/08/11 (土) 19:04:39) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

<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>

<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>