λ演算：函数式编程的基础

函数式编程基于一个理论基础，称为λ演算（lambda calculus），由阿隆佐·邱奇（Alonzo Church）提出。理解λ演算最简单的方式是将其视为一种理想化的、极简的函数式编程语言。换句话说，想象一下OCaml或任何类似的函数式编程语言，然后去掉所有与函数式编程无关的功能，剩下的部分本质上就是λ演算。

λ表达式

λ演算中的表达式称为λ表达式，可以通过以下三条规则构建：

• 一个变量 — 如 x、y、myvar 等 — 是一个λ表达式。
• 若 x 是一个变量，e 是一个λ表达式，则函数抽象（即函数定义）也是一个λ表达式。
• 若 e1 和 e2 都是λ表达式，则函数应用 e1 e2 也是一个λ表达式。

我们可以使用巴科斯-诺尔范式（BNF）来更简洁地表示λ演算的形式语法：

1<var> ::= x | y | myVar | ...
2<lambda_expr> ::= 
3  <var>
4| λ <var> . <lambda_expr>
5| <lambda_expr> <lambda_expr>

此外，我们可以在λ表达式中使用括号以避免歧义。

如上所示，λ演算的核心围绕两个概念：函数抽象和函数应用，这两个概念直接来源于数学函数。函数抽象描述了如何声明一个单参数的数学函数，例如 $f(x) = x$。在λ演算中，$\lambda x.\, x$ 表示一个接收输入 x 并返回自身的函数，这就是恒等函数。
函数应用则类似于将函数作用于某个参数。例如，我们可以将 $f(x) = x$ 应用于 $2$，得到 $f(2) = 2$。类似地，$(\lambda x.\, x)\,y$ 表示将函数 $\lambda x.\,x$ 应用于参数 $y$。

尽管λ演算仅包含变量和函数这两种语言元素，但它在计算能力上等同于任何通用编程语言，如C、Python、Java或OCaml。特别地，λ演算足以编码并实现数字、布尔值以及像对和列表这样的数据结构。更多细节可参考邱奇编码。事实上，我们甚至可以用λ演算编写一个微服务！当然，代码看起来可能会非常复杂难懂。

λ约简

运行一个程序意味着将表示该程序的λ表达式不断约简，直到无法再进一步约简为止。最终完全约简后的表达式即为程序的值。
像 $\lambda x.\,x \, x$ 这样的函数抽象或变量 $x$ 已经是完全约简的。相反，形如 $(\lambda x.\,e1)\,e2$ 的函数应用可以进一步约简：将函数的形式参数 x 替换为实际参数 e2，代入到函数体 e1 中。这种表达式被称为可约表达式或红点（redex）。

例如：

$(\lambda x.\,x \, x) \, y$

$y \, y$

现在出现了一个有趣的问题：“是否能在有限步内完全约简任意λ表达式？”答案是否定的。存在一些λ表达式永远无法被完全约简，例如 $(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$。这个表达式会不断自我应用，因此永远无法被完全约简：

$(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$

$(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$

$(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$

$\ldots$

仔细思考就会发现这很合理。λ演算允许我们构造出与Java或Python中无限循环程序等价的未定义值。

函数是一等公民

λ演算的一个迷人之处在于：变量与函数之间没有区别——两者都是表达式。变量或函数可以自由地作为参数传递给其他函数，也可以从函数中返回。例如，$(\lambda x.\,x \, z) \, (\lambda y. \, y)$ 表示将函数 $\lambda x.\,x \, z$ 应用于函数 $\lambda y.\, y$。在λ演算中，函数被视为一等公民。

函数式编程语言正是建立在这一思想之上，将函数当作一等公民处理。在这些语言中，函数可以像数字、布尔值或字符串一样被赋值给变量、传入函数或从函数返回。相比之下，在命令式编程语言中，函数是二等公民，即不能用于构造表达式，既不能赋值给变量，也不能作为参数传递给其他函数。

“一等公民”这一概念是函数式编程的核心思想之一，也是高阶函数的基础，而高阶函数正是函数式编程的标志性特征。

柯里化与部分应用

λ演算只允许函数接受一个参数。然而，λ演算的一个重要洞察是：我们可以将多参数函数表示为一系列嵌套的单参数函数。这种技术称为柯里化（Currying）。

举例说明：假设我们要定义一个函数，它接受两个参数 $x$ 和 $y$，然后将函数 $f$ 应用于这两个参数并返回结果。通过柯里化，我们可以将其定义为两个嵌套的单参数函数：$\lambda x.\lambda y.\, f \, x \, y$。

由于 $\lambda x.\lambda y.\, f \, x \, y$ 实际上是两个嵌套函数，将其应用于两个参数 $u$ 和 $v$，意味着先将其应用于 $u$，再应用于 $v$：

$(\lambda x.\lambda y.\, f \, x \, y) \, u \, v$

$(\lambda y.\, f \, u \, y) \, v$

$f \, u \, v$

柯里化的一个奇妙之处在于它支持部分应用。我们不必将函数 $\lambda x.\lambda y.\, f \, x \, y$ 完全应用到两个参数。我们可以只对其应用一个参数 $u$，然后停止。此时得到的是一个一元函数 $(\lambda y.\, f \, u \, y)$，其中 $x$ 被固定为 $u$。

柯里化与部分应用是函数式编程的另一大核心思想。OCaml 和 Haskell 均依赖柯里化来表示多参数函数。

约简策略

我们之前看到，形如 $(\lambda x.\,e1)\,e2$ 的λ表达式是一个红点（redex）。但如果参数本身也是一个红点呢？例如，$(\lambda x.\,x \, x) \, ((\lambda y.\,z) \, u)$ 本身就是一个红点，而其参数 $(\lambda y.\,z) \, u$ 也是一个红点。

此时我们可以采用以下两种策略之一：

• 先约简参数 $e2$，然后再将完全约简后的 $e2$ 代入 $e1$ 中替换 $x$。这种策略通常称为按值调用（call-by-value）。
• 直接将整个表达式 $e2$ 作为参数代入，不进行约简。这种策略也称为按名调用（call-by-name）。

以下是两种策略的对比：

这两种约简策略导致不同的求值顺序，但它们都终止，并得出相同的结果。事实上，对于同一个表达式，如果两种策略都能终止，它们总是产生相同的最终结果。

然而，当表达式中包含未定义值（如非终止的子表达式）时，两种策略可能导致不同结果。例如考虑函数应用 $(\lambda y. \, z) ((\lambda x.\,x \, x) \, (\lambda x.\,x \, x))$。这里，$\lambda y. \, z$ 可以看作一个常量函数，忽略输入参数，始终返回 $z$。我们将这个常量函数应用于 $(\lambda x.\,x \, x) \, (\lambda x.\,x \, x)$，而后者代表一个未定义值，因为该表达式永远无法完全约简。

根据不同的约简策略，$(\lambda y. \, z) ((\lambda x.\,x \, x) \, (\lambda x.\,x \, x))$ 的约简可能永远不会终止，也可能终止并返回值。如下所示：

函数式编程语言的表达能力在很大程度上取决于其采用的约简策略。OCaml 和 Haskell 采用了不同的策略，从而带来了一些根本性的差异。