The Three Projections of Doctor Futamura
This blog post explores the three Futamura projections, which are fundamental concepts in partial evaluation and programming language theory. The author explains how these projections relate to compiler optimization, program specialization, and the Futamura theorem, using accessible examples to illustrate the power of self-applicable partial evaluators.
背景メモ
- フタムラプロジェクションは、計算機科学者・二村良彦が1971年に提唱した、プログラム変換（部分評価）に関する3段階の自己適用技法。与えられたプログラムと入力から「より効率的なプログラム」を自動生成するアイデアを、よりメタなレベルへと一般化する。
- 第1投影は「解釈器 + プログラム → 出力を計算するコード」、第2投影は「コンパイラ + 解釈器 → プログラムをコンパイルするコード」、第3投影は「コンパイラ生成系 + 解釈器 → コンパイラを生成するコード」。
- この3つの射影は、インタプリタ、コンパイラ、さらにその生成系（コンパイラコンパイラ）をすべて統一的に導出できることを示す。理論的には美しいが、実行時最適化の限界や実用上の難しさから「フタムラの呪い」とも呼ばれる。
- 部分評価（partial evaluation）という技法が前提にあり、プログラムを「まだ来ていない入力」を待たずに部分的に実行・変換して効率化する。この考え方は、現代のJITコンパイラやメタプログラミングの理論的基盤のひとつになっている。