如何写一个自输出程序？

下面将使用 C 语言介绍 Quine 的撰写方法。首先不妨从一个空荡荡的程序开始。

int main() {
  return 0;
}

还行。这时候很自然地想把这段代码塞到一个 printf 里面去，但是没这么简单——程序本身已经不是空程序了。主要问题是，你不能简单地把代码给打印出来，因为要打印的内容必须出现在要打印的内容之中。听起来有点像递归，不过没那么复杂。

a = "%s";
printf(a, a); // 将打印出「%s」

这里我们成功地「递归」了 %s，现在把这个想法应用到整个程序上：

char program[]="char program[]=\"%s\";int main(){printf(program,program);return 0;}";int main(){printf(program,program);return 0;}

这里我们前进了一大步，但这段程序并不正确，因为最后打印出来的代码里没有 \"，而如果你要打印出来 \\"，那么代码里面就必须出现 \\\\"，这样就无穷无尽了。不过使用 ASCII 码即可轻松绕过这个问题：

char program[]="char program[]=%c%s%c;int main(){printf(program,34,program,34);return 0;}";int main(){printf(program,34,program,34);return 0;}

这就是最终的结果了。不妨试试？

λ 演算

Alonzo Church 提出的 λ 演算是计算机科学上最重要最精彩的成果，它催生了函数式编程语言、CPS 变换等非常重要的理论和工具，但同时它的思想也很简单且易于理解。本文的重点不是 λ 演算，所以内容不会非常严格，你只能了解到大体思想。如果你想体会为这些乱七八糟的符号挠破脑袋的感受，不妨去找一本相关著作。下面我们来看看 λ 演算到底是什么东西。

在「λ 演算」这样一个略显滑稽的名字背后，思想非常简单，即计算中的一切都被统一为函数应用。λ 演算中，每个函数都被表达为一个 λ 项，如：λx.x就是匿名的f(x)=x。在.和λ之间是函数的自变量，在.之后是函数体，你可以在函数体中对自变量做任何事，就如同f(x)=<函数体>一样。

λ 演算中，函数应用写作类似 (λx.x) 1 的格式，进行应用操作只需把函数体中所有的 x 替换成 1 并丢掉 λ、.和夹在它们之间的自变量。使用这样的规则，(λx.x+x) 1 首先规约为 1+1，计算可得结果 2。应用规则被称作 β-规约。

显然，λx.x 和 λy.y 其实没什么不同，你可以任意修改函数的自变量的名字，这个规则叫做 α-转换。

另一个聪明的思想是你可以给函数起名字。比方说 id := λx.x，然后 id 1 就等价于 (λx.x) 1。现在有个问题：函数的函数又怎么样呢？如果没有函数的函数才叫奇怪，因为上面的规则并没有限制这种情况，我们只是对 λ 项进行符号演算而已！猜猜看 λf.(λx.f x) id 是什么意思？使用我们在上文学习到的规则，λf.(λx.f x) id = λx.id x = λx.x = id。函数 λf.(λx.f x) 接受一个函数，并给出另一个函数，这与数学上的函数有所区别，所以我们把能接受函数为参数的函数叫做高阶函数。

Y 组合子

λ 演算看上去有点……太简单了？好像什么都干不了啊！请暂停 3 秒想想怎么使用 λ 演算算阶乘。时间到！是的，这一点也不显然！不过，可以先想想不用 λ 演算我们是怎么算阶乘的？比方说一个递归？这或许是最简单的方式：

int fact(int n) {
  if (n == 0) return 1;
  return n * fact(n-1);
}

这就是一个典型的递归函数。我承认我耍了点花招，因为我们还没提到如何在 λ 演算里表达数字和 if then else 逻辑，不过这些话题比较无趣（虽然首次接触时会觉得很开眼界），本文不会讲解这些东西，你只要把它们当作理所当然的就好。本文的重点是：如何在 λ 演算中写一个递归函数？记住：λ 项没有名字！不过，先给 λ 项起个名字也许能起一点作用。这样写阶乘函数如何：fact := (λn. if n = 0 then 1 else n * (fact n-1))？很遗憾，不行。λ 演算并不是一个编程语言，允许你在定义符号前就声明它。我们也许可以把这个函数展开一下：fact := (λn. if n = 0 then 1 else n * (if n-1 = 0 then 1 else n-1 * (fact n-2))) = ...。

