プログラムの実行順序

次のような節を考えてください。

          p :- p.

前に宣言的意味と手続き的意味をやりました。この節の宣言的意味というのは「ｐが真ならば、ｐは真である」です。これは宣言としては正しいですね。しかし、手続き的には無意味です。「ｐが真ならば、ｐは真である」とすると、その条件部の「ｐが真ならば」はいつ、真かどうか判定されるのでしょうか。例えば、

          ?- p.

と入力したとしましょう。目標ｐは上の節により、副目標ｐに置き換えられます。これが、また更にｐに置き換えられることになります。Ｐｒｏｌｏｇは延々ｐをｐに置き換え続け、無限ループに陥ります。

上に示したのは、Ｐｒｏｌｏｇを無限ループに陥らせる最も簡単な方法です。これは考えれば、すぐにわかりますから「うっかり」こういうプログラムを組むことはまずないと思います。しかし、ちょっと複雑なプログラムだと注意しないと「うっかり」しがちです。

さて、前章で扱った「猿バナナ」はどうでしょうか。

7.1 猿はうろうろ歩き回る...

「猿バナナ」のプログラムではchange関係の節はgrasp,climb,push,walkの順に記述されていました。（完全を期すためにはunclimbを加えるべきでしょうね）この順序が変わるとどうなるでしょう。walkの節が一番最初に書かれていると仮定して、前章で考えた最初の目標

          ?- getbanana(state(a,floor,c,empty)).

を再び考えてみましょう。さて、探索の過程はどのようになるでしょうか。

初期目標

          getbanana(state(a,floor,c,empty)).

getbananaの２番目の節を適用して、副目標は

          change(Operate,
                 state(a,floor,c,empty),
                 State2),
          getbanana(State2).

となる。

stateの各成分の値により適用できるのはwalkのあるchange節であるから、ここでOperateにwalk(a,Place2)を適用して、

          change(walk(a,Place2),
                 state(a,floor,c,empty),
                 state(Place2,floor,c,empty)),
          getbanana(state(Place2,floor,c,empty)).

となる。

change関係に関してはＰｌａｃｅ２を除いて解決したから、Ｐｌａｃｅ２の値は保留のまま、getbananaを考える。
もう一度、getbananaの２番目の節を適用して
```
          change(Operate',
                 state(Place2,floor,c,empty),
                 State2'),
          getbanana(State2').
```
となる。ここまでは、前章と同じである。前章では、ここでclimbを適用して失敗し、pushを適用して目標状態へ遷移した。しかし、今回はchange節の最初にwalkがあるので、ここでwalkを適用する。Operate'にwalk(Place2,Place2')を適用すると
```
          change(walk(Place2,Place2'),
                 state(Place2,floor,c,empty),
                 state(Place2',floor,c,empty)),
          getbanana(state(Place2',floor,c,empty)).
```
となる。
Ｐｌａｃｅ２及びＰｌａｃｅ２’の値を保留のまま、getbananaを考える。
もう一度、getbananaの２番目の節を適用して...

もう、気づいたでしょう。猿はａ地点からＰｌａｃｅ２へ、そしてＰｌａｃｅ２からＰｌａｃｅ２’へ、このまま続ければＰｌａｃｅ２’からＰｌａｃｅ２”へと部屋の中を歩き回っています。箱を使おうともせず、バナナを求めて床の上を歩き回っている様はいささか哀れでもあります。

いままで、プログラムの記述順序が意味を持つとはあまり考えませんでした。change節の先頭にwalkを持ってきたところで、宣言的な意味は変わらないはずです。しかし、Ｐｒｏｌｏｇがマッチングを行う場合、プログラムの上から順に照合していくため、節の順序を変えることは手続き的には大きな違いになることがあるのです。

図7.1　猿うろうろの探索木

7.2 プログラムの記述順序に関する実験

実は、磯野家の家族関係を考える際に用いたdescendant関係にもこのような無限ループに陥る危険が潜んでいました。descendant関係は、

          descendant(X,Y):-     % descendant_rule_1
              parent(Y,X).
          descendant(X,Y):-     % descendant_rule_2
              parent(Y,Z),
              descendant(X,Z).

となっていました。これを元のプログラムとして、変形パターンを３つ示します。descendant関係は２つの節からなり、その一方の節は２つの目標からなっています。そこで、

