Y组合子

Table of Contents

在这篇文章里，我会尝试推导出Y组合子，这是函数递归理论最重要的成果之一

Y组合子

在某些情况下可以不用给函数取名字，下面代码就是用匿名函数实现了“6加1”： 

((lambda (x)
   (+ x 1))
 6) ;; => 7

可不可以用匿名函数来表达递归过程呢？比如： 

(define fact
  (lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

在最后一行的使用了 fact 这个函数名字来产生递归调用，看起来好像无法用匿名函数来实现递归。实际上这个观点是错误的，后面一步一步地改造fact函数，来推导出整个过程

把fact作为参数传递

(define op-maker
  (lambda (op)
    (lambda (x)
      (op x))))

使用类似上面的模板代码把最后一行的 fact 作为参数传递进去： 

  (define fact-maker
    (lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* (procedure (- n 1)) n)))))  

;;  fact-maker ; =>  #<procedure:fact-maker>

;; ((fact-maker fact-maker) 5)  
; *: contract violation
;   expected: number?
;   given: #<procedure>
;   argument position: 1st

上面代码不工作，因为 fact-maker 返回值是一个 匿名函数 ，而 (* (fact-maker (- n 1)) n) 要求 (fact-maker (- n 1)) 是一个数字

用下面的代码来修复这个问题： 

(define fact-maker
    (lambda (procedure)
      (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1)))))))

((fact-maker fact-maker) 5) ; => 120

至今为止，我们成功地把函数名从过程体里面去掉了，但是我们在调用的时候还是要把函数名 fact-maker 传入

去除函数名

((fact-maker fact-maker) 5) 等价于 (fact 5), 因此可以重新定义fact函数为： 

(define fact 
  ((lambda (procedure)
     (lambda (n)
       (if (zero? n)
           1
           (* n ((procedure procedure) (- n 1)))))) ; fact-maker
   (lambda (procedure)
     (lambda (n)
       (if (zero? n)
           1
           (* n ((procedure procedure) (- n 1)))))) ; fact-maker
   ))

(fact 5) ; => 120

实际上可以完全不定义fact的名字，直接调用： 

(
 ((lambda (procedure)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((procedure procedure) (- n 1)))))) ; fact-maker
 (lambda (procedure)
   (lambda (n)
     (if (zero? n)
         1
         (* n ((procedure procedure) (- n 1)))))) ; fact-maker
) 5) ; => 120

这一大堆东西已经可以实现不定义函数名来完成递归调用了。接下来要把和fact函数相关的逻辑抽象出来，推广到通用过程中

分离业务逻辑

首先，把计算阶乘的逻辑分离出来作为一个参数，这样一来其他的计算逻辑，可以作为通过这个参数传递进去 

(define F
  (lambda (n)
       (if (zero? n)
           1
           (* n ((procedure procedure) (- n 1))))))

这并不难完全满足需求，还需要继续变换。我们知道 (h arg) 等价于 ( (lambda (x) (h x)) arg)，由此可以把 ((procedure procedure) (- n 1)) 替换成： 

((lambda (arg) ((procedure procedure) arg)) (- n 1))

把这个替换带 F 函数中： 

(define F
  (lambda (n)
    (if (zero? n)
        1
        (* n ((lambda (arg) ((procedure procedure) arg)) (- n 1))))))

接着把 ((lambda (arg) ((procedure procedure) arg)) (- n 1)) 抽象成一个参数： 

(define F
  ((lambda (func-arg)
     (lambda (n)
       (if (zero? n)
           1
           (* n (func-arg (- n 1))))))
   (lambda (arg) ((procedure procedure) arg))))

开始F的定义是： 

(define F (lambda (n) ... < procedure >))

现在F的定义是： 

(define F ((lambda (func-arg) (lambda (n) ...)) < procedure >))

而<procedure>的定义是： 

(lambda (arg) ((procedure procedure ) ...) ...)

代入步骤2的结果

现在把刚才的结果代入到步骤2的结果中： 

(define fact
  ((lambda (procedure)
     ((lambda (func-arg)
       (lambda (n)
          (if (zero? n)
              1
              (* n (func-arg (- n 1))))))
      (lambda (arg) ((procedure procedure) arg))))
   (lambda (procedure)
     ((lambda (func-arg)
       (lambda (n)
          (if (zero? n)
              1
              (* n (func-arg (- n 1))))))
      (lambda (arg) ((procedure procedure) arg))))))

(fact 5) ; => 120

注意 ((lambda (func-arg)… 之前的两个括号： 

......
((lambda (func-arg) < body-using-func-arg >) (lambda (arg) ...))

计算结果和下面是一样的： 

((lambda (arg) ((procedure procedure) arg)) (- n 1))

两者的区别是： 第一种形式参数是一个函数，而第二种形式的参数一个数字

替换fact逻辑

仔细研究下面的代码： 

(lambda (func-arg)
  (lambda (n)
    (if (zero? n)
        1
        (* n (func-arg (- n 1))))))

(lambda (func-arg) …) 这段代码包含了计算阶乘的所有逻辑，如果把它定义成 _F*_： 

(define F*
  (lambda (func-arg)
         (lambda (n)
            (if (zero? n)
                1
                (* n (func-arg (- n 1)))))))

(define fact
    ((lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))))

我们可以用 任何的其他业务逻辑 作为 F* 来替换 计算阶乘的特定逻辑 。唯一留下的问题在于：还需要在外面定义F*

把F*作为参数传入

把 fact 重新命名为 Y , F* 作为 Y 的参数 F 传入： 

(define Y
  (lambda (F) 
    ((lambda (procedure)
       (F (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       (F (lambda (arg) ((procedure procedure) arg)))))))

((Y F*) 5) ; => 120
((F* (Y F*)) 5) ; => 120

抽取重复的lambda定义

实际上(lambda (procedure) (X (lambda (arg) ((procedure procedure) arg))))被重复创建了两次，可以用 let 来简化： 

(define Y
  (lambda (F) 
    (let ((W (lambda (procedure)
               (F (lambda (arg) ((procedure procedure) arg))))))
      (W W))))

((Y F*) 5) ; =>120
((F* (Y F*)) 5) ; =>120

这就是Y组合子的定义。如果利用 define 的语法糖，可以写得更简洁： 

(define (Y F)
  (define (W P)
    (F (lambda (x) ((P P) x))))
  (W W))

意义

Y组合子也被称为 不动点的高阶函数 ， 可以很容易地证明： 

Y(F) = F ; F是一个函数

它的意义在于：

  1. 实现匿名函数的递归
  2. 递归可以不依赖栈