4.再帰


【sigma】

[1,2,3]の総和を求めるプログラムを実行してみます。
まず2行目のfunc述語を定義しました。
1節目のfunc述語は再帰の終了条件です。第1引数が[]となっており、質問と一致しないことがわかります。
よって2節目のfunc述語へ移ります。2節目のfunc述語は質問に必要な処理をしています。リストの頭部と尾部を分解し、再帰呼び出しを行います。

sigma1

※[]
空リストと言い、要素のないリストです。

※リスト 
リストは|(縦棒)を使うことによって分解することが出来ます [1,2,3]  → [A|B] → [1|2,3] 

※2節目のfunc述語はプログラムの条件部分になります。 
:-マークを使って左辺と右辺に分かれています。
1行目のように:-マークのない値の定義されているものは事実であり常に真ですが、2行目は左辺は結論部分であり、右辺は条件部分です。
 (左辺を頭部、右辺を本体と言います。)
よって、本体が真でなければ頭部は真ではありません。 

2節目のfunc述語の頭部で分解したリストの尾部を本体へ渡し、再び頭部へと戻ります。 更に尾部であったリストを分解し、それを続けることでリストが[]になりました。


下図は再帰呼び出しを繰り返し、ここで「空リストは0である」1節目の定義とマッチしています。

sigma1

2節目のfunc述語の頭部で分解したリストの尾部を本体へ渡し、再び頭部へと戻ります。 更に尾部であったリストを分解し、それを続けることでリストが[]になりました。
sigma3

再帰呼び出しされた述語が順番に戻っていく過程で、決まっていなかった変数Yへ値がユニフィケーションされていきます。その結果本体の処理が行われ、頭部が結論付けられていきます。
sigma4

再帰した2節目のfunc述語が1節目のfunc述語とマッチしたことで初めて Y の値(0)がユニフィケーションされました。 そのため、本体の計算が成立し、計算結果が次々と Yへユニフィケーションされていくことで解が求められます。 
今回は[1,2,3]の総和を求めたいので、1節目のfunc述語の第二引数を0としました。
仮に0ではなく1に設定すれば Y の初期値は1増えますので、解答は7になります。 
1節目のfunc 述語(終了条件)は求めたい解答の初期値を定義すればいいのです。 

 

 


【サザエさん一家】

 前回の単位節を応用して、家族関係について調べます。
”タラ”の祖母(Y)は誰か質問します。

sazae1

まず祖母を探しているの、複合項grandMotherへ。
次にparent(Y2,X)にてタラの親を探します。
sazae2

parent述語の先頭からマッチする節を探し、parent(sazae,tara)がマッチしました。
sazae3

次にサザエの親(Y2)を探しにいきます。
sazae4

サザエの親を探した際、最初にparent(namihei,sazae)がマッチしますが、parentの第2引数の複合項sexの引数がmaleでないことから失敗しました。→”なみへい”は女性ではないためユニフィケーションしません。
sazae5

female(namihei)が失敗したことで、parent(Y,Y2)をRetryします。
parent(fune,sazae)が見つかり、female(fune)も成立することからこの節は成功します。 sazae6

parent(fune,sazae)が成立し、頭部へ戻った時点で決まっていなかった変数Yにfuneがユニフィケーションし成功しました。
sazae7