1研究の背景

　関数型言語は,プログラム開発者に対して高いレベルでの柔軟性や信頼性を提供している.強い型付けシステムにより,プログラマは正しいプログラムを書くのが容易になる.遅延評価,抽象データ型,型の多様性のような特徴が,効率的なソフトウェア開発の手伝いをする.しかしその反面,これらの特徴はみな関数プログラム実行効率の悪化に強く影響してしまう.

　これらの望ましい言語の特徴を保持したまま高速に実行可能なプログラムを作るには,コンパイラにおける最適化が十分に機能する必要がある.簡潔で抽象的に記述されたプログラムを入力として受け取り,できるだけ効率よくそのプログラムを実行させるようなコンパイラを構築しなければならない.プログラム最適化をプログラム変換で行なう手法では,多くのプログラムの改善が,対象となるプログラムのソースレベルでの変遷によって表わされる.この手法は強力で,いくつかの単純な正当性を維持した変換法則から構成される変換システムによって,多くの強力な最適化が記述され,その中には元のプログラムの複雑さのオーダを変えてしまうようなものまで存在する.

　本論文では,関数型言語で記述されたプログラムを効率良く実行するための最適化手法を取り上げる.関数型言語では,プログラムによって作用を記述するのではなく,値を対象としてプログラムを記述する.すなわち,関数型言語で記述されたプログラムは関数定義とその値の操作を含み,これは手続き型言語では動作の列としてプログラムが構成されるのと対照的である.例えば,1からnまでの整数の二乗の和を求めるプログラムを,関数型言語の一つであるHaskellで記述すると以下のようになる.

　一方,これを手続き型言語の一つであるCで記述すると,以下のようになる.

　両者を比べてみると,Cのプログラムでは変数sumに対して加算を繰り返す動作によって,結果を得ていることがわかる.これがHaskellだと,同様の処理を基本的な関数の組み合わせによって簡潔に記述することが可能である.

2プログラム融合変換

　我々の考えを説明するために,先ほど例として挙げた,1からnまでの整数の2乗の和を計算する関数sumSqを考えてみよう.このプログラムは,リスト構造を扱う3つの再帰関数の組み合わせで定義されている.[1..n]は1からnまでの整数のリストを生成し,map squareは最初に生成されたリストの各要素を2乗したリストを生成し,sumはそのリストの各要素を足した値を計算する.

　このプログラムは可読性と高いレベルでの抽象化という点では優れている.プログラムsumSqは,数の生成,数の2乗,和の計算という3つの異なる処理を組み合わせて記述されているため,相対的に簡潔で書き易く,潜在的に再利用可能であるといえよう.その一方,このプログラムは本来不要であるはずの中間的なリスト構造を3つの関数間の情報伝達に用いているため,関数[1..n]はリスト[1,2,・・・,n]を関数map squareへ渡し,さらに関数sumへリスト[1,4,・・・,n2]を伝えている.

　残念ながら,このような中間データリストは,例え遅延評価の枠組であっても生産され伝えられ捨てられる.これは実行時間やメモリ消費において多大な影響をもたらす.効率的なプログラムを得るためには,3つの要素関数が1つにマージされ,中間データ構造の生成を抑えることが望ましい.これがプログラム融合変換(program fusion)の目指すところである.

　融合変換には大きくわけて探索ベースの手法と運算的手法の2通りのアプローチがある.

　伝統的な探索ベースの手法[Wadler88,Chin92]では,再帰関数の組み合わせを1つの関数に変換する際に,unfold/fold変換[Burstall & Darlington77]を用いる.我々の例では,再帰関数[m..n],map square,sumをunfoldし,展開された式に対して何らかの法則に基づいてそれを操作し,部分式からこれまでにunfoldしたパターンにマッチするようなら対応する関数適用でfoldすることによって新たな関数を得ることができる.

　この手法が探索ベースと呼ばれるのは,基本的にすべての現われた関数呼出の履歴を保存し,foldの段階において関数定義を探索しなければならないからである.この関数呼出の履歴を保存しステップの制御を賢く行なわなければならないのは,無限なunfoldを避けるためであるが,これにより実質的なコストや複雑度は増し,このためにこの手法を用いたシステムは実験用では存在するものの広く用いられるまでには至っていない.

　我々の関心は,運算的(calculational)な手法[Takano&Meijer95,Hu et al.96]にある.これは,探索ベースの手法と比べて相対的に新しく注目されている手法で,変換過程に重点をおいた既存のものと異なり,各要素となる関数内に存在する再帰構成子(hylomorphism,以下Hyloと略)の探索に着目している。従って融合変換自体は,単純な変換法則である酸性雨定理(Acid Rain)[Gill et al.93,Takano&Meijer95]を単に適用するだけで行なうことが可能である.

