Yet Another a Introduction to Y Combinator in Scheme

前言

在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 lengthdefine表达式将一个表达式(表达式即可能是函数也可能是值,在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了!
依此类推,我们能定义出length3length4length5,甚至length100length1000length10000了!
那么如果我们能写出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

对比一下我们的显式递归lengthnewlength:

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