M-PrologにおけるSCBM方式コンパイラ
M-Prologは、私が開発しているProlog処理系 N-Prolog の後継となる処理系です。近年、このM-Prologのコンパイラを設計・実装してきましたが、ようやく基本方式がまとまり、ある程度の成果が得られました。
本稿では、そのコンパイラ方式である SCBM (Sasagawa & Chat Backtracking Mechanism) について紹介します。
SCBMの特徴は、Prologのバックトラック情報を「再帰方向」と「連言方向」に分離し、2次元的な継続データ構造として管理する点にあります。これにより、WAMのような抽象機械を直接実装するのではなく、C言語の通常の関数呼び出しを活かしながら、再帰を含む非決定性述語のバックトラックを実現しようとするものです。
1. はじめに
Prologコンパイラでは、長年にわたり WAM (Warren Abstract Machine) が事実上の標準となっています。
WAMは1980年代初頭に考案された抽象機械であり、Prologに特有のユニフィケーション、選択点、環境、バックトラックなどを効率よく実現するための非常に優れた設計です。現在でも、高性能なProlog処理系の多くはWAM、あるいはWAMを基礎とした方式を採用しています。
一方で、現在の計算機環境はWAMが考案された当時とは大きく異なります。今日の一般的なPCは1980年代の大型計算機を大きく上回る性能を持ち、メモリ容量も十分に大きくなりました。また、GCCをはじめとするCコンパイラは非常に高度な最適化を行います。
そこで私は、次のような発想を持ちました。
抽象機械を介さず、C言語の通常の関数呼び出しを活かしたまま、Prologのバックトラックを実現できないだろうか。
もちろん、Prologの実行制御は単純ではありません。とくに非決定性述語、連言、再帰、そしてそれらが組み合わさった場合のバックトラックはかなり複雑です。
しかし、多少最適でない処理があったとしても、現在のCPU性能とメモリ容量で補える部分はあります。もしC言語の関数呼び出しをそのまま活かせるなら、実装は単純になり、処理系全体の見通しもよくなるのではないかと考えました。
この考えから生まれたのがSCBMです。
2. 単純な非決定性述語
まず、もっとも単純な非決定性述語を考えます。
n(1).
n(2).
n(3).
この述語は、バックトラックにより次の3つの解を生成します。
?- n(X).
X = 1 ;
X = 2 ;
X = 3 ;
no
この程度の非決定性をC言語で実装することは、それほど難しくありません。
必要なのは、「前回どの節を実行したか」を保存しておくことです。最初は第1節を実行し、バックトラックが起きたら第2節を実行し、さらにバックトラックが起きたら第3節を実行します。
つまり、述語ごとに選択肢、すなわち choice point を保存しておけばよいわけです。
C言語では、いったん関数から戻ると、その関数の実行状態は失われます。しかし、SCBMでは必要な選択情報を明示的に保存しておくことにより、再度その関数を呼び出したときに前回の続きから実行できるようにします。
この方式には、関数を再び呼び出すというオーバーヘッドがあります。しかし、そのかわりにPrologの証明木をC言語の関数呼び出しの連鎖として比較的自然に記述できます。
例えば、次のようなベンチマークを考えます。
bench :-
n(X),
n(Y),
n(Z),
n(A),
n(B),
fail.
bench.
これは単純な非決定性述語を連続して呼び出し、最後に強制的に失敗させることで全ての組み合わせを列挙するものです。
SCBMでは、それぞれの述語呼び出しの選択肢を保存し、失敗時には直前の選択点に戻って次の節を実行します。この単純なケースについては、M-Prologのコンパイラ版はSWI-Prologと同等以上の性能を示しました。
3. 再帰を伴う述語
次に、再帰を考えます。
単純な再帰の例として、階乗計算があります。
fact(0, 1).
fact(N, X) :-
N1 is N - 1,
fact(N1, X1),
X is N * X1.
この場合、通常は解が一意に定まります。したがって、バックトラックによって別解を探す必要はありません。このような決定的な再帰は、C言語の通常の再帰関数として比較的自然にコンパイルできます。
問題になるのは、再帰と非決定性が組み合わさった場合です。
代表的な例が append/3 です。
append([], X, X).
append([A|X], Y, [A|Z]) :-
append(X, Y, Z).
例えば、次の問い合わせを考えます。
?- append(X, Y, [1,2,3]).
X = []
Y = [1,2,3] ;
X = [1]
Y = [2,3] ;
X = [1,2]
Y = [3] ;
X = [1,2,3]
Y = [] ;
no
このように append/3 は再帰述語でありながら、複数の解を生成します。
ここでは、単に「前回どの節を実行したか」を保存するだけでは不十分です。再帰の深さごとに異なる選択点が存在し、それぞれの深さでバックトラックの状態を管理しなければならないからです。
これがSCBM実装における最初の難問でした。
4. SCBMの基本構造
SCBMでは、述語を大きく次のように分類します。
det : 決定的述語
nondet : 非決定性述語
recur : 再帰を含む非決定性述語
tail : 末尾再帰述語
dyn : 動的述語
このうち、SCBMの中心となるのは nondet と recur の区別です。
単純な非決定性述語では、横方向に選択点を並べていけば十分です。ところが、再帰を含む非決定性述語では、再帰の深さ方向にも選択点を管理する必要があります。
そこでSCBMでは、バックトラック情報を2次元的に管理します。
連言方向
+------+------+------+
再帰 0 | ○ | ○ | ○ |
方向 1 | ○ | ○ | |
2 | ○ | | |
3 | ○ | | |
+------+------+------+
横方向は、連言中に現れる非決定性述語の並びを表します。
例えば、
p(X), q(X), r(X)
のような問い合わせでは、p、q、r が横方向に並びます。
一方、縦方向は再帰の深さを表します。
再帰述語では、同じ述語が深く呼び出されていきます。その各段階で、どの節を選択したか、どの引数で成功したか、どこまで再実行すべきかを記録する必要があります。
このように、SCBMでは
横糸 = 連言方向
縦糸 = 再帰方向
としてバックトラック情報を整理します。
この発想により、連言による横方向のバックトラックと、再帰による縦方向のバックトラックを分離して扱うことができます。
5. 成功路の再現
再帰を含む非決定性述語で難しいのは、バックトラック時にC言語の再帰スタックをどのように再現するかです。
C言語では、関数から戻るとその関数呼び出しのスタックフレームは失われます。しかしPrologでは、バックトラックによって過去の実行地点に戻る必要があります。
SCBMでは、以前に成功した実行経路を記録しておき、バックトラック時にはその成功路をもう一度たどります。
ただし、このとき通常の計算やユニフィケーションを再実行するわけではありません。成功済みの経路を再現するだけです。
そして、前回成功した地点に到達したところで引数を復元し、そこから次の選択肢を試します。
つまり、SCBMの再帰バックトラックは次のように動作します。
1. 初回実行では通常どおり計算する
2. 成功した経路をSCBMに記録する
3. バックトラック時には成功路を再びたどる
4. 前回の成功地点に到達したら引数を復元する
5. 次の選択肢を試す
この「成功路を再現する」という考え方が、SCBMにおける再帰バックトラックの中心です。
6. modeによる実行状態の切り替え
SCBMでは、各スレッドごとに mode という状態を持たせています。
M-Prologはマルチスレッド処理系であるため、mode は次のようにスレッド番号 th を添字に持ちます。
mode[th]
mode には、主に次の2つの状態があります。
mode = 0 : 新規実行
mode = 1 : バックトラックによる再試行
新規実行の場合、述語は通常どおり計算を行い、新しい選択情報をSCBMに記録します。
一方、再試行の場合には、以前に記録された成功路をたどります。このときは、ユニフィケーションや実際の計算をそのまま再実行するのではなく、前回の成功経路を再現することが目的になります。
mode を切り替える契機は、述語の完全失敗です。
ある述語が完全に失敗すると、SCBMでは必要に応じて次のような処理を行います。
discard_conj(th);
または
discard_recur(th);
これにより不要になった選択情報を破棄し、mode を再試行状態に切り替えます。
その後、直前の述語がバックトラックされると、mode が 1 であるため、SCBMは以前の成功路をたどる動作を行います。そして前回の成功地点に到達した時点で mode を 0 に戻し、次の計算を開始します。
この mode の切り替えにより、SCBMは「新しく探索する場合」と「以前の成功路を再現する場合」を区別しています。
7. 実行例
SCBM方式の妥当性を確認するために、神戸大学の田村先生のページに掲載されていたPrologコードを利用しました。
このコードはチャーチ数を用いた自然数、加算、乗算、商、割り切れないことの判定、そして素数判定を表現しています。再帰が深くネストし、さらにバックトラックも絡むため、SCBMの検証には非常に良い題材でした。
nat(0).
nat(s(X)) :- nat(X).
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).
le(X, Y) :- plus(X, _, Y).
lt(X, Y) :- le(s(X), Y).
quot(X, Y, 0, X) :- lt(X, Y).
quot(X, Y, s(Q), R) :-
plus(Y, X1, X),
quot(X1, Y, Q, R).
dnd(M, N) :- quot(N, M, _, s(_)).
df(s(0), _).
df(s(s(M)), N) :-
dnd(s(s(M)), N),
df(s(M), N).
prime(s(X)) :- df(X, s(X)).
このコードでは、例えば prime/1 の判定において df/2、dnd/2、quot/4、plus/3 などが複雑に絡み合います。
とくに quot/4 は非決定性を含む再帰述語であり、途中で失敗した場合には深い再帰構造の中でバックトラックが発生します。
このような例が正しく動作すれば、SCBMの基本的な考え方はかなり有望であると考えられます。
8. M-Prologでの実行結果
以下は、M-Prologでコンパイルを行った例です。
M-Prolog Ver 0.50 [30M cells]
?- use_module(compiler).
yes
?- compile_file('./tests/bug').
phase pass1
phase pass2
phase pass3
compiling apptest/0 recur
compiling n/1 nondet
compiling bench/0 nondet
compiling bench1/0 nondet
compiling woo/1 recur
compiling partition/4 recur
compiling mmember/2 recur
compiling nat/1 recur
compiling plus/3 recur
compiling times/3 recur
compiling le/2 recur
compiling lt/2 recur
compiling quot/4 recur
compiling dnd/2 recur
compiling df/2 recur
compiling prime/1 recur
compiling mappend/3 recur
compiling apptest1/0 recur
compiling disj/0 nondet
compiling disjtest/0 nondet
compiling p/1 nondet
compiling cut/1 nondet
compiling cuttest/0 nondet
compiling nodiag/3 tail
compiling bar/1 det
compiling f/2 nondet
invoke GCC
yes
?- ['./tests/bug.o'].
yes
SCBM方式により、nat/1 と prime/1 の組み合わせも動作しました。
?- nat(X), prime(X).
X = s(s(0)) ;
X = s(s(s(0))) ;
X = s(s(s(s(s(0))))) ;
X = s(s(s(s(s(s(s(0))))))) ;
X = s(s(s(s(s(s(s(s(s(s(s(0))))))))))) ;
X = s(s(s(s(s(s(s(s(s(s(s(s(s(0))))))))))))) .
yes
また、append/3 に相当する mappend/3 も期待どおりに動作しました。
?- mappend(X, Y, [1,2,3]).
X = []
Y = [1,2,3] ;
X = [1]
Y = [2,3] ;
X = [1,2]
Y = [3] ;
X = [1,2,3]
Y = [] ;
no
これらの結果から、少なくとも再帰を含む非決定性述語について、SCBM方式が一定の実用性を持つ可能性が見えてきました。
9. Prolog処理系実装の難しさ
Prolog処理系の実装はかなり複雑です。
人間がPrologを使うときには、ユニフィケーション、変数束縛、バックトラック、節の選択、再帰呼び出しなどを意識せずに記述できます。しかし、その分、処理系側が多くの仕事を引き受けなければなりません。
インタプリタであれば、CPSや明示的な継続を用いることで比較的素直に実装できます。しかし、その方式では実行速度に限界があります。
高性能なProlog処理系でWAMが広く採用されてきたのは、まさにこのためです。WAMは複雑ですが、Prologの実行モデルを非常によく捉えた抽象機械です。
これに対してSCBMは、WAMを改良する方式ではありません。
むしろ、
WAMを使わず、C言語の関数呼び出しを活かしてPrologコンパイラを実装できないか
という別方向からの試みです。
SCBMがWAMのようにあらゆるPrologコードを正しく効率的に実行できるかどうかは、まだ結論できません。現段階では実証段階であり、さらに多くのテストが必要です。
しかし、今回の田村先生のコードのように、深い再帰と非決定性が絡む例を正しく実行できたことは、大きな前進だと考えています。
10. SCBMの意義
SCBMの意義は、単に新しいデータ構造を考案したことだけではありません。
私にとって重要なのは、Prologのバックトラックを次のように整理できたことです。
連言方向のバックトラック
再帰方向のバックトラック
従来、再帰と非決定性が絡み合うと、実行状態の把握が非常に難しくなります。デバッグプリントを追いかけていても、どこに戻るべきなのか、どの選択点が生きているのか、すぐに見失ってしまいます。
SCBMでは、これを縦糸と横糸のように分解して考えます。
縦糸 = 再帰
横糸 = 連言
この見方により、複雑に見えるバックトラックの構造を、ある程度整理して扱えるようになりました。
もちろん、まだ未解決の課題はあります。cut、if-then-else、動的述語、より複雑な相互再帰、組み込み述語との関係など、確認すべき点は多く残っています。
しかし、少なくともSCBMは、WAMとは異なるPrologコンパイラの可能性を示すものになったと考えています。
11. AIとの共同研究
今回のM-Prologコンパイラの設計と実装では、ChatGPTを大いに活用しました。
基本的なアイディアは私が考えたものです。しかし、その過程でChatGPTから多くのヒントを得ました。
ChatGPTはWAMやProlog処理系の一般的な知識を持っており、それとの比較を通じて、自分の方式の特徴を明確にすることができました。
また、実装段階ではコードレビューやデバッグの補助として非常に役立ちました。
コンピュータプログラムでは、配列添字が1つずれただけでも正しく動作しません。人間はどうしてもうっかりミスをします。ChatGPTにコードを見てもらうことで、そのようなミスを早く発見できることがありました。
さらに、試作品を実行するときには大量のデバッグプリントを出しました。その実行ログをChatGPTに見せ、どこで状態が崩れているのか、どの選択点が残っているのか、どのmodeで動作しているのかを一緒に追跡しました。
とくにSCBMのように、正解となる既存実装がない方式では、単にコードを書くだけでなく、設計そのものを何度も見直す必要があります。
実際、途中で何度も設計を変更しました。当初は気づいていなかった問題が実行ログから見つかり、それを解決するためにデータ構造を考え直しました。
その過程で、SCBMは最終的に2次元配列的な構造へと整理されました。
12. 人間とAIの縦糸・横糸
SCBMでは、再帰方向と連言方向を縦糸と横糸のように整理しました。
振り返ってみると、今回の研究そのものも、人間とAIによる縦糸と横糸の織物のようでした。
人間もAIも間違えます。しかし、間違え方が異なります。
人間は、基本的な発想を出したり、全体の設計を見通したり、なぜその方式に意味があるのかを考えることに向いています。
一方でAIは、局所的な矛盾を見つけたり、実行ログを追跡したり、既存知識との比較から別の視点を提示したりすることに優れています。
人間だけでは見落とすことがあります。AIだけでも、何を目指しているのかを決めることはできません。
しかし、両者を組み合わせることで、ひとりでは到達しにくい場所に近づけることがあります。
今回のM-Prologコンパイラの開発を通じて、私はそのことを強く実感しました。
13. おわりに
AIは急速に進歩しています。今後、創薬、核融合、材料科学、数学、計算機科学など、多くの研究分野でAIが重要な役割を果たすようになると言われています。
私は今回のSCBMの研究を通じて、その可能性を身近に経験しました。
AIは単なる作業補助ではありません。人間とは異なる視点を持つ、知的な共同作業者になりつつあります。
SCBMは、Prologコンパイラにおける新しいバックトラック方式の試みであると同時に、人間とAIが協力して設計・検証した研究成果でもあります。
その思いを込めて、この方式を次のように名付けました。
SCBM
Sasagawa & Chat Backtracking Mechanism
これはまだ実証段階の方式です。WAMに代わるものだと断言するには、さらに多くの検証が必要です。
しかし、少なくとも今回の結果により、WAMとは異なる道筋でPrologコンパイラを構成できる可能性が見えてきました。
人間とAIが縦糸と横糸を紡ぐように、新しい研究を進めていく時代が始まっているのかもしれません。