Shell's Home

Oct 9, 2012 - 2 minute read - Comments

Y Combinator

不动点理论

假定我们有一个函数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)。

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

  1. 首先let需要计算f,而f = (Y F)。F为以下函数,在let之后,F的值被唯一确定(赋值)。

    (lambda (h)
      (lambda (n)
        (if (< n 2) 1 (* n (h (- n 1))))))
    
  2. 因此,我们考虑以参数F计算以下表达式。

    (let ((g (lambda (h)
           (lambda (x) ((F (h h)) x)))))
      (g g))
    
  3. 这里,第二个let需要计算g,不过他已经很明显了。这很重要,因为在这个let中,g的值被唯一确定。他是一个lambda表达式,虽然这个表达式内有一些东西没被算出来(例如h)。

  4. 我们计算f = (g g) = (lambda (x) ((F (g g)) x))。在这个表达式内,f的值也被唯一确定,是一个lambda表达式。

  5. 现在,我们有了f,可以计算(f 10)了。

  6. (f 10) = ((F (g g)) 10) = ((F f) 10)。看到没有,不动点。

  7. 上文真正需要计算的是((F (g g)) 10),其中,(g g)需要被展开。而恰好,我们知道他的展开结果。

  8. ((F (lambda (x) ((F (g g)) x))) 10),这时才会对F进行计算。

  9. 上面的展开结果是((lambda (n) (if (< n 2) 1 (* n ((lambda (x) ((F (g g)) x)) (- n 1))))) 10)。而这就是一个纯粹的计算问题了。结果很明确,是(* 10 ((lambda (x) ((F (g g)) x)) 9))。

  10. 这时((lambda (x) ((F (g g)) x)) 9)会被求值,结果应该是((F (g g)) 9)。

  11. 此时我们就跳回了步骤7。

  12. 直到n=1,递归会逐步退回(很遗憾,这还不是尾递归。不过看过sicp的人都应当能想到如何改为尾递归)。

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

注意

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

  1. 和上一节的1一样,略。
  2. 我们修改一下表达式。

    (let ((g (lambda (h) (F (h h)))))
      (g g))
    
  3. 同样,g是唯一确定的。

  4. f = (g g) = (F (g g))。

  5. 和上面的4不一样,那时f是一个lambda表达式,可以延迟求值。这里的f可是一个表达式,必须先求值。但是对(g g)求值的结果是什么?死循环。

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

推导

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

  1. 首先,我们的算法是这样的。

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

    (let ((g (lambda (h n)
           (if (< n 2) 1 (* n (h h (- n 1)))))))
      (g g 10))
    
  3. 我们可以将上面的函数柯里化,转换为下面的函数。

    (let ((g (lambda (h)
           (lambda (n)
            (if (< n 2) 1 (* n ((h h) (- n 1))))))))
      ((g g) 10))
    
  4. 我们可以将上面的函数转换为下面的样子。

    (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)))
    
  5. 再柯里化一遍。

    (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)))
    
  6. 是不是看着眼熟?Y的定义出来了吧?

引用

  1. The Why of Y

Tags: computer scheme-2

小故事 国庆堵车

comments powered by Disqus