設計と効率的な実装手法

(1)

再帰的な文脈パターンマッチング機能を持つグラフ書換え言語の

設計と効率的な実装手法

提出日 : 2016 ^年 1 ^月 23 ^日指導 : 上田和紀教授

早稲田大学基幹理工学部情報理工・情報通信専攻

学籍番号 : 5114F070-7

奈良耕太

(2)

概要

奈良耕太パターンマッチングはデータ構造からそのある一部分を取り出す処理を簡潔に表現するための構文であり、特に関数型言語や論理型言語において言語機能の一つとして広く取り入れられている。データの取り出しはデータ構造に対して行われるもっとも基本的な操作の一つであり、頻出するものであるから、これを簡潔に記述することのできる言語機能は有用である。

しかし標準的なパターンマッチングの実装では、対象とするデータ構造の根にある特定のコンストラクタからその適当な子孫を取り出す、あるいはその有限回の繰り返ししかパターンとして記述することができず、“データ構造から条件にマッチする一部分を取り出す” という一般的な目的に対して必ずしも十分な表現力があるとは言えない。

本研究では、 “文脈” の概念をパターンマッチングに応用する Context Patterns、およびパターンを (再帰的に) 組み合わせてゆくことでより複雑なパターンを表現する

Pattern Functions の２つのアイデアに注目し、これらを実用的な実行効率で、かつより

一般的なグラフを対象に、両立させるグラフ書換え言語CSLMNtalを設計した。

これらのアイデアの両立によって、コンストラクタの有限回の繰り返しのみならず、再帰的なパターンに基づいて特定の条件を満たす要素をデータ構造から探索するような処理をも簡潔に記述することができ、かつマッチングの結果得られたデータと、データ構造全体からそのデータを除いた残り部分 (文脈) とがともに第一級のオブジェクトとして操作可能であるような、非常に強力なパターンマッチング機能を実現できることが期待される。

また CSLMNtalの処理系のうち、その核となるパターンマッチングやグラフの書換え

処理を行う部分については実装・評価も行った。ここで用いられている効率化の手法それ自体はグラフ書換え言語に限らず、一般的な関数型言語などのパターンマッチングにも応用できる可能性のあるものである。

(3)

Kota Nara Pattern matching provides us with concise syntax for expressing extraction of cer- tain elements in a data structure, which is widely used especially in functional and logic languages. A concise way of expressing data extraction is valuable, since it is one of the most fundamental operations on data structures.

However, most implementations of pattern matching only oﬀer syntax for extracting some argument from the principal constructor of a data structure or its ﬁnite repeti- tion, and is not expressive enough to achieve the general goal of extracting necessary data from a data structure.

In this research, I designed a graph rewriting language CSLMNtal, which combines two ideas on pattern matching: (1) Context Patterns which utilize the notion of

“Context” to pattern matching, and (2) Pattern Functions which allows us to build a copmlex pattern by (recursively) combining smaller patterns, with practical eﬃciency, on general graph structures.

By combining these ideas, we realized very powerful pattern matching which offers not only finite repetitions of constructors but the searching of elements that satisfy a condition given in terms of recursive patterns, and both the data extracted with pattern matching and the rest of the data structure (context) are obtained as first class citizens.

I also designed, implemented and assessed the algorithm of the pattern matching and graph rewriting, which is the core of the CSLMNtal implementation. Optimiza- tion techniques used in the implementation are not only speciﬁc to graph rewriting languages but expected to be utilized in other paradigms such as functional languages.

(4)

iii

図目次

2.1 Egison のパターンの構文 . . . 5

3.1 LMNtal プロセスの構文 . . . 8

3.2 LMNtal プロセスの構造同値 . . . 8

3.3 LMNtal の操作的意味論 . . . 10

3.4 LMNtal の拡張構文：プロセス文脈 . . . 11

3.5 LMNtal の拡張構文：ガード部を持つルール . . . 12

4.1 型宣言の構文 . . . 15

4.2 差分リストの例 . . . 16

4.3 CSLMNtalの構文：ガード部を持つルール . . . 18

4.4 CSLMNtalの拡張構文：代入構文 . . . 21

4.5 CSLMNtalの拡張構文：複数のガード部を持つルール . . . 22

5.1 継続を持つラムダ計算の構文 . . . 28

5.2 継続を持つラムダ計算の意味論 . . . 28

6.1 単純な連結パターンのマッチングアルゴリズム . . . 39

6.2 型検査の素朴なアルゴリズム . . . 40

6.3 リストの要素数とソートの所要時間の関係 . . . 47

6.4 算術式の演算子数と評価の所要時間の関係 . . . 48

(7)

第 1 ^章

はじめに

1.1 研究の背景と目的

パターンマッチングはデータ構造からそのある一部分を取り出す処理を簡潔に表現するための技術であり、特に関数型言語や論理型言語において言語機能の一つとして広く取り入れられている。データの取り出しはデータ構造に対して行われるもっとも基本的な操作の一つであり、頻出するものであるから、これを簡潔に記述することのできる言語機能は有用である。

しかし標準的なパターンマッチングの実装では、対象とするデータ構造の根にあたる特定のコンストラクタからその適当な子孫を取り出す、あるいはその有限回の繰り返ししかパターンとして記述することができず、“データ構造から条件にマッチするデータを取り出す” という一般的な目的に対して必ずしも十分な表現力があるとは言えない。

グラフ書換え系は、項書換え系のより一般的な形であり、グラフの全体または部分を与えられた規則に従って別のグラフに置き換えてゆくことによって計算が進行してゆく系である。書換え系は宣言型言語のモデルとして用いられることがあり、中でもグラフ書換え系をモデルとする言語に、 LMNtal [1] がある。グラフ構造は計算システムから社会組織に至るまで、さまざまな場面で見られるものであるから、グラフに対する処理を簡潔に記述することのできる言語は有用である。

本研究では、 “文脈” の概念をパターンマッチングに応用する Context Patterns [2]、およびパターンを (再帰的に) 組み合わせてゆくことでより複雑なパターンを表現する

Pattern Functions [3]の２つのアイデアに注目し、これらを実用的な実行効率で、かつよ

り一般的なグラフを対象に、両立させる宣言型言語 CSLMNtalをLMNtal の拡張として設計した。

(8)

第1章はじめに 2 これらのアイデアの両立によって、コンストラクタの有限回の繰り返しのみならず、再帰的なパターンに基づいて特定の条件を満たす要素をデータ構造から探索するような処理をも簡潔に記述することができ、かつマッチングの結果得られたデータと、データ構造全体からそのデータを除いた残り部分 (文脈) とがともに第一級のオブジェクトとして操作可能であるような、非常に強力なパターンマッチング機能を実現できることが期待される。

また設計した言語の処理系のうち、その核となるパターンマッチングやグラフの書換え処理を行う部分については実装・評価も行った。ここで用いられている効率化の手法それ自体はグラフ書換え系に限らず、一般的な関数型言語などのパターンマッチングにも応用できる可能性のあるものである。

