日々の流転

λ. Deriving Structural Hylomorphisms From Recursive Definitions by Zhenjiang Hu, Hideya Iwasaki, Masato Takeichi

m-a-oさんも書いていたが、Warm Fusion と比べるとシンプルで良いな。

ただ、CPOで多項式関手の始代数が存在するとか言っている*1のが、ちと不安だけど。

ここで扱っている言語はネストした再帰呼び出しを含まない。そのためアッカーマン関数やたらいまわし関数のような関数は扱えない。

2007-08-28 追記

書くのを忘れていた*2が、Grant Malcolm の Data structures and program transformation を実際に確認。“Data structures and program transformation”ではデータ型を圏論的に特徴付けて promotion 等を扱っているが、CPO等の具体的な圏でそれらのデータ型や関手が存在するとは言っていない。 むしろ、それらのデータ型定義から自由生成される圏で議論をしていると考えるべきところだろう。 また、polynomial functors という言葉も使っていない。

なのでこの論文(Deriving Structural Hylomorphisms From Recursive Definitions)での、「Thrughout this paper, our default category C is a CPO, the category of complete partial orders with continuous functions. (略) It is known that an initial algebra in the category of F-algebras exists when F is a polynomial functors[Mal90].」という記述は……