My Profile Photo

wlnirvana


Youth is not a time of life, it is a state of mind.


Y Combinator

最近读了The Little Schemer,里面有一章专门讲Y combinator。可是看完之后仍然觉得云里雾里的:只明白了Y Combinator是如何定义递归函数的,却不清楚Y combinator最初是怎么被想出来的。又在网上查了一些资料,心里有了个大概的眉目,总结在这里,算是对这段学习的一个交代吧。

Y combinator所要解决的问题,是如何在类似lambda演算的形式化系统中里面定义递归函数。lambda演算只有三种基本要素:变量、函数应用、函数抽象。尤其值得注意的是,与我们所熟悉的绝大多数编程语言不同,lambda演算中不能直接给变量赋值,而只能通过上述要素中的第二种——函数应用——来将形参与实参相绑定。可是,所谓递归函数,例如叫做f(暂时假定我们又有了绑定变量的能力,并将这个函数与变量名f相绑定),就是在函数体里面通过f这个变量名来调用该函数自身。如果我们丧失了这种绑定变量的能力,还怎么实现递归呢?答案(之一)就是Y combinator。下面就用一个Scheme的例子来演示Y combinator的一种推导方式。

Scheme中的length

Scheme中有一个内置函数length,能求list的长度。如果我们自己来写的话,一种可能的实现是这样:

(define len
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (len (cdr l)))])))

现在假如我们没有define了,还能不能定义一个求list长度的函数呢?第一反应是能,因为(define name value)所做的无非就是把value绑定到name。即便现在没了name,只要有value不是照样可以吗?所以我们可以把那部分value单独写出来:

(lambda (l)
  (cond [(null? 1) 0]
        [else (add1 (len (cdr l)))]))

可是现在问题来了:这个表达式里面的len指的是谁呢?这就涉及到了递归的核心。对于一个非递归函数,这种“只取value”的做法没有问题。可是递归就要继续调用一个函数,而且那个函数不是别人,就是这个函数自身啊!然而现在没有了保存自身的那个变量,还怎么继续呢?

把自身传进来

最直接的想法是,既然要用到一个函数(自身),那就把它当作参数传进来好啦。于是就有了

(lambda (self l)
  (cond [(null? l) 0]
        [else (add1 (self (cdr l)))]))

为了能够方便后面的分析,我们不妨把这个函数写成curried的形式,然后给它起名叫做“参数化的length”。写出来就是

(lambda (self)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 (self (cdr l)))])))

这种思想是好的,但其实无论是否curried,上面的实现都存在一个问题。以curried版本为例,一共4行代码,定义了一个匿名函数。这个匿名函数依次需要两个参数。第二个参数l不必多说,是我们想求长度的list。第一个参数self目的是想把这个匿名函数自身当作传递进来。可是既然self想指向的就是这4行的匿名函数自身,那self和这个匿名函数就应该以相同的方式被调用。那么匿名函数是如何被调用的呢?本段前面刚刚说过,“依次需要两个参数……”。然而第4行里面,self只有一个参数。匿名函数和self的调用方式不一样,这显然行不通。所以我们修改self的调用,给它加多一个参数,于是curried版本现在就变成了

(lambda (self)
  (lambda (l)
    (cond [(null? l) 0]
          [else (add1 ((self self) (cdr l)))])))

现在匿名函数和self的函数signature一致了,我们的无define版求list长度的函数也就(几乎)写好了。关键的问题来了:怎么使用它呢?嗯……要(依次)传两个参数,第一个是这个函数自己,第二个是想要求长度的list。等一下,什么叫做“传这个函数自己做参数”?答案简单得令人惊讶——没有绑定变量名不要紧,把这个函数复制、粘贴一份到参数的位置就可以了。所以,要求'(a b c)的长度,只需要

(((lambda (self)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 ((self self) (cdr l)))])))
  (lambda (self)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 ((self self) (cdr l)))]))))
 '(a b c))

复制到解释器里试一下。怎么样?答案是不是3呢?我们当然也可以用它求'(a)'(a b)等的长度。换言之,如果把这最后一个参数拿走,去掉最外面这层函数应用,我们就有了一个可以工作的求list长度的函数:

((lambda (self)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 ((self self) (cdr l)))])))
 (lambda (self)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 ((self self) (cdr l)))]))))

大功告成!回过头来看,其实我们的思路非常简单、清晰。

  1. 所谓递归,就是调用自身。
  2. 没有自身,那就把它传进来。
  3. 如何传?形参随便取一个变量名(比如self)就行。实参呢?把这个函数复制粘贴一遍就可以了。

从length到Y Combinator

到此为止,我们已经成功地在没有define的语言里实现了一个递归函数length。但仔细想想,这种策略其实不仅适用于length,也可用来实现其他的递归函数——无非就是传多一个参数,复制粘贴一遍自己嘛。所以,我们已经一劳永逸地解决了所有递归函数了!

