M-Prolog――脳疲労からの復活
しばらくM-Prologの開発を休んでいましたが、最近になって作業を再開しました。そして、どうやら最大の難関の一つを突破できたようです。
今回は、現在の開発状況についてご報告します。
成果
現在は、神戸大学の田村先生が紹介されているチャーチ数による計算を題材として、コンパイラの動作確認を行っています。
なかでも、times/3の実装にはかなり悩まされました。
図1
図2
times/3の動作
順方向の計算だけであれば、それほど難しくありません。
しかし、次のように逆方向の計算を行わせる場合は事情が大きく異なります。
?- times(X, Y, s(s(0))).
この計算では、強制バックトラックと再試行が必要になります。そのため、バックトラック機構が正確に動作しなければなりません。
ほんの少しでも設計に考慮不足があると、まったく正しく動作しません。
今回使用した定義は次のものです。
plus(0, Y, Y).
plus(s(X), Y, s(Z)) :-
plus(X, Y, Z).
times(0, _, 0).
times(s(X), Y, Z) :-
times(X, Y, Z1),
plus(Z1, Y, Z).
最初の解を表示した後、利用者がセミコロンを入力すると、強制バックトラックが発生します。
この時点で、最後に実行されたplus/3には、すでに別解がありません。そのため、さらに前の計算へ戻り、times/3の別解を探索しなければなりません。
この処理が、今回の大きな問題でした。
引数の復元
バックトラックして計算をやり直すためには、その時点で使用していた引数や変数の状態が残っていなければなりません。
SCBM2では、巨大な一つのC関数の内部に、Prologの各述語に対応するラベルを配置し、gotoによってラベル間を移動する方式を採用しています。
C関数内には、述語の実行に必要となる局所変数をあらかじめ用意し、そこへPrologの変数を割り当てています。
しかし、再帰呼び出しや別の述語の呼び出しが行われると、これらのC局所変数は上書きされます。そのため、バックトラックした時点では、以前の値をそのまま利用できません。
そこで、計算を開始する際に、引数リストをSCBMへ保存する方法を採用しました。
引数リストはセル構造で表現されています。その先頭アドレスを保持しておけば、バックトラック時に元の引数を復元できます。
変数スタックの復元
同様に、Cの局所変数だけでは、再試行に必要なProlog変数を保持できません。
そのため、times/3の第2節で再帰的なtimes/3を呼び出す前に、後続の計算で必要となる変数を変数スタックへpushしておきます。
再帰呼び出しが成功し、成功継続によってplus/3の処理へ移る直前に、それらの変数をpopして復元します。
さらに、バックトラックによって以前の計算状態へ戻る場合には、変数の値だけでなく、変数スタックのポインタも元の位置へ復元する必要がありました。
成功継続の復元
SCBM2では、成功継続と失敗継続を分けて保存しています。
成功継続は専用のスタックへ積み、失敗継続はSCBMのデータ構造へ保存します。
述語の呼び出しには、GCCの拡張機能であるコンピューテッドgotoを使用しています。述語の実行が成功すると、成功継続スタックから次のアドレスを取り出し、その場所へ直接ジャンプします。
ところが、バックトラックして以前の計算を再試行する場合には、引数や変数だけでなく、成功継続の状態も復元しなければなりません。
これを行わないと、再試行された述語が成功した後、本来予定されていた継続先とは異なる場所へgotoしてしまいます。
そこで、成功継続スタックのポインタもSCBMへ保存し、バックトラック時に復元するようにしました。
成功継続と失敗継続
SCBM2では、述語の呼び出しはすべてgotoによって行われます。
本体が連言になっている場合も、後続の述語へgotoで移動します。述語の実行が成功するたびに成功継続をたどり、成功継続スタックが空になった時点で、問い合わせ全体が成功したことになります。
ここで利用者がセミコロンを入力すると、強制バックトラックが開始されます。
現在の成功状態を終了させ、SCBMに保存されている失敗継続を取り出して、別解探索を再開します。その際には、次の状態を一体として復元しなければなりません。
- 実行時の引数リスト
- 変数スタックの位置
- 成功継続スタックの位置
- 再試行すべき節と失敗継続
文章にしてしまうと単純に見えます。
しかし、ここへ至るまでには、無数の推測、設計、再設計、手計算、デバッグ、試行錯誤がありました。
Prologの計算モデルは、LispやC言語とはまったく異なります。成功継続と失敗継続、単なる失敗と強制バックトラック、変数状態の復元などを同時に考えていると、ときには頭の中が完全に混乱しました。
AIの助けも借りながら検討を続け、ようやく根本的な問題を解決できたと思っています。
当初は、gotoを中心としてPrologの継続を処理する方法を思いついたものの、
「果たして、この方式は本当に機能するのだろうか」
という疑心暗鬼との闘いでもありました。
しかし、times/3の逆方向計算のように、再帰、連言、強制バックトラック、別解探索が組み合わされた処理が動作したことで、SCBM2の基本設計に間違いはないことを確認できました。
M-Prolog Ver.1.0へ向けて
今後は、さまざまなProlog述語を正常にコンパイルし、正しく動作させるための作業が続きます。
まだ山のような実装とテストが残っています。
しかし、今回の難関を突破したことで、M-Prolog Ver.1.0の公開へ向けた道筋が、ようやくはっきりと見えてきました。