メッセージ交換を用いた項書き換え系のリデューサの作成

概要

論文の詳細を見る
項書き換え系(以下TRS)のリダクションを実現する方法の1つに,メッセージ交換を用いる方法[1]がある.メッセージ交換によるリダクションは,TRS上の各関数記号fに対してproc(f)(プロセスという)を割り当て,リダクションの実行時には,それらの間で,定まったプロトコルを用いて通信を行うことによりリダクションを行う方法である.すなわち,この方法はTRSをプロセスの集合へ変換するコンパイル方式である.一般にコンパイル方式で最外戦略を実現する際には書き換えの制御を行うランタイムルーチンを付加する必要があり,書き換え規則の増加に対して柔軟に対応できない.そのため,一般のコンパイラは最内戦略をとることが多い.メッセージ交換による方式では,最外戦略の実現に関してこのルーチンを必要としないのが特長である.また,proc(f)は,それ自身がメッセージを受け取り,その内部構造(書き換え規則によって定まる)に従った動きをするため,proc(f)が受け取るメッセージの種類によりリダクション時の戦略を変えられる.さらに,メッセージの種類を増やすことにより,簡単に種々の制御機能を追加することができる.
一般社団法人情報処理学会の論文
1990-09-04