作者实现第二Futamura投影：将特化器自身特化以生成编译器

两个月前，我们把 compfuck 重新变回了解释器，并写了一个特化器：给定一个 Brainfuck 程序，它会把解释器折叠掉，只留下那些无法特化的操作。这就是第一 Futamura 投影，也是我过去用懒散的简写方式把 compfuck 类比成的东西。如果你错过了那篇文章，而这一整段话又让你完全摸不着头脑，那就从那里开始读吧！

当然，那篇文章只是第一步。我们的 Origami 工作还没有结束。

具体来说，我们最终得到了一种无需手写指令翻译就能获得编译程序的方法。这很棒，但我们仍然要对每一个程序运行特化器，每次都要走一遍解释器的源码。然而，特化器和解释器始终是相同的，我们只是换了不同的 Brainfuck 程序。这是浪费，我们可以做得更好。

你现在可能已经隐约知道该怎么处理了：如果输入的一部分是固定的，我们就可以特化。而第二 Futamura 投影正是对特化器本身做了这件事：

compiler = specialize(specializer, interpreter) compiler(program) = specialize(interpreter, program)

图 1：将特化器特化到解释器上。

我们把特化器喂给它自己，把解释器作为它的已知输入。输出的是一个程序，它接受一个 Brainfuck 程序并直接生成残余代码，而无需执行解释器。这就是一个编译器，奇妙又古怪。

这听起来可能像是个花招，而且我花了好一段时间才相信它能产生合理的结果，即使在我理解它之后也是如此。但它确实有效，而且我们最终得到的编译器看起来很像多年前我手写的那个。让我们看看我们是如何走到那一步的。

要特化一个程序，特化器必须理解它。我们旧的特化器只理解一个程序，即解释器。例如，它知道 p 和 i 是静态的，而每个 if 和 let 都属于源码遍历的一部分。我们手工决定了一大堆事情，基本上是为类 Carp 源码做了一个迷你 DSL。

这无法扩展到特化器自身。它的静态部分和动态部分在许多地方混杂在一起，它会调用辅助函数，而且它的递归调用如果天真地展开，并不都会终止。所以第一步是写一个足够通用的特化器，能够特化它自己，这次不用花招。

还有第二个更隐蔽的问题，我上次稍微 gloss over 了一下，因为写那篇文章时我还不完全确定如何解决它：旧的特化器通过把静态表达式交给 Carp 的 eval 来求值。如果我们特化那个，我们最多只能在输出中留下一个对 eval 的调用，而我们的“编译器”在编译时仍然会解释解释器的部分内容。为了消除这一点，特化器需要自己求值静态代码，而且要以一种反过来也能被特化的方式来做。如果这还不明白，没关系。做比说更容易。

不过在继续之前还有一件事，因为我想诚实一点：为了本教程的目的，我选择不把它做成第二 Futamura 投影的绝对通用实现。在不妨碍概念纯粹性的前提下，我们仍然会在方便的地方偷工减料。当这种情况发生时，我也会指出来。

上次，definterpreter 把解释器的函数体存为元数据。现在一个叫 remember 的宏也会存储参数，而 defmix——mix 是这门技术的先辈传下来的名字——对特化器的函数做同样的事，并把它们收集到一个列表中。那个列表就是作为程序的特化器。括号搜索像解释器一样被存储，所以解释器现在是一个有两个函数的程序：一个解释器循环和一个辅助函数。

Carp 在函数体被存储之前展开宏，所以 case、cond、and 和 or 会以 if 和 let 的形式到达1。我们的特化器只需要理解 if、带单个绑定的 let、quote、函数调用和少量原语。它基本上就是一个小型 Lisp，而特化器也是用它写的（没有宏的语法糖）。

我们保留上次对静态 p 和 i 以及动态 t 和 h 的划分，但用一条规则取代手工决策：

(defmix mentions? [e syms] (cond (symbol? e) (member? e syms) (or (list? e) (array? e)) (if (empty? e) false (or (mentions? (car e) syms) (mentions? (cdr e) syms))) false))

图 2：一个表达式是否使用了这些变量中的任何一个？

一个不提及任何动态变量的表达式可以在特化期间求值，而一个不提及任何静态变量的表达式没有什么可特化的，所以我们不动它。其他所有东西都会被拆解。

这条规则纯粹是语法上的，所以它有很多盲点。一个只提及静态变量的表达式会在特化期间运行，即使它有副作用。我们的两个程序都没有副作用，所以我们就这样吧。它的语义泛化留给读者作为练习。

在我们能折叠之前，我们必须求值。

上次，known 把静态表达式交给 eval。然而我们需要摆脱那个 eval，所以我们在我们的迷你 Lisp 中、为我们的迷你 Lisp 写一个求值器：

(defmix ev [prog e names vals] (cond (symbol? e) (List.nth vals (index-of e names)) (not (list? e)) e (= (car e) 'quote) (cadr e) (= (car e) 'if) (if (ev prog (cadr e) names vals) (ev prog (caddr e) names vals) (ev prog (cadddr e) names vals)) (= (car e) 'let) (ev prog (caddr e) (cons (car (cadr e)) names) (cons (ev prog (cadr (cadr e)) names vals) vals)) (empty? (lookup (car e) prog)) (ev-primitive prog e names vals) (memo (ev prog (caddr (lookup (car e) prog)) (cadr (lookup (car e) prog)) (ev-each prog (cdr e) names vals)))))

图 3：求值静态代码。

从语义上讲这很容易，但需要大量的 car 和 cdr，所以我们逐一来看：

我们顺便检查一下 ev-primitive。

(defmix ev-primitive [prog e names vals] (cond

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）