部分評価

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

部分評価(ぶぶんひょうか、: 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)の出力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)という題でまとめられた。Andrey P. Ershovがbit誌に寄せた(1980年掲載)「フタムラの射影について」では、部分評価(同文献中では「混合計算」と呼んでいる)プログラムとインタプリタ、コンパイラ、コンパイラジェネレータの関係を示した3つの式について『教科書が書かれるときには,すばらしい関係式 (I), (II) および (III) は「フタムラの射影」と当然呼ばれるでありましょう.』と締めくくっており、それが「二村射影」という表現の初出と言えるが(なお、Ershovはそのように書いているが、実際には最初の発表では前述のα(α, α)=ααがコンパイラジェネレータであるとは明確に触れておらず、72年と73年の報告が初出である)、英語でFutamura Projectionという表現が使われたのは、部分評価に関する国際会議Partial Evaluation and Mixed Computation(PEMC)において1987年のことであった。初出の文献は日本ソフトウェア科学会の『コンピュータソフトウェア』Vol. 21, No, 5 に二村へのQ&Aとともに再録されている。[1][2]

関連項目[編集]

参考文献[編集]

  • 二村良彦 (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. http://citeseer.ist.psu.edu/futamura99partial.html.  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.

本文注[編集]

  1. ^ 『コンピュータソフトウェア』Vol. 21, No, 5
  2. ^ 第1二村射影〜第3二村射影という呼称の初出については未確認

外部リンク[編集]