WHsT

WHsT

WHsT's name is .
Twitter: @xukiro, GitHub: whst

笨方法构造 Y-combinator


最近 Y-combinator (也叫不动点组合子)这个名词挺火的,一方面因为美国有个孵化器取了这个名字,另一方面则是因为「函数式编程」一定程度上的普及。部分「大V」在微博上故弄玄虚,甚至看到有人说「等你会写 yc 了再和我争论这个问题」,先不说把 Y-combinator 缩写成 yc 像是把 HTML5 缩写成 H5 那样好笑,这种态度像是 Y-combinator 是什么了不起的东西,让人哭笑不得。

这里就对这个东西科普一下,消除没有接触过的人对它的神秘感。本文假设读者会 Lisp 或 Python 中的一种语言,不需要额外的数学基础。

从概念上说,不动点其实很简单,函数 f 的不动点是一个值 x 使得 f(x) = x. 而高阶函数的不动点则是一个函数,即 y f = f (y f)。

MIT-Scheme 的 logo 上面的 (Y F) = (F (Y F)) 以及无穷递归的图案,实际上就代表这个意思:
MIT-Scheme

下面我们通过一个最简单的问题开始,循序渐进地推导Y组合子。以下示例代码基于《The Little Schemer》第九章改写。

首先,如果我们用普通的递归函数计算一个链表的长度,它应该是这样的:

1
2
3
4
5
(define length
(lambda (l)
(if (null? l)
0
(+ 1 (length (cdr l))))))

如果不懂 Scheme 也没关系,它大致等价于这段 Python 代码(注意对空表取反会得到 True):

1
length = lambda l: 0 if not l else 1 + lenth(l[1:])

这是最正常、最容易想到的写法。然而数学里最原始的 λ演算 中,所有函数都是匿名的。
也就是说,不能像最上面的这段代码一样给函数用 define 绑定一个名字,然后在函数体内调用这个函数自己。那么λ演算如何实现递归?

不如先假设有一个函数 ERROR,它接受一个参数,然后马上报错。
由于函数定义是匿名的,我们无法在函数内再通某个名字调用自身了。所以暂时用 ERROR 函数替代原来的 length:

1
2
3
4
(lambda (l)
(if (null? l)
0
(+ 1 (ERROR (cdr l)))))

这个函数可以处理空表,但是一旦表长度超过 0,就会调用 ERROR 产生错误。

那能否把函数体自己替换 ERROR 函数呢?这样就能调用「自己」了。像下面这样:

1
2
3
4
5
6
7
8
(lambda (l)
(if (null? l)
0
(+ 1 ((lambda (l)
(if (null? l)
0
(+ 1 (ERROR (cdr l)))))
(cdr l)))))

这下可以处理空表和长度为 1 的表。但是显然它还不够,因为如果列表长度超过 1 ,还是会触发 ERROR。
我们可以(无脑地)继续展开括号处:

1
2
3
4
5
6
7
8
9
10
11
12
(lambda (l)
(if (null? l)
0
(+ 1 ((lambda (l)
(if (null? l)
0
(+ 1 ((lambda (l)
(if (null? l)
0
(+ 1 (ERROR (cdr l)))))
(cdr l)))))
(cdr l)))))

这个函数可以处理列表长度不超过 2 的情况。

作为强迫症,这层层嵌套的匿名函数实在是太难看了,我们可以把函数在 if 在 else 分支要调用什么函数拿出来,作为一个单独的参数 func,这样可以让代码看起来平整一点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
((lambda (func)
(lambda (l)
(if (null? l)
0
(+ 1 (func (cdr l))))))
((lambda (func)
(lambda (l)
(if (null? l)
0
(+ 1 (func (cdr l))))))
((lambda (func)
(lambda (l)
(if (null? l)
0
(+ 1 (func (cdr l))))))
ERROR)))

这段代码和上一段本质相同,但好看些。然而,完全重复的代码还是很多。
观察其中的模式:每个函数取有一个形参 func,在表不为空时候调用 func 函数,而 func 绑定的实参和函数自己一模一样。所以可以继续把这个过程抽象一下,把重复的代码抽出来传给另一个函数,而另一个函数则负责重复这个模式:

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length (mk-length (mk-length ERROR))))
(lambda (func)
(lambda (l)
(if (null? l)
0
(+ 1 (func (cdr l)))))))

