日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

グラフ書換え言語 LMNtal からの C プログラムの自動
生成
冨岡 太一

上田 和紀

手続き型プログラムではポインタを用いることで，リストや木のような代数的データ構造よりも複雑な，グラフ構造を持つデータを扱うことができる．グラフ書換え言語ではこういった複雑なデータ構造の正当性を保つ操作を容易に記述できる．しかしながら，グラフ書換え言語で記述されたプログラムは一般に手続き型プログラムより性能が低く，またその成果を既存の言語と連携して使用することも難しい．この研究では，グラフ書換え言語 LMNtal で書かれたプログラムを C などのより低水準な手続き型言語で書かれた高速なプログラムへと変換することで，グラフ書換
えに基づいたプログラムをより効率的でユーザが利用しやすい形で得ることを目的とする．本論文では LMNtal のサブセット言語を定義し，その言語を C へと変換するためのアルゴリズムを示す．また，いくつかの例題を用いてその有用性を検証する．

と出力となるデータの構造が適切であることを保証

1 はじめにできる．その他にも，参照を扱うプログラムを検証す

オブジェクトとオブジェクト同士の参照からなるる手法に分離論理 [13] がある．分離論理ではヒープとデータ構造への操作はあらゆるプログラミングパラ

参照を形式化することによって参照を扱うプログラム

ダイムにおいて要求される．しかし，データ構造へのを形式的に記述し検証することを可能にしている．

操作によってデータ構造が不正にならないように手しかし，依然としてこれらの手法のみでは容易には

続き型言語でプログラムを書くことは容易ではない．

扱えないプログラムが存在する．多くの関数型言語がデータ構造が複雑になればなるほど操作の記述は複備えている，代数的データ構造を扱う型システムでは雑になる．それに加えてダングリングポインタや同じ根がちょうど 1 つある木構造は上手く扱うことがでオブジェクトを指す複数の参照が存在するときなど，きる．一方，根が複数本ある構造や循環などを持つ構

考慮しなければならない問題は多い．

造を扱うことは難しい．分離論理に基づいた検証でこういった問題に対し，プログラムがデータ構造のも，データ構造の仕様記述はヒープと参照を具体的に操作を適切に行うことを保証あるいは検証するため書き下さなければならず，ユーザにとっての負担は大の手法が考えられてきた．関数型言語ではデータ構造

きい．最近では分離論理によるプログラムの自動検証

を型として定義する．それによってプログラムの入力もされている [3] が，未だ研究途上である．

∗ Automatic Generation of C Programs from Graph

Rewriting Language LMNtal
This is an unrefereed paper. Copyrights belong to
the Author(s).
Taichi Tomioka, 早稲田大学大学院基幹理工学研究科情報理工・情報通信専攻, Dept. of Computer Science andEnginerring, WasedaUniversity.
Kazunori Ueda, 早 稲 田 大 学 理 工 学 術 院 情 報 理 工 学科, Dept. of Information and Computer Science,
Waseda University.

一般に，木よりも複雑な構造はグラフを形成する．
グラフ構造を直接扱う計算モデルとしてはグラフ書換え系がある．グラフ書換え系には AGG [6] や PRO-GRES [15]，我々の実装である LMNtal [18] [17] など多くの処理系が存在する．グラフ書換え系は 1 つ以上の書換え規則からなる計算モデルであり，書換え規則
をグラフに適用することによって計算を行う．書換え
規則は 2 つのグラフパターンを左右に並べた形で表現される．書換え規則の適用とは，左辺のグラフパンパイルされたプログラムはランタイムライブラリ

ターンと一致する部分グラフを右辺のグラフパターが提供する API によってより大きなプログラムへとンに置き換えることである．グラフ書換え系はグラフ

組み込むことができる．

の構造を直接扱うことができる．しかし，グラフのパ

また，モデル駆動型アーキテクチャ [8] にも同様の

ターンマッチは一般には同型サブグラフの探索を必要

手法が存在する．モデル駆動型アーキテクチャで記述とするため計算コストがかかる．また，手続き型言語

される可視化されたモデルはグラフ書換え系と相性との隔たりも大きいため，グラフ書換え系での成果をが良い．そこで UML（Unified Modeling Language）

現在ソフトウェア開発の主流である手続き型言語へと[4] や MOF（MetaObject Facility） [9] などのモデリ活かすことは実用上難しい．

ング言語で記述されたモデルについてグラフ書換え系本研究では，手続き型言語において複雑なデータ構を与えることでモデルと実装との差異を埋めることが造を扱うことの難しさとグラフ書換え系の扱いにくできる [20]．GReAT [1] [5] はそのような目的で開発ささを解決するために，グラフ書換え言語 LMNtal のれた言語である．そのコンパイラである CG（Codeプログラムから手続き型言語 C のプログラムを生成

Generator）は C++のプログラムを出力する [20]．出する手法を提案し実装する．本論文では LMNtal と力されたプログラムはランタイムライブラリ上で動C の橋渡しとなる言語 ADLMNtal の定義と，一部制作する．

約を持つ ADLMNtal プログラムの C への変換手法

上述した研究ではいずれもグラフを表現するためを提案，実装した．この実装は概念実証を目的としての抽象データ型やそれを扱うライブラリを必要とすいるため，細かな最適化は行わずに基本となる部分をる．本研究では生成されたソースコードをユーザが優先的に実装した．実装は LMNtal で記述され，全ある程度理解して修正することを意図しているため，

部で約 800 本の書換え規則からなる．複数の例題に

データ構造に関しては参照を表す型以外は通常の C対して提案手法が正しく動くことを確認し，効率化，プログラミングと近い形で記述されている．また，グC 言語との連携の 2 つの目的を達成した．

ラフすべてをデータモデルとして扱うのではなく，グラフのうちいくつかの節点が操作を表すものと考え

2 関連研究ることでマッチング処理を簡略化した．

グラフ書換え系から手続き型プログラムを生成する研究やツールは著者の知る限りいくつか存在する．

3 グラフ書換え言語 LMNtal

文献 [2] はグラフ書換えモデルの 1 つである GP2

本節ではグラフ書換え言語 LMNtal とそのサブセッ[10] [11] から同様の操作を行う C プログラムを生成

ト言語である FlatLMNtal について簡単に述べる．詳する研究である．GP2 プログラム中に出現する書換細については文献 [18] [17] を参照してほしい．

え規則を C のコード片にそれぞれ対応づけることに

LMNtal プログラムはアトム，リンク，膜，ルール

よって変換を行う．書換え規則を静的に解析することの基本要素からなる．アトム，リンクは直感的にはグで最適化された C プログラムを出力し，高速な書換

ラフ理論における節点と辺に対応している．LMNtal

えを可能にしている．

ではアトム，リンクを用いてプロセスと呼ばれる無向グラフ書換え言語の 1 つである PROGRES（PRO-gramming with Graph REwriting Systems） [15] は多重グラフを表現する．ただし，各アトムの辺は順序を持つため，正確には無向グラフではない．

強い型付きのマルチパラダイム言語である．PRO-

LMNtal の構文の一部を図 1 に示す．p(X1 , . . . , Xm )GRES にはグラフィカルな開発環境が提供されていと書くと，p がアトム，(X1 , . . . , Xm ) がそのアトる．開発環境で記述したプログラムはそのまま解釈

ム に 接 続 し て い る リ ン ク を 表 す．リ ン ク は 2 つして実行することも可能である一方，Modula-2 と Cのアトムを接続するものであるから，1 つのグラのプログラムにコンパイルすることができる [16]．コ

フ表現中には同じリンク名は高々2 つしか書くこ


P


::=
|

T

(空)

0
p(X1 , . . . , Xm )(m ≥ 0)

(アトム)

|

P, P

(分子)

|

{P }

(セル)

|

T :-T

(ルール)

0

(空)

::=
|

p(X1 , . . . , Xm )(m ≥ 0)

|

T, T

(分子)

|

{T }

(セル)

|

T :-T

(ルール)

図3

連結する．LMNtal では無向グラフによってリストを表現するため，これは他の言語では双方向リンクリス

(アトム)



LMNtal の書換え規則

トに相当する．nil，cons はリストの構造を表すためのアトムである．2 つの書換え規則を適用することによって，append アトムの 1 番目と 2 番目のリンクにつながったリストは連結され 3 番目のリンクへと接続される．

図1

LMNtal の基本構文

4 LMNtal サブセット ADLMNtal
本節ではさらに，LMNtal を手続き型プログラム
R = append(nil, Y):- R = Y.
R = append(cons(A, B), Y) :R = cons(A, append(B, Y)).
図2

LMNtal ルールの例

へと変換しやすくするためにサブセット言語 ADLM-

Ntal を定義する．本論文では実装の都合上 LMNtal
サブセットである FlatLMNtal のサブセットとして

ADLMNtal を定義するが，形式的には膜を含むよと が で き な い ．特 別 な ア ト ム と し て ，ア ト ム’=’

うに定義することも可能である．さらに，任意のは X=Y と 表 記 す る こ と が で き ，リ ン ク X と Y

FlatLMNtal プログラムが ADLMNtal へと変換できと を 接 続 す る ．ま た ，記 述 を 簡 単 に す る た め に ，ることを示すことで ADLMNtal が FlatLMNtal とp(s1 , . . . , sm ), q(t1 , . . . , tn ) は sm と ti が同じリンクな

同等の表現力を持つことを示す．

ら ば q(t1 , . . . , ti−1 , p(s1 , . . . , sm−1 ), ti+1 , . . . , tn ) と略記してよいとする．{} は膜と呼ばれ，LMNtal

4. 1 ADLMNtal

においてプロセスをグループ化したセルを構成するたADLMNtal は FlatLMNtal のアトムを 2 種類に分めに用いられる．膜は入れ子にすることができ，階層類することで得られる．それらのアトムをアクティブ構造を形成する．膜を含まない LMNtal のサブセッ

アトム（Active atom）とデータアトム（Data atom）

ト言語は FlatLMNtal と呼ばれる．

と呼ぶ．ADLMNtal の構文を図 4 に示す．また，こルールは左辺のグラフパターンを右辺のグラフパ
ターンに書き換える書換え規則である．例えば，図 2

れ以降有限個のリンクの列 X1 , . . . , Xm を飾り文字
を用いて X と表す．

に示す 2 本のルールがあるとする．このルールのう注目するべきは書換え規則の構文である．ここではち 2 本目のルールは図 3 の左側にマッチするグラフ

書換え規則の左辺には必ず 1 つだけアクティブアト

を右側の対応するグラフに書き換える．ルールの両辺ムを含んでいなければならないということを定めていに 1 度ずつ出現するリンクはどのアトムにつながっる．ADLMNtal の意味論は基本的には FlatLMNtalていてもよい．ルールに出現するリンクのうち，左辺に従うが，書換え規則の構文に応じて簡約規則も変えと右辺のアトムの引数を繋ぐリンクを自由リンク，そなければならない．FlatLMNtal の簡約規則 [18] を以うでないものを局所リンクという．

下に示す．

図 2 の 2 本のルールは LMNtal におけるリストをあるアトム p を 2 つのアトム pA と pI に分割する．



