不动点组合子

在一般的数学和计算机科学中，函数的不动点是由函数映射到自身的值。

在计算机科学的组合逻辑中，定点组合子（或定点组合子）是一个高阶函数 fix {\displaystyle {\textsf {fix}}} 返回其参数函数的某个固定点（如果存在） .

形式上，如果函数 f 有一个或多个不动点

在经典的无类型 lambda 演算中，每个函数都有一个不动点。

fix 的一个特定实现是 Curry 的悖论组合子 Y

在函数式编程中，Y 组合子可用于在不支持递归的编程语言中正式定义递归函数。

该组合器可用于实现 Curry 的悖论。 Curry 悖论的核心是无类型 lambda 演算作为演绎系统是不可靠的，Y 组合器通过允许匿名表达式表示零甚至多个值来证明这一点。 这在数理逻辑上是不一致的。

应用于具有一个变量的函数，Y 组合器通常不会终止。 通过将 Y 组合器应用于两个或多个变量的函数，可以获得更有趣的结果。 第二个变量可以用作计数器或索引。 结果函数的行为类似于命令式语言中的 while 或 for 循环。

以这种方式使用，Y 组合器实现了简单的递归。 在 lambda 演算中，不可能在函数体中引用函数的定义。 递归只能通过获取作为参数传入的函数来实现。 Y 组合器展示了这种编程风格。

Y 组合子是 lambda 演算中定点组合子的一个实现。 不动点组合子也可以很容易地用其他函数式和命令式语言定义。 由于 lambda 演算的局限性，在 lambda 演算中的实现更加困难。

不动点组合子可以应用于一系列不同的函数，但通常不会终止，除非有一个额外的参数。 当要修复的函数引用其参数时，将调用对该函数的另一个调用，因此计算永远不会开始。 相反，额外的参数用于触发计算的开始。

固定点的类型是固定函数的返回类型。 这可以是实数或函数或任何其他类型。

在无类型 lambda 演算中，应用定点组合器的函数可以使用编码来表示，例如 Church 编码。 在这种情况下，特定的 lambda 项（定义函数）被视为值。 在编码上运行（β 减少）定点组合器为结果提供一个 lambda 项，然后可以将其解释为定点值。

或者，函数可以被视为纯粹在 lambda 演算中定义的 lambda 项。

这些不同的方法会影响数学家和程序员如何看待定点组合器。 λ 演算数学家可能会将应用于函数的 Y 组合子视为满足不动点方程的表达式，因此是一个解。

相比之下，只想将定点组合器应用于某些一般编程任务的人可能只会将其视为实现递归的一种手段。

每个表达式都有一个值。 这在一般数学中是正确的，在 lambda 演算中也必须如此。 这意味着在 lambda 演算中，将定点组合器应用于函数会得到一个表达式，其值是函数的不动点。

但是，这是lambda演算域中的一个值，它可能不对应函数域中的任何值，所以在实际意义上它不一定是一个固定的poi。