Beautiful Y-combinator


如果仅仅是讨论编程相关,可能就不会牵涉到太多符号抽象,所涉及到的内容可能也是简化过的形式。从这个角度入手,这一段时间打算对一些 MonadY-Combinator 还有 CPS(Continuation-Passing-Style) 这三方面进行一点点总结。查了很久资料,发现很多东西都和 Lambda Calculus 相关,而这又需要不少 Mathematical Logic 的基础。

今天打算先玩一玩 Y-combinator 这个著名的不动点组合子,虽然这是 lambda calculus 的内容,但也是许多的 programmer 所熟悉的一个名词,玩不转的话似乎有点不太好。首先就是这个名词的问题,什么是组合子?什么是不动点?Y 组合子又是个什么东西,它能用来干什么?为什么要学习这个东西?其实第一次见到一个陌生的名词,心里大概就会来一遍这个过程。经过一点点了解,我觉得自己现在能够对这几个问题做一些回答(自问自答?)和总结。

首先是第一个问题,什么是组合子(combinator)?

可以将组合子考虑为不含自由变量 表达式,所谓的自由变量就是那些不被约束的变量,也就是说,伴随组合子的变量都是 bound variable (作为参数)。下面作为例子,来实现阶乘函数

(define factorial
  (lambda (x)
    (if (zero? x) 1
        (* x (factorial (sub1 x))))))

这个实现显然是 recursive 的,但是稍微有些怪怪的,因为我们没有把参数显式地放在函数名后,而是把 表达式放在内部作为函数体。这样做有什么特别的意图吗?是的,这样做是很有好处的,它更加清晰展地现了函数的定义,我们可以更形式化地来描述一下

是不是更清晰了?现在可以很容易看出来,这个函数不是组合子,因为 factorial 是自由变量。

接下来的问题是,什么是不动点(fixed-point)?

嘿!这不是什么新的玩意,我很清楚什么是不动点,被一个函数映射到自身的点就是这个函数的不动点嘛!不过,现在不妨扩宽一下思路,要知道函数可以被看作是 “first class” data objects,函数可以是高阶函数,不动点也可以是函数,那么

表示函数 是高阶函数 的不动点。

这一点其实也可以不用提,如果看过 SICP 的话,现在脑海中大概就会浮现出其中的那个例子,解决了如何求(一般意义下的)不动点的问题,方法是反复 apply 到自身

当然,数值上我们可能找不到不动点,要解释这一点可以举个例子,我直接从 SICP 里抄一个