本論文の以下の章では CSLMNtalの仕様と、パターンマッチングおよびグラフの書換え処理の実装手法を紹介する。またいくつかの例題について、従来のパターンマッチングとの表現力の比較や、性能の評価を行う。

1.2 ^{本論文の構成}

第 2 章では、本研究に先行する２つの関連研究を紹介する。第 3 章では、本研究で設計・実装する言語のベースとなった LMNtal 言語について簡単に解説する。第 4章では、

実際に本研究で設計した言語 CSLMNtalの設計 (構文・意味論) を示す。第 5 章では、

CSLMNtalのパターンマッチング機能を用いて簡潔に記述することのできるプログラム

の例をいくつか紹介する。第6 章では、 CSLMNtalの処理系のうち核となる、パターンマッチングおよびグラフの書換え処理の効率的な実装手法を提案する。またその性能評価を行う。

(9)

第 2 ^章

パターンマッチングの先行研究

本章では、本研究に先行する２つのパターンマッチングのアイデア、Context Patterns および Pattern Functionsを簡単に紹介する。

2.1 Context Patterns

Context Pattern は Mohnen によって Haskell [4] の拡張として提案されたパターンマッチングの構文である。この拡張の背景には、プログラミング言語の操作的意味論の記述のために Felleisen とHieb によって提案された評価文脈 (Reduction Context) [5] の概念がある。

プログラムの実行を式の簡約の連続とみなすとき、ある簡約における評価文脈とは、直感的には、式全体からその簡約によって変化する部分 (簡約器) を除いた残りのことを言う。たとえば以下の算術式において、

1 + 2 + 3

left-to-rightの評価戦略で次に簡約される部分 (簡約器) は 1 + 2

であり、その文脈は

[] + 3

である。ここで、[]は構文木の欠けを表現するための特別な終端記号であり、穴(Hole) と呼ばれる。

(10)

第2章パターンマッチングの先行研究 4 この概念を借りて、与えられたデータ構造を注目する特定の一部分と、その残り部分 (文脈) とに分解するための構文を提供するのが Context Pattern である。例として、与えられたリストをその末尾の要素と、末尾以外の要素のリストとのペアに分解する関数 initLast の、 Context Pattern を用いた実装を文献 [2] より引用する：

initLast :: [a] -> ([a], a) initLast (c [x]) = ((c []), x)

パターン (c [x]) は、引数に与えられたリストを１要素のリスト[x] とその文脈 c とに分解することを表す。ここで、文脈c はリスト全体からその末尾のコンスセルを取り除いた、不完全なリストとなる。これ自体はHaskell の適切な対象ではないが、代わりに与えられた引数で文脈の穴を埋めて返すような１引数関数に、パターン変数c が束縛される。したがってc ^{に空リスト}[] を適用すれば、元のリストの末尾 [x] ^{を空リスト} []

で置換して得られるオブジェクト、すなわち元のリストから末尾の要素を除いたリストが得られる。

同じ関数を Context Pattern を用いず、再帰呼出しによって表現すると次のようになるだろう：

initLast :: [a] -> ([a], a) initLast [x] = x

initLast (x:xs) = (x:ys, l) where (ys, l) = initLast xs

Context Pattern を用いた場合と比較すると、末尾の要素を探索する処理や、末尾の要素

を除いたリストを構成する処理を明示的に記述しなければならない点で、より抽象度の低い表現になっている。このように、 Context Pattern にはデータ構造に対する素朴な探索処理、および探索の結果得られたデータの文脈に対する操作を抽象化する機能がある。

2.2 Pattern Functions

Pattern Function は江木によってプログラミング言語 Egison の一機能として設計・

実装された、パターンを組み合わせることでより複雑なパターンを構成するための仕組み

である。 Egison の最大の特徴は標準形を持たないデータ(集合など) に対するパターン

(11)

⟨pattern⟩ ::= _ (wildcard)

| $⟨ident⟩ (pattern-variable)

| ,⟨expr⟩ (value-pattern)

| <⟨ident⟩ ⟨pattern⟩^∗> (inductive-pattern)

| (⟨pat-func⟩ ⟨pattern⟩^∗) (pattern-application)

| (|⟨pattern⟩^∗) (or-pattern)

| (&⟨pattern⟩^∗) (and-pattern)

| ^⟨pattern⟩ (not-pattern)

| [⟨pattern⟩] (tuple-pattern)

⟨pat-func⟩::=(pattern-function [⟨pat-var⟩^∗]⟨pattern’⟩)

⟨pattern’⟩ ::= ⟨ident⟩ (variable-pattern)

| _ (wildcard)

| $⟨ident⟩ (pattern-variable)

| ,⟨expr⟩ (value-pattern)

| <⟨ident⟩ ⟨pattern’⟩^∗> (inductive-pattern)

| (⟨pat-func⟩ ⟨pattern’⟩^∗) (pattern-application)

| (|⟨pattern’⟩^∗) (or-pattern)

| (&⟨pattern’⟩^∗) (and-pattern)

| ^⟨pattern’⟩ (not-pattern)

| [⟨pattern’⟩] (tuple-pattern)

図2.1 Egison のパターンの構文

マッチングであるが、本論文とは直接関係がないためここでは Pattern Function に絞って解説する。

Egison のパターンの構文を文献 [3] より図 2.1 に引用する。一般的なパターンマッ

チングと同様にワイルドカード (wildcard)、パターン変数 (pattern-variable)、パターンとしての具体値 (value-pattern)、コンストラクタやタプルに対する帰納的なパターン

*1 (inductive-pattern, tuple-pattern) を用いることができるほか、パターンの積・和・

否定(or-pattern, and-pattern, not-pattern) やPattern Function の呼び出し(pattern-

application)などの高階のパターンを用いることができる。

*1この表現は厳密でない。標準形を持たないデータに対するパターンマッチをサポートするため、ここでのコンストラクタとはデータ構造のコンストラクタではなくPattern Constructorと呼ばれる独自の独自の概念を指し、その点で一般的なパターンマッチングとは異なる。ただし、標準形を持つデータに対するパターンマッチングだけを考える場合、これはデータ構造のコンストラクタに相当するものである。

(12)

第2章パターンマッチングの先行研究 6

Pattern Function はパターンに似ているが、引数を取りその引数をパターン内で参照

できる点で通常のパターンと異なる。 Pattern Function 内でもPattern Function の呼び出しが認められていることから、Pattern Function を再帰的に組み合わせることで通常の構文では無限の長さになるようなパターンをも有限の長さで表現することが可能である。

Pattern Function を用いて表現された複雑なパターンの例を挙げる：

(define pf

(pattern-function [p]

(| <cons ,0 (pf p)> <cons (& (^ ,0) p) _>)))

Pattern Function pf はパターン p を引数に取り、リストに含まれる 0 でない最初の要

