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
发表回复