バックトラック
3.1子と、子の子と、子の子の子と...
磯野家にsisterやauntなどいろいろな関係を定義してきました。今度は「血縁関係」について考えてみましょう。例えば、波平さんとタラちゃんは血がつながっていますが、波平さんとマスオさんは血がつながっていません。ただし、いきなり血縁関係を考えるのはちょっと大変なので、先ず「直系の子孫」について考えます。直系の子孫といっても、時代劇や旧民法の話ではないので、父系も長男も関係なしです。タラちゃんは波平さんや舟さんの直系の子孫だけど、カツオやワカメの直系の子孫ではない、ということです。
さて、先ずはdescendantという関係を定義してみましょう。これは、直系の子孫を知るための関係です。「子孫」というと何代も何代も後の人のような感じがしますが、ここでは単に「子は子孫」、「子の子（孫）も子孫」、「子の子の子も子孫」、というように直系の下の世代はすべて子孫と考えます。
それでは、子孫のルールを考えてみましょう。
先ず、最初に
- 全てのX,Yに対して
XがYの子ならば、XはYの子孫である。
と言えます。これをＰｒｏｌｏｇで表現すると、次のようになります。
descendant(X,Y):-
parent(Y,X).
これで「子は子孫」はできました。前章でやったchildと同じですね。次は「子の子は子孫」ですね。これは
descendant(X,Y):-
parent(Y,Z),
parent(Z,X).
ですね。もう、簡単です。「子の子の子は子孫」も「子の子の子の子は子孫」も同様に定義すればいいんですから。
descendant(X,Y):-
parent(Y,Z1),
parent(Z1,Z2),
parent(Z2,X).
descendant(X,Y):-
parent(Y,Z1),
parent(Z1,Z2),
parent(Z2,Z3),
parent(Z3,X).
さて、どこまで続ければいいのでしょう。
プログラムの中の磯野家は海さんからタラちゃんまで４世代ですが、もし、もっと多くの人々が登場するならば、その中で子孫を知るためには一体、どれだけのdescendantを定義しなければならないのでしょう。
ここで再び「エレガント」です。descendantを用いてdescendantを定義すれば、もっと簡単に何世代でも子孫を知ることができるのです。そのためには、次のように考えます。
- すべてのX,Yに対して
(1) ZがYの子であるようなZが存在し、且つ
(2) XがZの子孫であるとき
XはYの子孫である。
これをＰｒｏｌｏｇにすると、次のようになります。
descendant(X,Y):-
parent(Y,Z),
descendant(X,Z).
「子の子は子孫」、「子の子の子は子孫」、といくつもdescendantを書いたのが、これならば３行だけで何世代でも処理できます。descendantからdescendantを呼ぶのは再帰呼び出しです。Ｃ言語のときも再帰はやりましたね。descendantは再帰呼び出しをすることで非常に簡単になりましたが、同時に再帰はプログラムを考えるときに混乱しがちなので十分注意が必要です。
それではdescendant関係をまとめてみましょう。
descendant(X,Y):- % descendant_rule_1
parent(Y,X).
descendant(X,Y):- % descendant_rule_2
parent(Y,Z),
descendant(X,Z).
descendantという節が２つ並んでいます。先ず、(1)ＸがＹの子ならば（ＹがＸの親ならば）ＸはＹの子孫という節と、そして(2)ＺがＹの子で、ＸがＺの子孫ならばＸはＹの子孫という節です。これらは２つでワンセットと考えられます。このような節の集合を手続き(procedure)と言います。
また、％以降はコメントです。Ｐｒｏｌｏｇの場合は、/ * から * / までと % から行末までがコメントとなります。
これで「波平さんの子孫は誰か」という質問ができるようになりました。
?- descendant(X,namihei).
X=sazae;
X=katuo;
X=wakame;
.....
descendantは子孫だけではなくて先祖も知ることができます。先祖、という言葉にはちょっとすごい響きがありますが、この場合の子孫同様に自分の家系の親から上の世代をすべて先祖と考えてください。「タラちゃんの先祖は誰か」ならば次のようになります。
?- descendant(tara,X).
X=sazae;
X=masuo;
X=namihei;
.....
3.2Ｐｒｏｌｏｇは何を考えているのか
descendant関係をＰｒｏｌｏｇで扱う場合、Ｐｒｏｌｏｇはどのように動いているのでしょうか。次のような質問をしたとします。
?- descendant(tara,fune).
質問は、Ｐｒｏｌｏｇにとっては満たすべき目標でした。Ｐｒｏｌｏｇはこの目標を満たそうとします。そのために、先ずdescendantという節があるかどうかを探します。Ｐｒｏｌｏｇは次の２つの節を見つけます。
descendant(X,Y):- % descendant_rule_1
parent(Y,X).
descendant(X,Y):- % descendant_rule_2
parent(Y,Z),
descendant(X,Z).
他にdescendantという名称の節はありませんから、Ｐｒｏｌｏｇが選択できるのはこの２つしかありません。Ｐｒｏｌｏｇは先に書かれている方から順に試してみます。
descendant(X,Y):- % descendant_rule_1
parent(Y,X).
目標がdescendant(tara,fune).なので、ルールの中の変数を
X=tara,Y=fune
に置き換えて考えます。すると、最初の目標descendant(tara,fune).は
parent(fune,tara).
に置き換えられます。Ｐｒｏｌｏｇはこの副目標を満たそうとしますが、失敗します。
Ｐｒｏｌｏｇは目標descendant(tara,fune).を充足しようとして、これを副目標parent(fune,tara).に置き換え、失敗しました。そこで、もう一度、最初の目標descendant(tara,fune).に戻ります。この、元の目標に戻る動作を{\gt バックトラック}(backtrack)と言います。
Ｐｒｏｌｏｇは元の目標descendant(tara,fune).に戻って、今度は
descendant(X,Y):- % descendant_rule_2
parent(Y,Z),
descendant(X,Z).
を試してみます。ルール中の変数のうち、ＸとＹについては
X=tara,Y=fune
と置き換えられます。しかし、Ｚに関しては、この時点では確定しませんので、Ｐｒｏｌｏｇは副目標として
parent(fune,Z),
descendant(tara,Z).
を満たそうとします。先にparent(fune,Z)について考えます。プログラム中には舟さんに関しては
parent(fune,sazae).
parent(fune,katuo).
parent(fune,wakame).
の３つの節があります。Ｚの値として、これら３つの候補が考えられる訳です。Ｐｒｏｌｏｇは、プログラムに書かれている順に候補をＺの値として当てはめていきますから、最初は
Z=sazae
です。したがって、副目標は
parent(fune,sazae),
descendant(tara,sazae).
となります。parent(fune,sazae)は真ですから、後はdescendant(tara,sazae)について考えます。これは再帰呼び出しなので、再びdescendantという節を探し、
descendant(X,Y):- % descendant_rule_1
parent(Y,X).
descendant(X,Y):- % descendant_rule_2
parent(Y,Z),
descendant(X,Z).
を見つけます。ここで、先ず
descendant(X,Y):- % descendant_rule_1
parent(Y,X).
について、その変数の値を
X=tara,Y=sazae
として、
parent(sazae,tara).
を新たな副目標とします。これは全く同一の内容の節がプログラム中にありますから真となります。
かくして、descendant(fune,tara).は真となるわけです。
このようにＰｒｏｌｏｇはプログラムの中を変数に値を代入しながら、いろいろ試行錯誤して探索していきます。探索に成功すればｙｅｓと答えるか、または変数の値を答えます。途中で探索に失敗した場合は自動的に探索の一つ前の段階に戻って、別の方法を試みます。これをバックトラックというのです。これはＰｒｏｌｏｇの大きな特徴であり、また、この特徴故にＰｒｏｌｏｇは人工知能向き、知識処理向きの言語と言われるのです。
《演習問題》
- descendant(tara,fune).という質問をしたときのＰｒｏｌｏｇの動作を図にしてみなさい。
- Ｐｒｏｌｏｇが以下の質問に対して、どのようにして答えを導くかを説明しなさい。また、バックトラックは生じるか、答えなさい。
- ?- mother(sazae,tara).
- ?- mother(fune,sazae).
- ?- descendant(tara,umi).
3.3磯野家の血のつながり
なんか犬神家のようなタイトルになってしまいましたが、最後に磯野家の皆さんの血がつながっているのか、いないのかという話です。これには次の３通りの「血のつながり方」を考えれば良い訳です。
- ＸがＹの子孫なら、ＸとＹとは血がつながっている。
- ＸがＹの先祖なら、ＸとＹとは血がつながっている。
- ＸとＹが共通の先祖を持つなら、ＸとＹとは血がつながっている。
簡単ですね。プログラムは次のようになります。
blood(X,Y):- % blood_rule_1
descendant(X,Y).
blood(X,Y):- % blood_rule_2
descendant(Y,X).
blood(X,Y):- % blood_rule_3
descendant(X,Z),
descendant(Y,Z),
different(X,Y).
タラちゃんと波平さん、マスオさんとワカメちゃんなどいろいろな人たちの血がつながっているかどうか確認してください。
確認が終わったら問題です。
《演習問題》
- blood(tara,X).という質問をしたときのＰｒｏｌｏｇの動作を図にしてみなさい。
- このとき、ＰｒｏｌｏｇがＸの値の候補としていくつかの人物を答えます。これにすべて；（セミコロン）で応答しなさい。そうすると、サザエ、カツオ、ワカメなどはＰｒｏｌｏｇがＸの候補として２回以上挙げてきます。なぜ、同じ答えを２回以上返してくるのかを答えなさい。
閑話休題
Ｐｒｏｌｏｇは1971年にマルセーユ大学のAlan Colmerauerによって開発され、その後 R.Kowalskiをはじめ様々な研究者の手を経て今日のものとなっています。
ＰｒｏｌｏｇはProgramming in logicから命名されています。その名の通り、論理型のプログラミングに向いており、特に人工知能に関連した分野でパソコンをはじめ、ワークステーション、ミニコンピュータ、メインフレームなどで広く用いられています。
Ｐｒｏｌｏｇは開発当初は処理能力や機能の面で余り評価されてはいませんでした。特に知識処理の研究において先進国であったアメリカでの評価はＬＩＳＰに比較されて惨憺たるものであったようです。しかし、Ｐｒｏｌｏｇがリスト（後で勉強しますよ）の処理に優れていることが判り、また処理速度の点で改善されてきてから、論理プログラミング言語の１つとして評価されてきています。
Ｐｒｏｌｏｇの処理プログラムは
の３つに大別されます。当初、インタプリタによる処理だけであったのが、コンパイラが開発され、現在では並列処理が可能となっているのです。コンパイラは、Ｐｒｏｌｏｇを機械語またはＣ言語などに変換して実行します。並列処理は同時に複数の処理を行うものですが、現時点では処理装置に依存する部分も大きく、完全に実用とは言い切れません。
もし、皆さんが自宅のパソコンにＰｒｏｌｏｇを入れてみたい、というのであれば、niftyなどのパソコン通信でダウンロードすることをお薦めします。学習や小規模のプログラム開発であればインタプリタで十分ですし、最初は逐一実行しながら開発した方が良いと思います。
目次に戻る
