另发表于知乎。
作为FP的基础,Lambda 演算将一切视为函数,对函数进行演算。
Lambda 演算本是 Church 为解释停机问题而提出,与 Turing 的解释并列。
Lambda-Calculus
Lambda 演算用三个语法构建合法的表达式。
| 语法 | 解释 |
|---|
| x | 一个对象,可以替换为任何字母。 |
| λx.( ) | 一个以 x 为变量的函数,括号作为返回值。 |
| ( )( ) | 将左侧括号视为函数,右侧括号视为变量,进行一次应用。 |
括号可以替换为三个语法之一。一个合法例子是 λa.(λb.(ab)) 。
Lambda 演算中最基本的对象是恒等函数 λx.x 。
Beta-Reduction
通过 Beta 归约可以进行表达式求值。
例如,对于一个表达式 (λx.(λy.(xy)))a ,即将 a 应用于函数
λx.(λy.(xy)) ,对它进行 Beta 归约的步骤如下:
- 函数以 x 为变量,而 x 的值为 a 。
- 只保留表达式中的函数体 λy.(xy) 。
- 将 x 替换为 a ,即为 λy.(ay) 。
由此完成了一次 Beta 归约,得到了新函数 λy.(ay) 。这个新函数接受一个 y 为变量,返回 y 应用于 a 的结果。
为了让函数接受多个参数,可以应用 Currying 思想。形式上,可以这样定义加法函数(事实上,由于我们还没有定义什么是“整数”,无法给出加法定义。关于加法的合法定义见整数。):
PLUS:=λx.(λy.(x+y))
计算 3+5 的值,需要计算 (PLUS 3)5 ,也即 ((λx.(λy.(x+y)))3)5 ,要进行两次 Beta 归约:
Boole 逻辑
Lambda 演算中,TRUE 和 FALSE 定义为接受两个参数的参数选择器:
TRUE:=λx.(λy.x)
FALSE:=λx.(λy.y)
TRUE 选择第一个参数,FALSE 选择第二个参数。
例如,对 (TRUE a)b 进行 Beta 规约:
- 先展开:((λx.(λy.x))a)b 。
- 代入 a : (λy.a)b 。
- 代入 b : a ,确实选择了第一个参数。
可以实现 Boole 运算:
| 函数 | 解释 |
|---|
| NOT:=λa.((a FALSE)TRUE) | 非:当 a 为 TRUE 时,选择 FALSE,否则选择 TRUE 。 |
| AND:=λa.(λb.((a b)FALSE)) | 与:当 a 为 TRUE 时,选择 b,否则选择 FALSE 。 |
| OR:=λa.(λb.((a TRUE)b)) | 或:当 a 为 TRUE 时,选择 TRUE,否则选择 b 。 |
这些 Boole 运算可以得到 TRUE 或 FALSE ,以用来选择其他变量。
整数
Lambda 演算将整数视作函数。函数接受两个参数,一个是 f ,一个是 x 。整数将 x 作为变量应用于 f 多次,应用次数即为整数值:
0:=λf.(λx.x)
1:=λf.(λx.(fx))
2:=λf.(λx.(f(fx)))
3:=λf.(λx.(f(f(fx))))
这样定义的好处之一是,可以方便地定义加法,但是先让我们定义后继:
SUCC:=λn.(λf.(λx.((nf)x)))
将 n 传入 SUCC 后,得到的函数 n+1 次将 x 应用于 f ,即得到了 n+1。因此,自然地得到加法:
ADD:=λa.(λb.((a SUCC)b))
乘法(例如 a∗b )有更容易理解的定义,因为它相当于将 b 应用 a 次:
MUL:=λa.(λb.(λf.(a(bf))))
幂的定义比较紧凑:
POW:=λa.(λb.(ba))
它表示将 a 复合 b 次,例如,计算 (POW 2)3 :
- 代入 POW : 3 2 。
- 代入 3 和 2 : (λa.(λb.(a(a(ab)))))(λc.(λd.(c(cd)))) 。
- 归约:λb.((λg.(λh.(g(gh))))((λe.(λf.(e(ef))))(λd.(b(bd))))) 。
- 归约:λb.((λg.(λh.(g(gh))))(λf.((λd.(b(bd)))(b(bf))))) 。
- 归约:λb.((λg.(λh.(g(gh))))(λf.(b(b(b(bf)))))) 。
- 归约:λb.(λh.((λf.(b(b(b(bf)))))(b(b(b(bh)))))) 。
- 归约:λb.(λh.(b(b(b(b(b(b(b(bh))))))))) 。
- 变量重命名:λf.(λx.(f(f(f(f(f(f(f(fx))))))))) 。
可见 (POW 2)3=8 。
递归与 Turing 不动点组合子
可以采用递归的形式表达阶乘函数:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
假设我们有了一个可以判断变量是否为 0 的函数 IS_ZERO ,形式上,阶乘函数应该写为:
FAC=λn.(((IS_ZERO n)1)((×n)(FAC((−n)1))))
但是这是不合法的,包含了递归调用。
为此,引入 Turing 不动点组合子 Θ:
Θ:=UU
其中:
U=λx.(λy.(y((xx)y)))
假设有一函数 F ,计算 ΘF :
- 代入 Θ :(UU)F 。
- 代入一个 U :((λx.(λy.(y((xx)y))))U)F 。
- 归约:(λy.(y((UU)y)))F 。
- 归约:F((UU)F) 。
- 用 Θ 替换 UU :F(ΘF) 。
由此可见,ΘF 是 F 的不动点。
现在,考虑一个函数:
F:=λf.(λn.(((IS_ZERO n)1)((×n)(f((−n)1)))))
将 Θ 作用于 F :
ΘF=F(ΘF)=λn.(((IS_ZERO n)1)((×n)((ΘF(−n)1))))
可见 ΘF 就是阶乘函数。
Lambda 演算的理论意义在于为 Lisp、Haskell 等语言提供理论基础,闭包也在很多编程语言中出现,Python 中也有lambda匿名函数。
留言
Loading comments