部分評価

部分評価（ぶぶんひょうか、）は、計算理論における特殊化（特化）による最適化の技法の1つ。
概要.
直感的には、典型的なコンピュータ・プログラムの最適化である定数畳み込みのようなものである。定数畳み込みは「部分評価のうち特に実施しやすい、定数のみからなる式の計算をおこなうもの」と言える。
理論的な説明としては、以下のようになる。プログラムを次のような入力データから出力データへの写像 "prog" とする。
formula_2 は"static data"（静的データ）であり、コンパイル時に分かっている入力データを指す。
部分評価とは、コンパイル時に、静的データから計算可能なものを全て事前に計算しておくことで、formula_3 を formula_4 とすることである。formula_5 は「残余プログラム (residual program)」と呼ばれ、本来のプログラムよりも効率化されていると期待できる。すなわち、部分評価とは、formula_6 から formula_5 への「残余化 (residualize)」と言うことができる。
formula_5 は formula_6 の formula_2 における射影である、とも言う。
二村射影.
部分評価の特筆すべき例として、二村良彦が1971年にその概念に辿りついた二村射影（ないし、二村の射影、と呼ばれる）がある。
formula_5 を計算するプログラム formula_12 を考える。
なんらかのプログラミング言語 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.5 Programmer's Manual") では、そのインタプリタがいかなるものであるかを説明することで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とともに再録されている。