写在前面
《the little schemer》中的第9章，可以换一个开头：故事从一个没有名字的递归开始说起……
鉴于理解的过程蛮苦逼，记录下整个Y combinator 的推导过程，便于下次失忆的时候能迅速回忆。
不过在推导前，先来看看Y combinator 是什么。
Y combinator
wiki上的解释 fixed-point combinator 是这样的：
fix, when applied to an arbitrary function f, yields the same result as f applied to the result of applying fix to f.
细节部分太复杂了。Google 到这篇 Y Combinator的scheme 实现， 发现作者的解释看起来清楚多了，可参阅。
简单而言, 一个公式：
fix f = f (fix f) for all f
对于任意的函数f, fix 接受参数 f，返回(fix f)，将 f 作用于 (fix f)，得到的结果仍为(fix f)。
在scheme中，Y 的定义如下：
(define Y
(lambda (le)
((lambda (f)
(f f))
(lambda (f)
(le (lambda (x)
((f f) x)))))))
或者这样：
(define Y
(lambda (F)
(let ((W (lambda (x)
(F (lambda arg (apply (x x) arg))))))
(W W))))
两者其实是一样的。
来看一个调用Y的实例：
定义一个函数 Fi，用来计算斐波那契数列：【 F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3) 】
(define Fi
(lambda (func-arg)
(lambda (n)
(cond
((zero? (sub1 n)) 1)
((zero? (- n 2)) 1)
(else (+ (func-arg (sub1 n)) (func-arg (- n 2))))))))
然后执行：
((Y Fi) 10)
;Value: 55
((Fi (Y Fi)) 10)
;Value: 55
两次调用的输出结果相同。
推导过程
以书中定义的length函数为例：
先定义一个永远不会有值输出，死循环的函数：eternity
(define eternity
(lambda (x)
(eternity x)))
length的定义如下：
(define length
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
这里，我们定义了一个函数，命名为length，而且在该函数内部调用了它自己。
现在问题来了，如果不允许使用define来定义函数，不给函数命名，如果实现length？
我们先从最简单的 length0 开始，当 list 为空时，(length l)为 0.
先来看 length0:
; length0
;
(lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
调用时， 也很简单：
((lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l)))))) (quote ()))
;Value: 0
由此，继续定义 length<=1 ：
; length<=1
;
(lambda (l)
(cond
((null? l) 0)
(else
(add1 (
(lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
(cdr l))))))
调用 length<=1 ：
((lambda (l)
(cond
((null? l) 0)
(else
(add1 (
(lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
(cdr l)))))) (quote (hello)))
;Value: 1
类推 length<=2：
(lambda (l)
(cond
((null? l) 0)
(else
(add1 (
(lambda (l)
(cond
((null? l) 0)
(else
(add1 (
(lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
(cdr l))))))
(cdr l))))))
调用 length<=2 ：
((lambda (l)
(cond
((null? l) 0)
(else
(add1 (
(lambda (l)
(cond
((null? l) 0)
(else
(add1 (
(lambda (l)
(cond
((null? l) 0)
(else (add1 (eternity (cdr l))))))
(cdr l))))))
(cdr l)))))) (quote (hello scheme)))
;Value: 2
按照这个规律，我们可以一直定义下去，length<=n, n 为无穷大……
但这显然不是一个函数该有的样子，所以我们换一种方式，来重新定义下 length0:
; redefine length0
;
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)
这里重新定义了一个函数，这个函数接受一个参数length，返回结果是一个lambda函数。
上面这段代码，调用了该函数，并将 eternity 作为参数值传递进去。与我们先前定义的 length0 没有区别，仅仅是写法不同而已。
用这种方式，可以类推出 length<=1, length<=2:
; rewrite length<=1 in the same style
;
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))) eternity))
;
; rewrite length<=2 in the same style
;
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))) eternity)))
顺着这个思路，再一次进行抽象提取，重新定义 length0:
; mk-length for length0
;
((lambda (mk-length)
(mk-length eternity))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
这里，是将整个 length 的定义，作为 mk-length 的参数值：
它其实是同我们第二次定义的 length0 是一样的：
只是这里调用了两次，一次将整个 length 的定义，作为 mk-length 的参数值，第二次将 eternity 作为 length 的参数值。
由此可以类推出length<=1, length<=2:
; mk-length for length<=1
;
((lambda (mk-length)
(mk-length
(mk-length eternity)))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
;
; mk-length for length<=2
;
((lambda (mk-length)
(mk-length
(mk-length
(mk-length eternity))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
这里，eternity 扮演的是参数值的角色，它本身是一个函数，我们使用 mk-length 来替换掉 eternity，当然也是可以的，重新看一下替换掉eternity后的 length0 :
; replace eternity with mk-length
;
((lambda (mk-length)
(mk-length mk-length))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
这里，length也不过是一个参数名，自然也是可以换成mk-length的。
; using mk-length instead of length
;
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (mk-length (cdr l))))))))
现在，调用上面这个函数，将eternity作为参数值，我们可以得到 length<=1:
; apply mk-length to get length<=1
;
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l))))))))
这里稍稍有点绕，截个图就明白了：
调用一次试试看：
(((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((mk-length eternity) (cdr l)))))))) (quote (apple)))
;Value: 1
结果无误。
现在，我们再将上面 length<=1定义中 的 eternity 替换成 mk-length:
; replace eternity with mk-length
;
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((mk-length mk-length) (cdr l))))))))
鉴于(f x) 与 (lambda (x) (f x)) 是一样的，所以我们使用((lambda (x) ((mk-length mk-length) x)) (cdr l)) 来替换掉((mk-length mk-length) (cdr l))。
替换后的结果如下：
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 ((lambda (x) ((mk-length mk-length) x)) (cdr l))))))))
再来一次抽取，将(lambda (x) ((mk-length mk-length) x)) 作为参数值提取出来：
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x) ((mk-length mk-length) x)))))
你会发现最初定义length的那段代码已经完整浮现了：
最后一次，将整块length的定义作为参数值，提取出来：
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))
这段代码中，将：
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
作为了le的参数值。
现在，我们移除掉这个参数值，得到如下代码：
(lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))
好了，我们可以撒花🎉啦。
用 f 替换 mk-length，Y combinator 登场：
; Y combinator
;
(define Y
(lambda (le)
((lambda (f)
(f f))
(lambda (f)
(le (lambda (x)
((f f) x)))))))
整个推导过程结束。
另，Peter Krumins 有一篇文章也详细演示了Y combinator的推导过程，可参阅 Deriving the Y-Combinator。
