不动点理论

假定我们有一个函数f，例如，f(x) = x^2。对于某些点，f(x) = x。在这个例子里面，0和1很明显就是两个点。这样的点称为不动点。

不动点理论在各种领域有广泛应用，我记得其中之一就是在血型比例上。当ABO遗传规则固定后，存在一些ABO血型比例，这些比例的人随机通婚，生下来的孩子的血型比例亦保持不变。这是三种血型千百年来存在的基础，否则随着遗传规则比例转变，其中某些血型可能已经在地球上消失了。

也许你很好奇，当我们有了一个规则后，例如f(x) = x^2，或者ABO遗传规则（这也可以当作一个函数，将父代ABO比例转换为子代的），如何才能计算出函数的不动点。

答案是不动点算子。

高阶抽象函数的不动点

我们先不继续讨论不动点算子，让我们先讨论一下抽象函数。上面，我们的f都是具体的演算规则，x是一个数（例如x），或者一个矩阵（例如ABO，也可以当作一种数来考虑）。如果x是一个函数会如何？

我们先看一个递归的阶乘计算函数：

(define fact
  (lambda (n)
    (if (< n 2) 1 (* n (fact (- n 1))))))

这是一个典型的阶乘计算函数，没错。问题是，我们在lambda里面调用了fact。从语言层面上说，这样做合法。然而从语言的研究角度说，这难免会带来一个问题。函数的名字，到底是一个可有可无的别名，还是一个在递归中必须的东西。如果是前者，我们可以完全用lambda构造递归函数。而如果是后者，我们无论如何努力，也无法仅仅使用lambda来构造一个递归。

OK，这和不动点有什么关系？这时，我们先假定函数f，是真正的阶乘计算函数。即f(n) = n!。那么对于以下函数，((F f) n) = (f n)。

F = (lambda (h) (lambda (n) (if (< n 2) 1 (* n (h (- n 1))))))

看不懂为什么？这是一个柯里化函数。当我们传递真正的阶乘函数f给F的时候，在函数体内，他叫做h。而按照f(n-1)的定义，我们得到的值和(f n)没有区别。因此，我们有(F f) = f，你也可以写作F(f) = f。

是不是觉得眼熟？是的，f是函数F的一个不动点。要获得真正的阶乘函数f，我们只要对F计算不动点即可。

Y算子

Y算子(或者叫做Y组合子)是另一种高阶函数，用于计算任意函数的不动点。

假定对于函数f，存在不动点x，有f(x) = x，那么Y(f) = x，这是Y算子的基础。按照上文代入，我们可以得到f(Y(f)) = Y(f)，或者可以写作scheme格式：(f (Y f)) = (Y f)，这就是Y算子。

我们先跳过Y算子的推导过程，直接给出他的scheme表达式：

(define Y
  (lambda (f)
    (let ((g (lambda (h)
           (lambda (x) ((f (h h)) x)))))
      (g g))))

验证

对于上文的F，我们有他的scheme定义，而要获得真正的阶乘函数，只要用Y作用于F的原始定义即可。

(let ((f (Y (lambda (h)
             (lambda (n)
              (if (< n 2) 1 (* n (h (- n 1)))))))))
  (display (f 10)))

这里就可以获得f(10)。

我们验证一下，看看事情是怎么走的。

首先let需要计算f，而f = (Y F)。F为以下函数，在let之后，F的值被唯一确定(赋值)。
```
(lambda (h)
  (lambda (n)
    (if (< n 2) 1 (* n (h (- n 1))))))
```

因此，我们考虑以参数F计算以下表达式。

(let ((g (lambda (h)
       (lambda (x) ((F (h h)) x)))))
  (g g))

这里，第二个let需要计算g，不过他已经很明显了。这很重要，因为在这个let中，g的值被唯一确定。他是一个lambda表达式，虽然这个表达式内有一些东西没被算出来(例如h)。
我们计算f = (g g) = (lambda (x) ((F (g g)) x))。在这个表达式内，f的值也被唯一确定，是一个lambda表达式。
现在，我们有了f，可以计算(f 10)了。
(f 10) = ((F (g g)) 10) = ((F f) 10)。看到没有，不动点。
上文真正需要计算的是((F (g g)) 10)，其中，(g g)需要被展开。而恰好，我们知道他的展开结果。
((F (lambda (x) ((F (g g)) x))) 10)，这时才会对F进行计算。
上面的展开结果是((lambda (n) (if (< n 2) 1 (* n ((lambda (x) ((F (g g)) x)) (- n 1))))) 10)。而这就是一个纯粹的计算问题了。结果很明确，是(* 10 ((lambda (x) ((F (g g)) x)) 9))。
这时((lambda (x) ((F (g g)) x)) 9)会被求值，结果应该是((F (g g)) 9)。
此时我们就跳回了步骤7。
直到n=1，递归会逐步退回（很遗憾，这还不是尾递归。不过看过sicp的人都应当能想到如何改为尾递归）。

而这里就解决了一个有趣的问题。当lambda内没有自己的名字时，如何调用自身？方法是将函数体包装在另一个lambda内。外层的lambda接收一个参数，这个参数就是自身。而最后得到的整一个函数，又需要用Y算子运算过。这样会还原出原始的递归定义。或者你可以说，Y算子帮助lambda函数实现了无名字的递归。

注意

而我们也注意到，(lambda (x) ((f (h h)) x)) = (f (h h))。但是如果你胆敢这么写，就等着循环到溢出吧。我们可以看一下原因。

我们修改一下表达式。

(let ((g (lambda (h) (F (h h)))))
  (g g))

同样，g是唯一确定的。
f = (g g) = (F (g g))。
和上面的4不一样，那时f是一个lambda表达式，可以延迟求值。这里的f可是一个表达式，必须先求值。但是对(g g)求值的结果是什么？死循环。

为什么？通常而言，第二种写法不可以，除非这个语言是应用序的。

推导

我们现在说一下Y算子的推导过程。

首先，我们的算法是这样的。

(define fact
  (lambda (n)
   (if (< n 2) 1 (* n (fact (- n 1))))))

你应当可以理解下面的手法，利用重复传入递归函数本身，避免自身引用的问题。
```
(let ((g (lambda (h n)
       (if (< n 2) 1 (* n (h h (- n 1)))))))
  (g g 10))
```

我们可以将上面的函数柯里化，转换为下面的函数。

(let ((g (lambda (h)
       (lambda (n)
        (if (< n 2) 1 (* n ((h h) (- n 1))))))))
  ((g g) 10))

我们可以将上面的函数转换为下面的样子。

(let ((g (lambda (h)
       (lambda (n)
         (let ((f (lambda (q n)
            (if (< n 2) 1 (* n (q (- n 1)))))))
           (f (h h) n))))))
  (display ((g g) 10)))

再柯里化一遍。

(let ((g (lambda (h)
       (lambda (n)
         (let ((f (lambda (q)
            (lambda (n)
              (if (< n 2) 1 (* n (q (- n 1))))))))
           ((f (h h)) n))))))
  (display ((g g) 10)))

是不是看着眼熟？Y的定义出来了吧？

引用

The Why of Y