最近读了The Little Schemer，里面有一章专门讲Y combinator。可是看完之后仍然觉得云里雾里的：只明白了Y Combinator是如何定义递归函数的，却不清楚Y combinator最初是怎么被想出来的。又在网上查了一些资料，心里有了个大概的眉目，总结在这里，算是对这段学习的一个交代吧。
Y combinator所要解决的问题，是如何在类似lambda演算的形式化系统中里面定义递归函数。lambda演算只有三种基本要素：变量、函数应用、函数抽象。尤其值得注意的是，与我们所熟悉的绝大多数编程语言不同，lambda演算中不能直接给变量赋值，而只能通过上述要素中的第二种——函数应用——来将形参与实参相绑定。可是，所谓递归函数，例如叫做f（暂时假定我们又有了绑定变量的能力，并将这个函数与变量名f相绑定），就是在函数体里面通过f这个变量名来调用该函数自身。如果我们丧失了这种绑定变量的能力，还怎么实现递归呢？答案（之一）就是Y combinator。下面就用一个Scheme的例子来演示Y combinator的一种推导方式。
Scheme中的length
Scheme中有一个内置函数length，能求list的长度。如果我们自己来写的话，一种可能的实现是这样：
(define len
(lambda (l)
(cond [(null? l) 0]
[else (add1 (len (cdr l)))])))
现在假如我们没有define了，还能不能定义一个求list长度的函数呢？第一反应是能，因为(define name value)所做的无非就是把value绑定到name。即便现在没了name，只要有value不是照样可以吗？所以我们可以把那部分value单独写出来：
(lambda (l)
(cond [(null? 1) 0]
[else (add1 (len (cdr l)))]))
可是现在问题来了：这个表达式里面的len指的是谁呢？这就涉及到了递归的核心。对于一个非递归函数，这种“只取value”的做法没有问题。可是递归就要继续调用一个函数，而且那个函数不是别人，就是这个函数自身啊！然而现在没有了保存自身的那个变量，还怎么继续呢？
把自身传进来
最直接的想法是，既然要用到一个函数（自身），那就把它当作参数传进来好啦。于是就有了
(lambda (self l)
(cond [(null? l) 0]
[else (add1 (self (cdr l)))]))
为了能够方便后面的分析，我们不妨把这个函数写成curried的形式，然后给它起名叫做“参数化的length”。写出来就是
(lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else (add1 (self (cdr l)))])))
这种思想是好的，但其实无论是否curried，上面的实现都存在一个问题。以curried版本为例，一共4行代码，定义了一个匿名函数。这个匿名函数依次需要两个参数。第二个参数l不必多说，是我们想求长度的list。第一个参数self目的是想把这个匿名函数自身当作传递进来。可是既然self想指向的就是这4行的匿名函数自身，那self和这个匿名函数就应该以相同的方式被调用。那么匿名函数是如何被调用的呢？本段前面刚刚说过，“依次需要两个参数……”。然而第4行里面，self只有一个参数。匿名函数和self的调用方式不一样，这显然行不通。所以我们修改self的调用，给它加多一个参数，于是curried版本现在就变成了
(lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else (add1 ((self self) (cdr l)))])))
现在匿名函数和self的函数signature一致了，我们的无define版求list长度的函数也就（几乎）写好了。关键的问题来了：怎么使用它呢？嗯……要（依次)传两个参数，第一个是这个函数自己，第二个是想要求长度的list。等一下，什么叫做“传这个函数自己做参数”？答案简单得令人惊讶——没有绑定变量名不要紧，把这个函数复制、粘贴一份到参数的位置就可以了。所以，要求'(a b c)的长度，只需要
(((lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else (add1 ((self self) (cdr l)))])))
(lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else (add1 ((self self) (cdr l)))]))))
'(a b c))
复制到解释器里试一下。怎么样？答案是不是3呢？我们当然也可以用它求'(a)、'(a b)等的长度。换言之，如果把这最后一个参数拿走，去掉最外面这层函数应用，我们就有了一个可以工作的求list长度的函数：
((lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else (add1 ((self self) (cdr l)))])))
(lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else (add1 ((self self) (cdr l)))]))))
大功告成！回过头来看，其实我们的思路非常简单、清晰。
- 所谓递归，就是调用自身。
- 没有自身，那就把它传进来。
- 如何传？形参随便取一个变量名（比如
self）就行。实参呢？把这个函数复制粘贴一遍就可以了。
从length到Y Combinator
到此为止，我们已经成功地在没有define的语言里实现了一个递归函数length。但仔细想想，这种策略其实不仅适用于length，也可用来实现其他的递归函数——无非就是传多一个参数，复制粘贴一遍自己嘛。所以，我们已经一劳永逸地解决了所有递归函数了！
话虽如此，不能否认的是，这种方式定义的递归函数使用起来很不方便。以我们的length为例（姑且称为length吧，虽然它其实没有被绑定到任何变量名）。首先，为了定义它，程序员必须将函数体复制粘贴一遍，造成了大量的重复代码。其次，要想用length求长度，它必须接受两个参数，第一个是一个函数（复制粘贴的自身），第二个是要求长度的list；但从语义上来说，length理应只接受一个list，其他所有与实现相关的复杂性都应该被封装起来。
先来解决第一个问题。宏观地从形式上看，用上面的函数是类似(f f)的一个函数应用，只不过这里的f比较复杂，需要替换为一个长长的lambda表达式罢了。由于出现了两次f，也有了两个长长的lambda表达式。能不能只写一次lambda表达式呢？可以！只要把(f f)这个模式抽象出去，成为一个新的函数就可以了：
((lambda (g)
(g g))
f)
;; where f =
;; (lambda (self)
;; (lambda (l)
;; (cond [(null? l) 0]
;; [else (add1 ((self self) (cdr l)))])))
注意，现在的实现里面虽然仍然有(g g)这种重复，但这两个g都是形参，真正的实参是f。也就是说，f才是那个长长的lambda表达式。如果我们把f替换掉，得到的是：
((lambda (g)
(g g))
(lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else (add1 ((self self) (cdr l)))]))))
怎么样，和之前的版本相比，是不是只有一个长lambda表达式，其他地方简短了许多？试试看，它是不是也能正常工作？
再来处理第二个问题。应该讲，由于有了刚刚的一层抽象，这“传两个参数”的问题似乎已经不是什么大问题了。我们完全可以把上面6行代码整体当作一个函数，它只接受一个参数，就是想求长度的list。但是，在函数体的第6行，递归调用的部分仍然有(self self)这样让人恼火的实现。能不能把它也干掉呢？
我们可以照猫画虎，对比着刚刚的经验来做。上面是(f f)形的表达式，其中f是长长的lambda；我们把f抽象出去做实参，从而只需要写一次f。这一回还是(f f)形的表达式，但这次我们想整个地把(f f)都抽象出去做实参，从而把递归调用的部分化简为一个简单的形参变量，比如h。一种可能的做法是：
;; 方法1
((lambda (g)
(g g))
(lambda (self)
(lambda (l)
(cond [(null? l) 0]
[else ((lambda (h) (add1 (h (cdr l))))
(self self))]))))
这种实现里面，抽象出的lambda只在else分支。或者我们也可以把它往外移一些，放在整个cond之外，变成
;; 方法2
((lambda (g)
(g g))
(lambda (self)
(lambda (l)
((lambda (h)
(cond [(null? l) 0]
[else (add1 (h (cdr l)))]))
(self self)))))
究竟是方法1还是方法2更好一些呢？一般来说，似乎方法1更合适，因为在方法1里面，h这个变量名起作用的的scope相对小一些，所以对其他部分的影响也小一些。不过方法2也有自己的优势：在这种实现里面，作为实参的(self self)不依赖于(null? l)的运行结果。在某种程度上，这也是耦合度的一种降低。
其实，方法1和方法2都还算得上是“温和”。对于方法1，我们更进一步设计一个方法0，把lambda抽象从add1外面移到里面，h的scope就更加缩小了。对于方法2，我们也能把lambda继续外移。考虑到实参(self self)连l这个变量名都用不着，lambda可以移出l的绑定，变成下面的方法3：
;; 方法3
((lambda (g)
(g g))
(lambda (self)
((lambda (h)
(lambda (l)
(cond [(null? l) 0]
[else (add1 (h (cdr l)))])))
(self self))))
这段代码还有点小问题，如果直接复制到解释器里，会陷入无限的递归无法退出。不过我们待会儿再来解决这个问题。先仔细看看方法3，有没有觉得有些部分似曾相识？没错，中间几行代码除了参数名不同，跟前面提到的“参数化的length”一模一样！这启发我们，会不会这几行代码就已经包含了实现length需要的所有信息？如果把它们抽象出去，剩下来的部分会不会是一个common pattern，可以用来处理所有的递归函数？为了验证这个想法，我们需要先解决前面提到的无限递归的问题。
为什么从方法2到方法3，会出现无限递归的问题呢？直观上看，两者都需要执行函数应用(g g)，形参g都会被替换为(lambda (self) ...。为了简洁，可以先只替换第一个g，那么这个函数应用就可以写成类似((lambda (self) ...) g)的形式。显然，为了完成函数应用，需要把...里面的self进一步替换成g。也正是在这儿，方法2和方法3出现了分歧。
方法2中，把self替换成g之后，函数应用的结果是一个lambda，即(lambda (l) ...，这意味着求值到此返回一个closure就结束了，被lambda包起来的运算会被延迟。而到了方法3，函数应用的结果是((lambda (h) ...。注意，开头是两个括号，换言之，是一层新的函数应用，其中函数部分是(lambda (h) ...)，实参部分是(self self)。既然是应用，求值到此并没有结束，只能继续计算。先看实参部分。前面说了，self要被替换成g，所以实参部分的(self self)其实又是一个(g g)，这相当于回到了上一段。如此往复，无限递归就产生了。
怎么解决这个问题呢？我们注意到，用lambda包起来的运算会被延迟，而(self self)的求值结果又恰好是一个函数。这启发我们利用lambda演算里的η展开，将(self self)转化为一个lambda。具体而言，就是等价地写为(lambda (x) ((self self) x))。从功能上讲，它跟(self self)是一样的，都是给它一个参数x，它就返回将(self self)作用于x的结果。但在求值顺序上，只要不真的给出这个x让它求结果，那么包在lambda里面的(self self)就永远不会被求值。所以，修正过的方法3就变成了：
((lambda (g)
(g g))
(lambda (self)
((lambda (h)
(lambda (l)
(cond [(null? l) 0]
[else (add1 (h (cdr l)))])))
(lambda (x) ((self self) x)))))
然后就可以继续刚刚的想法了，把“参数化的length”那部分也变成一个参数抽象出去。刚刚已经使用过了f、g、h，再往后该排到i，但是i貌似不像个函数，所以这一次我们折回去用f作形参:P
((lambda (f)
((lambda (g)
(g g))
(lambda (self)
(f (lambda (x) ((self self) x))))))
(lambda (h)
(lambda (l)
(cond [(null? l) 0]
[else (add1 (h (cdr l)))]))))
现在那个common pattern已经很明显了，就是
(lambda (f)
((lambda (g)
(g g))
(lambda (self)
(f (lambda (x) ((self self) x))))))
不妨把self换成h，稍稍整理下：
(lambda (f)
((lambda (g) (g g))
(lambda (h) (f (lambda (x) ((h h) x))))))
这就是传说中的Y combinator了。我们把它作用在参数化的length身上，得到的就是真正的length；把它作用在另外一个参数化的递归函数例如max-in-list-parameterized身上，就能得到真正的max-in-list。不信你试试:)
附录
用max-in-list验证Y
先尝试写出来递归的版本。为了防止命名的混淆，加个前缀，叫做recursive-max-in-list。
(define recursive-max-in-list
(lambda (l)
(if (= 1 (length l))
(car l)
(max (car l) (recursive-max-in-list (cdr l))))))
把recursive-max-in-list改成参数传进去，就可以得到参数化的版本。
(lambda (self)
(lambda (l)
(if (= 1 (length l))
(car l)
(max (car l) (self (cdr l))))))
定义有5行，有点长，来回复制粘贴太麻烦，所以干脆给起个名字max-in-list-parameterized。
(define max-in-list-parameterized
(lambda (self)
(lambda (l)
(if (= 1 (length l))
(car l)
(max (car l) (self (cdr l)))))))
同样，给Y combinator也起个名字，叫做Y。
(define Y
(lambda (f)
((lambda (g) (g g))
(lambda (h) (f (lambda (x) ((h h) x)))))))
好了，万事俱备，现在可以定义max-in-list了。
(define max-in-list (Y max-in-list-parameterized))
实验一下，看看max-in-list能不能用？
> (max-in-list '(1 5 8 3 4))
8
Yeah~！！
简化Y
上面的Y combinator虽然已经能用了，但是跟多数教科书、维基百科里面看到的形式还有一点差别。两者本质上是等价的，我们不妨来化简一下看看。
为了摆脱无限递归，刚刚我们做了一次η展开，体现Y当中，就是下面标注的部分。
(lambda (f)
((lambda (g) (g g))
(lambda (h) (f (lambda (x) ((h h) x))))))
^^^^^^^^^^^^^^^^^^^^^
用η规约化简回去，就得到了
(lambda (f)
((lambda (g) (g g))
(lambda (h) (f (h h)))))
注意，这么做是有代价的。一旦应用到参数化的length或者max-in-list上，会再次陷入无限递归。这是由Scheme的call-by-value求值规则决定的。不过为了得到经典的Y combinator形式，我们暂且忽略它。下面把h换个变量名x，得到：
(lambda (f)
((lambda (g) (g g))
(lambda (x) (f (x x)))))
然后把和g有关的那次函数应用展开（事实上这又是我们前面一次变形的逆操作）。
(lambda (f)
((lambda (x) (f (x x)))
(lambda (x) (f (x x)))))
当当当~！正牌Y combinator闪亮登场！！