9月 12 2014

［译］The Y Combinator

原文地址：猛击这里

博主竟然还是萌妹（误。

当你看到“Y Combinator”的时候会想到什么？如果你和我们一样，你大概会想到那家位于加利福尼亚的风投公司（比较为人所知的应该是Hacker News。

嗯，这里所说的是不动点组合子。下面是它最初的形式：

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

不不，请不要逃跑！（的确很想就是了…）这是为什么Y Combinator为什么以它命名的原因… 某种意义上它确实很酷。

为了理解究竟λf. (λx. f (x x))(λx. f (x x))是什么意思和它能够做什么，首先我们要先了解一些lambda演算的基础。

注：如果你对函数式编程感兴趣或者对它好奇，我想你一定会享受这篇文章。如果并没有完全理解，没关系，这篇文章又不会消失！

译注：为了便于理解下文的内容，需要说明一下lambda演算中的符号表示，即：

λx y. x+y 表示一个匿名函数，其接受x y作为参数，并返回x+y
函数式编程中，函数调用的形式是 (f x y) 而不是 f(x y)
符号”:=”代表”等于”的意思

Lambda 演算

Lambda演算（或λ－演算）是在1930年被Alonzo Church作为一种表达计算的形式系统（formal system for expressing computation）发明的。尽管其中有“微积分”一词（calculus），它却与牛顿和莱布尼兹发明的微积分相差很远。事实上，它在计算机领域的应用要比数学上要多，就我们大多数人所知。

有效的Lambda表达式可以用归纳法如下定义：

一个变量 x 是一个有效的Lambda表达式
如果 t 是一个有效的Lambda表达式并且 x 是一个变量，那么 λx. t 是一个有效的Lambda表达式
如果 t 和 s 都是有效的Lambda表达式，那么 t s 是一个有效的Lambda表达式

用例子来说明可能会更加形象。让我们从草稿开始构建一些Lambda表达式。之后我们会探讨它们的含义…

基于规则1，我们可以构造这样的Lambda表达式：

x
y

很好，这些看起来还不错。下面让我们看看用规则2能做什么。
既然我们已经有了合法的表达式 x 和 y 我们可以创造：

λx. x
λy. y
λx. y
λy. x

然后是规则3:

x x
x y
(λx. x) y
(λy. y) x
(λx. x) (λx. x)
(λy. y) (λx. x)
…

小练习：试着写一些你自己的Lambda表达式。

现在让我们来看看刚刚写下的Lambda表达式。

λx. x也被称作恒等函数（identify function）。λx. x <-这里加粗的x可以被解释为输入，λx. x <-这里加粗的x可以被解释为输出。也就是说，这个函数取一个输入x，然后输出相同的x。

如果你用一些支持Lambda的语言，比如Ruby，你可能已经见过这样的写法：

1	i = ->(x) { x }

如果你斜过来看一会，你可能会发现->符号有些像λ。

那么什么是λx. y？这是所谓的常函数。它忽略输入x然后返回y。

1	c = ->(x){ y }

你可能会问，“λy. y是不是恒等函数？“ 的确。λx. x和λy. y是 α-恒等(α-equivalent)的。事实上，以下这些都是α-恒等的：

λx. x
λy. y
λz. z
λ☃. ☃

这将带领我们来到对 约束变量 和 自由变量 的讨论。

##约束变量 vs. 自由变量

一个约束变量是在λ 的表达式中出现的变量并与参数具有相同的名字。一个自由变量是一个不是约束变量的变量。

举个例子，x 在 λx. x 中是一个约束变量，在 (λy.y)x 中是自由变量（传入参数）。

关于约束变量比较特殊的一点是你可以任意的重命名他们，只要对所有的变量应用就没问题。如果两个λ表达式在经过重命名后是一样的，那么就称他们是 α相等（α-equivalent）。

来看一个实际的例子：

1	m = ->(horrible_variable_name) { horrible_variable_name * y }

在这个例子中，把horrible_variable_name（约束变量）重命名是很安全的（例如x）：

1	m = ->(x) { x * y }

注意，你不能去重命名y，因为它是在区域外被定义的。或许y被定义为数字2，并且m是一个函数将自己的输入乘以2。如果我们直接讲y重命名为z（让我们假设它被定义为0），m将会变成一个永远返回0的函数呢。

##函数应用

太酷了，我们有了函数！但是它的参数是什么呢？这时野生的规则3就跳出来了！

如果 t 和 s 都是有效的Lambda表达式，那么 t s 是一个有效的Lambda表达式

(λx.x)y 就是一个函数应用的例子。更具体的说，它表示了以y作为传入参数时对函数λx.x的调用。

我们可以使用 β－规约（β-reduction）来化简（reduce）一个函数应用。

β－规约告诉我们表达式 (λx. t) s 可以被化简为 t [x := s] 读作“表达式t中所有的x都被替换为s“（t where all bound occurrences of x in t are substituted for s）

举个例子，将在x中所有的约束出现（在这个例子中恰好也是x）替换为x我们可以将 (λx. x) s 化简为 s。

(λx. x) s
x [x := s]
s

这样，我们看到 λx. x 做了和我们期待中的恒等函数一模一样的事情。

另一件值得一提的事情是我们可以定义一个获取多于一个参数的函数，基于λ表达式的递归定义。

译注：这里想要说明的应该是函数的柯里化（Currying）。关于柯里化，可以参见维基百科

举个例子，看一下这个表达式：

λy.(λx. x) y

然后喂给它两个参数，a 和 b：

(λy.(λx. x) y) a b
((λx. x) y) [y := a]) b
(λx. x) a b
(x [x := a]) b
a b

注意这里的函数应用是左结合的，即：

(λy.(λx. x) y) a b = (((λy.(λx. x) y) a) b)

