失敗駆動と再帰論理

論理だ、単一化だ、と言ってもループが書きたいときは書きたいのである。Prologの初歩的なイディオムとして、バックトラックを反復に利用する失敗駆動ループがある。例えばユーザにyes/noを選ばせたい場合などは、

yes_no :-
    repeat,                            % STEP1
    write('[yes/no] ?- '),             % STEP2
    read(X),                           % STEP3
    (X = yes -> !; X = no -> !, fail). % STEP4

入力がyesかnoで無ければSTEP4で単一化に失敗する。read/1もwrite/1もContinuationスタックには何も積まないため、repeat/0まで戻るが、この述語はこんな形をしている。

repeat.           % PRED1
repeat :- repeat. % PRED2

repeat/0はPRED2がPRED1を発火するためにいつでも成功する。斯くしてSTEP1は成功し、再びSTEP2で入力を求める。そして一度STEP4が成功すると、以降repeat/0が発火しないように枝を切り、yesなら成功、noなら失敗、となってyes_no/0は終了する。

失敗駆動ループはこのように(一瞥して分かる)小さな論理においてであれば便利に使える。しかしrepeat/0から失敗する部分までの論理が膨らんでくるとそうは行かない。プログラマの見落しが増大し、予期せぬ実行パスを生んでしまうからだ。そういったときは別のループイディオムがある。

yes_no :-
    write('[yes/no] ?- '),
    read(X),
    (X = yes -> !; (X = no -> !, fail; !, yes_no)).

この場合はrepeat/0が無い。失敗時には枝を切ってyes_no/0を再帰呼出する。開発過程で論理が膨らんで想定外の値が生まれると、即時に失敗してくれる。

このループイディオムには、実は論理型の本質が潜んでいる。後者のループを再帰論理と呼ぶことにしよう。図らずも今回の再帰論理は末尾再帰となっており、これが手続き型のforループと等価であることは明かであろう。当然、末尾再帰でない再帰論理もある。さて、論理型言語というかPrologは計算コストの見積りが簡単ではない。というのは、Prologがバックトラックを起すためである。

例えばaaaがbbbに依存し、bbbの候補が複数あり、bbbがcccに依存しているとする。aaaが呼出された時点では何れのbbbが成功するのか分からないため、まず何かのbbbを選択し、cccが呼出され、失敗すれば戻って別のbbbを選択する。このような仕組みがバックトラックによって実現されているわけだが、計算コストは一般的に空間か時間に依存した状態マシンの特性を指すので、経過したはずの状態を"無かった"ことにするような仕組みは相性が悪いのである。

しかし再帰論理の場合これは相当に改善される。次の例を見てほしい。

yes_no(X) :-
    write('[yes/no] ?- '),
    read(Y), !,
    ((Y = yes; Y = no) -> X = Y;
     yes_no(X)).

read(Y)を実行した次の述語が何になるかという部分に可能性の幅が存在する。再帰論理ではその候補の深さがここのみに依存するので、計算コストの伸びは限定的である。勿論ここで別の論理を呼出たとしても、またその論理にも同様の制限を設けることで、プログラム全体の計算コストはノイマン型に沿った定義となるのである。

論理型言語では、一見単純だと思われるイディオムの中に、思いも寄らない深い問題が眠っている事が多い。ということは翻ってみれば罠が一杯あるということでもあるし、未開拓の土地とも言うことが出来るであろう。そして敢えて触れなかった!（カット）について。これはバックトラックの無い世界では別の意味を持ち始めるのだが、それはまた別のはなし。