(define (fixed-point f first-huess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

可以看到最后的结果总是要和 tolerance 进行比较。在 lambda calculus 中,全体 表达式构成 空间, 表达式为 空间到 空间的函数,而且不动点定理保证了每个 表达式都有不动点。那么我们要怎么去求高阶函数的不动点呢?

可以用 Y-combinator!这也是我们对下一个问题的答复。

现在就提起 Y-combinator 可能还有些早,我们先来活跃一下自己的 recursion细胞,以便切入更深入的问题中去。刚刚我们实现了一个 recursive 的阶乘函数,现在再来实现一个小工具,求一个 list 的长

(define len
  (lambda (lst)
    (if (null? lst) 0
      (1+ (len (cdr lst))))))

很简单的一个函数,没有问题。

但是我们不想用 define 方法,这该怎么办呢?没有办法在函数体内应用 len 了。

先找一个函数用来占位吧,用 eternity 把它搞成一个偏递归函数。在 The Little Schemer 中有提到这个小方法,用来解释停机问题时用的,它的结果永远是

(define eternity
  (lambda (x) (eternity x)))

这里用了 define,不过不要紧,可以把它看成是一个外来的,无论何时都能 get 到的方法。

好了,现在让我们先忘了 define,或者说,不要在函数体内引入更多自由变量,试着实现一下 len 看看?

(lambda (lst)
  (cond ((null? lst) 0)
        (else (1+ (eternity (cdr lst))))))

好像做不到,仔细观察一下,这个函数只能处理空 list,非空的 list 会让它停不下来。根据这个函数的功能,我们先叫它 len-0 好了,这可以用 define 定义出来,不过我们的确没有引入自由变量。

再努力一下?

(lambda (lst)
  (cond ((null? lst) 0)
        (else (1+ ((lambda (lst)
                    (cond ((null? lst) 0)
                          (else (1+ eternity (cdr lst))))) 
                  (cdr lst))))))

虽然还是没有实现 len,但是这一回可以处理单元素 list 了,称它为 len-1 好了。

再来一次!

(lambda (lst)
  (cond ((null? lst) 0)
        (else (1+ ((lambda (lst)
                    (cond ((null? lst) 0)
                          (else (1+ ((lambda (lst)
                                      (cond ((null? lst) 0)
                                            (else (1+ (eternity
                                                      (cdr lst))))))
                                    (cdr lst))))))
                  (cdr lst))))))

我们更进了一步,实现了 len-2 方法,但是对于更长的 list 还是会停不下来呢。

这下就郁闷了,上面这么长的一大坨代码才只是实现了 len-2 就已经让人看着有点犯恶心了,况且我们也不可能一直像这样写下去的。那该怎么办呢?稍加观察,发现一层一层的这些结构长得都差不多,不如用一用抽象,先试着简化一下看看吧。

既然每次都是在 eternity 占位处再写深一层,那我们在原来 lambda 的基础上再抽一层

(lambda (f)
  (lambda (lst) 
    (cond ((null? lst) 0)
          (else (1+ (f (cdr lst)))))))

实现了一个高阶函数,现在用它来重写一下刚才的那些方法看看

首先是 len-0 的实现

(define len-0
  ((lambda (f)
     (lambda (lst) 
       (cond ((null? lst) 0)
             (else (1+ (f (cdr lst)))))))
    eternity))

然后是 len-1 的实现

(define len-1
  ((lambda (f)
    (lambda (lst)
      (cond ((null? lst) 0)
            (else (1+ (f (cdr lst)))))))
    ((lambda (g)
       (lambda (lst)
       (cond ((null? lst) 0)
             (else (1+ (g (cdr lst))))))) 
      eternity)))

虽然实现上没有问题,但还是麻烦了,我们直接用之前的定义去替换 lambda 块应该可以更清晰一些。现在来给我们刚才写好的高阶函数起个名字,由于结构和 len 一致,就叫作 almost-len 好了,现在再来试试。

先是 len-0 的简化

(define len-0
  (almost-len eternity))

然后是 len-1 的简化

(define len-1
  (almost-len len-0))

; 展开后看得更清楚
(define len-1
  (almost-len
    (almost-len eternity)))

然后可以一直以这种模式进行下去,比如说我们现在实现一个 len-4 看看

; 各种定义链
(define len-0 (almost-len eternity))
(define len-1 (almost-len len-0))
(define len-2 (almost-len len-1))
...
(define len-4 (almost-len len-3))

; 同样展开一下看看
(define len-4
    (almost-len
      (almost-len
        (almost-len
          (almost-len 
            (almost-len eternity))))))

这还不算完,还可以继续下去,但是没什么意义了,我们还是写不出来 len 函数。

从这里似乎可以看出点什么来,这种反复应用的模式似乎在哪见过?假设我们一直这样反复应用,实际上就可以逐渐逼近 len 函数了,这个应用链表示为

哦!这就是在求不动点嘛。反复应用到 almost-len 上,似乎就可以得到 len 了,这说明了什么呢?

假设现在我们有一个能够 work 的函数 len 在手上,如果把它应用到 almost-len 上去就有

((lambda (f)
   (lambda (lst)
     (cond ((null? lst) 0)
           (else (1+ (f (cdr lst)))))))
 len)

很显然,这个函数应该能很好地工作,产生的函数是什么呢?

对!它产生了 len 函数。那么这说明了什么呢?

这说明了,对于一个函数 g,我们可以用技巧在外面加一层 lambda 构造出 almost-g 高阶函数,这个高阶函数的不动点就是 g 函数本身。就像我们构造了 almost-len,它的不动点就是 len 函数。回想一下,我们在开头提到 Y-combinator 可以算出高阶函数的不动点,也就是说

那我们现在是不是可以写出 Y 了呢?

(define Y
  (lambda (f)
    (f (Y f))))

(define len (Y almost-len))

扔个 list 进去验证一下,发现这个函数在我的解释器下跑不出结果来,它停不下来。

可是为什么呢?

仔细一想,发现和求值方式有关。其实这个函数可以在实现了 lazy 的解释器下运行,如果用 strict scheme 来进行求值,无论何时调用 (Y f) 表达式,就一定会立刻进行规约,形式化描述一下

这样的话,是等不到调用的结果作为参数被送入 f 中的。但是,如果实现了 lazy 的话,表达式 (Y f) 不会被立刻规约,而是作为参数送入 f 中(也就是 almost-len)将函数体展开。因为对于 lazy 是可以完成求值的,那么这的确是实现了 len 函数, 这种形式是正则序(normal-order),与之对应,也有 strict 的形式,称之为应用序(applicative-order)。

该怎么解决这个问题呢?

面包会有的,办法也会有的。解决办法就是在外面搞一层 lambda 构造抽象屏障,用来抵消一次规约。对于一个计算过程,可以在外面套一层 lambda,实际上函数的作用不会发生变化,但是却大有益处。

沿着这种思路,我们把 Y 的形式修改一下

(define Y
  (lambda (f)
    (f (lambda (x) ((Y f) x)))))

函数 f 面对的是一个 表达式,函数体能够顺利展开,我们看不到 的内部是什么。

; 直接形式
(Y almost-len)

; 展开 Y
(almost-len (lambda (x) ((Y almost-len) x)))

; 展开 almost-len 进行 apply
(lambda (lst)
  (cond ((null? lst) 0)
        (else (1+ 
               (lambda (x) ((Y almost-len) x)))
               (cdr lst))))

看起来不错!

那么,现在可以结束了吗?

不,还不够!

要知道,虽然我们已经定义出了可以工作的 Y ,但是这并不是组合子,在 Y 的定义中有自由变量在里面,这并不是我们最终想要得到的,我们想要的是 Y 组合子。像上面这样定义的 Y 仍然是一种显式的递归,而组合子是不能进行显式递归的,所以现在的努力方向是把自由变量干掉。为了方便起见,我们现在假设求值都是 lazy 的形式,也就是 normal-order 的,毕竟用之前的 trick 将之改为applicative-order也很容易。

重新来考虑一下我们要实现的 len 函数,不能有自由变量,那么把自己作用在自己上面呢?

; 之前定义的 almost-len
(lambda (f)
  (lambda (lst) 
    (cond ((null? lst) 0)
          (else (1+ (f (cdr lst)))))))

; 将它作用在自己上面!
((lambda (x)
  (x x))
 (lambda (f)
   (lambda (lst)
     (cond ((null? lst) 0)
           (else (1+ (f (cdr lst))))))))

等等!这里有些不对!如果拿这个 应用到一个 list 上,会得到一个参数类型错误,因为 (cdr lst) 不可以作为参数喂给一个高阶函数,这里需要再修改一下,我们要找一个函数喂给它,可是找谁好呢?不能有自由变量,那么还是把它自己再喂进去好了。

; 将它作用在自己上面!
((lambda (x)
  (x x))
 (lambda (f)
   (lambda (lst)
     (cond ((null? lst) 0)
           (else (1+ ((f f) (cdr lst))))))))

我们不妨给底下那个 表达式起个名字,就叫它 part-len 好了,拆开后更清楚一些

(define part-len
  (lambda (f)
    (lambda (lst)
      (cond ((null? lst) 0)
            (else (1+ ((f f) (cdr lst))))))))

((lambda (x) (x x)) part-len) ; 得到 len 函数了!

这一步意义非凡!

太棒了!我们现在实现了 len 函数,没有用到显式的递归,所有的变量都是 bound variable。现在我们离真理越来越近了,继续走下去!上面的形式还是有些不太好,中间的 (f f) 让我们失去了递归的形式,我们现在再做一个变换,让它的形式更好一些。

(define part-len
  (lambda (g)
    (lambda (f)
      (lambda (lst)
        (cond ((null? lst) 0)
              (else (1+ (f (cdr lst))))))
    (g g))))

这样就舒服多了,中间又变回了 almost-len 的形式,我们可以进一步把这一块替换掉

(define part-len
  (lambda (g)
    (almost-len (g g))))

好!现在再组合自调用函数构成 len 函数,参数也可以用 x 替代,没有关系

(define len
  ((lambda (x) (x x))
   (lambda (x)
     (almost-len (x x)))))

最后,因为 almost-len 是预先定义好的函数,也是要送给 Y 组合子的函数,把它抽出来

(define len
  ((lambda (f) 
   ((lambda (x) (x x))
    (lambda (x) (f (x x)))))
  almost-len)

很显然,中间就是我们的 Y-combinator 了,把它抽出来

(define Y
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (x) (f (x x))))))

