バックトラックする複雑なProlog述語を書く前に、その基礎となる理論の概要と、どのようにそれが実現されているかを理解することが必要です。

Prolog述語のバックトラック中の制御の流れを説明するために、ボックスモデルがあります。詳細については、以下の文献の182ペ−ジを参照して下さい。

Programming in Prolog by W.F.Clocksin and C.S.Mellish 3rd edition, pub. Springer-Verlag 邦訳：「Ｐｒｏｌｏｇプログラミング」 発行：マイクロソフトウェア株式会社

Prologの述語は、図Ｃ-４で示されているように４つのポ−トを持つ箱で表現できます。

+------------------------+ CALL-----> | | ----->EXIT | Prolog | | Predicate | FAIL<----- | | <-----REDO +------------------------+

図Ｃ-４：ボックスモデルにおける述語の実行

Prologのそれぞれのゴ−ルに、このようなボックスモデルが１つずつ存在します。このことは、述語を再帰呼び出しする時に特に重要となります。つまり、再帰呼び出しのたびに新しいボックスが作らるのです。

それぞれのポートの意味は、以下のようになります。

ＣＡＬＬ- 最初にその述語が呼び出される時、このポ−トから入ります。ゴ−ル（呼び出された述語）に対応するボックスが生成され、このボックスは、ゴ−ルを最初に満たす解を捜すために活性化されます。

ＥＸＩＴ- 解が見つかった時、制御はこのポ−トからボックスの外に出ます。このときボックスは、非活性状態になりますが破壊されません。それは、述語の実行に成功して戻ったということを表しています。

ＲＥＤＯ- バックトラックのために、さらにゴ−ルを満たす解が必要な時には、このポ−トから再びボックスに入り再活性化します。

ＦＡＩＬ- もうこれ以上他の解が見つからない時、このポ−トから外に出ます。このときボックスは破壊され、これを"内部破壊"と呼びます。それはそのゴ−ルの失敗を表しています。

！　　　- （"カット"）-この他にボックスは、"外部破壊"されることもあります。バックトラック中に制御の流れが"カット"によってそのボックスをとびこえたり、ゴ−ルがアボ−トされている時におこります。

どのボックスでもCALLとFAILは常に１回ですが、EXITとREDOは何回も通ることがあります。

＜述語を書く時の注意＞

もし述語がバックトラックするものであれば、REDOポ−トを使って再びボックスに入らなければなりません。REDOポ−トから入った時に何をすべきかを知るためには、述語が前の活性化の時にどこにいたかについての情報を、記録しておかなければなりません。すなわち、どんな解がすでに見つかっているかということです。

述語がFAILによってボックスの外に出た時には、何らかの”後始末”をするとよいことがあります。そのボックスは、ボックスモデルのレベルでは、必ずしも元に戻されないような副作用を生んだかもしれません。変数の単一化を取り消し、プログラムで使われていた記憶領域を解除しなければなりません。特に、ボックスがファイルのオ−プンをした場合には注意して下さい。ファイルをクロ−ズすべきでしょうか？ 画面の変更や、アサ−トをリセットしたり削除する必要があるかもしれません。

＜ボックスモデルのコル−チンによる実現＞

ボックスモデルは、コル−チンによってシュミレ−トできます。コル−チンは、M.A. Jacksonの研究に基づくものです（Language Design for Modular Software Construction, IFIP, North Holland, Amsterdam,1977を参照して下さい）。コル−チンは、再入可能なル−チンです（ここでのＣ言語における使い方では）。これは、ある時点でル−チンを出ても、ル−チンの状態を記憶したまま呼び出されているプログラムに戻ることができるということです。まるでル−チンを出なかったかのように、変数，構造の制御など、すべてル−チンを出た時の状態そのままで、ル−チンに再入することができます。また何回でもル−チンを出たり、再入したりできます。

ボックスモデルのそれぞれのポ−トは、図Ｃ-５に示されるように、コル−チンでいう下記の各動作に相当します。

+----------------------------------------+ CALL--->| create +----------------+ detach |--->EXIT | & start | 　　　　　 | | | | コル−チン | | FAIL<---| detach & | 　　　　　 | resume |<---REDO | destroy +----------------+ | +----------------------------------------+ 　　 図Ｃ-５コル−チンとしてのボックスモデル

ＣＡＬＬ＝create & start: コル−チンの実体を作り、初期化して実行を開始します。すなわち最初の解を捜し始めます。

ＥＸＩＴ＝detach: コル−チンの実体を破壊することなく、脱出します。後でこの実体の実行を再開できるように、局所変数やプログラムポインタなどをセ−ブします。

ＲＥＤＯ＝resume: 新しい解を捜すために、直前にdetachによって実行が停止された所から、実行を再開します。

ＦＡＩＬ＝detach & destroy: コル−チンの実体から出て、これを破壊します。