関数プログラムの再帰構造の抽象化とプログラム融合変換に関する研究

構成的手法によるプログラム変換では,プログラムや型定義を数学的な対象として扱い,少数の強力な変換定理を用いてプログラムを効率のよいものに変換していく.本研究では,従来は十分な考察がなされていなかった相互再帰などの複雑な再帰構造を対象とし,その定式化・変換定理などの実用面における考察を行った.そのために,単純再帰の場合の(一引数の)通常の関手の拡張である二項関手(二引数の関手)を用いて相互再帰を定式化するアプローチをとり,次のような成果を得ることができた.・二項関手への拡張に対応し,Catamorphism,Anamorphism,Hylomorphismなどのプログラム標準形を拡張した.・この拡張は「自然な」拡張になっているので,従来の単純な再帰の場合の融合変換定理が,同じ形の式を保ったまま成立することが示された.・単純な再帰関数のtuple(組)は,相互再帰の特殊な場合として捉えることが可能であることが判明した.したがって,同一のデータ構造を複数回辿るのを防ぐのに有効とされる「tupling」と呼ばれる技法(の一部)は,二項関手を用いた相互再帰の枠組の中に統合することが可能である.

構成的手法によるプログラム変換では,プログラムや型定義を数学的な対象として扱い,少数の強力な変換定理を用いてプログラムを効率のよいものに変換していく.本研究では,従来は十分な考察がなされていなかった相互再帰などの複雑な再帰構造を対象とし,その定式化・変換定理などの実用面における考察を行った.そのために,単純再帰の場合の(一引数の)通常の関手の拡張である二項関手(二引数の関手)を用いて相互再帰を定式化するアプローチをとり,次のような成果を得ることができた.・二項関手への拡張に対応し,Catamorphism,Anamorphism,Hylomorphismなどのプログラム標準形を拡張した.・この拡張は「自然な」拡張になっているので,従来の単純な再帰の場合の融合変換定理が,同じ形の式を保ったまま成立することが示された.・単純な再帰関数のtuple(組)は,相互再帰の特殊な場合として捉えることが可能であることが判明した.したがって,同一のデータ構造を複数回辿るのを防ぐのに有効とされる「tupling」と呼ばれる技法(の一部)は,二項関手を用いた相互再帰の枠組の中に統合することが可能である.