Prolog
PrologDay 20

非非Prolog的Prologプログラミング

More than 3 years have passed since last update.

12/2の記事mandel59 さんが書かれた記事に TakaoOzaki さんが尾崎さんらしいコメントしてたのが面白かったです.そこで私もProlog的という妄念について個人的なコメントをしようと思いました.


非Prolog的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.

Prolog的という概念は特に定義されていないと思いますので,私はこのコードが取り立てて非Prolog的だとは思わないですが,敢えて申しますと,

?- f(N, 55).

というクエリが通らないのは嫌です.ここで改めて mandel59 さんの記事に目を戻しますと,


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


と書かれています.しかしながら記事中のフィボナッチ関数の定義には n に関する記述がありませんので well-defined になっていません.当然この n は自然数です.実際に Prolog 処理系は変数 N を決定する術が無くて困っているので,関数を述語で表現する際には可能な限り well-defined に与えてやらなくてはなりません.


非非Prolog的Prologプログラミング

私は別にProlog的という概念を述べたいわけじゃないんですけど,非Prolog的ってことも無いんじゃないの?という感じの書き方を示したいと思います.

まず自然数を定義してやります.

nat(0).

nat(N) :- nat(N0), succ(N0, N).

これで ?- nat(N). とすれば自然数 N が列挙できます.ちなみに succ/2 は ISO-Prolog の仕様にはありませんが,大半の処理系では実装されています.自分で書いたとして難しくありませんので,興味がある人は調べてください.

あとはほぼ元のコードのままで問題ありません.

fib(1, 1) :- !.

fib(2, 1) :- !.
fib(N, M) :-
nat(N), 2 < N,
N1 is N - 1,
N2 is N - 2,
fib(N1, M1), fib(N2, M2),
plus(M1, M2, M), !.

これで先程の問題は解決します.

?- fib(10, X).

X = 55.
?- fib(N, 55).
N = 10.


予告

明日は suharahiromichi さんの記事についてです.