Prolog
SWI-Prolog
PrologDay 5

もっと非Prolog的Prologプログラミング

More than 3 years have passed since last update.


もっと非Prolog的Prologプログラミング

2014/12/05 @suharahiromichi

この文章のソースコードは以下にあります。

https://github.com/suharahiromichi/prolog/blob/master/cps_fib_quiita.swi

2日目のmandel59氏による「非Prolog的Prologプログラミング」では、フィボナッチ数列を例にPureな関数型言語をPrologに変換する説明がありました。

フィボナッチ数列の計算といえば、忘れてはいけないのは、継続渡しスタイル(CPS)での計算ですね。

「継続」を引数に渡すことで、いろいろとよいことがあるのだそうです。

Prologでこれをやってみよう、というのが今日の話題です。


2日めのプログラム

2日目のプログラムを再掲させていただきます。


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.


CPSの例

CPSでのフィボナッチ数列のプログラムをSchemeで書いた例を示します。これは、

http://d.hatena.ne.jp/nozom/20061014/1160814110

を参考にさせていただきました。

(define (fib_cps n k)

(if (or (= n 1) (= n 2))
(k 1)
(fib_cps (- n 1)
(lambda (v1)
(fib_cps (- n 2)
(lambda (v2)
(k (+ v1 v2))))))))

2番めの引数 k が継続です。(k 1)(k (+ v1 v2)) が継続が実際に実行される箇所です。kには、

(lambda ...) が継続として渡されます。

(lambda ...) の本体の中に fib_cps の呼び出しがあり、さらに継続があるので、ちょっと複雑なことになっています。


Prologでは

さて、このSchemeのプログラムを2日目と同様に、Prologに書き直してみましょう。

fib_cps(N, K, R) の節の最後に再帰呼び出しがあり、この部分が末尾再帰になっています。

ここでも、2番めの引数 K が継続です。継続の実行には高階述語のcallを使用します。また、Prologには「lambda」がないので、q1とq2という述語を定義しなければいけませんでした。ちょっと残念ですね。

その継続として渡される2引数のq1(K, N)q2(K, V)はどこで定義されているのだろう?と思ったひとはマニュアルで高階述語の call を調べてみましょう。きっとPrologが一層好きになるに違いありません。


fib_cps(1, K, R) :- !,
call(K, 1, R).
fib_cps(2, K, R) :- !,
call(K, 1, R).
fib_cps(N, K, R) :-
N1 is N - 1,
fib_cps(N1, q1(K, N), R).

q1(K, N, V, R) :-
N2 is N - 2,
fib_cps(N2, q2(K, V), R).
q2(K, N, V, R) :-
V1 is N + V,
call(K, V1, R).

fib_cps(N, R) :-
fib_cps(N, id, R).
id(A, A).

go :-
f(10, R1),
fib_cps(10, R2),
write(R1), nl,
write(R2), nl.

では、実行してみましょう。

% swipl -f cps_fib_quiita.swi

?- go.
55
55
true .


まとめ


  1. Prologでは、継続渡しスタイルのプログラムも書ける。