话虽如此,不能否认的是,这种方式定义的递归函数使用起来很不方便。以我们的length为例(姑且称为length吧,虽然它其实没有被绑定到任何变量名)。首先,为了定义它,程序员必须将函数体复制粘贴一遍,造成了大量的重复代码。其次,要想用length求长度,它必须接受两个参数,第一个是一个函数(复制粘贴的自身),第二个是要求长度的list;但从语义上来说,length理应只接受一个list,其他所有与实现相关的复杂性都应该被封装起来。

先来解决第一个问题。宏观地从形式上看,用上面的函数是类似(f f)的一个函数应用,只不过这里的f比较复杂,需要替换为一个长长的lambda表达式罢了。由于出现了两次f,也有了两个长长的lambda表达式。能不能只写一次lambda表达式呢?可以!只要把(f f)这个模式抽象出去,成为一个新的函数就可以了:

((lambda (g)
   (g g))
 f)

 ;; where f =
 ;; (lambda (self)
 ;;   (lambda (l)
 ;;     (cond [(null? l) 0]
 ;;           [else (add1 ((self self) (cdr l)))])))

注意,现在的实现里面虽然仍然有(g g)这种重复,但这两个g都是形参,真正的实参是f。也就是说,f才是那个长长的lambda表达式。如果我们把f替换掉,得到的是:

((lambda (g)
   (g g))
 (lambda (self)
    (lambda (l)
      (cond [(null? l) 0]
            [else (add1 ((self self) (cdr l)))]))))

怎么样,和之前的版本相比,是不是只有一个长lambda表达式,其他地方简短了许多?试试看,它是不是也能正常工作?

再来处理第二个问题。应该讲,由于有了刚刚的一层抽象,这“传两个参数”的问题似乎已经不是什么大问题了。我们完全可以把上面6行代码整体当作一个函数,它只接受一个参数,就是想求长度的list。但是,在函数体的第6行,递归调用的部分仍然有(self self)这样让人恼火的实现。能不能把它也干掉呢?

我们可以照猫画虎,对比着刚刚的经验来做。上面是(f f)形的表达式,其中f是长长的lambda;我们把f抽象出去做实参,从而只需要写一次f。这一回还是(f f)形的表达式,但这次我们想整个地把(f f)都抽象出去做实参,从而把递归调用的部分化简为一个简单的形参变量,比如h。一种可能的做法是:

;; 方法1
((lambda (g)
   (g g))
 (lambda (self)
   (lambda (l)
     (cond [(null? l) 0]
           [else ((lambda (h) (add1 (h (cdr l))))
                  (self self))]))))

这种实现里面,抽象出的lambda只在else分支。或者我们也可以把它往外移一些,放在整个cond之外,变成

;; 方法2
((lambda (g)
   (g g))
 (lambda (self)
   (lambda (l)
     ((lambda (h)
        (cond [(null? l) 0]
              [else (add1 (h (cdr l)))]))
      (self self)))))

究竟是方法1还是方法2更好一些呢?一般来说,似乎方法1更合适,因为在方法1里面,h这个变量名起作用的的scope相对小一些,所以对其他部分的影响也小一些。不过方法2也有自己的优势:在这种实现里面,作为实参的(self self)不依赖于(null? l)的运行结果。在某种程度上,这也是耦合度的一种降低。

其实,方法1和方法2都还算得上是“温和”。对于方法1,我们更进一步设计一个方法0,把lambda抽象从add1外面移到里面,h的scope就更加缩小了。对于方法2,我们也能把lambda继续外移。考虑到实参(self self)l这个变量名都用不着,lambda可以移出l的绑定,变成下面的方法3:

;; 方法3
((lambda (g)
   (g g))
 (lambda (self)
   ((lambda (h)
      (lambda (l)
        (cond [(null? l) 0]
              [else (add1 (h (cdr l)))])))
    (self self))))

这段代码还有点小问题,如果直接复制到解释器里,会陷入无限的递归无法退出。不过我们待会儿再来解决这个问题。先仔细看看方法3,有没有觉得有些部分似曾相识?没错,中间几行代码除了参数名不同,跟前面提到的“参数化的length”一模一样!这启发我们,会不会这几行代码就已经包含了实现length需要的所有信息?如果把它们抽象出去,剩下来的部分会不会是一个common pattern,可以用来处理所有的递归函数?为了验证这个想法,我们需要先解决前面提到的无限递归的问题。

