缘起
第一次听说Y组合子，大概是在19年的时候。当时看到这么个东西的时候，就觉得很漂亮。然后，也不知道薅掉多少根头发，终于在最近顿悟了其中的关键步骤，遂把思路整理成文章记录下来。
先简单说一下Y组合子产生的背景吧。
上个世纪三十年代，丘奇发明了Lambda演算（它是后来很多函数式变成的理论基础）。大概是因为信奉如无必要勿增实体，当年老爷子提出的理论里，函数是单参的、也没有名字的概念。
之后，柯里先救了一次场，证明多参函数可以用单参函数等价表示，这就是函数式编程里大名鼎鼎的柯里化。
但是没有函数名，怎么实现递归呢？关键时刻，柯里大神再次救场，证明了不需要名字，也能实现函数的递归。
不过，纯数学的理论证明咱也不会啊，所以，下面就用Scheme语言（基于Lambda的一种Lisp方言）以工程的视角推导出一个Y组合子。
推导过程
(define fact
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1)))))
)
这是一个递归求阶乘的函数。刚才说了，Lambda演算不能存在函数名，也就是说不能用define定义fact。但是，这里其实有一个变通方案：不能定义函数名，但是可以给变量命名，比如n。所以，第一步，我们把fact作为变量传进来。
(define some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1))))))
)
((some-name 'null) 1)
((some-name (some-name 'null)) 2)
((some-name (some-name (some-name 'null))) 3)
-
针对第一个式子，其实fact传入的是什么东西都无所谓，因为n = 1，所以不会走到(fact 0)，否则fact带入'null，会报错
-
针对第二个式子，n = 2时，带入得到 (* 2 (...))，其中...的部分就是第一个式子的内容，即((some-name 'null) 1)
-
针对第三个式子，n = 3时，带入得到 (* 3 (...))，其中...的部分就是第二个式子的内容，即((some-name (some-name 'null)) 2)
其实可以看出来，只要最后的(fact 0)不要真的执行到，就可以算越来越大的n
但是，我们不想 n = 4式，写这么长的式子了，((some-name (some-name (some-name (some-name 'null)))) 4)
所以我们试着做以下这2个替换：
第一步：既然'null都可以让程序跑起来，那替换成some-name是不是也可以？
((some-name some-name) 1)
((some-name (some-name some-name)) 2)
((some-name (some-name (some-name some-name))) 3)
第二步：既然程序最后终止在(fact 0)，用some-name带入fact后，实际上是终止在(some-name 0)
那是不是把(fact 0)改写成((fact fact) 0)，程序就不会终止了？
(define some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n ((fact fact) (- n 1))))))
)
((some-name some-name) 1)
((some-name some-name) 2)
; = (* 2 ((some-name some-name) 1))
((some-name some-name) 3)
; = (* 3 ((some-name some-name) 2))
; = (* 3 (* 2 ((some-name some-name) 1)))
((some-name some-name) 4)
; = (* 4 ((some-name some-name) 3))
; = (* 4 (* 3 ((some-name some-name) 2)))
; = (* 4 (* 3 (* 2 ((some-name some-name) 1))))
(((lambda (g) (g g)) some-name) 4)
可以看到这时候，其实要不要some-name已经没有关系了，完全可以把some-name用它真正的定义塞进去
(
; 这其实是一个函数，接受一个参数n，计算n的阶乘
(
(lambda (g) (g g))
; 这其实是刚才的some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n ((fact fact) (- n 1))))))
)
4)
上面的那个函数成为“穷人的Y组合子”，因为它指针对特定的递归函数生效，在这个例子里是fact
我们希望把fact提出去，让这个函数更通用一些
首先把fact代换为f（这一步实际上只是为了好看）
(
; 这其实是一个函数，接受一个参数n，计算n的阶乘
(
(lambda (g) (g g))
; 这其实是刚才的some-name
(lambda (f)
(lambda (n)
(if (< n 2) 1 (* n ((f f) (- n 1))))))
)
4)
接着我们把(f f)提出去
(
(
(lambda (g) (g g))
(lambda (f)
(
; 这是最初的阶乘函数
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1))))))
; 用lambda包一下，本质上就是刚才的 (f f)
; 这一步主要是因为Scheme是应用序求值
; 因此，如果不用lambda让它延迟求值的话，就会提前递归下去
(lambda (x) ((f f) x))
)
)
)
4)
再把fact相关的提出去
(define some-name
(lambda (fact)
(lambda (n)
(if (< n 2) 1 (* n (fact (- n 1))))))
)
(
(
(lambda (g) (g g))
(lambda (f) (some-name (lambda (x) ((f f) x))))
)
4)
(
(
; This is Y !!!
(lambda (fn)
(
(lambda (g) (g g))
(lambda (f) (fn (lambda (x) ((f f) x))))
)
)
some-name
)
4)
最终我们得到Y组合子
(define Y
(lambda (fn)
((lambda (g) (g g))
(lambda (f) (fn (lambda (x) ((f f) x)))))))
拿阶乘函数先测试下
((Y some-name) 5)
试试斐波那契数列
(define meta-fib
(lambda (fib)
(lambda (n)
(if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2)))))))
((Y meta-fib) 10)
网友评论