素とパターン p とをマッチするパターンを返す (car 部が 0 ^であれば cdr 部とパターン (pf p) とのマッチを試み、さもなければ car部が 0 であることを確認したうえでパターン p とマッチを試みる)。これを用いて、たとえば受け取ったリストから 0 でない最初の要素をパターン変数 $x ^{に取り出すパターンを} (pf $x) と書くことができる。これと等価なパターンを Pattern Function を用いずに表現しようとすれば無限の長さになるだろう。

(13)

第 3 ^章

LMNtal

CSLMNtalは言語モデルLMNtal [1] (のサブセットFlatLMNtal: 以下たんにLMNtal と書く) を拡張する形で設計したため、本章でLMNtal の構文および意味論を簡単に解説する。本章は概ね文献[1] の内容に基づいているが、本研究と直接関係のない階層化機能の解説は省いた。

3.1 ^概要

LMNtal (エレメンタル)はグラフ書換え系をモデルとする宣言型言語で、そのプログラ

ムはグラフと、グラフ (の一部) を書き換える規則の集まりとして表現される。LMNtal の対象は一般的なグラフ理論で扱うグラフとはやや性質が異なり、プロセス (process) と呼ばれる。

プロセスの構文を図 3.1 に、プロセスの同値関係 (≡) を図 3.2 に示す。ここで

⟨LinkName⟩ は大文字アルファベットから始まる識別子、 ⟨AtomName⟩ ^{はそれ以外} の識別子または“’” で囲まれた文字列である。分子を構成する “,” はルールを構成する

“ :- ” よりも強い結合力を持つ。可読性のために、名前が演算子であるようなアトムを X = Y のように表す。これは’=’(X, Y)と等価である。

3.2 ^{アトムとリンク}

アトム (atom) はプロセスを構成するもっとも基本的なオブジェクトで、一般的なグラ

フでいうノードに相当するものである。アトムは名前といくつかの順序づけられた引数を持つ。アトムの引数の数をそのアトムの価数 (arity) と呼ぶ。アトムのそれぞれの引数

(14)

第3章 LMNtal 8

X ::= ⟨LinkName⟩ p ::= ⟨AtomName⟩

P ::= ϵ (空)

| p(X₁, . . . , X_n) (n≥0) (アトム)

| P, P (分子)

| P :- P (ルール)

図3.1 LMNtal プロセスの構文

1. ϵ, P ≡ P

2. P1, P2 ≡ P2, P1

3. P₁,(P₂, P₃) ≡ (P₁, P₂), P₃

4. X =X ≡ ϵ

5. X₁ =X₂ ≡ X₂ =X₁

6. P ≡ P[X1 ←X2]

(X₁ は P の局所リンク) 7. X1 =X2, P ≡ P[X1 ←X2]

(X₁ はアトム P の自由リンク) 8. P1 ≡P1 ⇒ P1, P2 ≡P₁^′, P2

図3.2 LMNtal プロセスの構造同値

にはリンク名 (link name) を書くことができ、同じリンク名の対によって、一般的なグ

ラフの無向エッヂに相当するリンク (link) を表現する。たとえば、アトムa とb、b と c とをそれぞれリンクで接続したプロセスを次のように表現できる：

a(X), b(X, Y), c(Y)

リンクは３つ以上のアトムを連結することはできない (リンク条件)。したがって、あるプロセスに同じリンク名はたかだか２回しか出現しない。あるプロセスの中でちょうど２回リンク名が出現するリンクを特にそのプロセスの局所リンク (local link)、１回出現するリンクを自由リンク (free link) と呼ぶ。たとえば a(X), b(X, Y), c(Y) の部分プロセス a(X), b(X,Y)^{において、} X ^{は局所リンクであり} Y ^{は自由リンクである。}

同値関係の規則 6. によれば、 LMNtal プロセスにとって局所リンク名は本質的でない。たとえば、プロセスa(X), b(X, Y), c(Y) に含まれる２箇所の X の出現を Z で置

(15)

き換えて得られるプロセスa(Z), b(Z, Y), c(Y) は、元のプロセスと同値である(α変換)。一方、引数には順序が付いており、たとえばアトムb の２つの引数を交換して得られるプロセス a(X), b(Y, X), c(Y) は元のプロセスと同値でない。

リンク条件によって、局所リンクを持つプロセス P1 と、その局所リンクと同じリンク名を１つ以上持つプロセス P₂ に対してプロセス P₁, P₂ やP₂, P₁ は定義されない。便宜のために、本論文ではこのようなプロセスの組に対してもプロセス P₁, P₂ および P₂, P₁ を次のように定義する：P1 に出現する局所リンクを P2 に出現しない適当なリンク名で置き換えて得られるプロセス P₁^′ を一つ決めて、P1, P2

def= P₁^′, P2 また P2, P1

def= P2, P₁^′。

LMNtal で唯一予約されているアトムは２価の ’=’ であり、その意味は同値関係の規

則 4.、5. および 7. に表現されている。直感的には、２価の ’=’ アトムはその２つの引数を直接リンクで接続することを表す。たとえば a(X), b(Y), X = Y は a(X), b(X) と同値である。

3.3 ^ルール

ルールの操作的意味論 (→) を図 3.3 に示す。ルールは２つのプロセスを “:-” で結んだものであり、直感的には “左辺にマッチするプロセスを右辺のプロセスに書き換えてよい” という規則を表す。たとえば、プロセス p(A, A), (p(X, Y) :- q(X, Y))は次のように書き換えられる。

p(A, A), (p(X, Y) :- q(X, Y))

≡ p(X, X), (p(X, Y) :- q(X, Y))

≡ p(X, Y), Y = X, (p(X, Y) :- q(X, Y))

→ q(X, Y), Y = X, (p(X, Y) :- q(X, Y))

≡ q(X, X), (p(X, Y) :- q(X, Y))

リンク条件から、ルール中に出現するリンク名は必ず以下の３通りに分類でき、ルールが自由リンクを持つことはない。

1. 左辺に２度出現 …… リンクの削除 2. 右辺に２度出現 …… リンクの生成

3. 両辺に１度づつ出現 …… リンクの接続先の変更

3.4 ^別記法

可読性のため、また記述性のために、LMNtal は次の別記法を認めている。

(16)

第3章 LMNtal 10

P1,(P1 :-P2)→P2,(P1 :- P2) (P₁ は２価の ’=’ アトムを持たない)

P₁ →P₁^′ P1, P2 →P₁^′, P2

P1 →P₁^′ P1 ≡P2 P₁^′ ≡P₂^′ P₂ →P₂^′

図3.3 LMNtal の操作的意味論

3.4.1 ^{ピリオドの使用}

“:-” よりも結合力の弱い“,” として“.” を用いることができる。これによって、ルールとアトムとの分子を作成する際にルールを括弧で囲む必要がなくなる。

3.4.2 ^{引数リストの別記法}

アトムの引数リストに対して、次の３つの別記法を適用することができる。

1. 引数のないアトムa() ^をたんに a ^{と表記する}

2. アトムa(X, Y) の最終引数を外に出して Y = a(X) と表記する

3. ’=’ アトムを含むプロセス a(X, Y), Y = bをたんに a(X, b) と表記するたとえば、次の４つの表記はすべて等価である。

• a(X,Y), b(X), c(Z,Y)

• a(X,Y), X = b, Y = c(Z)

• a(b,c(Z))

• c(Z) = a(b)

3.4.3 ^{リストの略記法}

LMNtal では慣習的に、リストをcons^{を表す３価の}’.’ アトムと、空リストを表す１

価の ’[]’アトムの組み合わせによって表現する。この方法でリストを書く場合、Prolog

(17)

P := $p[X1, . . . , Xn] (n >0)

図3.4 LMNtal の拡張構文：プロセス文脈

流のリスト記法を用いることができる。

例えば X = [a, b] ^はリスト ’.’(a, ’.’(b, ’[]’), X) ^{を表し、また} X = [a, b

| X]は循環リスト ’.’(a, ’.’(b, X), X) を表す。

3.5 ^{プロセス文脈}

実用上、LMNtalの処理系 [6] は主に算術演算や不特定多数のアトムの一括複製・削除

のために、形式的定義にある構文・意味論に加えてプロセス文脈 (process context) と呼ばれる拡張構文を持つ。プロセス文脈の構文を図 3.4に示す。プロセス文脈の引数リストに対しても、アトムと同様の別記法を用いることができる。

プロセス文脈はアトムに似ているが、ルール中にしか書くことができない。ルール左辺に書かれたあるプロセス文脈 $p[X1, . . . , Xn] は、単一のアトムの代わりに、X1, . . . , Xn

を自由リンクに持つ (それ以外の自由リンクは持たない) ０個以上のアトムから構成されたプロセス全体を代表する。このときX₁, . . . , X_n は互いに異なるリンク名でなければならない。

それぞれのプロセス文脈には、そのプロセス文脈がマッチするプロセスの範囲を定めるガード条件 (guard condition) をルールのガード部 (guard) で指定する。ガード部を持つルールの形式的な構文を3.5に示す。ガード部はルールの“:-”と “|” の間をいい、ここに任意個のガード条件を書くことができる。ガード条件はあらかじめ処理系で定義された型制約か、２つの算術式を比較演算で結んだもののいづれかである。

ルール左辺に書かれたプロセス文脈は、同じ価数・名前のプロセス文脈を右辺にも書くことができ、右辺に書かれたそれらは書換えの際に左辺でマッチしたプロセスで置き換えられる。またルール左辺には出現せず、ガード条件p^∗ = e で初めて出現したプロセス文脈名 p^∗ は、１価で同じ名前のプロセス文脈を右辺にも書くことができ、書換えの際に右辺の算術式 e を評価した結果の数値を名前に持つアトムで置き換えられる。それ以外のプロセス文脈をルール右辺に書くことはできない。

たとえばプロセス文脈を含む次のルール：

(18)

第3章 LMNtal 12

u := ⟨UnaryOp⟩ b := ⟨BinaryOp⟩ r := ⟨RelOp⟩

t := ⟨TypeName⟩

e := u e|e b e |$p| ⟨Constant⟩ (算術式)

c := t($p)|e r e (ガード条件)

P := P :- c1, . . . , cn|P (n≥0) (ガード部を持つルール)

図3.5 LMNtal の拡張構文：ガード部を持つルール

x(X), $x[X] :- int($x), $y = $x + 1 | y(Y), $y[Y]

は、１価の x アトムとこれに接続された整数アトム (名前を整数として解釈できるアトム) にマッチし、 x アトムを y アトムで置き換え、また整数アトムを１だけインクリメントする。形式的意味論の立場からは、このルールは、次の無数のルールからなる分子

..., (x(X), -1(X) :- y(Y), 0(Y)), (x(X), 0(X) :- y(Y), 1(Y)), (x(X), 1(X) :- y(Y), 2(Y)), ...

と等価であると説明される。

ガード部は次の構文規則を満たさなければならない：

1. ルール左辺に出現するすべてのプロセス文脈名はガード部でそれぞれ１回以上出現する

2. ルール左辺に出現しないプロセス文脈名 p^∗ の出現するガード条件はp^∗ = e の形をしていなければならない

ガード部で用いることのできる型名、比較演算子、算術演算子は以下のとおりである：

• ^型名

– ground …… 強連結な任意のプロセス – unary …… １価の単一のアトム

– int …… 整数アトム (名前が整数であるようなアトム)

– float …… 浮動小数点数アトム (名前が小数であるようなアトム) – uniq…… 同じプロセス文脈に対して１度だけ成功する

(19)

• ^{比較演算子}

– =, \= …… ２つの ground の比較

– =:=, =\=, <, <=, >=, > ^{…… ２つの} int ^の比較

– =:=., =\=., <., <=., >=., >. …… ２つの float の比較

• ^{算術単項演算子 ……} +, -

• ^{算術２項演算子 ……} +, -, *, /, mod

(20)

14

第 4 ^章

提案言語の設計

本章では、提案言語 CSLMNtalの設計 (構文・意味論) について述べる。

4.1 ^設計方針

本研究で設計する言語は、Pattern Functionsのように(再帰的で)複雑なパターンマッチングをより一般的なグラフに対しても行うことができ、かつContext Patterns のようにパターンマッチングの結果得られたデータだけでなくその文脈もまた第一級のオブジェクトとして操作可能であるような言語である。

そのような言語の実現のために、第 3 章で解説した言語モデル LMNtal の構文・意味論に、組込みの型だけでなく Pattern Function によって定義されるような複雑なパターン (で定義された型) にもマッチできるような拡張されたプロセス文脈機能を導入する。

LMNtal の対象はもとよりグラフであり、またプロセス文脈はアトムのように自由に複

製・削除・移動することができる第一級のオブジェクトである。

4.2 ^{型定義の構文と意味}

本論文の以下の部分では、X₁, . . . , X_n (n≥0) のような自由リンク名の列を単一の飾り文字で X などと表現することがある。

ある t 型のプロセス文脈$p[X]がプロセス P にマッチすることを P ∈t(X) と定義すれば、プロセス文脈の型は自由リンク名の列をパラメタに持つプロセスの (無限) 集合であるとみなせるから、プロセス文脈の型をユーザーが定義するためには、そのような集合のテキスト表現があればよい。CSLMNtalにおいてプロセス文脈の型を定義するための

(21)

TypeRule ::= P :- t1(X1), . . . , tn(Xn). (n≥0)

TypeDef ::= typedeft(X){TypeRule₁ . . . TypeRule_n} (n≥0)

図4.1 型宣言の構文

構文を図 4.1に示す。ただし、可読性のため右辺が空であるような TypeRule の“:-” は省略することがある。また TypeRule が１つしかない TypeDef の波括弧も省略することがある。

簡単な型定義の例を挙げる：

typedef abc(X) { a(X). b(X). c(X). }

この定義は、直感的には次の主張を表す：abc(X) は、３つのプロセスa(X);b(X);c(X) からなる３要素の集合である。あるいは次のようにも表現できる：リンクX(だけ)を自由リンクとするプロセス P が型 abc のプロセス文脈にマッチするとは、P がa(X); b(X);

c(X)のいづれかであるということである。

集合の要素を具体的にすべて列挙するだけでなく、“:-” を用いることで集合を(相互) 再帰的に定義することもできる。これを用いて、たとえば差分リスト [7] (とみなせるプロセス) の集合を定義すると次のようになる。ただし差分リストとは空リストで終端されていない線形リストのことをいう (図 4.2)。

typedef dlist(T, H) { H = T.

H = ’.’(A, B) :- atom(A), dlist(T, B).

}

この宣言は、直感的には次の主張を表す：２つのリンクH^、T(だけ)を自由リンクとするプロセスP が型 dlist を持つプロセス文脈にマッチするとは、P が H = T であるか、あるいは集合atom(A)の元P1 とdlist(T, B)の元P2 があって H = ’.’(A, B), P1, P2

であるということである。ただし atom は後述する単一のアトムを表す組込みの型である。たとえば次のプロセスはdlist(T, H) の元である：

H = ’.’(1, ’.’(2, ’.’(3, ’.’(4, ’.’(5, T)))))

(22)

第4章提案言語の設計 16

図4.2 差分リストの例

型定義 TypeDef は次の構文規則を満たさなければならない：

1. 型定義の仮引数に含まれるリンク名は互いに異なる

2. どの TypeRule も、 t(X) を左辺に書き加えるとルールにならなければならない 3. 左辺のあらゆる空でない部分プロセスは少なくとも一つの自由リンクを持たなけれ

ばならない

規則 2. はリンク条件を破るようなプロセスを排除する。3. は次のようなプロセス P を排除する：P に含まれるあるアトムが、P のどの自由リンクからも到達することができない。このようなプロセスを排除すると、自由リンクの列 X ^{が決まれば} X ^{を引数とす} るプロセス文脈の指すプロセスも(存在すれば) 一意に決まることになり、好都合である。

4. は再帰的に型検査の対象となる２つのプロセスが互いに直接接続されているようなプロセスを排除する。3. の構文規則は取り除いても構文・意味論自体に曖昧さや矛盾を生じるものではなく、処理系の効率化や拡張を見込んで設けられたものである。これに加えて本研究の実装には次の制約がある：

• TypeRule 右辺に出現するリンク名は、同じリンク名が左辺か型定義の仮引数に含

まれていなければならない

これは技術的な理由によるもので、将来的には取り除かれることが期待される。

形式的には、TypeRule とグラフ集合との対応付け S を次のように定義できる。

P :- t1(X1), . . . , tn(Xn) 7→S {P, P₁, . . . , P_n |P_k ∈t_k(Xk)} この S のもとで、宣言

typedeft(X){TypeRule₁ . . . TypeRule_n} は集合 t(X) を

S(TypeRule₁)∪ · · · ∪S(TypeRule_n)

(23)

と定義するものと決める。S と t(X) の定義が相互再帰的であるが、それぞれ集合の包含関係にかんして最小の解を取るものとする。

またatomを含むいくつかの型名に対して、その組み込みの定義を以下のように与える：

• linked(X₁, X₂)

単一のプロセス X1 = X2 のみからなる集合。

• int(X)

X をただ一つの引数とし、名前が整数であるようなアトムの集合。以下、P ∈ int(X) に対して、⌈P⌉ でその名前の表す整数を指すことにする。

• ’<’(X1, X2)

分子 P₁, P₂ であって、P₁ ∈ int(X₁), P₂ ∈ int(X₂),⌈P₁⌉ <⌈P₂⌉ ^{であるような} ものの集合。’<=’(X1, X2),’>’(X1, X2),’>=’(X1, X2),’=’(X1, X2)も同様に定義する。

• atom(X)

引数リストが X となっているような n 価のアトムの集合。X1 = X2 ∈ atom(X1, X2) ではあるが、操作的意味論 (→) の付帯条件により２価の = アトムを含むプロセスはどんなルールにもマッチしない。

• ’==’(X1,X2)

同じアトム名p を持つ２つのアトムの分子p(X1), p(X2) の集合。

• ground(X)

X (だけ) を自由リンクに持ち、含まれるどのアトムにもいづれかの自由リンクかから到達することのできるようなプロセスの集合。

• connected(X)

X (だけ) を自由リンクに持ち、含まれるどのアトムにもすべての自由リンクかから到達することのできるようなプロセスの集合。

• ’===’(X1,X2)

分子 P₁, P₂ であって、P₁ ∈ ground(X1), P₂ ∈ ground(X2), P₁ ≡P₂ であるようなものの集合。

4.3 プロセス文脈の構文と意味

文献 [6] の処理系と同様に、CSLMNtalでもプロセス文脈を含むルールが認められる。

プロセス文脈の構文は第 3 章と同様である。

(24)

t := ⟨TypeName⟩ c := t($p)

P := P|c1, . . . , cn :- P (n≥0)

図4.3 CSLMNtalの構文：ガード部を持つルール

プロセス文脈を含むルールの構文を 4.3に示す。従来の処理系の実装していた構文と比較すると、ガード部を表す“|” がルールの右辺・左辺を結合する “:-” と入れ替わっている点、数値比較の構文が削除され型制約に統一されている点が異なる。従来の処理系と同様に、左辺に書かれていないプロセス文脈名を右辺で用いることはできない。また、それぞれのプロセス文脈に対してちょうど１つの型を記述しなければならない。

ガード条件を含むルールの例を挙げる：

dlist?($x[T], T) | dlist($x) :- yes.

このルールは直感的には次のような書換えを表す： dlist? アトムに２本のリンクで接続された部分プロセスが型 dlist を持つならば、それら全体を単一の yes ^{アトムに書き} 換える。たとえば次のプロセス：

dlist?(X,X), dlist?(a,a), dlist?([1, 2 | Y],Y)

と上のルールとを並べておくと、次のように書き換えられてゆく (ルールは省略した)。

dlist?(X,X), dlist?(a,a), dlist?([1, 2 | Y],Y) --> dlist?(X,X), dlist?(a,a), yes

--> yes, dlist?(a,a), yes

a(H), a(T) ^はdlist(T,H)の元ではないから、これ以上は適用できるルールはなく、ここで実行が停止する。

形式的には任意のルール r から、ガード部を持たないルールのみからなるr と等価なプロセスを機械的に構成することができる：

1. 空のガードを持つルール P₁| :- P₂ はルール P₁ :- P₂ と等価

(25)

2. ルールP1|t($p), . . . :-P2 はルールの集合 {

P₁⟨$p[X]←P⟩| . . . :- P₂⟨$p[Y]←P,X=Y⟩P ∈t(X) }

の元をすべて “,” で結合した分子と等価。ただし、P₁⟨P₂ ←P₃⟩ ^は P₁ の部分プロセスP2 にP3 を、リンク条件を満たすよう局所リンクを改名して代入したもの。

