部分評価

部分評価とは

部分評価（Partial Evaluation）は、計算理論におけるプログラム最適化の技法の一つです。これは、プログラムの実行時に必要となる入力データのうち、コンパイル時に既に判明している静的データ（static data）を事前に処理することで、プログラムの実行効率を向上させることを目的とします。

部分評価の概要

直感的に理解するためには、定数畳み込みを考えるとわかりやすいでしょう。定数畳み込みは、式の中の定数部分をコンパイル時に計算することで最適化を行う手法ですが、部分評価はこれをさらに一般化したものと捉えることができます。つまり、コンパイル時に計算可能な処理を全て済ませておくという考え方です。

プログラム `prog` は、静的データ `I_static` と動的データ `I_dynamic` を入力として、出力 `O` を生成する写像であるとします。

math
{\mathit {prog}}:I_{\mathit {static}}\times I_{\mathit {dynamic}}\to O

部分評価では、このプログラム `prog` と静的データ `I_static` が与えられた時に、それらから計算可能な部分を全て事前計算し、その結果をプログラムに組み込みます。これにより、プログラムは以下のような形に変形されます。

math
{\mathit {prog}}^{}:I_{\mathit {dynamic}}\to O

ここで、`prog` は「残余プログラム（residual program）」と呼ばれ、元のプログラム `prog` よりも効率的に実行できることが期待されます。

部分評価のプロセス

部分評価は、元のプログラム `prog` から残余プログラム `prog` を生成するプロセス、すなわち「残余化（residualize）」と捉えることができます。この残余プログラムは、元のプログラムの静的データにおける射影であると表現することもできます。

二村射影

部分評価の重要な応用例として、「二村射影（Futamura Projection）」が挙げられます。これは、1971年に二村良彦氏が提唱した概念で、部分評価を自己適用することで、コンパイラやコンパイラジェネレータを自動生成する理論です。

残余プログラム `prog` を計算するプログラムを α とすると、

math
\alpha ({\mathit {prog}},\,I_{\mathit {static}})={\mathit {prog}}^{*}

と表すことができます。ここで、あるプログラミング言語 X のインタプリタ I と、言語 X で書かれたプログラム p があるとします。この時、α(I, p) の出力 Ip は、p を I で実行した場合と同じ結果となるプログラムとなり、これはプログラム p を言語 X のコンパイラでコンパイルしたものと同等になります。これが第一二村射影です。

さらに、α(α, I) = αI について考えると、αI(p) = Ip となり、αI は言語 X のコンパイラそのものであると言えます。これが第二二村射影です。

そして、α(α, α) = αα について考えると、αα(I) = αI となり、αα はプログラミング言語のインタプリタを入力とし、その言語のコンパイラを出力する、コンパイラジェネレータとなります。これが第三二村射影です。

二村氏は、Lispのマニュアルを読んでコンパイラを実装する過程で、インタプリタがあればそこからコンパイラを生成できるという発想に至ったと言います。この自己適用という概念は「運良く」導き出されたものだと述べています。

二村射影の歴史

二村氏による最初の発表は「計算過程の部分評価：コンパイラ・コンパイラの一方法」（1971年）という題でまとめられました。その後、アンドレイ・エルショフ氏が bit誌に「フタムラの射影について」という記事を寄稿し、部分評価とインタプリタ、コンパイラ、コンパイラジェネレータの関係を説明する3つの式を「フタムラの射影」と呼ぶべきだと述べました。

英語で Futamura Projection という表現が使われるようになったのは、部分評価に関する国際会議 Partial Evaluation and Mixed Computation (PEMC) において1987年のことでした。初出の文献は日本ソフトウェア科学会の『コンピュータソフトウェア』に二村氏へのQ&Aとともに再録されています。

参考文献

- 二村良彦 (1971). “計算過程の部分評価 – コンパイラ・コンパイラの一方法”. 電子通信学会論文誌 54-C (8): 721–728.
- Yoshihiko Futamura (1971). “Partial Evaluation of Computation Process – An Approach to a Compiler-Compiler”. Systems, Computers, Controls 2 (5): 45–50.
- Charles Consel and Olivier Danvy (1993). “Tutorial Notes on Partial Evaluation”. Proceedings of the Twentieth Annual ACM Symposium on Principles of Programming Languages: 493–501.
- Andrey P. Ershov (1980年). “フタムラの射影について”. bit Vol. 12 No. 14. 1980年12月号: 4–5.

外部リンク

- Neil D. Jones, Carsten K. Gomard, and Peter Sestoft: Partial Evaluation and Automatic Program Generation (1993) - オンラインで全文が公開されている書籍。
- partial-eval.org - 部分評価研究に関するオンライン書誌情報。
- C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)
- C++ Templates as Partial Evaluation - PDF版
- Applying Dynamic Partial Evaluation to dynamic, reflective programming languages

もう一度検索