• 22 Dec. '14 -- fib_cps/3 中のカットの間違いを修正．

昨日 は 非Prolog的Prologプログラミング について言及しました．mandel59 さんの記事には，私だけでなく suharahiromichi さんが既に もっと非Prolog的Prologプログラミング として言及されていましたので，今回はそちらの継続渡しについて考えます．

#もっと非Prolog的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).

動作の詳細は元記事に譲るとして今回のコードも ?- fib_cps(N, 55). が通りませんから，これを解決したいと思います．

昨日の記事の中で私は Prolog 処理系が変数の決定に困らないために，述語の定義は well-defined に与えましょうと述べました．しかしながら今回のコードにおいて call/3 の部分は well-defined になりようがありません．そこで call/3 が扱うよりもずっと小さいクラスの集合を定義してやる必要があります．

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

継続を評価する（ことに相当する）述語 call/3 を次のように改めることで，非常に小さい集合を定義します．

cont(id, X, Y) :- id(X, Y).
cont(q1(K, N), X, Y) :- q1(K, N, X, Y).
cont(q2(K, N), X, Y) :- q2(K, N, X, Y).

少し説明を添えると，継続に限らず Prolog で処理の流れを柔軟にしようと思ったときに call/3 を使うことは自然なものだと思うのですが，それは同時に不確かさをもたらすことに繋がります．そこでプロダクションコードなどでは上のようにして，カスタマイズポイントを設けて分岐を記述させるアプローチを取る場合があります．

さてここでちょっと殺まらないといけないんですが，昨日の自然数の定義はあまり良くありませんでした．継続渡し形式の利点は，処理の流れを明確に記述することにあるわけですが，これを Prolog で素直にやってしまうと choice ポイントを余計に増やしてしまい，望ましくないバックトラックを行なわせてしまう恐れがあります．そのため，昨日の定義を流用するとハマってしまいます．今回は次のように書き直してください．

nat(0).
nat(N) :- var(N), nat(N0), succ(N0, N).
nat(N) :- 0 < N, succ(_N, N).

これで準備が出来ました．各述語の中では（変数の宣言を除けば）基本的に一度に一つの処理だけ記述していることに注目してください．このお陰で，各処理が双方向的になっていれば，継続渡し形式で書いた Prolog コードは自然と各変数を双方向に求めることが出来ます．

fib_cps(1, K, R) :- cont(K, 1, R).
fib_cps(2, K, R) :- cont(K, 1, R), !.
fib_cps(N, K, R) :-
    nat(N), 2 < N,
    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) :-
    plus(N, V, V1),
    cont(K, V1, R).
id(A, A).

これで知りたい変数は全て Prolog が見つけてくれます．

?- fib_cps(10, id, X).
X = 55.
?- fib_cps(N, id, 55).
N = 10.
?- fib_cps(10, K, 55).
K = id.

#Prolog的とは

2日に渡ってProlog的という妄念に関して，Prolog的で無いということは無い，という考え方で書いたつもりです．実はこういうスタイルこそ個人的に Prolog っぽいなと思うことがあります．というのは Prolog では任意要素の評価を行なう場合に，

forall(A, B) :-
    \+ ( call(A),
         \+ call(B)
       ).

という感じで否定述語をよく用いるためです．まぁ個人的な気持ちの問題ですが…