ソフトウェアが大規模になるにしたがって,その開発や維持管理は,より複雑で困難なものになっている.高階関数(higher order function)や遅延評価(lazy evaluation)といった機能を備えた関数型言語は,アルゴリズムを簡潔に記述する能力を持ち,ソフトウェアの開発や維持管理の負担を軽減する.さらに,関数型言語は参照透過性(referential transparency)という良い性質を備えている.したがって,この性質を積極的に利用してプログラム変換をおこなうことで,関数プログラムをより効率の良いものへと変形することができる.この結果,簡潔なプログラムを効率良く実行することが可能となる.

　遅延評価では,名前による呼び出し(call-by-name)と引数の評価結果の再利用によって,引数に対する不必要な評価を避けている.完全遅延評価(fully lazy evaluation)は遅延評価における不必要な評価の回避を一般の部分式にまで押し進めた評価方式である.すなわち完全遅延評価においては,各部分式に対して,その中のすべての変数が束縛された後は,その部分式は高々一度しか評価されない,という性質も満たされる.この性質を満たすためには,各部分式に対して以前の評価結果を保持するなんらかの機構を持つことが必要である.この機構によれば関数プログラムを一旦評価すれば,その定義が評価結果で置き換えられ,それ以降の評価においては,初めの評価より簡約段数が少なくなる.本論文では,こうして関数プログラムが改善されることに着目して,これを積極的に利用して関数プログラムの改善を実行するための手法を確立する.完全遅延評価の実現のためには,グラフ簡約(graph reduction)によるものと遅延評価系を用いるものとが有名であるが,グラフ簡約は実行速度について劣るので,遅延評価系によるものを採用した.

　遅延評価系による完全遅延評価の実現は,ソースプログラムレベルの変換によって実行する.この変換には,超結合子(supercombinator)や完全遅延ラムダ持ち上げ(fully lazy lambda lifting),およびラムダ巻き上げ(lambda hoisting)など,いくつかの算法が提案されているが,これらを比較検討した結果,その差異は対象としている遅延評価系の差異によるものであり,能力的には同等であると結論した.これより,いずれの算法を使用しても良いことが判明したが,後に評価結果を大域的に保持しておく機構であるpersistencyを実現しやすいという理由から,ラムダ巻き上げを採用した.

　さらに,完全遅延評価系を部分評価系(partial evaluator)として評価を試みた結果,従来の部分評価系では,停止性を確保することが問題とされてきたが,完全遅延評価系では,評価が要求駆動的(demand-driven)に進むので,停止性について考慮する必要がないという利点を持つことがわかった.しかしながら,自由変数を含むような簡約基(redex)であっても簡約可能な場合に,従来の部分評価系では簡約を先に進めることができるにもかかわらず,完全遅延評価系では中の自由変数が束縛される度に同じ簡約を繰り返してしまうという欠点があることが判明した.この欠点を克服するために新しい評価系-完全遅延部分評価系(fully lazy partial evaluator)-を提案した.簡約の停止性を保証して,なおかつ完全遅延性を損なわないような簡約基を単純(simple)であると定義して,完全遅延部分評価系では,自由変数を含んでいても単純であるような簡約基は後処理系が簡約を実行し,同じ簡約を繰り返さないようにする.

　また,関数プログラムの領域とは独立に研究されているような最適化技法であっても,完全遅延評価による関数プログラムの改善に役立つものとして,表計算(tabulation),遅延メモ化(lazy memoisation),共有解析(sharing analysis),冗長な仮引数の除去(elimination of redundant parameters)などを採り上げ,これらの有効性について例証した.共有解析と冗長な仮引数の除去については,一般の関数プログラムに対する算法が存在していなかったので,本論文においてこれらの算法を提案した.

　部分評価系としての完全遅延部分評価系の能力を確かめるため,翻訳系翻訳系(compiler-compiler)の自動導出実験をおこなった.部分評価系をII,通訳系(interpreter)をI,プログラムをp,入力データをdとすると,

　がそれぞれ,プログラムpの翻訳コード、翻訳系,翻訳系翻訳系となる.完全遅延評価系も部分評価系であるから,完全遅延部分評価系でも翻訳系翻訳系が導出できるはずである.実際には,通訳系Iとしてパタン照合関数を,プログラムpと入力データdとして二つのパタンを使って実験した結果,一度目の評価によって部分計算が進み,二度目の評価では簡約段数が半減し,自動的に翻訳系翻訳系や翻訳系が導出できたと結論した.この理論は部分計算の分野では1960年代には確立されていたが,その長い歴史にもかかわらず,自己適用可能な部分評価系が出現したのはここ数年である.これらの評価系では停止性を確保するために,抽象解釈(abstract interpretation)によっており,複雑な計算を必要とする.これに対して,完全遅延部分評価系では非常に簡単に翻訳系翻訳系の導出に成功しており,その優秀性を示している.

