Posted at
PrologDay 2

非Prolog的Prologプログラミング

More than 3 years have passed since last update.

論理型プログラミング言語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以外の方が楽。