Prolog の紹介
フィボナッチで各種言語をベンチマーク - satosystemsの日記 で Prolog のフィボナッチを以下のように実装しました。
fib(0, 0). fib(1, 1). fib(N, NF) :- A is N - 2, B is N - 1, fib(A, AF), fib(B, BF), NF is AF + BF. goal :- fib(38, NF), write([NF]), nl.
アルゴリズムがなんだか全くわからなかったのでリベンジしたところ、意味がわかるようになったので、メモを兼ねて皆さんに紹介します。
そもそも Prolog とは
論理プログラミング - Wikipedia
論理型言語は上記のようにいくつかの分類に分けられるのですが、Prolog は 1972 年からの歴史を持つプログラミング言語で、派生や方言が Lisp 並みにあって、処理系によってどれに分類されるか決まってきます。
要するに、関数型言語とはまた異なるのですが、宣言を記述する言語なのです。
宣言するのは事実、規則、質問です。事実と規則から質問の回答を処理系が推論します。
以上を踏まえて、フィボナッチのコードを解説します。
解説
まずは、以下です。
fib(0, 0). fib(1, 1).
これはフィボナッチの事実を宣言しています。読み方は「フィボナッチ数の 0 番目は 0」「フィボナッチ数の 1 番目は 1」ぐらいです。
次は以下です。
fib(N, NF) :- A is N - 2, B is N - 1, fib(A, AF), fib(B, BF), NF is AF + BF.
これはフィボナッチの規則を宣言しています。Prolog では、大文字およびアンダースコアで始まる名前は変数です。つまり、「フィボナッチ数の N 番目は NF」という規則を宣言し、その詳細規則を :- 以下に宣言しています。
「A is N - 2」は手続き型言語なら「var A = N - 2;」ぐらいの感じです。カンマで区切られたこの規則は、サブゴールと言い、すべてのサブゴールが満たされた場合に頭部の宣言が真（Yes）になります。
このサブゴールの集合（述語）を JavaScript で書き換えてみましょう。
fib(N, NF) :-
var A = N - 2; var B = N - 1;
var AF = fib(A); var BF = fib(B);
var NF = AF + BF;
うわっ、そういうことなの？なるほどねー。
最後の部分です。
goal :- fib(38, NF), write([NF]), nl.
goal というのは問題の回答を求める宣言です。fib(38, NF) の NF は変数で、ここに 38 番目のフィボナッチ数の解が得られます。
それを出力して改行、というのが今回の処理のすべてです。
応用
以下は好きなアニメによって属性を推論し、鈴木の友人を探し出すというコードです。
% 各人が好きなアニメを事実として宣言 loves(yamada, k_on). loves(tanaka, lucky_star). loves(suzuki, totoro). loves(saitoh, ponyo). % アニメ制作プロダクションのタイトルを事実として宣言 production(kyoto, k_on). production(kyoto, lucky_star). production(ghibli, totoro). production(ghibli, ponyo). % 友人関係を推論 friend(A, B) :- \+(A = B), loves(A, AT), loves(B, BT), production(P1, AT), production(P2, BT), P1 = P2. goal :- friend(suzuki, Who), % 鈴木の友人を Who に求める write([Who]), nl.
\+(A = B) というサブゴールは、友人関係なので同一人物ではない、という規則です。後は読むのは簡単ですね。
