氏名: 大塚 和明 (089630408)

論文題目: CMLによる同期機能付きMRCインタプリタの実装


論文概要

メタ項書換え計算(MRC)は、項書換え系を処理するアルゴリズムの記述、 検証を書換え計算に基づいて行うために開発された計算モデルである。 MRCの機能の一つに書換えの同期がある。同期機能によって、ラベルの付いた 書換え規則による書換えは単独では許されず、同一ラベルの二つの規則が 適用可能なときにその二つの規則による書換えが同時に行われる。 この書換えを同期書換えという。同期書換えを利用して書換えの順序を 制御できるようになる。

本論文では、CML (Concurrent ML) 言語を用いて、 同期機能を持つMRCインタプリタを実装する。

CML言語は並列プログラミングと関数型プログラミングの二つの プログラミングモデルを支援し、プロセス間の通信や同期を扱う プログラミングを可能にする。 また、CML言語は関数型言語であるSML言語の拡張であり、SML/NJ の トップレベルでのモジュールの集合として実装されている。

MRCインタプリタでの書換えのアルゴリズムは、まず同期しない書換えを 書換えできなくなるまで行う。次に、同期書換えを一度だけ行い、その後、 再び同期しない書換えを行う。これを繰り返しながら書換えを進めて行く。

MRCの同期書換えはCMLを用いて次のように実装される。 同期書換えはまず、ラベル付き規則についてパターンマッチングを行う。 関数Checkop.runは制御用スレッドcheckを生成し、checkは子スレッドcheckl、 checkrをCML関数spawnによって生成する。checkl、checkrはそれぞれ左部分木、 右部分木のパターンマッチングを行い、その結果をCML関数sendによって 親スレッドのcheckにチャネルを通して送る。checkはこの結果をCML関数recvに よって 受け取り、両方ともtrueの時だけtrueを、それ以外のときはfalseをチャネルを 通して runに送る。この値がパターンマッチングの結果となる。この後、パターンマッ チング の結果がtrueであれば書換えを行い、falseならば次のラベルについて 同様の操作を行う。

CMLでの実装はプログラムの理解のしやすさ、発展性では優れていると思われ る。 しかし、その書換え速度はいままでのインタプリタに比べて1/2〜1/3となってい る。 速度低下の原因調査と改善は今後の課題である。


目次に戻る


asakura@nuie.nagoya-u.ac.jp