実行方法
- http://www.swi-prolog.org/ (私は cygwin の物を使用)
- /usr/bin/pl にインストールされる。インタラクティブシェル使用。
- prolog の文で、?- が先頭にあるやつは、シェルに入力
- prolog の文で、何も付かないもの(定義)は別ファイルに書いて consult(ファイル名). か、assert(定義). で定義追加。
述語
father(lisa, homer).
prolog で一番引っかかったのが「述語」という考え方だ。例えば homer が lisa の父である時、father(homer, lisa). というらしいが、この場合、なんで述語が father なのか納得行かない。じゃあ、lisa の父は homer であると言うと、homer(lisa, father) になっちゃうじゃないか！と思うわけ。つまり、どれが述語かどうかは文脈によってどうとでも取れる。
だけど問題は、問い合わせる時にあるみたい。father(homer, lisa) の時、father(X, lisa) とする事で、lisa の父が誰かが分かる。しかし、X (homer, lisa) と問い合わせて lisa と homer の関係を聞く事は出来ない。本当にこれをやりたければ、relation(father, homer, lisa) のように、新しく関係を表す述語を決めないといけない。なるほど。
つまり、述語とは、問い合わせる可能性の無い要素を選べば良いのかな。何となく、SQL の「テーブル名」のような物じゃないかと思った。
非決定性とバックトラック
バックトラックという言葉も無駄に魔術的な単語だ。何度聞いても意味が分からなかったが、どうも色々想像するに、列挙する事をバックトラックと言うらしい。非決定性というのもいやらしい。まるでプログラムの挙動が予測出来ないような、生きているか死んでいるか分からないようなネコを記述出来るかのような語感だが、どうも複数の値が返るのを非決定性と呼んでいるようだ。prolog はユーザが ; を押すのを待って一つずつ答えを返すので、リストが無限でも大丈夫。
さて、列挙といえば SQL の SELECT や Haskell の内包表現だけど、[(x, y) | x <- bin, y <- bin] where bin = [True, False] のような事を prolog でどう書くかというと、こうなるらしい。
bin(true). bin(false). twobin(X, Y) :- bin(X), bin(Y). ?- twobin(X, Y). X = true, Y = true ; X = true, Y = false ; X = false, Y = true ; X = false, Y = false ; No
単純で素晴らしい。コンマで区切られた項のそれぞれは、map 関数 (又は #collect:)だと考える事が出来る。後ろの項を全部検索してから、前の項を繰り返すという事。さて、prolog にもリストがあるので、これをリストにしてみる。Haskell と違って、遅延評価はここまでで、リストにすると答えは全部いっぺんに出る。
seq(L) :- seq([], L). seq(L0, L) :- twobin(X, Y), % twobin の組み合わせを列挙する。 not(member([X, Y], L0)), % リストにすでにあれば別のを試す !, % リストに無ければもう試さなくて良い。 seq([[X, Y] | L0], L). % 追加したリストを元に別の組を探す。 seq(L, L). % 追加する組が無くなればそれが答え。 ?- seq(L). L = [[false, false], [false, true], [true, false], [true, true]] ;
ライブラリを使えば findall([X, Y], twobin(X, Y), L). とも書ける。が、上で書いた seq には prolog のもう一ついやらしい面、カットが登場する。
カット
tomodachi(gaian). tomodachi(suneo). tomodachi(shizuka) :- !. tomodachi(nobita). ?- tomodachi(X). X = gaian ; X = suneo ; X = shizuka ; No
定義の途中にカット(!)を入れると、まだ nobita が残っているのに検索が終わる。
途中ですが、なんか体調悪いので寝ます。あとでもっとカットと、ユニフィケーションについて書く予定かもしれない。
