简明Y-combinator指南

程序设计理论 Y组合子

本文试图给出一个简洁的Y-combinator的小课程，它源自与这个帖子。我进行了翻译，改写，并简化了相关内容。希望对大家有所帮助。我只是一个搬运工，功劳归原作者。读者基本无需什么基础，只要有一个可以运行Scheme的环境即可，边看边动手试一下。

为什么需要学习Y-combinator?

• 它是计算机程序理论中最优雅的理论之一。

• 它是区分懂程序理论与懂写程序的试金石之一。

以阶乘(Factorials)为例

阶乘的递归定义：

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

阶乘的Scheme程序：

  (define (factorial n)
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

阶乘的另一种Scheme写法

  (define factorial
    (lambda (n)
      (if (= n 0)
          1
          (* n (factorial (- n 1))))))

使用Lambda定义的函数是一种匿名函数，即函数本身没有名字。以上两个递归程序等价。

“消灭”递归

思考: 使用Scheme定义factorial函数是否可以不使用递归？

答案是肯定的，而这直接引出Y combinator。

理论基础

以下解释一些基本概念

什么是Y combinator？

Y-combinator是一种高阶函数，它的输入是一种函数（非递归），它可以返回一种递归函数。

Lazy求值还是Strict求值？

• Lazy evaluation，对表达式求值，你只需要对可得到最终结果的部分进行求值，即不影响最终结果的部分不会被计算。
• Strict evaluation，表达式的所有部分都被求值，然后得到最终结果。

实践中，lazy evaluation更通用，但strict evaluation更容易控制且更高效。

以下内容两种方法都将涉及。

只有一种Y combinator还是有多种?

实际上，有无穷种Y-combinator，以下只涉及两种：lazy型和strict型，分别记为：normal-order Y combinator 和applicative-order Y combinator（SICP中的概念）。

静态类型还是动态类型?

以下定义使用动态类型，具体细节暂时可以不讨论。Scheme支持动态类型。

什么是"combinator"？

Combinator（组合子）是一种没有自由变量的Lambda表达式。

实例，分析以下表达式的自由变量与受限变量：

(lambda (x) x)
(lambda (x) y)
(lambda (x) (lambda (y) x))
(lambda (x) (lambda (y) (x y)))
(x (lambda (y) y))
((lambda (x) x) y)

答案：

1、x是受限变量，这是一个combinator.
2、y是自由变量，不是combinator.
3、x是受限变量，这是一个combinator.
4、x和y都是受限变量，这是组合子.
5、非lambda表达式，非组合子；x是自由变量，y是受限变量.
6、非lambda表达式，非组合子；x是受限变量，y是自由变量.

以下定义是否combinator？

   (define factorial
     (lambda (n)
       (if (= n 0)
           1
           (* n (factorial (- n 1))))))

否！

以下定义是否组合子？

  (lambda (n)
    (if (= n 0)
        1
        (* n (factorial (- n 1)))))

否！因为，factorial是自由变量。

回到问题中来

抽象出递归函数调用

之前给出的factorial函数：

  (define factorial
    (lambda (n)
      (if (= n 0)
          1
          (* n (factorial (- n 1))))))

我们试图把函数体中的factorial去掉。

首先我们这样做：

  (define sort-of-factorial
    (lambda (n)
      (if (= n 0)
          1
          (* n (<???> (- n 1))))))

里面应该放什么？

函数式编程中的一个原则：当你不知道那里要放什么，你就把它抽象出来，然后把它作为一个函数的参数。因此，我们得到：

  (define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))

这里我们干了这样一些事情：把对factorial的递归调用重新命名为f，然后把f作为一个函数的参数，这个函数我们命名为almost-factorial。注意：almost-factorial并非factorial函数，它是一个高阶函数，输入一个参数f（f是函数），然后返回另一个函数(就是(lambda (n) ...) 那部分)。这个函数有望成为一个factorial函数，如果我们选对了f的话！

预知未来

提前透露一下以下我们大概想做的事情：一旦我们定义好 Y-combinator，我们就可以使用Y和almost-factorial来定义factorial函数：

  (define factorial (Y almost-factorial))

从而在不需要递归调用的前提下得到一个递归函数。

从 almost-factorial得到factorial

假定我们有一个factorial function factorialA，无论如何得到，也无论它是否递归。考虑一下程序：

  (define factorialB (almost-factorial factorialA))

问题：factorialB是否阶乘函数？

要回答这个问题，我们需要展开almost-factorial的定义:

  (define factorialB
    ((lambda (f)
       (lambda (n)
         (if (= n 0)
             1
             (* n (f (- n 1))))))
     factorialA))

现在，用factorialA替换f，得到:

  (define factorialB
    (lambda (n)
      (if (= n 0)
          1
          (* n (factorialA (- n 1))))))

这很像一个递归的阶乘函数，但它并不是：factorialA并不等同factorialB。所以，它是一个依赖于factorialA的非递归函数。它能正常工作吗？当然，稍微分析可知，factorialB能计算阶乘当且仅当factorialA是一个阶乘函数。现在的问题是，我们不知道factorialA怎么得来！

我们能否这样定义：

  (define factorialA (almost-factorial factorialA))

思路是：如果factorialA是一个正常的阶乘函数，我们把它扔给almost-factorial函数就又得到一个正确的阶乘函数，为什么不把这个函数命名为“factorialA”？但是，这......分明就是“永动机”啊！

实际上，如果你使用DrScheme，并且使用"lazy Scheme" language level，这个定义竟然是对的！！！

定义以下函数:

  (define identity (lambda (x) x))
  (define factorial0 (almost-factorial identity))

identity函数很简单：输入一个参数，然后输出该参数。这是一个组合子。我们使用它作为占位符，在我们需要传输一个函数作为参数但又不知道需要传送什么函数的时候使用它。

factorial0计算输入为0时的阶乘值。验证如下：

  (factorial0 0)
  ==> ((almost-factorial identity) 0)
  ==> (((lambda (f)
          (lambda (n)
             (if (= n 0)
                 1
                 (* n (f (- n 1))))))
        identity)
       0)
  ==> ((lambda (n)
         (if (= n 0)
             1
             (* n (identity (- n 1)))))
       0)
  ==> (if (= 0 0)
          1
          (* 0 (identity (- 0 1))))
  ==> (if #t
          1
          (* 0 (identity (- 0 1))))
  ==> 1

OK，确实是对的，但当n > 0时它无法计算。比如，n = 1时：

  (factorial0 1)
  ==> (* 1 (identity (- 1 1)))
  ==> (* 1 (identity 0))
  ==> (* 1 0)
  ==> 0

错！考虑下一个程序:

  (define factorial1
    (almost-factorial factorial0))

它可以计算0和1的阶乘。自己验证。我们这样做下去：

  (define factorial2 (almost-factorial factorial1))
  (define factorial3 (almost-factorial factorial2))
  (define factorial4 (almost-factorial factorial3))
  (define factorial5 (almost-factorial factorial4))

用这种方法，尽管我们可以得到某个n的阶乘函数，但是我们还是无法得到一个任意n的函数。

函数的不动点

函数f的不动点(fixpoint)就是一个值x，使得f(x) = x。不动点不但可以是值，还可以是函数，实际上可以是不同的实物。almost-factorial的不动点就是一个函数：

  fixpoint-function = (almost-factorial fixpoint-function)

通过替换：

  fixpoint-function =
    (almost-factorial
      (almost-factorial fixpoint-function))
    = (almost-factorial
        (almost-factorial
          (almost-factorial fixpoint-function)))
    = ...
    = (almost-factorial
        (almost-factorial
          (almost-factorial
            (almost-factorial
              (almost-factorial ...)))))

不难看出，almost-factorial的不动点就是阶乘函数：

  factorial = (almost-factorial factorial)
    = (almost-factorial
        (almost-factorial
          (almost-factorial
            (almost-factorial
              (almost-factorial ...)))))

但是仅仅知道factorial是almost-factorial的不动点并不够。如何求得这个不动点呢？

使用Y combinator！ Y也被称为不动点组合子：给定一个函数，求该函数的不动点。

消灭递归(lazy版本)

Y的工作是：

  (Y f) = fixpoint-of-f

f的不动点是什么？由定义，我们知道：

  (f fixpoint-of-f) = fixpoint-of-f

因此：

  (Y f) = fixpoint-of-f = (f fixpoint-of-f)

得到：

  (Y f) = (f (Y f))

乌拉！我们定义出来Y！写成Scheme程序就是：

  (define (Y f) (f (Y f)))

或者用Lambda：

  (define Y
    (lambda (f)
      (f (Y f))))

然而，这里有两个问题：

1、它只能在lazy语言中工作。
2、这个Y并不是一个combinator，因为Y在定义体中是自由变量，只有定义结束它才是受限变量。

无论如何，如果你使用lazy Scheme，你确实可以得到一个factorials:

  (define Y
    (lambda (f)
      (f (Y f))))
  (define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))
  (define factorial (Y almost-factorial))

这是正确的！

我们完成了什么？开始我们试图不使用递归调用来定义factorial函数，现在基本完成任务。然而，目前的Y还是递归的。不可否认，我们已经前进了一大步，为了定义递归函数，仅仅在Y的定义中使用递归。

消灭递归(strict 版本)

如果在标准Scheme中使用以上定义：

  (Y f)
  = (f (Y f))
  = (f (f (Y f)))
  = (f (f (f (Y f))))

(Y f)的求值将不终止，也就是说以上定义不适合 strict语言。

有一种聪明的方法可以拯救世界。考虑到(Y f)是一个带一个参数的函数，因此，这等式满足：

  (Y f) = (lambda (x) ((Y f) x))

无论(Y f) 这个函数是什么，(lambda (x) ((Y f) x))都与之等价。

根据以上分析，Y可以被定义为：

  (define Y
    (lambda (f)
      (f (lambda (x) ((Y f) x)))))

既然(lambda (x) ((Y f) x)) 与 (Y f)等价，以上定义是对的！我们可以使用这个Y来定义factorial函数。

最酷的是，这个版本的Y可以工作在strict语言中 (比如标准Scheme)！因为，如果你给Y一个f，让它找不动点，它返回：

  (Y f) = (f (lambda (x) ((Y f) x)))

这一次，不会陷入无穷循环，因为内部的(Y f)被一个Lambda表达式保护着，它保持不动直到它需要被求值（Scheme中，lambda表达式不会被求值，直到它被应用到某个参数上）。本质上，我们是使用lambda来对(Y f)延迟求值。所以，如果f是almost-factorial，我们会得到：

  (define almost-factorial
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1)))))))
  (define factorial (Y almost-factorial))

展开对Y的调用：

  (define factorial
    ((lambda (f) (f (lambda (x) ((Y f) x))))
     almost-factorial))
  ==>
  (define factorial
    (almost-factorial (lambda (x) ((Y almost-factorial) x))))
  ==>
  (define factorial
    (lambda (n)
      (if (= n 0)
          1
          (* n ((lambda (x) ((Y almost-factorial) x)) (- n 1))))))

请验证！

以上分析也许容易，也许不容易，无论如何，鼓励大家去尝试，必要收获。至此，我们基本完成任务，除了一点细节。作为简明版本tutorial，就此略过。详细内容请看Mike帖子。