不动点组合子 我们先从组合逻辑的基础概念开始。组合逻辑是一种形式系统，它通过组合子（即没有自由变量的λ项）来构建函数和应用，避免了变量的使用。组合子可以看作是一些基本的高阶函数，它们通过函数应用来组合。 接下来，我们介绍几个关键的组合子： 恒等组合子 I ：定义为 Ix = x。 常值组合子 K ：定义为 Kxy = x。它接受两个参数，丢弃第二个，返回第一个。 应用组合子 S ：定义为 Sfgx = fx(gx)。它是一个更复杂的组合子，用于模拟函数应用。 现在，我们进入核心概念：不动点。在数学中，一个函数 f 的不动点是一个值 x，使得 f(x) = x。例如，对于函数 f(x) = x²，0 和 1 都是它的不动点。 在计算理论中，我们关心的是如何为任意函数找到一个不动点。不动点组合子就是一个高阶函数 Y，它满足以下性质：对于任意函数 g，Yg 是 g 的一个不动点，即 g(Yg) = Yg。 为什么不动点组合子很重要？因为它允许我们定义递归函数。在函数式编程中，如果一个函数没有名字，它就不能直接调用自身。但通过不动点组合子，我们可以将递归“编码”进去。 最著名的不动点组合子可能是图灵组合子 Θ，它满足一个更强的性质：Θg = g(Θg)。但为了更容易理解，我们通常先看一个更简单的例子：Curry 的 Y 组合子，定义为 Y = λf.(λx.f (x x)) (λx.f (x x))。 让我们验证一下 Y 确实是不动点组合子。对于任意函数 g，计算 Yg： Yg = (λf.(λx.f (x x)) (λx.f (x x))) g = (λx.g (x x)) (λx.g (x x)) = g ((λx.g (x x)) (λx.g (x x))) = g (Yg) 所以，我们得到了 g(Yg) = Yg，这正是不动点的定义。 在组合逻辑中，我们有不使用变量的不动点组合子。例如，图灵组合子可以定义为 Θ = (λx.λy.y (x x y)) (λx.λy.y (x x y))。 不动点组合子在编程语言理论中有深远的影响。它是实现递归的核心工具，也是指称语义学中描述递归程序含义的基础。通过不动点，我们可以为循环和递归函数赋予数学上的严谨解释。