9. 递归函数¶

9.1. 函数的不动点¶

在前一节中，为了把 \(\lambda\) 演算变成一门"真正的"编程语言，我们看到可以恰当地定义布尔常量（true、false）、条件表达式（if-then-else）、逻辑运算符（and、or、not）、整数（0、1、2、3 等）以及算术运算符（\(+\)、\(-\) 等）。

然而，还缺少一样东西。我们仍然需要能够定义递归函数（阶乘等）。但要递归，我们需要一个"名字"，以便在我们正在创建的函数内部指代我们正在创建的这一个函数。而 \(\lambda\) 演算并不给我们全局名字。相反，我们只有表示函数抽象中参数的变量。那么这个困境有出路吗？答案是"有"，它被称为 不动点组合子（fixed point combinator） 。我们首先定义函数的 不动点（fixed point） 的概念。

对于任何函数 \(f\) 和 \(x\)，如果 \(f(x) = x\)，那么 \(x\) 被称为函数 \(f\) 的 不动点 。

下面是一些当函数是实变量的函数时可以思考的例子：

你能为函数 \(f(t) = t^2\) 找到一个或多个不动点吗？
你能为函数 \(f(t) = 1\) 找到一个或多个不动点吗？
你能为函数 \(f(t) = t+1\) 找到一个或多个不动点吗？

9.2. Y 不动点组合子¶

当我们处理上面这些例子那样的实变量函数时，寻找不动点的"算法"是求解方程 \(f(x) = x\)。如果能找到解，函数就有不动点；否则就没有。

对任意 \(\lambda\)-演算函数，是否存在寻找其不动点的类似方法？考虑一个出于历史原因我们称之为 \(Y\) 的函数。它的定义如下：

\[Y = \lambda h.(\lambda x.(h \; (x \; x))\; \lambda x.(h \; (x \; x)))\]

\(Y\) 将为任意函数 F 找到其 不动点 。

也就是说，对于任何函数 F，\((Y \; F)\) 都是 F 的一个不动点，即 \((F \; (Y \; F)) = (Y \; F)\)。换句话说，如果我们将 Y 应用于 F ，得到的结果是一个值，把这个值交给 F 时，会再给我们 Y 应用于 F 的结果。

要看清这一点，注意对 \((Y \; F)\) 进行 \(\beta\)-归约所需的替换会引导我们得到：

\[(Y \; F) = (\lambda h.(\lambda x.(h \; (x \; x)) \; \lambda x.(h \; (x \; x))) \; F) = (\lambda x.(F \; (x \; x)) \; \lambda x.(F \; (x \; x))) = (F \; (\lambda x.(F \; (x \; x)) \; \lambda x.(F \; (x \;x)))) = (F \; (Y \; F))\]

因此 Y 有一个卓越的性质：一旦应用于任何函数 F ，它就能不断生成把 F 应用于 (Y F) 的应用。也就是说，

\[(Y \; F) = (F \; (Y \; F)) = (F \; (F \; (Y \; F))) = (F \; (F \; (F \; (Y \; F)))) = \; ...\]

如果我们利用这个性质，并以一种使其"几乎递归"的方式定义一个函数 F ，那么把 Y 应用于这个几乎递归的函数，就会得到我们想要的递归函数。换句话说， Y 把几乎递归的函数变成递归函数。

9.3. 使用 Y 实现阶乘¶

为了说明，让我们使用上一节在 \(\lambda\) 演算中定义的丘奇数、IF-THEN-ELSE、MULT、ISZERO 和 PRED 函数，来定义一个新的几乎递归的函数：

\[\lambda g. \lambda n.(IF \; (ISZERO \; n) \; THEN \; ONE \; ELSE \; ((MULT \; n) \; (g \; (PRED \; n))))\]

这个新函数很像我们通常认为的递归阶乘函数， 只不过 它使用参数 \(g\) 而不是全局定义的名字 \(g\)。因此它在 \(\lambda\) 演算中是有效的定义。尽管有效，可惜它也不是递归的阶乘函数。然而神奇的是，如果我们把 \(Y\) 应用于这个函数，即：

\[(Y \; \lambda g. \lambda n.(IF \; (ISZERO \; n) \; THEN \; ONE \; ELSE \; ((MULT \; n) \; (g \; (PRED \; n)))))\]

我们得到阶乘函数。可能需要一些时间来确信这一点。尝试进行展开（ \(\beta\) -reductions）以评估阶乘函数。

\[((Y \; \lambda g. \lambda n.(IF \; (ISZERO \; n) \; THEN \; ONE \; ELSE \; ((MULT \; n) \; (g \; (PRED \; n))))) \; THREE)\]

并且，您应该看到如何最终产生丘奇数字 \(SIX\) 。为了开始这个过程，您可能希望将上述 \(\lambda g\) 抽象简写为 AFACT 。然后注意：

\[((Y \; AFACT) \; THREE) = ((AFACT \; (Y \; AFACT)) \; THREE)\]

对 \(((AFACT \; (Y \; AFACT)) \; THREE)\) 中最左边的可归约式进行 β-归约，即把 AFACT 定义中的 g 参数替换为 \((Y \; AFACT)\)，你就会得到……

\[( \lambda n.(IF \; (ISZERO \; n) \; THEN \; ONE \; ELSE \; ((MULT \; n) \; ((Y \; AFACT) \; (PRED \; n)))) \; THREE )\]

注意，\((Y \; AFACT)\) 在 ELSE 分支中再次出现。组合子的性质允许我们把这里的 \((Y \; AFACT)\) 替换为 \((AFACT \; (Y \; AFACT)\)，从而可以再次把 AFACT 抽象的 g 参数替换为 \((Y \; AFACT)\)。从这里继续下去，你最终会得到 SIX 作为返回的值。

令人惊叹的是，在完全停留在丘奇布尔值丘奇数所定义的语言内部的情况下，我们已经能够产生阶乘函数的递归版本。这在理论上非常重要，因为它证明了丘奇的 \(\lambda\) 演算能够驾驭递归定义函数的全部能力。

9.4. 识别不动点组合子¶

虽然上面定义的函数 \(Y\) 是一个著名的不动点组合子，但还有许多其他的不动点组合子，也就是具有如下性质的函数 \(Z\)：

\[(F \; (Z \; F)) = (Z \; F)\]

对所有函数 \(F\) 都成立。本节将提供识别其他不动点组合子的练习。

为了减少这个问题中的语法杂乱，我们在书写 \(\lambda\) 表达式时会采取一些捷径。首先，对于有两个或更多参数的（柯里化）函数，我们省去除第一个之外的所有 \(\lambda\) 和除最后一个之外的所有圆点。因此，例如，我们将使用：

\[\lambda abcd.E\]

作为下面形式的缩写：

\[\lambda a.\!\lambda b.\!\lambda c.\!\lambda d.E\]

其次，为了减少括号，我们将使用 \((u\ v\ w\ x\ y\ z)\) 作为 \((((((u\ v)\ w)\ x)\ y)\ z)\) 的缩写。本质上，我们让函数应用成为左结合。 这种记号只用于下面的练习题。不要在家庭作业、考试或其他练习题中使用它。

OpenDSA 完整目录

Chapter 29 Lambda Calculus

9. 递归函数¶

9.1. 函数的不动点¶

9.2. Y 不动点组合子¶

9.3. 使用 Y 实现阶乘¶

9.4. 识别不动点组合子¶