Lambda初级简介 - Y组合子

子又生孙,孙又生子,子子孙孙无穷匮也。

不用函数名,就能实现递归吗?

​ 上篇我们成功构建了最基本的运算系统,可以编写特定算法了。可是,正当我们试图用最基本的递归实现阶乘的时候,我们发现,似乎λ演算里并不支持我们熟悉的,基于有名函数的递归。先前也已经说过,函数名只是一个小把戏,并不是λ演算所必须的。那么,如果没有函数名,递归还能被实现吗?

​ 答案当然是肯定的,λ演算若连递归都无法实现,那么要它何用(笑)。

​ 仔细想一想,如果我有一个函数,这个函数接受自己作为参数,然后执行参数传入参数,就可以实现最简单的递归。比如:

1
(λx.x x)(λx.x x)

​ 显而易见,如果将其展开,结果就是(λx.x x)被调用了无限次。不过,此处的x不过是用来递归的函数,是整个递归的主心骨,但是我们递归是要有目的的,是要有一个函数传递进去随着x的调用被调用的。应该怎么做呢?很简单,就如上文所述,假定我们的递归元函数(递归的中心部分)利用接受一个自身作为函数来进行递归的话,那么x x则返回(λx.x x),所以很简单,我们只要将x x作为参数传入我们的函数,在我们的函数里调用这个参数,我们就能实现递归了。所以,新的函数定义为:

1
λf.(λx.f(x x))(λx.f(x x))

​ 这就是大名鼎鼎的Y组合子!上述文字通过定义的方法解释了Y组合子的由来,下面我来详细介绍一下这个由Haskell B. Curry发明的Y组合子。Y组合子是λ演算里最著名的不动点组合子;不动点组合子,是用来计算其他函数的不动点的高阶函数(接受一个或多个函数,返回一个函数的函数)。不动点,就是一个函数里传入参数等于返回参数的参数。举个例子,函数f=x^2的不动点就是0和1,因为f(0)=0,f(1)=1。一阶函数的不动点为一阶值,那么高阶函数的不动点自然是高阶值,也就是函数。所以,综上所述,Y组合子的作用应该是g = Y(g),并不断展开Y内的参数g,以实现递归展开g的效果。下面就来亲自试一试吧!

1
2
3
4
5
6
7
Y := λf.(λx.f(x x))(λx.f(x x))
Y g
(λf.(λx.f(x x))(λx.f(x x))) g # 代换Y的定义
(λx.g(x x))(λx.g(x x)) # 应用β-归约
g((λx.g(x x))(λx.g(x x))) # 应用β-归约
g(Y g) # 代换Y g
g(g(Y g)) = g(g(g(Y g))) # 永远...

​ 就是这样。那么下面来看看阶乘的实现吧!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
FACT := λn.IF (ISZERO n) 1 (mul n (FACT (pre n)))	# 我们上次写的阶乘函数
FACT := λf.λn.IF (ISZERO n) 1 (mul n (f (pre n))) # 根据需要改成使用Y组合子的模式
# 对于FACT, 下面的展开过程将不会处理其中的过程, 直接返回结果.
# Let's rock and roll!
g := FACT # 简化一些
g(Y g)3
IF (ISZERO 3) 1 (mul 3 ((Y g) (pre 3)))) # 代换并应用
3 * (g(Y g)2) # Y g展开为g(Y g), pre 5代换结果为4
3 * (IF (ISZERO 2) 1 (mul 2 ((Y g) (pre 2))))) # 同理
3 * (2 * (g(Y g)1))
3 * (2 * (IF (ISZERO 1) 1 (mul 1 ((Y g) (pre 1))))))
3 * (2 * (1 * (g(Y g)0)))
3 * (2 * (1 * (IF (ISZERO 0) 1 (mul 0 ((Y g) (pre 0)))))))
3 * (2 * (1 * (1))) = 3 * 2 * 1 = 3! # 最终结果符合定义!

​ 完美!

​ 现在,回想我们在邱奇数那章曾经使用的JavaScript,现在让我们用JavaScript实现个Y组合子!

​ 处于方便考虑,我们不使用邱奇数和邱奇布尔,直接用JavaScript内置的更加方便我们感受Y组合子和接下来的一切。

1
2
3
FACT = f => n => n < 2 ? 1 : n * f(n - 1);
Y = f => (x => f(x(x)))(x => f(x(x)));
FACT(Y(FACT))(3)

​ 然后我们高兴的打开console,输入这些代码,敲下了回车。结果却报错“Maximum stack size exceeded”。这是因为什么呢?难道我们写错了吗?并不是,这个原因其实很简单。我们知道,在处理λ表达式的时候,我们是直接用整个函数体去当做参数去应用到其他函数里面去,比如说我们把Y g展开成g(Y g),这其中就是直接把g的函数定义代入Y函数内,这种传值方式叫做传名策略,他不要求参数表达式一定要被计算出来,仅仅将参数表达式直接代入即可。而JavaScript这种传统的机器编程语言,他的传值方式是传值策略,就是一定要把参数表达式计算出来的一种传值方式。这样,我们在λ演算里可以毫无压力地展开g,代入参数(Y g)和3,然后求出3*(g(Y g))来,逐次类推。而在JavaScript里,必须求值。那么FACT(Y(FACT))(3)则必须先把Y(FACT)进行求值,而显然这会陷入无穷递归,直到爆栈……

​ 那么怎么办呢?当然,伟大的先辈们已经给我们想好了主意,Y组合子还有一种挺有名的变体,名字叫Z组合子,她就是用来专门处理传值调用的问题的。在介绍Z组合子之前,我们先来看一条归约。可能你会说,归约不就是两条吗?没错,基础归约的确只有两条,但是我们接下来要介绍的η-变换是对归约的一种补充。

​ η-变换是外延性的表达,通过集合论的外延公理,两集合相等当且仅当其包含相同元素,这条定义,我们就很好理解在函数里的外延性指的是,两函数相等当且仅当其对公共函数域内所有变量的映射相等。也就是说如果f(x) = g(x),那么f=g。所以,η-变换的定义是,两个函数对于所有参数结果一致,则两函数相等或同一函数。用λ表达式来表达,就是:λx.f x和f等价,当x不在f中自由出现时。

​ 所以,如果要让Y组合子内的f接受一个参数,毫无疑问应该在x x外侧嵌套一个接受v的函数。他会将参数展开到下阶段表达式的右侧,从而令f接受这个参数而不用使用传名策略,同时这个嵌套的函数根据η-变换也是等价于原表达式的。Z组合子的定义是:

1
Z := λf.(λx.f(λv.(x x)v))(λx.f(λv.(x x)v))

​ 由于v的存在,所以求值必须引入参数,在非传名策略以及非不严格类型的情况下也不会发散。让我们在JavaScript里实现:

1
2
3
FACT = f => n => n < 2 ? 1 : n * f(n - 1);
Z = f => (x => f(v => (x(x))(v)))(x => f(v => (x(x))(v)));
Z(FACT)(10);

​ 运行完美!

​ 你可能在想,既然存在Y组合子、Z组合子,那么就一定存在其他高阶函数,也就是组合子。没错,λ演算的魅力还远远不止这些。请看下回揭晓。