SCBM-Prolog 解決への道
数か月にわたるバグの正体が見えてきた
改良案は失敗だった
忙しい時期をようやく乗り越え、SCBM-Prologの開発を再開しました。
これまで考えてきた改良案を実装して試してみました。しかし、残念ながらうまく動きません。
なぜだろう？
じっくり考え直してみると、今回の改良案も、結局は従来の方式と同じことをしていたのです。
そして、何か月も私を悩ませてきた問題の根本原因が、ようやく見えてきました。
問題は再帰とバックトラックの組み合わせにあった
次のPrologプログラムを考えます。
perm1([],[]).
perm1(Xs,[X|Ys]) :-
select1(X,Xs,Zs),
perm1(Zs,Ys).
これはリストの順列を生成するプログラムです。
例えば、
?- perm1([1,2,3], X).
を実行すると、6通りの順列を順番に求めます。
処理の流れは単純です。
-
select1がリストから要素を1つ選びます。 - 残ったリストを使って
perm1を再帰呼び出しします。 - 再帰先の処理が終わると、バックトラックして
select1に戻り、別の要素を選び直します。
Prologではごく普通の処理です。
しかし、SCBM方式では、この3番目の処理に重大な問題がありました。
失敗継続の戻り先が変わってしまう
SCBM方式では、バックトラックのために「失敗継続」を動的に生成します。
失敗継続とは、簡単にいえば「現在の処理が失敗したとき、どこに戻って何を再開するか」を記録したものです。
SCBMでは、この失敗継続を管理するためにBP（バックポインタ）を使用しています。
従来の方式では、新しい失敗継続を生成するとき、直前のBPを記録していました。
一見すると、これで問題なさそうです。
ところが、再帰とバックトラックが組み合わさると事情が変わります。
例えば、次のような処理が起こります。
まず、select1 が成功して、後続の perm1 が呼び出されます。
この perm1 が失敗すると、先ほどの select1 に戻って別の解を探します。
ここまでは正常です。
ところが、select1 自身もバックトラックによって新しい失敗継続を生成することがあります。
すると、BPの状態が変わります。
その後、再び select1 が成功して後続の perm1 が失敗継続を生成すると、変更後の直前のBPを記録してしまいます。
しかし、そのBPは本来戻るべき場所を指しているとは限りません。
つまり、select1 の内部で生成された失敗継続と、perm1 が失敗したときに戻るべき失敗継続を混同していたのです。
これでは、バックトラックを繰り返すうちに制御の流れが狂ってしまいます。
どうやら、これが何か月も悩まされてきたバグの根本原因だったようです。
解決策：成功継続にBPを伝達する
そこで、新しい方法を考えました。
重要なのは、現在のBPをその都度参照するのではなく、本来戻るべきBPを後続の述語へ確実に伝えることです。
SCBM方式には、失敗継続とは別に「成功継続」があります。
成功継続とは、現在の述語が成功した後に実行する処理を記録したものです。
ここで、select1 を呼び出すときに、後続の perm1 へ進むための成功継続を生成します。
そして、その成功継続に、select1 を呼び出した時点のBPを記録しておきます。
select1 が成功すると、成功継続によって次の perm1 に制御が移ります。
このとき、成功継続に保存しておいたBPも一緒に伝達します。
後続の perm1 は、新たな失敗継続を生成するときに、このBPを使用します。
こうすれば、途中で select1 が何度バックトラックし、新しい失敗継続をいくつ生成したとしても問題ありません。
perm1 は、正しい戻り先を知っているからです。
成功継続と失敗継続を連携させる
今回のアイデアの重要な点は、成功継続が単に次の処理へ制御を渡すだけではなく、失敗したときの戻り先も伝えることです。
整理すると、次のようになります。
- 成功継続：次に実行する処理と、その処理に必要なBPを伝える。
- 失敗継続：伝えられたBPを利用して、正しい場所へバックトラックする。
これにより、select1 の内部で失敗継続がどれほど複雑に生成されても、後続の perm1 はその影響を受けなくなります。
大切なのは、失敗継続が生成された順番ではありません。
どの処理から呼び出され、失敗したときにどこへ戻るべきかという関係なのです。
ようやく解決への道が見えてきた
これまで私は、失敗継続をどのように管理し、バックトラック時にどのように復元するかを繰り返し考えてきました。
しかし、問題の本質はもっと単純でした。
動的に変化するBPをそのまま使っていたことが問題だったのです。
成功継続を利用して、本来の戻り先を後続の述語へ伝達すればよいのです。
新しい複雑な管理機構を追加する必要はありません。
SCBM方式にもともと存在する成功継続と失敗継続を連携させるだけです。
まだ実装による最終確認は必要ですが、少なくともこれまでの問題を説明できる、筋の通った解決策にたどり着きました。
数か月にわたって悩み続けた問題でした。
ようやく出口が見えてきた気がします。