広範囲なデータ型を対象とした機械的プログラム変換手法の確立

一般にプログラム変換において、データ型毎に変換規則を用意する必要がある。プログラム変換の代表的な例として融合変換があるが、これまで融合変換の研究では、各データ型毎に規則を用意するか、または関手を用いてさまざまなデータ型規則を統一的に記述すると言うことが行われてきた。これに対し、融合変換に、プログラム変換において最も基本的な、関数定義の展開を用いる新たな関数融合方式を提案した(ACM POPL 2007)。この手法では、データ型にかかわらず適用可能な関数の展開を用いるため、データ型ごとに融合規則を用意する必要がなく、また、適用対象の関数定義に特定の形を要求しないため、ユーザー定義の関数が適用対象となる。新たな関数融合方式の核となる考え方は、融合対象の関数をf、gとすると、新しい関数hx=f(gx)を定義し、f、gの定義による展開、簡約など、意味を保つ変換を行い、f、gの連続適用が現れた部分をhで置き換えるというものである。この置き換えを行う規則をfixed point promotion規則として定義した。この変換を行う規則をapply distribution規則として定義した。これらの規則は、複数引数関数の場合にも自然に拡張され、カリー化されている場合にもされていない場合にも成り立つ。提案した新たな規則に基づいて、プログラム(関数定義が1etで入れ子になっている場合)を受け取り融合を行うアルゴリズムを設計し、SML#コンパイラの中間言語上に試験的に実装した。典型的な例で融合変換が成功し、メモリー使用料が半分程度、実行時間が6-8割程度にまで削減され、コード量が数パーセント程度増加する場合もあるという程度である。

一般にプログラム変換において、データ型毎に変換規則を用意する必要がある。プログラム変換の代表的な例として融合変換があるが、これまで融合変換の研究では、各データ型毎に規則を用意するか、または関手を用いてさまざまなデータ型規則を統一的に記述すると言うことが行われてきた。これに対し、融合変換に、プログラム変換において最も基本的な、関数定義の展開を用いる新たな関数融合方式を提案した(ACM POPL 2007)。この手法では、データ型にかかわらず適用可能な関数の展開を用いるため、データ型ごとに融合規則を用意する必要がなく、また、適用対象の関数定義に特定の形を要求しないため、ユーザー定義の関数が適用対象となる。新たな関数融合方式の核となる考え方は、融合対象の関数をf、gとすると、新しい関数hx=f(gx)を定義し、f、gの定義による展開、簡約など、意味を保つ変換を行い、f、gの連続適用が現れた部分をhで置き換えるというものである。この置き換えを行う規則をfixed point promotion規則として定義した。この変換を行う規則をapply distribution規則として定義した。これらの規則は、複数引数関数の場合にも自然に拡張され、カリー化されている場合にもされていない場合にも成り立つ。提案した新たな規則に基づいて、プログラム(関数定義が1etで入れ子になっている場合)を受け取り融合を行うアルゴリズムを設計し、SML#コンパイラの中間言語上に試験的に実装した。典型的な例で融合変換が成功し、メモリー使用料が半分程度、実行時間が6-8割程度にまで削減され、コード量が数パーセント程度増加する場合もあるという程度である。