Yifu's Blog
0%

Yet Another a Introduction to Y Combinator in Scheme

Posted on Edited on In

前言

在Lambda演算中，函数是没有名字的（都是匿名函数），那么如果函数没有名字，也就无法在函数体内显式地调用自身，也就无法定义递归函数，Y combinator就是用来解决这个问题的。
这篇文章想抛开那些数学概念，用程序语言（Scheme）的形式来讲解我们是如何推导出Y combinator的。

运行环境：
IDE：DrRacket

什么是递归函数？

我们以递归函数length为例，length函数接受一个list，返回list的元素数目。

1
2
3
4
5
(define length
  (lambda (lst)
    (if (null? lst)
        0
        (add1 (length (rest lst))))))

若你熟悉Scheme函数定义，可以跳过本小结后面部分。

(define length，define表达式将一个表达式（表达式即可能是函数也可能是值，在Scheme中并不区分这两点）绑定至一个名字，形式如同(define name func)，之后便可以使用name调用func这个函数。在本定义中，func是后面整个用括号包围的lambda表达式，也就是2-4行。
(lambda args body)，lambda表达式定义了一个匿名函数，表达式中第二个元素是参数列表，第三个元素是函数体。也就是说，这个匿名函数接受一个参数lst，然后对函数体进行求值。
(if condition then else),if表达式，若condition为真，则求值then，若condition为假，则求值else。
null?接受一个list，判断是否为空。
add1接受一个值，将其加1后返回，定义如下：

1
2
3
4
5
6
(define add1
  (lambda (n)
    (+ 1 n)))

> (add1 3)
4

rest返回lst去掉第一个元素的剩余部分，其实就是(define rest cdr)。
也就是说，length函数接受一个list，若list为空，则返回0，若list非空，则求去掉第一个元素的list长度，并将其加一。求值过程如下：

1
2
3
4
5
6
(length `(1 2)) ; `(1 2) is a list has two elements
(add1 (length `(2))) ; `(2) is (rest `(1 2))
(add1 (add1 (length `()))) ; `() is empty list
(add1 (add1 0))
(add1 1)
2

假如length没有名字？

如果我们去掉define，拿出其中的函数定义，是这样。

1
2
3
4
(lambda (lst)
    (if (null? lst)
        0
        (add1 (length (rest lst))))) ; length is undefined

**WAIT！！**既然现在没有了length,显然我们也无法在函数体内调用length了。
那么我们应该把length换成什么呢？
我也不知道。
那么我们先试一试换成别的吧。
假设我们现在有一个函数id,这个函数什么都不做，只接受一个参数并将其返回，定义如下。

1
2
3
4
5
(define id
  (lambda (x) x))

> (id 1)
1

那么，我们把id丢进length定义里面试试：

1
2
3
4
5
; length0
(lambda (lst)
    (if (null? lst)
        0
        (add1 (id (rest lst)))))

看上去是个奇怪的函数，这个函数能工作吗？
我们可以试一试。

1
2
3
4
5
6
7
> ((lambda (lst)
   (if (null? lst)
       0
       (add1 (id (rest lst)))))
 `())

0

我们喂给这个奇怪的函数一个空list，它居然能返回正确的值！
具体原因，请读者先自己思考一下（笑
。
。
。
很简单，因为(null? lst)为真，所以if表达式直接返回了0，压根没有对(add1 (id (rest lst)))进行求值。
那么我们如果喂(apple)呢，显然这个奇怪的函数并不能返回正确的长度，因为(id (rest lst))无法给出“去掉第一个值的list的长度”。
总结一下，这个奇怪的函数：

  • 若list长度为0，可以正常工作
  • 若list长度大于0，无法工作

那么，我们将这个函数叫做length0,代表它对长度为0及0以下（并不存在）的list可以正常工作。

length1, length2, and …

好了，我们现在有一个length0，可以求出空表的长度。
那么下面这个函数有什么作用呢？

1
2
3
4
5
; length1
(lambda (lst)
    (if (null? lst)
        0
        (add1 (length0 (rest lst)))))

由于(length0 (rest lst))是可以正确计算的，所以上面这个函数，可以计算长度小于等于1的list的长度。
你可能会问，但是我们没有length0这个名字呀？
没关系，我们将length0代换成上一小结的匿名函数形式，如下：

1
2
3
4
5
6
7
8
9
; length1
(lambda (lst)
  (if (null? lst)
      0
      (add1 ((lambda (lst)
               (if (null? lst)
                   0
                   (add1 (id (rest lst)))))
             (rest lst)))))

那么这个函数，我们就可以把它叫作length1了，因为它可以正确求出长度小于等于1的list的长度！
那么，length2就再来一次啦，把length1丢进那个定义，也不需要显式使用length2啦！

1
2
3
4
5
6
7
8
9
10
11
12
13
; length2
(lambda (lst)
  (if (null? lst)
      0
      (add1 ((lambda (lst)
               (if (null? lst)
                   0
                   (add1 ((lambda (lst)
                            (if (null? lst)
                                0
                                (add1 (id (rest lst)))))
                          (rest lst)))))
             (rest lst)))))

试一试length2！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> ((lambda (lst)
   (if (null? lst)
       0
       (add1 ((lambda (lst)
                (if (null? lst)
                    0
                    (add1 ((lambda (lst)
                             (if (null? lst)
                                 0
                                 (add1 (id (rest lst)))))
                           (rest lst)))))
              (rest lst)))))
 `(two apple))

2

真棒！现在能解决长度小于等于2的list了！
依此类推，我们能定义出length3、length4、length5,甚至length100、length1000、length10000了！
那么如果我们能写出length∞，不就得到了我们的原始length函数了吗，因为length是可以处理任意长度的list的函数！
但是，我们没办法写出length∞，因为无穷行代码哪里也放不下啊！（笑

试着进行抽象

试着观察length0 length1 length2，我们会发现，这三个函数都遵循相同的形式，只有last-length这个地方是需要改变的：

1
2
3
4
5
; same pattern
(lambda (lst)
    (if (null? lst)
        0
        (add1 (last-length (rest lst)))))

根据DRY原则，我们为什么不把相同的形式给抽象出来呢？
我们可以写出一个函数，接受一个参数last-length，然后就可以利用这个函数生成之后的length[i]了。
就像这样：

1
2
3
4
5
6
; abstract-length
(lambda (last-length)
  (lambda (lst)
    (if (null? lst)
        0
        (add1 (last-length (rest lst))))))

这个函数接受参数last-length,然后就会返回一个新的函数，可以比last-length多处理一个长度的list。
那么，length0可以表示为：

1
2
3
4
5
6
7
; length0
((lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst))))))
 (id))

那么同理，length1可以表示为：

1
2
3
4
5
6
7
; length1
((lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst))))))
 (length0))

当然，我们并没有length0,需要将其转换为匿名形式，也就是这样：

1
2
3
4
5
6
7
8
9
10
11
12
; length1
((lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst))))))
 ((lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst))))))
 (id)))

那么length2？
容易，再来一次：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
; length2
((lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst))))))
 ((lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst))))))
 ((lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst))))))
 (id))))

**WAIT!!!**这难道不是依然在重复增加代码吗？
好吧，其实我们还是有所推进，别急，慢慢来。

返回length函数的函数：make-length

按照我们刚刚的抽象，abstract-length：

1
2
3
4
5
6
; abstract-length
(lambda (last-length)
  (lambda (lst)
    (if (null? lst)
        0
        (add1 (last-length (rest lst))))))

对于这个函数，我们如果：

  • 喂给它id,即(abstract-length id)，那么它会返回length0
  • 喂给它length[i]，即(abstract-length length[i])，那么它会返回length[i+1]
    既然这个函数能够返回我们需要的length[i],不妨将其称之为make-length函数。
    那就可以写成函数应用的形式，就像我们对last-length的抽象：
1
2
3
4
; length0
((lambda (make-length)
   (make-length id))
 abstract-length)

依然运用我们的old trick，将abstract-length写成匿名形式：

1
2
3
4
5
6
7
8
; length0
((lambda (make-length)
   (make-length id))
 (lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst)))))))

好了，虽然这个形式看上去很复杂，但是它就是我们熟悉的length0!
那么，length1呢？
很简单，我们只需要将length0喂给我们的abstract-length，就会得到length1。也就是将length0中的id替换成length0：

1
2
3
4
; length1
((lambda (make-length)
   (make-length length0))
 abstract-length)

换成匿名表达：

1
2
3
4
5
6
7
8
; length1
((lambda (make-length)
   (make-length (make-length id)))
 (lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst)))))))

再进一步，length2：

1
2
3
4
5
6
7
8
; length2
((lambda (make-length)
   (make-length (make-length (make-length id))))
 (lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst)))))))

那，length3？

1
2
3
4
5
6
7
8
; length3
((lambda (make-length)
   (make-length (make-length (make-length (make-length id)))))
 (lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst)))))))

好了好了，就不再继续演示了。
那么回顾一下我们的新表示方法，好像它们之间的差别，仅仅在于对参数id应用了多少次make-length函数：

  • length0: (make-length id)
  • length1: (make-length (make-length id))
  • length2: (make-length (make-length (make-length id)))
  • length3: (make-length (make-length (make-length (make-length id))))

是不是有点类似汉诺塔？

快到终点了

事实上，每当我们使用length函数，我们并不会给它一个无限长的list。
那么，只要我们用一个足够大的length[i]，可不可行呢？按照我们上一小节的抽象，我们可以轻易地写出length100，甚至length10000000000000000。
问题在于，这个足够大的数，仍然可能不够大。

那么什么时候我们会知道，这个数不够大呢？
显然，当我们需要用到最最最最内层的函数id，也就是计算(id (rest lst))的时候，就代表，这个数不够大了。

**注意：**我们喂给length2一个长度小于等于2的list时，id的函数应用是没有求值的。

那么，如果每当我们需要对id的函数应用求值的时候，我们再对其应用一次make-length，不就可以避免对id的函数应用求值了吗？

那么，如果我们从不对id的函数应用求值，也就是说，id根本没什么用，我们可以把任意函数传递给最内层的make-length。

那么，为何不试一试把make-length作为最内层的参数传给make-length呢。
那么，length0:

1
2
3
4
5
6
7
8
; length0
((lambda (make-length)
   (make-length make-length))
 (lambda (last-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (last-length (rest lst)))))))

回过头来看，其实last-length也是接受一个参数length[i]，然后返回新的函数length[i+1]。

那不是和make-length一样了？
是这样。
那我们将last-length改名为make-length也可以吗？
可以。只要保持函数参数和函数体内的名字一致即可。
那我们改名吧：

1
2
3
4
5
6
7
8
; length0
((lambda (make-length)
   (make-length make-length))
 (lambda (make-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (make-length (rest lst)))))))

进一步，依照刚刚所说，我们只需要将length1中最内层的函数应用添加一层

1
2
3
4
5
6
7
8
; length1
((lambda (make-length)
   (make-length make-length))
 (lambda (make-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 ((make-length id) (rest lst)))))))

等等？为什么id又出现了？
因为我们只能处理长度小于等于1的list。
如何解决此困境？
再次将make-length传递给自身，这样每当我们需要更长的length[i]的时候，就会自动将函数的处理能力+1。
就像这样：

1
2
3
4
5
6
7
8
; length1
((lambda (make-length)
   (make-length make-length))
 (lambda (make-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 ((make-length make-length) (rest lst)))))))

这个函数的工作机理是，它展开的层数总是和喂给它的list长度一样多。因为一旦层数不够长，他就会将make-length应用于自身，增加多一次的处理。

试一试length1能否工作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
> (((lambda (make-length)
    (make-length make-length))
  (lambda (make-length)
    (lambda (lst)
      (if (null? lst)
          0
          (add1 ((make-length make-length) (rest lst)))))))
 `(apple))

 1

 > (((lambda (make-length)
    (make-length make-length))
  (lambda (make-length)
    (lambda (lst)
      (if (null? lst)
          0
          (add1 ((make-length make-length) (rest lst)))))))
 `(two apple))

 2

很好，我们得到了一个能工作的length1，事实上，这已经不再是length1了，因为它能处理长度为2的list！甚至更长的！
这就和我们最初的length一样了！

（如果你不明白这里的length1为何能工作，可以试着再读一读这两个小节，或者手动推演一下这个lambda式子）

不止应用于length

对比一下我们的显式递归length和newlength:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
; length
(define length
  (lambda (lst)
    (if (null? lst)
        0
        (add1 (length (rest lst))))))

; newlength
((lambda (make-length)
   (make-length make-length))
 (lambda (make-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 ((make-length make-length) (rest lst)))))))

这两个定义在形式上还是有差别，因为前者定义中的(length (rest lst))，在后者定义中变成了((make-length make-length) (rest lst))。

为了使它们表现的一致，我们将(make-length make-length)抽象出来就好了，然后作为参数传进去，而且我们将参数取名为length！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
; length
(define length
  (lambda (lst)
    (if (null? lst)
        0
        (add1 (length (rest lst))))))

; newlength
((lambda (make-length)
   (make-length make-length))
 (lambda (make-length)
   ((lambda (length)
    ;;;;;;;
     (lambda (lst)
       (if (null? lst)
           0
           (add1 (length (rest lst))))))
    ;;;;;;;
   (make-length make-length))))

好了，看上去大功告成，可以把两个定义在形式上相同的地方抽象出来，这样就可以用在别的递归函数定义中了。

WAIT！还没完，我们试着用一用newlength，试着对(apple)求值：

1
2
3
4
5
6
7
8
9
10
> (((lambda (make-length)
    (make-length make-length))
  (lambda (make-length)
    ((lambda (length)
       (lambda (lst)
         (if (null? lst)
             0
             (add1 (length (rest lst))))))
     (make-length make-length))))
 `(apple))

我们需要将这个表达式的值求出来，然后应用到(apple)上

1
2
3
4
5
6
7
8
9
10
11
12
13
((lambda (make-length)
   (make-length make-length))
 ; A-start
 (lambda (make-length)
   ((lambda (length)
      (lambda (lst)
        (if (null? lst)
            0
            (add1 (length (rest lst))))))
    (make-length make-length)))
 ; A-end
 )

首先我们需要将(lambda (make-length) (make-length make-length))应用于后面那个式子(记作A)上，得到(A A)，即：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(
 ; B-start
 (lambda (make-length)
   ((lambda (length)
      (lambda (lst)
        (if (null? lst)
            0
            (add1 (length (rest lst))))))
    (make-length make-length)))
 ; B-end
 ; C-start
 (lambda (make-length)
   ((lambda (length)
      (lambda (lst)
        (if (null? lst)
            0
            (add1 (length (rest lst))))))
    (make-length make-length)))
 ; C-end
 )

然后继续求值，将B应用于C，也就是将B的参数make-length用C进行代换，得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

(
 ; D-start
 (lambda (length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (length (rest lst))))))
 ; D-end
 ; E-start
 ((lambda (make-length)
    ((lambda (length)
       (lambda (lst)
         (if (null? lst)
             0
             (add1 (length (rest lst))))))
     (make-length make-length)))
  (lambda (make-length)
    ((lambda (length)
       (lambda (lst)
         (if (null? lst)
             0
             (add1 (length (rest lst))))))
     (make-length make-length))))
 ; E-end
 )

