Lambda Calculus 编程语言

我刚成为程序员的时候，有一次调试一段 C 语言代码。我一层一层的进入到被调用的子函数中去，想看看一个数据到底是怎么产生的。终于在遇到一个库函数的时候，调试器无法再跟踪进去了。C 语言程序通常会调用很多已经编译好的库函数，程序员只知道这些函数的接口，但看不到它们的实现代码。我知道这是处于效率的考虑，但还是忍不住想，一种编程语言，可不可以不调用任何编译好的库，所有功能都以源代码的形式提供给程序员，方便学习啊。后来进而又想，也许很多关键字，运算符都不是必须提前编译好的，有没有编程语言可以以源代码的形式提供这些关键字，运算符呢？

这些问题，当时也只是一想，没有去研究。多年之后，我在帮老婆做编程作业的时候发现，她们在课上居然学到了这样一种编程语言，叫做 Lambda Calculus。

Lambda Calculus 是一类非常精简的编程语言中的代表。这类语言中还包含 SKI，Iota 和 Jot 等，不过 Lambda Calculus 还是最经典的。Lambda Calculus 小到什么程度呢？只需要用几行文字就可以把 Lambda Calculus 的全部语法描述的清清楚楚，所以这里就介绍一下：

• Lambda Calculus 中用到的全部字符包括：小写英文字母，英文句号，小括号和一个希腊字母 lambda “λ”。
• 名字 name：由单个英文小写字母构成，格式为 <name\>。 比如 x，y，a 等；
• 函数定义 function：由“λ”字符跟一个变量名，跟一个英文句号，再跟一个表达式，结构为 λ<name\>.<expression\>。比如 λx.x，这个函数写成数学的形式是 f(x) = x；
• 函数调用 application：由函数定义加另一段表达式构成，格式<function\><expression\>。比如： (λx.x)a，这表示，把 a 作为参数传递给前面那个函数，运算结果就是 a。
• name, function, application 又被统称为 expression （表达式）。
• 括号用于控制计算的优先级。有时代码里也会加入空格以方便阅读。

以上就是这个编程语言的全部语法了。当时的要求是给这个语言编写一个编译器，其中最核心的部分只用了十来行代码就实现了，恐怕很难有比这更简单的编程语言了。可以直观的看出，这个编程语言的一些简单运算规则：

• λx.x 与 λy.y 是完全等价的，或者可以写成 λx.x ≡ λy.y
• (λx.x)a 可以简化成（推演运算得到） a，或者写成 (λx.x)a = a
• (λx.y)a = y
• (λx.(λy.x))a = λy.a

大家已经发现了，这个语言，连循环、判断等结构都没有，对了，这些都要自己编程实现；甚至连数字也没有，加减法也没有，这些也通通都要自己定义和实现。下面就介绍一下如何使用 Lambda Calculus 编写一些基本的功能。

• 实现多参数函数，这个方法有个专用名叫函数柯里化。比如实现函数f(x, y, z) = ((x, y), z) 可以使用如下的代码： λx.λy.λz.xyz
• 逻辑运算中的“真”被定义为：TRUE ≡ λx.λy.x。这里对于“真”的定义是：输入两个参数，返回第一个。推算一下
  • TRUE a b ≡ (λx.λy.x) a b = (λy.a) b = a
• 逻辑运算中的“假”被定义为：FALSE ≡ λx.λy.y。也就是输入两个参数，返回第二个。推算一下
  • FALSE a b ≡ (λx.λy.y) a b = (λy.y) b = b
• 判断语句 if，假设我们需要当变量 b 为 真时，返回 t；当 b 为假时返回 f。那么可以定义 IF ≡ λx.x 即 IF b t f ≡ λx.x b t f。 推算一下
  • IF TRUE t f ≡ (λx.x) (λx.λy.x) t f = (λx.λy.x) t f = t
  • IF FALSE t f ≡ (λx.x) (λx.λy.y) t f = (λx.λy.y) t f = f
• 有了以上的基础，逻辑运算的定义就简单多了，比如：
  • AND a b ≡ IF a b FALSE
  • OR a b ≡ IF a TRUE b
  • NOT a ≡ IF a FALSE TRUE
• 定义数字：
  • 我们可以只考虑自然数，其它数值都可以从自然数推算得到。自然数的定义是：
    • 0 是自然数
    • 每一个确定的自然数 a，都有一个确定的后继数 a' ，a' 也是自然数
    • 对于每个自然数 b、c，b = c 当且仅当 (b 的后继数) = (c 的后继数)
    • 0 不是任何自然数的后继数
  • 基于自然数定义，我们可以在 Lambda Calculus 如下定义自然数
    • 0 ≡ λf.λx.x 可发现 0 ≡ FALSE
    • 1 ≡ λf.λx.f x
    • 2 ≡ λf.λx.f (f x)
    • 3 ≡ λf.λx.f (f (f x))
    • ……
• 为了方便数字运算还要先定义一个辅助的“后继函数”：S = λn.λf.λx.f((n f) x) 。调用这个函数会得到输入参数的后继数，比如 S4 = 5。试验一下：
  • S 0 ≡ (λn.λf.λx.f((n f) x)) (λf.λx.x) = λf.λx.f(λx.x f) x) = λf.λx.f x ≡ 1
• 加法就可以定义为： ADD ≡ λa λb.(a S) b 。 拭一下：
  • ADD 2 3 = (λa λb.(a S) b) 2 3 = 2 S 3 ≡ (λf.λx.f (f x)) S 3 = λx. S (S x) 3 = S (S 3) = S 4 = 5

以上是 Lambda Calculus 一些最基本的功能，作为一个图灵完全的语言，它能做的远不止这些，其它编程语言能做的，它基本也都可以做。但是我们也发现了，如果一个语言什么预先定义都没有，一切都需要开发者自己从头做起，那么在实际应用中就效率太低了。

Lambda Calculus 的发明人是 Alonzo Church，他有个大名鼎鼎的学生，图灵。Lambda Calculus 对于后来编程语言的发展产生了深远的影响。函数式编程就是受此启发而来。如今，Lambda 函数更是成了主流编程语言的标配。