二村映射
Futamura 投影（Futamura Projection）是编程语言和编译技术中的一个重要概念，由日本计算机科学家 Futamura Yoshihiko 在 1971 年提出。Futamura 投影解释了如何通过对解释器进行部分求值（Partial Evaluation），将解释器转换为编译器，以及进一步的可能转变。
背景与基本概念
在理解 Futamura 投影之前，需要了解以下两个概念：
解释器（Interpreter）：一种程序，它读取并执行另一个程序的代码。解释器按代码的一行或一段来处理，逐行或逐段地将源代码翻译成目标代码并执行。
部分求值（Partial Evaluation）：一种编译技术，旨在通过提前计算程序中能够在编译时确定的部分，从而生成更高效的代码。部分求值会保留在运行时才知道的部分，从而使得程序既高效又灵活。
三次 Futamura 投影
Futamura 投影可以分为三个阶段，称为“第一次投影”、“第二次投影”和“第三次投影”：
- 第一次 Futamura 投影：
- 将解释器和一个特定的源程序作为部分求值器的输入，生成一个针对该特定源程序的专用编译器。这个编译器可以直接将源程序翻译成目标代码。
- 形式化描述：如果有解释器
I和源程序P，通过部分求值（PE），我们可以生成一个等价的目标程序P'。 - 表示为：
PE(I, P) = P'，其中P'是源程序P对应的目标代码。
- 第二次 Futamura 投影：
- 将解释器本身作为部分求值器的输入，生成一个针对任何源程序的编译器。这意味着将解释器的行为部分求值，得到一个编译器。
- 形式化描述：通过部分求值器
PE对解释器I进行部分求值，可以生成一个编译器C，这个编译器可以将任何源程序P翻译成目标程序P'。 - 表示为：
PE(PE, I) = C，其中C是一个可以将源程序P编译成目标代码P'的编译器。
- 第三次 Futamura 投影：
- 将部分求值器本身作为输入，对其进行部分求值，生成一个可以生成编译器的编译器生成器（也称为编译器生成器、编译器编译器）。
- 形式化描述：通过部分求值器
PE对PE进行部分求值，可以生成一个编译器生成器G，该生成器能够生成编译器。 - 表示为：
PE(PE, PE) = G，其中G是一个可以生成编译器的编译器生成器。
意义与应用
Futamura 投影展示了如何通过部分求值将解释器转化为编译器，并进一步展示了编译器生成器的潜力。这一思想在编程语言的实现和优化领域具有重要意义，特别是在自动化生成编译器和提高编译效率方面。
- 第一次投影提供了从解释器生成专用编译器的方法，使得特定源程序可以直接被编译为目标代码。
- 第二次投影展示了如何生成通用编译器，从而无需解释器就可以直接编译任何源程序。
- 第三次投影则展示了生成编译器生成器的可能性，即自动化工具可以生成编译器，这对编程语言设计与实现具有深远影响。
Futamura 投影是一种理论工具，展示了编译和解释之间的深层联系，并引导了编译器自动生成技术的发展。
摘自论坛
相比上一节强调物理或逻辑上客观存在的 “界限”，本节主要强调一种心智活动。这样的心智活动具有一个明显的特征，那就是它具有一种 “递归” 的结构。我们首先从一个概念中抽象出它的形成过程，再将这样的思维过程应用于这个概念自身。如此，我们得到的新概念常常具有这样的结构： A 的 A。
个人认为，本节讨论的思想或许是本文的所有思想中最为重要的那一个。这是因为高阶这一思想具有很好的方法论层面上的指导意义，并且在实践中操作起来又有趣又直截了当——同时，个人的看法是通过这一思想生成的很多概念对启迪编程初学者的思维具有非常重要的意义（事实上，如果要从整个技术界中选一个本科教育一般不大重视、但又极度有价值的术语，我会选闭包和高阶函数）。
通过这样一种 “递归式” 的抽象过程得到的 A 的 A
这一形式的概念，我们通常将其称作 “高阶
A”。比如，将函数代表的过程 (A -> B)
抽象出来，再应用于函数自身，我们就得到了 函数的函数，即
高阶函数（higher-order
function）。个人认为高阶函数和闭包是计算机领域最为重要的抽象之一。
例如，将类型的形成过程（类型描述一个语言中最小单位的类别）抽象出来，应用于类型自身，我们就得到了 类型的类型，即 型别（kind）。
二村映射 (Futamura Projections)
最后，作为压轴，讲一个我昨晚在一篇屯了半年一年的文章中看到的一个概念。我想这个概念应该是超出大部分读者的经验的，而我觉得它还蛮有意思，所以放到最后来大概说说。我们需要从故事的最开始讲起——可能要过很久才能最终看到这个词。
编译技术的分类
我们知道大体上编译技术可以分为两种，分别是 编译器 (compiler) 和 解释器 (interpreter)。编译器执行的是一个两阶段的过程：首先，自源代码编译出目标程序 (target program)，再向目标程序提供输入，然后得到程序的输出；解释器执行的则是一个一阶段的过程：解释器接收源代码和输入，并直接得到程序的输出。在本节中，我们主要关注解释器。
绝大部分的编译原理教科书和课程都只涵盖这两者。然而，事实上还存在着第三种编译技术：某种程度上，它介于解释器和编译器之间，但它既不是解释器又不是编译器——请特别注意这一点。为了方便理解，我先岔开点讲。
函数式编程中的概念
稍有函数式经验的读者应该都听过 柯里化
(Currying)。如果有一个接收 n
个输入的函数，我们可以把它转化成一叠嵌套的高阶函数，这叠高阶函数中的第
i 个接收原函数中的第 i
个输入（仅一个），然后返回接收剩下 n-i 个输入的函数（故为
“高阶函数”）：比如，一个接收 3 个输入的函数
((A, B, C) -> Output)
经柯里化后会成为一叠高阶函数，这个高阶函数中的第一个接收一个输入
A，然后返回一个接收输入 B
的高阶函数；再向其提供输入
C，才能得到最终结果，即柯里化后的结果是
(A -> (B -> (C -> Output)))。
尽管在支持闭包和高阶函数的语言中柯里化和 反柯里化 (Uncurrying) 都能以非常浅显 (trivial) 的方式实现，但仅有少数的编程语言才一等地支持了柯里化，比如 ML 系语言（Haskell, SML, OCaml, F#）和 Scala。
对于一个经柯里化后的函数，如果我们只向它提供前
i (i<n)
个输入，那么我们必然得不到最终的输出，而只能得到一个高阶函数，它会再处理余下的输入：这称作
部分应用 (Partial Application)。
讲了这么一大堆，其实主要就是为了部分应用这个概念。你可能会想知道为什么我在上文不用参数这个惯用说法而是用输入，你可能也已经猜到了，这是因为我希望在此强调将解释器理解成一个函数的思想：它的输入是源代码和这段代码的输入，它的输出是这段代码的输出（事实上，很多语言都提供一些十分类似解释器的机制，它们确实是函数（比如
eval））。
部分求值 (Partial Evaluation)
是的，之所以要将解释器理解成一个函数，是因为我正是要借用部分应用的思想：既然解释器的输入是源代码和输入，那么我能不能部分应用这个 “函数”（即解释器），首先给定源代码，得到一个 “处理剩下参数的高阶函数”（即一个中间程序），然后对于这个中间程序，再提供它的输入，然后得到结果？
答案是，这是可行的。事实上，这一过程称作 部分求值 (Partial Evaluation)，而执行这一过程的程序我们称作 部分求值器 (Partial Evaluator)。部分求值器作用于一个程序和它的一些参数，输出一个该程序对于这组参数 “特化” 后的新的程序。这里的 “一个程序” 我们称作 源程序 (Source Program)，“新的程序” 我们称作 残差程序 (Residual Program)。
回到上边有关解释器举例上来。我们将一个解释器和一个源程序传入部分求值器中，得到的残差程序就是一个接收 输入 返回 输出 的中间程序。
是不是觉得非常的熟悉……？第一阶段我们提供源代码，得到中间程序；第二阶段我们提供输入，随后得到输出。这是在做什么…？
是的，这就是编译。神奇之处在于，我们并没有手工编写一个编译器，我们只是将一个解释器和需要被求值的源代码扔给了部分求值器而已——某种意义上来说，我们是 “免费” 得到了一个编译器。
部分求值器与语言虚拟机
你可能在思考这有什么用？你或许已经将这一思路和语言虚拟机联系了起来：众所周知，实现编译器通常比实现解释器难得多，那我们能不能弄一个本质其实是一个部分求值器的语言虚拟机，在这个虚拟机上实现一门新的语言只需要编写一个解释器就行了，而语言虚拟机会调用它的部分求值器自动帮我生成对应的、更加高效的 “编译器” 呢？
显然，这是完全可行的——事实上这是有产业实践的。PyPy 是一个 Python 语言的解释器实现，它正是基于以上语言虚拟机的思路实现的：在 PyPy VM 上工作的语言有 Python, Ruby 和逻辑编程语言 Prolog 等；除此以外，泛语言高级语言虚拟机（HLLVM）GraalVM 的一个重要组件同样如此，工作在 GraalVM 上的语言包括 JavaScript, Ruby, Python, Java, R 等。
这其实就是 第一类二村映射 (First Futamura Projection)。
二村映射的递归性
既然是放在 “高阶” 这一主题下的，我们当然要用到这一思想：正如前几段的粗体所提示的，部分求值器其实也是一个程序，它自身也能够被部分求值。
回想一开始，解释器 的输入是 源代码 和 输入，我们将 解释器（主体） 和 源代码（主体的其中一个输入） 单独拎出来，扔进了部分求值器中，这是第一类二村映射；即是说，在第一类二村映射中，部分求值器 的输入是 解释器 和 源代码。
我们将这一过程——即 “将 主体 和 主体的其中一个输入 单独拎出来扔进部分求值器中”—— “高阶化”，作用于自身，简单的代换就能得到，我们需要将 部分求值器（主体） 和 解释器 （主体的其中一个输入） 扔进一个部分求值器中。现在我们需要弄清楚，这个 “高阶过程” 得到的残差程序是什么。
注意到，在第一类二村映射中输入只有 解释器 和 源代码。既然我们已经部分求值了前者，那么下一步自然只剩下后者了：向上一段提到的 残差程序 提供 源代码，我们就能得到 目标程序。
向一个程序提供源代码得到另一个程序……
听起来有点像是某个我们已经知道的东西会做的事情。是的，这就是编译。我们的这个
“高阶过程” 得到的残差程序其实是一个编译器，而我们的这个
“高阶过程”
所做的，正是在生成编译器，即，这一过程其实是编译器的编译器——如此，我们终于见到了本节概述中提到的
A 的 A
这样的结构，如果你愿意的话，或许你还可以将这称作高阶编译器。
这其实就是 第二类二村映射 second Futamura projection。
那么，这个 “高阶化” 的过程还能继续下去吗？显然如此。再继续下去，我们就能得到_编译器的编译器的编译器_，也即第三类二村映射 third Futamura projection。再往后呢？这点就留给读者自行阅读和思考啦。