またX=Y ^は X ^の k 番目のリンクと Y ^のk 番目のリンク (k = 1,2, . . .) をそれぞれ’=’ アトムで接続したプロセス。

これは、プロセス文脈を含むルールを無数のルールからなる分子とみなす立場をより形式的に表現したものになっている。

たとえば、次の型定義：

typedef ab(X) { a(X). b(X). } typedef cd(X) { c(X). c(X). } のもとで、ルール

foo($x,$y) | ab($x), cd($y) :- . は２つのルールからなるプロセス

foo(a,$y) | cd($y) :- . foo(b,$y) | cd($y) :- .

と等価であり、またこれは４つのガード部を持たないルールからなるプロセス foo(a,c) :- . foo(a,d) :- .

foo(b,c) :- . foo(b,d) :- . と等価である。

4.4 ^別記法

可読性のため、また記述性のために、CSLMNtalは LMNtal の認める別記法に加え次の別記法を認める。

(26)

4.4.1 ガード部の左辺への統合

t ^{型のプロセス文脈} $x ^{を持つルール} P₁, $x | t($x) :- ... ^{を、ガード条件を左} 辺にまとめて P1, $x:t :- ... と記述することができる。

4.5 ^拡張構文

実用上、 CSLMNtalの処理系は形式的意味論には含まれていなかったいくつかの拡張

構文を持つ。これら (と等価あるいはそれ以上の機能) の仕様を十分に検討し、意味論の簡潔さを保ちつつ言語仕様に含めることは将来課題とする。

4.5.1 分子に対するプロセス型

実用上、複数のプロセス文脈の分子全体に対して型検査を行いたいことがある。たとえば次のようなルール：

a(X), b(Y), $x[X, Y] | ’===’($x) :- ...

の右辺で、X からつながっていた構造と Y からつながっていた構造とをそれぞれ独立に操作したいというのは自然な要求である。このために、複数のプロセス文脈の分子全体に対して型制約を記述することを認める。

分子に対するプロセス型によって、上のルールは次のように書くことができる：

a($x), b($y) | ’===’($x, $y) :- ...

あるいは演算子アトムのための略記法を型制約に援用して次のように書くこともできる：

a($x), b($y) | $x === $y :- ...

このルールのマッチするプロセスは上のプロセスと同じだが、右辺で$x と $y とをそれぞれ独立して操作することができる。

4.5.2 ガード部でのプロセス文脈生成

算術演算等を含むような書換えを簡潔に記述するために、代入 (<-) 構文 (図 4.4) によって新しいプロセス文脈を生成するようなガード条件を認める。代入の左辺にはルール

(27)

f := ⟨FuncName⟩

e := f(e₁, . . . , e_n)|$p|p(n≥0) c := $p <- e

図4.4 CSLMNtalの拡張構文：代入構文

左辺に出現していない単一のプロセス文脈名を、右辺には具体的なアトム名p・既出のプロセス文脈名 $p およびメタ関数 f の呼び出しからなる式を書くことができる。

ガード部でのプロセス文脈生成によって、たとえば次のようなルールを書くことができる。

X = add($a, $b) | $c <- ’+’($a, $b) :- X = $c.

あるいは演算子アトムの略記法を援用して次のように書くこともできる：

X = add($a, $b) | $c <- $a + $b :- X = $c.

このルールは３価の add アトムと、これに接続された２つのint ^{なプロセス} $a, $b ^にマッチし、それら全体を $a, $b の和に書き換える。

組込みのメタ関数には次のものがある：

• ^{０引数関数 ……} gensym

• ^{１引数関数 ……} +, -

• ^{２引数関数 ……} +, -, *, /, mod

メタ関数のユーザー定義のための構文は検討中である。

4.6 ^{型検査の省略・重複}

上で述べたように、あるプロセス文脈の引数リストが決まればそのプロセス文脈の表すプロセスは型に関わらず一意に決まる。したがって、同じプロセスに対して複数回の型検査を行う、あるいは一度も行わないことを認めてもルールに意味にあいまいさを生じることはない。

型定義でも同様に、ある左辺の自由リンク名が右辺で出現しない、あるいは２度以上出現するような TypeRule を認める。ただし以降の章で述べる最適化のために、型定義の仮

(28)

P :=P|c11,· · · , c1n1 :- P1· · · |cm1,· · · , cmnm :- Pm .

図4.5 CSLMNtalの拡張構文：複数のガード部を持つルール

引数に含まれる自由リンク名にはこれを認めない。

これを用いると、たとえば差分リスト型を次のように一般化できる：

typedef dlist(T, H) { H = T.

H = ’.’(A, B) :- dlist(T, B).

}

この定義によれば、 dlist ^の要素は atom でなくてもよく、また要素間に循環参照等があってもよい。これは２番目の TypeRule の右辺に ground(A)を補って得られる型定義とは異なることに注意する。

4.6.1 複数のガード部を持つルール

型が別の型に含まれるグラフにアトムを追加してゆくことで定義される都合上、

CSLMNtalには “atom 以外の ground” のような否定的なガード条件を書きづらいとい

う性質がある。

これを改善する一つの方法として、ガード部の個数を一般化し、一つのルールに複数のガード部を書くことを認める (図 4.5)。ルールに複数のガード部が書かれたとき、そのルールはすべてのガード部が失敗するときに限り失敗する。いづれかのガード部が成功する場合、そのうちもっとも上に書かれたものが書換えに採用される。

4.6.2 ユーザー定義の演算子

可読性のために、ユーザーはパーサーが中置・前置演算子として認識する文字列を以下のように定義することができる：

defop OP, ASSOCIATIVITY, PRIORITY(, ARITY).

(29)

ただし OP, ASSOCIATIVITY, PRIORITY, ARITY はそれぞれ、演算子として定義するアトム名・結合性・優先度・価数である。結合性はright,leftまたはprefix、優先度は整数で、同じ優先度に結合性の異なる中値演算子を定義することはできない。価数は prefix な演算子に対してのみ定義でき、その値は自然数である。

たとえば、プログラム中の次の行：

defop ->, right, 500.

以降の部分では、“X = ’->’(Y, Z)” を “X = Y -> Z” と略記できる。

デフォルトで定義されている演算子を表 4.1 に示す。

表4.1 CSLMNtalの拡張構文：ビルトインの演算子

優先度結合性演算子

1000 right ’=’

2000 right ’===’, ’==’, ’>=’, ’<=’, ’<’, ’>’

3000 left ’+’, ’-’

4000 left ’*’, ’/’, ’mod

9000 prefix ’-’

(30)

24

第 5 ^章

例題

本章では、 CSLMNtalのパターンマッチング機能を生かして書かれた例題を紹介し、

表現力を確認する。

5.1 ^{リストの交換ソート}

数のリストを昇順に交換ソートする処理を考えると、これは次の２つのステップの繰り返しとみなすことができる。

1. 交換の対象となる要素のペアを決める(なければ終了)

2. 交換する

このうち、対象となる要素のペアを決める処理は一種のリストに対する探索であり、(拡張された) パターンマッチングによって簡潔に記述できるべきものである。

