LMNtalルールコンパイラにおける内部命令の設計

LMNtalルールコンパイラにおける
内部命令の設計
早稲田大学理工学部情報学科
○水野謙
永田貴彦
加藤紀夫
上田和紀
LMNtalとは
階層的グラフの書き換えに基づく並行言語モデル
プロセスとデータを同等に扱う
多重集合が膜によって階層化される
膜は局所的な書き換えルールを持つ事ができる
ルールの移送が可能
グラフィカルなプログラミングが可能
LMNtalプロセス
アトム



GUI表現
小文字英数で始まる名前を持つ｡
有限本のリンクが接続する。
名前と接続するリンクの数（ファンクタ）で
識別される。
a
b
リンク
リンク



a
:-
書き換え規則をあらわす。
膜

c
大文字で始まる名前を持つ。
アトム間を接続する。
ルール
階層化された多重集合をつくる。
アトム
a
b
LMNtalプログラムの例（１）
no1 no2
res
a
c
c
n
c
c
n
no3 no4
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
Z0
a
Y
n :-
Z0
=
Y
LMNtalプログラムの例（１）
no1
res
no2
c
a
c
n
c
c
n
no3 no4
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
Z0
a
Y
n :-
Z0
=
Y
LMNtalプログラムの例（１）
no1
res
no2
c
a
c
n
c
c
n
no3 no4
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
Z0
a
Y
n :-
Z0
=
Y
LMNtalプログラムの例（１）
no1 no2
res
c
c
a
n
c
c
n
no3 no4
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
Z0
a
Y
n :-
Z0
=
Y
LMNtalプログラムの例（１）
no1 no2
res
c
c
a
n
c
c
n
no3 no4
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
Z0
a
Y
n :-
Z0
=
Y
LMNtalプログラムの例（１）
no1 no2
res
c
c
=
c
c
n
no3 no4
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
Z0
a
Y
n :-
Z0
=
Y
LMNtalプログラムの例（１）
no1 no2
res
c
c
c
c
n
no3 no4
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
Z0
a
Y
n :-
Z0
=
Y
LMNtalプログラムの例（１）
res(a(c(no1, c(no2, n)),
c(no3, c(no4, n)))),
( a(c(D, L1), L2, Z)
:- c(D, a(L1, L2), Z) ),
( a(n, L2, Z) :- Z=L2 )
LMNtalプログラムの例（２）
a
b
$p @p
a
$q @q
b
:-
:-
c
$p @p
$q @q
LMNtalプログラムの例（２）
a
b
$p @p
a
$q @q
b
:-
:-
c
$p @p
$q @q
LMNtalプログラムの例（２）
c
$p @p
a
$q @q
b
:-
:-
c
$p @p
$q @q
LMNtalプログラムの例（２）
{ a }, { b, (a, b :- c) },
( { $p,@p }, { $q,@q }
:- { $p,$q,@p,@q} )
プロトタイプ処理系
http://www.ueda.info.waseda.ac.jp/lmntal/
Javaによる実装
LMNtalプロセス（アトム、膜、リンク、ルール）を
Javaのオブジェクトとして扱う
ルールは、LMNtalプロセスを検査・操作するた
めの命令列にコンパイルされる


マッチング : ルール左辺にマッチするプロセスの有無
を調べる
ボディ実行 : ルール適用によるプロセスの書き換えを
おこなう
処理系の動作
LMNtal
ソース
ルール
コンパイラ
内部
命令列
最適化済
命令列
最適化器
実行時
処理系
解釈実行
(将来)
バイト
コード
Java
ソース
トランス
レータ
javac
実行時
処理系
実行
マッチング命令
アトムの検査・取得
deref
findatom
func
eqatom
neqatom
[-dstatom, srcatom, srcpos, dstpos] リンク先のアトム取得
[-dstatom, srcmem, func]
ファンクタによるアトム取得
[srcatom, func]
ファンクタの確認
[atom1, atom2]
アトムの同一性確認
[atom1, atom2]
アトムの非同一性比較
膜の検査・取得
testmem
lockmem
anymem
eqmem
norules
[dstmem, srcatom]
[-dstmem, freelinkatom]
[-dstmem, srcmem]
[mem1, mem2]
[srcmem]
アトムの所属確認
所属膜の取得
膜の取得
膜の一致確認
ルールが存在しない事の確認
ボディ命令
アトムの操作
removeatom
newatom
[srcatom]
[-dstatom, srcmem, func]
アトムの除去
アトムの生成
リンクの操作
newlink
unify
getlink
inheritlink
[atom1,
[atom1,
[-link,
[atom1,
pos1,
pos1,
atom,
pos1,
atom2, pos2]
atom2, pos2]
pos]
link2]
リンクの生成
リンクの単一化
リンクの取得
リンクの継承
膜の操作
removemem
newmem
movecells
[srcmem, parentmem]
[-dstmem, srcmem]
[dstmem, srcmem]
膜の除去
膜の生成
セルの移動
ルールの操作
loadruleset
[dstmem, ruleset]
ルールの読み込み
マッチング : アトムの取得
アトムの取得

