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组合子，那么就一定存在其他高阶函数，也就是组合子。没错，λ演算的魅力还远远不止这些。请看下回揭晓。