lambda演算中的递归与Y组合子

λthis.

考虑在$\lambda$演算中实现一个递归的阶乘函数，
$fact(n)=\begin{cases} 1&,n=0 \\ n\cdot fact(n-1)&,n\neq0 \end{cases}$

按照习惯性的做法，可能会写成:

λn.(if (= n 0) 1 (* n (this (- x 1))))

其中this表示这个函数自身。

然而，对于这个函数而言，this并没有意义，没有“调用自身的函数”这个实体存在

如果我们想要用this，就要在这个函数中实现this的功能，构造出一个“调用自身的函数”

我们顺着这个思路下去，构造this：

λthis.λn.(if (= n 0) 1 (* n (this (- x 1))))

由于this从意义上应该是调用函数自身，λthis.λn.balabala这个函数的第一参数应该是函数自身，第二参数才是数值，所以

(this (- x 1))

是有问题的，我们应将它修改为：

(this this (- x 1))

于是得到：

λthis.λn.(if (= n 0) 1 (* n (this this (- x 1))))

同样的，为了确保this的意义，也为了构造出$fact(n)$这个只有一个参数的函数，需要将函数自身传给this。

由是我们得到阶乘函数：

fact:=(λthis.λn.(if (= n 0) 1 (* n (this this (- x 1)))) λthis.λn.(if (= n 0) 1 (* n (this this (- x 1)))))例：(fact 4)值为24

至此，我们完成了对“调用自身的函数”的构造，另一种意义上讲，我们实现了$\lambda$演算中的递归

使用λthis.实现递归

一旦理解了"this的语义是函数自身，故其第一参数应是函数自身"，其实就已然实现了递归

基于对this语义的定义，我们可以设计任意的递归函数

拿常见Fibonacci数列来举例：
$fib(n)=\begin{cases} 1&,n=1\\ 1&,n=2\\ fib(n-1)+fib(n-2)&,n\notin\{1,2\}\\ \end{cases}$
在$\lambda$演算下我们设计成：

fib:=(λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this this (- n 1)) (this this (- n 2)))))λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this this (- n 1)) (this this (- n 2))))))例：(fib 5)值为5

Y组合子

我们发现，尽管上述的fib函数在语义上，逻辑上都没有问题，但写起来比较繁琐，不习惯。

一方面为简化书写，另一方面为符合习惯，我们考虑设计一个函数，能让以下这种写法，自动转换成完整的递归函数：

λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this (- n 1)) (this (- n 2)))))

我们设输入函数为F，输出函数为G

F:=λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this (- n 1)) (this (- n 2)))))))G:=(λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this this (- n 1)) (this this (- n 2)))))λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this this (- n 1)) (this this (- n 2))))))

也就是说我们想要设计一个函数，设为Y，它能做到：(Y F)=G

那么Y要怎么设计呢？

观察总结Y需要做的事情：

1. 生成**将F中的this替换成(this this)**的新函数，假设为f

2. 返回将新函数自身传递给自身的函数，即返回(f f)

首先，生成**将F中的this替换成(this this)**的新函数，可以这样实现：

A:=λF.λthis.(F (this this))

(A F)
=
λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this this (- n 1)) (this this (- n 2)))))))

其次，返回将新函数自身传递给自身的函数，可以这样实现：

B:=λf.(f f)

(B (A F))
=
((A F)(A F))
=
(λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this this (- n 1)) (this this (- n 2)))))λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this this (- n 1)) (this this (- n 2))))))
=G即(B (A F))=G 

所以Y就是：λF.(B (A F))

我们展开它：

λF.(B (A F))
=λF.(λf.(f f) (λF.λthis.(F (this this)) F))
=λF.(λf.(f f) λthis.(F (this this)))
=λF.(λthis.(F (this this)) λthis.(F (this this)))
=λf.(λx.(f (x x)) λx.(f (x x)))

得到Y组合子：
Y:=λf.(λx.(f (x x)) λx.(f (x x)))

有了它，现在我们可以这样设计递归函数了：

fact:=(Y λthis.λn.(if (= n 0) 1 (* n (this (- x 1)))))fib:=(Y λthis.λn.(if (= n 1) 1(if (= n 2) 1 (+ (this (- n 1)) (this (- n 2)))))

相关链接：https://en.wikipedia.org/wiki/Lambda_calculus