完全遅延評価による関数プログラムの部分計算

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

部分計算とは,汎用プログラムを実行環境に基づいて特殊化し,効率的なプログラムに変更することである.完全遅延評価と呼ばれる関数プログラムの評価方式は,部分計算の能力をある程度備えていることがわかっている.この研究では,この点に着目して完全遅延評価系を部分計算に利用するために有効であると思われる技法を開発し,実験を行なった.その結果,新たに以下のような知見を得た:・表計算,遅延メモ化,冗長な仮引数の除去が有効であることが判明した.これをパタン照合アルゴリズムの導出に適用して,単純なプログラムからKnuth-Morris-Prattアルゴリズムに対応するプログラムを導出することに成功した.・また,コンパイラの最適化技法の一つとして知られている共通部分式の削除を,関数プログラムに対しても適用できるように拡張した.これにより,異なる条件分岐の中に存在する共通部分式も一つにまとめることができるようになり,テストプログラムを与えて,どれか一つを評価することによって,その評価結果をすべての分岐で享受することができるようになった.・また,従来の研究によって部分計算を実行することで,インタプリタからコンパイラやコンパイラコンパイラを導出できることが理論的には示されていたが,満足すべき結果は出ていなかった.この研究では,科学研究費補助金によって購入したパーソナルコンピュータとハードディスクからなるシステム上にラムダ巻き上げ技法によって実現した完全遅延評価系を用いることで,これらのプログラムを導出することに成功した.