KL1 による並列プログラミング 早稲田大学理工学部情報学科 上田研究室 4 年 高木祐介 takagi@ueda.info.waseda.ac.jp 1999 年 10 月 5 日 Copyright, 1996 © Dale Carnegie & Associates, Inc.

発表の概要 KL1 の概略 マルチ集合の演算モジュールを作る 実装 評価 今後の予定

参考文献 1 並列論理型言語 GHC とその応用 KLIC 講習会テキスト 淵一博 監修、古川康一 溝口文雄 共編、 古川康一 竹内彰一 上田和紀 他 共著、 共立出版、 1987 KLIC 講習会テキスト KLIC システム編、 KL1 言語編 平成 5 年 新世代コンピュータ技術開発機構 平成 7 年 日本情報処理開発協会開発研究室

参考文献 2 1998 年度 情報科学特別講義 III （東京大学理学部） KLIC.info Inside KLIC Version 1.0 、関田大吾、 1998 分散 KL1 言語処理系の設計と実装 五十嵐宏、上田和紀、 1999 http://www.icot.or.jp/

言語のクラス GHC, Flat GHC, Moded Flat GHC KL1 KLIC, KLIJava, KL1j

データ型 アトミックデータ 構造データ 記号アトム symbol [ ] 整数アトム 30000 -1234 ファンクタ f(a,b) 整数アトム 30000 -1234 + - * / mod < > =< >= =:= =\= := 構造データ ファンクタ f(a,b) コンス [a|b] リスト [a,b] = [a | [b | [ ]]]

論理変数 大文字か下線で始まる名前を持つ。 単一代入。値に付けた名前。型を持たない。 値を具体化するには、 純関数型言語の変数。 const (C), final (Java) 値を具体化するには、 値と単一化 (unification) する。 Var = value 具体化済みの変数と単一化する。 Var = Var0 具体化済みの変数を、さらに違う値で具体化しようとすると失敗する。

述語 名前と引数の個数 (arity) で区別される。 節の集合として定義する。 関数、手続き、サブルーチン。 head(Args) :- 条件Goals | bodyGoals. 関数、手続き、サブルーチン。 バックトラックしない。 (cf. Prolog) ガードでの単一化は値を具体化しない。 ゴール（述語呼び出し）の中断。

モジュール 述語の名前空間。 定義の仕方。 :- module main. 他モジュールの述語呼び出し。 お約束。 tty:ttystream(Os) お約束。 プログラム実行の始めに main:main が呼ばれる。

短縮形 単一化ガードゴールは、ヘッドでのマッチングとして書ける。 無条件ガードゴール true の省略。 not(In, Out) :- In=1 | Out=0. not(1, Out) :- true | Out=0. 無条件ガードゴール true の省略。 not(1, Out) :- Out=0. 何もしないボディゴール true の省略。 counter([ ], Count).

通信 ゴール間で変数を共有する。 共有変数を具体化する。（送信） 共有変数の値を見る。（受信） 共有変数が具体化されるのを待つ。（同期） main :- not(1,X), not(X,Y), io:outstream([print(Y),nl]). 共有変数を具体化する。（送信） 共有変数の値を見る。（受信） 共有変数が具体化されるのを待つ。（同期） 未完成データ構造 [a|X] ストリーム通信、サーバ [show(V)|Stream]

ループ 再帰で書く。（末尾再帰） ループ中の局所変数は、再帰述語の引数。 終了節。終了条件をガードに置く。 count_down(0). 継続節。継続条件をガードに置いて、再帰。 count_down(N0) :- N0>0 | N1:=N0-1, count_down(N1).

実行制御プラグマ プログラムの正当性を（ほとんど）変えない。 分散指定 goal @node(NodeNumber) current_node(NodeNumber, NumberOfNodes) ゴール優先度 goal @lower_priority 節優先度指定 alternatively.

並列プログラミングの指針 負荷分散。寝てる人がいないようにする。 管理職優先。 通信は少なくする。 データがノード間を移動しないようにする。

マルチ集合の演算モジュール multi_set encode(L,M), decode(M,L) マルチ集合の外部表現 L を内部表現 M に変換、 M を L に逆変換する。 union, intersection, difference(M1,M2,M) M1,M2 の和集合、積集合、差集合を求める。 contraction(M0,M) 要素の重複を取り除く。 choose(M0,E,M) 任意の要素 E を取り出す。

内部表現の決定 「集合の要素と個数の対」の整列リスト 各ノードの担当データを決めておく。 担当データリストの先頭要素に、担当ノード番号を置いておく。（オリジナル）

評価 10 回計測の最頻値を取った。 10 回の最頻値が複数あったら、最頻値が一つになるまで計測。 複数の最頻値の平均の方が良かったか?

今後の予定 randset.kl1 は、負荷が軽すぎるので、ドライバを変えて性能評価してみる。 卒論は分散。以下 2 案。 KL1j のコンパイラを取りあえず作って評価する。 分散アプリケーションを作ってみて、プログラミング環境を評価する。