もっと非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では、継続渡しスタイルのプログラムも書ける。