部分評価

部分評価（ぶぶんひょうか、英: partial evaluation）は、計算理論における特殊化（特化）による最適化の技法の1つ。

概要

直感的には、典型的なコンピュータ・プログラムの最適化である定数畳み込みのようなものである。定数畳み込みは「部分評価のうち特に実施しやすい、定数のみからなる式の計算をおこなうもの」と言える。

理論的な説明としては、以下のようになる。プログラムを次のような入力データから出力データへの写像 prog とする。

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

$I_{\mathit {static}}$ はstatic data（静的データ）であり、コンパイル時に分かっている入力データを指す。

部分評価とは、コンパイル時に、静的データから計算可能なものを全て事前に計算しておくことで、 $\langle {\mathit {prog}},\,I_{\mathit {static}}\rangle$ を ${\mathit {prog}}^{*}:I_{\mathit {dynamic}}\to O$ とすることである。 ${\mathit {prog}}^{*}$ は「残余プログラム (residual program)」と呼ばれ、本来のプログラムよりも効率化されていると期待できる。すなわち、部分評価とは、 ${\mathit {prog}}$ から ${\mathit {prog}}^{*}$ への「残余化 (residualize)」と言うことができる。

${\mathit {prog}}^{*}$ は ${\mathit {prog}}$ の $I_{\mathit {static}}$ における射影である、とも言う。

二村射影

部分評価の特筆すべき例として、二村良彦が1971年にその概念に辿りついた二村射影（ないし、二村の射影、と呼ばれる）がある。

${\mathit {prog}}^{*}$ を計算するプログラム $\alpha ({\mathit {prog}},\,I_{\mathit {static}})={\mathit {prog}}^{*}$ を考える。

なんらかのプログラミング言語 X のインタプリタ I、その言語で書かれたプログラム p があるとすると、α(I, p) の出力 I_p は、p を I で実行した場合と同じ結果となるプログラムである。すなわちプログラミング言語 X のコンパイラで p をコンパイルしたものと同等である。これが第1二村射影である。

α(α, I) = α_I について考える。α_I(p) = I_p なので、α_I はプログラミング言語 X のコンパイラである。これが第2二村射影である。

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

当時二村はLispのマニュアルを読んでコンパイラを実装する仕事に取り組んでいた。マニュアル (LISP 1.5 Programmer's Manual^[1]) では、そのインタプリタがいかなるものであるかを説明することでLispが説明されており、インタプリタがあればそこからコンパイラを生成することができるのではないか、というのが最初の発想だった。部分計算や自己適用という概念は「運良く」導き出すことができたものだ、という。

最初の発表は「計算過程の部分評価: コンパイラ・コンパイラの一方法」（1971年）という題でまとめられた。アンドレイ・エルショフ（英語版）（露: Андре́й Петро́вич Ершо́в）がbit誌に寄せた（1980年掲載）「フタムラの射影について」では、部分評価（同文献中では「混合計算」と呼んでいる）プログラムとインタプリタ、コンパイラ、コンパイラジェネレータの関係を示した3つの式について『教科書が書かれるときには，すばらしい関係式 (I)， (II) および (III) は「フタムラの射影」と当然呼ばれるでありましょう．』と締めくくっており、それが「二村射影」という表現の初出と言えるが（なお、エルショフはそのように書いているが、実際には最初の発表では前述の α(α, α) = α_α がコンパイラジェネレータであるとは明確に触れておらず、72年と73年の報告が初出である）、英語でFutamura Projectionという表現が使われたのは、部分評価に関する国際会議Partial Evaluation and Mixed Computation (PEMC) において1987年のことであった。初出の文献は日本ソフトウェア科学会の『コンピュータソフトウェア』Vol. 21, No. 5に二村へのQ&Aとともに再録されている^[2]^[3]。

参考文献

二村良彦 (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. Reprinted in Higher-Order and Symbolic Computation 12 (4): 381–391, 1999, with a foreword.
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.

本文注

^ John McCarthy (1962). LISP 1.5 Programmer's Manual. MIT Press. ISBN 0-262-13011-4
^ 『コンピュータソフトウェア』Vol. 21, No. 52024年10月22日閲覧。
^ 第1二村射影〜第3二村射影という呼称の初出については未確認

外部リンク

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

[1] John McCarthy (1962). LISP 1.5 Programmer's Manual. MIT Press. ISBN 0-262-13011-4

[2] 『コンピュータソフトウェア』Vol. 21, No. 52024年10月22日閲覧。

[3] 第1二村射影〜第3二村射影という呼称の初出については未確認

[1]

[2]

[3]

概要

二村射影

関連項目

参考文献

本文注

外部リンク