非正格関数の融合変換における始代数の存在について

酒井政裕,萩野達也,「非正格関数の融合変換における始代数の存在について」, 第10回プログラミングおよびプログラミング言語ワークショップ (PPL2008), pp. 82-85, 2008年3月.

This paper is based on the first author’s master thesis written at the Keio University, Japan.

Abstract

純粋関数型言語の最適化手法としてプログラムの代数的性質に基づいた推論と変換は重要な位置を占めており、特に再帰的なデータ型を始代数とみなすことによって得られる融合変換のための手法が知られている。

しかし、一方で非正格な言語では始代数とみなせないデータ型が存在し得る。そのためこれらの手法を非正格な言語に適用するには、従来は適用対象の関数が正格である場合に限定する必要があった。

本論文ではこの問題について論じ、非正格な言語のデータ型に対応する始代数が存在する為の十分条件を示す。これにより関数の正格性を条件とせずに、始代数の存在を前提とした変換が可能になる。この条件は単純かつ一般的なもので、通常の関数型言語で用いられる多くのデータ型に対して適用できる。

Links: