非Prolog的Prologプログラミング

論理型プログラミング言語Prologは述語を定義してプログラミングする。でも、関数を基本単位としたプログラミングをしてきたのに、いきなり述語で書けと言われても、どうすればいいか分からない。今回は、関数を述語で表現してみる。

関数

フィボナッチ数列のn項目を返す関数f(n)の定義を普通に書いてみる。

f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2) if n > 1

これをPrologで書きなおす。

f(0, 0).
f(1, 1).
f(N, Y) :-
    N > 1,
    !,
    N1 is N - 1,
    f(N1, Y1),
    N2 is N - 2,
    f(N2, Y2),
    Y is Y1 + Y2.

f(0) = 0, f(1) = 1という定義を、Prologのf(0, 0), f(1, 1)という命題で表している。

最後の節の、カット!の前に書いてあるN > 1は、（この節で）関数が定義されている条件を表す。条件が満たされていれば、この次に進む。

カット!を通ると、失敗してもこれより前にバックトラックしなくなる。条件が満たされていれば、その時点で（プログラマーにとっては）この先失敗することがないと分かっているので、カットしてしまおう。

その後の命題の列は、y = f(n - 1) + f(n - 2)を表すためのものだけど、そのまま表現できないので、変数を導入して細かい命題に分割している。

まとめ

関数を組み合わせてプログラミングしたいなら、Prolog以外の方が楽。