这两天看了下教主关于reinvent Y组合子的PPT，对以前觉得天书一般的Y Combinator有了些理解，于是翻到《The Little Schemer》的第九章，把它的推导看了一遍，这下总算是大概明白了。
Y组合子来自于lambda calculus中对于递归函数的处理。因为lambda calculus中，函数是不允许调用自己的，就像我们不能把自己举起来一样。
用 Scheme的观点来看，Y 就是这样一个操作符，它作用于任何一个 (接受一个函数作为参数的) 函数 F，就会返回一个函数 X。再把 F 作用于这个函数 X，还是得到 X。所以 X 被叫做 F 的不动点(fixed point)。
所以我们常常见到 "(Y F) = (F (Y F))" 这种说法。比如在这里：
…… 为了防止误人子弟，你最好先找本 Lambda Calculus 的书来看 看。Lambda calculas 里的 Y Conbinator 要广泛的多。F 不一定只 接受一个函数作为参数。Fixed point 不但可以是函数，还可以是任何 lambda term。
因为Scheme 是一种实际的语言，跟纯粹的理论还是有一定差距。如果要完全实验lambda calculas, 最好使用一些专用的 lambda 计算器。比如：http://okmij.org/ftp/Computation/lambda-calc.html 就有多种语言实现的 lambda 计算器。
我们从一个简单的例子开始推导。以下是一个阶乘函数的scheme代码。输入正整数n，返回n！。
(define fact ;;定义函数名为fact
(lambda (n) ;;接收一个参数n
(cond ((= n 0) 1) ;;如果n=0，则返回1
(else (* n (fact (- n 1))))))) ;;否则返回n*(fact (n-1))的值
既然factorial函数不能自己调用自己，那递归时的(fact (- n 1))这部分又如何而来呢？想象一下人如果真的要把自己举起来，那怎么办？克隆一个自己把自己举起来？因此我们将fact函数改造一下，增加一个参数，以下我们忽略掉函数名定义，只关注函数体部分：
(lambda (fact) ;;接受一个参数fact
(lambda (n) ;;再接收一个参数n
(cond ((= n 0) 1)
(else (* n (fact (- n 1)))))))
然后把fact函数本身作为增加的那个参数调用自己。
观察到代码中有两部分是完全相同的，我们何不把这部分提取出来呢？同样，增加一个参数，把提取出的部分作为输入，得到：
划线部分的fact fact这样的结构是否看起来有些不“和谐”呢？提取出来：
注意到上图中黑色方框部分了没？是不是就是我们第一步改造后的fact函数呢？再次提取出来：
好了，取出最上面的一部分就是我们想要的Y组合子了。因为lambda(mk-fact)和lambda(fact)这两个函数的参数不会相互作用，所以变量可以用同一个名称，修改一下变量名：
(lambda (h)
((lambda (f) (f f))
(lambda (f) (h (f f)))))
看起来似乎大功告成了，不过还差最后一步。我们这里得到的Y组合子只有在call-by-need或者call-by-name这样的惰性求值时才能使用,而我们常用的语言是call-by-value的，这样(f f)会导致无限递归，所以略微修改一下，变成(lambda (x)((f f)x)，让它可以返回一个函数：
(define Y
(lambda (h)
((lambda (f) (f f))
(lambda (f) (h(lambda (x)((f f)x)))))))
好了，我们来测试一下：
怎么样，是不是很神奇呢？
那么Y-Combinator到底是如何作用的呢？再来看看我们的factorial函数，它分为两部分：
(lambda (fact)
(lambda (n)
(cond ((= n 0) 1) ;;判断边界，负责终止函数
(else (* n (fact (- n 1))))))) ;;延续部分，负责继续递归
对于我们的factorial函数来说，在延续部分，只需要我们递归的次数多到足够到达边界条件，那么我们就可以得到所希望的结果。试试看？
输入6个以上factorial函数时，此时最后的(lambda (x)(* 100 x))函数只是为了满足最内层的factorial函数的输入，并不会参与计算。
而当factorial函数的个数少于6个时就会调用(lambda (x)(* 100 x))得到错误结果。
Y-Combinator就是用来制造无数个(factorial(…))这样的嵌套结构，这样无论输入的n有多大，都可以保证程序的正确性。I
