第6章 CSLMNtalの実装手法 42 トの外にコンスセルがが存在すれば、効率はさらに悪くなる。交換ソートは本来 O(n2) の時間で実行できるはずだから、これはとうてい実用に耐えないものである。
から適当なTypeRule を用いて、その一端が T にマッチするような dlist 型のプロセ スを一つ探し、これを仮に $d1 として後続を呼ぶ。たとえばこの例では、dlist の一番 目のTypeRule を用いるともっとも手ごろな dlist 型のプロセス X = R1 が得られる。
これを仮に $d1 として、後続に制御を移す。後続が失敗した場合、別の TypeRule を試 す。たとえばdlist の二番目のルールと一番目のルールをこの順に用いると、次に大き なdlist 型のプロセスX = ’.’(P, R1) (P は何らかのアトム) が得られる。これを繰 り返してゆけば、同じ処理を手続き型で実装した場合のように、リストを先頭から順に探 索してゆくことができる。
プロセスのトラバースの仕方 (TypeRule の選び方) にはいくつかの戦略が考えられる。
保守的なものでは幅優先探索や反復深化探索 (使うTypeRule の数が少ないプロセスから 調べる) があるが、ここでは深さ優先探索を選んで実装した。深さ優先探索は TypeRule の順序によって実行効率に大きな差が出てしまうが、一方でこれはプログラマによる効率 化の余地が大きいということでもある。
6.3.2 変化しない文脈の再利用
ボトムアップの文脈のマッチングによってパターンマッチング自体の効率は改善する。
しかし、交換ソートの最悪の交換回数がO(n2)であることを考えると、リスト全体のソー トを O(n2) の時間で行うためには１回のパターンマッチングのコストが平均 O(1) でな ければならない。これはパターンマッチングの効率化だけでは不可能である。
素朴なルールの実装では、一度ルール適用に成功してグラフを書き換えると、パターン マッチングの過程で得られた情報はすべて捨ててまた初めからパターンマッチングをし直 す。これは、同じ文脈に対して同じ型を複数回検査してしまうなどの無駄を生じる。例の 交換ソートを手続き的に実装する場合、要素の交換が起こってもリストの先頭には戻ら ず、交換の起こった地点から処理を引き続けるだろう。
このような無駄を排除するためには、ルールのマッチするプロセスのうち書換えの前後 で変化しない部分に注目し、この部分に対するマッチングの結果を再利用することが考え られる。たとえば次のような形のルール：
P1, P2 :- P1, P2′
を考えると、このルールのマッチするプロセスのうち P1 は書換えの前後で変化しない。
したがって、これを
第6章 CSLMNtalの実装手法 44 1. P1 をマッチ
2. P2 をマッチ
3. 書換えを行って 1. に戻る と実行するよりも、
1. P1 をマッチ 2. P2 をマッチ
3. 書換えを行って 2. に戻る と実行した方が効率が良い。
複数のルールをまたぐ場合も同様で、たとえば次のようなルール群：
P1, P2 :- P1, P2′ P1, P3 :- P1, P3′ は以下のように効率化できる。
1. P1 をマッチ
2. P2 または P3 をマッチ 3. 書換えを行って 2. に戻る
共通部分を持つルールをプログラム中から機械的に抽出できると良いが、そのための良い アルゴリズムは現時点で見つかっていない。そこで、開発中の処理系では次のような構文 で、ユーザーがルールの共通部分を指定できるようにする：
P { P1 :- P1′. · · · Pn :- Pn′. }
“リンク条件” は “共通部分を持つルール” において、次のように言い換えられる：
1. それぞれのPk :- Pk′ はリンク条件を満たすルール たとえば次のルール
a(X) :- b(X) :- c(X). c(X) :- d(X).
はリンク名 X が５度出現しているが、２つのルール b(X) :- c(X) および c(X) :-d(X) がそれぞれリンク条件を満たすルールであるため、このルールは全体としてリンク 条件を満たす。
変化しない文脈の再利用は次のように実装することができる：“後続を呼び出し、その 戻り値の否定を返す” 部分手続き loop% を、変化しない部分に対するパターンマッチン グとそれ以外の部分に対するパターンマッチングとの間に挿入する。また、スタックに積 まれたすべてのプロセスを削除する部分手続き remove-processesを、引数 n を取って スタックのn 番目に積まれたプロセスだけを削除するように変更する。その上で、#t を 返す関数を後続としてルールのオブジェクトを呼び出す。
(seq% (match-component P1) ; 書換えで変化しない部分 loop%
(match-component P2)
(remove-processes 1) ; P2 だけを削除 (instantiate-process P2′))
グラフの書換えに成功したとき、後続の戻り値が#tであるため(match-component P2) はバックトラックしない。しかしloop%はその否定#fを返すため、(match-component P1) はバックトラックする。すなわち、引き続き次の文脈を探索する。
6.3.3 戻りがけ順計算の最適化
変化しない文脈の再利用は、ソートのようにデータ構造のルートから末端に向かって計 算の進んでいくような例では有効である。しかし評価文脈の例のように、データ構造の末 端から戻りがけに計算をしていくような例題に対しては機能しない。
戻りがけに計算をしていくような例題の実行を効率化するためには、パターンマッチン グ処理のうち loop% よりも上流にある各ステップ (部分手続き) において、ルール適用が 成功したうえで後続から制御が戻ってきた場合、そのまま呼び出し元に制御を戻すのでな くもう一度そのステップを繰り返し、これに失敗してから初めて制御を戻すようにすれば よい。このとき、“loop% より上流にある或る部分手続き P が制御を呼び出し元に戻す ならば、そのとき P に至った探索経路に対してこのルールが成功することはない” こと が保証される。ここから次のことが言える：非決定性を生じないステップではこの繰り返 し処理を行う必要はない、また非決定性を生じるステップでも、今まさに制御の戻ってき た枝については再び試す必要がない。
したがって具体的には、ソースコードに次の変更を加えればよい：
1. loop% を、 “後続が non-#f な値を返す限り後続を繰り返し呼び続け、後続が #f を返した場合、後続が過去に１回以上 non-#fな値を返したならば特別なシンボル
第6章 CSLMNtalの実装手法 46 loopを、さもなければ #f を返す” 部分手続きとする
2. or% を、“ある部分手続きが loop を返した場合、その部分手続きを除いた残りの すべての部分手続きを再び上から順に試し、すべてが#f を返したならば loop を 返す。ある部分手続きが loop を返したならばこれを繰返す。さもなければ後続の 戻り値をそのまま返す” よう変更する。
3. match-component も同様に、“後続が loop を返した場合、そのプロセスを除い た残りのすべてのプロセス候補を再び順に試す。すべてのプロセスについて後続が
#f を返したならばloop を返す。あるプロセスについて loop を返したならばこ れを繰返す。さもなければ後続の戻り値をそのまま返す” よう変更する。
6.3.4 実行効率の評価
ここに挙げた３つの効率化を実装し、第 5章のいくつかの例題について実行効率を評価 した。ただし現状の処理系にはパーザー等のインターフェースが未実装であるため、実行 時間の計測にあたってはルールの内部表現を直接入力することで実行した。実行環境は以 下のとおりである：
OS Windows 7 64bit (SP1) CPU Core i5-2450
RAM 4GiB
Runtime gosh 0.9.3.3
リストの交換ソート
ソートの例題における、リストの要素数とソートの所要時間との関係を図6.3 に示す。
実線は上から O(n3), O(n2), O(n) 、データ系列はそれぞれ
• random…… 1 から 1000 までの乱数からなるリスト
• random small …… 1 から 3 までの乱数からなるリスト
• descending…… 1000 から 1 づつ減ってゆく降順リスト
• ascending…… 1 から 1 づつ増えてゆく昇順リスト
• constant …… すべての要素が 1 であるようなリスト
である。
図6.3 リストの要素数とソートの所要時間の関係
これによれば、どのデータセットも実行時間は O(n2) に漸近していて、また交換回数 の多いデータセットほど定数倍が大きくなっている。これは手続き的に実装した場合と同 様の振舞いである。
逐次処理の表現
逐次処理の例題における、算術式中の add 演算子の数と式全体の評価にかかる時間と の関係を図 6.4 に示す。実線は上からO(n2), O(n)、データ系列はそれぞれ
• balanced…… 構文木が平衡二分木であるような算術式
• left-leaning …… すべての add の右オペランドが定数であるような算術式
• right-leaning …… すべての add の左オペランドが定数であるような算術式
である。なおここでは扱う数値の大きさの実行時間への影響には関心がないため、算術式 中のすべての定数を０として計測を行った。
図を見てみると、漸近計算量は O(n)に漸近している。これも手続き的に実装した場合 と同様の振舞いである。
第6章 CSLMNtalの実装手法 48
図6.4 算術式の演算子数と評価の所要時間の関係
継続を持つ関数型言語のプロトタイピング
第 5 章のモデルは、元の意味論と対応を取るため代入(subst) がβ簡約のたびに代入 の対象となる変数を探索する冗長な定義となっており、本質的に実行効率が悪い。これは 処理系の実行アルゴリズムに起因するものではない。
グラフ書換え系におけるλ計算の適切なエンコード方法にかんする研究[12] があるが、
本論文の趣旨とは直接関係がないためここでは触れない。
ソーシャルグラフの探索
ソーシャルグラフの探索の例題は現状の処理系で効率的に実行することができない。こ れは制約：
• TypeRule 右辺に出現するリンク名は、同じリンク名が左辺か型定義の仮引数に含
まれていなければならない
のために型の定義が冗長となっているからである。
この制約が取り除かれれば、型 “->+” の２番目のTypeRule を次のように書き換える ことで