现在看来，这个问题和前文所述的自输出程序是一模一样的，你不得不把 fact 的代码放到 fact 的代码里面！那么我们之前所用的思想在这里还能用吗？我们刚才到底做了什么？我们把代码放进了一个变量，然后使用规则，使得值自己能生成更多值……这里，大概可以先引进一个变量，然后假装我们已经定义了fact。

g := λfact. λn. if n = 0 then 1 else n * (fact n-1)

这又是一个进步。为什么？因为 fact 成功出现在函数体内部了！现在的问题是，如何把 g 变成 fact？从上面的展开步骤来看，g (g (g ...)) 就是我们需要的，这暗示我们去构造一个函数，使得 f g = g (f g), for all g。幸运的是，确实存在这样一个函数，它就是 Y 组合子，又称不动点组合子。

Y := λf. (λx. f (x x)) (λx. f (x x))

不太显然地看出来，fact := Y g。如果你怀疑这个结果，请自己尝试。规约过程如下：

Y g = (λx. g (x x)) (λx. g (x x))
    = g ((λx. g (x x)) (λx. g (x x)))         = g (Y g)
    = g (g ((λx. g (x x)) (λx. g (x x))))     = g (g (Y g))
    = g (g (g ((λx. g (x x)) (λx. g (x x))))) = g (g (g (Y g)))

现在我们可以自信地宣称 fact := Y g。实际上，使用 Y 组合子，我们可以在 λ 演算中表达任意递归函数。

结论

（2017年8月26日更新）还记得 Y 组合子的另一个名字吗？它也叫不动点组合子。这是什么意思呢？先说不动点，如果对于一个函数存在 x 满足 f x = x，那么 x 就是 f 的不动点。现在我们把一个程序看作把程序映射到输出的函数，那么由于 Y 的存在，可以断言一定可以写出 Quine。根据 Church-Turing 论题，一切图灵完备的语言都可以写出 Quine！这部分内容有误，请看下面的评论。（我之前完全没想到 Quine 的可能性问题，后来在某 Scheme 群中讨论起了 Scheme 怎么写 Quine 的问题，于是才想起来还有这样的问题。后来去读维基百科才发现这已经是现成的结论了，维基百科上指出这是 Kleene 递归定理的结果。）

提出和解决自指问题一直都很有趣，它也许能带来新发现、新思想，它也有可能引起矛盾，使得理论轰然崩塌。我们现在可以看到，λ 演算中递归问题和自输出程序的编写在精神上是一致的：把自己放到自己里面去。两者的解决方法也很相像：要让 A 出现在 A 里面，先假装 A 已经存在，然后用 A 自己产生更多的 A，而这是底层规则所允许的。写 Quine 时，这个规则是 printf，而在 Y 组合子中，这个规则是 β-规约。

但是问题并没有结束。如果我们把编译+运行看作 λ 演算中的规约，显然这是个死循环。那么回头看看 fact 函数，你能断言这个递归一定会终止吗？……

延伸阅读

本文只是写来好玩的介绍性的文章。这里有一些资源供你深入了解。注意，为了 Y 组合子形式上的简便，我使用了 call-by-name，其 call-by-value 形式是 Y := λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))。

Wikipedia Quine
Types and Programming Languages by Benjamin C. Pierce. 这本书清晰讲解了 λ 演算，并使用 OCaml 语言将其在电脑上实现。

@monsoon 向我指出：Y 的作用是把一个函数 f 丢进去返回一个函数 Y f，这个函数本身是 f 的不动点，而 Quine 本身已经是（执行环境的）不动点了，这样我的原文说法就有些问题。我一开始的想法是：任何一个图灵完备的语言都可以表达递归计算，这蕴含着 Y，而 Y 的思想与 Quine 是一致的，这就蕴含了 Quine 是可能的。但是这个说法太 naive 了，根本不算证明。后来看到 Wikipedia 关于「执行环境不动点」的说法，就（惨剧的开始）自己乱搞了起来，而没有细心体会前人的智慧，甚至没仔细学习 Kleene's Recursion Theorems，犯了多个错误。这里直接引述 Wikipedia 的说法：「当执行环境被看作将程序转换为输出的函数时，Quine 是执行环境的不动点。」