从自输出程序到 Y 组合子

发表于 2017/08/16

有一类程序可以打印出自己的源代码,这种程序叫做自输出程序,也叫做 Quine。本文将向你展示 Quine 和 Y 组合子之间的关系。

本文的撰写受到了这篇文章这篇文章的启发。

如何写一个自输出程序?

下面将使用 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))

评论

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