完成了!

结束了吗?

很遗憾,还没有哦~

现在我们得到的是正则序 Y 组合子,是 lazy 的,试一下就会发现,解释器会给出错误表示递归太深溢出了。不过我们可以很容易把它改写成 applicative-order 的形式,只要在外面搞一层 lambda 就可以了。

; Applicative-order Y-combinator
(define Y 
  (lambda (f)
    ((lambda (x) (x x))
     (lambda (x) (f (lambda (y) ((x x) y)))))))

大功告成!

到这里,算是最终完成了对 Y 组合子的推导,得到了封闭的组合子形式。没有自由变量,没有副作用,非常纯粹,以非常完美的形式展现在我们的眼前。Y 组合子的形式由 Haskell B. Curry 给出,这个很有魔法感的东西形式化的表述非常简洁

这个形式对应于我们推出的 lazy 形式,也就是 normal-order Y-combinator 了。

仔细看会发现有些不一样的地方,不过它们是等价的,我们给出的是

只要再进行一次 -规约就得到上面的形式了。

现在看看把一个类似于 almost-len 的函数作用上去会怎么样,验证一下能不能得到不动点

经过几次 -规约,结果显而易见。

Y-combinator 形式非常优美。有了它,对 表达式进行递归就不成问题,它可以把传入函数本身的计算过程给『算出来』。