Lambda初级简介 - 组合子演算

发表于 | 更新于 | 分类于

简单易懂的现代魔法

抽象函数的固定模型，固定模型的计算系统

​ 上次我们介绍了Y组合子和Z组合子，那么可能有人想要问了，有没有其他的组合子呢？当然有，根据维基百科介绍，目前普遍接受的λ组合子有：

1
2
3
4
5
6
7
8
9
10
I := λx.x
K := λx.λy.x
S := λx.λy.λz.x z (y z)
B := λx.λy.λz.x (y z)
C := λx.λy.λz.x z y
W := λx.λy.x y y
U := λx.λy.y (x x y)
ω := λx.x x
Ω := ω ω
Y := λg.(λx.g (x x)) (λx.g (x x))

​ 可以看到，ω组合子正式我们在上篇推导Y组合子的中间产物。不过我们这节要介绍的组合子演算，是由S、K、I组成的演算系统。其他组合子不在初级简介的范畴内。SKI演算系统，有时候称为SK基演算，这是因为用S、K可以做到和I一样的效果，两者是外延相等（注意外延相等不等于函数自身相同，使用等价一词以区分项相同使用的相等）。用S、K表达I的方法是：

1
2
3
4
5
6
7
8
((S K K) x)
((λz.K z(K z)) x)	# 根据定义
(K x (K x))			# 应用x
(K x)				# 根据定义
x					# ((S K K) x) = x
I x					# = I x
# 所以对于任意项x, ((S K K) x) = I x
# 所以(S K K)和I外延性等价

​ S和K的定义都十分简单，但是证明表示，是用S、K可以组合成任何λ项！这就是说消除了λ演算里面函数定义的抽象过程，可以完全使用固定模型来表示任何函数！因为S、K组合子可以组合成任何λ项，λ演算可以计算任何可计算问题，所以，SKI演算系统是图灵完全的！拥有和λ演算等价的计算能力。

​ SKI演算系统（下文简称CC系统，Combinator Calculus，组合子演算）显然和λ演算息息相关，所以自然有将任意λ表达式转换成组合子表达式的方法。对于这种转换，我们定义一个变换函数T，T的定义如下（V为变量，E为项）：

  1. T[V] => V

  2. T[ (E1 E2) ] => ( T[E1] T[E2] )

  3. T[λx.E] => (K T[E] ) … 如果x在E中没有自由出现

  4. T[λx.x] => I

  5. T[λx.λy.E] => T[λx.T[λy.E]] … 如果x在E中自由出现

  6. T[λx.(E1 E2)] => (S T[λx.E1] T[λx.E2])

    利用这六个变换规则，我们就可以将λ表达式转换成组合子表达式，也就是通常说的，消除函数抽象。前四个规则是相当显然的。第五个规则则是表达如果x在E中自由出现时，x无法被立即转换消除掉，所以先转换其主体，然后利用规则6最终消除抽象。在规则6里，λx.(E1 E2)是一个接受一个参数并应用到E1 E2上，即等于(E1 E2)[x:=v]，据此可推导：

1
2
3
4
5
6
7
8
λx.(E1 E2) v
(E1 E2)[x:=v]			# 应用v
(E1[x:=v])(E2[x:=v])	# 分别代换v到E1E2上
((λx.E1 v)(λx.E2 v))	# 根据定义
(S λx.E1 λx.E2 v)		# S的定义
((S λx.E1 λx.E2) v)		# 抽出v
# 所以可得λx.E1 E2 等价于 S(λx.E1 λx.E2)
# 进而得出等价于(S T[λx.E1] T[λx.E2])

​ 如果接受η-变换的话，变换函数可以根据外延性定理增加一条：

  1. T[λx.E x] = T[E] … 如果x在E中没有自由出现

    我们也很容易接受一个函数：接受x并应用x于函数E，等价于函数E本身这种关系。

    这就是我要介绍的组合子演算的内容，现在用一次转换和应用来表演一下学到的新东西：

​ 转化λx y.(y x)到组合子表达式：

1
2
3
4
5
6
7
8
9
T[λx y.(y x)]
T[λx.λy.(y x)]
T[λx.T[λy.(y x)]]				# rule 5
T[λx.(S T[λy.y] T[λy.x])]		# rule 6
T[λx.(S I T[λy.x])]				# rule 4
T[λx.(S I (K x))]				# rule 3
(S T[λx.(S I)] T[λx.(K x)])		# rule 6
(S (K (S I)) T[λx.(K x)])		# rule 3
(S (K (S I)) K)		# rule 7!

​ 对于这个结果，我们可以验证：

1
2
3
4
5
6
(S (K (S I)) K)	x y
((K (S I)) x (K x)) y
(S I (K x)) y
(I y (K x y) )
(y (K x y))
(y x)

​ 完美！那么，这一系列就到此结束了！