　先程の例でいうと,sumSqはsum.map square.enumFromToの関数結合で表わされる.なおenumFromTo m nは[m..n]を関数形として明記した等価な表現とする.これを実際にHylo融合変換を用いて変換するには,3つの各再帰関数からHylo関数に変形する.次に各Hylo関数が融合に適した条件を備えているか判定し,備えているときは酸性雨定理に従って2つのHyloを1つのHyloに変換することができる.この処理を繰り返した上で,最終的に結果として残ったHyloを元の形である再帰的な定義に書き換え直すことによって,Hylo構造に含まれる非効率的な部分を除去する.この例では,以下のプログラムが変換結果として生成され,これが元のものと比べてより効率的であることは,すべての中間データ構造が除去されたことから明らかである.

3本論文の貢献

　運算的な手法は,より現実的なものとして議論されてきたが,我々の知っている範囲では,この手法に基づき実装された融合変換システムはこれまで存在しなかった.この融合変換システムの設計と実装において困難であるのは,以下の2点にまとめられる.

・変換法則を実装するための構成的アルゴリズムの開発

　プログラム運算は,プログラム変換の一種で,豊富に用意された変換法則に基づくプログラムヘの操作が適用されることによって進行する.しかしこれらの法則は,基本的に自動変換ではなく手によって変換されるように導かれるよう開発されたものであり,その多くは構成的ではない.したがって,全自動融合変換システムを実装するためには,まずそれらの非構成的変換法則を実装するための構成的アルゴリズムを開発しなければならない.

・実用的な利用のための実装上の問題点

　実用的な融合変換システムの設計実装にあたって,多くの実用的問題点を考慮しなければならない.とくに言語設計とアルゴリズム設計の2点の仕様に焦点をあてることにする.言語設計は,対象とする問題を指定するのに便利なだけでなく,一般的かつ十分な機能をもつものでなくてはならない.アルゴリズム設計は,単純なトイプログラムだけではなく,実用的な規模のプログラムに対しても適用可能なものであるようにしなければならない.

　本論文の主な貢献は,これまで理論としてしか示されることのなかった構成的アルゴリズム論に基づく融合変換に対し,その具体的な手順をアルゴリズムとして示すとこにある.また,ここで示したアルゴリズムを,広く利用されている既存のコンパイラに最適化処理として埋め込むことによって,その有効性の検証も行なった.これらの事項に関して,以下においてより詳しく説明する.

Hylo融合変換の理論的背景の確立

・構成的アルゴリズム論に基づく融合変換の実装への試み

　まず,構成的アルゴリズム論に基づいた運算的アプローチの概念を融合変換システムの実装に用いた最初の試みである.これは,理論的な関心にとどまっていた従来の探索型手法とは大きく異なる点である.また,shortcut融合変換エGill et al.93,Gill96]はすでに処理系の内部に実装済で広く利用されているが,カテゴリ理論を用いてさらに拡張しているHylo融合変換では,リスト以外の中間再帰構造も除去可能であったり,変換対象の関数に予め前処理しておく必要がない,などの利点があることが知られている.

・融合変換を行なうために不足していたアルゴリズムの提示

　酸性雨定理を適用するために必要なφ,ψ部からγ,σを導出するためのアルゴリズムを,入力となる式の場合分けとして明確に示した.またHyloにおけるψ側の再構成アルゴリズムを示し,これによってφ,ψの簡略化がより進みさらに融合変換可能な箇所が増えたことを確認した.

汎用処理系に対するHylo融合変換の実装

・GHCに対する融合変換の実装

　HYLO融合変換を独自のシステムではなく,既存のHaskeｌｌコンパイラ(GHC)内部に最適化変換の一種として埋め込むことによって,様々な範囲のプログラムに適用可能な一般的システムとすることができた.なお,この実装はHaskellコンパイラに強く依存するものではなく,他の処理系や他の言語にも拡張できることを明記しておく.

・WWWインターフェースの実装

　GHCは効率の良いコードを生成するなどの長所も多く備えているがファイルサイズも大きく,初心者が手軽にインストールして使うには難しい側面もある.したがって,誰にでも我々の融合変換の動作を確認してもらえるように,WebサーバでCGIスクリプトを用意し,外部から我々のWebサーバにアクセスするとCGIを経由してHylo融合変換を行なえるような枠組を作成した.

・NoFibベンチマークに対する効果測定

　これまでに多かったnクィーン問題への融合変換のようなトイプログラムでの例だけではなく,数千行からなるような規模の大きいプログラムも含むHaskellの標準的ベンチマークであるNoFibに対して,我々の融合変換の処理を適用し,そのヒーブ使用量などの減少度を調べた.また既に実装されているshortcut融合変換融合変換との比較も行ない,我々の手法の有効性を確認した.

・実装して明らかになったノウハウの提示

　例えばHylo融合変換をどのタイミングで実行するのが一番効果が得られるか,またHylo関数の引数が構成子式だった場合に,それを一段簡約することによって融合変換可能な箇所が増え,全体としてどれほど効率が上がるか、などの実装を行なったことによる様々な試行の結果も合わせて提示することができた.

　本論文は、信頼性の高い計算機プログラムを開発する手法として提案されている構成的アルゴリズム論に基づくプログラミング方法論を実践するにあたり、プログラムの効率を改善するためのプログラム変換技術を扱ったものである。一般に、プログラムはモジュールで構成されるが、モジュール間で受け渡されるデータを除去して実行効率のよいプログラムを得るための実用的な方法を確立する必要があり、そこでは、理論的な成果である融合変換を実用的なコンパイラに実装して、その効果を評価することが課題となる。本研究は、その課題に対して、必要とされるアルゴリズムの開発とそれを既存のコンパイラに実装する手法、さらに、実用規模のプログラムに対するベンチマークによる評価を与えたものである。

　第1章「序論」では、本論文で扱う関数型言語におけるプログラム変換について概説している。研究の背景として関数型言語を用いる利点であるプログラムの簡潔さやモジュール性などを述べた後、短所である実行効率について言及し、それを改善するための既存研究を紹介している。とくに、そのような効率改善の一手法である融合変換(Hylo融合変換)を実在するコンパイラに実装し、その効果を評価した本論文の貢献について要約している。

　第2章「予備知識」では、関数プログラミングの基本的な概念や構成的アルゴリズム論に関する研究を概観し、構成的アルゴリズム論を用いて、プログラム中に内在する再帰構造を抽出しそれを操作するHylo融合変換の特徴に言及している。さらに、本論文中で用いる記法や背景となる定理を示している。

　第3章「運算的融合変換」では、Hyloシステムを実現するために必要ないくつかの重要なアルゴリズムを提示している。これらのアルゴリズムは従来の研究では示されていなかったものであり、自動変換システムを作る際の障壁となっていた部分でもある。ここではとくに、データ生成と消費を捕獲する多様型関数を導出するためのアルゴリズムに焦点をあてている。Hylo再帰関数の導出や展開に関するアルゴリズムは、既存研究を拡張したものとなっている。

　第4章「融合変換の実装」では、Hylo融合変換の処理を、実際に広く用いられている関数型言語のコンパイラ内部に実装した方法について述べている。独自のシステムを構築するのではなく、既存コンパイラに埋め込むことによって、これが広く一般的に利用され、実用的な規模の例題に対して融合変換の有効性を検証することが可能になる。また、WWW上で、融合変換を埋め込んだコンパイラを利用できるインタフェースを用意し、融合変換の効果を視覚的に表示できる仕組みの実現についても触れている。

　第5章「融合変換の性能評価」では、まず、インタープリタを基にしたプロトタイプ上で、プログラムを人手で融合変換したものの実行効率の比較実験を行なって融合変換の有効性を検証した結果を示している。ついで、前章で述べたコンパイラを用いて実用的規模のプログラムによるベンチマークでその長所と短所を広く調べている。そこでは、Hylo融合変換と、別に提案されているfoldr/build融合変換の特長を比較し、後者の適用範囲よりも広い範囲のプログラムに対してHylo融合変換が適用され、効果的であると主張している。

　第6章「関連研究」では、中間データとして受け渡しされるデータ構造を除去するための手法を広くサーベイしている。これらの手法は、fold/unfold変換に基づく手法、リストのデータ構造に着目したfoldr/build法、それを一般の再帰データ型に拡張した本研究の中心的な課題であるHylo融合変換、の3つに大別され、これらの長所短所の比較に加えて、それらの関係を明確にし、そのいくつかは型推論に基づく解析によって変換後の効率が向上することを示している。

　第7章「結論」では、論文の全体を総括し、本論文の主な貢献である構成的アルゴリズム論に基づいた運算的融合変換のアルゴリズムが実在する関数型言語のコンパイラに対しても十分に利用可能であることを確認している。また、今後の課題として、現在のシステ.ムにおける実装上の課題やHylo融合変換と他手法との組み合せた場合の相乗効果などに触れている。

　以上、これを要するに、本研究は関数プログラムの融合変換に関する理論的な成果をもとに、それを実用的なコンパイラに実装するためのアルゴリズムを開発し、それを用いたコンパイラによって、融合変換の効果を実用規模のプログラムに対して実証したものであり、情報工学の研究に貢献するところ大である。よって本論文は博士(工学)の論文として合格と認められる。