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

(3) 帰納的な並列記号処理のための
  プログラミング環境の開発

研究代表者:佐藤 泰介 教授
      東京工業大学 大学院 情報理工学研究科




[目次]

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


[研究の背景]

増大した計算機パワーをより有効に使うターゲットとして並列帰納情報処理 が有望であると考えられる。これは生データを解析して背後の規則性をシン ボリックにルールとして抽出する過程を帰納的情報処理と名付け、それを並 列処理により高速に実行しようとするものである。

既に帰納的な記号処理のパラダイムとして HMMやボルツマンマシンによるパ ターン認識、ID3 のような機械学習、ILPによる帰納的プログラミング、GA/ GP によるシステム同定あるいはデータベースマイニングなど多くのものが 開発されている。しかしそれらは無関係に発展して来たものであり統合化や 並列インプリメンテーションへの関心も低いままに留まっている。本研究は 上に挙げた各分野を包括するの共通の理論基盤を開発しつつ、並列記号処理 のためのプログラミング環境を整えることにより知能の帰納的側面を工学的 に実現することを目指している。

しかしながら共通の理論基盤の開発(プログラムと帰納学習の意味論レベル の統合を最初の一歩と考えている)は未知の部分が多いため十分な理論展開 までにはかなりな時間が予想される。 一方並列処理に関しては ICOTで開発 されたFGHC、KL1/KLIC などの処理系の存在を始め手がかりも徐々にに整い つつある。従って本提案では提案の短期的性格を考慮し並列プログラミング の具体化を主たるターゲットとする。

振り返ってみると並列プログラミングの支援環境は着実に進歩しているが、 多くのプログラマにとって、未だ敷居の高い存在であることに変わりはな い。ハードウェア技術の進歩により、並列コンピュータは誰でも入手でき るようになったが、それに比べソフトウェア技術の進歩は遅々としている。 プログラマなら誰でも並列プログラミングに取り組めるというレベルには 達していない。

並列プログラミングを容易にする試みとして、ICOT でも KL1 の開発が行 われ、 数々の成果をあげてきた。 しかし、現在および近未来の並列コン ピュータシステムの普及状況を考えると、スクリプト言語程度の手軽さで 容易に並列プログラミングに取り組める支援ツールの開発が切に望まれる。


[研究の目的]

本研究の狙いは、

であるが、前の二つに関しては「研究の背景」で述べたような状況 - 特に、 大部分のプログラマが、 並列プログラミングの初心者である点 - をふまえる 必要がある。

これらの目標を達成するための一つの有望な技法が、Visual Programming である。 本研究では、Visual Programming 方式に基づき、並列プログラ ミングに最低限必要な技能の修得が容易であり、しかも、熟練プログラマ にとっても有益なプログラミング環境の構築を当面の目的とする。

より具体的には、 FGHC あるいは KL1 をターゲットとした Visual Programming 環境を構築する。ただし、FGHC または KL1 のプログラム ---す なわち、ガード付きホーン節の集合--- を、単に視覚的にプログラマに提示す ることが本研究の目的ではない。本研究では、近年発達したオブジェクト指向 設計法やパタンなどの考え方、Visual Languages や GUI の研究から得られた 知見などを参考に、 並列プログ ラミングのあり方を根本に戻って考え直す。 ターゲットとして FGHC または KL1 を利用するのは、並列プログラミング言 語として充分な表現力を持っており、しかも、KLICという高性能で移植性にす ぐれた処理系が存在するからである。初心者が直接利用する並列プログラミン グ言語として、KL1 がすぐれているとは、必ずしも思われない。


[研究の内容]

本研究の中心的課題となるのは、並列プログラムとその挙動をプログラマに対 して視覚的に提示する部分の基本設計、及び共通の理論基盤としての並列処理 に適合する帰納的記号処理の意味論の研究である。

前者に関しては現在予備的に検討を進めているが、 次のような点が重要となる。

表現の局所性
プログラムおよびその実行状態に関する情報は、コンピュータのディスプレイ という限られた領域に、図形とテクストの集まりとして提示される。プログラ ムの全体を一度に提示することは到底不可能であり、プログラマは、ディスプ レイ上の情報だけを頼りに、プログラミングやデバッグなどの作業を行う必要 がある。 したがって、プログラムの一部に関する局所的な情報だけから、 そ のプログラム部分の意味/挙動を容易に推察できる必要がある。

このような局所的表現の単位として、プロセスあるいは並列オブジェクトは自 然なものである。プロセスを単位として図形表現を行った場合、問題となるの は、 プロセス間に共有資源が存在する場合である。 このような場合、資源を 共有するすべてのプロセスの挙動を知らないと、プログセスの意味を理解する のは困難である。したがって、共有資源は少なければ少ないほど、局所的な表 現の了解性は高くなる。

