最近在看《暗时间》，书中有Y组合子的推导过程，初看时很难理解，这里记录一下加深记忆，我们使用Scheme语言的语法。
我们知道Scheme中可以这样定义递归函数
(= n 0)1(* n (func (- n 1)))))
但是我们知道define这个函数只起到了一个语法糖的效果，再对应lambda表达式还未知的时候是不能使用这个函数。
接下来我们只通过使用lambda表达式来推导出递归函数。
我们先做一下尝试
(= n 0)1(* n (<func-name> (- n 1)))))
注意到，我们的func-name处需要填入的这个函数的名字，但是我们现在并不知道这个函数的名字，为了在函数体中获得这个函数，我们增加一个参数（把这个需要的函数作为参数传入自身中）
(= n 0)1(* n (self self (- n 1)))))
现在我们得到的这个函数已经可以产生递归了，为了看起来更加清晰，我们把这个函数体缩写成单个字母P表示
(P P 5)
可以得到值120。
接下来我们继续引入一个概念叫做“不动点原理“，我们先回到存在func-name的第二段代码中，假设存在这样一个完美的函数（即不需要把自身作为参数传入），我们把他记为perfect。
并修改P为
(= n 0)1(* n (self (- n 1)))))
此时注意下面两个式子
(P perfect 5)(P P 5)
显然第一个调用是可以求出值，而第二个调用是存在问题的，因为展开后的第二此调用P只传入了一个参数4。 接下来我们修改一下第一个调用
(P perfect)
想一想这是什么东西？一个还需要一个参数的函数！正规一点说就是”函数的部分求值”。 为了更清楚的看看这个新函数是怎么回事，我们把他展开来看看：
(= n 0)1(* n (perfect (- n 1)))))
这正是我们在第一段代码递归中的函数体。 因此我们可以得到这样一个等式 (P perfect) == perfect 现在不动点这个概念就可以下定义了，此时perfect称为函数P的不动点。
好了，我们现在回到一开始，记住perfect这个完美的递归函数是我们假设出来的，接下来我们要做的就是在已经知道函数P的情况下找到这个perfect，我们引入一个函数叫Y，Y函数有这样一个作用：
(Y P) == perfect
即把函数P作为Y的参数后可以得到对应于P的完美的递归函数perfect。
为了得到这样的函数Y，我们看下面的这个函数magic：
self)))
我们调用
(magic magic)
就变成了
(P (magic magic))
所以(magic magic)就是P的不动点。 注意我们的目的仍然是构造Y，Y的功能是把magic函数体中的P变成参数，并返回(magic magic)
magic))
展开来也就是
))(P (self self))))
好了，，上面这个东西就是我们的函数Y，这样传入任何类似P的“假冒的递归“函数时，都可以得到对应完美的递归函数了。
天才是百分之一的灵感加上百分之九十九的努力
