再帰論理、ふたたび

前回（失敗駆動と再帰論理）、失敗駆動ループを再帰論理に書き換えることで計算コストの見通しをすっきりさせると述べた。

しかし失敗駆動ループと違って、再帰論理はバックトラック時の継続を再帰の度に確保する必要があり不効率である。そのために!（カット）を挟んだのである。一般的に再帰構造が、反復よりコストを伴うのは紛れもない事実である。だが同時に、不効率な部分を!（カット）がそぎ落とす際の作法を、最適化の構造として一般化出来るのである。

Tail recursion
Schemeと違いPrologの仕様に末尾再帰最適化は存在しないが、その主旨は概ね流用可能である。入力文字列をリストとして認識する readline/1 を例に見てみよう。まずは"らしくない"例。

% readline/1
readline(Cs) :- readline(_, Cs).
% readline/2
readline(C, [C|Cs]) :-
    get0(C),
    (terminal(C) -> Cs = [];
     readline(_, Cs)).
% terminal/1
terminal(46).

入力バッファの終端判定は terminal/1 で行うものとする。ここではピリオド(. ASCIIで46)とした。副作用を伴う述語 get0/1 があるので、この部分はバックトラック出来ない。以前の話にある通り、I/Oの出入り口ではそれを捕獲するバッファを用意する。そこで readline/2 では入力毎に終端判定を行い、バックトラックせずに新しい環境フレームをスタックに積んで、文字を繋げていく。

readline/2 の記述は些か手続き的過ぎる嫌いがあるので、もう少し宣言的に書き下そう。

readline(C, []) :- get0(C), terminal(C).
readline(C, [C|Cs]) :- get0(C), readline(_, Cs).

宣言的に近づいた気もするが、明らかに get0/1 の記述が余計である。しかし入力がヘッドではなくボディにあるのでこれを前に持ってくる必要がある。部屋が無限にあるホテルが満席のとき、新たな客をどう迎え入れるか？の逆をやって解決してみよう。

No.1 -> No.2, No.2 -> No.3, .., No.Inf -> No.Inf+1

の逆なので最後尾から順に手前に移動する。

readline(C, []) :- terminal(C).                      % もう入力は不要
readline(C1, [C1|Cs]) :- get0(C2), readline(C2, Cs). % 次の入力の備え

今度は頭の入力が余るので、呼び出し元 readline/1 に与えてやる。

readline(Cs) :- get0(C), readline(C, Cs).

後は終端判定部がループの終了条件とするために!（カット）を仕込んで終わりである。

readline(Cs) :- get0(C), readline(C, Cs).
readline(C, []) :- terminal(C), !.
readline(C1, [C1|Cs]) :- get0(C2), readline(C2, Cs).