这下好看多了~
不过我们一开始的问题还是没解决:如果表长度超过了 2,这里还是会调用 ERROR。

如果观察能力敏锐的话,你也许已经看出来了……
是的,为什么非得死心眼地把 ERROR 传给 mk-length 呢?完全可以把 mk-length 传给他自己啊!这样就能让下面这个匿名函数不断地调用自己了:

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length mk-length))
(lambda (func)
(lambda (l)
(if (null? l)
0
(+ 1 (func (cdr l)))))))

先别高兴,这段代码实际上有错!!!如果你扔给它一个列表,解释器会告诉你「不能把 procedure 和 number 相加」。不难看出来,是因为最后一行的 func 实际上不能直接应用到列表上,而需要先给他一个函数,这样才能返回一个接受列表的函数。这很好处理,把 func 改成 (func func) 即可:

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length mk-length))
(lambda (func)
(lambda (l)
(if (null? l)
0
(+ 1 ((func func) (cdr l)))))))

函数参数的名字并不重要,不如统一成同样的名字:

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(if (null? l)
0
(+ 1 ((mk-length mk-length) (cdr l)))))))

等价 Python 代码:

1
2
3
(lambda mkLength: mkLength(mkLength))\
(lambda mkLength: lambda l:\
0 if not l else 1 + mkLength(mkLength)(l[1:]))

你可以亲手在解释器里试试,现在这个函数可以工作了。
现在的问题是,这个函数已经被我们改得面目全非,尤其是这个 (mk-length mk-length) 一点也不像原来的 length 函数。我们不如弄一个参数叫 length,然后传 (mk-length mk-length) 给他:

1
2
3
4
5
6
7
8
9
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(if (null? l)
0
(+ 1 (length (cdr l))))))
(mk-length mk-length))))

这下和原始的 length 函数有点像了,不幸的是它会陷入无限递归。因为在上一个正确版本中,(mk-length mk-length)只在表非空时需要被求值;而这一个版本会在 if 执行前先对它求值,导致无穷尽的展开。这里我们的 trick 是创建一个新的等价匿名函数:用 (lambda (x) ((mk-length mk-length) x) 代替 (mk-length mk-length)。如此一来,只会在调用这个匿名函数的时候对 (mk-length mk-length) 求值。这次修改后函数长这样:

1
2
3
4
5
6
7
8
9
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(if (null? l)
0
(+ 1 (length (cdr l))))))
(lambda (x) ((mk-length mk-length) x)))))

现在可以看到,上面这段代码的第 4 ~ 8 行已经和最开始的代码几乎相同一样了。 我们把他移出来放到末尾的 6 ~ 10 行(虚线是为了方便观察画的):

1
2
3
4
5
6
7
8
9
10
11
((lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x) ((mk-length mk-length) x))))))
- - - - - - - - - - - - - - - - - - - - - - - - -
(lambda (length)
(lambda (l)
(if (null? l)
0
(+ 1 (length (cdr l)))))))

现在你可以看到,虚线下面几乎和原函数相同。而虚线上面这个函数,实际上就是 Y-combinator!因此 Y-combinator 用代码是这样定义的:

1
2
3
4
5
(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))

Python 版:

1
Y = lambda le: (lambda f: f(f)) (lambda f: le(lambda x: f(f)(x)))

接下来就可以测试一番了 ^_^

Scheme 测试
Python 测试

这就是 applicative order Y-combinator,用他就能实现匿名函数的递归调用啦 :-P


另外说几句。在 Haskell 这样的惰性求值的语言中,写Y不动点组合子更简单。我们只需要完全按定义来:

1
2
fix :: (a -> a) -> a
fix f = f (fix f)

再有函数类似于

1
f = \length l -> if null l then 0 else succ . length $ tail l

然后可以输入表达式 (fix f) [1..n] 就可以得到长度 n. 很方便吧~