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 b t f ≡ λb.b t f 。 推算一下 IF TRUE t f ≡ ((λb.b) (λx.λy.x)) t f = (λx.λy.x) t f = t ; IF FALSE b t f ≡ (λb.b t f) (λx.λy.y) = (λ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 ≡ λf.λx.x 可发现 0 ≡ FALSE
    • 1 ≡ λf.λx.f x
    • 2 ≡ λf.λx.f (f x)
    • 3 ≡ λf.λx.f (f (f x) 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 函数更是成了主流编程语言的标配。

广告

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

您正在使用您的 WordPress.com 账号评论。 注销 /  更改 )

Twitter picture

您正在使用您的 Twitter 账号评论。 注销 /  更改 )

Facebook photo

您正在使用您的 Facebook 账号评论。 注销 /  更改 )

Connecting to %s