我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

让我们重构并创建一个名为fact的新函数，它返回一个匿名的阶乘计算函数，而不是执行计算本身:

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

这有点奇怪，但这没什么问题。我们只是在每一步生成一个新的阶乘函数。

这个阶段的递归仍然相当明确。事实函数需要知道自己的名字。让我们参数化递归调用:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

这很好，但是递归仍然需要知道自己的名字。让我们把它参数化:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

现在，我们不直接调用递归器(recurser)，而是创建一个包装器函数，返回它的结果:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

现在我们可以完全去掉递归的名字;它只是Y内部函数的一个参数，可以用函数本身替换:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

唯一仍然引用的外部名称是fact，但现在应该清楚了，它也很容易参数化，创建完整的，通用的解决方案:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

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

如果你准备好长篇大论，Mike Vanier有一个很好的解释。长话短说，它允许您在一种不一定支持递归的语言中实现递归。

不动点组合子(或不动点运算符)是一种高阶函数，用于计算其他函数的一个不动点。此操作与编程语言理论相关，因为它允许以重写规则的形式实现递归，而不需要语言的运行时引擎的显式支持。(src维基百科)

其他答案对此提供了相当简洁的答案，但没有一个重要的事实:你不需要用任何实用语言以这种令人费解的方式实现定点组合子，这样做没有任何实际目的(除了“看，我知道y组合子是什么”)。这是一个重要的理论概念，但没有什么实际价值。

匿名的递归

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

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定理

JavaScript中的y组合子:

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

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120

编辑: 通过查看代码，我学到了很多东西，但是如果没有一些背景知识，这个代码有点难以理解——对此我感到抱歉。有了其他答案提供的一些常识，你就可以开始分析正在发生的事情了。

The Y function is the "y-combinator". Now take a look at the var factorial line where Y is used. Notice you pass a function to it that has a parameter (in this example, recurse) that is also used later on in the inner function. The parameter name basically becomes the name of the inner function allowing it to perform a recursive call (since it uses recurse() in it's definition.) The y-combinator performs the magic of associating the otherwise anonymous inner function with the parameter name of the function passed to Y.

关于Y如何变魔术的完整解释，请查看链接文章(顺便说一下，不是我写的)。