はじめに
これから1年計画で、SCBM-Prologの新しい開発プロジェクト「YAMATO計画」を開始します。
2026年4月ごろからSCBM方式の研究開発を続けてきました。数多くの試行錯誤を重ねましたが、SCBM3では複雑な再帰とバックトラックの組み合わせを完全には処理できませんでした。
そこで、これまでの経験を生かし、データ構造を根本から見直すことにしました。
今回の基本方針は非常に単純です。
SLDリゾルーションの証明過程をそのままデータ構造として表現し、それをC言語のgotoによって高速に実行する。
これがYAMATO計画の核心です。
1. SCBM3で直面した問題
SCBM3では、成功継続と失敗継続をスタックで管理していました。
通常の述語呼び出しでは問題なく動作します。しかし、再帰が深くなり、何度もバックトラックを繰り返すと、成功継続が途中で失われてしまう問題がありました。
本来、バックトラックによって以前の選択点へ戻った場合でも、その後に実行すべき述語への接続は保持されていなければなりません。
ところが、スタック上で成功継続を積み直したり破棄したりする過程で、必要な接続が失われてしまうのです。
この問題を解決するために、成功継続の保存方法や変数ポインタの復元方法など、非常に多くの試行錯誤を行いました。
しかし、満足できる解決には至りませんでした。
そこで、スタックを中心とする制御構造そのものを見直すことにしました。
2. 双方向リストによる証明過程の表現
YAMATOでは、述語の呼び出しを一つのオブジェクトとして扱います。
そして、これらの述語オブジェクトを双方向リストで接続します。
各オブジェクトには、実行に必要な状態を保存します。
- C言語で記述された実行コードへのラベル
- ローカルスタック
- 変数ポインタ
- 引数カウンタ
- ワーキングポインタ
- プルーフカウンタ（証明過程を指すポインタ）
- 成功継続と失敗継続の管理に必要な情報
双方向リストを順方向に辿ることで、次に実行すべき述語を特定できます。
逆方向に辿ることで、以前の選択点を探索できます。
つまり、成功継続と失敗継続を、スタックの位置に依存するのではなく、証明過程の中の接続関係として扱うわけです。
3. 再帰は述語オブジェクトへの置き換えによって処理する
YAMATOでは、再帰を特別な制御構造として扱いません。
例えば、次のPrologプログラムを考えます。
perm1([], []).
perm1(X, [Y|Z]) :-
select1(Y, X, W),
perm1(W, Z).
perm1 が再帰的に呼び出された場合、その呼び出しを新しい述語オブジェクトに展開・置換します。
本体部に複数の述語があれば、それぞれをオブジェクトとして生成し、双方向リストに挿入します。
再帰がさらに深くなれば、同じ処理を繰り返します。
これはSLDリゾルーションにおいて、選択したゴールを節の本体に置き換える操作に対応します。
したがって、再帰の深さに応じた特別な制御を用意する必要はありません。
再帰も通常の述語呼び出しも、同じ証明過程の展開として扱います。
ただし、バックトラックによる再試行に必要な選択点や環境情報は保持します。
4. C言語のgotoによる高速実行
SCBM3で採用したgoto方式は、YAMATOでも引き続き使用します。
述語の処理コードはC言語で記述します。
このコードは、引数のunify、本体部の展開、述語オブジェクトの生成などを行います。
生成されたオブジェクトは双方向リストに挿入され、実行エンジンに制御が渡されます。
実行エンジンはプルーフカウンタを参照し、次に実行するオブジェクトを決定します。
そして、そのオブジェクトが保持するラベルへgotoでジャンプします。
この方式では、述語ごとにC関数を呼び出す必要がありません。
関数呼び出しに伴うオーバーヘッドを避けることで、高速実行を狙います。
なお、ラベルアドレスへの間接ジャンプには、GCCなどが提供するcomputed goto拡張を利用することを想定しています。
5. 成功継続と失敗継続
成功継続では、双方向リストを順方向に辿ります。
次の述語オブジェクトを取得し、保存されているラベルへジャンプして実行を続けます。
失敗した場合には、双方向リストを逆方向に辿ります。
そして、再試行可能な非決定性述語の選択点を探し、必要な環境を復元してバックトラックを実行します。
ここで重要なのは、証明過程の接続と選択点の状態を明示的に管理することです。
SCBM3では成功継続がスタック操作によって失われることがありました。
YAMATOでは、オブジェクト間の接続を保持することで、この問題を構造的に解決しようと考えています。
6. WAMとは異なるアプローチ
一般的な高速Prolog処理系では、WAM（Warren Abstract Machine）がよく知られています。
WAMはPrologを効率よく実行するために設計された抽象機械です。専用の命令体系、レジスタ、環境フレーム、選択点などを利用します。
これに対してYAMATOでは、Prologの基礎となるSLDリゾルーションの証明過程をできるだけ素直に表現します。
基本的な考え方は次のとおりです。
SLDリゾルーションを理解すれば、YAMATOの実行過程も理解できる。
証明過程と実行時のデータ構造が対応しているため、動作を追跡しやすく、デバッグもしやすいと期待しています。
一方で、実行部分にはC言語のgotoを利用して速度を追求します。
WAMと同じ内部構造を採用するのではなく、SLDの構造を維持しながら高速化を目指すわけです。
もちろん、双方向リストの操作やオブジェクト生成にはコストがかかります。実際にどの程度高速になるかは、実装後のベンチマークによって確認する必要があります。
7. YAMATO計画の目標
今回の開発では、SCBM3で得られた経験を最大限に活用します。
最初の目標は、perm1/2 のような再帰と非決定性が組み合わさった述語を正確に実行することです。
そのうえで、複雑なバックトラックを伴うプログラムへ対応範囲を広げ、実行速度も測定していきます。
目指しているのは、単なる高速化ではありません。
SLDリゾルーションに忠実で、理解しやすく、しかも高速なProlog計算モデルです。
おわりに — 2027年10月、地球への帰還
YAMATO計画の完成目標は2027年10月です。
これから仕事が繁忙期に入るため、趣味として少しずつ開発を進めることになります。
SCBM3では半年間にわたって試行錯誤を繰り返しました。うまくいかなかったことも数多くあります。
しかし、その経験によって問題の本質が少しずつ見えてきました。
今度は1年かけて、じっくり取り組もうと思います。
アニメ『宇宙戦艦ヤマト』では、ヤマトは地球を救うため、コスモクリーナを求めて1年間の航海に出発しました。
私のYAMATO計画も1年間の航海です。
2027年10月、コスモクリーナを持って地球に帰還することを目指します。