すでに取得しているアトムと接続している場合
 リンク先アトムの取得 deref
 ファンクタの確認

func
[-dstatom, srcatom, srcpos, dstpos]
[srcatom, func]
接続していない場合
 アトムの取得
findatom[-dstatom, srcmem, func]
すでに取得しているアトムとの非同一性の確認
neqatom [atom1, atom2]
• neqatomが必要な例
X
b
b
Y
• neqatomは不要な例
b
X
a
b
b
Y
マッチング : リンクの検査
取得したアトムに接続しているリンクを、次のよう
にして検査する。

接続先のアトムをまだ取得していない場合
 アトムの取得・検査を行う

すでに取得している場合
deref [dstatom, srcatom, srcpos, dstpos]
eqatom [atom1, atom2]
例：
a
b
c
ボディ実行
removeatom [srcatom]
1. 左辺のアトムを除去する。
removemem [srcmem]
2. 左辺の膜を除去する。
newmem
[-dstmem, srcmem]
3. 右辺の膜を生成する。
4. プロセス文脈の内容を移動する。 movecells [dstmem, srcmem]
newatom
[-dstatom, srcmem, func]
5. 右辺のアトムを生成する。
6. ルール文脈の内容をコピーする。 copyrules [dstmem, srcmem]
loadruleset [dstmem, ruleset]
7. 右辺のルールをロードする。
[atom1, pos1, atom2, pos2]
8. リンクのつなぎ替えをおこなう。 newlink
unify
[atom1, pos1, atom2, pos2]
getlink
[-link, atom, pos]
inheritlink [atom1, pos1, link2]
ボディ実行 : リンクのつなぎ替え
右辺に２回出現するリンク

newlink命令で生成する。
左辺と右辺に１回ずつ出現するリンク


「=」アトムに接続している場合、
unify命令を用いる。
それ以外のアトムに接続している場合、
getlink/inheritlink命令を用いる。
X
a
:-
X
b
命令列の例
Z0
a
Y
A
X
c
:-
Z0
A
c
a
Y
X
findatom
deref
func
[1, 0, append_3]
[2, 1, 0, 2]
[2, cons_3]
removeatom
removeatom
newatom
newatom
getlink
getlink
getlink
getlink
inheritlink
newlink
inheritlink
inheritlink
inheritlink
[1]
[2]
[3,
[4,
[5,
[6,
[7,
[8,
[3,
[3,
[3,
[4,
[4,
0,
0,
1,
1,
2,
2,
0,
1,
2,
0,
1,
cons_3]
append_3]
1]
2]
0]
1]
7]
4, 2]
6]
8]
5]
命令列の最適化
アトムの再利用
膜の再利用
ルール適用のループ化
アトムの再利用
左辺のアトムをすべて除去してから右辺のアトムを生成
するのは明らかに冗長
アトムを再利用する事で、除去・生成を低減する。
リンクのつなぎ替えも一部省略できるようになる｡
Z0
a
A
X
c
Y
1. 左辺のアトムの除去
2. 右辺のアトムの生成
3. リンクのつなぎ替え
:-
Z0
A
c
a
X
Y
アトムの再利用によって
不要になる
リンクA、Yの処理は不要になる
最適化の効果
リスト連結
素数生成
時間速度比率時間速度比率
(sec)
最適化前
アトム再利用
ループ化
(103回/sec)
4.07
3.52
0.66
環境
CPU
:
Memory :
OS
:
java
:
7.36 1.00
8.51 1.16
45.4
6.17
8.03
7.28
0.83
Pentium Ⅲ-M 800MHz
384MB
Windows XP Home
j2sdk1.4.2
1.33 1.00
1.47 1.10
12.8
2.63
まとめと今後の課題
内部命令セット、および命令列の生成手順を示した。
アトムの再利用による最適化を紹介した。
プリミティブ型を扱うルールの最適化
Javaへのトランスレータの実装

Download Report