構成的手法によるプログラムの効率化に関する研究

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

構成的手法によるプログラム変換では,プログラムや型定義を数学的な対象として扱い,少数の強力な変換定理を用いてプログラムを効率のよいものに変換していく.本研究では,関数プログラムをその対象とし,構成的手法を用いたプログラムの効率化の可能性について考察し,以下のような結果を得た.・構成的手法においてはcatamorphismと呼ばれる範疇の関数(プログラム)が重要な役割を果たすが,従来のcatamorphismだけでは記述できないようなプログラムに関しても型変換の前処理を施すことによってcatamorphismの枠組に入れることができることを示した.・上の「型変換」はcatamorphismとは双対の関係にあるanamorphismの範疇に入るものになり,その結果,元の(変換前の)プログラムはcatamorphismとanamorphismの合成,すなわちhylomorphismで表現されることが判明した.・hylomorphismに対する変換定理を適用しやすくするための,hylomorphismを「再構成」する変換アルゴリズムを確立した.・従来のcatamorphismを高階関数に拡張するというという「高階catamorphism」の考えは,上で述べた型変換の前処理と密接な関係にあることが判明した.以上によりhylomorphismが,構成的手法の見地からみた関数プログラムの「標準形」となりうる可能性が示された.