LoginSignup
9

More than 5 years have passed since last update.

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

Last updated at Posted at 2014-12-04

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
9