CSLMNtal ルールの構成

効率を考慮しない場合の、パターンマッチングおよびグラフの書換え処理の実装につい て大まかに方針を解説する。ソースコードが公開されているため、実装の詳細には深入り せず、方針や重要なテクニックの解説にとどめる。効率化の手法は後に議論する。

プロセス文脈を含まないパターンマッチング

パターンがプロセス文脈を含まない場合のパターンマッチングについて考える。

まずパターン P が連結な場合、あるプロセス Q から P にマッチする部分プロセスP^′ を図 6.1の手順で取り出すことができる。ここで、P にマッチするプロセスを Qが複数 持っている場合、結果に非決定性があることに注意する。

パターン P が連結でない場合、これはいくつかの連結なパターンP₁, . . . , P_n に分割す ることができる。上のアルゴリズムに “後続が#f を返したら別の候補を試す” 処理を加 えてこれを部分手続きとして実装すれば、パターン P にマッチする部分プロセスを取り 出す処理はたんにP₁, . . . , P_n それぞれに対するマッチングの seq% として実装できる。

(seq% (match-component P1) ...

(match-component Pn)) プロセス文脈の型検査

プロセス文脈を含むパターンは、まずプロセス文脈を含まない部分についてパターン マッチングを行い、その後プロセス文脈に対して型検査を行えばよい。

PROCEDUREmatchComponent(P, Q) : h←^プロセスP の適当なアトム

foreachh^′ in{x|x∈Q, x≡h^′} P^′←^{空のプロセス}

S ←^{空のスタック} r←^{空のマップ} S.push(⟨h, h^′⟩) while ¬(S.empty)

⟨a, a^′⟩ ←S.pop

if a̸≡a^′ then returnfalse else

P^′.add(a^′) r[a]←a^′

forifrom 0toarity(a)−1

if a.arg(i)はP のポートthen continue else

if a.arg(i).index ̸= a^′.arg(i).index then returnfalse else

a←a.arg(i).atom a^′←a^′.arg(i).atom if a∈P^′ then

if r[a] =a^′then continue else returnfalse

else

if a^′∈QthenS.push(⟨a, a^′⟩) else returnfalse

returnP^′

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

(seq% (match-component P1) ...

(match-component P_n) (type-check t₁ X1) ...

(type-check t_k Xk))

type-check が失敗したときに#f を返すようにしておけば、 match-component の “後 続が #f を返したら別のマッチを試す” 性質とあわせて、自然にバックトラックが実現さ れる。

第6章 CSLMNtalの実装手法 40

PROCEDUREtypeCheck(t,X) : P ← X に対応する、検査対象のプロセス foreachr int.typeRules

foreachP^′ inr.patternにマッチするP の部分プロセス foreach t(X) inr.subGoals

unlesstypeCheck(t,X) nextg

returntrue returnfalse

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

型定義の構文制約から、プロセス文脈の引数にあたる自由リンクの列が確定すれば検査 対象のプロセスは一意に決まる。これを用いて、ユーザー定義の型t および検査対象の 自由リンクの列 X から実際に型検査を行う素朴なアルゴリズムを図 6.2 のように実装で きる。

グラフの書換え

グラフの書換えは次の２つのステップからなる：

1. パターンにマッチした部分プロセスを削除する (remove-processes) 2. 新しい部分プロセスを生成する (instantiate-process)

パターンマッチングや型検査を行う部分手続きが１つのスタックを引き回し、マッチした プロセスをこのスタックに積んでから後続を呼ぶようにすれば、後続の関数はマッチした プロセスに関する情報を得ることができる。

(define (match-component pattern) (lambda% (stack)

...

;; パターンマッチに成功

(stack-push! stack <^{得られたプロセス}>) (next stack)

(stack-pop! stack) ...))

remove-process はこの情報を利用して、たんにスタックに積まれたプロセスに含まれ るアトムを全て削除すればよい。instantiate-processの実装は自明である。

これらをパターンマッチングの処理に seq% で接続すれば、パターンマッチングから書 き換えまでの一連の処理を行う、CSLMNtalルールの内部表現として利用できる部分手 続きが得られる。たとえば、次のようなルール：

P1, P2, $p1:t1[X1], $p2:t2[X2] :- Q

は内部的には次のような部分手続きにコンパイルして保持しておけばよい (seq% (match-component P₁)

(match-component P2) (type-check t1 X1) (type-check t₂ X2) remove-processes

(instantiate-process Q))

実行効率の解析

本節で紹介した実装は非常に効率が悪い。

たとえば第 5章で紹介したリストのソートの例を考えると、本節の実装では次のような 手順でパターンマッチが行われる。

1. アトムsort(X) を探す

2. アトム’.’(H1, T1, R1) を探す (O(n) つの選択肢) 3. アトム’.’(H2, T2, R2) を探す (O(n) つの選択肢)

4. プロセス文脈の分子 $x1[H1], $x2[H2] ^が ’>’ ^{型であることを検査} (O(1) のコ スト)

5. プロセス文脈 $d1[R1, X] が dlist 型であることを検査 (O(n) のコスト) 6. プロセス文脈 $d2[R2, T1] ^がdlist ^{型であることを検査} (O(n) のコスト) この手順では、交換すべき２つの要素を発見するまでに最悪で

O(n)·O(n)·(O(1) +O(n) +O(n)) =O(n³)

の時間がかかる (n はリストの要素数)。交換が最悪で O(n²) 回必要だから、リスト全 体を整列するには最悪で O(n⁵) の時間がかかると考えられる。さらに、この実行効率は ソート対象のリスト以外のリストの存在を考えない場合のものであり、ソート対象のリス

第6章 CSLMNtalの実装手法 42 トの外にコンスセルがが存在すれば、効率はさらに悪くなる。交換ソートは本来 O(n²) の時間で実行できるはずだから、これはとうてい実用に耐えないものである。