从递归到 Y 组合子

停机问题

我们再来回顾一下停机问题

是否存在一个函数 P,对于任意输入的函数 w,能够判断 w 会在有限时间内结束或者死循环。

通过前文的论述,我们已经知道这样的函数 P 是不存在的。由此可知,某些函数存在可以用语言描述却无法被程序定义的情况,以 Scheme 语言为例,即无法用 (define ...) 给函数命名。

递归

我们知道递归在 Scheme 中重要性是处在第一序列的。《The Little Schemer》书里,几乎所有函数都是围绕着递归思想来创建的。下面来看一个用于获取列表 l 的长度的例子:

1
2
3
4
5
(define length
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))

它定义了 length 这个函数名称并用其进行递归操作。

如果这时候告诉你,(define ...) 不能用了,那么还能有什么方法可以表示出 length 函数呢?答案是有的,不过得让我们一步步来接近它。

高阶函数

高阶函数的一个形式是:接受一个函数作为参数,返回另一个函数。在上述例子中,我们可以引入一个高阶函数,把函数 length 作为参数传入:

1
2
3
4
5
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))

显然它返回的也是 length 函数本身,而且没有再用到 (define ...)。因为这个高阶函数创建了 length 函数(make length),所以干脆就叫它 mk-length

事情看起来已经符合我们的要求了,接下来似乎只要

1
(mk-length length)

就能得到 length 函数。不过传入的 length 参数依旧需要通过 mk-length 来生成,也就是:

1
(mk-length (mk-length length))

可以预见接下来还会有:

1
(mk-length (mk-length (mk-length length)))
1
2
3
4
(mk-length
(mk-length
(mk-length
...)))

这样下去就进入了无限循环。让我们先回到 (mk-length length)

从头开始

上面 length 被不停创建的过程触发了无限递归,要解决这个问题,我们来做一个神奇的替换。

1
2
3
(define eternity
(lambda (x)
(eternity x)))

eternity 是我们之前创建出来的一个最简单的偏函数,并且也是无限递归的。我们用它来替换 length,代入 (mk-length eternity) 并展开:

1
2
3
4
5
6
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)

再创建一个高阶函数,将 mk-length 本身作为参数提取出来:

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length eternity))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))

那么上面这个函数是否已经创建出了 length 函数呢,我们代入具体的列表 l 来检验。

当 l 是空列表时,进入 (null? l) 分支,返回值是 0,正确。

当 l 是 (a) 这样的非空列表时,则进入 else 分支,但是 (etertiny (quote ())) 并不会返回值,函数也就不会返回正确的答案。

这个函数看起来只能计算空列表的长度,称之为 length0 似乎更加贴切。

1
(define length0 (mk-length eternity))

接下来我们可以写出 length1,它可以计算长度不超过 1 的列表:

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length length0))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))

展开:

1
2
3
4
5
6
7
8
((lambda (mk-length)
(mk-length
(mk-length eternity)))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))

可以写出 length2 了吗?当然:

1
2
3
4
5
6
7
8
9
((lambda (mk-length)
(mk-length
(mk-length
(mk-length eternity))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))

它可以计算长度不大于 2 的列表。lengthN 呢?

1
2
3
4
5
6
7
8
9
10
((lambda (mk-length)
(mk-length
(mk-length
(mk-length
...))))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))

要写 N 个 mk-length 了。

分析上面的推导过程可知,我们现在还无法定义一个通用的 length 函数,使得它能够计算任意列表的长度。从另一个角度考虑,如果在上面的函数形式中,我们能够写出足够多个 mk-length ,那么就能计算任意列表的长度了。但是“足够多”太抽象,不同列表所要求的个数有所不同,对于一个程序或者函数来讲,这样是写不出来的。

我算我自己

我们再来看看 mk-length,因为它的参数是一个函数,所以理论上可以调用任意函数。我们把 mk-length 传给自己试试:

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length mk-length))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))

length 作为入参可以用任意字符表示,甚至是 mk-length

1
2
3
4
5
6
7
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (mk-length (cdr l))))))))

现在我们得出了什么呢?当传入非空列表时,else 分支的 mk-length 接收一个列表作为参数,但是它实际上需要的参数是函数,所以最后并不会计算出值,这就和 length0 一样了。同时也表明我们将 mk-length 传给自己其实没有改变整个函数的意义。

如果我们用这个参数 mk-length 继续创建递归,就用 eternity 好了:

1
2
3
4
5
6
7
8
9
10
; 函数一
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length eternity)
(cdr l))))))))

代入列表 l 看看,l 这里是 (apple)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
; 第一步
(((lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length eternity)
(cdr l)))))))
(lambda (mk-length) ; 代入展开
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length eternity)
(cdr l))))))))
l)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
; 第二步
((lambda (l)
(cond
((null? l) 0)
(else (add1 (((lambda (mk-length)
(lambda (l)
(cond
((null? l) 0)
(else (add1
((mk-length eternity)
(cdr l)))))))
eternity) ; 代入展开
(cdr l))))))
l)
1
2
3
4
5
6
7
8
9
10
11
12
; 第三步
((lambda (l)
(cond
((null? l) 0)
(else (add1 ((lambda (l)
(cond
((null? l) 0)
(else (add1
((eternity eternity)
(cdr l))))))
(cdr l)))))) ; 代入展开,这里 (cdr l) 是 (quote ()),返回 0
l)

