查看“︁不动点组合子”︁的源代码

'''不动点组合子'''（{{lang-en|Fixed-point combinator}}，或'''不动点算子'''）是计算其他函数的一个[[不动点]]的[[高阶函数]]。

函数 '''f''' 的不动點是將函數應用在輸入值 x 時，會傳回與輸入值相同的值，使得 '''f'''(x) = x。例如，0 和 1 是函数 '''f'''(x) = x<sup>2</sup> 的不动点，因为 0<sup>2</sup> = 0 而 1<sup>2</sup> = 1。鉴于一阶函数（在简单值比如整数上的函数）的不动点是个一阶值，高阶函数 '''f''' 的不动点是另一个函数 '''g''' 使得 '''f'''('''g''') = '''g'''。那么，不动点算子 '''fix''' 的定義是
: <math> x = f\ x </math>

使得对于任何函数 f
: <math> \textsf{fix}\ f = f\ (\textsf{fix}\ f) </math>

不动点组合子它们可以用非递归的 [[Λ演算|lambda抽象]]来定义，在 lambda演算中的函數都是匿名的。然而在命令式編程語言中的遞歸，或許限制只能以呼叫函數名稱作為參數來實作。在函數式編程語言中的不动点，以 lambda抽象来定义的'''Y'''組合子為：
: <math>\textsf{Y} = \lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x)) </math>
則允许匿名函数足夠逹成递归的作用，即[[递归函数]]。應用於帶有一個變量的函數，'''Y'''組合子通常不會終止。將 '''Y'''組合子應用於二或更多個變量的函數，會獲得更有趣的結果。第二個變量可當作計數器或索引。由此產生的函數行為，表現出如命令式語言中一個<code>while</code>或<code>for</code>迴圈。

這個組合子也是 Curry悖論的核心，演示了無型別的 lambda演算是一個不穩固的推論系統，因由 '''Y'''組合子允許一個匿名表達式來表示零或者甚至許多值，這在數理邏輯上是不一致的。

== Y组合子 ==
在[[无类型lambda演算]]中众所周知的（可能是最简单的）不动点组合子叫做'''Y'''组合子。它是[[Haskell Curry|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演算，可以写出不动点算子，“有用的”不动点算子（它的应用总是会返回）的类型将是有限制的。

例如，在[[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'''的主体。

== 例子 ==

考虑阶乘函数（使用[[邱奇数]]）。平常的递归数学等式
:'''fact'''(n) = if n=0 then 1 else n * '''fact'''(n-1)
可以用lambda演算把这个递归的一个“单一步骤”表达为
:'''F''' = λf. λx. (ISZERO x) 1 (MULT x (f (PRED x))),
这里的"f"是给阶乘函数的占位参数，用于传递给自身。
函数'''F'''进行求值递归公式中的一个单一步骤。
应用'''fix'''算子得到
:'''fix'''('''F''')(n) = '''F'''('''fix'''('''F'''))(n)
:'''fix'''('''F''')(n) = λx. (ISZERO x) 1 (MULT x ('''fix'''('''F''') (PRED x)))(n)
:'''fix'''('''F''')(n) = (ISZERO n) 1 (MULT n ('''fix'''('''F''') (PRED n)))我们可以简写'''fix'''('''F''')为'''fact'''，得到
:'''fact'''(n) = (ISZERO n) 1 (MULT n ('''fact'''(PRED n)))所以我们见到了不动点算子确实把我们的非递归的“阶乘步骤”函数转换成满足预期等式的递归函数。

== 其他不动点组合子 ==

'''Y'''组合子的可以在传值调用的[[应用序求值]]中使用的变体，由普通'''Y'''组合子的部分的[[Eta展开|η-展开]]给出：

: '''Z''' = λf.(λx. f (λ'''y'''. x x '''y''')) (λx. f (λ'''y'''. x x '''y'''))

'''Y'''组合子用[[SKI组合子演算|SKI-演算]]表达为
: '''Y''' = S (K (S I I)) (S (S (K S) K) (K (S I I)))在SK-演算中最简单的组合子由[[John Tromp]]发现，它是

: '''Y'''' = S S K (S (K (S S (S (S S K)))) K)它对应于lambda表达式

: '''Y'''' = (λx.λy. x y x) (λy.λx. y (x y x))

另一个常见不动点组合子是图灵不动点组合子（[[阿兰·图灵]]发现的）:

: '''Θ''' = (λx.λy.(y (x x y))) (λx.λy.(y (x x y)))它也有一个简单的传值调用形式：

: '''Θ'''<sub>'''v'''</sub> = (λx.λy.(y (λ'''z'''. x x y '''z'''))) (λx.λy.(y (λ'''z'''. x x y '''z''')))

== 参见 ==

* [[组合子逻辑]]
* [[lambda演算]]
* [[有类型lambda演算]]

== 外部链接 ==

* http://okmij.org/ftp/Computation/fixed-point-combinators.html{{Wayback|url=http://okmij.org/ftp/Computation/fixed-point-combinators.html |date=20201107223632 }}
* http://www.cs.brown.edu/courses/cs173/2002/Lectures/2002-10-28-lc.pdf{{Wayback|url=http://www.cs.brown.edu/courses/cs173/2002/Lectures/2002-10-28-lc.pdf |date=20201103170053 }}
* http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/{{Wayback|url=http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/ |date=20110604185257 }}
* http://www.csse.monash.edu.au/~lloyd/tildeFP/Lambda/Examples/Y/（executable）{{dead link|date=2017年11月 |bot=InternetArchiveBot |fix-attempted=yes }}
* https://web.archive.org/web/20060719181315/http://www.ececs.uc.edu/~franco/C511/html/Scheme/ycomb.html
* http://stackoverflow.com/questions/93526/what-is-a-y-combinator{{Wayback|url=http://stackoverflow.com/questions/93526/what-is-a-y-combinator |date=20201203041930 }}

[[Category:Lambda演算]]
[[Category:不动点]]
[[Category:组合子逻辑]]
[[Category:递归]]