1.1. lambda 演算¶

lambda 演算 （也写作 \(\lambda\)-calculus，其中 lambda 是希腊字母 \(\lambda\) 的名称）是由阿隆佐·丘奇（Alonzo Church）于 1930 年代初期为了研究哪些函数是可计算的而创建的。除了在可计算性理论中是简洁而强大的模型之外，lambda 演算也是最简单的函数式编程语言。lambda 演算看起来就像一门玩具语言，尽管它（可以证明！）与今天使用的任何一种编程语言（如 JavaScript、Java、C++ 等）一样强大。

lambda 演算中的程序称为 lambda 表达式 （缩写为 \(\lambda exp\)），它只有三种类型。事实上，下面是 lambda 演算的一个完整的 BNF 文法：

该 BNF 文法告诉我们，lambda 演算中的表达式共有三种形式：

1. 变量（variable） （上面的第一条产生式）：通常我们用单个字母（可带整数下标）来表示一个变量。因此，\(x, y, a_1\) 和 \(p_2\) 都是变量的例子。

2. 函数抽象（function abstraction） （上面的第二条产生式）：这种 \(\lambda\) 表达式，也叫 lambda 抽象，对应一个函数定义，包含两个组成部分：函数的形式参数（必须恰好有一个参数，即上面第二条产生式中的非终结符 \(< var >\)）和函数体（即同一条产生式中的非终结符 \(<\lambda exp >\)）。例如，\(\lambda x.y\) 就是形式参数为 \(x\)、函数体为 \(y\) 的函数。注意，终结符 \(\lambda\) 后面的非终结符 \(<var>\) 并不是函数的名称。事实上，lambda 演算中的所有函数都是匿名的。

3. 应用 （上文第三种表示形式）：此类 :math:`lambda` 表达式对应于函数调用（或应用、或调用），包含两个组成部分：被调用的函数，其次是传递给函数的参数。例如， :math:`(fx)` 是将变量 :math:`f` （必须代表一个函数，因为函数是lambda演算中唯一的值）应用于参数 :math:`x` ，该参数也必须代表一个函数。

   注意，在 lambda 演算中，括号同时包围函数及其实参；而在许多现代编程语言中（以及数学记法中），函数在前、实参跟在括号里，就像这样：\(f(x)\)。在 lambda 演算中，函数调用两边的括号不是可选的。此外，上面的文法表明，括号不能用于任何其他地方。

上面的文法相当简洁，因为它只包含两个非终结符。然而它却能生成一个无限的表达式集合，它们代表了所有可计算函数！回顾一下，BNF 文法的表达能力来自递归，递归出现在上面文法的第二条和第三条产生式中。

下面的幻灯片演示了如何使用上面的文法为给定的 lambda 表达式构建语法分析树。

Settings

Saving...
Server Error
Resubmit

思考题

Q1. 为什么非终结符 \(<var>\) 不出现在上面文法的任何产生式的左侧？这个文法不完整吗？

Q2. 这个文法包含多少个终结符？

Q3. 由于第三条产生式是双重递归的，这个文法有歧义吗？

1.2. 练习：lambda 演算语法¶

通过下面的练习测试你对 lambda 演算语法的掌握程度。要获得这个随机练习的学分，你必须连续三次答对。

1.3. 更多 lambda 演算语法练习¶

一旦你能持续解决上一道题，就试试这个强度更高的练习：每次你必须分析四个表达式。要获得这个随机练习的学分，你必须连续三次答对。