　さらに完全遅延部分評価系に最適化技法を組合わせた場合の能力を確かめるために,比較的単純なパタン照合関数から,Knuth-Morris-Pratt算法やAho-Corasick算法といった効率的な算法に対応する関数プログラムを導出する実験をおこなった.この実験では,不照合を引き起こす以前に,パタンと一致していたテキスト部分に対する情報から次の行動を決める関数が重要な役割を果たし,この関数を遅延メモ化しておくことでプログラムの改善をはかる.遅延メモ化に表計算を組合わせることで,遅延メモ化のためのハッシュ表を小さくすることが可能となる.また冗長な仮引数の除去をおこなうことで,関数プログラムを完全遅延評価にとって見通しの良い構造に変換することができ,簡約段数を大幅に減少させることができることが判明した.

　全体としてまとめると,本論文は以下の点で貢献している.

　・遅延評価系による完全遅延評価の実現のためのプログラム変換算法の差異が,各算法が想定する遅延評価系の差異によるものであることを明らかにし,これらの算法が同等の能力を持つことを示した.

　・完全遅延評価による関数プログラムの改善の過程を調べ,自由変数を含む簡約基については,簡約を進めることができないという問題点を指摘し,この問題点を克服するために完全遅延部分評価系を提案した.

　・完全遅延部分評価系が翻訳系翻訳系を容易に導出できることを示した.また,表計算,遅延メモ化,冗長な仮引数の除去などの技法が完全遅延評価による関数プログラムの改善に役立つことを示すために.完全遅延部分評価系にこれらの技法を組合わせて,比較的単純なパタン照合プログラムから,KMP算法やAC算法に対応するプログラムを導出した.

　本論文は,「完全遅延評価による関数プログラムの改善に関する研究」(Improvement of Functional Programs by Fully Lazy Evaluation)と題し,英文で六章から成る.

　ソフトウェアが大規模になるにしたがって,その開発や維持管理はますます複雑で困難なものになっている.高階関数や遅延評価といった機能を備えている関数型言語は,アルゴリズムを簡潔に記述する能力を持ち,ソフトウェアの開発や維持管理の負担を軽減するために活用できる可能性を有している.さらに,関数型言語の持つ参照透過性という性質を積極的に利用して,プログラムを実行効率の良いものへ変換することも可能である.

　遅延評価は引数に対する不必要な評価を回避するものであるが,完全遅延評価は,これを一般の部分式の評価にまで拡張したものであり,各部分式について,その中のすべての変数が束縛された後は,その部分式は高々一度しか評価しないようになっている.そのために,各部分式に対して,一度評価した結果を保持する機構があるが,本論文では,この機構を積極的に利用することによって関数プログラムを改善する手法を提案している.

　また,関数プログラムとは独立に研究されている種々のプログラムの最適化技法のなかに,完全遅延評価による関数プログラムの改善に役立つものがあることを論じ,これらの有効性を例証している.特に共有解析と冗長な仮引数の除去という技法については,従来一般の関数プログラムに対する算法がなかったので,本論文においてこれらの算法を提案している.

　以下,各章の概要を述べる.

　第1章は序論であり,研究の目的,関数型言語の定義とこれに対する基本操作,完全遅延評価,関数プログラムの改善の意味などについて述べている.

　第2章は完全遅延評価の実現方法と題し,グラフ簡約による方法および遅延評価系を用いるいくつかの手法を紹介している.後者の場合,ソースプログラムの変換のために提案されている完全遅延ラムダ持ち上げやラムダ巻き上げなどの算法を比較検討し,その差異は対象としている遅延評価系の差異によるものであり,能力的には同等であることを示している.

　第3章は完全遅延部分評価系について論じている.完全遅延評価系を部分評価系として使用する場合,従来の部分評価系と比べて,停止性の確保という点では優れているが,同じ簡約を繰り返し実行してしまうことがあるという欠点を有することを指摘し,この欠点を克服する新しい評価系として完全遅延部分評価系を提案し,その実現方法を詳細に論じている.

　第4章では,前章で得た成果を,部分計算の主要な研究分野のひとつである翻訳系翻訳系の自動導出に応用している.この分野の研究の歴史は長いが,自己適用可能な部分評価系が出現したのは,ごく最近のことであり,それらは複雑な計算を必要としている.これに対して著者の提案した方式では,非常に簡単に翻訳系翻訳系が導出できることを実証している.

　第5章では,完全遅延部分評価系に最適化技法を組合せた場合の能力を検証することを目的として,比較的単純なパタン照合関数から,Knuth-Morris-Pratt算法,Aho-Corasick算法などの効率的な算法に対応する関数プログラムを導出する実験を行うた結果を述べている.最適化技法としては,遅延メモ化,表計算,冗長な仮引数の除去などの技法が,きわめて有効であることを実証している.

　第6章は結論である.

　以上を要するに本論文は,アルゴリズムを簡潔に記述する能力を有するが,従来は必ずしも実用的でなかった関数型言語に対して,完全遅延評価という手法を用いてプログラムを改善するための種々の提案をし,それらの提案が翻訳系翻訳系の導出などの実用的な問題に対しても有効であることを実証したものであり,関数プログラムを今後さらに大規槙な実用的問題へ適用するための基礎を築いたものということができ,情報工学に貢献するところが大きい.

　よって本論文は博士(工学)の学位請求論文として合格と認められる.