書換え計算モデル論に基づく宣言型言語の並列性の解析および制御

点击翻译按钮获取中文摘要

宣言型言語で書かれたプログラムに暗黙的に存在する並列性を活用し、超並列計算環境下で高速に宣言型プログラムを実行できることを実証しようというのが、本研究の目的である。本研究では、宣言型言語の計算モデルとして、項書換え系に着目している。研究の課題を、(1)項書換え系の超並列計算の理論的な問題点の解明、(2)項書換え超並列計算の実現、(3)項書換え系を計算モデルとする超並列計算に適した宣言型言語の設計に分け、研究を推進した。以下に具体的な研究成果を述べる。項書換え系の簡約戦略項書換え系の簡約戦略における並列処理と逐次処理の長短得失について、理論的な検討を行った。逐次戦略には計算可能性と計算コストの双方を損なわないで、より広いクラスの項書換え系を対象とする正規化戦略がある。これまでに、簡約における巡経路を巧妙に検出し、逐次でも正規化戦略となる知的逐次戦略を見出した。この新たな逐次戦略は従来の逐次戦略の限界であった強逐次正交項書換え系より広い項書換え系に適用することができる。項書換え超並列計算の実現条件付き項書換え系のナローイング戦略を検討した。ナローイングの完全性を保証する戦略として、LOI戦略(Leftmost Outside-In戦略)を定義し、その完全性を示した。完全性は、strict-equationを条件にもつ正交条件付き項書換え系に対して保証される。この結果をさらに作用型条件付き項書換え系に拡張し、高階プログラミングが可能な言語の計算モデルを設計した。並列/分散環境下での制約解決系ナローイング計算系と制約解消系を組み合わせた計算系、制約ナローイング計算系を設計した。