CMGTPの新実装

従来のCMGTPは、並列化を主目的としたMGTPや一部の問題に特化されたMGTPの 拡張として実装されており、必ずしも最適かつ汎用のシステムとはいえない。 我々は、CMGTPを法的推論等、より広範な応用問題に利用していくことを考え ており、汎用計算機上での効率良い実装を必要としている。

CMGTPの効率的実装の最大の妨げとなるのは、選言による多重環境の問題であ る。(C)MGTPは選言に基づいて場合分け推論を行うが、各場合ごとに保持され る情報について、MGTPにおいては場合分け前の共有情報が保たれるのに対し、 CMGTPでは書換えが生じて共有情報が保たれない。このようなとき、各場合ご とに共有情報の複製を作るのが安易であるが、メモリと処理時間を著しく消費 するのが難点である。実行コストの安い多重環境の実現がまず第一に求められ る。

実は、基本MGTP自体についてもまだ改善の余地が残されている。モデル候補と 節の前件に関する連言照合や、後件の包摂検査はMGTPの処理時間の大半を占め るが、いずれも構造データの集合に対する所属検査を基本演算としている。安 易な実装では、要素数Nの集合を線形リストで実装し、線形探索を行うので、 の計算量となっていた。適切なインデキシングを用いれば、所 属検査は で済むはずである。ただし、多重環境下において高 速な所属検査を行うためにはまた別の工夫が必要であろう。

我々は、場合分けの逐次実行を前提として、幾つかの新しい実装技法を導入す ることにより、従来の基本MGTPをも凌ぐ高能率なCMGTPを実現した。実装には Java言語を用いた。合わせて入力節文法も拡張し、問題記述能力の向上を図っ ている。

以下の新たな実装技法が従来のCMGTP処理系に大きな改善をもたらした。

• 複製によらない多重環境の実現
• Activation-cell による時間所属検査
• 項インデキシング機構による基底リテラルの同一化(次節の項メモリの 改良と連携)

これらの技法は、pure-MGTP自体についても旧版に対しての改善にもなってい る。 表1では、 KLIC-MGTP（項メモリ不使用）、Java-MGTP及び新版Java-CMGTP(New) の実行性能を比較した。 新版は制約処理の拡張機能を有しながら、 従来の(pure-)MGTPに比べても高速化されている。 これは、A-セルという新たな実装技法の導入により、 連言照合、包摂検査、場合分けに伴うオーバヘッド（ただし、pure-MGTPでは 環境複製問題は回避されている）等、 MGTPの基本演算部分において顕著な改善が得られたことを示している。

表2では、 旧版Java-CMGTP(Old)と新版Java-CMGTP(New)の実行性能を比較した。 旧版においては、特に多重環境に関して java.util.Vector クラスの利用と その複製(clone)を採用している点が低効率の主要因となっている。 新版の旧版に対する改善の度合は格段（数10倍に達する）であり、 複製操作が如何に重いかがわかる。

Activation-cell はProlog等の論理型プログラムにおける 差分リストやショートサーキット法など、 論理変数を用いた種々のプログラミング技法の``妙味''と通じるものがあり、 共有部分を有する複数の集合に対する操作等にも応用の効く、 新しいプログラミング技法を示唆するものと考える。