今回、作成したプログラムは、Prologで記述した。その理由は、一階述語論理 の全解計算の手法にQSQR法を用いた際、そのアルゴリズムにPrologによる計算 方法を参考にしたからである。これは、速度の面では他の高速な言語に比べて 不利だが、今後のQSQR法のプログラム作成のため、アルゴリズムを把握する上 で重要であり、また、比較対象となるPrologの計算とも比較が容易である。
また、エミュレーションとしての効果を期待でき、どのような状況でQSQR法が 有利なのかを調べることができる。
なお、ここでのQSQR法は単に全解を出力するだけでなく、中間ノードも含めて ゴールの証明木を出力する必要がある(命題版NBP法の入力とするため）。この ため、これまでとは違った実装上の問題が生じている。
現在の実装では、QSQR法と、バックトラックを用いて問題を解くProlog計算を 比べると、問題によってどちらが速いかが変わり、QSQR法の利点が得られてい ない。これは、もともと無駄な計算が少ない問題ではQSQR法の利点があまり生 きず、またメモリの使用量の大きさから、メモリキャッシュなどのページフォ ルト量により、特に遅くなることがあるからだと思われる。
以下は現在までに見つかった、QSQR法の速度が思ったより上っていない理由で ある。
QSQR法ではPrologなどと違い、ある解を計算するのに直接には 必要のないノード情報も保持する必要がある。それゆえ、大きな問題になれば なるほど使用メモリ量はPrologの推論に比べて不利になる。この使用メモリ量 の増大はキャッシュの関係から直接速度に関係し、QSQR法の大きなボトルネッ クになっていると思われる。しかし、あるノードの全ての答をリストで上位ノードに返すことはゴール指向 ボトムアップ推論を行なう上で必要な機能であり、現在のところまだ良い解決 法を見いだしていない。
QSQR法はすでに解いた問い合わせやその答を常に保持すること によって、再計算を防いでいるが、問題によるとこのリストが爆発的に増える ことがある。QSQR法に限らず、Prologでも不利な点には変わらないのだが、QSQR法は解き方 で損するだけでなく、親子関係知識の問題の場合を例にとると、QやLのリスト にすべての親子関係を保持しつつ問題を解いていかなければならない。これは 巨大な無駄な情報をメモリに保持しておくことになる。
これゆえ効果的にQSQR法を用いるには、ノードの計算順を選ぶ必要があること が分かる。例えば述語の選択関数を左優先でなく、引数の中に変数が少ないも のを優先して解いていけば、より効果的な推論が行なえると考えられる。
一度解いた問い合わせ(Query)を保持しておくことがQSQR法の特 徴であるが、このQueryの保持方法も多少問題がある。今回のプログラムでは、Qリストを検索する前に問い合わせの変数のバインディ ングをすべて調べ、unification後に元の問い合わせで変数だった部分が具体 値にunifyされている時には即座に失敗させて、次のunificationを試みるよう にしている。これは効率的ではなく、Prolog以外のもっと低レベルな言語で実 現する際にはより効率的な検索が可能になると考えられる。