简单的 Lambda Calculus（拉姆达演算）

本文主要是对 Learn X in Y minutes 的 Lambda Calculus 的部分翻译。同时参考了 The Lambda Calculus –
Stanford Encyclopedia of Philosophy。

P.S. 建议先读后者，通读后有一定的认识即可，之后再从前者处验证一下。

Lambda 演算（ $\lambda-calculus<strong>$ ）是由 Alonzo Church 原创的一种世界上最小的编程语言。即便没有数字、字符串、布尔值等任何非函数数据类型，其仍然可以用于表示任何图灵机。

拉姆达演算由三个部分组成：变量、函数以及应用。

最基本的函数是identity function: $\lambda x.x$ ，代表着 $f(x)=x$ ，第一个 $x$ 是函数的参数，第二个是函数体。

自由变量与约束变量

在函数 $\lambda x.x$ 中，” $x$ “被称作约束变量，因为其既在参数中，又在函数体中。

在 $\lambda x.y$ 中， $y$ 被称作自由变量，因为其未被预先声明。

求值

求值操作通过 $\beta$ 化简( $\beta - reduction$ )完成，其本质上是词法作用域的替换。

当对 $(\lambda x.x)a$ 求值时，我们将函数主体中出现的所有 $x$ 替换为 $a$ 。

$(\lambda x.x)a$ 的求值结果是: $a$ ;
$(\lambda x.y)a$ 的求值结果是: $y$ 。

P.S. 这或许不太直观，因此我多加了一个例子：当我们要求一个多项式的值，例如 $x^2-2 \cdot x+5$ 在 $x=2$ 时的值，使用 $\lambda$ 演算来表示这个情况:
$(\lambda x[x^2 - 2 \cdot x + 5])2 \Rightarrow 2^2 - 2 \cdot 2 + 5 \Rightarrow 5$

你也可以创造更高阶的函数:

$(\lambda x.(\lambda y.x))a$ 求值为 $\lambda y.a$

即使 $\lambda$ 演算通常来说只支持单参数函数，我们仍然可以通过一种名为柯里化(Currying)的技巧来创建多参数函数。

$(\lambda x.\lambda y.\lambda z.xyz)$ 相当于 $f(x, y, z) = ( (x y) z)$

P.S. $(\lambda x.\lambda y.\lambda z.xyz)$ 实际上是”依次进行函数应用”，即 $\lambda x.$ 接受第一个参数x，传递给 $\lambda y.\lambda z.xyz$ ，以此类推，这实际上是一个三层嵌套，依次等待参数传给 $x,y,z$ 。

有时， $\lambda xy.<body>$ 也可以表示为 $\lambda x.\lambda y.<body>$

重要的是要认识到传统的 lambda 演算没有数字、字符或任何非函数数据类型！

布尔逻辑

在 lambda 演算中没有 “True” 或 “False”，甚至没有 1 或 0。

在 lambda 演算中：

T 由 $\lambda x. \lambda y.x$ 表示；

F 由 $\lambda x. \lambda y.y$ 表示。

首先，我们可以定义一个 if 函数 $\lambda btf$ ，其在 $b$ 为 True 的时候返回 $t$ ，在 $b$ 为 False 的时候返回 $f$ 。

$IF$ 相当于： $\lambda b.\lambda t.\lambda f.\text{b t f}$

使用 $IF$ 我们就可以定义基本的布尔逻辑操作：

$\text{a AND b}$ 相当于： $\lambda ab.\text{IF a b F}$ ；

$\text{a OR b}$ 相当于： $\lambda ab.\text{IF a T b}$ ；

$\text{NOT a}$ 相当于： $\lambda a.\text{IF a F T}$ 。

注意： $\text{IF a b c}$ 本质上是在说： $\text{IF( ( a b ) c )}$

数字

尽管 lambda 演算中没有数字，我们仍然可以使用丘奇数字对数字进行编码。

对于任何一个数字 n： $n=\lambda f.f^{n}$ ，所以：

$0=\lambda f.\lambda x.x$

$1=\lambda f.\lambda x.\text{f x}$

$2=\lambda f.\lambda x.\text{f ( f x )}$

$3=\lambda f.\lambda x.\text{f ( f ( f x ) )}$

P.S. 可以注意到，实际上我们使用“次数”来定义自然数。

为了增加丘奇数，我们使用后继函数(successor function) $\text{S(n) = n + 1}$ ：

$S = \lambda n.\lambda f.\lambda x.\text{f ( ( n f ) x )}$

使用后继函数我们可以定义加法：

$\text{ADD} = \lambda ab.\text{(a S)b}$

P.S. 我们定义的ADD中的 $a$ 的意思是重复 $a$ 次S，即 $\text{ADD 2 3 = S(S(3))}$ ， $S(3)=4$ ，再 $S(4)=5$ 。同时要注意，此处并不是“定义” $\text{(a S)b}$ 中的a代表次数，这是严格的 $\beta$ 化简的结果。如果你只需要简单的 $\lambda$ 演算知识来快速入门，那么到这里已经足够了。后文的Get even smaller部分将会提到更多的炫酷的演算方式，我应该会后续单独翻译一篇更详细的关于它们的文章，而不是在这里提到。

名称	语法	实例	解释
变量	$<name>$	$x$	名为 $x$ 的变量
函数	$\lambda<parameters>.<body>$	$\lambda x.x$	形参为 $x$ 且主体为 $x$ 的函数
应用	$<function><variable or function>$	$(\lambda x.x)a$	以实参 $a$ 调用函数 $\lambda x.x$