【专栏】康托尔、哥德尔、图灵——永恒的金色对角线（3）

Y Combinator

让我们暂且搁下但记住绕人的图灵停机问题，走进函数式编程语言的世界，走进由跟图灵机理论等价的lambda算子发展出来的另一个平行的语言世界。让我们来看一看被人们一代一代吟唱着的神奇的Y Combinator。

关于Y Combinator的文章可谓数不胜数，这个由师从希尔伯特的著名逻辑学家Haskell B.Curry（Haskell语言就是以他命名的，而函数式编程语言里面的Curry手法也是以他命名）“发明”出来的组合算子（Haskell是研究组合逻辑(combinatory logic)的）仿佛有种神奇的魔力，它能够算出给定lambda表达式（函数）的不动点。从而使得递归成为可能。事实上，我们待会就会看到，Y Combinator在神奇的表面之下，其实隐藏着深刻的意义，其背后体现的意义，曾经开出过历史上最灿烂的数学之花，所以MIT的计算机科学系将它做成系徽也就不足为奇了。

作者：刘未鹏 出版：电子工业出版社

当然，要了解这个神奇的算子，我们需要一点点lambda算子理论的基础知识，不过别担心，lambda算子理论是我目前见过的最简洁的公理系统，这个系统仅仅由三条非常简单的公理构成，而这三条公理里面我们又只需要关注前两条。

以下小节——lambda calculus——纯粹是为了没有接触过lambda算子理论的读者准备的，并不属于本文重点讨论的东西，然而要讨论Y combinator就必须先了解一下lambda（当然，以编程语言来了解也行，但是你会看到，丘齐最初提出的lambda算子理论才是最最简洁和漂亮的，学起来也最省事。）所以我单独准备了一个小节来介绍它。如果你已经知道，可以跳过这一小节。不知道的读者也可以跳过这一小节去wikipedia上面看，这里的介绍使用了wikipedia上的方式。

lambda calculus

先来看一下lambda表达式的基本语法(BNF)：

<expr> ::= <identifier>

<expr> ::= lambda <identifier-list>. <expr>

<expr> ::= (<expr> <expr>)

前两条语法用于生成lambda表达式（lambda函数），如：

lambda x y. x + y

haskell里面为了简洁起见用“\”来代替希腊字母lambda，它们形状比较相似。故而上面的定义也可以写成：

\ x y. x + y

这是一个匿名的加法函数，它接受两个参数，返回两值相加的结果。当然，这里我们为了方便起见赋予了lambda函数直观的计算意义，而实际上lambda calculus里面一切都只不过是文本替换，有点像C语言的宏。并且这里的“+”我们假设已经是一个具有原子语义的运算符^[1]，此外，为了方便我们使用了中缀表达（按照lambda calculus系统的语法实际上应该写成“(+ x y)”才对——参考第三条语法）。

那么，函数定义出来了，怎么使用呢？最后一条规则就是用来调用一个lambda函数的：

((lambda x y. x + y) 2 3)

以上这一行就是把刚才定义的加法函数运用到2和3上（这个调用语法形式跟命令式语言(imperative language)惯用的调用形式有点区别，后者是“f(x, y)”，而这里是“(f x y)”，不过好在顺序没变:) ）。为了表达简洁一点，我们可以给(lambda x y. x + y)起一个名字，像这样：

let Add = (lambda x y. x + y)

这样我们便可以使用Add来表示该lambda函数了：

(Add 2 3)

不过还是为了方便起见，后面调用的时候一般用“Add(2, 3)”，即我们熟悉的形式。

有了语法规则之后，我们便可以看一看这个语言系统的两条简单至极的公理了：

Alpha转换公理：例如，“lambda x y. x + y”转换为“lambda a b. a + b”。换句话说，函数的参数起什么名字没有关系，可以随意替换，只要函数体里面对参数的使用的地方也同时注意相应替换掉就是了。

Beta转换公理：例如，“(lambda x y. x + y) 2 3”转换为“2 + 3”。这个就更简单了，也就是说，当把一个lambda函数用到参数身上时，只需用实际的参数来替换掉其函数体中的相应变量即可。

就这些。是不是感觉有点太简单了？但事实就是如此，lambda算子系统从根本上其实就这些东西，然而你却能够从这几个简单的规则中推演出神奇无比的Y combinator来。我们这就开始！

【注释】

[1]关于如何在lambdacalculus系统里实现“+”操作符及自然数等等，可参加扩展阅读。

（待续；此文的修订版已收录《暗时间》一书，由电子工业出版社2011年8月出版。作者于2009年7月获得南京大学计算机系硕士学位，现在微软亚洲研究院创新工程中心从事软件研发工程师工作。）