不动点组合子

维基百科，自由的百科全书

不动点组合子(或不动点算子)是计算其他函数的一个不动点的高阶函数。

函数 f 的不动点是一个值 x 使得 f(x) = x。例如，0 和 1 是函数 f(x) = x² 的不动点，因为 0² = 0 而 1² = 1。鉴于一阶函数(在简单值比如整数上的函数)的不动点是个一阶值，高阶函数 f 的不动点是另一个函数 g 使得 f(g) = g。那么，不动点算子是任何函数 fix 使得对于任何函数 f 都有

f(fix(f)) = fix(f).

不动点组合子允许定义匿名的递归函数。有些令人惊奇，它们可以用非递归的lambda 抽象来定义。

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

Y = λf.(λx.f (x x)) (λx.f (x x))

[编辑] 不动点组合子的存在性

在数学的特定形式化中，比如无类型 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) = 如果 n=0 则 1 否则 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 组合子的部分的 η-展开给出:

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

Y 组合子用 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)))

它也有一个简单的传值调用形式:

Θ_v = (λx. λy. (y (λz. x x y z))) (λx. λy. (y (λz. x x y z)))

[编辑] 参见

[编辑] 外部链接

来自“http://zh.wikipedia.org../../../%E4%B8%8D/%E5%8A%A8/%E7%82%B9/%E4%B8%8D%E5%8A%A8%E7%82%B9%E7%BB%84%E5%90%88%E5%AD%90.html”

页面分类: 递归论