推导 Y Combinator(待完成)

    Programming Language

等了好久,终于能听 Ian 讲课了。一会儿北京时间 20:00 马上开始。之后尝试重新推导一下 Y 算子,纪念这个我一生中历史性的时刻。现在,我已经打开各种可能需要的软件准备就绪了。


先实现不使用 Define 的情况下能正常递归

第一步,正常写出 mylength 函数作为最简单的模型。这是一个接受链表(list)作为参数,返回其长度(一个整数值,显示链表中有效负载的数量)的函数。

(define mylength
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 (mylength (cdr l)))))))

测试 mylength 函数,输出正确的话就可以继续推导。

(mylength '(9 19 29))  ;; 输出 3 (链表有 3 个有效负载:9, 19, 29)

第二步,开始考虑如果没有 define 来绑定函数名的情况。于是,我们只能将上面 mylength 函数绑定在参数上。于是 mylength 函数作为参数传进去,以便能被调用。因此我们多加了一层嵌套,用这个嵌套带来的参数 mylength 绑定函数体内容。这样我们就可以使用它了。

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                           ;;
    (lambda (l)                                ;;
      (cond ((null? l) 0)                      ;;
            (else (+ 1 (mylength (cdr l))))))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (l)                                ;;
    (cond ((null? l) 0)                      ;;
          (else (+ 1 (mylength (cdr l))))))  ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

但是,如果直接调用这个函数就会报错。因为第二小块代码的 mylength 这个变量是没有定义的。于是我们把第二步中的代码(第二小块)修改成下面这样:

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                           ;;
    (lambda (l)                                ;;
      (cond ((null? l) 0)                      ;;
            (else (+ 1 (mylength (cdr l))))))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                           ;;
    (lambda (l)                                ;;
      (cond ((null? l) 0)                      ;;
            (else (+ 1 (mylength (cdr l))))))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

但这样还不够,因为两小块代码要求其输入参数 mylength 是个函数,不能是 (cdr l) 这种链表。运行到 (mylength (cdr l)) 这段的代码就会报错。于是我们再改代码,变成下面这样:

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                                      ;;
    (lambda (l)                                           ;;
      (cond ((null? l) 0)                                 ;;
            (else (+ 1 ((mylength mylength) (cdr l))))))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (mylength)                                      ;;
    (lambda (l)                                           ;;
      (cond ((null? l) 0)                                 ;;
            (else (+ 1 ((mylength mylength) (cdr l))))))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

到这步,我们发现这一大块代码可以直接调用来计算链表(list)的长度了。和之前有 define 时的代码效果一样:

(
((lambda (mylength)
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 ((mylength mylength) (cdr l)))))))

 (lambda (mylength)
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 ((mylength mylength) (cdr l))))))))

'(9 19 29))   ;; 输出 3

既然没有 define 代码也已能正确运行,就说明 Y 算子已经隐藏在其中了。于是我们可以开始各种调整,想办法提取整理出 Y 算子了。


推导 Y 算子

我们先观察一下最早有 define 的时候函数的样子:

(define mylength
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 (mylength (cdr l)))))))

我们的目标是把上一节最后看起来很多的代码转化成「一个函数的调用」,将「一块和最开始 define 的代码模式很像的代码」作为参数输入该函数。如果成功,那么该函数就是 Y 算子啦。可以用它来作用在其他更多的函数上实现递归。(如果看不明白目标,可以往下看完推导在回来看这段描述)

第 1 次转换:我们看到有两小块重复的代码,于是先提取它们

((lambda (f) (f f))

 (lambda (mylength)
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 ((mylength mylength) (cdr l))))))))

观察发现,第 1 次转换之后,代码已经很像原来有 define 时候的代码了。那么是不是 (lambda (f) (f f)) 就是 Y 算子呢?不是的,因为目前还不够像。(mylength mylength) (cdr l) 这一块的代码和原来的 (mylength (cdr l)) 相比,多了一次函数调用。我们要继续提取,把它变成调用次数一样的模式。也就是一个函数将 (mylength mylength) 想办法变成 mylength

第 2 次转换:(mylength mylength) 提取出来,通过函数调用来将它传入函数体

(
  (lambda (f) (f f))

  (lambda (mylength)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (g)                          ;;
      (lambda (l)                         ;;
        (cond ((null? l) 0)               ;;
              (else (+ 1 (g (cdr l))))))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (mylength mylength)
    )
  )
)

我们很高兴地发现,经过第 2 次转换之后,出现了长得很像原来 define 阶段的代码块了(被注释符号“框”起来的那块)。赶紧将这次转换得到的代码输入计算机,看看对不对吧:

(
  (
    (lambda (f) (f f))

    (lambda (mylength)
      (
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
       (lambda (g)                          ;;
        (lambda (l)                         ;;
          (cond ((null? l) 0)               ;;
                (else (+ 1 (g (cdr l))))))) ;;
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        (mylength mylength)
      )
    )
  )

'(9 19 29))   ;; 死循环

我们很遗憾发现,输入上面的这段代码,对函数进行调用,计算 (9 19 29) 的长度时,内存溢出,函数进入了死循环。到底是怎么回事呢?


中场分析

通过一步一步地拆解函数计算的过程,我们很快就找到了原因:是 (mylength mylength) 这个表达式将我们带入了死循环。但为什么 (mylength mylength) 在前面的代码中没有进入死循环,而当我们将它提取出来之后就进入死循环了呢?我们来好好看一看这个表达式的计算过程吧。

第 2 次转换之后,mylength 这个参数获取的代码内容变成了下面这样:

;;; mylength ;;;

(lambda (mylength)
  (
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (lambda (g)                          ;;
    (lambda (l)                         ;;
      (cond ((null? l) 0)               ;;
            (else (+ 1 (g (cdr l))))))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    (mylength mylength)
  )
)

所以 (mylength mylength) 就变成:

(
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(lambda (mylength)                      ;;
  ((lambda (g)                          ;;
    (lambda (l)                         ;;
      (cond ((null? l) 0)               ;;
            (else (+ 1 (g (cdr l))))))) ;;
    (mylength mylength)))               ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(lambda (mylength)                      ;;
  ((lambda (g)                          ;;
    (lambda (l)                         ;;
      (cond ((null? l) 0)               ;;
            (else (+ 1 (g (cdr l))))))) ;;
    (mylength mylength)))               ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

然后变成:

(
(lambda (g)                         
  (lambda (l)                        
    (cond ((null? l) 0)              
          (else (+ 1 (g (cdr l)))))))

    (
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (mylength)                      ;;
        ((lambda (g)                          ;;
          (lambda (l)                         ;;
            (cond ((null? l) 0)               ;;
                  (else (+ 1 (g (cdr l))))))) ;;
          (mylength mylength)))               ;;
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (mylength)                      ;;
        ((lambda (g)                          ;;
          (lambda (l)                         ;;
            (cond ((null? l) 0)               ;;
                  (else (+ 1 (g (cdr l))))))) ;;
          (mylength mylength)))               ;;
      ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
    )

)

展开到这一步我们发现了,由于计算机会优先对表达式求值,而 (mylength mylength) 这个表达式被提取到外部之后,每一次计算机对它求值,都会生成一个仍然处于函数体外部的表达式 (mylength mylength) 需要计算机求值。于是于是计算机又会对 (mylength mylength) 再次进行求值,结果就是出现了不断扩展的,越来越长的表达式。

而对于把 (mylength mylength) 提取出来之前的代码,(mylength mylength) 这个表达式被求值之后生成的是一个函数,没有出现暴露在函数体外部等待求值的表达式。它同样会产生表达式 (mylength mylength) ,只不过此时的 (mylength mylength) 被包裹在了所生成的函数里。更准确地说,是被包裹在了函数体中的一个条件分支里。只有计算时进入了该条分支,才会触发下一次对表达式 (mylength mylength) 的求值。

于是,「第 2 次转换」的前后所发生的关键性变化是 (mylength mylength) 表达式的求值步骤由「原来的 cond 条件分支内部」被提取到了「函数外部」。因此导致:

  • 求值的时间点被提前了;
  • 求值之后会生成新的,需要继续提前求值的,同样的表达式 (mylength mylength)
  • 递归的过程 (mylength mylength) 本来位于条件分支中,于是边界条件(Base Case)所提供的终止功能就会发挥作用:每次先要判断是否到达边界条件终止程序,然后才会进入含有递归的过程 (mylength mylength) 的分支中。这样避免进入死循环。
  • (mylength mylength) 这一递归过程被提出分支之后,程序运行流就再也触碰不到边界终止条件。没有了终止条件,就会导致死循环。

继续推导 Y 算子

上一节我们发现了问题所在,就是表达式 (mylength mylength) 被提取出来之后会导致计算机要先对它求值之后才能进行之后的步骤。而它又会在被求值后中生成新的「自己」,并且这个「自己」也需要同样被求值之后计算机才能进行之后的计算步骤。我们希望它像被提取出来前一样,「对其求值」的这一步骤能再次被放进函数的分支内。

第 3 次转换:将表达式 (mylength mylength) 打包进一个函数来延缓对它求值的时间。这种转换被称为 Eta-Expansion ( Eta-Conversion 的反向操作)。

(
  (lambda (f) (f f))

  (lambda (mylength)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (g)                          ;;
      (lambda (l)                         ;;
        (cond ((null? l) 0)               ;;
              (else (+ 1 (g (cdr l))))))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (x) ((mylength mylength) x))
    )
  )
)

