(14) KLIC 上の MGTP 処理系に関する研究

［目次］

1. 研究の背景
2. 研究の目的
3. 研究の内容
4. ソフトウェア成果

［研究の背景］

現在、演繹データベース処理のような有限領域の問題を対象とするグランド版 MGTPと、数学の定理証明のような無限領域の問題を対象とするノングランド版 MGTPの二種が開発されている。両版ともPIM/m-256PEシステム上でほぼ線形に 近い良好な並列性能を達成し、有限代数における未解決問題を解く事にも成功 している。

［研究の目的］

今後より多くの人達に利用してもらうためには、先ず可搬性に優れたシステム を提供し、そしてそれを使い勝手の良いものに発展させていくことが必要であ ると考える。本研究の第一の目的は、KLIC版MGTPをより使いやすいシステムに 成長させ、MGTPを普及していくことにある。KLIC版をその基礎に置くのは、可 搬性に優れているからである。

使いやすさの探求と共に、MGTP上で編み出されてきた推論技法や推論の拡張手 法をシステムに採り入れ、定量的に評価することも重要であると考える。これ によってMGTPの多様化を図り、より魅力あるシステムにしていくことを目指す。 また、開発途上で作成される様々なKLICプログラムの部品の内、汎用性がある ものについては、KLICユーティリティとしてIFSとして登録していく。

［研究の内容］

(1) 既システムの整備：

可搬性を高めるために、Prolog上で稼働している変換部をKLICもしくは Perlといったより可搬性に優れるシステム上で動くように書き換える。また、 推論方式別に提供していた推論部を一つに統一化し、利用の簡便化を図る。

(2) NHMの導入：

MGTPの実用性を高める為に重要な、探索空間の枝刈り手法の一つである NHM(ノンホーン・マジックセット)法をMGTPに導入し、これに基づく変換シス テムを作成する。またその枝刈り効果について、定量的に調べる。

(3) MGTPプログラミング環境の開発：

MGTP節でのプログラミング効率を高めるために、デバッガとMGTPの計算過 程の視覚化システムを作成する。前者については、スタイルチェッカやトレー サ等のデバッギングに有用なツール群を作成していくとともに、ボトムアップ 定理証明系のデバッグモデルについても考察する。後者については、現在ある 視覚化システムを可搬性を考えてTcl/Tkに移植するとともに、新たに、MGTP証 明図や連言照合計算の視覚化にも取り組む。

(4) 推論記述言語としての拡張：

MGTPを単なるモデル枚挙システムとしてではなく、各種推論システムのプ ラットフォームとして利用するために、MGTP節を推論記述言語として拡張し、 実装を行う。拡張によって、推論規則だけではなく推論の制御(KLICのプラグ マのようなもの)も記述できるようにする。

(5) 推論速度の高速化：

MGTP節からKL1節への変換の最適化、および動的に生成されるデータへの アクセスを高速化するために基本ルーチンのC化を行う。また、並列化による 高速化を図るために、分散KLIC上での実装、特に負荷分散手法についての考察 および実験を進める。

(6) その他：

KLIC上でプログラミングを進めていく上で有用なツールやライブラリ群を 適宜作成していく。これらは主としてMGTP開発の効率を高める目的で作成され るものである。当面、ガード述語及びボディ述語(ユーザ定義述語を含む)の実 行を対話的に行う機能、インクリメンタルにコンパイル・リンクを行える機能 などを具備するKLIC実行環境(KLIC\_RUNと呼ぶ)を構築する。

［ソフトウェア成果］

作成されるソフトウェア名称：

KLIC-MGTP & KLIC-RUN

そのソフトウェアの機能/役割/特徴：

MGTPの基本機能は(一階の)入力節集合のモデルを枚挙することである。枚 挙にはもれがないので(完全性)、枚挙されたモデル数が０の時は、与えられた 節集合は充足不可能であることがわかる。このことからMGTPは、一階の定理証 明系として使用できることが分かる。

モデルは、節集合を満たす領域(集合)であるから、問題の解が満たすべき 条件(制約)を節集合で記述した場合、枚挙されたモデルは、解そのものとなる。 モデルは節の入力順に依存せず求まるので、宣言的に問題の解法が記述できる。

一方、MGTPの入力節は、条件式とその成立時のアクションを記述したもの と手続き的に解釈することができ、MGTPをプログラミング言語とみなすことが できる。このことは、MGTPの潜在的な能力の高さを示しており、実際に推論系 記述言語として利用されている。またユーザは、並列実行の為の指示をMGTPの 節記述に埋め込むことができる。

このようにMGTPでは、宣言的記述と手続き的記述の双方が可能である。ま た、KL1では失われた完全性を保持しているのにもかかわらず、計算機構は極 めて単純な原理に基づいており、プログラムがコンパクトで手を加え易いのが 特徴である。この単純さが故にMGTPには、様々な使いよう(汎用性)があるので ある。MGTPはそれ単体のみではなく、より大きなシステムの部品として利用す る事もできるオープンなシステムである。

KLIC実行環境(KLIC-RUN)においては、できるだけLispやPrologのような感 覚でユーザ定義述語の走行・デバッグを行える機能を備える。また、入出力に 関するユーティリティの整備を図る。