メタ計算の進化的探索に基づく正当で効率的なプログラムの自動生成

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

メタ計算は、仕様から正当なプログラムを生成するための新しい方法である。メタ計算では、計算状態の束をメタ節集合で表現し、メタルールで変換を次々に行うことによって新しいメタ節を得る。最初と最後のメタ節集合のペアから正当なルールを得ることができ、そのようなルールを集めることによって、プログラムを得ることができる。得られたプログラムの(部分)正当性は、個々のメタルールの正当性から保証できる。正しいメタルールを仕様から作る方法もすでに与えられている。このルール生成のパラメータは、最初のメタ節集合とルール適用の2つである。ルール適用は、メタ節集合のどの位置にどのメタルールを適用するか、それを何回繰り返すかである。本研究では、これらのパラメータを遺伝子にコーディングして、進化的探索によって、よりよいルールを低コストで発見する方法を提案した。その際、ルールの評価として、分岐数が少なく、節のサイズが小さいものを優先する指標を用いた。ポイントとなるのは遺伝子へのコーディングである。ルール適用の可能性はそのときのメタ節集合によって大きく変わるので、あらかじめ遺伝子の空間を固定するのは得策ではない。そこで、メタ節集合とメタルールが与えられたとき、ルール適用の可能性の集合を高速に計算する手法や、その中のルール適用の1つの可能性をメタ節集合に適用して、次のメタ節集合を求める手法を考案し、それらをET言語に組み込み述語として導入した。これにより、メタ計算を基礎とした進化的探索のアルゴリズムの実現が容易になり、メタ計算の探索に基づくプログラム生成を効率的に行うことが可能になった。