Help us understand the problem. What is going on with this article?

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

More than 5 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では、継続渡しスタイルのプログラムも書ける。
suharahiromichi
定理証明系や論理プログラミングに興味をもっています。
https://sites.google.com/site/suharahiromichi/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした