早稲田大学大学院 基幹理工学研究科 情報理工学専攻

グラフ書換え系 LMNtal の 実行時処理系 SLIM における グラフパターンマッチングの高速化

提出日： 2015 年 1 月 24 日 指導 ： 上田 和紀 教授

早稲田大学大学院 基幹理工学研究科 情報理工学専攻

学籍番号： 5113B002-0

青山 龍一

私たちが扱うデータ量はコンピュータの発展により増す一方, 同時にそれぞれのデータ は互いに何らかの関係を持っている. 複雑なデータの関係を簡潔に表すデータ構造をグラ フという. グラフ書換え系とは規則によってグラフ構造を部分的に書き換えて行くことで 実行が進む系である. グラフ書換え系をコンピュータ上で実現する際, グラフ構造を容易 に扱えるデータ構造は自明でない. さらにグラフ書換え系が大規模グラフを扱うとき, 処 理系が扱うグラフのデータ構造によって,書き換わるグラフ構造を抽出するのに多大な時 間がかかることが考えられる. したがって,処理系は大規模グラフデータの中から,書き換 わるグラフ構造を高速に探索することが重要である.

LMNtalとは階層グラフ書換えに基づく並行言語モデルである. LMNtalの構成要素と

して,アトム, リンク,膜,ルールの4つが存在する. LMNtalはルールによって階層グラフ 構造を書き換えてゆくグラフ書換え系の1つである. SLIMは軽量化・高速化を目的に開

発されたLMNtal実行時処理系の1つであり,モデル検査機能を備えている.

SLIMによるLMNtalプログラムの実行性能は従来の実行時処理系と比較すると飛躍的

に向上したが, 大規模なLMNtalグラフを扱う際やルールの記述によってプログラムの実 行時間が著しく増加することがある. これはほとんどの場合,書き換え対象となるグラフ 構造の探索効率に起因している.

SLIMのルール適用時におけるグラフ構造探索の高速化を図るために,本研究ではアト ムの動的操作と並列パターンマッチングの2つの手法を提案した.

アトムの動的操作は SLIMにおいて連結リスト中に格納されているアトムの位置をグ ラフ書き換え時に操作し,グラフパターンマッチング処理の計算量を改善する手法である.

並列パターンマッチングはSLIM実行時において,大規模LMNtalグラフを扱う際にボ トルネックとなりやすいグラフパターンマッチングを複数のスレッドで行う手法である.

本研究の成果として,アトムの動的操作によって,計算量が想定より悪かったプログラム の計算量を改善し, 並列パターンマッチングによって10コア使用時に逐次実行と比較し て最大5倍の速度向上を達成した.

The amount of data we deal with is increasing because of the developing computers, and each piece of data have some relationships. Graph are a data structure which represents the relationship between complex data. The execution of a graph rewriting system proceeds by rewriting parts of graphs using rules. When we implement a graph rewriting system on a computer, data structure for handling graphs easily is not obvious. Furthermore, when a graph rewriting system deals with a large-scale graph, it may take much time to extract a rewritten graph depending on a graph data structure a runtime system deals with. It is important for the runtime system to search a subgraph to be rewritten from a large-scale graph.

LMNtal is a concurrent language model based on hierarchical graph rewriting. . . . atoms, links, membranes, and rules. LMNtal is a graph rewriting system whose execution proceeds by rewriting hierarchical graphs by rules. SLIM is a lightweight, efficient runtime system of LMNtal that features a model checker.

An execution performance of an LMNtal program in SLIM increased dramatically com- pared with its predecessor, but depending on scale of a LMNtal graph and description of rules, executing time increased significantly due to the search of a graph to be rewritten.

In order to increase the speed of graph search in rule application, we suggest the two technique in this study, Dynamic Atom Operation and Parallel Pattern Matching. Dynamic Atom Operation is a technique to minimize wasteful graph pattern matching by altering the positions of atoms in a linked list of SLIM when a rule rewrites a graph. This optimization is to improve the computational complexity of program execution. Parallel Pattern Matching is a technique that performs graph search with multiple threads when SLIM deals with a large-scale graph.

As the result of this study, we improved the computational complexity of programs that performed worse than expected, and achieved a maximum of five times speedup with ten threads.

目次

第1章 序論 1

1.1 背景 . . . 1

1.2 研究の目的 . . . 2

1.3 論文の構成 . . . 2

第2章 グラフ理論 3 2.1 グラフ . . . 3

2.2 連結グラフ . . . 5

2.3 部分グラフ . . . 5

2.4 疎グラフと密グラフ . . . 5

2.5 最短経路問題 . . . 5

2.6 グラフ書換え系とグラフパターンマッチング . . . 6

第3章 LMNtalとその処理系 7 3.1 LMNtalの基礎事項 . . . 7

3.2 LMNtalの特徴 . . . 10

3.3 LMNtalの構文 . . . 10

3.4 プロセス文脈と型つきプロセス文脈 . . . 10

3.5 システムルールセットとLMNtalライブラリ . . . 12

3.6 LMNtalプログラムの省略記法 . . . 13

3.7 HyperLMNtal . . . 13

3.8 LMNtal処理系概要 . . . 15

3.9 LMNtalの中間命令 . . . 15

3.10 ルール適用におけるグラフパターンマッチング . . . 15

3.11 ルール適用におけるグラフ書換え . . . 18

3.12 ルール適用の計算量 . . . 19

第4章 LMNtal実行時処理系SLIM 21 4.1 SLIM概要 . . . 21

4.2 SLIM実行の種類 . . . 21

4.3 SLIMにおけるLMNtalグラフの表現方法 . . . 22

4.4 グラフパターンマッチング . . . 23

4.5 グラフ書換えによるアトムリストの変化 . . . 23

第5章 LMNtalプログラム例題 25 5.1 最短経路問題 . . . 25

5.2 グラフ構造探索問題 . . . 28

第6章 アトムの動的操作 33 6.1 既存のSLIMの問題点 . . . 33

6.2 アトム操作命令の導入 . . . 34

6.3 アトムリストの整列 . . . 35

6.4 アトム操作命令のコンパイラによる出力 . . . 36

6.5 関連研究 . . . 38

第7章 並列パターンマッチングの導入 39 7.1 並列化の概要 . . . 39

7.2 並列パターンマッチング中間命令と実装概要 . . . 39

7.3 スレッドへの担当する始点アトムの割り当て . . . 41

7.4 並列パターンマッチング手法の戦略 . . . 42

7.5 ルール左辺のグラフ構造の同時発見 . . . 42

7.6 並列パターンマッチングアルゴリズムの詳細 . . . 43

7.7 関連研究 . . . 45

第8章 評価実験 46 8.1 最短経路問題に関する計測 . . . 47

8.2 グラフ構造探索問題 . . . 49

第9章 まとめと今後の課題 57 9.1 まとめ . . . 57

9.2 今後の課題 . . . 57

謝辞 60

参考文献 61

発表文献 63

付録A グラフ構造探索例題の応用 64

A.1 1本のエッジしか接続されていないノード. . . 64 A.2 四角形構造 . . . 64 A.3 閉路抽出 . . . 64

付録B LMNtalプログラム 66

B.1 最短経路問題 . . . 66 B.2 グラフ構造抽出例題 . . . 69

図目次

2.1 一般的なグラフの例 . . . 3

2.2 多重エッジを含むグラフ . . . 4

2.3 自己ループを含むグラフ . . . 4

2.4 有向グラフ . . . 4

2.5 重みつきグラフ . . . 4

2.6 ダイクストラアルゴリズム . . . 6

3.1 LMNtalグラフの例 . . . 7

3.2 リンクの順序付け . . . 8

3.3 図3.1を記述したLMNtalプログラム . . . 9

3.4 LMNtalの構文規則 . . . 11

3.5 プロセス文脈を利用したLMNtalプログラムの例. . . 11

3.6 HyperLMNtalプログラムの例 . . . 14

3.7 図3.6の実行の流れ . . . 14

3.8 LMNtalプログラムの実行の流れ. . . 15

3.9 主要なLMNtal中間命令の解説 . . . 16

3.10 特定の部分グラフ構造を消去するLMNtalルール. . . 17

3.11 図3.10の中間命令列 . . . 17

3.12 図3.10のコードの展開 . . . 18

4.1 アトムリストの例 . . . 23

4.2 始点アトム選択アルゴリズム . . . 24

5.1 扱う重み付き無向グラフ . . . 26

5.2 LMNtalで記述した最短経路問題. . . 26

5.3 アトムeの例 . . . 26

5.4 アトムcostの例 . . . 26

5.5 ルールの適用条件 . . . 27

5.6 図5.5を意味するグラフ構造 . . . 27

5.7 HyperLMNtalで記述した最短経路問題 . . . 28

5.8 HyperLMNtalでエンコードした際のルールの適用条件. . . 28

5.9 単純なエンコード法 . . . 29

5.10 エンコードするグラフ . . . 30

5.11 図5.10をLMNtalでエンコードしたときのプログラム. . . 30

5.12 図5.11のLMNtalグラフ. . . 30

5.13 エッジのエンコードをリンクにしたときのプログラム . . . 31

5.14 図5.13のLMNtalグラフ. . . 31

5.15 今回探索するグラフ構造 . . . 32

5.16 グラフ中の三角形を探索するルール . . . 32

6.1 アトム操作命令 . . . 34

6.2 headatom命令 . . . 35

6.3 tailatomlist命令 . . . 35

6.4 ルール適用の流れの変化 . . . 37

7.1 並列パターンマッチング命令 . . . 40

7.2 図3.11の中間命令列の拡張 . . . 40

7.3 始点アトムの分配例 . . . 41

7.4 並列パターンマッチング手法における始点アトム選択アルゴリズム . . . . 44

8.1 アトムの動的操作による効果(最短経路問題) . . . 47

8.2 並列パターンマッチングの性能評価(最短経路問題) . . . 48

8.3 アトムの再利用による効果(グラフ構造探索問題) . . . 49

8.4 アトムの動的操作による効果(グラフ構造探索問題) . . . 50

8.5 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 10%) . . 53

8.6 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 1%) . . . 53

8.7 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.1%) . . 54

8.8 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.01%) . 54 8.9 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 10%) . . 55

8.10 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 1%) . . . 55

8.11 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.1%) . . 56

8.12 依存型並列パターンマッチングの性能評価(グラフ構造探索問題, 0.01%) . 56 8.13 図8.11の計測の続き . . . 56

A.1 グラフ中のunaryノードを消去するルール . . . 64

A.2 グラフ中の三角形を抽出するルール . . . 65

A.3 グラフ中の三角形を抽出するルール . . . 65

表目次

6.1 アトムの動的操作時に指標となるアトムの優先度 . . . 36 8.1 実験環境 . . . 46

第 1 章

序論

1.1 背景

CPU の処理速度はプロセッサ技術の発展により, ムーアの法則に準じて著しく向上し た. しかし,今日ムーアの法則は限界を達しており,以前と同様にコンピュータの処理速度 が向上するのは難しいと考えられている[11]. さらなる処理速度の向上を図る手法として, 複数CPUを使用する並列化手法が挙げられる. 今後開発するソフトウェアは並列化プロ グラミング[4]を行うことで,処理速度向上が期待できると考えられる.

一 方, 私 た ち が 扱 う デ ー タ 量 は 年 々 増 加 し て お り, 2020 年 に 価 値 の あ る デ ー タ は

13,000EB 超に達する見通しである¹. 生成されるデータの中で, モノのインターネッ

ト(Internet of Things)から得られる情報の割合が年々増えていき, それらの情報が今後新

しいビジネススタイルにつながると考えられている². 新たな情報を得るためには,生成さ れたデータ中から有能な情報を高速に抽出する必要がある. このことはデータマイニング を行うソフトウェアや制約に基づいて処理を行うソフトウェアの性能向上を考える際に非 常に重要である.

大規模データから新たな情報を手に入れられる他に, 個々のデータ同士の関係からも有 能な情報を得ることができる. 近年SNSなどの急速な発達³により,個々の単純な関係では なく複雑な関係を扱うことが今後開発されるソフトウェアに求められる. 物事の複雑な関 係を抽象的に扱った構造がグラフ[3]である. 部分的にグラフを書き換えることで実行が 進む系をグラフ書換え系という. グラフ書換え系をコンピュータ上で実現する際, グラフ

1 http://www.emc.com/about/news/press/2014/20141209-01.htm

2 http://www.emc.com/collateral/analyst-reports/idc-digital-universe-2014.pdf

3 http://www.ictr.co.jp/report/20140821000067.html

構造を容易に扱えるデータ構造は自明でない. さらにグラフ書換え系が大規模グラフデー タを扱う際に,処理系が扱うグラフのデータ構造によって,書き換えられる部分グラフ構造 を探索するのに多大な時間がかかると考えられる. したがって,グラフ書き換え系を実現 する処理系は大規模グラフデータの中から, 書き換わる部分グラフ構造を高速に探索する ことが重要である.

LMNtal[6][8]は階層グラフ書換えに基づく並行言語モデルであり,書換え規則によって

階層グラフ構造を書き換えることでプログラム実行が進むグラフ書換え系の1つである.

LMNtalの実行時処理系としてSLIM[12]が近年開発されている. SLIMの開発により, 以

前の実行時処理系[9]と比較して,軽量化かつ高速化を実現した.

私たちが扱うデータ量が著しく増えている近年,大規模LMNtalグラフを扱うプログラ ムを現実的な時間内で処理できるよう,さらにSLIMを拡張して実行処理をできるだけ最 適化しなければならない. しかし現状のSLIMは扱うグラフの規模に対するスケーラビリ ティが非常に悪い. その主な原因として, LMNtalグラフから書き換わる部分グラフ構造を 探索する過程に課題があることが挙げられる.

1.2 研究の目的

本研究の目的はグラフ書換え系において, 書き換わるグラフ構造を効率よく探索して処 理の高速化を図ることで,扱うグラフのスケーラビリティを向上させることである. 具体

的にはLMNtal実行時処理系SLIMにおいて,大規模LMNtalグラフを使用したプログラ

ムが現実的な時間内で処理できるように,書換え規則適用時のグラフパターンマッチング 処理の効率化を図り,実行時間の短縮を目指すことである.

1.3 論文の構成

本論文の構成は下記の通りである.

第2章ではグラフ理論の基礎に関して述べる. 第3章ではグラフ書換え系の1つである

LMNtalとその処理系に関して述べる. 第4章ではLMNtal実行時処理系 SLIMに関して

述べる. 第5章では本論文で扱う例題に関して解説する. 第6章では提案手法の1つであ るアトムの動的操作に関して述べる. 第7章では提案手法の1つである並列グラフパター ンマッチングに関して述べる. 第8章では第6, 7章の提案手法を使用した評価実験の結果 と考察を述べる. 第9章ではまとめと今後の課題に関して述べる.

第 2 章

グラフ理論

本章ではグラフ理論の基礎とグラフパターンマッチングに関して述べる. この章では主 に文献[3], [5]を参考に記述した.

2.1 グラフ

グラフGとは,ノードとエッジから成り立つデータ構造であり,以下のように表現する. G =(V,E)

一般的なグラフの例として図2.1に示す. Vはノードの有限集合, Eはエッジの有限集合 であり,グラフはこの2つの集合の組である.

図2.1 一般的なグラフの例

ある2つのノード間に複数のエッジが存在する場合,それらのエッジを多重エッジとい う. また,エッジの両端が同じノードに接続されているエッジを自己ループという.

図2.2 多重エッジを含むグラフ 図2.3 自己ループを含むグラフ

多重エッジや自己ループが存在しないグラフを単純グラフという. 図2.1 は単純グラフ に属する. 単純グラフにおけるエッジは基数が2であるノードの部分集合の集合とも定義 することもできる. すなわち単純グラフのエッジEは以下のように表すことができる.

E ={e⊆V | |e|= 2}

エッジには向きをつけることができ,向きがあるエッジを有向エッジ,向きがないエッジ を無向エッジと呼ぶ. 有向エッジから成り立つグラフを有向グラフ, 無向エッジから成り 立つグラフを無向グラフという. 図2.1は無向グラフに属する.本論文で扱うグラフは無向 エッジを主に使用する.

エッジに重みを伴ったグラフを重みつきグラフという. 本論文での重みは0を除く自然 数のみを前提とし,図中のエッジの横に付随している自然数をそのエッジの重みとして話 を進める.

図2.4 有向グラフ

2 1 3

1

6 4

1 3

6

5 2

2

5

2

図2.5 重みつきグラフ

2.2 連結グラフ

グラフ理論における通路とは隣り合うノード同士がエッジによってつながっているノー ドの列である. すなわち通路wは以下のように表すことができる.

w={v₀,v₁, . . . ,v_k}, k ≥1, {v_j,v_j+1} ⊆ E f or j= 0,1, . . . ,k−1

通路の集合のうち,v₀ = v_k となるwを閉路という. 通路を形成する列のうち,あるノー ドが他のどのノードとも等しくならないときの通路を道という. グラフ中の任意の２つの ノードの間に道が存在するグラフを連結グラフという. 図2.1は連結グラフに属する. 

2.3 部分グラフ

グラフG =(V,E)の部分グラフG^′ とはグラフGのノードVの部分集合V^′ とエッジの 端点の少なくとも一方がV^′ に含まれているエッジEの部分集合E^′ から形成されるグラ フである.

2.4 疎グラフと密グラフ

グラフはさらに存在するエッジの数によっても分類することができる. グラフGに存在 するノードV に対して,エッジ Eの数が|V|log|V|^{未満のときを疎グラフ},|V|log|V|^以上 のときを密グラフという. 図2.1は疎グラフに属する. 

2.5 最短経路問題

グラフ理論における最短経路問題とは重みつきグラフGにおいて,あるノードから他の ノードまでの最小コストを求める問題であり, カーナビの経路案内やインターネット上の 通信の効率化などに応用されている. 問題の種類として,G に存在する２つのノード間の 最小コストを求める2頂点対最短経路問題(one to one),Gに存在する1つのノードからそ れ以外のすべてのノード間の最小コストを求める単一始点最短経路問題(one to all),さら に単一始点最短経路問題をG に存在するすべてのノードに対して行う全点対最短経路問

題(all to all)が挙げられる. 本論文においては単一始点最短経路問題を前提として論ずる.

最短経路問題を解く有名なアルゴリズムとしてダイクストラアルゴリズム[5]が存在す

る. このアルゴリズムの擬似コードを図2.6に示す. ダイクストラアルゴリズムの計算量は 扱うグラフG = (V,E)の場合, 疎グラフにおいてはO((E+V) logV),密グラフではO(V²) となる.

proceduredijkstra single source shortestpath(V,E,w,s) 1: V_T :={s}

2: for allv∈(V−V_T)do 3: if(s,v)existthen 4: l[v] :=w(s,v) 5: else

6: l[v] :=∞ 7: end if 8: end for

9: whileV_T ,Vdo

10: find a vertex u such that l[u] :=min{l[v]∥v∈(V−V_T)} 11: V_T :=V_T ∪ {u}

12: for allv∈(V−V_T)do

13: l[u] :=min{l[v], l[u]+w(u,v)} 14: end for

15: end while

図2.6 ダイクストラアルゴリズム

2.6 グラフ書換え系とグラフパターンマッチング

グラフ書換え系とはグラフ構造を書き換えていくことで実行が進む系である.

グラフ理論におけるパターンマッチングとはグラフGのエッジの集合Eのうち,互いに 端点のノードを共有しないエッジの集合E^′ を求める問題である.

この論文におけるグラフパターンマッチングとはグラフ理論におけるパターンマッチン グとは異なり, 規則によって書き換わる部分グラフ構造をグラフ中から抽出することと定 義する. すなわちグラフGにおいて書き換わる部分グラフG^′ を探索することと定義して 論ずる.

第 3 章

LMNtal _{とその処理系}

本章ではLMNtalの基礎とその言語処理系に関して述べる. この章を記述するにあたり,

文献[8][9]を主に参考にして記述した.

3.1 LMNtal の基礎事項

LMNtal¹とは階層グラフ構造の部分的な書換えによって実行が進むグラフ書換え系の

1つである. LMNtalの構成要素はアトム,リンク, 膜, ルールの4つである. このうちルー

ルを除く3 つの要素から成り立つ階層グラフ構造をLMNtal グラフという. LMNtal グ ラフの例を図3.1 に示す. また, 膜を除くアトム, リンク, ルールから成り立つLMNtalを flatLMNtalと呼ぶ. グラフ書換えはルールによって実現される.

a

b d

c a

1 a

1 a

図3.1 LMNtalグラフの例

1 http://www.ueda.info.waseda.ac.jp/lmntal/

以下の小節において, LMNtalの個々の要素に関して言及する.

3.1.1 アトム

アトムはグラフ理論におけるノードに対応する. アトム内の情報としてアトム名とarity の２つがある. arityとはそのアトムから延びるリンクの本数に対応する. アトム名とarity の組をファンクタという.

LMNtalのアトムはグラフにおけるノードとは違い, アトムから延びるリンクに順序が

付いている. 本論文において図に示したLMNtalグラフ中のアトムは時計9時方向から反 時計回りの順番でリンクが順序づけられていると仮定する. 例として図3.2 に示したアト ムにおいて,リンクの順序は赤字で記述した数字に対応する.

LMNtalプログラムにおいてアトム名は小文字アルファベットから始まる. 本論文では

アトム名が“a”であるアトムを「アトムa」と記述している. アトムは関数のように引数 を所持しており, 各引数にはリンク名が記述される. 引数の順序はアトムから伸びている リンクの順序に対応している.

1

a

2 1 a

3

2

図3.2 リンクの順序付け

3.1.2 リンク

リンクは グ ラ フ 理 論 に お け る 無 向 エ ッ ジ に 対 応 し, 2 つ の ア ト ム 間 の 接 続 を 担 う.

LMNtalプログラムにおいてリンク名は大文字アルファベットから始まり, LMNtalグラフ

において同じリンク名は2回登場する.

3.1.3 膜

膜はプロセスの多重集合を形成する. プロセスとはアトム, リンク, 膜,ルールから成り 立つ集合である. 膜を利用することで, ルールの適用範囲を制御することができる. また, 膜の操作は相対的に階層が低い位置にある膜に存在するルールによって行うことができ る. LMNtalプログラムにおいて膜は“{” (プロセス) “}”と記述する.

図3.1を記述したLMNtalプログラムを図3.3に示す. プログラム中の0引数のアトム cが一番高い階層に存在する. 

a(L),1(L),a(L1),1(L1),a(M).

{

a(N,N1),b(N1,N2,M),d(N2,N).

{ c().

}.

}.

図3.3 図3.1を記述したLMNtalプログラム

3.1.4 ルール

ルールはLMNtalグラフを書き換える規則である. ルールはHead部,Guard部,Body

部から成り立ち,以下のようにLMNtalプログラムでは記述される. Head :- Guard|Body.

Head部はルールによって書き換えられるLMNtalグラフの部分構造, Guard部はルール によるグラフ書換えに必要な制約条件, Body部はルールによって書き換わるLMNtalグラ フの部分構造を記述する. 本論文ではルール中のHead部をルールの左辺, Body部をルー ルの右辺と呼んでいる. Guard部による制約条件がない場合は, 左辺の部分グラフ構造が ルールによって無条件で右辺のグラフ構造に書き換わる. ルールの左辺のグラフ構造を探 索し, ルールの右辺のグラフ構造に書き換える行為を本論文では「ルールを適用する」と 呼ぶ.

ルール中の左辺と右辺の部分グラフ構造にそれぞれ１回ずつ出現するリンクを自由リン ク,いずれのどちらかに2回出現するリンクを局所リンクという.

3.2 LMNtal の特徴

LMNtalの特徴を以下に示す.

グラフ構造と階層構造との組み合わせ

LMNtalはアトムとリンクによるグラフ構造と膜による階層構造の組み合わせに

よって高い表現能力を持ち,複雑な計算モデル（λ^計算,π^計算,ambient計算）を簡 潔に記述することができる．

実行の非決定性

LMNtalのプログラム実行は一般的なプログラミング言語とは異なり, 実行順序が

一意に定まらない. LMNtalのルールは左辺の部分グラフ構造を右辺に書き換える ことで実行が進むが, 扱うLMNtalグラフによって左辺にマッチする部分グラフ構 造は複数存在する可能性が考えれられる. また, LMNtalプログラムにおいて複数の ルールが存在する場合, LMNtalグラフによって複数のルールが適用できる可能性 が考えられる. 以上のことより, LMNtalは非決定的な実行を行うことが可能で, 実 行ごとに異なる結果を出力することが十分考えられる.

モデル検査におけるモデル記述言語

LMNtal実行時処理系 SLIMにはモデル検査機能[10]が導入されている. LMNtal

を使用したモデル検査は扱うシステムとその仕様がどちらもLMNtalで記述できる ことを特徴としている.

3.3 LMNtal の構文

LMNtalの構文を図3.4に示す. ちなみにXi はリンク名, pはアトム名, Pはプロセス,T はプロセステンプレートである.

3.4 プロセス文脈と型つきプロセス文脈

LMNtalにおけるプロセス文脈とはルールにおいて記述されていない同階層の部分プロ

セスを指す. プロセス文脈もアトムと同じように複数の引数を持つことができるが, その 引数には明示的な自由リンクと明示的でない自由リンクの2種類のリンクが記述できる. さらにプロセス文脈はルール適用によって複製,消去できる.

P ::= 0 （空）

| p(X1, . . . ,Xm) (m≥0) （アトム）

| P,P （分子）

| {P} ^（セル）

| T :- T （ルール）

T ::= 0 （空）

| p(X1, . . . ,Xm) (m≥0) （アトム）

| T,T （分子）

| {T} ^（セル）

| T :- T （ルール）

| @p （ルール文脈）

| $p[X1, . . . ,Xm|A] (m≥0) （プロセス文脈）

A ::= [ ] （空）

| *X （リンク束）

図3.4 LMNtalの構文規則

図3.5における “$p”がプロセス文脈である. ルールの記述によりこのプロセス文脈は 膜内の１つのアトムa以外のプロセスに一致する. このルールは膜内の１つのアトムa以 外のプロセスを一つ階層が下の膜に移動させる意味を持つ. 具体的には$pはbに一致し, ルールによってbが一つ下の階層の膜に移動する.

{ a,b.

b:-c.

}.

{a,$p[|*A],@q}/:-$p[|*A].

図3.5 プロセス文脈を利用したLMNtalプログラムの例

ルール中の「/」はこの前に記述してある膜が停止膜であることを意味する. 停止膜とは 膜中のルールがすべて適用できなくなったときの膜を指す. つまり膜の中のルールがすべ て反応した後に外のルールが適用される. 外部的なルールによって, 停止膜中のプロセス に変化が起きたときは,その膜は停止膜でなくなる.

ルール中の“@q”はルール文脈と言い,この場合は3行目の「b :- c.」に一致する. ルー ルはルール内の右辺に記述できるので, ルールによって新たなルールを生成することが できる. 膜内のルールは階層が下のルールによって消去したり,他の膜に移動させたりで きる.

型付きプロセス文脈は文字通りプロセス文脈に型をつけたプロセス文脈であり,ルール のガード文において型の制約をつけることができる. 以下主要な型に関して説明する.

• ground型

– 膜を含まない連結部分グラフにマッチする.

• unary型

– 1価のアトムにマッチする. ground型のsubsetである.

• int型

– アトム名がint型である1価のアトムにマッチする. unary型のsubsetである.

• string型

– アトム名が string型である 1価のアトムにマッチする. unary 型のsubset で ある.

3.5 システムルールセットと LMNtal ライブラリ

LMNtal では算術演算など全ての膜に適用されるルールが用意されており, それらの

ルールはシステムルールという. 例えば3引数のアトム“+”において, リンク先のアトム の型がどちらもint型であるとき, システムルールによってリンク先のアトムの加算が行 われる.

さらに LMNtalには様々なLMNtalライブラリが用意されている. 例えば標準入力か

ら得た文字列をアトムに変換するモジュールや,引数に接続したアトムの型を変換するモ ジュールなどが用意されている.

これらの機能は第4章で説明するSLIMにおいて, 実行時に“–use-builtin-rule”のオプ ションを指定することで使用できる. しかしこの機能は処理系の実行性能に影響を及ぼす ので,本論文の性能評価では使用していない.

3.6 LMNtal プログラムの省略記法

本節ではLMNtalプログラムの省略記法に関して述べる.

• a()⇔ a

– 0引数のアトムはカッコを省略することができる.

• a(X,Y)⇔ Y =a(X)

– アトムの最終引数はイコールで表現することができる.

• a(X,Y), Y =b(Z)⇔a(X,b(Z)) – Yを直接代入することができる.

• $x[A|[]]⇔ $x[A]

– 明示的でない自由リンクが空のときに省略することができる.

• $x[A]⇔A= $x

• a(X,A), A=$x[Z]⇔a(X,$x[Z]) – アトムの省略記法と同様.

3.7 HyperLMNtal

HyperLMNtal[13][17]とは新たな要素ハイパーリンクを追加したLMNtalの拡張言語モ

デルである.

ハイパーリンクとはLMNtalの要素の一つであるリンクとは異なり,１つ以上のアトム を接続することができるリンクである. ハイパーリンクは型付きプロセス文脈のunary型 の拡張として扱われている. しかしリンクの一種として直感的に扱えるように, リンクの 記述方法の頭に“!”を付けることで型付きプロセス文脈を記述せずにハイパーリンクを表 現することができる.

ハイパーリンクに関わる機能を複数説明する. 1つ目はルールのHead部で宣言された ハイパーリンク!H を使用して, Guard部に“num(!H)”と記述することで, 指定したハイ パーリンクのリンク数を取得することができる. 2 つ目はルールのHead部で宣言した複 数の異なるハイパーリンク“!H,!I”を使用して, Body 部に“!H ><!I”と記述することで, 2つの異なるハイパーリンクを併合することができる. 3つ目は“!H : a”のように記述す

ることでハイパーリンクに属性をつけることができる. この場合ハイパーリンク!H の属 性に“a”を付けることができる. この属性は制約条件としてルールのHead部やGuard部 で使用することができる.

HyperLMNtalでは型付きプロセス文脈の拡張として, hlground型が導入されている. こ

の型はground型ではマッチしないハイパーリンクをマッチできるように設計されている.

ハイパーリンクを使用した例題プログラムを図3.6 に示す. このプログラム中のルール は1引数のアトムaのリンク先のハイパーリンクが3つ未満のリンクから成り立ち,かつ 1引数のアトムcのリンク先がハイパーリンクであり,さらにアトムaとアトムcが接続 しているハイパーリンクが異なるときに適用され, 2 つの異なるハイパーリンクは併合さ れて1つのハイパーリンクを形成する.

ハイパーリンクは現状のLMNtalコンパイラ(後述)においてグラフの初期構造に記述 できない. したがって,このプログラムではアトムinitを使用してハイパーリンクを含むグ ラフを生成するルールが2行目に記述されている. .

init.

init:-a(!H),b(!H),c(!I),d(!I).

a(!H),c(!I):-num(!H)<3|a(!H),c(!I),!H><!I.

図3.6 HyperLMNtalプログラムの例

a

d c

b a

d c

b init

図3.7 図3.6の実行の流れ

3.8 LMNtal 処理系概要

LMNtal処理系[9]の大まかな概要を図3.8にまとめた.

LMNtalȗȭǰȩȠ ɶ᧓ԡˋЗ ܱᘍኽௐ

LMNtal dzȳȑǤȩ ܱᘍ଺ϼྸኒ

図3.8 LMNtalプログラムの実行の流れ

LMNtalプログラム(*.lmn)は最初に LMNtalコンパイラによって中間命令列(*.il) に

変換する. そして実行時処理系によって中間命令を解釈実行を行う. 中間命令はLMNtal 独自の命令である.

実行時処理系の一つとしてSLIM[12]が近年開発されている. 詳細は4章で述べる.

他にもLMNtalに関連した多数のアプリケーションが存在し, 処理系を含めこれらのア

プリケーションは論文執筆時点でGitHubにてソースコードが公開されている².

3.9 LMNtal の中間命令

本節ではLMNtalの中間命令に関して述べる. 実行時処理系はLMNtalプログラムを処

理する際,一度中間命令列に変換してからその中間命令列を解釈実行する. 図3.9には今回 重要となる中間命令を挙げている.

3.10 ルール適用におけるグラフパターンマッチング

LMNtalルールをコンパイルした際に, 出力された中間命令は主に2つの部分に分ける

ことができる. コンパイラが出力したルール1本当たりの中間命令列にはcommit命令が 必ず1つだけ存在し, commit命令より前の部分命令列をグラフパターンマッチ部, commit 命令より後の部分命令列をグラフ書換え部と呼ぶ. 前者はルール左辺の部分グラフ構造を グラフ中から探索するための中間命令列,後者はルールによってグラフを書換えを行うた めの中間命令列である. グラフパターンマッチ部の中間命令列にしたがってグラフ構造を

2 http://github.com/lmntal

findatom[atom, srcmem, f unc]

膜srcmemに存在し,ファンクタ f uncであるアトムを１つ取り出し,その参照をatomに代 入する.取り出せるアトムがなくなった場合,この命令は失敗する.

commit[rulename, lineno]

ルール適用時のグラフパターンマッチングに成功すると達する命令. 以降の中間命令は失敗 しない.

removeatom[atom, srcmem, f unc]

ファンクタが f uncであるアトムatomを膜srcmemから取り出す.

copyatom[dstatom, srcmem, srcatom]

膜srcmemに中に存在するアトムsrcatomを複製してアトムdstatomを生成する.

newatom[atom, srcmem, f unc]

ファンクタが f uncであるアトムatomを膜srcmemに生成する.

newlink[atom₁, pos₁, atom₂, pos₂, srcmem]

アトムatom₁の第pos₁引数とアトムatom₂の第pos₂引数をリンクで接続する。

freeatom[atom]

アトムatomのメモリを解放する。

図3.9 主要なLMNtal中間命令の解説

検査することをパターンマッチと呼び,左辺の部分グラフ構造を探索することをグラフパ ターンマッチングと呼ぶ.

中間命令列によって左辺の部分グラフ構造を探索する際に, 探索の開始地点となるア トムを本論文では起点アトムと呼ぶ. この起点アトムはfindatom命令によって探索され, ルール左辺に存在する連結グラフの数だけ存在する. 1回ルール適用を行う時に,パターン マッチは最悪で起点アトムの組み合わせ分だけ行われる.

HyperLMNtalにおいてパターンマッチ数を最小限に抑える探索手法が存在する[17]. こ

の最適化手法はハイパーリンクをたどってグラフパターンマッチングすることで,始点ア トムの候補となるアトムを必要最小限に抑えることができる. 本論文で扱う例題はこのハ イパーリンクによる最適化された探索手法でグラフパターンマッチングが行われている.

LMNtalグラフパターンマッチングのアルゴリズムを具体的な例を挙げながら説明する.

図3.11は図3.10に記述したルールのコンパイル時に生成した中間命令列である. 図3.10

のルール左辺は2つの連結部分グラフから成り立っている. 図3.11の中間命令列のうち,

2行目から4行までが“a(b)”の部分連結グラフのパターンマッチング, 5行目から7行目

までが“c(d)”の部分連結グラフのパターンマッチングである. 実行時処理系はこの中間命

令にしたがって,グラフパターンマッチングとグラフ書換えを行う. a(b),c(d):-.

図3.10 特定の部分グラフ構造を消去するLMNtalルール

spec [1, 5]

findatom [1, 0, ’b’_1]

deref [2, 1, 0, 0]

func [2, ’a’_1]

findatom [3, 0, ’b’_1]

neqatom [3, 1]

deref [4, 3, 0, 0]

func [4, ’c’_1]

commit ["_abcb", 0]

removeatom [1, 0, ’b’_1]

removeatom [2, 0, ’a’_1]

removeatom [3, 0, ’b’_1]

removeatom [4, 0, ’c’_1]

freeatom [1]

freeatom [2]

freeatom [3]

freeatom [4]

proceed []

図3.11 図3.10の中間命令列

LMNtalコンパイラがルール左辺のグラフ構造から始点アトムをどのように選んでいる

のかを説明する. 現状のLMNtalコンパイラはルールの一番左にあるアトムを始点アトム として選んでいる. ただし, 省略記法でルール左辺の部分グラフ構造を記述した場合は必 ずしも一番左に書いたアトムが始点アトムになるとは限らない. 省略記法で書かれている 図3.10はコンパイラ内部で図3.12のように展開される. 始点アトムを基準として,そこか らリンクを使ってたどることでパターンマッチを行う. 始点アトムからたどることができ ない部分グラフは再度始点アトムを設定して同様にパターンマッチを行う. 図3.12 にお いて1つ目の始点アトムは一番左に記述されているアトムbとなる. このときアトムbか

らアトムaをたどることができるが,アトムcとアトムdはたどることができない. した がって,たどることのできないアトムはそのアトム集合のうち一番左側に記述されている アトムを次の始点アトムとして再度設定する. この例の場合はアトムcを2つ目の始点ア トムとして設定している. 設定する始点アトムの数はルール左辺に存在する部分連結グラ フの数に等しくなる. ルールにしたがってLMNtalコンパイラはすべてのアトムが探索さ れるよう,中間命令列を作成する.

b(X),a(X),d(Y),c(Y):-.

図3.12 図3.10のコードの展開

LMNtalの中間命令は解釈実行する際に戻り値として成功か失敗かを返す. 命令の失敗

は意図しないグラフ構造に到達したときやルールのガード条件を満たさない場合に起こ る. 中間命令が失敗した場合はバックトラックが起き, 失敗した命令の上にある最初の特 殊な中間命令（例えばfindatom命令,以降特殊な命令を findatom命令として論ずる）ま でバックトラックする. バックトラックによってfindatom命令まで戻った時,始点アトム の候補となる他のアトムを探索し, 再度中間命令列にしたがってパターンマッチを行う.

findatom命令も指定したファンクタのアトムが存在しないとき,またはfindatom命令で始

点アトムとなるアトムがすべて以降の中間命令で失敗してバックトラックが起きたとき にバックトラックする. バックトラックによって中間命令列の先頭に到達した場合, その ルールの適用は失敗する. すなわち,このルール左辺の部分グラフ構造にマッチするグラ フが同じプロセス内に無かったことになる.

グラフ書換え部の中間命令は必ず成功するため,バックトラックが起こらない. すなわ ち解釈実行によって, commit命令まで実行した場合は必ずそのルール適用が成功し,グラ フ書換えが行われる.

3.11 ルール適用におけるグラフ書換え

この節ではルール左辺にマッチした部分グラフをどのように書き換えるかを説明する. 最初にマッチした部分グラフ構造中のアトムをグラフ中からremoveatom命令, remove- mem命令などの命令を使用してグラフ中から取り出す. そして生成するルール右辺のグラ

フ構造をnewatom命令, newmem命令, newlink命令などの命令で作成する. ルール右辺と

左辺に同じ名前のリンク(つまり自由リンク)が存在する場合はrelink命令によってリン クをつなぎ換える. 最後にfreeatom命令, freemem命令によって書換えによって存在しな

くなったアトムを消去する.

以前のLMNtalコンパイラはルールによるグラフ書き換えるときに,左辺の部分グラフ

構造を一度壊した後,右辺の部分グラフ構造を生成していた. しかし左辺と右辺それぞれ の部分グラフ構造の差分が極めて少ないときに,同じファンクタを持つアトムを壊して再 度生成することは,処理系の性能を向上させることを考えると得策ではない. アトムの再

利用[14][16]とはルール左辺と右辺それぞれの部分グラフを比較して,同じファンクタを

持つアトムが存在する場合は最大限再利用する最適化手法であり, ルール左辺と右辺のグ ラフの差分が小さいときに余計なアトムの消去や生成をしなくて済むことを特徴として いる.

本論文では常にLMNtalコンパイラはアトム再利用の最適化が行われていることを前提 としている.

3.12 ルール適用の計算量

本節では1回あたりのルール適用時の計算量をグラフパターンマッチングとグラフ書換 えそれぞれに対して考察する.

グラフパターンマッチングはルール左辺の部分グラフ構造に存在する始点アトムの数, 各始点アトムの候補となるアトムの数, ルール左辺に明示しているアトムやリンク, プロ セス文脈の数など様々な要因によって計算量が変化する. 特にプロセス文脈の型がground

型やhlground型の場合はリンク先の部分連結グラフの規模分の計算量を要する. 本研究で

扱う例題はルール左辺に明示しているアトムやリンク, プロセス文脈の数と比較して各始 点アトムの候補となるアトム数が極めて多いこと,かつプロセス文脈の型が ground型を 扱わないことを特徴としている. したがって, グラフパターンマッチングの計算量は始点 アトムの数とそれぞれの始点アトムの候補となるアトムの数に依存すると改定する.

さらに始点アトムのうち,ハイパーリンクの最適化探索手法で探索される始点アトムは 候補となるアトム数を制限することができる. 本研究で扱う例題はハイパーリンクで探索 される始点アトムの候補数が最初に始点アトムの候補となるアトムの数と比較して極めて 少ないことを特徴としている. よって,最終的にグラフパターンマッチングの計算量は最 初に選ばれる始点アトムの候補となるアトム数に依存すると仮定する.

グラフ書換えの計算量は書き換わるグラフの差分に依存する. 特に ground型のプロセ ス文脈を複製する場合は, その部分連結グラフの規模分だけの計算量がかかる. しかし, 本 研究で扱う例題はルールによって書き換わるグラフの差分が始点アトムの候補となるアト ムの規模と比較すると極めて小さく,かつground型を使用しないことを考えると,グラフ

書換えにおける計算量は無視できるくらい小さい規模と仮定する.

まとめると,本論文ではルール適用の計算量はそのままグラフパターンマッチングの計 算量に等しくなり,その計算量は最初に探索する始点アトムの候補となるアトムの数に依 存する.

第 4 章

LMNtal _{実行時処理系} SLIM

この章ではLMNtalの実行時処理系SLIM[12]に関する詳細を述べる.

4.1 SLIM 概要

以前開発されていた LMNtalの実行時処理系 [9]はJava言語で実装されていることを 理由に, メモリ使用や実行性能に課題が存在した. SLIMはこれらの課題を解決するため に,軽量化かつ高速化を目的として開発された.

SLIMはC言語によって実装され,さらに以前の実行時処理系と比較してLMNtalグラ フに関する必要最低限のオブジェクトのみを生成しているので, 軽量化かつ高速化を実現 した.

SLIMにはモデル検査機能[10]が導入されており, LMNtalを記述言語としてシステム の性質を検証することができる.

4.2 SLIM 実行の種類

LMNtalの特徴の1つとして,プログラムの実行が非決定的な点が挙げられる.したがっ

てSLIMには2種類の実行モードが存在する.

一つ目は非決定実行モードであり,遷移する可能性のある状態を網羅的に探索する. 遷 移はルールによるグラフ書換えに, 状態は LMNtalグラフに対応する. 異なる LMNtalグ ラフは別状態となる. このモードはSLIM実行時に“–nd”オプションを付けることで実行 できる.

二つ目は通常実行モードであり,複数ある状態遷移の実行経路のうち, 1つの経路を実行

する. 通常実行モードの目的として,いかに最終状態 (どのルールも適用できない状態)ま で高速に遷移できるかが鍵となる. このモードはSLIM実行時に“–nd”オプションを付け ないことで実行できる.

本論文におけるSLIMの実行は通常実行モードであることを前提としている.

4.3 SLIM における LMNtal グラフの表現方法

この節ではSLIM内でどのようにLMNtalグラフを表現しているかを説明する.

SLIMにおいて,アトムを表現するデータ構造が主に2種類存在する. 1つ目はシンボル

アトムで, SLIM内で専用のアトム構造体によって表現されている. 構造体内部にはリンク

によって隣接しているアトムのポインタを所持している. このことを理由にSLIMではリ ンクを表現する構造体は存在しない. 2つ目はデータアトムで, string型やint型などの型 がついているアトムを隣接しているシンボルアトムの構造体に直接データを書き込むこと で表現されている. このデータアトムの存在によって, SLIMは大幅にメモリ消費量を抑え ることが可能となった. 逆にデータアトム同士が隣接するLMNtalグラフではSLIMにお いて扱えないことが短所として存在する.

SLIMではシンボルアトムを膜ごとに管理している. どの膜にも存在していない一番下 の階層にあるアトムはグローバル膜と呼ばれる膜に所属していると考える. 膜にも独自の 構造体が用意されており, それぞれの膜は同じ階層同士の膜を連結リストによって管理さ れている. さらに膜の構造体にはその膜の中に存在する階層が1つ上の膜の構造体, 膜が 存在する階層が1つ下の膜の構造体のポインタを所持している.

膜の中のシンボルアトムは同じファンクタごとに連結リスト構造で管理されている. こ のリスト構造をアトムリストという. ちなみにデータアトムを要素とするアトムリストは 存在しない. アトムリストの例を図 4.1に示す. 図中の上のアトムリストは1引数のアト ムnのアトムリストであり,下のアトムリストは2引数のアトムaのアトムリストである. 本論文中で図に示したアトムリストは左側がアトムリストの先頭であることを仮定して いる.

特殊な LMNtal のデータ構造をいくつか紹介する. 1 つ目は膜を貫くリンクであり,

SLIM内部においては特殊なアトム(in, out) によって表現されている. 2つ目はハイパー リンクであり,こちらも特殊なアトム(+)によって同じハイパーリンクを管理している. 詳 しくは文献[17]に委ねる.

n n n n n n

a a a a

図4.1 アトムリストの例

4.4 グラフパターンマッチング

SLIMにおけるグラフパターンマッチングはコンパイラによって生成された中間命令に したがって, ルール左辺の部分グラフ構造を探索する. この節ではグラフパターンマッチ ング時において,グラフの探索始点であるである始点アトムをSLIMの内部でどのように 探索しているかを説明する.

SLIMはアトムをアトムリストによって管理しているので, findatom命令によって始点 アトムを選ぶ際に引数に指定されたファンクタと合致したアトムリストを参照し, その 先頭のアトムからパターンマッチを行う. 引数に指定されたファンクタと同じアトムリ ストへの参照はハッシュ値計算によりO(1)で実現されている. 中間命令の失敗によって

findatom命令までバックトラックした場合, アトムリストにおいて失敗したアトムの次に

つながっているアトムを次の始点アトムとして設定し,パターンマッチを再開する. アト ムリスト中の末尾にあるアトムのパターンマッチが失敗した場合, このfindatom命令が バックトラックを起こす.

findatom 命令における始点アトムの選択アルゴリズムの擬似コードを図 4.2 に示す.

TRUEを返すとルール左辺のグラフ構造が探索されたことを意味し, FALSEを返すとルー ル左辺のグラフ構造が探索されなかったことを意味する.

4.5 グラフ書換えによるアトムリストの変化

この節ではグラフ書換え操作によって SLIM内のアトムリストがどのように変化する かを説明する.

ルールによって書き換わるアトムはremoveatom命令によってアトムリストから取り除 かれる. ただし, 右辺にも同じファンクタを持つアトムが存在する場合はアトムの再利用

procedureAlgorithm of choosing a start atom(Atomlist) 1: ifAtomlist non-existthen

2: return FALSE 3: end if

4: Atom:=get atomlist head(Atomlist) 5: Atom_t:=get atomlist tail(Atomlist) 6: while do

7: ifpattern match(Atom)then 8: return TRUE

9: end if

10: ifAtom==Atom_tthen 11: return FALSE 12: end if

13: Atom:=get atomlist next(Atom, Atomlist) 14: end while

図4.2 始点アトム選択アルゴリズム

による最適化によってアトムリストから取り除かれない.

ルールによって生成されるアトムはnewatom命令によって新たに生成され,そのアトム は同じファンクタのアトムリストの末尾に挿入される. 挿入するアトムと同じファンクタ のアトムリストはハッシュ値計算によりO(1)で取得することができる. もし生成したア トムと同じファンクタのアトムリストが存在しない場合,新たにそのファンクタ専用のア トムリストが生成され,生成したアトムが挿入される.

アトムリストが連結リストであることを理由に,アトムリストにおけるアトムの抜去と 挿入にかかる計算量はいずれもO(1)である.

第 5 章

LMNtal _{プログラム例題}

本章では第8章の評価実験で扱うLMNtalプログラムに関して説明する. 本論文で使用 する2つの例題(最短経路問題, グラフ構造探索問題)の特徴として,例題をLMNtalでエ ンコードしたときに1本のルールによって例題の仕様が実現される点が挙げられる.

5.1 最短経路問題

LMNtalの最短経路問題のエンコードは過去に複数の方法[15]が提案されているが, そ

の中で膜を使用しないエンコード方法¹と新たにハイパーリンクを使用したエンコード方 法に関して本節では述べる.

5.1.1 膜を使用しない最短経路問題のエンコード

膜を使用しない方法で最短経路問題をエンコードしたLMNtalプログラム例を図5.2に 示す. このプログラムは図5.1に示した重み付き無向グラフにおいて,ノードaを基準とす る単一始点最短経路問題をエンコードしたプログラムである. このプログラムは2つの主 要なアトム(e, cost)と１本のルールから成り立つ.

アトムeは3引数のアトムであり,エンコードされるグラフのエッジの情報を所持する. 第一引数にはエッジの始点の情報を持ったunary型のアトム,第二引数にはエッジの終点 の情報を持ったunary型のアトム,第三引数にはそのエッジの重みを表す1以上の整数ア トムにそれぞれ接続されている. アトムe単体では1つの有向重み付きエッジを意味する が, 第一引数と第二引数が入れ替わり, 第三引数が等しいアトムeが存在する場合は無向

1 http://www.ueda.info.waseda.ac.jp/lmntal/demo/shortestpathAll2all.lmn

1 3

2

1 3

d c

b a

図5.1 扱う重み付き無向グラフ

cost(a,a,0), cost(a,b,100), cost(a,c,100), cost(a,d,100), e(a,b,2), e(a,c,1), e(c,b,3), e(b,d,1), e(c,d,3),

e(b,a,2), e(c,a,1), e(b,c,3), e(d,b,1), e(d,c,3).

cost($s0,$p,$w1), e($p0,$t0,$w0), cost($s,$t,$w2) :-

$s0==$s, $p0==$p, $t0==$t, $w=$w0+$w1, $w<$w2 | cost($s0,$p,$w1), e($p0,$t0,$w0), cost($s,$t,$w).

図5.2 LMNtalで記述した最短経路問題

エッジを表現することができる. アトムeの具体的なグラフを図5.3に示す.

アトムcost もアトムeと同様な構造をしており,  第一引数のノードから第二引数の ノードまでにかかるコストを第三引数で表している. 第三引数の初期値として, 第一引数 と第二引数が同じノード名の場合には0,異なる場合は100を接続する. (100はマジック ナンバーであり,意味としては∞^{として使用している}. LMNtalでは∞^{を意味するアトム} は表現できない)最終的にプログラムが停止した時, アトムcostの第三引数に所持してい る値が最小のコストとなる. アトムcostの具体的なグラフを図5.4に示す.

e

a b 1

図5.3 アトムeの例

cost

a a 0

図5.4 アトムcostの例

LMNtalにおける最短経路問題はアトム costで所持している第三引数の値をルールに

よって更新していくことで実行が進む. ルールが適用される条件を図5.5に示す. この部分

LMNtalグラフは図5.6のグラフを意味している. 図中のw1 はノードs, p間の道のコスト である. このルールは現在のコスト値wよりも w1+w2 のコスト値の方が小さい場合,w がノードs, t間の最小コストではないと分かるため, 新たにw₁+w₂ をコスト値として更

新する. LMNtalによる最短経路問題のエンコードの特徴として,一本の簡潔なルールで最

短経路問題を解くことができる点が挙げられる.

cost

s p w₁

cost

s t w

e

p t w₂

図5.5 ルールの適用条件

s

t

w w

p

w

図5.6 図5.5を意味するグラフ構造

このエンコード方法の短所として,パターンマッチの回数が必要以上に多くなることが 挙げれる. 現状のエンコードは 1回のパターンマッチにおいて,アトムeを含む部分グラ フを１つ,アトムcostを含む部分グラフを2つ抽出している. このとき,リンク先の情報の 比較によって適用できるかどうかをチェックするため,アトムe,アトムcostそれぞれ存在 する個数を|e|,|c|^とすると, 1回のルール適用あたり最悪O(|e| ∗ |c|²)の計算量が生じる.

5.1.2 HyperLMNtal を使用した最短経路問題のエンコード

現状の最短経路問題のエンコード方法の問題点を解決するために,新たにHyperLMNtal を使用したエンコード方法を行った. HyperLMNtalで記述した最短経路問題を図5.7に示 す. 図5.2の記述方法と異なる点として,同じノードを指すリンク先をハイパーリンクに よってまとめていることにある. ハイパーリンクで同じノードのリンクをまとめることで, ハイパーリンクを使用した最適化探索を適用することができ,探索すべきアトムの量を減 らすことが可能となった. つまり,図5.2では連結していなかった3つの部分グラフ構造を ハイパーリンクによって接続することで,すべてのノードをリンクとハイパーリンクでた どれるようになった.

HyperLMNtalでエンコードした際にルール適用する部分グラフを図5.8に示す. 図5.5

の条件が3つの連結グラフから成り立つのに対し,図5.8の条件が1つの連結グラフから 成り立っていることが分かる. LMNtalでモデルを記述する際に,ルール左辺に存在する連 結グラフの数を最小限にすることがパターンマッチング処理の削減につながる.

init.

init:-

cost(!A,!A,0), cost(!A,!B,100), cost(!A,!C,100), cost(!A,!D,100), e(!A,!B,2), e(!A,!C,1), e(!C,!B,3), e(!B,!D,1), e(!C,!D,3),

e(!B,!A,2), e(!C,!A,1), e(!B,!A,3), e(!D,!B,1), e(!D,!C,3).

cost(!S,!P,$c1), e(!P,!T,$c0), cost(!S,!T,$c2) :-

$c=$c0+$c1, $c<$c2 |

cost(!S,!P,$c1), e(!P,!T,$c0), cost(!S,!T,$c).

図5.7 HyperLMNtalで記述した最短経路問題

cost w₁

cost w

e

w₂

!T

!P

!S

図5.8 HyperLMNtalでエンコードした際のルールの適用条件

5.2 グラフ構造探索問題

前節においては重み付き無効グラフをアトム eを使用したエンコードを行った. 本節で は一般的なグラフをLMNtalにエンコードする手法と, そのエンコード方法を使用した新 たな例題(グラフ構造探索問題)に関して述べる.

5.2.1 ハイパーリンクを使用したグラフ構造のエンコード法

一般的なグラフを LMNtal でエンコードする際, 単純にノードをアトムに, エッジを リンクに対応させるのはあまり好ましくない. 具体的に図 5.9を使用しながら説明する.

LMNtalのアトムは接続されるリンクに順序付けがあることから, グラフをLMNtalグラ

フで一意にエンコードすることができない. 図5.9の左のグラフもLMNtalでは2通りの グラフに変換してしまう可能性がある. 一意にLMNtalグラフへエンコードできないなら ば,複数のグラフに対応したルールを記述しなければならなくなり,必然的にルールの本数 が増加してしまう. よってこのエンコード方法ではLMNtalの特徴である簡潔な表現性が 生かされなくなる. 様々なグラフ問題に対応するためにも,本論文ではハイパーリンクを 使用したグラフのエンコード方法を提案する. エンコード方法のポイントとして, ノード とエッジをどちらもハイパーリンクを使用して表現することである.

a b

c

a b

c

a c

b

図5.9 単純なエンコード法

ノード専用のハイパーリンクはエッジの接続だけではなく, ノードの属性などをハイ パーリンクでまとめることができる. 本手法においてノードの情報は2引数のアトム n を使用して管理されており,第一引数にはノードに接続されているエッジをまとめたハイ パーリンク, 第二引数にはノードの属性をまとめたハイパーリンクに接続されている. ア トムnの第二引数の接続において,属性情報が1つしかない場合は直接リンクでその情報 に接続することができる. 今回の例題は各ノードに1つのフラグの情報のみを所持してい るグラフを扱うので,属性をまとめるハイパーリンクは使用していない.

同様にエッジ専用のハイパーリンクもノードの接続だけではなく,エッジの属性や重み などをまとめて表現することができる. ノードの情報がアトムnで管理されているのに対 して,エッジの情報はアトムeで管理されている.

アトムを表現するハイパーリンクとエッジを表現するハイパーリンクそれぞれの表現範 囲を区別するため,今回のエンコード方法ではポートアトム（2引数のアトムp）とよばれ るアトムが挿入されている. ポートアトムの第一引数にはアトム専用のハイパーリンクに, 第二引数にはリンク専用のハイパーリンクに接続される.