部分評価
直感的には、典型的なコンピュータ・プログラムの最適化である定数畳み込みのようなものである。定数畳み込みは「部分評価のうち特に実施しやすい、定数のみからなる式の計算をおこなうもの」と言える。
理論的な説明としては、以下のようになる。プログラムを次のような入力データから出力データへの写像 prog とする。
p r o g : I s t a t i c × I d y n a m i c → O {\displaystyle {\mathit {prog}}:I_{\mathit {static}}\times I_{\mathit {dynamic}}\to O}
I s t a t i c {\displaystyle I_{\mathit {static}}} はstatic data(静的データ)であり、コンパイル時に分かっている入力データを指す。
部分評価とは、コンパイル時に、静的データから計算可能なものを全て事前に計算しておくことで、 ⟨ p r o g , I s t a t i c ⟩ {\displaystyle \langle {\mathit {prog}},\,I_{\mathit {static}}\rangle } を p r o g ∗ : I d y n a m i c → O {\displaystyle {\mathit {prog}}^{*}:I_{\mathit {dynamic}}\to O} とすることである。
部分評価(ぶぶんひょうか、英: partial evaluation)は、計算理論における特殊化(特化)による最適化の技法の1つ。
部分評価の特筆すべき例として、二村良彦が1971年にその概念に辿りついた二村射影(ないし、二村の射影、と呼ばれる)がある。
p r o g ∗ {\displaystyle {\mathit {prog}}^{*}} を計算するプログラム α ( p r o g , I s t a t i c ) = p r o g ∗ {\displaystyle \alpha ({\mathit {prog}},\,I_{\mathit {static}})={\mathit {prog}}^{*}} を考える。
なんらかのプログラミング言語 X のインタプリタ I、その言語で書かれたプログラム p があるとすると、α(I, p) の出力 Ip は、p を I で実行した場合と同じ結果となるプログラムである。すなわちプログラミング言語 X のコンパイラで p をコンパイルしたものと同等である。これが第1二村射影である。
α(α, I) = αI について考える。αI(p) = Ip なので、αI はプログラミング言語 X のコンパイラである。これが第2二村射影である。
α(α, α) = αα について考える。αα(I) = αI なので、αα はあるプログラミング言語のインタプリタを入力とし、その言語のコンパイラを出力する、コンパイラジェネレータである。これが第3二村射影である。
当時二村はLispのマニュアルを読んでコンパイラを実装する仕事に取り組んでいた。マニュアル (LISP 1.