はじめに
大学でPrologという論理型プログラミングの存在を知り、練習として素数判定プログラムを作りました。
完成までに試行錯誤したことでかなりPrologへの理解につながったので、足跡として残しておきます。
目次
1.素数判定プログラム
2.実際に動かしてみる
3.仕組みを考える
4.おわりに
1. 素数判定プログラム
とりあえず、コードだけ知りたい人の為に今回作ったコードを最初に張っておきます。
fact1(X, Y) :- 0 is X mod Y, !.
fact1(X, Y) :- X > Y+1, fact1(X, Y+1).
fact2(2) :- true, !.
fact2(X) :- X < 2,!,false.
fact2(X) :- not(fact1(X,2)).
なんでこれで素数判定ができるか知りたい人は続きをどうぞ。
2. 実際に動かしてみる
まずは本当に素数判定ができるか動かしてみましょう。
Prologにはオンライン上で実行させられるツールがあります。
今回はこれを使って動作を確認していきたいと思います。
実行方法
1. 上記のリンクを開いたらProgramをクリック
2. コードを貼り付ける
ここまででPrologにおけるプログラムの部分は完成です。
ここから実行していきます。
3. 右下のスペースにfact2(7)と入力してみる
4. Run!
trueと出たらOK!
3. 仕組みを考える
Prologの独特な部分として、すべての内容が真になるものを、すべて探そうとします。
これを前提として以降を読み進めてください。
fact1
まずはfact1から考えます。
fact1(X, Y) :- 0 is X mod Y, !.
fact1(X, Y) :- X > Y+1, fact1(X, Y+1).
この部分ではfact1(X, Y)という関数を定義しているのですが、処理は1行目から始まりXをYで割った余りが0になるかを確認します。
本来は,で複数の条件を書いていくのですが、ここでは2つ目の条件として!が入っていることが分かります。
これは前の条件が真になった時、以降の処理を行わないという意味になります。(カットと言います)
例えばX=4,Y=2の時はtrueが返答されて、2行目から下は実行されません。
次に2行目です。
ここでは他のプログラムでいうforを実現しています。
1行目と同様に考えていきます。まずはX > Y+1 で大小関係の比較を行います。これは、Y+1でもわかる通り、次の周回に行くべきかどうかを決定しています。つまり継続条件です。
そして継続条件が真であったときは,の後のfact1(X, Y+1)を評価します。そしてY+2、Y+3とYを1ずつ増やしながら再帰していきます。
Prologではforを再帰関数で表現するのです。
以上の説明から考えるとfact1はYからX未満のすべての数の中で1つでもXを割り切れるものがあればtrueを返すというプログラムだと分かります。
fact2
ここまでの内容が理解できればfact2は簡単です。
fact2(2) :- true, !.
fact2(X) :- X < 2,!,false.
fact2(X) :- not(fact1(X,2)).
1行目では2が入った時はtrueを返して処理を終了させています。これは、3行目でfact1(X,2)と呼び出しているのですが、fact1の1行目の条件よりfact1がtrueになって素数ではなくなってしまうため、例外的に処理しています。
2行目も同様にtrueとなってしまうのを回避するために2より小さい数では常にfalseを返しています。
最後に3行目で、fact1の逆、つまり素数ならばtrueを返して終了です。
以上
これでプログラム全体を理解できました。一つ一つ分解して考えるとそこまで難しくもないのかなと思います。
軽い練習として、53も素数として判定するようにしてみても面白いかもしれません。
おわりに
リアルタイムで知識を増やしながら書き進めたので、間違いやより良い表現があれば、コメントでお知らせください。