从递归到 Y 组合子
2019 年 01 月 29 日
停机问题
我们再来回顾一下停机问题：
是否存在一个函数 P，对于任意输入的函数 w，能够判断 w 会在有限时间内结束或者死循环。
通过前文的论述，我们已经知道这样的函数 P 是不存在的。由此可知，某些函数存在可以用语言描述却无法被程序定义的情况，以 Scheme 语言为例，即无法用 (define ...) 给函数命名。
递归
我们知道递归在 Scheme 中重要性是处在第一序列的。「The Little Schemer」书里，几乎所有函数都是围绕着递归思想来创建的。下面来看一个用于获取列表 l 的长度的例子：
(define length
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))它定义了 length 这个函数名称并用其进行递归操作。
如果这时候告诉你，(define ...) 不能用了，那么还能有什么方法可以表示出 length 函数呢？答案是有的，不过得让我们一步步来接近它。
高阶函数
高阶函数的一个形式是：接受一个函数作为参数，返回另一个函数。在上述例子中，我们可以引入一个高阶函数，把函数 length 作为参数传入：
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))显然它返回的也是 length 函数本身，而且没有再用到 (define ...)。因为这个高阶函数创建了 length 函数（make length），所以干脆就叫它 mk-length。
事情看起来已经符合我们的要求了，接下来似乎只要
(mk-length length)就能得到 length 函数。不过传入的 length 参数依旧需要通过 mk-length 来生成，也就是：
(mk-length (mk-length length))可以预见接下来还会有：
(mk-length (mk-length (mk-length length)))(mk-length
(mk-length
(mk-length
...)))这样下去就进入了无限循环。让我们先回到 (mk-length length)。
从头开始
上面 length 被不停创建的过程触发了无限递归，要解决这个问题，我们来做一个神奇的替换。
(define eternity
(lambda (x)
(eternity x)))eternity 是我们之前创建出来的一个最简单的偏函数，并且也是无限递归的。我们用它来替换 length，代入 (mk-length eternity) 并展开：
((lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l)))))))
eternity)再创建一个高阶函数，将 mk-length 本身作为参数提取出来：
((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 似乎更加贴切。
(define length0 (mk-length eternity))接下来我们可以写出 length1，它可以计算长度不超过 1 的列表：
((lambda (mk-length)
(mk-length length0))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))展开：
((lambda (mk-length)
(mk-length
(mk-length eternity)))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))可以写出 length2 了吗？当然：
((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 呢？
((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 传给自己试试：
((lambda (mk-length)
(mk-length mk-length))
(lambda (length)
(lambda (l)
(cond
((null? l) 0)
(else (add1 (length (cdr l))))))))length 作为入参可以用任意字符表示，甚至是 mk-length：
((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 好了：
; 函数一
((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)：
; 第一步
(((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); 第二步
((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); 第三步
((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)，前三步是和上面一样的，最后可以简化成：
(add1 (add1 ((eternity eternity) (quote ()))))其中 (eternity eternity) 在无限递归，上述表达式没有返回值，所以我们算不出长度为 2 的列表。那么函数一其实就是 length1。问题来了，有没有什么办法可以让 (eternity eternity) 这个位置的递归继续下去，这样我们好像就可以计算任意长度的列表了。
解决方案还是和这一节最开始用的相同方法，我们让 mk-length 来调用 mk-length：
((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) 语句提取出来，让函数更加清晰：
((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 也就是上面这个函数，我们来试试吧。
((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))))((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)))))((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，它是一个单参数函数。那么我们构造一个单参数函数，它可以做到惰性求值：
(lambda (x)
((mk-length mk-length) x))Lambda 演算中的第三条 η-变换规则规定到：对于任一给定的参数，当且仅当两个函数得到的结果都一致，则它们将被视同为一个函数。即如果对于给定的 l，((mk-length mk-length) l) 和 ((lambda (x) ((mk-length mk-length) x)) l) 的值都相同，那么就说这两个函数是等价的。显然他们就是同一个函数。那么做完替换之后长这样：
((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 的部分，作为参数：
((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 的逻辑部分剥离出来：
(lambda (le)
((lambda (mk-length)
(mk-length mk-length))
(lambda (mk-length)
(le (lambda (x)
((mk-length mk-length) x))))))简化一下：
(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 是什么。
(define fixed-point
(mk-length fixed-point))那么可以替换函数体中的 fixed-point 为 (mk-length fixed-point)：
(define fixed-point
(mk-length
(mk-length fixed-point)))(define fixed-point
(mk-length
(mk-length
(mk-length fixed-point))))(define fixed-point
(mk-length
(mk-length
(mk-length
...))))看上去很眼熟对不对？所以 mk-length 的不动点就是我们想要的 length。于是求 length 的问题就转化为：有没有这样一个函数 calc-fixed-point，代入参数 mk-length，然后得到 mk-length 的不动点：
(calc-fixed-point mk-length) = length又是一个眼熟的表达式，calc-fixed-point 看起来就是我们上面所得到的 Y 组合子，它可以计算参数的不动点。所以有时它又被称为不动点组合子。
关于 Lambda 演算、组合子、由不动点推导 Y 组合子等知识点，本文暂不作讨论。我光是看明白「The Little Schemer」第九章里推导 Y 组合子的过程，头就已经大了好几圈，头发也多掉了好几万根，就像书里说得那样。文章也无法避免由主观臆断而产生的概念性或者推导上的错误，欢迎指正。
参考链接
- 「The Little Schemer：递归与函数式的奥妙」第 9 章
- The Y Combinator
- Little Schemer: why wrap (mk-length mk-length) into a function?
- 十分钟速通 Y Combinator
- scheme 下的停机问题和 Y 组合子
- Y 不动点组合子用在哪里？
- Lambda 演算 - 维基百科
- 不动点组合子 - 维基百科
EOF