我们将上面转换完成的代码再次输入计算机进行测试:

(
  ((lambda (f) (f f))

   (lambda (mylength)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (g)                          ;;
      (lambda (l)                         ;;
        (cond ((null? l) 0)               ;;
              (else (+ 1 (g (cdr l))))))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (x) ((mylength mylength) x))
    )
   )
  )

'(9 19 29) )   ;; 输出 3

成功了。我们可以接着转换了(每一步转换都要保证代码能正确运行才能进行下一步)。

第 4 次转换:更改变量名,让内部被注释框选的函数更像 define 阶段的函数(Modulo Alpha-Equivalence)

(
  (lambda (f) (f f))

  (lambda (g)
    (
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
     (lambda (mylength)                          ;;
      (lambda (l)                                ;;
        (cond ((null? l) 0)                      ;;
              (else (+ 1 (mylength (cdr l))))))) ;;
    ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
      (lambda (x) ((g g) x))
    )
  )
)

经过第 4 次转换(已经输入计算机测试了代码),我们得到了和 define 阶段几乎一样的函数。除了 define 的位置使用了 lambda 之外,其他部分几乎一样了。

;;; 使用 define 的时候 ;;;
(define mylength
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 (mylength (cdr l)))))))

;;; 没有 define 的时候 ;;;
(lambda (mylength)
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 (mylength (cdr l)))))))

第 5 次转换:把和使用 define 阶段的代码很像的部分提取出来

(
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  (lambda (y)                                  ;;
    (                                          ;;
      (lambda (f) (f f))                       ;;
                                               ;;
      (lambda (g)                              ;;
        ( y                                    ;;  Y 算子
          (lambda (x) ((g g) x))               ;;
        )                                      ;;
      )                                        ;;
    )                                          ;;
  )                                            ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
   (lambda (mylength)                          ;;
    (lambda (l)                                ;;
      (cond ((null? l) 0)                      ;;  目标函数
            (else (+ 1 (mylength (cdr l))))))) ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
)

第 5 次转换后(已经输入计算机测试了代码),我们最终获得 Y 算子,整理后如下:

;;; Y 算子 ;;;
(lambda (g)
  ((lambda (f) (f f))
    (lambda (f)
      (g (lambda (x) ((f f) x))))))

使用 Y 算子

Y 算子的使用非常简单,只需要在目标函数外再嵌套一层函数,把这层额外的函数所带来的参数名作为递归函数名就行。

比如有 define 的时候函数的样子:

(define mylength
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 (mylength (cdr l)))))))

这时候我们把 define 改成 lambda(这样就去掉了 define)变成:

(lambda (mylength)
  (lambda (l)
    (cond ((null? l) 0)
          (else (+ 1 (mylength (cdr l)))))))

然后再用 Y 算子作用于这个 lambda 匿名函数就可以得到相应的递归函数 F 了:

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

(define F
  (Y (lambda (mylength)
       (lambda (l)
         (cond ((null? l) 0)
               (else (+ 1 (mylength (cdr l)))))))))

(F '(9 19 29))  ;; 输出 3 (链表有 3 个有效负载:9, 19, 29)

打赏