ADLMNtal では pA はアクティブアトム，pI はデー

A

::=

p(X )

D

::=

0 | p(X ) | D, D

P::=

A | D | P, P | A, D :- P

タアトムである．ここで導入される関数 select は書換え規則の左辺に含まれるアクティブアトムのうち 1
つを恣意的に選択し，またアクティブアトムを削除するような操作を加える．図 7 の定義では n 個のア

図4

クティブアトムの中から 1 つだけを選び（それを pAi

ADLMNtal の構文とする）それ以外のアクティブアトムを左辺から削(R6′ )

tr(T, (T :- U )) −−−−→ tr(U, (T :- U ))



y



y

(R6′′ )

tr(T ), tr(T :- U ) −−−−→ tr(U ), tr(T :- U )∗図5変換関数 tr と簡約規則の関係
def

tr(p(X ))=deftr(P, Q)=tr(T :- U )
図6

def

=

除する．この選び方は処理系や引数によって変えても良く，また常に先頭を取るといった方法でも良い．

select で右辺に導入されるアトム t1 , . . . , tn は一意なシンボルを持つデータアトムである．tr の定義から
アクティブアトム pA を含む書換え規則の左辺は常に対応するデータアトム pI を含む．したがって，それらの書換え規則と select で新たに作られる書換え規pA (L), pI (X , L)

則は危険対を作らないため，書換えの合流性が保た

tr(P ), tr(Q)select(tr(T ) :- tr(U ))れる．

tr(T ) = pA1 (L1 ), . . . , pAn (Ln ), D とし，tr(U ) =変換関数 tr の定義

P とおくと，
tr(T ), tr(T :- U )defselect(pA1 (L1 ), . . . , pAn (Ln ), D :- P ) =(pAi (Li ), D :- P, pAi (Li ), t1 (L1 ), . . . , tn (Ln )),= tr(T ), select(tr(T ) :- tr(U ))(pA1 (t1 ) :- ), . . . , (pAn (tn ) :- )= pA1 (L1 ), . . . , pAn (Ln ), D,

図7(pAi (Li ), D :- P, pAi (Li ), t1 (L1 ), . . . , tn (Ln )),変換関数 select の定義(pA1 (t1 ) :- ), . . . , (pAn (tn ) :- )→ pA1 (L1 ), . . . , pAn (Ln ), P, t1 (L1 ), . . . , tn (Ln )(pAi (Li ), D :- P, pAi (Li ), t1 (L1 ), . . . , tn (Ln )),(R6′ ) T, (T :- U ) −→ U, (T :- U ).
ADLMNtal では以上の規則は次の規則に対応する．
(R6′′ ) A, D, (A, D :- P ) −→ P, (A, D :- P ).

(pA1 (t1 ) :- ), . . . , (pAn (tn ) :- )∗→ P,
(pAi (Li ), D :- P, pAi (Li ), t1 (L1 ), . . . , tn (Ln )),(pA1 (t1 ) :- ), . . . , (pAn (tn ) :- )= tr(U ), tr(T :- U )であるから，(R6′′ ) の有限回の適用によって (R6′ ) を

4. 2 ADLMNtal の表現力

再現することができる．したがって，任意の LMNtal

ADLMNtal では書換え規則の構文に制限が入ってプログラムについて等価な計算を行う ADLMNtal プ

いるために表現力は FlatLMNtal より低いように見ログラムが存在する．

える．しかし，FlatLMNtal を機械的に変換すること

select 関数は複数のアクティブアトムからマッチン

で FlatLMNtal での計算を再現する ADLMNtal プ

グに使用するものを 1 つ選択する．このときの選びログラムを得ることができる．つまり，図 5 を可換に方によって変換後の ADLMNtal のプログラムの効率する変換関数 tr が存在する．

は異なる．たとえば，特に個数の多いアトムを選択しtr は構文規則について帰納的に定義される．tr はてしまうとマッチング候補が多くできてしまうため効率が下がる．FlatLMNtal から ADLMNtal への自動

5. 2 書換え規則の変換変換を行う場合はより高効率な選び方をすることが

ADLMNtal の書換え規則の定義から，書換え規則重要である．このようなツールは本論文では扱わず，には必ず 1 つアクティブアトムが含まれる．逆に，書ADLMNtal を記述するユーザが明確にアクティブア

換え規則の適用はアクティブアトムが主体となって行

トム，データアトムの区別を与えるものとする．

われると考えることもできる．その観点では，アクティブアトムは書換え規則の左辺のデータアトムを入5 変換アルゴリズム

力として右辺のプロセスを出力する．このような観察

この節では 4 節で与えた ADLMNtal のプログラム

から，本論文ではアクティブアトムは C プログラム

を C プログラムへと変換する手法を説明する．直感における関数と対応させる．その定義はアクティブア

的には，アクティブアトムは C における関数に，デートムを含む書換え規則から生成される．書換え規則がタアトムはメモリ上のオブジェクトに対応する．

A, D:-P であるとき，生成されるプログラムの疑似
コードは次のようになる．

5. 1 ADLMNtal の C でのデータ表現
LMNtal の実行環境におけるプロセスの形式化については文献 [22] が詳しい．LMNtal アトムは引数に順番を持つため，頂点同士の対によって辺を表現することができない．そこで，アトムと引数番号の組をvoid A(...) {if ( 入力が D とマッチングするか ) {P を生成する ;D を削除する ;}}ポート（port）と定義し，ポート同士が互いに参照しているときのみリンクが存在するとする．本論文では書換え規則が複数ある場合はそれらの書換え規則