现在来看一下这个表达式：

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

试着对它用一下β－规约？

(λx. x x)(λx. x x)
(x x) [x := (λx. x x)]
(λx. x x)(λx. x x)

等等。我们是不是又回到了开始？我们刚刚发现了 Ω (omega) ，一个分歧组合子（divergent combinator）。当一个表达式不具备 β-范式(β-normal form) 的时候，就称它是分歧的。当一个lambda表达式不能被β-规约的时候，就称它表现出β-范式。一个组合子就是一个没有自由变量的lambda表达式。

你们不对无限递归感到好奇吗？（笑

谈到递归，我们怎么在lambda演算中定义类似于递归函数呢？用Ruby写起来可能像这样：

def fact(n)
  if n == 0
    1
  else
    n * fact(n-1)
  end
end

这个函数有什么特殊之处呢？它引用了自身。你可能会说类似”噢，这不过是递归而已“这样的话，不过你很可能会对lambda演算中不允许这种类型的自我引用感到吃惊，至少不是直接引用。

自我引用是一种如此简单却强大的概念，允许了像下面这句话一样对存在性的好奇。

This statement is false. （这个命题是错误的。）

那么，这个命题为真吗？如果它为真，那么它是假的；如果它为假，那么它是真的。

再来一些命题如何？

The statement below is true.（下面这个命题是真的）
The statement above is false.（上面这个命题是假的）

如果这引起了你的好奇心，那么我推荐你读一下Douglas Hofstadter的 Gödel, Escher, Bach（译注：中文名似乎叫 GEB:集异璧之大成 传说中原作者参与翻译的中译本，不可多得的奇书）。到目前为止我只读了一半，感觉就像在埃舍尔的迷宫中漫游一样。相信我，迷失在其中是值得的，但是我好像跑题了（笑。

Escher's labyrinth

那么，我们是如何在不采用自我引用的情况下达到自我引用呢？我想是时候回顾一下我们的神秘朋友，Y不动点组合子了。

##终焉，Y Combinator

来回顾一下我们的老朋友：

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

希望现在你对它感到更加熟悉了（笑。

现在回到阶乘函数。如果函数允许自我引用，我们就能写出如下定义：

f := λx.(if x == 0 then 1 else x * f (x–1))

但是很显然，我们已经知道这么做是不被允许的。那么，让我们回溯几步然后试一些完全不同的东西。让我们定义一个完全的lambda表达式F 以f作为参数：

F := λf. λx.(if x == 0 then 1 else x * f (x–1))

但是若想做到这一点，我们需要一些东西来使F启动，即提供给参数f一个初始值。此外，我们需要一个p使得Fp等于p。

这不仅仅是因为p是我们将要传入f（伪递归函数）这个λ表达式体中的值，同时也因为我们想要Fp能够完成和p自己能够完成的相同的事情，即允许指代它自己，而不是被当作参数传入。

以上这一段落对我来说是最棘手的一部分，它悄悄地介绍了没有直接自我引用的自我引用。所以在我们继续前进之前确保你已经理解了为什么我们要让Fp和p相等。请再读一遍吧（笑。

那么，换句话说，我们想要找到F的一个不动点。在数学的定义上，一个函数的不动点就是使得f(x) 等于 x的x取值。举个例子，对于函数f(x) = x * x，0和1就是它的不动点。

顺着这个想法，如果我们找到一个F的不动点p使得Fp等于p，我们就可以用Fp或者p（它们是同一种东西）作为那个没有直接自我引用的“递归函数”。

显然对于任意的λ表达式f，(λx. f (x x))(λx. f (x x))是它的一个不动点。

让我们看看这是怎么一回事。

X = (λx. f (x x))(λx. f (x x))
X = f (x x) [x := λx. f (x x)]
X = f ((λx. f (x x)) (λx. f (x x)))
X = f X

你可以看到，对于任意的函数f，输入X保持不变。

得知了这一点，我们就可以构造一个函数，其参数为一个函数f并返回它的不动点：

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

没错，这就是我们的Y-combinator，Y不动点组合子。它返回任意函数f的不动点。让我们称呼它为Y。对于任意函数f，Yf是f的一个不动点，换句话说，f(Yf)和Yf是相等的。事实上，出于这个原因，Y－不动点组合子也被称为不动点组合子。

那么现在，我们可以令p = Yf来满足Fp等于p的要求。为了驱动这个函数，我们可以令p作为F的参数来得到F(YF)，它恰好等于YF。现在我们已经准备好了。

现在让我们看看用它来实现阶乘会发生什么。试着喂给它一个3。

YF 3
F(YF) 3
λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 3
λx.(if x == 0 then 1 else x (YF)(x–1)) 3
if 3 == 0 then 1 else 3 (YF)(3–1)
3 (YF) 2
3 F(YF) 2
3 (λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 2)
3 (λx.(if x == 0 then 1 else x (YF)(x–1)) 2)
3 (if 2 == 0 then 1 else 2 (YF)(2–1))
3 (2 (YF) 1)
6 (YF) 1
6 F(YF) 1
6 (λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 1)
6 (λx.(if x == 0 then 1 else x (YF)(x–1)) 1)
6 (if 1 == 0 then 1 else 1 (YF)(1–1))
6 (YF) 0
6 F(YF) 0
6 (λf. λx.(if x == 0 then 1 else x f (x–1)) (YF) 0)
6 (if 0 == 0 then 1 else 0 (YF)(0–1))
6 1
6

…现在你得到它了。

3! = 6

以上。

Phantom Shrine

Haskell, Programming Languages, Hardware, and Happy Hacking!

［译］The Y Combinator

Lambda 演算

##约束变量 vs. 自由变量

##函数应用

##终焉，Y Combinator