記号処理言語の新しい評価機構の関する研究

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

Improving Valueとは,「少しづつ(ある判断基準からみて)改良されていく値の系列」を表現するデータ構造であり,枝苅りに代表される探索問題において不要な探索を回避するのに役立つことが知られている.本研究では,関数型言語をはじめとする「記号処理言語」に関して,Improving Valueを一般化したデータ構造に基づく新たな評価機構の可能性について考察し,以下のような結果を得た.・探索問題だけではなく,無限リストの長さを扱ったり繰り返し計算をおこなうような場面でImproving Valueが有効であることが判明した.ただし,関数型言語における参照透明性などの「良い性質」をいかに保存してImproving Valueを言語に採り入れるか,という問題点があることもわかった.・評価機構としては従来のstrictな評価だけでは不十分で,強strict(従来のstrictに相当する)と弱strictという二段階の評価機構が必要であることが判明した.・本研究費補助金によって購入した計算機を用いて,G-machineと呼ばれる関数型言語の翻訳系を,Inproving Valueを扱うことができるように拡張した.・Improving Valueによる利点を享受するするためには,プログラムに対する静的な変換(前処理)をおこなうことも重要である.本研究では,構成的手法を用いた関数プログラム変換が実行効率の向上に広く貢献できることを示した.