CSLMNtalにおける、リストに対する交換ソートを行う手続き sort の実装を示す：

sort($d1:dlist[’.’($n, $d2:dlist[’.’($m, T)])

| $n > $m :- sort($d1[’.’($n, $d2[’.’($m, T)]).

dlist 型のプロセス文脈 $d1, $d2 は、交換の対象となる２つの要素 $x1, $x2 が同じリストの要素であることを保証する。これを用いて、リスト中から順序の反転している２つの要素のペアを探索するという処理を、その具体的なフローを記述することなしに表現できている。ここで２つの要素が隣接していなくてもよい点は注目に値する。

(31)

このルールとともにたとえばプロセス sort([1, 5, 3, 2, 3, 1, 5]) を置いておくと、次のように簡約されてゆく (ルールは省略した)。

sort([1, 5, 3, 2, 3, 1, 5])

→ sort([1, 3, 5, 2, 3, 1, 5])

→ sort([1, 1, 5, 2, 3, 3, 5])

→ sort([1, 1, 2, 5, 3, 3, 5])

→ sort([1, 1, 2, 3, 5, 3, 5])

→ sort([1, 1, 2, 3, 3, 5, 5])

上のプログラムと等価な交換ソートのプログラムをたとえば Scheme によって実装すると次のようになる：

(define (sort! lst)

(let ([x lst] [y (undefined)]) (while (pair? x)

(set! y (cdr x)) (while (pair? y)

(when (> (car x) (car y)) (let ([t (car x)]))

(set-car! x (car y)) (set-car! y t)) (set! y (cdr y))) (set! x (cdr x)))))

交換ソートは本質的にリストを２重にイテレートする必要があり、再帰による簡潔な表現は難しく、手続き的な実装にならざるを得ない。

同様のパターンマッチングは第 2 章で紹介したContext Patterns (文献 [2]) でも記述できるとされており、示されているコードも確かに sort の表現になっているように見える：

sort :: Ord [a] => [a] -> [a]

sort (c x y if y < x) = sort (c y x) sort zs = zs

(32)

第5章例題 26 しかし、論文に示された意味論 (Haskell コードへの変換による) ではリストを完全には整列できず、いくつかの反転対が残ったまま実行が停止する。

5.2 逐次処理の表現

一般に、書き換え系は非決定的なシステムの挙動を簡潔に記述できる一方、逐次的な処理の記述力は手続き型言語に劣る。

たとえば、整数定数と add からなる単純な算術式を、評価順序を考えずに評価する手続き eval の実装はほとんど自明である：

X = add($x, $y) | $z <- $x + $y :- X = $z.

たんに、適当な add アトムを探しその第１・第２引数の和でadd 自身を置き換えればよい。しかし、この評価器にたとえばleft-to-right の評価順序を導入する方法はさほど自明でない。

第 2 章で、操作的意味論の分野では文脈の概念が“評価文脈” として評価順序の表現のために用いられてきたことに触れた。本研究で設計したパターンマッチングの仕組みを用いると、この “評価文脈”をもパターンとして簡潔に表現することができる。これは、パターンマッチングが逐次的な処理の記述に活用できることを示唆するものである。

例の評価器に left-to-right の評価順序を導入するためには、まず評価文脈の取りうる形をプロセス文脈の型として表現し、

typedef context(Hole, Root) { Root = Hole.

Root = add(X, Y) :- int(X), context(Hole, Y).

Root = add(X, Y) :- context(Hole, X), ground(Y).

}

式のルート (eval) と評価基との間の構造 $c にこの制約を適用すればよい：

eval($c:context[add($x, $y)]) | $z <- $x + $y :- eval($c[$z]).

型context の主張は次のとおりである：

1. 評価対象の根にあるadd はただちに評価してよい

(33)

2. 評価対象の根が add アトムで、その第１引数がint ならば、その右部分木を評価してよい

3. さもなければ、左部分木を評価してよい

これは “add アトムの右部分木を評価するためには左部分木の評価が終わっていなければならない” ことを制約しており、確かにleft-to-right の評価順序の表現になっている。穴 ([]) のような特殊な終端記号を用意することなく、たんに２つの自由リンクを持つプロセスとして構文木の欠けを表現できている点は注目に値する

このルールとともにたとえばプロセス eval(add(add(1, add(2, 3)), add(add(4, 5), add(6, 7))))を置いておくと、次のように簡約されてゆく(ルールは省略した)。

eval(add(add(1, add(2, 3)), add(add(4, 5), add(6, 7))))

→ eval(add(add(1, 5), add(add(4, 5), add(6, 7))))

→ eval(add(6, add(add(4, 5), add(6, 7))))

→ eval(add(6, add(9, add(6, 7))))

→ eval(add(6, add(9, 13)))

→ eval(add(6, 22))

→ eval(28)

5.3 継続を持つ関数型言語のプロトタイピング

Scheme を始めとするいくつかの関数型言語は、継続と呼ばれる制御機能を持つ。これ

は大域脱出・コルーチンなどの複雑な制御機能を一般化した非常に強力なものであり、その簡潔な実装は自明でない。

CSLMNtalでは、プロセス文脈が第一級のオブジェクトである性質を用いることで、継

続を持つような関数型言語の意味論を極めて簡潔に記述することができる。例として文献 [11] で紹介されている、継続を導入したラムダ計算の意味論を CSLMNtalで実装する。

対象言語の構文を図 5.1 に、意味論を図5.2 にそれぞれ示す。この意味論において継

続の捕捉 call/ccは、その式の評価文脈C をオブジェクトとしてラップして返却する関

数として表現される。また継続の呼び出しは、呼び出された時点の評価文脈を呼び出された継続オブジェクトの保持する評価文脈で置き換えることで表現される。

対象言語の構文および評価文脈の定義は、たんにこれを CSLMNtalの構文規則にしたがって書き直すことで容易にCSLMNtalの型にエンコードすることができる：

(34)

第5章例題 28

x := ⟨Identifier⟩

v := lambda x.e|contC |1+|call/cc| ⟨NaturalConstant⟩ e := e e|x|v

C := []|C e|vC

図5.1 継続を持つラムダ計算の構文

C[(lambda x e₁) e₂] → C[e1{x/e₂}] (e1{x/e2} ^は e1 の x に e2 を代入したもの)

C[1+ v] → C[v+ 1]

C[call/cc v] → C[v (cont C)]

C₁[(cont C₂) v] → C₂[v]

図5.2 継続を持つラムダ計算の意味論

typedef x(L) :- atom(L).

typedef v(L) {

L = lambda(X, E) :- x(X), e(E).

L = cont(Hole, Body) :- c(Hole, Body).

L = succ.

L = call_cc.

:- int(L).

}

typedef e(L) {

L = E1 @ E2 :- e(E1), e(E2).

:- x(L).

:- v(L).

}

typedef c(Hole, Body) { Body = Hole.

Body = V @ C :- v(V), c(Hole, M).

Body = C @ E :- c(Hole, M), e(E).

}

この定義を用いて、評価順序や、継続の捕捉・呼出しによる制御までを含めた意味論を

(35)

CSLMNtalで次のように実装できる：

eval($c:c[lambda(X, E1) @ E2]) :- eval($c[subst(E1, X, E2)]).

eval($c:c[succ @ $v]) | $v2 <- $v + 1 :- eval($c[$v2]).

eval($c:c[call_cc @ $v:v]) :- eval($c[$v @ cont(H, $c[H])]).

eval($c:c[cont(H, $c2:c[H]) @ $v:v]) :- eval($c2[$v]).

ここで subst ^{は後述する} capture-avoiding な代入を表すアトムである。それぞれの

CSLMNtalルールがそれぞれの意味論の規則に明らかに対応していることは注目に値す

る。閉じたラムダ項だけを考えれば、subst は次のように定義できる：

Ret = subst(E1 @ E2, $x, $v)

:- Ret = subst(E1, $x, $v) @ subst(E2, $x, $v).

Ret = subst(lambda($x1, E), $x2, $v)

| $x1 == $x2 :- Ret = lambda($x1, E)

| :- Ret = lambda($x1, subst(E, $x2, $v)).

Ret = subst($x1, $x2, $v)

| $x1 == $x2 :- Ret = $v

| atom($x1) :- Ret = $x1.

5.4 ソーシャルグラフの探索

Twitter ^*1 やFacebook ^*2 などの SNS では、“フォロー” や “友人” 機能によって人間関係のグラフ (ソーシャルグラフ) を構築する。ソーシャルグラフから特定の関係にある２者を探索することはグラフからのデータの取り出しであるから、パターンマッチングによって簡潔に記述できるべきである。

例として、 Twitter の “フォロー” 関係を次のようなグラフ構造で表現することを考える：

user([L1, L2]), user([L3]), user([L4]), L1 -> L3, L4 -> L2

“フォロー” はユーザー間の有向リンクとなるため、この向きを２引数の’->’アトムで表

現する (LMNtal のリンクに向きはないが、引数の順序が重要であるという性質により、

*1https://twitter.com/

*2https://www.facebook.com/

(36)

第5章例題 30 L1 -> L3 を L3 -> L1 で置き換えて得られるグラフは元のグラフとは区別される)。

フォロー (->) 関係を有限回辿って得られる推移閉包(->+) を型として次のように書く

ことができる：

typedef ->(U1, U2) { X -> Y :- dlist(X, U1), dlist(Y, U2). } typedef ->+(U1, U2) { :- U1 -> U2. user(X) :- U1 -> X, X ->+ U2. }

これを用いて、間接的に相互フォローの関係にある (u₁ ->+ u₂, u₂ ->+ u₁ の関係にある) ２ユーザーの組 (u₁, u₂) を次のように抽出できる：

user(X), user(Y) | X ->+ Y, Y ->+ X :- ...

(37)

第 6 ^章

CSLMNtal ^{の実装手法}

第 4 章で設計した言語は強力ではあるが、その処理系を実用的な実行効率で実装できることは自明でない。本章では CSLMNtalの処理系のうち、核となるパターンマッチングおよびグラフの書換え処理に関連する部分の効率的な実装手法を紹介する。本章で解説されているすべての手法はhttp://github.com/k-nara/csflatlmn/ ^{に実装があり、}

パーザー等のインターフェースを補えば CSLMNtal処理系として利用できる。

本章で掲載されているソースコードは特に明示されない限り、プログラミング言語 Gauche [8] のプログラムである。

6.1 ^{グラフの内部表現}

6.1.1 アトム

n 価のアトムとは、名前と n つの順序づいた引数を持つものであった。この処理系では、これを名前を表す文字列と引数を保持する長さ n の配列とのペアで保持する。配列のそれぞれの要素は、別のアトム a へのポインタと引数のインデックスを表す自然数 n のペアである。これによって、この引数に一端が接続されたリンクの他端が a の第 n 引数に接続されていることを表現する。

6.1.2 プロセス

この処理系では、簡単のためにアトムのみからなるプロセスとルールとをそれぞれ別のデータ構造で管理している。

分子を作る “,” が可換かつ結合的なので、アトムのみからなるプロセスは本質的にア

(38)

第6章 CSLMNtalの実装手法 32 トムの集合である。頻出する以下の操作：

• プロセスへのアトムの追加・削除

• プロセスにあるアトムが含まれいているかの検査

• プロセスから特定のアトム名・価数を持つアトムを次々に (それぞれ定数時間で) 取り出すイテレータを得る

を定数時間で行うため、この処理系ではプロセスを、キーがアトム名・価数のペア、値がアトムの存在表であるようなハッシュテーブルで保持する。存在表とはキーと値のペアではなくたんにキーが存在するかどうかだけを管理するハッシュテーブルであり、特にここで用いるのはイテレータの取得・呼び出しが定数時間で行えるようなものである。

6.1.3 ^存在表

“変化しない文脈の再利用” の実装のため、存在表の提供するイテレータは破壊的変更に強くなければならない。具体的には：

• そのイテレータの生成後に追加された要素をも取り出すことができる

• そのイテレータの生成後に削除された要素はスキップする

このような存在表はハッシュテーブルと線形リストのペアとして実装することができる。

(define-class <set> ()

((hash :init-keyword :hash) (head :init-keyword :head) (tail :init-keyword :tail)))

(define (make-set :optional [type ’eq?]) (let1 tail-cell (cons #f #f)

(make <set>

:hash (make-hash-table type) :head (cons #f tail-cell) :tail tail-cell)))

(39)

存在表に要素を追加するときには、ハッシュテーブルにこれを追加したのち、線形リストの末尾にも破壊的に追加する。

(define (set-add! set key) (unless (set-member? set key)

(hash-table-put! (slot-ref set ’hash) key #t) (set-car! (slot-ref set ’tail) key)

(let1 newtail (cons #f #f)

(set-cdr! (slot-ref set ’tail) newtail) (slot-set! set ’tail newtail))))

存在表から要素を除くときには、ハッシュテーブルからのみこれを削除する。

(define (set-remove! set key)

(hash-table-delete! (slot-ref set ’hash) key))

存在表のイテレータは線形リスト中のあるコンスセルへのポインタを保持し、その car 部がハッシュテーブルに含まれていればそのオブジェクトを返し、さもなければそのコンスセルを線形リストから破壊的に除いたうえで次のコンスセルについて繰り返す。その後ポインタを一つ進める。

(define (set-get-iterator set :optional [default #f]) (let ([last-pair (slot-ref set ’head)]

[hash (slot-ref set ’hash)]) (rec (f)

(cond [(not (cddr last-pair)) ;; 末尾に来た default]

[(hash-table-get hash (cadr last-pair) #f) (set! last-pair (cdr last-pair))

(car last-pair)]

[else

(set-cdr! last-pair (cddr last-pair)) (f)]))))

設計と効率的な実装手法

再帰的な文脈パターンマッチング 機能を持つグラフ書換え言語の