Y组合子
Y组合子（Y Combinator）是对匿名函数进行递归的通用抽象方法（或函数）。
计算模型的经典描述有两种：图灵机和λ演算（λ-calculus）。简单来说，图灵机是对用于“计算的机器”的抽象，而λ演算是对“计算本身”的抽象（是一种”最小“的编程语言）。
λ演算的表达式（expr）只有四种形式：
(1) 常量： 数字（如1、2），或基本运算函数的符号（如+、-）；
(2) 变量： 可代换为其它名字或值而不改变表达式的求值结果(如x、y）；
(3) 函数： 形如λx.x+1的表达式，等价于数学的f(x)=x+1，但所有函数都没有名字;
(4) 求值： 比如(λx.x+1)3的求值结果是4。
用Lisp语言或其方言来描述λ演算是非常方便的。如上面的表达式λx.x+1等价于以下代码：
(lambda (x) ;一个单参匿名函数，参数为x
(+ x 1)) ;函数体为 x+1
(λx.x+1)3的求值过程等价于以下Lisp求值过程：( (lambda (x) (+ x 1)) 3) ; 对匿名函数(lambda (x) (+ x 1))在x=3上求值
; 取出匿名函数的函数体(+ x 1)，
; 然后用3替代x
(+ 3 1) ; 此表达式求值结果为4
(define factorial ;定义一个叫factorial的名字
(lambda (x) ;它绑定到一个 单参x匿名函数
(if (= x 1) ; 函数体为： 如果x=1
1 ; 返回1
(* x (factorial (- x 1)))))) ; 否则返回x * factorial(x-1)
define语句把匿名函数和factorial这个符号绑定（允许函数有名字），函数内部才允许(* x (factorial (- x 1))的表达式存在。
那么问题来了，世界之初，天地混沌如鸡子，没有define语句。如何只用纯匿名函数进行递归？
1. 双重套娃¶
俄罗斯套娃
f，g这样的名字，它们可直接脑补为一个形如(lambda (x) <body>)的匿名函数。在没有define语句时，如果要在f的内部调用g，则g需作为参数在f内体现。f的形式应该如下：(lambda (g) ;
(lambda (x) ; 出现了，f是一个套娃函数
<body>)) ; (f g)会生成新函数(lambda (x) (dosomething g))
factorial套娃，可以得到以下的匿名函数，我们叫他a：
;a形式的阶乘套娃
(lambda (f) ;一个匿名函数，其单参f是
(lambda (x) ; 另外一个单参x的匿名函数
(if (= x 1) ; ...这里无需解释
1 ;
(* x (f (- x 1)))))) ; 注意(f ...) 这个调用是否成立
(a 1)来求1的阶乘，因为a的输入必须是一个函数。对任意函数any-func，(a any-func)的求值结果应该如下：(lambda (x)
(if (= x 1)
1
(* x (any-func (- x 1)))))
((a any-func) 1)。不妨直接用a代替any-func。((a a) 1)的值为1，其求值过程如下：((a a) 1) ;我们把第一个a写回lambda形式
;=>
(lambda (x) ;对(a a)求值会返回一个无穷套娃的函数
(if (= x 1) ;
1 ;
(* x (a (- x 1))))) ; 这里的(a (- x 1))可以无穷无尽的替换下去
;=>
(if (= 1 1) ;对上面的函数体中把x=1代入后
1 ; 只会对True分支执行： 返回1
(* x (a (- x 1)))) ;注意：这个分支不会执行，所以无穷套娃也没问题
;=>
1 ;((a a) 1) = 1
;实际上整个求值表达式写出来是这样的，
;没有a语句，只有匿名函数,它的求值结果是1，现在知道为什么我们暂时需要它的名字为a了吧：）
(((lambda (f)
(lambda (x)
(if (= x 1)
1
(* x (f (- x 1)))))) ;不要被括号吓倒，无非是拷贝粘贴的功夫
(lambda (f)
(lambda (x)
(if (= x 1)
1
(* x (f (- x 1)))))))
1)
((a a) 2)求值会出错。以下代换揭示了出错的原因：((a a) 2) ;参考上面的替换过程，得到
;=>
(if (= 2 1) ;对上面的函数体中把x=2代入后
1 ; 忽略True分支
(* 2 (a (- 2 1)))) ; 展开这个无穷套娃函数
;=>
(* 2 ;
(a 1)) ;这行会出错！！！a的参数不能是数值
(if ...)的False分支采用((a a) some-value)的调用形式才能处理x大于1的情况。因此，需对a进行改动得到一个新的匿名函数(不妨称其为b)：;b形式的套娃函数
(lambda (f) ;
(lambda (x) ;
(if (= x 1) ;
1 ;
(* x ((f f) (- x 1)))))) ;b和a仅在这里不同，把f改成了(f f)
((b b) 3)是否正确，展开过程如下：
(lambda (x) ;对(b b)求值会返回类似于(a a)
(if (= x 1) ;的无穷套娃
1 ;
(* x ((b b) (- x 1))))) ;仅最后一行不同
;=>
(if (= 3 1) ;对((b b) 3)求值
1 ;
(* 3 ((b b) (- 3 1))))) ;仅执行False分支
;=>
(* 3 ;
((b b) 2)) ;显然((b b) 2)的展开一定是
;(* 2 ((b b) 1))
;=>
(* 3 ;出现了，阶乘
(* 2 1)) ;((b b) 1)肯定是1
(b b)即：((lambda (f) ;恩，外部是个关于b的双重套娃
(lambda (x) ;套的两个娃的每个娃都是关于 f和x的双重套娃
(if (= x 1) ;套娃套着套娃
1 ;就问你怕不怕
(* x ((f f) (- x 1))))))
(lambda (f)
(lambda (x)
(if (= x 1)
1
(* x ((f f) (- x 1)))))))
2. 抽象出Y组合子¶
我们之前进行了以下两步实现了匿名函数递归：
;1. 把函数当作参数仿照define的过程改写
((lambda (f) ;首先将普通递归函数套个娃
(lambda (x) ;
... (... (f new-x)))) ; 匿名的a
;2. 把递归部分的(f ...)改写为((f f) ...)
((lambda (f) ;
(lambda (x) ;
... (... ((f f) new-x)) ;把a函数体的f修改为(f f)得到b
;3. 对b进行套娃
((b b) x)
a形式的匿名函数保留了递归的词法形式但无法直接递归调用。如果存在某个通用过程Y，它接受一个a形式的匿名函数，自动转换为(b b)的形式，这样的通用函数被称为Y组合子。
小贴士： 根据Y组合子的定义，它一定满足(Y a)=(b b)。
2.1 由a生成b，继续套娃¶
首先，我们必须设计一个函数p满足(p a)=b。a和b的两种通用形式分别如下（只考虑递归部分，不考虑终止条件）：
;形式a
(lambda (f)
(lambda (x)
(do-something (f new-x)))
;形式b
(lambda (g)
(lambda (x)
(do-something ((g g) new-x))))
c的(a c)求值会得到：(lambda (x)
(do-something (c new-x)))
c凑成满足(c new-x)=((g g) new-x)的形式，则c必然可以写为：(lambda (y) ;c的参数是一个数值y
((g g) y)) ;需要一个外部传入的函数g作为参数，暂时我们不管它
;对(c new-x)的求值即为
((g g) new-x) ;满足c=(g g)=一个关于数值y的单参函数
c代入上面的(a c)求值，可以得到：
(lambda (x)
(do-something ((g g) new-x))) ;出现了b的函数体部分
g即可以得到b的表达式：;没错，这就是b，形式为(lambda (g) (a c))
(lambda (g)
(lambda (x)
(do-something ((g g) new-x))))
(p a)求值，它必须满足(p a)=(lambda (g) (a c))：
(lambda (g)
(a c))
;把c的完整形式写出来，(p a)应该是这样=>
(lambda (g)
(a (lambda (y)
((g g) y))))
a作为参数f传入（继续套娃），则p可以写为：
(lambda (f)
(lambda (g)
(f (lambda (y)
((g g) y))
;它满足(p a)=(lambda (g) (a c))=b
a形式匿名函数，(p a)的求值过程如下：((lambda (f) ;
(lambda (g) ;
(f (lambda (y) ;这里是p函数
((g g) y))))) ;
a) ;
;=>
(lambda (g) ;
(a c)) ;暂时把上面f后面的函数写为c
;=>
(lambda (g)
((lambda (f) ;写出a的完整形式
(lambda (x)
(if (= x 1)
1
(* x (f (- x 1))))))
c))
;=>
(lambda (g)
(lambda (x)
(if (= x 1)
1
(* x (c (- x 1))))))
;=>
(lambda (g) ;得到了b的形式
(lambda (x)
(if (= x 1)
1
(* x ((g g) (- x 1))))))
;没错，你得到了(p a)=b
2.2 由p生成Y，再次套娃¶
由于b=(p a)，(Y a)=(b b)=((p a) (p a))，则Y可表达为：
(lambda (a)
(b b)))
;(b b)写为((lambda (f) (f f) b) =>
(lambda (a)
((lambda (f) (f f))
(p a))) ;b替换为(p a)
;b写为(lambda (g) (a c)) =>
(lambda (a)
((lambda (f) (f f))
(lambda (g) (a c))))
;写出c的完整形式 =>
(lambda (a)
((lambda (f) (f f))
(lambda (g)
(a (lambda (y)
((g g) y))))))
;没错，啊，这个人就是娘，啊，这个人就是妈。哦不是，这是Y-combinator
a形式单参匿名函数进行递归了，其调用方式为((Y a) x)，我们来试一下阶乘，看看全部展开是个什么东西。
假设a-fact是一种a形式的阶乘函数，5的阶乘可以表示为((Y a-fact) 5)，其完整形式如下：((Y a-fact) 5) ;来吧，求5的阶乘
;写出Y的完整形式 =>
(((lambda (a)
((lambda (f) (f f)) ;没错，这么一大陀就是Y
(lambda (g)
(a (lambda (y) ;
((g g) y))))))
a-fact) ;a-fact要传入Y
5) ;5要传入(Y a)
;写出参数a-fact的完整形式 =>
(((lambda (a) ;
((lambda (f) (f f)) ;这里是Y组合子
(lambda (g)
(a (lambda (y)
((g g) y))))))
(lambda (f) ;这里就是a形式的阶乘
(lambda (x) ; ...
(if (= x 1) ; ...
1 ; ...
(* x (f (- x 1))))))) ; ...
5)
;好了，你可以看到为啥define语句这么重要了吧
define语句完成了一个几乎不可能的任务。神说：要有光。
3. 总结¶
看来在一个没有define语句的编程世界里，我们完全可以用匿名函数无中生有的构造了一个通用递归函数Y。方法就是套娃，如果套娃解决不了，那么就再套一层娃。
这是一个极其烧脑的过程，所以我领悟了这句话：“无中生有的东西，你把它讲一遍，等于你也有责任的”。
然而你可能要问了，这个Y组合子有什么用？答案是：没什么用。
但是注意Y在干什么，它输入一个函数a，然后生成了另外一个函数b，并把它进行(b b)的自我调用，最终生成了递归函数（比如factorial）。
再看一下这个神秘的魔法：(Y a)=(b b)=factorial，我们不禁发问：难道非要有什么用才有用吗？:)...