部分評価（英: Partial evaluation）とは、情報工学における特殊化（特化）による最適化の技法の1つ。
目次
1 概要
2 二村射影
3 関連項目
4 参考文献
5 外部リンク
//
プログラムを次のような入力データから出力データへの写像 prog とする。
Istatic は static data（静的データ）であり、コンパイル時に分かっている入力データを指す。
部分評価とは、コンパイル時の静的データを全て事前に計算しておくことで、 を とすることである。prog * は「残余プログラム(residual program)」と呼ばれ、本来のプログラムよりも効率化されていると期待できる。すなわち、部分評価とは、prog から prog * への「残余化(residualize)」と言うことができる。
部分評価の特筆すべき例として、二村良彦が1970年代に発表した二村射影がある。この場合、prog は任意のプログラミング言語のインタプリタである。
Istatic がそのインタプリタ上で動作するソースコードとしたとき、インタプリタの部分評価で生成される prog* は、そのソースコードだけを実行するよう特化したインタプリタであり、インタプリタを実装した言語で書かれていて、ソースコードを改めて供給する必要は無く、本来のインタプリタとソースコードの組合せよりも高速に実行される。すなわち、prog* は Istatic をコンパイルしたものと等価である。
この技法を第一種の二村射影と呼び、二村射影には以下の三種類がある。
インタプリタの特化によるコンパイル
自己適用によるコンパイラ生成
二階の自己適用によるコンパイラ生成器の生成
関連項目
Smn定理
テンプレートメタプログラミング
評価戦略 - 先行評価、遅延評価、短絡評価
参考文献
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.
外部リンク
⇒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
カテゴリ: コンパイラ | プログラミング
更新日時:2008年3月21日(金)08:06
取得日時:2008/10/20 06:15