完全遅延部分評価のための処理系の開発

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

部分計算とは,汎用プログラムを実行環境に基づいて特殊化し,効率的なプログラムに変更することである.完全遅延評価と呼ばれる関数プログラムの評価方式は,部分計算の能力をある程度備えていることがわかっている.この研究では,部分計算の実行に適した技法を組込んだ完全遅延評価用の翻訳系の開発をし,これを使った実験を行なった.その結果,新たに以下のような知見を得た:・表計算,遅延メモ化,冗長な仮引数の除去,共通部分式の削除といった,部分計算に有効な技法を組込んだコードを生成する翻訳系を提案した.この翻訳系を科学研究費補助金によって購入した高速なワークステーション上に実現し,これをパタン照合アルゴリズムの導出に適用して,比較的単純なプログラムからAho-Corasickアルゴリズムに対応するプログラムを導出することに成功した.・また,従来の研究によって部分計算を実行することで,通訳系から翻訳系や翻訳系翻訳系を導出できることが理論的には示されていたが,満足すべき結果は出ていなかった.本処理系によって,その可能性を例示することができた.・さらに,完全遅延部分評価を並列実行する際には,必須性解析による閉包の構成除去に加えて,更新回避解析によって,閉包の更新を省略することができるようになり,その結果,実行速度がかなり改善できることを示した.