上面的大多数答案描述了y组合子是什么，但没有描述它的用途。

用不动点组合子来证明lambda演算是图灵完备的。这是计算理论中一个非常重要的结果，为函数式编程提供了理论基础。

学习不动点组合子也帮助我真正理解了函数式编程。但我从未发现它们在实际编程中有任何用处。

我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html中引用了这个，这是我几年前写的一个解释。

在本例中我将使用JavaScript，但许多其他语言也可以。

我们的目标是写出一个1的递归函数 变量只使用1变量的函数，没有 赋值，通过名称定义事物等(为什么这是我们的 目标是另一个问题，我们把它作为 我们所面临的挑战。)似乎不可能，是吧?作为 举个例子，让我们实现阶乘。

第一步是说我们可以很容易地做到这一点，如果我们 作弊了一点。使用二元函数和 我们至少可以避免使用 赋值来建立递归。

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

现在我们看看能不能少作弊。首先我们用 任务，但我们不需要。我们可以写成X和 Y内联。

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

但是我们用两个变量的函数来得到一个1的函数 变量。我们能解决这个问题吗?一个叫 Haskell Curry有一个巧妙的技巧，如果你有好的高阶 那么你只需要一个变量的函数。的 证明是你可以从函数2(或更多) 一般情况下)变量以1变量为纯粹 像这样的机械文本转换:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

在那里……完全一样。(这个技巧叫做 “模仿”它的发明者。Haskell也是一种语言 以哈斯克尔·库里命名。把它归为无用的琐事。) 现在只要把这个变换应用到任何地方，我们就得到 我们的最终版本。

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

尽管试一试。Alert()返回，将其绑定到一个按钮，等等。 该代码不使用，递归地计算阶乘 2变量的赋值、声明或函数。(但 试图追踪它是如何工作的可能会让你头晕目眩。 递过来，没有推导，只是稍微重新格式化了一下 会导致代码令人困惑。)

可以将递归定义阶乘的4行替换为 任何你想要的递归函数。

this运算符可以简化你的生活:

var Y = function(f) {
    return (function(g) {
        return g(g);
    })(function(h) {
        return function() {
            return f.apply(h(h), arguments);
        };
    });
};

这样就避免了额外的函数:

var fac = Y(function(n) {
    return n == 0 ? 1 : n * this(n - 1);
});

最后，调用fac(5)。

y组合子实现匿名递归。所以与其

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

你可以这样做

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

当然，y-combinator只适用于按名字命名的语言。如果你想在任何正常的值调用语言中使用它，那么你将需要相关的z-combinator (y-combinator将发散/无限循环)。

上面的大多数答案描述了y组合子是什么，但没有描述它的用途。

用不动点组合子来证明lambda演算是图灵完备的。这是计算理论中一个非常重要的结果，为函数式编程提供了理论基础。

学习不动点组合子也帮助我真正理解了函数式编程。但我从未发现它们在实际编程中有任何用处。

匿名的递归

定点组合子是一种根据定义满足等价的高阶函数固定

forall f.  fix f  =  f (fix f)

固定f表示定点方程x的解

               x  =  f x

自然数的阶乘可以用

fact 0 = 1
fact n = n * fact (n - 1)

在一般/μ-递归函数上使用固定的、任意的构造证明可以在没有匿名自指性的情况下导出。

fact n = (fix fact') n

在哪里

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

这样

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

这个形式证明

fact 3  =  6

系统地使用定点组合子等价来重写

fix fact'  ->  fact' (fix fact')

微积分

无类型lambda演算形式主义包含在上下文无关的语法中

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

v在变量范围内，和约简规则一起

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Beta约简用表达式(“参数”)e替换抽象(“函数”)体B中变量x的所有自由出现。Eta约简消除了冗余抽象。它有时在形式主义中被省略。不适用约简规则的不可约表达式是正常形式或规范形式。

λ x y. E

是简写

λ x. λ y. E

(抽象multiarity),

E F G

是简写

(E F) G

(应用程序left-associativity),

λ x. x

and

λ y. y

alpha-equivalent。

抽象和应用是lambda演算中仅有的两个“语言原语”，但它们允许对任意复杂的数据和操作进行编码。

教会数字是一种自然数的编码，类似于花生公理化自然数。

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

一个正式的证明

1 + 2  =  3

使用beta约简重写规则:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

组合子

在lambda微积分中，组合子是不包含自由变量的抽象。最简单的，I，单位组合子

λ x. x

同构的恒等函数

id x = x

这样的组合子是像SKI系统这样的组合子计算器的基本操作符。

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

减少不是强归一化;并不是所有的可约化表达式，“重解”，在约简下收敛到正常形式。一个简单的例子是ω ω组合子的发散应用

λ x. x x

本身:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

减少最左边的子表达式(“头”)是优先的。应用顺序在替换前规范化参数，常规顺序则不然。这两种策略类似于渴望求值(例如C)和懒惰求值(例如Haskell)。

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

在热切应用阶beta缩减下发散

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

因为在严格的语义上

forall f.  f _|_  =  _|_

但在惰性法阶约简下是收敛的

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

如果一个表达式具有正规形式，则用正规阶beta缩减法可以找到它。

Y

Y定点组合子的基本性质

λ f. (λ x. f (x x)) (λ x. f (x x))

是由

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

等效

Y g  =  g (Y g)

同构于

fix f  =  f (fix f)

无类型lambda演算可以在一般/μ递归函数上编码任意构造证明。

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(乘法延迟，汇流)

对于丘奇无类型lambda演算，除了Y之外，已经证明存在一个递归可枚举的无穷个定点组合子。

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

法阶beta约简使未扩展的无类型lambda演算成为一个图灵完全重写系统。

在Haskell中，可以优雅地实现定点组合子

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

Haskell的惰性在所有子表达式都被求值之前归一到有限。

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

---

大卫·特纳:丘奇的论文和函数式编程 阿朗佐·丘奇:初等数论的一个不可解问题 微积分 Church-Rosser定理