LMNtalからC言語への変換の設計と実装 研究の背景・目的 1G04R013 石川 力 高速なLMNtal実行環境を得ること Java言語による実行時処理系の実装 それを利用するJava言語ソースコードへの変換 C言語による実行時処理系(SLIM)の再設計・実装 それを利用するC言語ソースコードへの変換 (今回のテーマ) 変換器(トランスレータ)の役割 LMNtalプログラム 中間命令列を同じ挙動をする C言語ソースコードに変換 コンパイル後インタプリタの オブジェクトファイルとリンク 中間命令列(参考) LMNtalコンパイラ このルールのマッチング・書き換えは次のような細粒度の命令列に変換できる a b ⇒ a c トランスレータ 中間命令列 a b マッチング始点を選択 リンク先を参照 リンク先の種類を確認 アトムの生成 リンクの繋ぎ替え アトムの削除 インタプリタ(実行時処理系) (1) a (4) C言語ソースコード c (機能を利用) 階層グラフ構造の操作 ルール実行の制御 etc ・・・ (2) a (5) a b C言語コンパイラ c (3) a b (6) a c 実行ファイル 実行結果 この細粒度の命令列を中間命令列と呼んでいる 変換の様子 変換前 変換後 変換前ルール群 変換後ルール群 :- :- :- :- 変換後ルール(C言語関数) 変換前ルール(中間命令列) int trans_rule_1_0(LmnMembrane *TRANS_DATA(0), long TRANS_ATTR(0))‏ { spec [1, 5] findatom [1, 0, 'y'_1] deref [2, 1, 0, 0] func [2, 'x'_1] commit [null, 0] dequeueatom [1] dequeueatom [2] removeatom [1, 0, 'y'_1] removeatom [2, 0, 'x'_1] newatom [3, 0, 'z'_1] newatom [4, 0, 'x'_1] newlink [3, 0, 4, 0, 0] enqueueatom [4] enqueueatom [3] freeatom [1] freeatom [2] proceed [] long TRANS_DATA(1), TRANS_ATTR(1), a1; AtomListEntry *i1; func [ 2, 'x'_1 ] ・・・・・・・ if(TRANS_ATTR(2)!=7) continue; a2 = trans_aritys[7]; func [ 　　　, 　　　] lmn_mem_remove_atom(TRANS_DATA(0), TRANS_DATA(1), TRANS_ATTR(1)); if(TRANS_ATTR(　　　)!=　　　　) $$f; a　　　 = trans_aritys[　　　]; lmn_mem_remove_atom(TRANS_DATA(0), TRANS_DATA(2), TRANS_ATTR(2)); a3 = trans_aritys[8]; TRANS_ATTR(3) = 8; TRANS_DATA(3) = (LmnWord)lmn_new_atom(TRANS_ATTR(3)); lmn_mem_push_atom(TRANS_DATA(0), TRANS_DATA(3), TRANS_ATTR(3)); 中間命令のテンプレート ・・・・・・・ } 各中間命令について処理 速度性能比較 まとめ・今後の課題 SLIMトランスレータ 100倍 SLIM インタプリタ SLIMを利用したC言語ソースコードへのトランスレータを作成し、高速なLMNtal実行環境を得た C言語とは言ってもプログラムの挙動はグラフマッチングと書き換えで動作するモデルであり、C言語らしいものではない これをより効率的な動作をするように改良していくことが今後の課題である Javaによるトランスレータ Java版実行時処理系インタープリット実行での性能を 1としたときのグラフ gen : アトムを単純に生成削除する quicksort : 逆順クイックソート jos : Josephus(ヨセフス)の問題 (リンク繋ぎ替えを多用) lambda : LMNtalにエンコードされたChurch数の累乗演算(総合的な例)

研究の背景・目的 ルールによるマッチング・書き換えの実行 イメージ LMNtalプログラム実行の様子 高速なLMNtal実行環境を得ること 中間命令列 Java言語による実行時処理系の実装 それを利用するJava言語ソースコードへの変換 C言語による実行時処理系の再設計・実装 それを利用するC言語ソースコードへの変換 (今回のテーマ) 中間命令列とは、グラフを操作するための粒度の小さい命令セットである 以下の例は概念を示すためのもので実際の中間命令列とは異なっている (1)‏ findatom [1, 0, 'a'_1] グラフの始点を選ぶ (2)‏ deref [2, 1, 0, 0] リンクをたどる (3)‏ func [2, 'b'_1] アトムの種類を確認する (4)‏ newatom [3, 0, 'c'_1] 新しいアトムを生成する (5)‏ newlink [1, 0, 3, 0] リンクを張る (6)‏ freeatom [2] アトムを消す ルールによるマッチング・書き換えの実行 イメージ a b ⇒ a c の場合 a b マッチング始点を選択 リンク先を参照 リンク先の種類を確認 アトムの生成 リンクの繋ぎ替え アトムの削除 (4) (1) a c LMNtalプログラム実行の様子 (2) a a b (5) c (3) a b y a c c n y c a c n y c c a n (6) a c s t s t s t c c n c c n c c n ルールは細粒度のグラフ操作の命令列(中間命令列)として実行 ルール1 ルール1 u v u v u v ルール1 ルール2 Y a c T Y c a T Y a n Y ⇒ ⇒ B H H B B B グラフ書き換えで計算を進めるため 性能向上のためにはグラフ表現・操作の効率化が重要

変換の様子 中間命令列(参考) 変換後 変換前 変換後ルール群 変換前ルール群 変換後ルール(C言語関数) 変換前ルール(中間命令列) int trans_rule_1_0(LmnMembrane *TRANS_DATA(0), long TRANS_ATTR(0))‏ { spec [1, 5] findatom [1, 0, 'y'_1] deref [2, 1, 0, 0] func [2, 'x'_1] commit [null, 0] dequeueatom [1] dequeueatom [2] removeatom [1, 0, 'y'_1] removeatom [2, 0, 'x'_1] newatom [3, 0, 'z'_1] newatom [4, 0, 'x'_1] newlink [3, 0, 4, 0, 0] enqueueatom [4] enqueueatom [3] freeatom [1] freeatom [2] proceed [] long TRANS_DATA(1), TRANS_ATTR(1), a1; AtomListEntry *i1; func [ 2, 'x'_1 ] ・・・・・・・ if(TRANS_ATTR(2)!=7) continue; a2 = trans_aritys[7]; func [ 　　　, 　　　] lmn_mem_remove_atom(TRANS_DATA(0), TRANS_DATA(1), TRANS_ATTR(1)); if(TRANS_ATTR(　　　)!=　　　　) $$f; a　　　 = trans_aritys[　　　]; lmn_mem_remove_atom(TRANS_DATA(0), TRANS_DATA(2), TRANS_ATTR(2)); a3 = trans_aritys[8]; TRANS_ATTR(3) = 8; TRANS_DATA(3) = (LmnWord)lmn_new_atom(TRANS_ATTR(3)); lmn_mem_push_atom(TRANS_DATA(0), TRANS_DATA(3), TRANS_ATTR(3)); 中間命令のテンプレート ・・・・・・・ } 各中間命令について処理 中間命令列(参考) このルールのマッチング・書き換えは次のような細粒度の命令列に変換できる a b ⇒ a c a b マッチング始点を選択 リンク先を参照 リンク先の種類を確認 アトムの生成 リンクの繋ぎ替え アトムの削除 (1) a (4) c (2) a (5) a b c (3) a b (6) a c この細粒度の命令列を中間命令列と呼んでいる

LMNtalからC言語への変換の設計と実装 1G04R013 石川 力