published on
tags: tech scheme

Y-combinator的推导

今天花费了巨大的努力,自己推导了一遍Y-combinator。发现结果蛮简单的,就是中间遇到了几个障碍消耗了很久,作此文记录一下。

下文代码均使用scheme,不过对其要求不高,本来我对scheme知道的也不多。

引入:什么是Y-combinator

这里直接讲这玩意做什么的吧,历史上是怎么产生的我就没追溯了。

一句话来描述就是,我们可以通过这个玩意编写匿名递归函数。

先看例子吧,举个简单的递归函数:计算阶乘(好像大家都喜欢用这个例子)

(define fact
  (lambda (n)
    (if (equal? n 0)
        1
        (* n (fact (- n 1))))))

注意如果我们要将其写成一个匿名函数,那么我们不可能在函数里面使用fact,那么通过加一个self参数可以解决这个问题。

(define fact
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

这样调用的时候写成: ((fact fact) 6),可惜这样写是错的…., 因为上面最后一行需要写成 (* n ((self self) (- n 1)))))))

这样就编写出来了可以匿名递归的函数,但是有一个麻烦的地方是你程序里面要写成(self self),别人调用的时候也要写两遍函数名,这样就还有改进的空间。下面开始改进,我们用F表示这个函数,我们自己希望写成(不包括define F的部分):

(define F
  (lambda (self)
    (lambda (n)
      (if (equal? n 0)
          1
          (* n (self (- n 1)))))))

然后有一个运算符Y,只要执行(Y F),就得到了我们想要的内容。比如

(define fact (Y F))
(fact 6) ;=> this return 720

那么主要的工作就是这个Y长什么样了

Y的推导

注意到由于F的新写法,我们必须把正确的函数传进去,而不是传F自身,而正确的函数就是我们想要的(Y F),我们从这里开始。

(define Y
  (lambda (F)
    (F (Y F))))

这里的Y出现了递归,我们利用上文已经实现过的匿名递归技术来解决这个难题(写起来麻烦没关系,只要这次麻烦过了,呵呵~),将这个东西的名字叫做self-Y好了,于是代码演化成下面这样:

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (F ((self self) F))))))
    (self-Y self-Y)))

哦,我们居然把Y写出来了,可惜这里面还有一点小问题,仔细看一下你会发现这简直就直接死循环了啊… 问题在于这个问题是个递归的,而你想把它展开却没有边界条件…… 这就变成无限循环了。

于是有意思的地方来了,我们可以借用Lazy计算的思路,等到我要用到这个函数了,我再做这个运算,于是变成:

(define Y
  (let ((self-Y (lambda (self)
                 (lambda (F)
                   (lambda (n)
                     ((F ((self self) F)) n))))))
    (self-Y self-Y)))

这样只有当我们给出了F的参数之后,相应的展开工作才会进行,我们的fact函数可以完美运作了。

至此,我们就成功的推导出来了Y的实现。可喜可贺,可喜可贺。当然,对于我来说,只支持一个参数的F函数当然不够满意,利用scheme的语法特性,我们可以改成下面这样。

(define Y
  (let ((self-Y (lambda (self)
                  (lambda (F)
                    (lambda n
                      (apply (F ((self self) F)) n))))))
        (self-Y self-Y)))

使用的例子

最后给一个使用匿名的递归函数的例子, 下面的语句计算了1到7的阶乘:

(map (Y (lambda (self)
          (lambda (n)
            (if (equal? n 0)
                1
                (* n (self (- n 1)))))))
     '(1 2 3 4 5 6 7))