现在能够计算长度是 1 的列表了。那长度为 2 的呢?假设这时 l 是 (apple banana),前三步是和上面一样的,最后可以简化成:

1
(add1 (add1 ((eternity eternity) (quote ()))))

其中 (eternity eternity) 在无限递归,上述表达式没有返回值,所以我们算不出长度为 2 的列表。那么函数一其实就是 length1。问题来了,有没有什么办法可以让 (eternity eternity) 这个位置的递归继续下去,这样我们好像就可以计算任意长度的列表了。

解决方案还是和这一节最开始用的相同方法,我们让 mk-length 来调用 mk-length

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

这么做的目的是在递归即将结束的时候,又将 mk-length 传递给自身,确保递归的不断进行。

有点激动呀,我们终于能够抛弃 (define ...),仅用 lambda 表达式就写出 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)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))

第 4 到 8 行长得就很像一开始的 mk-length,这么一来就舒服了。之后当然是用具体的列表来测试啦,依旧借用 (apple)。要计算 (length (quote (apple))) 的值需要先展开 length 也就是上面这个函数,我们来试试吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length) ; 代入展开
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length) ; 代入展开
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
((lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length)))
(lambda (mk-length) ; 代入展开...
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(mk-length mk-length))))))

咦等等,这么一级级展开完全没有尽头,我们只是不停地把 mk-length 应用到它自己身上,周而复始。(mk-length mk-length) 本来期待它返回一个函数的,现在再也返回不了了。这可怎么办,胜利道路严重受阻。

不要方,我们还有一个武器——惰性求值,它的思想简单来说就是使表达式在被用到的时候才求值。在我们的需求里面就是对 (mk-length mk-length) 惰性求值,前面的运算里面不对它进行展开。

如何做?我们考虑到 (mk-length mk-length) 返回的函数在理论条件下就是 length,它是一个单参数函数。那么我们构造一个单参数函数,它可以做到惰性求值:

1
2
(lambda (x)
((mk-length mk-length) x))

Lambda 演算中的第三条 η-变换规则规定到:对于任一给定的参数,当且仅当两个函数得到的结果都一致,则它们将被视同为一个函数。即如果对于给定的 l,((mk-length mk-length) l)((lambda (x) ((mk-length mk-length) x)) l) 的值都相同,那么就说这两个函数是等价的。显然他们就是同一个函数。那么做完替换之后长这样:

1
2
3
4
5
6
7
8
9
10
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
(lambda (x)
((mk-length mk-length) x)))))

我们再构建一个高阶函数,移出第 4 到 8 行长得像 mk-length 的部分,作为参数:

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)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))

🎉 大功告成!以上就是我们不用 (define ...) 而写出的 length 最终版本。不容易啊。

Y 组合子

我们把上面函数调用 mk-length 的逻辑部分剥离出来:

1
2
3
4
5
6
(lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))

简化一下:

1
2
3
4
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x))))))

这玩意儿就叫应用序 Y 组合子(applicative-order Y combinator)!

仔细体会整个过程,在不给函数命名的情况下,我们最终却实现了这个递归函数。实际上正是 Y 组合子做了这件极其伟大的事情——实现递归。

补充:不动点组合子

这里我们先引入不动点的概念:对于函数 f,如果存在变量 x,有 f(x) = x,此时就说 x 是函数 f 的不动点。

我们来看看 mk-length 的不动点 fixed-point 是什么。

1
2
(define fixed-point
(mk-length fixed-point))

那么可以替换函数体中的 fixed-point(mk-length fixed-point)

1
2
3
(define fixed-point
(mk-length
(mk-length fixed-point)))
1
2
3
4
(define fixed-point
(mk-length
(mk-length
(mk-length fixed-point))))
1
2
3
4
5
(define fixed-point
(mk-length
(mk-length
(mk-length
...))))

看上去很眼熟对不对?所以 mk-length 的不动点就是我们想要的 length。于是求 length 的问题就转化为:有没有这样一个函数 calc-fixed-point,代入参数 mk-length,然后得到 mk-length 的不动点:

1
(calc-fixed-point mk-length) = length

又是一个眼熟的表达式,calc-fixed-point 看起来就是我们上面所得到的 Y 组合子,它可以计算参数的不动点。所以有时它又被称为不动点组合子。


关于 Lambda 演算、组合子、由不动点推导 Y 组合子等知识点,本文暂不作讨论。我光是看明白《The Little Schemer》第九章里推导 Y 组合子的过程,头就已经大了好几圈,头发也多掉了好几根,就像书里说得那样。文章也无法避免由主观臆断而产生的概念性或者推导上的错误,欢迎指正。

参考链接

  1. 《The Little Schemer:递归与函数式的奥妙》第 9 章
  2. The Y Combinator
  3. Little Schemer: why wrap (mk-length mk-length) into a function?
  4. 十分钟速通 Y Combinator
  5. scheme 下的停机问题和 Y 组合子
  6. Y 不动点组合子用在哪里?
  7. Lambda 演算 - 维基百科
  8. 不动点组合子 - 维基百科

– EOF –