为什么从方法2到方法3,会出现无限递归的问题呢?直观上看,两者都需要执行函数应用(g g),形参g都会被替换为(lambda (self) ...。为了简洁,可以先只替换第一个g,那么这个函数应用就可以写成类似((lambda (self) ...) g)的形式。显然,为了完成函数应用,需要把...里面的self进一步替换成g。也正是在这儿,方法2和方法3出现了分歧。

方法2中,把self替换成g之后,函数应用的结果是一个lambda,即(lambda (l) ...,这意味着求值到此返回一个closure就结束了,被lambda包起来的运算会被延迟。而到了方法3,函数应用的结果是((lambda (h) ...。注意,开头是两个括号,换言之,是一层新的函数应用,其中函数部分是(lambda (h) ...),实参部分是(self self)。既然是应用,求值到此并没有结束,只能继续计算。先看实参部分。前面说了,self要被替换成g,所以实参部分的(self self)其实又是一个(g g),这相当于回到了上一段。如此往复,无限递归就产生了。

怎么解决这个问题呢?我们注意到,用lambda包起来的运算会被延迟,而(self self)的求值结果又恰好是一个函数。这启发我们利用lambda演算里的η展开,将(self self)转化为一个lambda。具体而言,就是等价地写为(lambda (x) ((self self) x))。从功能上讲,它跟(self self)是一样的,都是给它一个参数x,它就返回将(self self)作用于x的结果。但在求值顺序上,只要不真的给出这个x让它求结果,那么包在lambda里面的(self self)就永远不会被求值。所以,修正过的方法3就变成了:

((lambda (g)
   (g g))
 (lambda (self)
   ((lambda (h)
      (lambda (l)
        (cond [(null? l) 0]
              [else (add1 (h (cdr l)))])))
    (lambda (x) ((self self) x)))))

然后就可以继续刚刚的想法了,把“参数化的length”那部分也变成一个参数抽象出去。刚刚已经使用过了fgh,再往后该排到i,但是i貌似不像个函数,所以这一次我们折回去用f作形参:P

((lambda (f)
   ((lambda (g)
      (g g))
    (lambda (self)
      (f (lambda (x) ((self self) x))))))
 (lambda (h)
   (lambda (l)
     (cond [(null? l) 0]
           [else (add1 (h (cdr l)))]))))

现在那个common pattern已经很明显了,就是

(lambda (f)
  ((lambda (g)
     (g g))
   (lambda (self)
     (f (lambda (x) ((self self) x))))))

不妨把self换成h,稍稍整理下:

(lambda (f)
  ((lambda (g) (g g))
   (lambda (h) (f (lambda (x) ((h h) x))))))

这就是传说中的Y combinator了。我们把它作用在参数化的length身上,得到的就是真正的length;把它作用在另外一个参数化的递归函数例如max-in-list-parameterized身上,就能得到真正的max-in-list。不信你试试:)


附录

max-in-list验证Y

先尝试写出来递归的版本。为了防止命名的混淆,加个前缀,叫做recursive-max-in-list

(define recursive-max-in-list
  (lambda (l)
    (if (= 1 (length l))
        (car l)
        (max (car l) (recursive-max-in-list (cdr l))))))

recursive-max-in-list改成参数传进去,就可以得到参数化的版本。

(lambda (self)
  (lambda (l)
    (if (= 1 (length l))
        (car l)
        (max (car l) (self (cdr l))))))

定义有5行,有点长,来回复制粘贴太麻烦,所以干脆给起个名字max-in-list-parameterized

(define max-in-list-parameterized
  (lambda (self)
    (lambda (l)
      (if (= 1 (length l))
          (car l)
          (max (car l) (self (cdr l)))))))

同样,给Y combinator也起个名字,叫做Y

(define Y
  (lambda (f)
    ((lambda (g) (g g))
     (lambda (h) (f (lambda (x) ((h h) x)))))))

好了,万事俱备,现在可以定义max-in-list了。

(define max-in-list (Y max-in-list-parameterized))

实验一下,看看max-in-list能不能用?

> (max-in-list '(1 5 8 3 4))
8

Yeah~!!

简化Y

上面的Y combinator虽然已经能用了,但是跟多数教科书、维基百科里面看到的形式还有一点差别。两者本质上是等价的,我们不妨来化简一下看看。

为了摆脱无限递归,刚刚我们做了一次η展开,体现Y当中,就是下面标注的部分。

(lambda (f)
  ((lambda (g) (g g))
   (lambda (h) (f (lambda (x) ((h h) x))))))
                  ^^^^^^^^^^^^^^^^^^^^^

用η规约化简回去,就得到了

(lambda (f)
  ((lambda (g) (g g))
   (lambda (h) (f (h h)))))

注意,这么做是有代价的。一旦应用到参数化的length或者max-in-list上,会再次陷入无限递归。这是由Scheme的call-by-value求值规则决定的。不过为了得到经典的Y combinator形式,我们暂且忽略它。下面把h换个变量名x,得到:

(lambda (f)
  ((lambda (g) (g g))
   (lambda (x) (f (x x)))))

然后把和g有关的那次函数应用展开(事实上这又是我们前面一次变形的逆操作)。

(lambda (f)
  ((lambda (x) (f (x x)))
   (lambda (x) (f (x x)))))

当当当~!正牌Y combinator闪亮登场!!

comments powered by Disqus