2. lambda 演算的语义¶
2.1. lambda 演算的语义¶
在前一节中，我们介绍了 lambda 演算的全部语法。本章其余部分（包括本节）讨论 lambda 演算的语义，也就是 lambda 表达式的含义，换句话说，就是它们如何被解释、它们的值是什么。显然，lambda 演算的表达能力是出众的：它那微小的语法就能让我们表达丰富的计算，事实上是所有可能的计算（关于这一点，可以查阅 丘奇-图灵论题）。
注意，lambda 演算中的所有程序都是表达式，也就是说，程序因求值而获得其值。lambda 演算不包含任何语句，也就是不包含那些为了副作用而执行、例如通过赋值语句修改内存内容或通过打印语句向标准输出流发送字符串的命令。因此，lambda 演算是纯粹的函数式语言。
现在，我们解释 lambda 演算文法中给出的三种 lambda 表达式的含义。对每一种 lambda 表达式，我们既给出英文陈述，又给出对应的 JavaScript 代码片段来描述它的含义。
lambda 演算中的 变量 （即 lambda 演算文法中的第一条产生式）是另一个 lambda 表达式的占位符。换句话说，与所有编程语言一样，变量可以用来引用某个可能已知也可能未知的值。因此，lambda 演算中的变量 \(x\) 和 \(p_1\) 可以分别用 JavaScript 中的变量
x和p1来表示。例
\(\lambda\) 表达式
语义的英文陈述
JavaScript 实现
1
\(x\)
命名为 \(x\) 的变量
x
lambda 演算与 JavaScript 的主要区别在于：在 lambda 演算中，每个变量在整个程序的执行期间只能被绑定到一个值；而在 JavaScript 中，执行期间可以使用赋值语句多次改变变量的值。总之，lambda 演算中的变量更像命令式编程语言中的具名常量，而不像变量。此外，由于 lambda 演算中唯一的值是函数，所以所有变量都是函数值的占位符。
lambda 演算中的 lambda 抽象 （文法中的第二条产生式）是一个函数定义，也就是说，它是一个定义函数的表达式，不是 函数调用。由于 lambda 演算中的所有函数都是匿名的且只接受一个参数，我们要定义一个函数所需的全部信息就是其参数的名字（即文法第二条产生式中跟在 \(\lambda\) 后面的变量）和它的函数体（一个 lambda 表达式）。
例
\(\lambda\) 表达式
语义的英文陈述
JavaScript 实现
2
\(\lambda x.x\)
返回 \(x\) 的 \(x\) 的函数（即恒等函数 identity function）
function (x) { return x; }
3
\(\lambda y.y\)
返回 \(y\) 的 \(y\) 的函数（即恒等函数）
function (y) { return y; }
4
\(\lambda x.y\)
返回 \(y\) 的（关于 \(x\) 的）常函数
function (x) { return y; }
5
\(\lambda z.y\)
与上面相同的函数
function (z) { return y; }
6
\(\lambda y.x\)
返回 \(x\) 的（关于 \(y\) 的）常函数
function (y) { return x; }
7
\(\lambda x.\lambda y.y\)
\(x\) 的函数，返回 \(y\) 的函数，该函数返回 \(y\) （换句话说，即 \(x\) 的函数，它返回恒等函数）
function (x) { return function (y) { return y; }; }
注意，上面的例 7 是双参数（即 \(x\) 和 \(y\)）的 柯里化（curried） 函数，它返回它的第二个参数。
lambda 演算中的 函数应用 （文法中的第三条产生式）是一次函数调用，也就是说，它是把某个函数应用于单个实参的表达式。函数应用的第一个组成部分或者是变量（见下面的例 8），或者是一个更复杂的、最终会求值成函数的 lambda 表达式。在下面的例 9 和例 10 中，函数应用的第一个组成部分是 lambda 抽象，也就是一个被定义并立即调用的函数。在 JavaScript 中，这种函数应用是一种常见的习惯用法，有时被称为 IIFE。
例
\(\lambda\) 表达式
语义的英文陈述
JavaScript 实现
8
\((x\ y)\)
把函数 \(x\) 应用于实参 \(y\) 的调用
x(y)
9
\((\lambda x.x\ y)\)
恒等函数应用于 \(y\)
(function (x) { return x; })(y)
10
\((\lambda z.x\ y)\)
常函数 \(x\) 应用于 \(y\)
(function (z) { return x; })(y)
11
\(\lambda x.(x\ y)\)
返回当 \(x\) 被调用时返回值的 \(x\) 的函数 作用于 \(y\)
function (x) { return x(y); }
12
\((\lambda x.\lambda y.y\ z)\)
上面例 7 中的函数应用于 \(z\)。由于这个双参数的柯里化函数只被传入一个实参，这个应用求值后将返回恒等函数。
(function (x) { return function (y) { return y; }; })(z)
13
\(( (\lambda x.\lambda y.y\ u)\ v)\)
上面例 7 中的函数应用于 \(u\) 和 \(v\)。由于这个双参数的柯里化函数被传入两个实参，这个应用求值后将返回第二个实参的值，即 \(v\)。
(function (x) { return function (y) { return y; }; })(u)(v)
注意，在上面的例 11 中，顶层表达式是一个 lambda 抽象，其函数体是一个函数应用。
2.2. 练习：lambda 演算的语义¶
这道题考察 lambda 表达式与 JavaScript 表达式之间的语义等价关系。
