Y组合子(不动点组合子)的简单推导

First Post:

Blog Link:

对于一个函数 (其中 中可能含有对 的引用)

,则对于之前定义的 ,应该有 (或者写成 ),也就是说 的不动点。

不动点组合子可以写成 ( 其中 表示满足方程 ),也就是输入一个函数 ,返回满足方程

可以写成lambda演算的形式: (其中 表示将中所有 的自由出现替换为 )。

因此不动点组合子可以写成

注意该写法适用于call-by-name,而不适用于call-by-value。通常call-by-value将一般的 形式的方程转换成lambda演算时需要添加其他的原语(比如unfold)来延迟对 的代换。不过因为不动点组合子一般只用于函数,因此可以通过函数封装来延迟代换,也就是可以写成: ,或者:

在scheme中,Y组合子可以写成:

1
2
3
4
5
6
(define Y
(lambda (g)
(let ((d (lambda (f)
(lambda args
(apply (g (f f)) args)))))
(d d))))

注意scheme中的函数一般是非柯里化的,所以用apply来处理变长参数。