ADLMNtal のデータアトムは C でのメモリ上のオブによる定義が単に並べられる．このとき，並び方にジェクトに対応させる．このとき，データアトムはアよって変換後の結果が異なることがある．LMNtal でトムのラベルを区別するためのフィールドと引数の数は書換え規則を適用する順序は非決定的であるため，だけポートを持つ構造体で表される．また，ポートはこれに順序を入れると本来得られる複数の実行経路あるメモリオブジェクトに対する参照とそのオブジェのうち 1 つしか得られない．ただし，変換後のプロ

クトのフィールドをさす参照からなる．たとえば，リグラムに対して擬似乱数を用いて条件分岐するコーストを構成する 2 種類のデータアトム R = cons(A,ドを書くことで非決定的なプログラムのランダム実B) と R = nil は次の C 構造体定義と対応する．

行を再現することができる．

struct port { void * obj ; void * ref ; };5. 3 変換可能なプログラムの性質
struct cons {int label ;port A , B , R ;};struct nil {int label ;port R ;};プロセスに複数のアクティブアトムが存在するとき，これらを実行する順序には注意が必要である．上記の方法で変換した ADLMNtal プログラムを C の関数呼び出しによって実行することを考える．C の関数呼び出しは呼び出しスタックを用いて実行されるため，その実行は特定の順序で行われなければならな
い．具体的には，ADLMNtal プロセスが C の関数呼び出しによって実行されるためには，アクティブアト
ムは次のような手続きによって実行できなければならない．

1. 初期プロセスのアクティブアトムを好きな順番

でスタックに積む

2. スタックの一番上のアクティブアトムを含む書換え規則を適用する

3. 2 によって新しく生成されたアクティブアトム

L2C は LMNtal で実装され，構文解析器などを含め約 800 本の書換え規則からなる．そのうち，提案
手法を実装している部分は約 470 本で，残りは構文解析器である．

を好きな順番でスタックに積む

4. 2, 3 をスタックが空になるまで繰り返す
この手続きによって実行可能な ADLMNtal のプロセ
スは逐次性を持つという．
逐次性を持たないプロセスを実行するためにはあ6. 1 2 種類のアトムの分類
ADLMNtal には 2 種類のアトムが存在するため，ユーザがそれぞれのアトムを定義する方法が必要になる．

る関数の適用を一時中断して他の関数を適用し，後6. 1. 1 データアトム定義

で再開する機能が必要である．C プログラムでこれ

ここで，データアトムが構成するプロセスの構造をを実現するためにはスケジューラを実装すればよい．

定義する．LMNtal プロセスの構造を型として定める

スケジューラは実行していないアクティブアトムを保手法については文献 [23] [21] で議論されている．ここ

持しておき，その中から 1 つを選んで実行を試みる．

ではプロセスの集合を生成文法により定め，それを型選んだアクティブアトムが書換えに成功すれば新たにとして扱う．

できたアクティブアトムをスケジューラに登録する．

データアトム定義は type(t(S)) = {Ruleset} のもし書換えに失敗すればスケジューラは他の実行さように書く．ここで，t は定義したい型の識別子，S

れていないアクティブアトムの実行を試みる．この手は t 型のプロセスが持つルートのリンク列を表す．

順を繰り返し，アクティブアトムが 0 個になるかす

Ruleset はプロセス型の構造を生成する規則であり，べてのアクティブアトムの書換えに失敗すればスケ

通常の LMNtal の構文に従うが，左辺は S を引数にジューラは停止する．この手続きによって実行可能な含むアトム 1 つからなり，右辺は任意個の型識別子を

ADLMNtal のプロセスは並行性を持つという．

名前にもつアトムからなる．Ruleset に含まれる規則

並行性を持つプロセスを実行するその他の方法とはアトムを終端記号，リンクを非終端記号とする生成

して，C に提供されているマルチスレッドライブラリ規則である．この観点からは，S は開始記号とみなさなどを用いて OS にスケジューリングを一任するといれる．右辺の型識別子の引数に与えられるリンクはそうものが考えられる．この場合，並列にプロセスを書の型の開始記号と同一視されて新たに生成規則が適き換えるためには排他制御を行わなければならない．

用される．

データ構造を並列に操作するアルゴリズムには参照に中間データを用いる手法 [19] やデータにタグを付与する手法 [7] があり，これらを用いることでプロセスを並列に書き換えることができる．

6 実装
以上の議論に基づいて，ADLMNtal のプログラム

例えば，双方向リストは次のように定義される．
type ( list ( L )) = {nil ( L ) : - .
cons (A , B , L ) : - list ( B ).
}この規則は，{L=nil, L=cons( , nil),を C へと変換するツール（L2C）のプロトタイプを

L=cons( , cons( , nil)), . . .}実装した．L2C には以下のような制約が存在する．

というプロセスの集合を与える．右辺に制約のない• 入力の ADLMNtal プログラムは逐次性を持つ

リンクは任意のプロセスを許す．

• 書換え規則の左辺は連結でなければならない

データアトム定義は現状の実装では C プログラム• ユーザはデータアトム定義，アクティブアトム

において構造体定義を生成するために使われている．

定義を与える6. 3 節で述べるように，将来的には最適化に利用する

ことが期待される．

6. 1. 2 アクティブアトム定義
アクティブアトムはそのアクティブアトムを左辺に含む書換え規則を用いて C 関数定義に変換される．
ここでは解析を簡単にするためにあるアクティブアト

type ( skiplist ( P2 , P1 )) = {nil ( P2 , P1 ) : - .
lnode (V , N1 , P1 ) : int ( V ) , skiplist ( P2 , N1 ).
enode (V , N2 , N1 , P2 , P1 ) : int ( V ) , skiplist ( N2 , N1 ).
}.

ムについての書換え規則をまとめて定義する構文を与える．
ア ク ティブ ア ト ム 定 義 は function(f (A)) =図8

スキップリストのデータアトム定義{Ruleset} のように書く．ここで，f は定義したい

図 8 の定義ではスキップリストは 2 つのルートを関数の識別子，A はアクティブアトム f の引数のリ持ち，高さ 1 のノードを lnode，高さ 2 のノードをンク列を表す．Ruleset は通常の ADLMNtal の書換

enode とする nil で終端された直鎖状のデータ構造

え規則からなる．ただし，それぞれの規則の左辺は連になる．スキップリストの挿入，検索操作の定義を結でなければならない．

図 9 に示す．アトム名の末尾に l， e がついている

非連結成分を操作するためには，アクティブアトム

ものはそれぞれ高さ 1，2 のノードを走査しているこに直接つながっていないデータアトムを取得する方法とを表している．たとえば insert では，まず高さ 2が必要になる．そのためには全てのデータアトムを一のノードを辿り（insert e），挿入する値より大き括で管理するストアを持つというものが考えられる．

いノードの手前から高さ 1 のノードを走査し始める

これはサイズの異なるメモリオブジェクトを効率的（insert l）．insert l は挿入する値より大きいノーに管理，検索，列挙できなければならず，大掛かりな

ドか末尾のノードの手前に値を挿入し，スキップリス

仕組が必要となる．特殊な場合として，0 引数のデート全体を昇順に保つ．

タアトムは大域変数をカウンタとして用いることでL2C が生成した C プログラムは挿入関数が 293 行，

実装することも可能である．しかしながら，本論文で検索関数が 374 行であった．

は ADLMNtal を C へ変換する手法の概念実証のた

6. 2. 2 無向グラフの複製

めのツールを実装することを目指したため，非連結成

次に，より複雑なデータ構造への操作の例として無分については見送ることとした．

向グラフの複製を扱う．無向グラフはノード間に双方向ポインタによってエッジが張られているデータ構造

6. 2 例題

である．LMNtal プロセスのリンクは向きを持たない

L2C のプロトタイプを用いることで上述の制限をため，（辺に順序を持つ）無向グラフを自然に表現で満たす ADLMNtal プログラムから C プログラムをきる．ここでは簡単のために各ノードの次数は高々3生成することができる．動作を確認した問題にはリスであるとする．図 10 に無向グラフのデータアトム定ト，木の操作，グラフ構造を持つデータの操作，文脈

義と，複製関数のインターフェースとなるデータアト

自由文法による文字列の生成があるが，本論文ではそムの定義を示す．ここでのアクティブアトムは常にイの中から 2 つの例題について述べる．

ンターフェースとなるデータアトムを介して入力を受

6. 2. 1 スキップリストの挿入，検索

け取る．

スキップリスト [12] は通常の線形リストに加えて

図 11 は複製関数の定義である．複製関数は 3 引数

ノード間を飛び越えるような参照を持つリストであのアクティブアトム copy で表され，第 1 引数のノーる．通常のスキップリストの高さは確率的に決定されドを複製して第 2，第 3 引数にそれぞれ返す．このとるが，ここでは高さが高々 2 で要素の挿入順に依存すき，第 1 引数のノードはデータアトム e を通じて受けるとする．このとき，スキップリストのデータ構造は取る．これは無向グラフが閉路を持つときに copy 同

3 種類のアトムで表すことができる．

士が衝突したことを検知するためである．copy 同士

function ( insert_l (A , B , C , D , E )) = {insert_l (X , N2 , N1 , P2 , P1 ) , nil ( N2 , N1 ) : - int ( X ) | lnode (X , L , P1 ) , nil ( P2 , L ).
insert_l (X , N2 , N1 , P2 , P1 ) , lnode (V , NN1 , N1 ) : - X > V | lnode (V , L , P1 ) , insert_l (X , N2 , NN1 , P2 , L ).
insert_l (X , N2 , N1 , P2 , P1 ) , lnode (V , NN1 , N1 ) : - X = < V | enode (X , N2 , L , P2 , P1 ) , lnode (V , NN1 , L ).
insert_l (X , N2 , N1 , P2 , P1 ) , enode (V , NN2 , NN1 , N2 , N1 ) : - int ( X ) , int ( V ) |lnode (X , L , P1 ) , enode (V , NN2 , NN1 , P2 , L ).
}.
function ( insert_e (X , N2 , N1 , P2 , P1 )) = {insert_e (X , N2 , NN1 , P2 , P1 ) , nil ( N2 , PP1 ) : - int ( X ) | insert_l (X , N2 , NN1 , P2 , P1 ) , nil ( N2 , PP1 ).
insert_e (X , N2 , N1 , P2 , P1 ) , enode (V , NN2 , NN1 , N2 , PP1 ) : - X > V |N1 = P1 , enode (V , L2 , L1 , P2 , PP1 ) , insert_e (X , NN2 , NN1 , L2 , L1 ).
insert_e (X , N2 , N1 , P2 , P1 ) , enode (V , NN2 , NN1 , N2 , PP1 ) : - X = < V |insert_l (X , N2 , N1 , P2 , P1 ) , enode (V , NN2 , NN1 , N2 , PP1 ).
}.
function ( insert (X , N2 , N1 , P2 , P1 )) = {insert (X , N2 , N1 , P2 , P1 ) : - int ( X ) | insert_e (X , N2 , N1 , P2 , P1 ).
}.
function ( member_l (X , N1 , P1 , R )) = {R = member_l (X , L1 , P1 ) , nil ( L1 , P2 ) : - int ( X ) | R = false , nil ( P1 , P2 ).
R = member_l (X , L1 , P1 ) , lnode (Y , N1 , L1 ) : - X =:= Y | R = true , lnode (Y , N1 , P1 ).
R = member_l (X , L1 , P1 ) , lnode (Y , N1 , L1 ) : - X < Y | R = false , lnode (Y , N1 , P1 ).
R = member_l (X , L1 , P1 ) , lnode (Y , N1 , L1 ) : - X > Y | lnode (Y , L1 , P1 ) , R = member_l (X , N1 , L1 ).
R = member_l (X , L1 , P1 ) , enode (Y , NN2 , NN1 , P2 , L1 ) : - int ( X ) , int ( Y ) | R = false , enode (Y , NN2 , NN1 , P2 , P1 ).
R = member_l (X , L1 , P1 ) , nil ( P2 , L1 ) : - int ( X ) | R = false , nil ( P2 , P1 ).
}.
function ( member_e (X , N2 , N1 , P2 , P1 , R )) = {R = member_e (X , L2 , N1 , P2 , P1 ) , nil ( L2 , NN1 ) : - int ( X ) | R = member_l (X , N1 , P1 ) , nil ( P2 , NN1 ).
R = member_e (X , L2 , N1 , P2 , P1 ) , enode (Y , NN2 , NN1 , L2 , PP1 ) : - X =:= Y |R = true , N1 = P1 , enode (Y , NN2 , NN1 , P2 , PP1 ).
R = member_e (X , L2 , N1 , P2 , P1 ) , enode (Y , NN2 , NN1 , L2 , PP1 ) : - X < Y |R = member_l (X , N1 , P1 ) , enode (Y , NN2 , NN1 , P2 , PP1 ).
R = member_e (X , L2 , N1 , P2 , P1 ) , enode (Y , NN2 , NN1 , L2 , PP1 ) : - X > Y |N1 = P1 , enode (Y , L2 , L1 , P2 , PP1 ) , R = member_e (X , NN2 , NN1 , L2 , L1 ).
}.
function ( member (X , N2 , N1 , P2 , P1 , R )) = {R = member (X , N2 , N1 , P2 , P1 ) : - int ( X ) | R = member_e (X , N2 , N1 , P2 , P1 ).
}.

図9

スキップリストの挿入，検索が衝突した際は b というデータアトムを相手の copyに送る．b を受け取った copy はもう複製するノードがないと判断し終了する．

L2C によって生成された C プログラムの複製関数
は 319 行であった．

6. 2. 3 性能評価
LMNtal 処理系 SLIM と L2C が生成した C プログ
ラムとの実行時間を計測した結果を表 1 に示す．L2C

type ( graph ( X )) = {n1 ( X ) : - .
n2 (A , X ) : - .
n3 (A , B , X ) : - .
}.
type ( copy_arg ( X )) = {e (A , X ) : - .
b (A , B , X ) : - .
}.

が生成した C プログラムは -O オプションをつけてコンパイルした．これにより，アクティブアトムの末

図 10

無向グラフと複製関数のインターフェースの定義

尾呼び出しが最適化されることが期待される．
表 1 において，graph random はランダムな無向

2 分木に対して挿入と検索を行うプログラムである．

グラフ，graph straight は n2 と n1 のみからなる直skiplist と bin tree にはランダムな数値データを与え

線状の無向グラフを入力として無向グラフを複製すて挿入，検索した．

るプログラムに与えたものである．また，bin tree は

SLIM と L2C の性能比に関しては問題によって様々function ( copy ( Graph , Ret1 , Ret2 )) = {copy ( e ( X ) , Ra , Rb ) , n1 ( X ) : - n1 ( Ra ) , n1 ( Rb ).
copy ( e ( X ) , Ra , Rb ) , n2 (A , X ) : - n2 ( A1 , Ra ) , n2 ( A2 , Rb ) , copy ( e ( A ) , A1 , A2 ).
copy ( e ( X ) , Ra , Rb ) , n2 (X , A ) : - n2 ( Ra , A1 ) , n2 ( Rb , A2 ) , copy ( e ( A ) , A1 , A2 ).
copy ( e ( X ) , Ra , Rb ) , n3 (A , B , X ) : - n3 ( A1 , B1 , Ra ) , n3 ( A2 , B2 , Rb ) , copy ( e ( A ) , A1 , A2 ) , copy ( e ( B ) , B1 , B2 ).
copy ( e ( X ) , Ra , Rb ) , n3 (X , A , B ) : - n3 ( Ra , A1 , B1 ) , n3 ( Rb , A2 , B2 ) , copy ( e ( A ) , A1 , A2 ) , copy ( e ( B ) , B1 , B2 ).
copy ( e ( X ) , Ra , Rb ) , n3 (B , X , A ) : - n3 ( B1 , Ra , A1 ) , n3 ( B2 , Rb , A2 ) , copy ( e ( A ) , A1 , A2 ) , copy ( e ( B ) , B1 , B2 ).
copy ( e ( L ) , B , C ) , e (X , L ) : - b (B , C , X ).
copy ( e ( L ) , B , C ) , e (L , X ) : - b (B , C , X ).
copy (X , B , C ) , b (P , Q , X ) : - B = P , C = Q .
}.

図 11
表1

無向グラフの複製関数の定義

L2C と SLIM の性能比較 (実行時間 [s])

SLIM

L2C

L2C(tcmalloc)

SLIM/L2C

skiplist

78.05638.48218.3044.26

graph random

20.525

1.183

0.580

35.38

graph straight33.038

3.476

1.793

18.42

bin tree52.71324.657

10.1985.16である．特に性能比が大きい graph random につい6. 3. 1 ポート削減ては，SLIM が書換え規則ごとにアトムを探索する

5. 1 節では変換された C プログラムではアトム間のに対し，L2C ではアクティブアトムごとに属するの参照が 2 つのフィールドから成るとした．1 つは接書換え規則を試すという処理の順番の違いによる．

続先アトムへの参照で，これはマッチングの際にアトgraph random では copy アトムが多数発生しそれらムが条件に合致するかどうかを判定するために使わを書き換えるルールが必ず 1 つ存在するが，SLIM でれる．もう 1 つは接続先アトムのどのフィールドにはそのルールを選ぶまで copy アトムを対象として違接続しているかを表す．これは書換えの際に接続先アうルールの適用を試してしまう．L2C により変換さトムのフィールドを書き換えて参照を張り直すためにれた後の C プログラムではそのようなことが起きな使われる．しかし，データアトム定義ではデータアト

いため，特に高速になる．skiplist，bin tree はあま

ムの種類によって接続先のフィールドが決定されるこり性能の改善が見られない．これは SLIM が整数をとがある．この場合には接続先フィールドの情報は型表すアトムについて参照に直接埋め込むという最適定義から得られるため実際のデータから削減するこ化をしており，L2C ではしていないことが一因であとができる．

ると考えられる．

6. 2 節のスキップリストの例では，各データアトムのルート以外の引数は接続先のフィールドを静的に決

6. 3 最適化

定できる．これらのフィールドについては接続先アトADLMNtal から機械的に生成された C プログラム

ムの情報のみで十分である．また，insert と member

は FlatLMNtal インタプリタより効率的である．しではスキップリストのルートを張り直しているがルー

かし，依然として余分なメモリを使用しているところ

トに接続しているアトムの情報は利用していないたや余計に処理を行っているところがある．それらを削め，ルートの接続先フィールドの情報のみで十分であ減するためにいくつかの最適化が考えられる．

る．スキップリストを構成するデータアトムは最大 5引数であるから，C ではタグフィールドと 5 つのポー

トで 11 ワードの構造体として表される．この最適化により，各ポートは 1 つのポインタとなり 6 ワードの構造体となる．

6. 3. 3 参照の単方向化
ADLMNtal から生成される C プログラムではすべてのデータは双方向に参照される．双方向参照はデー

一方，無向グラフの例ではいずれのデータアトムもタの柔軟な操作を可能にするが，参照が単方向にしかどのフィールドに接続しているか決定できない．無向

利用されない場合は無駄なメモリを使用していること

グラフの複製では重複を防ぐために直前に複製したになる．ADLMNtal においてデータアトムの参照を

データアトムがどの引数とつながっていたか確認しな利用するのは以下の 2 通りである．(1) データアトム

ければならない．そのため，接続先フィールドの情報の引数が局所リンクで，そのリンクを通じてアクティが実行時に必要になる．

ブアトムに到達できないとき．(2) データアトムの引6. 3. 2 アトム，ポート再利用

数が自由リンクで，そのリンクをつなぎかえるとき．

L2C が生成した C プログラムでは，データアト

ただし，(2) はアトムを再利用しかつ余計なリンクのムの生成，削除に malloc/free 関数を使用している．

つなぎ替えを行わないという前提がある．

データアトムは書換えが起きるたびに都度生成，削除

6. 2 節のスキップリストの例では，insert l におされるため，malloc/free 関数が多数呼び出されるこ

いては skiplist のルートの 1 つである P1 は局所リととなる．malloc/free 関数が性能に与える影響を確ンクであり (1) に該当しない．insert e においては認するために，標準の C アロケータの代わりにより自由リンクでありつなぎ替えを行わないため，(2) に効率の良いアロケータである tcmalloc [14] を使っては該当しない．このように見ていくと，skiplist の6. 2 節の例題を計測した．

2 つのルート P1，P2 はどの書換え規則においても上

表 1 から，malloc/free 関数の呼出が性能に大き記 2 条件に該当しないことがわかる．したがって，こく影響していることがわかる．ADLMNtal ではデーのプログラムにおいては逆向き参照である P1，P2 はタアトムの種類によってメモリオブジェクトのサイ

必須ではなく，単方向スキップリストで十分であるとズが決定されるため，書換え規則の両辺に含まれるいうことがわかる．ポート削減と組み合わせれば，ス

同種のアトムを確保，解放せずに再利用することでキップリストの 1 つのノードは 4 ワード（値，ノーmalloc/free 関数の呼び出し回数を減らすことができ

ドの種類，次の要素への 2 つの参照）で表される．

る．また，そのとき書換えの前後でリンクの接続先が無向グラフの例ではどの参照も双方向であること変わらない場合は参照をつなぎかえる回数も減らすを意図しているが，この最適化を適用しても参照が単ことができる．

方向になることはない．

6. 2 節の例では，スキップリストの member はデー
タアトムの構造を変えないため，効果的な最適化が可

7 まとめと今後の課題能である．member l の 4 つ目の書換え規則では，整本論文では，グラフ書換え言語である LMNtal から

数アトム 2 個，データアトム 1 個，アクティブアトム

C プログラムを機械的に生成するための手法を提案のポート 4 個で合わせて 7 回ずつの malloc/free が呼した．LMNtal と C の間に存在する大きな隔たりをばれ，リンクの接続が 5 回行われる．最適化をすると解消するため，LMNtal に制約を加えた ADLMNtal

malloc/free がなくなり，リンクの接続は 3 回になる．

を定義した．ADLMNtal で記述された例題から C プ

無向グラフではスキップリストほどの最適化は見

ログラムが生成でき，元の LMNtal 処理系よりも効られない．copy の 2 つ目の書換え規則では，5 回の率的に動くことを確認した．今後の課題としては以下

free と 6 回の malloc，6 回のリンクの接続が行われのものが考えられる．

るが，最適化後は 1 回の malloc，6 回のリンクの接続になる．

5 節では ADLMNtal プログラムの逐次性，並行性を導入した．6 節では逐次性を持つ ADLMNtal プロ
グラムを対象としており，与えられた ADLMNtal プ

ログラムが逐次性を持つかどうかを判定することは重要である．逐次性判定はデータアトムに対して構造型と入出力型を導入することで可能だと考えられる．

6 節では非連結成分を扱うための手法について述べた．しかし，5 節で述べたように並列な C プログラ
ムを生成する場合は，大域的な領域に共有資源があると問題になりやすい．これらの手法を効率よく実装することは，実用上重要である．
謝辞 本研究を進めるにあたって活発な議論をしてくださった上田研究室の皆様と，松本翔太氏，恒川雄
太郎氏に感謝いたします．

参 考 文 献[ 1 ] Agrawal, A., Karsai, G., and Lédeczi, Á.: An
End-to-end Domain-driven Software Development
Framework, Companion of the 18th Annual ACM
SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’03, ACM, 2003, pp. 8–15.
[ 2 ] Bak, C. and Plump, D.: Compiling Graph Programs to C, International Conference on Graph
Transformation (ICGT 2016), LNCS, Vol. 9761,
Springer, 2016, pp. 102–117.
[ 3 ] Bakst, A. and Jhala, R.: Predicate Abstraction
for Linked Data Structures, Springer Berlin Heidelberg, 2016, pp. 65–84.
[ 4 ] Booch, G., Jacobson, I., and Rumbaugh, J.: The
unified modeling language reference manual, 1999.
[ 5 ] Karsai, G., Agrawal, A., Shi, F., and Sprinkle, J.: On the use of graph transformations in
the formal specification of computer-based systems, Proceedings of IEEE TC-ECBS and IFIP10,
Vol. 1(2003), pp. 19–27.
[ 6 ] Löwe, M. and Beyer, M.: AGG – An implementation of algebraic graph rewriting, Rewriting Techniques and Applications: 5th International Conference (RTA–93), LNCS, Vol. 690, Springer, 1993,
pp. 451–456.
[ 7 ] Michael, M. M.: High Performance Dynamic
Lock-free Hash Tables and List-based Sets, Proceedings of the Fourteenth Annual ACM Symposium on
Parallel Algorithms and Architectures, SPAA ’02,
New York, NY, USA, ACM, 2002, pp. 73–82.
[ 8 ] OMG: “MDA – The Architecture Of Choice For
A Changing World”, Needham, MA, 2017. [Online]
http://www.omg.org/mda/.
[ 9 ] OMG: “OMG’s MetaObject Facility”, Needham,

MA, 2017. [Online] http://www.omg.org/mof/.
[10] Plump, D.: The graph programming language
GP, International Conference on Algebraic Informatics, LNCS, Vol. 5725, Springer, 2009, pp. 99–
122.
[11] Plump, D.: The Design of GP 2, 10th International Workshop on Reduction Strategies in
Rewriting and Programming (WRS 2011), EPTCS,
Vol. 82, 2012, pp. 1–16.
[12] Pugh, W.: Skip lists: A probabilistic alternative
to balanced trees, Springer Berlin Heidelberg, 1989,
pp. 437–449.
[13] Reynolds, J. C.: Separation logic: A logic forshared mutable data structures, Logic in Computer
Science, 2002. Proceedings. 17th Annual IEEE
Symposium on, IEEE, 2002, pp. 55–74.
[14] Sanjay, G. and Menage, P.: “TCMalloc :Thread-Caching Malloc”, 2017. [Online] http://
goog-perftools.sourceforge.net/doc/tcmalloc.html.
[15] Schürr, A.: PROGRES, A Visual Language
and Environment for PROgramming with Graph
REwriting Systems, Technical Report AIB 94–11,
RWTH Aachen, Germany, 1994.
[16] Schürr, A., Winter, A. J., and Zündorf, A.: The
PROGRES approach: Language and environment,
Handbook of graph grammars and computing bygraph transformation, World Scientific Publishing,
1999, pp. 487–550.
[17] Ueda, K.: LMNtal as a hierarchical logic programming language, Theoretical Computer Science,Vol. 410, No. 46(2009), pp. 4784–4800.
[18] Ueda, K. and Kato, N.: LMNtal: a language
model with links and membranes, International
Workshop on Membrane Computing (WMC 2004),
LNCS, Vol. 3365, Springer, 2004, pp. 110–125.
[19] Valois, J. D.: Lock-free linked lists using
compare-and-swap, Proceedings of the fourteenth
annual ACM symposium on Principles of distributed computing, ACM, 1995, pp. 214–222.
[20] Vizhanyo, A., Agrawal, A., and Shi, F.: Towards generation of eﬃcient transformations, International Conference on Generative Programmingand Component Engineering (GPCE 2004), LNCS,
Vol. 3286, Springer, 2004, pp. 298–316.
[21] 吉元 佑介, 上田 和紀: グラフ書換え系における静的グラフ型検査, 日本ソフトウェア科学会第 32 回大会,
2015.
[22] 信夫 裕貴, 田辺 良則, 上田 和紀: LMNtal におけるグラフ書換え操作の Coq による形式化, 日本ソフト
ウェア科学会第 30 回大会, 2013.
[23] 奈良 耕太, 上田 和紀: パターン定義によるマッチン
グを導入したグラフ書換え言語とその実装, 日本ソフト
ウェア科学会第 31 回大会, 2014.