首页 > 代码库 > Y combinator
Y combinator
在lambda演算中，只有两类表达式，一类是函数定义(lambda 表达式)，一类是函数应用在参数上。函数定义的形式是匿名的，同时因为没有赋值语句，所以函数它是没有名称可以指代的，没有名称来引用函数，这里自然就遇到一个问题，lambda演算中如何实现递归呢，也就是lambda表达式如何引用自身。Y combinator就是解决匿名函数实现递归的问题的，准确的说是解决匿名函数实现递归的很优雅的方式。下面用scheme语言给出我理解的Y combinator的推导过程。
先不去看Y combinator到底是个什么东西，直接考虑，如果对匿名函数递归的实现阶乘
1 (lambda (n)2 (if (< n 2)3 14 (* n (f (- n 1)))5 )6 )
上面代码中写了一个实现阶乘匿名的函数，但是引用了一个不知从哪来的f，f实际上就是匿名函数本身，所以现在就必须想办法把匿名阶乘函数传递给f，匿名函数传递值的唯一办法是通过应用参数实现，好，现在就给这个匿名的阶乘函数添加一个捕获自身的参数
1 (lambda (f)2 (lambda (n)3 (if (< n 2)4 15 (* n (f (- n 1)))6 )7 )8 )
现在是添加一个可以捕获自己的参数了，但是还没有捕获自身这个动作，也就是需要应用下自身，自身没有名字怎么办，好吧，把自己再写一遍
1 (lambda (f) 2 (lambda (n) 3 (if (< n 2) 4 1 5 (* n (f (- n 1))) 6 ) 7 ) 8 ) 9 (lambda (f)10 (lambda (n)11 (if (< n 2)12 113 (* n (f (- n 1)))14 ) 15 )16 )
仔细看看现在的代码好像还有问题，当“自身”传递给f的时候，f是直接应用了n-1的值，但事实上"自身"是有两个参数的，第一个是f，第二个n，这里f作为“自身”的名字却只应用了一个参数实际上是有问题的，所以(f (- n 1)应该改成((f f) (- n 1))
1 (lambda (f) 2 (lambda (n) 3 (if (< n 2) 4 1 5 (* n ((f f) (- n 1))) 6 ) 7 ) 8 ) 9 (lambda (f)10 (lambda (n)11 (if (< n 2)12 113 (* n ((f f) (- n 1)))14 ) 15 )16 )
如上，就是一个完整的实现阶乘的递归函数。
那Y combinator到底是什么神奇的东西呢，我不用你，其实我依然实现了匿名函数的递归。简单来说Y combinator也是一个匿名函数，也是一个高阶函数，输入是函数，输出是函数，Y combinator的魔力在于应用G后，能生成G的不动点，G的形式如下面代码，
1 (lambda (f)2 (lambda (args)3 ( ...4 (f args)5 ...6 )7 )8 )
何为不动点，假如存在一个函数F，使得GF=F，F就是G的不动点，而F实际上就是YG，取得不动点，意义在哪，还以阶乘例子说
1 Fact‘ = (lambda (f)2 (lambda (n)3 (if (< n 2)4 15 (* n (f (- n 1)))6 )7 )8 )
Fact‘不是阶乘函数，但是我假设有一个叫Fact的阶乘函数，那么Fact’应用到Fact是不是就是我要的阶乘函数，也就是Fact’Fact = Fact，这里就发现了Fact实际上就是Fact‘的不动点，根据之前说的，Y应用Fact’后获取的就是Fact，现在我们知道了Fact‘的形式，Fact的形式也知道了，然后就是想通过YFact’=Fact等式来推出Y的形式
1 ;将(lambda (x) (x x))应用到Fact‘可以得到 2 (lambda (x) (x x)) Fact‘ 3 = 4 (lambda (f) 5 (lambda (n) 6 (if (< n 2) 7 1 8 (* n (f (- n 1))) 9 )10 )11 )12 (lambda (f)13 (lambda (n)14 (if (< n 2)15 116 (* n (f (-n 1)))17 ) 18 )19 )
显然(lambda (x) (x x))Fact‘与Fact还是不等价的
1 ;我们需要先把Fact’的形式: 2 (lambda (f) 3 (lambda (n) 4 (if (< n 2) 5 1 6 (* n (f (- n 1))) 7 ) 8 ) 9 )10 ;变换成11 (lambda (f)12 (lambda (n)13 (if (< n 2)14 115 (* n ((f f) (- n 1)))16 ) 17 )18 )19 ;然后作用到(lambda (x) (x x))就是完整的Fact了
考虑匿名函数(lambda (g) (lambda (f) (g (f f))))应用到Fact‘，展开便是我们想要的形式了，再综合前述的(lambda (x) (x x))应用便得到Fact
于是完整的过程是(lambda (x) (x x)) ((lambda (g) (lambda (f) (g (f f)))) Fact‘) = Fact,走到这一步还不够，我们要找的Y是能够直接应用Fact’的，
由于(lambda (x) (x x))本质上应用的是(lambda (f) (Fact‘ (f f)))，Fact’只要能够传递给(g (f f))中的g，最终就能得到Fact，
现在把参数g放到最外层，得到的lambda表达式就是我们想要的Y
(lambda (g) ((lambda (x) (x x)) (lambda (f) (g (f f)))))
参考：http://en.wikipedia.org/wiki/Fixed-point_combinator#Y_combinator
Y combinator