无 let，无递归，无问题：Y 组合子与 Z 组合子的温和入门

背景

在函数式编程理论中，组合子（Combinators）是纯函数式编程的核心概念。其中，Y 组合子（Y Combinator）和 Z 组合子（Z Combinator）尤为著名，它们允许在没有任何显式递归或变量声明的情况下实现递归行为。

这篇文章源自 Hacker News 社区的一篇技术讨论，旨在通过 JavaScript 这一具体语言，以循序渐进的方式推导 Y 组合子的本质。文章从一个看似简单的编程挑战开始：编写一个计算阶乘 fact(n) 的函数，但严禁使用循环（for, while）、显式递归（函数调用自身）以及变量声明（let, const, function 等）。

这个挑战的目的不仅仅是为了炫技，而是为了揭示计算理论中“递归”与“不动点（Fixed Point）”之间的深层联系，并解释为什么在严格限制声明和直接递归的环境下，我们需要借助高阶函数和组合子来模拟递归。

核心内容

1. 从显式递归到相互递归

首先，我们看一个标准的阶乘递归实现，这是我们要模仿的目标行为：

function fact(n) {
  if (n === 0) return 1;
  else return n * fact(n - 1);
}

然而，题目禁止在 fact 内部调用 fact。如果我们试图通过两个函数相互调用来绕过这一限制，例如 factf 调用 factg，factg 调用 factf，虽然避免了直接递归，但这构成了相互递归（Mutual Recursion）。根据更严格的规则，相互递归也是不被允许的。

2. 提取生成器模式

为了进一步抽象，我们尝试将递归逻辑提取到一个生成器函数 factgen 中，该函数接收一个参数 self，该参数代表“下一个要调用的函数”。

function factgen(self, n) {
  if (n === 0) return 1;
  else return n * self(self, n - 1);
}

let fact = n => factgen(factgen, n);

在这个实现中，fact(4) 的执行过程如下：

1. factgen(factgen, 4)
2. 返回 4 * factgen(factgen, 3)
3. 返回 4 * 3 * factgen(factgen, 2) ...以此类推，直到 n 为 0。

这里的关键洞察是：self(self, n) 这种模式在每次执行时并没有消除自我引用，而是生成了一个新的调用 self(self, n-1)。这种 g(g, ...) 的模式捕获了递归的核心机制：它通过自我应用（self-application）在每次迭代中保留结构，仅改变输入参数。

3. 消除声明与匿名函数

题目进一步禁止使用 function 关键字和变量声明（let）。我们只能使用匿名箭头函数。

让我们关注递归的核心模式 x => x(x)。如果我们定义一个函数 rep：

let rep = x => x(x)

当我们将 rep 作为参数传入自身时，即 rep(rep)，在纯表达式演算（Equational Reasoning）中，它等价于 (x => x(x))(x => x(x))。这个表达式在展开后依然包含自身结构。虽然在实际 JavaScript 引擎中，这会因无限求值导致栈溢出，但在理论层面，它展示了无需声明即可实现自我复制/自我引用的能力。

4. 引入不动点组合子 Y

为了利用这种自我复制的能力来做实际工作（如计算阶乘），我们需要将具体的业务逻辑 h 嵌入到这个自我复制的框架中。

定义 rep 为：

let rep = x => h(x(x))

此时，rep(rep) 会归约为 h(rep(rep))。这非常接近递归的定义：一个函数应用其自身的结果。

为了封装这一过程，我们定义 Y 组合子：

let Y = (h) => {
  let rep = x => h(x(x))
  return rep(rep)
}

Y 是一个高阶函数，它接收一个函数 h，并返回 h 的不动点（Fixed Point）。

什么是固定点？ 如果 p = Y(f)，那么根据上述推导，p 满足 p = f(p)。 这意味着，Y(f) 的结果 p 在作为参数传入 f 后，依然返回 p 本身。这正是递归的本质：函数在内部调用自己，而 Y 组合子自动提供了这种“自我调用”的机制。

5. 从 Y 到 Z：解决求值顺序问题

文章最后指出了 Y 组合子在 JavaScript 等**应用序求值（Applicative Order）**语言中的致命缺陷：rep(rep) 会立即尝试求值 x(x)，导致无限递归和栈溢出。

为了解决这个问题，我们需要惰性求值（Lazy Evaluation）或延迟调用。这就是 Z 组合子（Z Combinator） 的由来。

Z 组合子通过引入一层额外的抽象（通常是一个 lambda 表达式）来延迟求值：

// Y 组合子 (在严格求值语言中会导致栈溢出)
let Y = h => (x => h(x(x)))(x => h(x(x)))

// Z 组合子 (适用于 JavaScript 等应用序语言)
let Z = h => (x => h((...args) => x(x)(...args)))(x => h((...args) => x(x)(...args)))

或者更简洁地理解，Z 组合子将 x(x) 的调用包裹在一个匿名函数中，只有当该函数被实际调用时，递归才会发生。这使得我们可以安全地在 JavaScript 中实现真正的递归，而无需任何 let、const 或 function 声明。

关键要点

• 递归的本质是不动点：递归函数可以被视为其自身的固定点。Y 组合子是一个不动点组合子，它接受一个函数 h 并返回 h 的固定点，从而允许在不显式命名的情况下实现递归。
• 自我应用（Self-Application）是核心：x => x(x) 这种模式是构建递归的基础。它允许一个函数在内部引用自身，而不需要语言层面的递归关键字。
• Y 组合子 vs Z 组合子：
  • Y 组合子适用于**正则序求值（Normal Order）**或惰性求值的语言（如 Haskell）。在 JavaScript 等应用序语言中直接使用 Y 组合子会导致无限递归和栈溢出。
  • Z 组合子是 Y 组合子在应用序语言中的变体，通过延迟求值（将 x(x) 包裹在匿名函数中）来避免立即无限递归，使其能在 JavaScript 中实际工作。
• 无声明递归：通过高阶函数和组合子，可以在完全禁止变量声明（let/const）和函数声明（function）的情况下实现递归逻辑，这展示了函数式编程中“一切皆函数”的强大抽象能力。
• 相互递归的消除：通过提取生成器模式，可以将相互递归转化为单一函数的自我应用，进而抽象为组合子。

意义与影响

• 理论计算机科学的教育价值：这篇文章清晰地展示了从具体编程问题到抽象数学概念（不动点定理）的推导过程。它帮助开发者理解递归不仅仅是语言特性，更是一种可以通过高阶函数模拟的计算模式。
• 函数式编程的基石：Y 和 Z 组合子是 lambda 演算中的核心概念。理解它们有助于深入掌握函数式编程范式，特别是在处理高阶函数、柯里化（Currying）和惰性求值时。
• 语言设计的启示：通过对比 Y 和 Z 组合子，