本研究で追及するのは、 状態を持ったオブジェクトの共有をある程度許しつ つ、 しかも、 本質的には共有が必要でない状況においてはreferential transparency が成り立つような図形/テクスト表現の開発である。

スケーラビリティ
前項とも関連するが、限られた面積のディスプレイ上に、大規模なプログラム の構造をいかに表示するかが、 Visual Programming の大きな課題の一つであ る。本研究では、プロセスという構成単位を、ストリームで結合することによ り、より大きなプロセスを作成する方式を基本とする。 これは、FGHC や KL1 で通常用いられるプログラミング技法である。

さらに、パタンやフレームワークに相当する、より大きな構成単位を導入する ことも考えられる。パタンやフレームワークの図形表現については、今後の検 討課題である。

動的な挙動の静的な表現
Visual なプログラミング環境であろうと、古典的なテクストベースのプログ ラミング環境であろうと、プログラムが静的な図形やテクストにより表現され ることに変わりはない。一方、プログラムの実行は、本質的に動的である。動 的な挙動を静的な表現に押し込めざるを得ないところに、プログラミングの難 しさがある。

本研究では、人間の認知能力の限界を重視し、プログラムはあくまで静的に表 現する。プログラムの諸側面のうち、自然に静的に表現できるものについては、 静的な図形/テクスト表現をあたえ、どうしても動的にしか表現できない側面 については、書き換え規則の形で表現することにする。

オブジェクト指向設計法などとの関連
近年、さまざまオブジェクト指向設計法が提案されており、それにともないプ ログラムの設計段階で描くべき図についても、ある程度標準的なものが定まり つつある。たとえば、オブジェクト間の関連の図、データフロー図、オブジェ クト内の状態遷移の図、イベントのトレース図などが提唱されている。

本研究では、このようなプログラム設計段階の図表現に関する研究の成果を重 視する。すなわち、プロセス間ネットワークの初期化、プロセス内の状態遷移、 ストリームの内容の変化などを、オブジェクト指向設計法で使われるのと類似 の形式の図で表現する。 FGHC や KL1 では、ガード付きホーン節という単一 の形式ですべてを表現しようとしたが、本研究では、複数の形式の図を使う。

一共通の理論基盤としての帰納的記号処理の意味論の研究については、確率論 とホーンプログラムの最小モデル意味論の融合した分布意味論が基本となると 考えている。分布意味論とは確率論とホーンプログラムの最小モデル意味論を 融合させたものであるり、最小モデルを成分が0または1の無限次元の確率ベ クトルの実現値としてとらえる。分布を与えられたデータから推定することが 主要な課題であるが、その推定は数値計算と記号処理が混在する並列度の高い プロセスとなることが予想される。分布意味論は生まれたばかりであるので、 さしあたり分布意味論の様々な具体化、例えば

  1. HMMなどの確率オートマタの一般化
  2. 強化学習への適用
  3. abductive programming との融合

などが取り組むべきテーマとして挙げられる。

[ソフトウェア成果]

作成されるソフトウェア名称
KLIEG1 システム

そのソフトウェアの機能/役割/特徴
KLIEG システムは、プロセスとストリームの概念に基づく並列プログラミング をおこなうための Visual Programming 環境である。KL1 と比較すると、次の ような特徴がある。

抽象化のレベルが高い
プロセスとストリームを基本とした計算モデルを提供している。

論理変数を可能な限り排除する
データフローの向きがわかりやすくなる。また、不必要な共有を排除すること により、プログラムの了解性が高まる。

目的に応じて複数の形式の図を用いる
プロセス間ネットワークの設定とプロセス内の状態変化を表現するために、 KL1では、同じ形式のガード付きホーン節を使うが、KLIEG では異なる形 式の図を使う。特に、ネットワークが静的または準静的な場合には、ネッ トワークの形に対応した図形表現を用意。

また、既存の Visual Languages などと比較とすると次のような特徴がある。

単純なデータフローでもコントロールフローでもない表現
並列プログラミング用の Visual Languages には、データフローを図形で表す ものが多い。KLIEG もある意味ではデータフローを基礎とするが、必要なら論 理変数を用いることもできる。

ソフトウェア工学的知見を利用
オブジェクト間の関連図、オブジェクト内の状態遷移図などに相当する複数の 形式の表現を導入することにより、オブジェクト指向設計法などでよく使われ る図と似た表現が可能となる。

静的な図と動的な図の分離
デフォルトでは静的という考え方にのっとり、図は可能な限り静的に記述する。 どうしても動的な要素が必要な場合だけ、図形で表現した書換え規則を用いる。


www-admin@icot.or.jp