簡易エキスパートシステムの作成 (前編)
今回は 記号のパターンマッチング の応用例として、簡単なエキスパートシステムを作成してみましょう。
●エキスパートシステムと Prolog
エキスパートシステムとは、専門家の知識をコンピュータに記憶しておき、それを使って問題を解決する、あるいは問題解決のための手助けを行うように作られたシステムです。ここで作成するプログラムは、このような難しいシステムではありません。「パターンマッチングとバックトラックを組み合わせることでデータの中から解答を導き出す」という簡単なものです。
実をいうと、パターンマッチングとバックトラックを機能に持つプログラミング言語に Prolog があります。簡易システムとはいっても、Prolog とよく似た動作をさせることは可能です。逆に言えば、Prolog の動作はこれから作成する簡易エキスパートシステムの参考になるものです。解を求めるときのパターンマッチングとバックトラックの動作はどちらも同じです。
まずは最初に Prolog を例にして、パターンマッチングとバックトラックの動作を簡単に説明します。
●Prolog とは？
Prolog は 1971年フランスのマルセイユ大学の Alain Colmeraur によって開発されたプログラミング言語です。日本で行われた第五世代コンピュータプロジェクトで、中核となるプログラミング言語として採用され一躍有名になりました。Ｃ言語や BASIC が手続き型言語、Lisp が関数型言語と呼ばれているのに対し、Prolog は論理型言語と呼ばれています。これは Prolog の計算の仕組みが、論理学を基礎にして成り立っているからです。
Prolog は物事の間に成り立つ関係を定義していくことでプログラムを作成します。そして、もっとも基本的な関係を表したものを「事実 (fact)」といいます。Prolog のプログラムは、この事実関係を問い合わせることで動作します。すなわち、Prolog は今まで定義された事実を参照して、与えられた質問の答を導き出す言語、といってもいいでしょう。たとえば、「太郎はコーヒーが好きである」という関係があると、次の質問に答えることができます。
だれがコーヒーを好きか？ => 太郎 太郎はなにが好きか？ => コーヒー
実際には、このような日本語を使ってプログラムできないので、文章の中の「述語 (predicate)」を中心にして、事実を次のように表します。
好き(太郎, コーヒー).
これはエジンバラ Prolog という処理系 [*1] での表現方法です。ほかの例も示しましょう。
「太郎はココアが好き」 --> 好き(太郎, ココア). 「花子は紅茶が好き」 --> 好き(花子, 紅茶).
このように、関係を示す言葉をいちばん前に持ってきて表現する方法を「述語表記」といい、後ろに続く言葉を「引数」といいます。最後のピリオドを除けばＣ言語の関数と形はよく似ていますね。
それでは、実際に今まで出た例を Prolog に入力してみます。
| 好き( 太郎, コーヒー).
| は Prolog インタプリタのプロンプト [*2] を表しています。入力した事実は Prolog 内にあるデータベースに格納されます。それでは、太郎がコーヒーを好きかたずねてみましょう。質問する場合は ?- を使います。
| ?-好き(太郎, コーヒー). yes
まあ、これは当たり前ですね。では、花子は紅茶が好きか、たずねてみましょう。
| ?-好き(花子, 紅茶). no
これは「花子は紅茶が好きである」という事実がないので、Prolog は違うといってきたのです。では、定義してみましょう。
| 好き(花子, 紅茶). | ?-好き(花子, 紅茶). yes
今度は、そうだよといってきました。
ある事実に対して yes か no しかたずねることができないのであれば面白くありませんね。事実が増えてくると、たとえば太郎が好きなものは何かとか、コーヒーを好きな人は誰か、といった質問をしたいと思うでしょう。
もちろん、Prolog はそのような質問を受け付けることができます。そのためには「変数」を使います。Prolog の変数はパターンマッチングのパターン変数と同じ働きをします。エジンバラ Prolog では、半角英大文字から始まる名前を変数として扱います。
- 【変数の例】 X Y Z Prolog Lisp Abc
- 【名前の例】 x y z prolog lisp abc
Prolog には次の事実が入力されているものとします。
- 好き(太郎, コーヒー).
- 好き(花子, 紅茶).
- 好き(太郎, ココア).
太郎が好きなものは何か質問してみましょう。
| ?-好き(太郎, X). X = コーヒー ->
-> はほかの解答を調べるか、Prolog がたずねていることを示す記号です。ここで ; を入力すると、Prolog は別の解答を探します。
それでは、別の解があるか調べてみましょう。
X = コーヒー -> ; X = ココア -> ; no
Prolog の変数はパターン変数と同様に複数使うこともできます。好き(X, Y). と質問すれば、「好き」という関係をもつすべての事実を求めることができます。ただし、述語の部分を変数にすることはできません。
| ?-好き(X, Y). X = 太郎 Y = コーヒー -> ; X = 花子 Y = 紅茶 -> ; X = 太郎 Y = ココア -> ; no
別解を求める場合は代入された変数を未束縛の状態に戻します。そして次に定義されている事実とマッチングを行います。つまり、バックトラックすることでデータベース全体を検索するわけです。
[*1] イギリスのエジンバラ大学で作られた処理系で Prolog の標準とされています。
[*2] プロンプトは Prolog 処理系によって違います。 Prolog Programming で使っている SWI-Prolog の場合、質問を受け付けるプロンプト ?- が表示されます。この場合、事実をそのまま入力することはできません。ご注意くださいませ。
●Prolog のプログラムとは？
Prolog は複数の事実を用いてひとつの事実を表すことができます。これを「規則 (rule)」といいます。一般に規則は次のような形をとります。
head :- goal1, goal2, ... goalN.
これは goal1 から goalN までの規則がすべて成り立てば規則 head が成立する、ということを表します。つまり、規則を「～かつ～」で結びつけているのです。先頭の head を「頭部」といい、残りの goal をまとめて「体部」といいます。また、各々の goal を「ゴール」といいます。そして、事実、規則および質問のことをまとめて「節 (clause)」と呼びます。簡単な例を示します。
| 飛ぶ(X) :- 飛行機(X). | 飛行機(ジェット機). | 飛行機(ヘリコプター).
最初の節は「飛行機は空を飛ぶ」という規則を表しています。次の 2 つの節は、「ジェット機は飛行機である」と「ヘリコプターは飛行機である」という事実を表しています。このことから、「ジェット機は空を飛ぶ」という結論を導くことができます。では、Prolog に質問してみましょう。
| ?-飛ぶ(ジェット機). yes
それでは、太郎君は空を飛べるか質問してみましょう。
| ?-飛ぶ(太郎). no
太郎君は空を飛べません。ところで、空を飛べるのは飛行機だけではありません。スーパーマンも空を飛べますね。実は、太郎君はなんとスーパーマンだったのです。その規則を追加しましょう。
| 飛ぶ(X) :- スーパーマン(X). | スーパーマン(太郎).
もう一度、太郎君が飛べるか質問してみます。
| ?-飛ぶ(太郎). yes
太郎君は空を飛ぶことができました。変数を使うと、空を飛べるものがすべてわかります。
| ?-飛ぶ(Y). Y = ジェット機 -> ; Y = ヘリコプター -> ; Y = 太郎 -> ; no
それでは、Prolog の動作を詳細に追いかけてみましょう。
まず質問と節の頭部をパターンマッチングし、それに成功する節を選びます。この例では 飛ぶ(Y) と 飛ぶ(X) がパターンマッチングに成功します。変数を含むパターン同士のマッチングですから、ユニフィケーションが行われるわけです。これにより変数 Y と X が関連付けられます。
次に、体部の実行に移ります。体部の実行はゴールを順番に質問していくことと同じです。この場合、飛行機(X) が実行され、これとパターンマッチングする節が選択されます。その結果、飛行機(ジェット機) とマッチングし、変数 X は「ジェット機」という値になります。
選択された節は事実なので、実行する体部はありません。元の節に戻りますが、次に実行するゴールはないので、この節が成功したことになります。したがって、飛ぶ(X) は成功するのです。そのあと、質問の節に戻り、Y は X とマッチングしているので、 その値が「ジェット機」となります。
次は、別解を探索する動作を説明しましょう。Prolog では、別解を探索することを「再試行」といいます。再試行する場合、いちばん最後に実行したゴールから行われます。このとき、束縛された変数は自由変数に戻されることに注意してください。
最初に、飛行機(X) が再試行されます。まず、変数 X が自由変数に戻されます。飛行機(X) の実行によって束縛された変数を自由変数に戻すのであって、それ以前に束縛された変数は自由変数に戻しません。
そして、飛行機(X) とマッチングする節を再度探索します。このとき、すでにマッチングした 飛行機(ジェット機) は探索の対象から外されます。今度は 飛行機(ヘリコプター) とマッチングしました。X の値は「ヘリコプター」に定まります。飛ぶ(X) が成功したので、この再試行も成功です。Y = ヘリコプター という結果になります。
もう一度、再試行しましょう。飛行機(X) を実行するですが、これ以上事実は定義されていません。したがって、飛行機(X) は失敗します。失敗した場合は、ひとつ前のゴールを再試行します。すべてのゴールの再試行に失敗したら、その節は失敗となります。この場合、再試行するゴールはありませんので、規則 飛ぶ(X) :- 飛行機(X). が失敗します。
節が失敗した場合は、その節を呼び出した節を再試行します。この場合、質問 飛ぶ(Y) を再試行します。飛ぶ(Y) とマッチングする節を探すと、飛ぶ(X) :- スーパーマン(X). が見つかります。今度は、この節を実行します。同じようにゴールを実行して、「太郎」という答えが見つかります。
さらに再試行します。まず、スーパーマン(X) を再試行しますが、マッチングする節が見つかりません。規則飛ぶ(X) :- スーパーマン(X). は失敗します。そして、質問 ?-飛ぶ(Y). を再試行しますが、もはやマッチングする節はありません。飛ぶ(Y) は失敗します。飛ぶ(Y) は質問でしたから no という結果が表示されます。
これが Prolog の基本的な動作です。これから作成する「簡易エキスパートシステム」は、Prolog と同様にパターンマッチングとバックトラックによって解を探索します。
●パターンマッチングからエキスパートシステムへ
それでは、Prolog の動作を参考に簡易エキスパートシステムを作成しましょう。Prolog では「述語(引数, ..., 引数).」で事実を定義しましたが、これをそのまま Lisp で実現するのは面倒です。そこで、リストを使って次のように表します。
(述語 引数 ... 引数)
このほうがパターンマッチングをそのまま適用できるので都合がよいのです。述語はパターン変数以外のシンボルで表します。引数は、シンボル、パターン変数、数値、リストとします。それから、今後はパターン変数をたんに「変数」と書くことにします。
次に規則ですが、Prolog では「head :- goal1, goal2, ... goalN.」と表しましたが、これも単純なリストで表すことにします。
(head goal1 goal2 ... goalN)
リストの先頭が頭部となり、残りが体部となります。ただし、このままでは事実と規則の区別がつかなくなるので、事実と規則を次のように表すことにします。
- 事実 : ((述語 引数 ... 引数))
- 規則 : ((述語 引数 ... 引数) (述語 引数 ... 引数) ... )
このように、(head) のみの規則を事実とすることにします。
事実と規則は簡単に取り出せるように、頭部の述語の属性リストに格納することにします。属性名は RULE とします。
●変数の管理方法
次に、変数について詳しく検討してみます。ここで注意してもらいたいのが変数の有効範囲です。Prolog の場合、変数は同じ節内でのみ有効です。つまり、局所変数として扱われるのです。このため、Prolog では再帰呼び出しも可能です。たとえば、前回の質問 ?-飛ぶ(Y). の変数を X に変えてみます。
規則 飛ぶ(X) :- 飛行機(X). の変数 X は同じ変数です。ところが、この変数と質問 ?-飛ぶ(X). の X は、名前は同じですが別の変数として扱われるのです。したがって、前回と同じように答えを求めることができます。
このように、Prolog で行われるパターンマッチングは、同じ名前であっても別の変数として扱うため、厳密な意味でのユニフィケーションを必要としません。関数 unify では、同一変数のチェックを insidep で行いましたが、この処理は不要になります。
ところが、いいことだけではありません。今度は変数の管理方法が問題になるのです。記号のパターンマッチング で作成したユニフィケーションは、変数名 (シンボル) が同じであれば節が異なっていても同じ変数として扱います。これは一般的なユニフィケーションでは当然のことなのですが、今回のようなエキスパートシステムとはあまり相性がよくありません。
ですが、心配は無用です。とても簡単な方法で回避することができます。それは、節によって異なるシンボルを使用し、変数名が重ならないようにすることです。節を属性リストに登録するとき、変数を新しいシンボルに置換することにしましょう。
Common Lisp には、パッケージ (package) に登録しないシンボルを生成する関数 gensym があります。
gensym &optional x
Common Lisp の場合、シンボルはパッケージで管理されます。パッケージの説明は拙作のページ パッケージの基本的な使い方 をお読みくださいませ。
gensym は新しいシンボルを生成しますが、そのシンボルはパッケージに登録されません。このようなシンボルを「unintern されたシンボル」とか「uninterned なシンボル」といいます。シンボル名は新しく生成され、'G' とそのあとに 10 進数の数字が続きます。
簡単な使用例を示しましょう。
* (setq a (gensym)) #:G392 * (eq a 'g392) NIL
#: は unintern されたシンボルであることを示します。シンボル G392 はパッケージに登録されますが、#:G392 はパッケージに登録されていないので、2 つのシンボルは異なります。したがって、eq で比較しても NIL となります。
このように unintern されたシンボルは、それ以前の S 式で使われているシンボルとは異なります。したがって、節内の変数をこのシンボルで置き換えれば、ほかの節で使う変数と衝突することはなくなります。
また、オプションパラメータ x に文字列を与えるとシンボル名を変更することができます。
* (gensym "?") #:?393
このように、変数の条件を満たすシンボルを生成することができます。Common Lisp には gensym のほかにも unintern されたシンボルを生成する関数があります。
copy-symbol symbol &optional copy-props make-symbol string
copy-symbol は引数 symbol と同じ名前の unintern されたシンボルを生成します。オプションパラメータ copy-props が真ならば、新しいシンボルの初期値と関数定義は symbol と同じになり、属性リストもコピーされます。
make-symbol は unintern されたシンボルを生成します。シンボルの名前は引数の string で指定します。値と関数定義は未定義のままで、属性リストは空の状態です。簡単な使用例を示しましょう。
* (setq a (copy-symbol 'bar)) #:BAR * (setq b (copy-symbol 'bar)) #:BAR * (eq a 'bar) NIL * (eq b 'bar) NIL * (eq a b) NIL * (setq a (make-symbol "FOO")) #:FOO * (setq b (make-symbol "FOO")) #:FOO * (eq a 'foo) NIL * (eq b 'foo) NIL * (eq a b) NIL
このように、copy-symbol や make-symbol でも unintern されたシンボルを生成することができます。
ところが、節の変数を変えるだけではまだ不十分なのです。再帰呼び出しが行われると同じ節を呼び出すことになり、そこで変数の衝突が発生するからです。これを回避するため、ユニフィケーションを行うところで、節の変数を置き換えることにします。
この方法だと、再帰呼び出しが行われるたびに新しい変数に置き変わるのでうまく動作します。欠点として、ユニフィケーションを行うたびに変数を置換するので、実行速度が遅くなることです。ここは実行速度よりも、簡単に作れる方法を選ぶことにしましょう。
変数の置き換えは リスト操作関数 で説明した関数 sublis を使うと簡単です。まず、節内で使われている変数を集めます。この関数を collect-variable としましょう。
(collect-variable '((foo ?x ?y) (bar1 ?x) (bar2 ?y))) => (?x ?y)
次に、この変数と gensym で生成するシンボルの連想リストを作ります。これは mapcar を使えば簡単です。
(mapcar (lambda (x) (cons x (gensym "?"))) '(?x ?y)) => ((?x . #:?1) (?y . #:?2))
あとは、この連想リストと節を sublis に渡せばいいのです。
(sublis '((?x . #:?1) (?y . #:?2)) '((foo ?x ?y) (bar1 ?x) (bar2 ?y))) => ((foo #:?1 #:?2) (bar1 #:?1) (bar2 #:?2))
実際のプログラムは節を定義するところで作ります。
●バックトラックの管理
次は簡易エキスパートシステムの動作について考えてみます。box モデルという Prolog の動作を表す方法を使うとわかりやすいと思います。次の図を見てください。
box モデルは実行中の節をボックスとし、その状態を Call, Redo, Exit, Fail で表します。節が初めて実行されることを Call といいます。このときにボックスが作られます。成功した場合を Exit といい、再試行した場合を Redo といいます。失敗した場合を Fail といい、このときボックスが破壊されます。このボックスに必要な情報を保存しておくことでバックトラックが可能になります。
それでは、このボックスに対応する構造体を作りましょう。名前は実行環境を格納することから ENV としました。
リスト : 実行環境の定義 (defstruct env goal ; ゴール節 rule-list ; 述語に定義されている規則 exec-rule ; 実行中の規則 exec-env ; 作成した環境（スタックになる） binding ; 束縛リスト prev-binding) ; Env を作成したときの束縛リスト
GOAL は実行する節が入ります。これとマッチングする節を RULE-LIST から探します。RULE-LIST は ENV の実体を生成するときに、述語の属性リストから節を取り出してセットします。EXEC-RULE は現在実行中の節をセットします。RULE-LIST でマッチングした節は、そこから取り出して EXEC-RULEにセットします。これで、バックトラックした場合でも、同じ節が再び使われることはありません。
EXEC-ENV は、規則の体部を実行するために生成した環境 ENV の実体をリストに格納します。したがって、環境 ENV は「木構造」になるわけです。つまり、エキスパートシステムが動作することにより ENV の木構造が生成され、再試行のときには作られた木構造をたどることで動作するわけです。EXEC-ENV はスタックとして動作させるので、環境は実行した順番とは逆に格納されていきます。再試行のときには EXEC-ENV の第 1 要素が、その節で最後に実行された環境となります。
ENV のオブジェクトを生成するとき、その時点で有効な束縛リストを PREV-BINDING にセットし、この束縛リストを使ってユニフィケーションを行います。ユニフィケーションが成功した場合、関数 unify は新しく束縛された変数を束縛リストに追加して返すので、それを BINDING にセットします。再試行するときは、PREV-BINDING の束縛リストを使うだけで、この環境で束縛された変数をクリアする (束縛リストから削除する) ことができます。
実際にどのような動作になるか、次の事実と規則を使って具体的に説明します。
- 事実 1 : ((foo a)), ((foo b))
- 事実 2 : ((bar a)), ((bar b))
- 規則 : ((foo1 ?x ?y) (foo ?x) (bar ?y))
まず、質問として (foo1 ?a ?b) が与えられると、それを解くために env0 が生成されます。
env0 goal : (foo1 ?a ?b) rule-list : ( ((foo1 ?x ?y) (foo ?x) (bar ?y)) ) exec-rule : nil exec-env : nil binding : nil prev-binding : nil
GOAL には質問 (foo1 ?a ?b) がセットされ、foo1 の属性リストから属性 RULE に格納されている節がセットされます。次に、GOAL と頭部がマッチングする節を RULE-LIST の中から探します。この場合、節はひとつしかないですが、それがマッチングします。env0 は次のようになります。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : nil binding : ((?a . ?x) (?b . ?y)) prev-binding : nil
マッチングした節は EXEC-RULE にセットされ、RULE-LIST から削除されます。そして、束縛リストを BINDING にセットします。ここで、変数 ?a と ?x, ?b と ?y のリンケージがセットされます。
次に、規則の体部を実行します。まず、(foo ?x) を実行するため新しい環境 env1 を作り EXEC-ENV にセットします。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : (env1) binding : ((?a . ?x) (?b . ?y)) prev-binding : nil env1 goal : (foo ?x) : (foo ?x) rule-list : ( ((foo a)) ((foo b)) ) : ( ((foo b) ) exec-rule : nil => : ((foo a)) exec-env : nil : nil binding : nil : ((?x . a) (?a . ?x) (?b . ?y)) prev-binding : ((?a . ?x) (?b . ?y))
env1 は (foo ?x) が GOAL なので、述語 FOO から節を取り出して RULE-LIST にセットします。あとは、この中から GOAL とマッチングする節を探します。その結果、((foo a)) が EXEC-RULE にセットされて、?x は a に束縛されます。この場合、体部がないので (foo ?x) はマッチング成功となります。
env1 が成功したので env0 に戻り、次の (bar ?y) を実行します。ここでも環境 env2 を作り EXEC-ENV に追加します。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : (env2 env1) binding : ((?a . ?x) (?b . ?y)) prev-binding : nil env2 goal : (bar ?y) : (bar ?y) rule-list : ( ((bar a)) ((bar b)) ) : ( ((bar b)) ) exec-rule : nil => : ((bar a)) exec-env : nil : nil binding : nil : ((?y . a) (?x . a) (?a . ?x) (?b . ?y)) prev-binding : ((?x . a) (?a . ?x) (?b . ?y))
env2 の動作は env1 と同じです。その結果、(bar ?y) のマッチングは成功し、?y は a に束縛されます。そのあと env0 に戻りますが、このあとに実行する体部はありませんので、この規則はマッチング成功となります。したがって、?a = a, ?b = a という結果が得られます。これを box で表すと次のようになります。
プログラムの実行が進むにつれ、ボックスが生成されていくことがわかると思います。
次に、再試行する様子を見てみましょう。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : (env2 env1) binding : ((?a . ?x) (?b . ?y)) prev-binding : nil
env0 の exec-env から env2 へ移動します。exec-env はスタックと同じ動作なので、先頭にある環境が最後に実行した環境となります。
env2 goal : (bar ?y) : (bar ?y) rule-list : ( ((bar b)) ) : nil exec-rule : ((bar a)) => : ((bar b)) exec-env : nil : nil binding : ((?y . a) (?x . a) (?a . ?x) (?b . ?y)) : ((?y . b) (?x . a) (?a . ?x) (?b . ?y)) prev-binding : ((?x . a) (?a . ?x) (?b . ?y)) : ((?x . a) (?a . ?x) (?b . ?y))
env2 の EXEC-ENV は nil なので、これ以上たどるべき環境はありません。そこで、PREV-BINDING の状態で goal とマッチングする節を rule-list から探します。すると、((bar b)) とマッチングが成功し、?y は b に束縛されます。
env2 がマッチング成功したので env0 に戻り、この結果 Env0 もマッチング成功となります。その結果、?a = a, ?b = b と表示されます。これを box モデルで表すと、次のようになります。
この場合は env2 で別解を見つけることができました。それでは、もう一度再試行します。この場合も先ほどと同様に env0 から再試行します。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : (env2 env1) binding : ((?a . ?x) (?b . ?y)) prev-binding : nil env2 goal : (bar ?y) rule-list : nil exec-rule : ((bar b)) => 失敗！ exec-env : nil binding : ((?y . b) (?x . a) (?a . ?x) (?b . ?y)) prev-binding : ((?x . a) (?a . ?x) (?b . ?y))
env2 の EXEC-ENV は NIL なので、これ以上たどるべき環境はありません。そこで、GOAL とマッチングする節を RULE-LIST から探します。ところが、RULE-LIST は空リスト NIL なので探索する節はありません。env2 は失敗します。そこで env0 に戻ります。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : (env1) binding : ((?a . ?x) (?b . ?y)) prev-binding : nil
env0 では EXEX-ENV から失敗した env2 を削除し、残っている環境 env1 に移動します。これを box モデルで表すと、次のようになります。
失敗した box は消滅してバックトラックするわけです。では、続きの様子を見てみます。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : (env1) binding : ((?a . ?x) (?b . ?y)) prev-binding : nil env1 goal : (foo ?x) : (foo ?x) rule-list : ( ((foo b) ) : nil exec-rule : ((foo a)) => : ((foo b)) exec-env : nil : nil binding : ((?x . a) (?a . ?x) (?b . ?y)) : ((?x . b) (?a . ?x) (?b . ?y)) prev-binding : ((?a . ?x) (?b . ?y)) : ((?a . ?x) (?b . ?y))
env1 の EXEC-ENV は NIL なので、これ以上たどるべき環境はありません。そこで、GOAL とマッチングする節を RULE-LIST から探します。すると、((foo b)) とマッチングが成功し、?x は b に束縛されます。
env1 がマッチング成功したので env0 に戻り、次の体部 (bar ?y) を実行します。この場合、環境 env2 を新しく作ることに注意してください。
env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) exec-env : (env2 env1) binding : ((?a . ?x) (?b . ?y)) prev-binding : nil env2 goal : (bar ?y) : (bar ?y) rule-list : ( ((bar a)) ((bar b)) ) : ( ((bar b)) ) exec-rule : nil => : ((bar a)) exec-env : nil : nil binding : nil : ((?y . a) (?x . a) (?a . ?x) (?b . ?y)) prev-binding : ((?x . a) (?a . ?x) (?b . ?y))
Env2 は新しく作られる環境なので、rule-list には述語 foo の属性リストから節がセットされます。以前実行した環境とは違うことに注意してください。環境は違いますが、動作は同じです。box モデルを見てください。
env1 が成功し、新しい box である env2 が生成されます。そこで、(bar ?y) のマッチングが行われ、その結果 ?y が a に束縛されるので、?a = b, ?b = a になります。ここで再試行すると、env2 で別解が求められ、?a = b, ?b = b になります。この場合は、env2 の再試行だけですので簡単ですね。次が最後の再試行になります。
env2 の RULE-LIST は空なので再試行は失敗します。そこで、env0 の EXEC-ENV から env2 を削除し、env1 へバックトラックします。しかし、env1 の RULE-LIST も空なので、ここでも再試行に失敗します。その結果、env0 では env1 を EXEC-ENV から削除します。すると、EXEC-ENV は空リスト NIL になるので、これ以上バックトラックする環境がなくなります。
Env0 goal : (foo1 ?a ?b) rule-list : nil exec-rule : ((foo1 ?x ?y) (foo ?x) (bar ?y)) => 失敗 exec-env : nil binding : ((?a . ?x) (?b . ?y)) prev-binding : nil
そこで、goal とマッチングする規則を RULE-LIST から探すのですが、RULE-LIST は空リスト NIL ですね。その結果、env0 はマッチング失敗となるのです。これを box モデルで表すと、次のようになります。
再試行しましたが、env2 では別解が見つからず Fail となりました。次に env1 が再試行されましたが、これも別解が見つからず Fail となりました。最後に env0 に戻りますが、これ以上再試行する節がないので Fail となるのです。