SCBM-Prolog 動作報告 ― 9Queensの実行に成功

WAMとは異なる発想に基づくPrologコンパイラの設計・実装を進めています。

SCBM方式（Sasagawa Continuation Backtracking Model） と名付けた独自の方式です。

ロビンソンのSLD反駁に基づき、双方向リストとGCC拡張のcomputed goto（計算型goto）を使用して、Prolog特有の制御構造を実現しています。

このたび、9Queensが動作するようになりましたので、その成果を報告します。

9Queensの全解

下記は、9Queensの解を画面に表示した際の出力の一部です。

9Queensの全352解が得られ、解に重複がないことは、ChatGPTを利用して検証しています。

9Queensの実行速度

下記は、AMD Ryzenを搭載したLinuxマシンでの測定結果です。

解の画面表示を行わずに、9Queensの実行時間を計測したものです。

現時点では、SWI-Prologのほうが約1.5倍高速です。

それでも、SCBM-Prologは約10 MLIPS（1000万LIPS）の性能を達成しており、まずまずの結果だと考えています。

WAMとの違い

現在のProlog処理系では、David H. D. Warren氏が考案したWAM（Warren Abstract Machine）に基づく実装が広く採用されています。

WAMは非常に優れた設計ですが、その仕組みは複雑であり、理解や実装には相応の労力が必要です。

一方、SCBM方式は、双方向リスト上に証明過程を線形化し、成功継続と失敗継続を統一的に扱う、比較的単純な仕組みです。

このため、個人が独自のPrologコンパイラを開発する際の、一つの土台になりうると考えています。

今後の開発

現在、カット（!）、選言（;）、非決定性を持つ組込み述語（例えばappend/3）などの実装が残っています。

2027年10月の完成を目標に、引き続き開発を進めています。

全体の設計と基本方針の決定は私自身が行い、細部の処理や部品の改良にはAIを活用しています。

今後、さらに実行速度を向上させるためには、生成される機械語の効率や、キャッシュメモリの有効活用などが重要になります。

こうした低レベルの最適化については、AIの持つ知識やコード分析能力が大いに役立つと期待しています。

最終的には、SWI-Prologに比肩する実行性能を目指します。

ソースコード

SCBM-Prologは、GitHub上でオープンソースとして公開しています。