enumerater using PROgram in LOGic

That's close on two points!
First, I have handed in this report below, in time!
because this midnight is deadline.

Second, Tomorrow, I will participate in the party held by WRESS, where there will be gathered 300 people who can speak English for discussing! I heard team tables were already dicided, and the table I'm in gatherd good English speakers. How fun it seems! I will make full use of it!

----------
1. 問題設定
2. 考え方
3. 作成したプログラム
4. 実行結果
5. 考察
6. 感想



1. 問題設定
　　三つの自然数の足し算の全ての場合を列挙する。

2. 考え方
　　配布資料で示されている関数addは、第３引数が既に分かっているとき、バックトラックによって様々な解を捜し求めてくれる。しかしながら、第３引数が未知のときは、関数add内の再帰ループの結果が真となり、第１引数と第３引数のインクリメントが永遠と行われてしまう。
このような関数addの性質を踏まえつつ、関数addを用いて３項の加算演算を行う関数add3を使う。その後、関数add3を用いて三つの自然数の足し算の全ての場合を列挙する関数enum3を作成する。
このとき、関数addと同様の理由で、全ての変数を未知の状態で関数add3を呼び出してしまうと、再帰関数addでtrueの永久ループにはまってしまい、バックトラックが発生しなくなる。よって、常にバックトラックを発生させるため、まずは3項加算式の解である第4引数の値を決定させる。その後、関数add3を呼び出すことでバックトラックが起こり、三つの自然数の足し算の全ての場合を列挙する関数enum3が完成する。

3. 作成したプログラム
/* X + Y = Z */
add(0, Y, Y).
add(s(X), Y, s(Z)) :- add(X, Y, Z).

/* A + B + C = D */
add3(0, 0, Z, Z).
add3(0, s(X), Y, s(Z)):-
add3(0, X, Y, Z).
add3(s(A), B, C, s(D)):-
add3(A, B, C, D).

/* 3項加算演算で起こりうる全ての場合を列挙する */
enum3(A,B,C,D) :-
add(D,0,D), % 先にDの値を評価行う。
add3(A,B,C,D). % その後、AとBとCの評価を行う。

4. 実行結果
?- enum3(A,B,C,D).
A = 0,
B = 0,
C = 0,
D = 0 ;

A = 0,
B = 0,
C = s(0),
D = s(0) ;

A = 0,
B = s(0),
C = 0,
D = s(0) ;

A = s(0),
B = 0,
C = 0,
D = s(0) ;

A = 0,
B = 0,
C = s(s(0)),
D = s(s(0)) ;

A = 0,
B = s(0),
C = s(0),
D = s(s(0)) ;

A = 0,
B = s(s(0)),
C = 0,
D = s(s(0)) ;

A = s(0),
B = 0,
C = s(0),
D = s(s(0)) ;

A = s(0),
B = s(0),
C = 0,
D = s(s(0)) ;

A = s(s(0)),
B = 0,
C = 0,
D = s(s(0)) ;

5. 考察
　　本項目では、バックトラックの理解を深めるため、prologで関数enum3を呼び出したとき、処理系の内部ではどのような振る舞いが行われているのかを考察したい。
　　関数enum3が呼び出されたとき、最初に評価される式はadd(D,0,D)である。ここで、関数addの持つデータベースを見るとadd(0, Y, Y)と書かれていることがわかる。よって、このとき関数add3から関数addに渡される第２引数の値が0であることが分かっているので、add(0, Y, Y)より第３引数は0と判断する。結果、enum3の第４引数Dは0であると判断された。
その後、関数enum3の関数add3が呼び出される。このとき、これまでの結果から既にDの値は分かっているので、実際に関数add3に渡される引数はadd3(A, B, C, 0)となる。
　　次に、関数add3の内部の振る舞いについて考える。関数add3ではデータベースとしてadd3(0, 0, Z, Z)を持っている。関数addのときと同じように、第４引数が0であることからD=C=0である判断される。
その後、add3(0, s(X), Y, s(Z)):- add(X,Y,Z).の評価を行う。関数addで使う引数のYとZは共に0であることが分かっているため、実際に渡される引数はadd(X, 0, 0)となり、X+0=0よりX=0という結果を得る。つまり関数enum3の第二引数Bが0である判断される。
最後に、add3(s(A), B, C, s(D)):- add3(A, B, C, D).の評価を行う。これまでの結果から、再帰的に呼び出す関数add3に渡される引数は、add3(A, 0, 0, 0)となる。そして、再び関数add3の先頭の式から評価が開始される。つまり、データベースadd3(0, 0, Z, Z)と、引き渡された引数(A, 0, 0, 0)の照合が行われる。このとき、4つの引数のうち3つがデータベースと一致していることから、Aに入る引数は0であると判断される。結果、関数enum3の出力する値は、”A=0, B=0, C=0. D=0”となる。
一巡目の解求まると、バックトラックによって、今まで通ってきた解を順々に戻っていく。結果、関数enum3で一番初めのadd(D,0,D)を呼び出したところまで戻る。そして、他の解を探すため、分岐点の違う分岐ルートを選ぶ。つまり、関数add内の分岐、

add(0, Y, Y). 　（最初に通ったルート）
　add(s(X), Y, s(Z)) :- add(X, Y, Z).　(←違う分岐ルート：今度はこっちを通る)

である。コレによりs(D)が行われる。つまりs(0)となり、再び関数addが引数(s(0), 0, s(0))を伴って呼び出される。addが呼び出されると、本考察冒頭と同様に、データベースとの照合が行われる。そして、バックトラックにより関数enum3に戻り、関数add3が引数(A, B, C, s(0))を伴って渡されて呼び出される。
その後、関数add3のデータベースより、第３引数=第４引数と判断され、D=C=s(0)と判断される。そして、この後も１順目と同様に、式を評価していく。
このようにして、関数enum3では自明の解を得るまで式を次々と評価していく。このため、”2.考え方”の部分でも述べたが、式を評価していく途中で自明の解が得られない再帰ループに入ってしまった場合、思ったとおりの振る舞いをしてくれなくなる。
これらのことから、今回の問題のような列挙を目的とした探索をして欲しい場合は、処理系が一つずつ解を導いてくれるようにprogrammingする必要があるといえる。本プログラムでは、これらのことを意識し、バックトラックが常に発生する仕組みを構築した。結果、本プログラムは仕様に沿う振る舞いをしてくれた。

6. 感想
PrologがどのようなStepで走っているのかを理解するのが難しく、理解するのにかなりの時間を使ってしまった。そのため、課題２の問題例で示されている他の問題や、オリジナルの問題を解くことが出来なかった。なので、今回解けなかった問題に対しては、自由課題として後日提出したい。

Tweet