部分評価のソースを表示

{{簡易区別|部分適用}}
'''部分評価'''（ぶぶんひょうか、{{lang-en-short|partial evaluation}}）は、[[計算理論]]における[[特殊化]]（特化）による[[最適化 (情報工学)|最適化]]の技法の1つ。

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

理論的な説明としては、以下のようになる。[[プログラム (コンピュータ)|プログラム]]を次のような入力データから出力データへの[[写像]] ''prog'' とする。
:<math>\mathit{prog} : I_{\mathit{static}} \times I_{\mathit{dynamic}} \to O</math>

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

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

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

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

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

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

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

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

当時二村は[[LISP|Lisp]]のマニュアルを読んでコンパイラを実装する仕事に取り組んでいた。マニュアル (''LISP 1.5 Programmer's Manual''<ref>{{Cite book
|title=LISP 1.5 Programmer's Manual
|author=John McCarthy |authorlink1=ジョン・マッカーシー
|isbn = 0-262-13011-4 
|year = 1962
|publisher={{仮リンク|MIT Press|en|MIT Press}}
}}</ref>) では、そのインタプリタがいかなるものであるかを説明することでLispが説明されており、インタプリタがあればそこからコンパイラを生成することができるのではないか、というのが最初の発想だった。部分計算や自己適用という概念は「運良く」導き出すことができたものだ、という。

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

== 関連項目 ==
* [[Smn定理]]
* [[テンプレートメタプログラミング]]
* [[評価戦略]] - [[先行評価]]、[[遅延評価]]、[[短絡評価]]
* [[ジャストインタイムコンパイル方式]] (JIT)

== 参考文献 ==
* {{cite journal|author=二村良彦|title=計算過程の部分評価 &ndash; コンパイラ・コンパイラの一方法|journal=電子通信学会論文誌|volume=54-C|issue=8|page=|pages=721&ndash;728|year=1971}}
* {{cite journal|author=Yoshihiko Futamura|url=http://citeseer.ist.psu.edu/futamura99partial.html|title=Partial Evaluation of Computation Process &ndash; An Approach to a Compiler-Compiler|journal=Systems, Computers, Controls|volume=2|issue=5|page=|pages=45&ndash;50|year=1971}} Reprinted in ''Higher-Order and Symbolic Computation'' '''12''' (4): 381&ndash;391, 1999, with a foreword.
* {{cite journal|author=Charles Consel and Olivier Danvy|title=Tutorial Notes on Partial Evaluation|journal=Proceedings of the Twentieth Annual ACM Symposium on Principles of Programming Languages|volume=|page=|pages=493&ndash;501|year=1993}}
* Andrey P. Ershov (1980年). “フタムラの射影について”. bit Vol. 12 No. 14. 1980年12月号: 4–5.
=== 本文注 ===
<references/>

== 外部リンク ==
* [http://www.itu.dk/people/sestoft/pebook/ Neil D. Jones, Carsten K. Gomard, and Peter Sestoft: ''Partial Evaluation and Automatic Program Generation'' (1993)] - オンラインで全文が公開されている書籍。
* [http://partial-eval.org partial-eval.org] - 部分評価研究に関するオンライン書誌情報。
* [http://osl.iu.edu/~tveldhui/papers/pepm99/ C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)]
** [https://arxiv.org/pdf/cs.PL/9810010 C++ Templates as Partial Evaluation] - PDF版
* [http://people.csail.mit.edu/gregs/dynamic-pe.html Applying Dynamic Partial Evaluation to dynamic, reflective programming languages]

{{DEFAULTSORT:ふふんひようか}}
[[Category:評価戦略]]
[[Category:コンパイラ最適化]]