累積変数を用いるリスト処理関数とその融合法

概要

論文の詳細を見る
関数の間で渡される中間データを排除する方法として,Wadlerによって提案されたdeforestationというプログラム融合手法がよく知られている.その派生としてGillがshortcut deforestationを提案し,これは以下の2点で優れたものとなっている.1つは,変換規則が1つだけであり,実装が非常に容易であること.もう1つが,deforestationが扱うことのできない累積変数を持った関数の融合が可能であることである.しかしながら,変換後のプログラムの分析のしやすさという点では,現在の累積変数に関する解決方法は必ずしも優れているとはいえない.本発表は,ある種の累積変数を持った関数について,関数融合を可能とする方法を提案する.この方法として,まずリスト処理を行う累積変数を持った関数を定義し,shortcut deforestationに基づいた融合法を説明する.また,これを簡略化した融合法も提案する.今回提案する手法は,ある特定の種類の累積変数を扱うものだが,変換後のプログラムの分析が容易となる利点がある.関数融合については,近年属性文法に基づいた手法が提案されており,累積変数を持った関数の融合を実現している.こうした手法との比較も行う.
一般社団法人情報処理学会の論文
2002-03-15