现在我们得到了形如(D E)的式子，然后我们继续求值，你会注意到，E的形状和刚刚我们得到的(A A)形状是一样的，所以我们会在这里一直循环下去。

这就很奇怪了，我们在把(make-length make-length)抽象出来之前函数都是好的呀？

回想一下，make-length的作用是生成一个新的length[i+1]函数，然后将其应用于一个list。
但是我们把(make-length make-length)抽象出来之后，我们无法得到这个length[i+1]函数，因为Scheme是应用序求值策略，make-length反复对自身进行应用。
因此，我们要想一个办法，先让make-length的应用停一停，等到需要它对自身进行应用的时候，再继续。
这个方法并不复杂，就是将(make-length make-length)包裹在一个lambda表达式之中，即(lambda (x) ((make-length make-length) x))。

1
2
3
4
5
6
7
8
9
; newlength
((lambda (make-length)
   (make-length make-length))
 (lambda (make-length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 ((lambda (x) ((make-length make-length) x))
                (rest lst)))))))

然后我们再把它抽象出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
; new newlength
((lambda (make-length)
   (make-length make-length))
 (lambda (make-length)
   (
    ;;;;;;
    (lambda (length)
      (lambda (lst)
        (if (null? lst)
            0
            (add1 (length (rest lst))))))
    ;;;;;;
    (lambda (x) ((make-length make-length) x)))))

