二村投影（Futamura Projections）

1. 背景となる三つの概念

#

インタプリタ

#

インタプリタ（interpreter）は、あるプログラムを読み取り、その動作を実行するプログラムです。入力としてソースプログラムとその入力データを受け取り、結果を直接生成します。

インタプリタ（I）
  入力：ソースプログラム P、入力データ x
  出力：P(x) の実行結果

コンパイラ

#

コンパイラ（compiler）は、ソースプログラムを別の実行可能なプログラムへ変換します。変換は実行前に行われ、生成されたプログラムへ入力を与えると結果が得られます。

部分評価

#

部分評価（partial evaluation）は、プログラムの入力の一部が事前に分かっているとき、その部分を先に計算して、残りの入力だけを受け取る特化されたプログラムを生成する方法です。

プログラム P と既知の入力 a
  ↓ 部分評価器 PE
残差プログラム P_a
  ↓ 残りの入力 b
P(a, b) の結果

2. 第一 Futamura projection

#

インタプリタ I がソースプログラム P と入力 x を受け取るとします。

I(P, x) = P(x) の実行結果

ここで、ソースプログラム P が事前に分かっているとき、I と P を部分評価器に渡します。

PE(I, P) = P'

得られた P' は、もとのソースプログラム P 専用のプログラムです。P' は、毎回ソースコードを解釈する代わりに、残りの入力を受け取って結果を生成します。

これは、特定のソースプログラムに対する専用コンパイラを、インタプリタと部分評価器から生成したと考えられます。これが第一 Futamura projection です。

3. 第二 Futamura projection

#

第一投影では、インタプリタに特定のソースプログラムを与えました。次に、インタプリタそのものを部分評価器へ渡します。

PE(PE, I) = C

ここで生成された C はコンパイラです。C に任意のソースプログラム P を与えると、そのプログラム専用の実行形式を生成できます。

つまり、部分評価器をインタプリタに対して適用することで、一般的なコンパイラを生成できます。これが第二 Futamura projection です。

4. 第三 Futamura projection

#

部分評価器も一つのプログラムです。したがって、部分評価器自身を部分評価器へ渡すことも考えられます。

PE(PE, PE) = G

G は、インタプリタからコンパイラを生成するコンパイラ生成器です。このように、部分評価の仕組みを自分自身へ適用することで、第三 Futamura projection が得られます。

5. 関数型プログラミングとの関係

#

カリー化

#

三つの入力を受け取る関数を考えます。

f : (A, B, C) -> Output

これをカリー化すると、次のような入れ子の関数になります。

f : A -> (B -> (C -> Output))

最初の入力 A だけを与えると、残りの B と C を受け取る関数が返ります。このように、一部の入力を先に与えて残りの入力を待つ処理が、部分適用（partial application）です。

部分適用と部分評価

#

インタプリタを一つの関数として見ると、入力はソースプログラムと、そのソースプログラムに与える入力データです。ソースプログラムを先に固定することは、インタプリタを部分適用することに似ています。

部分評価器は、この考え方をより一般的に扱い、既知の計算を事前に実行して残差プログラムを生成します。

6. 言語処理系への応用

#

コンパイラを一から実装するよりも、インタプリタを実装して部分評価器を組み合わせる方が、言語処理系の研究では扱いやすい場合があります。

この考え方は、PyPy のような言語処理系や、GraalVM のような多言語ランタイムを理解する際にも関連します。ただし、実際の処理系は単純な数式どおりに動くわけではなく、JIT コンパイル、最適化、実行時プロファイルなど多くの技術を組み合わせています。

7. Futamura projection のまとめ

#

Futamura projection の面白さは、インタプリタ、コンパイラ、部分評価器を別々の魔法として扱うのではなく、プログラムを別のプログラムに適用する操作として統一的に見られる点にあります。