(23) KL/1による宣言型三次元アルゴリズム アニメーション システム

［目次］

1. 研究の背景
2. 研究の目的
3. 研究内容
4. 研究体制／研究方法
5. 想定されるソフトウェア成果

［研究の背景］

従来より並列アルゴリズム開発や並列プログラミングは、デバッグ・チューニング・ソフトウェアメンテナンスなどが困難とされてきた。KL/1などの従来の言語と比較して並列性の抽象度の高い言語の登場によって、一定のの進歩はあったが、それでも(言語システムのみでは)全面的な解決には到らず、プログラミング環境、特にその中でも視覚的なプログラム開発支援は大変重用視されている。しかも近年はグラフィカルユーザインタフェース(以下,GUI)のアニメーション・三次元・その他のマルチメディア情報などを扱える先進的GUIシステムの登場とあいまって、プログラミング支援のための視覚化システムも一層の高度化が要求されている。

しかし、GUIや視覚化システムがそのように高度化するにつれ、アプリケーションのデータ・視覚的表現・その両者の対応関係が複雑化し、有効な視覚化を得るには多大な開発コストが要求されている。特に、三次元のアニメーションを活用した並列プログラムの視覚化システムでは、システム自身が複雑であるのみならず、ユーザが自身の並列アルゴリズムや並列プログラムの視覚化を三次元やアニメーションの機能をフルに生かして行うのは大変開発コストがかかってしまう。 AVSなどの計算の結果をデータフロー的に視覚化するようなシステムはあるが、それらは動的なプログラムの実行状態を表示するようには作られていない。並列プログラムの視覚化システムとしてはPolkaなどがあるが、三次元を含む複雑なデータ構造の視覚化には適していない。

［研究の目的］

我々は、過去より「絵・抽象的データ間の宣言的双方向変換の枠組」という、新しいGUIの構築パラダイムを提案し、宣言型のGUIシステムTRIPなどの各種システムを開発し、GUIに特化した制約解消技法や、例示からの制約の汎化手法などのソフトウェア基盤技術の研究を行ってきた。 本研究ではそれらの研究をベースとして、KL/1を含む並列言語で書かれたアルゴリズムやプログラムを、宣言的な視覚化規則により三次元のアルゴリズムアニメーションとしてユーザに提示するシステムTRIP-3DAを、KL/1を宣言規則の変換エンジンとして用いて開発する。ユーザは簡便な宣言的な規則によって様々な三次元の視覚化技法やアニメーション技法を用いることが可能となるため、 Visual Janusのような、従来の並列プログラム視覚化システムのように、ある特定の視覚化のスタイルや技法に縛られることがない。また、複雑なアニメーションなども、簡潔な記述によって可能であり、システムのデフォルトの視覚化も容易に修正できる。

このように、本システムを開発することにより、アルゴリズムやプログラムに適した様々な視覚化が容易に行えるようになることにより、並列アルゴリズムやプログラムの開発・デバッグ・チューニング・解説・教育などを高度に支援することが可能になる。TRIP-3DAは、KL/1やOpenGLなどの汎用のプラットフォーム上で高速に動作するように開発するため、IRISなどのグラフィックスワークステーションのみならず、通常のワークステーションや高性能PC上で三次元アニメーションを用いた並列アルゴリズムやプログラムの視覚化が行える。

［研究内容］

我々の従来からの研究の特色は、以前より提案している「絵・抽象的データ間の宣言的双方向変換の枠組」の時系列方向の拡張により、簡単な宣言的記述のみで、アプリケーション内のデータの動的挙動をアニメーションとして変換することができ、さらにGUI用の、動的な制約の連立が可能で、高速な制約解消アルゴリズムを実現するアルゴリズムDetailにより、レイアウトや動きに関する制約解消が行われることによって、アニメーションが半自動生成されることにある。

具体的には、このモデルにおけるアプリケーションデータの視覚化は，アプリケーションのデータ表現(AR)から 絵のデータ表現(PR)への一連の変換と考える．逆に，ユーザの絵に対する操作/変更のアプリケーションデータへの反映は， PR から AR への変換として捉える．抽象構造表現(ASR)と絵構造表現(VSR)とは，この変換をAR や PR に依存せずに実現するためのもので，それぞれ AR と PR との構造を表すための一般的な中間表現である．つまり， AR=>PR の変換を， ASR=>VSR の変換で表現する．また，それは宣言的に対応規則によって記述できる．例えば、グラフ構造の視覚化のためには、以下のような規則を宣言する:

　node(X) :- 　
　　circle(X,15,［］),　
　　label(l(X),X,［］),　
　　contain(X,l(X),0,［］).　
　edge(A,B) :- 　
　　connect(A,B,center,center,［］),　
　　adjacent(A,B,1).　

これに対し、

　node(a). node(b). ... node(f). % ノード　
　 　edge(a,b). edge(a,c). 　　　% エッジ　
　　...　
　edge(c,f). edge(d,b).　

のようなグラフの具体的なデータを与えると、自動的にグラフが描画される。

今回研究開発するシステムにおいては、このマッピングの部分にKLICを使用することにより、KL/1で書かれた並列アルゴリズム及びプログラムの視覚化に対応できるようにする。また、三次元の視覚化用のVSRプリミティブを用意し、高速な三次元表示に対応する。

さらに、アニメーションを扱うため，双方向変換モデルを拡張する。アニメーションの実行を，アプリケーションの実行にともなって変化していくアプリケーションデータの列，それに対応する図の列，及びそれらをつないでいく「操作」の列としてとらえ、アプリケーションが何らかの「操作」の実行をすると，モデル内の各データはそのデータ表現上での対応する「操作」によって次の状態に移り、同時に絵のデータも対応する「操作」によって，次の状態に移る．ここで、抽象構造表現 (ASR)上での操作を「抽象操作」絵構造表現(VSR)上での操作を「遷移操作」と呼ぶ。それぞれの「操作」間を変換規則で対応づけ，遷移方法の指定ができるようにすることにより、アニメーションの作成者は，この二つの間の対応規則を与えることで様々なアニメーションを作成できる。また、ユーザが指定しない部分は、操作のそれぞれの前後のモデル上でのデータの視覚化をキーフレームとして、その間を保管することにより、アニメーションのデータを自動生成する。

具体的的には、先のグラフ上でのなんらかのデータの遷移を、ノードの大きさの変化 (データがあるノードが大きい) で表すとすると、

traverse(X,Y) :- shrink(X, ［smooth］), enlarge(X, ［smooth］).　

といった遷移操作の変換規則を指定するだけで良く、ノードのサイズの変化による配置の変化などは、制約解消系が自動的に行う。また、本例では［smooth］といったアニメーションに対する属性を付加することにより、アニメーションの遷移時にそれぞれがスムースに(この場合は線形な大きさの変化)かつ同時に大きさの変化のアニメーションが起こることになる。

今回研究開発するシステムにおいては、このようなアニメーションの遷移則による生成を行う部分をKLICに移植することにより、並列アルゴリズムの視覚化を行えるようにする。特に、並列アニメーション時において、複数の遷移がある時点で同期するsynch()などのVSRプリミティブを用意することにより、ある物体が遷移中に別な物体が動作を始める、といった並行性を視覚化することが容易に可能になる。

最後に、サンプルプログラムとして、幾つかの並列アルゴリズムの三次元アニメーションの視覚化を通じ、有効な視覚化法を探る。

(以下が、TRIP関連の参考文献の一部)

［1］ Shin Takahashi, Satoshi Matsuoka, Akinori Yonezawa, and Tomihisa Kamada.
A General Framework for Bidirectional Translation between Abstract and Pictorial Data. In Proceedings of the ACM Symposium on User Interface Software and Technology (UIST'91), Vol. 4, pp. 165-174, November 1991.

［2］ Satoshi Matsuoka, Shin Takahashi, Tomihisa Kamada, and Akinori Yonezawa.
A General Framework for Bi-directional Translation between Abstract and Pictorial Data. ACM Transactions on Information Systems (TOIS), Vol. 10, No. 4, pp. 408-437, October 1992.

［3］ Shin Takahashi, Ken Miyashita, Satoshi Matsuoka, and Akinori Yonezawa.
A framework for constructing animations via declarative mapping rules. In Proceedings of the 1994 IEEE Symposium on Visual Languages (VL'94), Vol. 10, pp. 314-322, 1994.

［4］ Ken Miyashita, Satoshi Matsuoka, Shin Takahashi, and Akinori Yonezawa.
Declarative Programming of Graphical Interfaces by Visual Examples. In Proceedings of the ACM Symposium on User Interface Software and Technology (UIST'92), volume 5, pages 107-116, November 1992.

［5］ Ken Miyashita, Satoshi Matsuoka, Shin Takahashi, and Akinori Yonezawa.
Interactive generation of graphical user interfaces by multiple visual examples. In Proceedings of the ACM Symposium on User Interface Software and Technology (UIST'94), volume 7, pages 85-94, 1994.

［6］ Hiroshi Hosobe, Ken Miyashita, Shin Takahashi, Satoshi Matsuoka, and Akinori Yonezawa.
Locally simultaneous constraint satisfaction. In Proceedings of the Second Workshop on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science. Springer-Verlag, 1994.

［研究体制／研究方法］