二村射影
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/23 06:34 UTC 版)
部分評価の特筆すべき例として、二村良彦が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.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とともに再録されている。
※この「二村射影」の解説は、「部分評価」の解説の一部です。
「二村射影」を含む「部分評価」の記事については、「部分評価」の概要を参照ください。
- 二村射影のページへのリンク
