不动点组合子学术资讯 - 科技工作者之家

不动点组合子（英语：Fixed-point combinator，或不动点算子）是计算其他函数的一个不动点的高阶函数。

简介不动点组合子（英语：Fixed-point combinator，或不动点算子）是计算其他函数的一个不动点的高阶函数。

函数f的不动点是将函数应用在输入值 x 时，会传回与输出值相同的值，使得f(x) = x。例如，0 和 1 是函数f(x) = x的不动点，因为 0= 0 而 1= 1。鉴于一阶函数（在简单值比如整数上的函数）的不动点是个一阶值，高阶函数f的不动点是另一个函数g使得f(g) =g。那么，不动点算子fix的定义是x=f\ x。1

使得对于任何函数 f

不动点组合子它们可以用非递归的lambda抽象来定义，在 lambda演算中的函数都是匿名的。然而在命令式编程语言中的递归，或许限制只能以呼叫函数名称作为参数来实作。在函数式编程语言中的不动点，以 lambda抽象来定义的Y组合子为：

则允许匿名函数足够逹成递归的作用，即递归函数。应用于带有一个变量的函数，Y组合子通常不会终止。将Y组合子应用于二或更多个变量的函数，会获得更有趣的结果。第二个变量可当作计数器或索引。由此产生的函数行为，表现出如命令式语言中一个while或for循环。

这个组合子也是 Curry悖论的核心，演示了无型别的 lambda演算是一个不稳固的推论系统，因由Y组合子允许一个匿名表达式来表示零或者甚至许多值，这在数理逻辑上是不一致的。

组合子在无类型lambda演算中众所周知的（可能是最简单的）不动点组合子叫做Y组合子。它是Haskell B. Curry发现的，定义为

Y:= λf.(λx.(f (x x)) λx.(f (x x))) 用一个例子函数g来展开它，我们可以看到上面这个函数是怎么成为一个不动点组合子的：

(Y****g)

= (λf.(λx.(f (x x)) λx.(f (x x)))g)

= (λx.(g(x x)) λx.(g(x x)))（λf的β-归约 - 应用主函数于g）

= (λy.(g(y y)) λx.(g(x x)))（α-转换 - 重命名约束变量）

= (g(λx.(g(x x)) λx.(g(x x))))（λy的β-归约 - 应用左侧函数于右侧函数）

= (g(Y****g))（Y的定义）

注意Y组合子意图用于传名求值策略，因为 (Y****g)在传值设置下会发散（对于任何g）。

存在性在数学的特定形式化中，比如无类型lambda演算和组合演算中，所有表达式都被当作高阶函数。在这些形式化中，不动点组合子的存在性意味着“所有函数都至少有一个不动点”，函数可以有多于一个不同的不动点。

在其他系统中，比如简单类型lambda演算，不能写出有良好类型（well-typed）的不动点组合子。在这些系统中对递归的任何支持都必须明确的增加到语言中。带有扩展的递归类型的简单类型lambda演算，可以写出不动点算子，“有用的”不动点算子（它的应用总是会返回）的类型将是有限制的。2

例如，在Standard ML中Y组合子的传值调用变体有类型∀a.∀b.((a→b)→(a→b))→(a→b)，而传名调用变体有类型∀a.(a→a)→a。传名调用（正规）变体在应用于传值调用的语言的时候将永远循环下去 -- 所有应用Y(f)展开为f(Y(f))。按传值调用语言的要求，到f的参数将接着展开，生成f(f(Y(f)))。这个过程永远重复下去（直到系统耗尽内存），而不会实际上求值f的主体。