共计 2240 个字符，预计需要花费 6 分钟才能阅读完成。
Lambda 演算
Lambda 演算 (lambda calculus, λ-calculus), 最后由阿隆佐·邱奇(Alonzo Church) 提出, 是世界上最小的编程语言. 只管没有数字, 字符串, 布尔或者任何非函数的数据类型, lambda 演算仍能够示意任何图灵机.
Lambda 演算由三种元素组成: 变量 (variables)、函数(functions) 和利用(applications)。
最根本的函数为恒等函数: λx.x, 它等价于 f(x) = x. 第一个 ”x” 为函数的参数, 第二个为函数体.
自在变量和束缚变量:
- 在函数 λx.x 中,“x” 被称作束缚变量因为它同时呈现在函数体和函数参数中
- 在 λx.y 中, “y” 被称作自在变量因为它没有被事后申明.
求值:
求值操作是通过 β - 归约 (β-Reduction) 实现的, 它实质上是词法层面上的替换.
当对表达式(λx.x)a 求值时, 咱们将函数体中所有呈现的 ”x” 替换为 ”a”
- (λx.x)a 计算结果为: a
- (λx.y)a 计算结果为: y
你甚至能够创立高阶函数:
- (λx.(λy.x))a 计算结果为: λy.a
只管 lambda 演算传统上仅反对单个参数的函数, 但咱们能够通过一种叫作柯里化 (Currying) 的技巧创立多个参数的函数
- (λx.λy.λz.xyz)等价于 f(x, y, z) = ((x y) z)
有时 λxy.<body> 与 λx.λy.<body> 能够调换应用
意识到传统的 lambda 演算没有数字, 字符或者任何非函数的数据类型很重要.
布尔逻辑:
在 lambda 演算中没有 ” 真 ” 或 ” 假 ”. 甚至没有 1 或 0.
作为替换:
T 示意为: λx.λy.x
F 示意为: λx.λy.y
首先, 咱们能够定义一个 ”if” 函数 λbtf, 它当 b 为真时返回 t, b 为假时返回 f
IF 等价于: λb.λt.λf.b t f
通过 IF, 咱们能够定义根本的布尔逻辑运算符:
a AND b 等价于: λab.IF a b F
a OR b 等价于: λab.IF a T b
NOT a 等价于: λa.IF a F T
留神: IF a b c 实质上指: IF((a b) c)数字：
只管 lambda 演算中没有数字, 咱们还能够用邱奇编码 (Church numerals) 将数字嵌入到 lambda 演算中.
对于任意数字 n: n = λf.fn 所以:
0 = λf.λx.x
1 = λf.λx.f x
2 = λf.λx.f(f x)
3 = λf.λx.f(f(f x))
要减少一个邱奇数, 咱们应用后继函数
S(n) = n + 1:S = λn.λf.λx.f((n f) x)
应用后继函数, 咱们能够定义加法:
ADD = λab.(a S)b
挑战: 试定义乘法函数!
变得更小: SKI, SK 和 Iota
SKI 组合子演算
令 S, K, I 为下列函数:
I x = x
K x y = x
S x y z = x z (y z)
咱们能够将 lambda 演算中的表达式转换为 SKI 组合子演算中的表达式:
- λx.x = I
- λx.c = Kc
- λx.(y z) = S (λx.y) (λx.z)
以邱奇数 2 为例:
2 = λf.λx.f(f x)
对于外面的局部 λx.f(f x):
λx.f(f x)
= S (λx.f) (λx.(f x)) (case 3)
= S (K f) (S (λx.f) (λx.x)) (case 2, 3)
= S (K f) (S (K f) I) (case 2, 1)所以:
2
= λf.λx.f(f x)
= λf.(S (K f) (S (K f) I))
= λf.((S (K f)) (S (K f) I))
= S (λf.(S (K f))) (λf.(S (K f) I)) (case 3)对于第一个参数 λf.(S (K f))有: λf.(S (K f))
= S (λf.S) (λf.(K f)) (case 3)
= S (K S) (S (λf.K) (λf.f)) (case 2, 3)
= S (K S) (S (K K) I) (case 2, 3)对于第二个参数 λf.(S (K f) I)有：λf.(S (K f) I)
= λf.((S (K f)) I)
= S (λf.(S (K f))) (λf.I) (case 3)
= S (S (λf.S) (λf.(K f))) (K I) (case 2, 3)
= S (S (K S) (S (λf.K) (λf.f))) (K I) (case 1, 3)
= S (S (K S) (S (K K) I)) (K I) (case 1, 2)综上:
2
= S (λf.(S (K f))) (λf.(S (K f) I))
= S (S (K S) (S (K K) I)) (S (S (K S) (S (K K) I)) (K I))如果开展这个表达式, 咱们最终又会失去邱奇数 2 的雷同的表达式.
SK 组合子演算
SKI 组合子演算还能够进一步简化. 咱们能够通过 I = SKK 移除 I 组合子. 咱们能够将所有的 I 替换为 SKK.
ι 组合子
SK 组合子仍不是最简的. 定义:
ι = λf.((f S) K)
咱们有:
I = ιι
K = ι(ιI) = ι(ι(ιι))
S = ι(K) = ι(ι(ι(ιι)))更多浏览:
- A Tutorial Introduction to the Lambda Calculus(英文)
- Cornell CS 312 Recitation 26: The Lambda Calculus(英文)
- Wikipedia – Lambda Calculus(英文)
- Wikipedia – SKI combinator calculus(英文)
- Wikipedia – Iota and Jot(英文)
- λ 演算 – 维基百科，自在的百科全书
- SKI 组合子演算 – 维基百科，自在的百科全书
有倡议？或者发现什么谬误？在 Github 上开一个 issue，或者发动 pull request！
原著 Max Sun，并由 0 个好心人批改。
Translated by: Maoyin Sun
© 2022 Max Sun, Yan Hui Hang