２つの節（descendant_rule_1とdescendant_rule_2）の入れ替え
同一の節内（descendant_rule_2）の目標の入れ替え

を行うと変形パターンを３つ作れます。元のプログラムをtrans1とし、変形をそれぞれtrans2,trans3,trans4とします。これらのプログラムは宣言的な意味はいずれも変わりありません。

          % 元のプログラム
          trans1(X,Y):-
              parent(Y,X).
          trans1(X,Y):-
              parent(Y,Z),
              trans1(X,Z).

          % trans2 元のプログラムの節の入れ替え
          trans2(X,Y):-
              parent(Y,Z),
              trans2(X,Z).
          trans2(X,Y):-
              parent(Y,X).

          % trans3 元のプログラムの２番目の節の目標の入れ替え
          trans3(X,Y):-
              parent(Y,X).
          trans3(X,Y):-
              trans3(X,Z),
              parent(Y,Z).

          % trans4 元のプログラムの目標と節の入れ替え
          trans4(X,Y):-
              trans4(X,Z),
              parent(Y,Z).
          trans4(X,Y):-
              parent(Y,X).

３章で舟さんとタラちゃんのdescendant関係について勉強しました。ここでも同じように舟さんとタラちゃんのtrans1,trans2,trans3,trans4のそれぞれの関係について考えてみましょう。さて、次のように入力したらどうなるでしょう。

          ?- trans1(tara,fune).

          ?- trans2(tara,fune).

          ?- trans3(tara,fune).

          ?- trans4(tara,fune).

《演習問題》

３章でdescendant(tara,fune).を入力した場合にＰｒｏｌｏｇがどのように動いているかを調べたときのように、trans2,trans3,trans4が上のように入力された場合にどのように動いているか調べなさい。

元のプログラムと３つの変形パターンとの４通りのdescendant(trans)を比較してみれば、以下のことが考えられます。

parent関係のような、その節の存在で目標が充足するかどうかが決まる節を先に調べ、ルールを後に調べるようにする。
再帰呼び出しを後に調べるようにする。

これらは一概には言えませんが、経験則として頭に留めておくことは有益です。

さて、４通りのdescendantについて考えてみましょう。一番効率の良い処理をしているのはtrans1です。trans1とtrans2は、descendant関係に関するどのような質問にも答えられますが、trans4は決して答えに到達することはできません。そして、trans3はできたりできなかったりします。

《演習問題》

trans1では正しく答えられるのに、trans3では正しく答えられない質問を１つ挙げなさい。また、その理由を述べなさい。

閑話休題

　人工知能に関する逸話というとかならず登場するのがELIZAです。ELIZAはカウンセラーのように振る舞い、ユーザである患者の考えや感じ方を追求しようとするプログラムです。その対話は、次のようなものでした。

人 　間「人間は皆同じね。」
ELIZA  「どのように？」
人　 間「みんな私を困らせるわ。」
ELIZA  「例えばどんな風に？」
人　 間「私のボーイフレンドはここに行けと言ったし。」
ELIZA  「あなたのボーイフレンドがここに行けと言ったのですね？」
人　 間「彼は私が憂鬱症だと言うの。」
ELIZA  「憂鬱症とはお気の毒です。」
人　 間「そうなんです。私は不幸です。」
ELIZA  「ここに来ると不幸でなくなると思いましたか？」
人　 間「誰かに助けて欲しいんです。」
ELIZA  「あなたにとって助けとは何でしょうか？」
人　 間「お母さんと仲良くできることかと思います。」
ELIZA  「あなたの家族についてもっと話してください。」

　実際にこのプログラムの振る舞いを見た多くの人々が、ELIZAは人間の言葉を理解して、ユーザの抱える問題に真剣に対応してくれたものと信じました。精神分析医たちは、このプログラムの中に本当に診療知識が入っていて、患者の役に立つと考えました。あるユーザはプログラムと数時間も対話し、主治医か長年の親友のように思いこみました。　しかし、実はELIZAは見せかけの対話をしていたにすぎなかったのです。例えば、ユーザが入力した言葉の中に"母"という単語があったら、"あなたの家族についてもっと話してください。"と出力する、というような仕組みになっていたのです。誰が何のためにこのようなプログラムを作成したのでしょうか。続きは８章の最終ページです。

目次に戻る