平成７年度 委託研究ソフトウェアの 提案

(4) KL1プログラム開発支援ツール

研究代表者：上田 和紀 助教授
　　　　　　早稲田大学 理工学部 情報学科



［目次］

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

［研究の背景］

並列論理型言語のプログラミングとその効率的実行にとって、モード解析と呼 ばれる技法は、非常に基本的な情報を提供する。モード解析とは、並行論理プ ログラムのデータの流れや通信プロトコルに関する性質を、静的に解析するも のである。これは研究代表者によって1990年に提案され、1994年までに理論的 な整備はほぼ完了した。抽象解釈に基づくモード解析の研究は多いが、本体系 の特徴は、他の言語に見られる型推論と類似のアルゴリズムに基づいており、 単純であってしかも大規模プログラムへの適用が容易な点である。

モード解析の実用面については、1994年度までの研究で、KL1言語特有の機能 の解析技法の検討、およびモード解析の基本アルゴリズムのKL1による実装が 進み、モード体系の実用化に向けて進展した。しかし、実際のKL1プログラム に適用したときに生ずるであろう種々の問題点を検討する段階にはいたってお らず、まだ一般のKL1プログラマが利用できるシステムは完成していない。

［研究の目的］

モード解析は、並行論理プログラムの実行時の情報の流れに関する性質に関す る基本的な情報を提供するもので、多くの言語の静的型体系と同様の重要性と 役割をもつ。

モード解析には、

(a)プログラムの静的デバッグ、
(b)プログラミングスタイルのチェック、
(c)最適化、
(d)プログラム解析の基礎情報の提供、
(e)動的デバッグのための基礎情報の提供、

などさまざまな応用がある。解析系の核部分は、このいずれにもほぼ共通に用 いることができるが、本研究では、まず静的デバッガを完成させ、それを発展 させてスタイルチェッカの作成することを目指す。「良い」KL1プログラミン グのガイドラインが広く流布していない現状を考えると、KL1プログラマに対 して、ツールの形でプログラミングスタイルのガイドラインを提供することは 非常に重要である。

また、本解析系自身は、かなり複雑なグラフ構造を用いる。これをKL1のプロ セス構造を用いて記述し、KLIC処理系で実行することは、複雑なプロセス構造 の記述実験としての意義をもつ。また、これを完全にwell-modedなプログラム として記述することは、モード体系の下でのKL1の記述力の確認という意義も もつ。

［研究の内容］

現在稼働している実験的モード解析系を発展させることによって、KL1のため の静的デバッグ環境およびスタイルチェッカを構築する。具体的には、次のよ うな機能を順次検討し、実現する：

(a) KL1特有の言語機能の取扱いの検討と実現

(b) 分割解析および結果表示のための、グラフ入出力機能の実現
本モード解析系は、プログラムの分割解析が容易であることが大きな特徴で ある。分割解析のためには、プログラムモジュールごとの解析結果を外部に 保存する機能と、読み出す機能が必要である。また、解析の中間結果や最終 結果をプログラマに提示するために、よりユーザフレンドリな入出力機能も 設計、実現する必要がある。解析結果のモードグラフの構造は相当複雑にな りうるので、その入出力方式は自明ではない。

(c) モード宣言機能の検討、実現
本モード解析系のもう一つの特徴は、モード推論、モード宣言、モード検査が 同一の枠組でできることである。また、モジュールインタフェースとなる述語 のモードが宣言できることは有用だと考えられる。そこで、モード宣言のため の言語機能を検討し、実現する。

(d) 性能改善と並列実行の検討
現在の基本アルゴリズムの実装は、実際に扱うグラフ構造やモード制約の統計 的特性に応じて最適化してはいない。そこで、各種のプログラムの解析を通じ て性能改善を図る。特に、データ表現の再検討や、不要な逐次性の除去を行な う。また、本解析は、(成功する限り)それほど計算時間のかかるものではない が、性能改善の一環として、並列実行の可能性について検討を行なう。

(e) モードづけできないプログラムのの解析
既存の多くのプログラムは、大体においてwell-modedに書かれている半面、部 分的にill-modedな部分を有すると考えられる。この場合、プログラム全体と してill-modedである、という解析結果を提示しても、あまり有用でない。そ こで、ill-modedなプログラムに対しては、ATMSの考え方を利用し、ill-moded である理由の「良い」説明を見つけ、プログラマに提示するようにする。

(f) 動的デバッグ環境の検討
静的デバッグ環境が稼働を始めれば、それを用いることにより、本質的に動的 デバッグが必要なプログラムエラーに対して、今までより高度なデバッガが実 現できる可能性がある。そこで、静的デバッグ環境の開発状況をみて、動的デ バッグ環境の検討を開始する。

［ソフトウェア成果］

(1)作成されるソフトウェア名称
Klint

(2)そのソフトウェアの機能／役割／特徴
klint は、KL1プログラムを構成する述語の引数や変数が、どのような通信プ ロトコルで使われているかを静的に解析するツールである。この解析を、モー ド解析ともいう。モード解析に成功したプログラムは、実行時にプロトコルの 不整合によるユニフィケーションの失敗が起きないことが保証される。このた め、今まで実行時デバッグによって除去していた誤りの多くが、静的に除去で きるようになる。

このようにモード体系は、強い型体系と同様な工学的意義をもっており、実際、 これまでの予備実験によって、多くの誤りが静的に除去できることが経験され ている。

klint は、モードづけができるプログラムに対しては、各述語のプロトコルを 出力し、モードづけできない場合は、その理由を解析して出力する。モードづ けの機能は、Prolog処理系に見られる singleton 変数の警告機能を含んでい る。さらに、可能な場合、プログラミング・スタイルに関する改善提案を出力 する。

klint は、大規模プログラムにも対応しており、通信プロトコルに関するモジュー ルインタフェースを宣言したり、モジュールごとにモードを解析したりするこ とが可能である。


www-admin@icot.or.jp