; length
(define length
  (lambda (lst)
    (if (null? lst)
        0
        (add1 (length (rest lst))))))

这样，我们就得能正确使用的newlength了，就能继续我们的抽象工作了。

对比一下newlength和原始length，使用“;;;;;;”分隔开的部分，完全就是原始length的定义，除了将原始length定义中的define替换成lambda。而且这部分，和make-length完全无关！

那么，我们将这部分抽象出来，使其变成一个函数应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(
 ; Y-start
 (lambda (a-func)
   ((lambda (make-length)
      (make-length make-length))
    (lambda (make-length)
      (a-func (lambda (x)
                ((make-length make-length) x))))))
 ; Y-end
 ; F-start
 (lambda (length)
   (lambda (lst)
     (if (null? lst)
         0
         (add1 (length (rest lst))))))
 ; F-end
)

现在我们有了两部分，Y和F：

  • Y部分是一个函数，它接受一个和原始length具有相同形式的函数，然后返回一个递归函数length；
  • F部分，就是和原始length形式相同的匿名函数啦。

那么这个Y部分，就是我们的Y combinator！一般被称作应用序Y combinator。
化简一下：

1
2
3
4
5
6
7
; applicative-order Y combinator
(lambda (func)
  ((lambda (f)
     (f f))
   (lambda (f)
     (func (lambda (x)
             ((f f) x))))))

有了Y combinator，我们就能从匿名函数中定义递归函数了！

练习

你能写出一个简单的阶乘函数factorial，然后用Y combinator将其变成匿名递归函数吗？

参考

  1. The Little Schemer
  2. Fixed-point combinator - Wikipidia
  3. Normal Order and Applicative Order - SICP