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

具有完全惰性求值的函数程序的部分计算

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

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

Part of the calculation is based on the specialization of the operating environment in general, and the optimization of the efficiency is based on the optimization of the operating environment. The evaluation method of complete delay evaluation is different from that of partial calculation ability. This research is aimed at the development of a complete evaluation system and its application. As a result, the following information is obtained: table calculation, delay reduction, removal of long quotation. This is the first time that the Knuth-Morris-Pratt family has been successfully exported to China. In addition, the optimization technique of the optimization of the system is to eliminate the common partial expression, and the relevant number is to apply the optimization technique to the system. A common partial expression exists in the case of a conditional divergence, and a common partial expression exists in the case of a conditional divergence. The results of the calculation are shown in this paper. This research was successful in the acquisition of scientific research grants and the implementation of a comprehensive evaluation system.