关于函数式编程:Y-分钟速成-Lambda-Calculus

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) = ((()))

Lambda 演算

自在变量和束缚变量:

求值:

布尔逻辑:

SK 组合子演算

组合子

更多浏览: