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

全延迟部分评估处理系统的开发

• 批准号: 07780235
• 负责人: 金子 敬一
• 金额: $ 0.64万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780235/
• 关键词: 完全遅延評価; 部分計算; 関数プログラム

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

部分计算是根据执行环境专门化通用程序并将其转变为高效程序的过程。函数式程序的求值方法称为完全惰性求值，在某种程度上具有执行部分计算的能力。研究中，我们开发了一个用于完全惰性评估的翻译系统，该系统结合了适合执行部分计算的技术。我们用它进行了实验。结果，我们获得了以下新知识：·它对于电子表格计算、延迟记忆、删除冗余形式参数和删除公共子表达式等部分计算很有用。我们提出了一个翻译系统。生成包含有效技术的代码。我们在通过科学研究补助金购买的高速工作站上实现了该翻译系统。通过将其应用于模式匹配算法的推导，我们成功地从一个相对简单的程序推导了与 Aho-Corasick 算法相对应的程序。此外，通过使用传统研究进行部分计算，我们成功地推导了与 Aho-Corasick 算法相对应的程序。 Aho-Corasick 算法虽然从理论上表明可以从系统导出翻译系统或翻译系统，但这并不令人满意。没有获得期望的结果。该处理系统能够说明这种可能性。此外，当并行执行完全延迟部分评估时，除了通过本质性分析去除闭包结构之外，我们还表明更新避免分析可以省略闭包更新，因此执行速度可以显着提高。