Y-Combinator

https://eecs.ceas.uc.edu/~franco/C511/html/Scheme/ycomb.html

一些情况下不需要给过程命名.

((lambda (x) (+ x 1)) 6)

递归函数能不命名么? 以阶乘函数fact为例, 下面逐步移掉对fact对名字的使用.

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

第一步把名字当做参数传入.

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

用在阶乘这里, 即:

(define fact-maker
  (lambda (op)
    (lambda (x)
      (if (zero? x)
          1
          (* x (op (- x 1)))))))
> ((fact-maker fact-maker) 3)
*: contract violation
  expected: number?
  given: #<procedure:.../ycombinator.rkt:15:4>
  argument position: 2nd
  other arguments...:

不符合调用规则, 实际是不能工作的.

修改程序:

(define fact-maker
  (lambda (op)
    (lambda (x)
      (if (zero? x)
          1
          (* x ((op op) (- x 1)))))))
> ((fact-maker fact-maker) 3)
6

现在fact等价为(fact-maker fact-maker), 原地替换fact-maker则阶乘函数可以等价写为:

(define fact
  ((lambda (op)
     (lambda (x)
       (if (zero? x)
           1
           (* x ((op op) (- x 1))))))
   (lambda (op)
     (lambda (x)
       (if (zero? x)
           1
           (* x ((op op) (- x 1))))))))

这里实现了一个不需要名字的fact函数.

下面演示使用Y-combinator来泛化到所有递归函数上 .

先把计算阶乘的逻辑剥离出来.

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

我们知道:

(f arg) <=> ((lambda (x) (f x)) arg)

所以((op op) (- n 1))可以改写成:

((lambda arg) ((op op) arg) (- n 1))

替换F中的((op op) ...), 得到.

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

现在用改写过的F替换掉上面fact中的对应逻辑,

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

留意((lambda (func-arg) ...))这部分代码是阶乘函数的核心逻辑.将它提出来.

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

那么fact可以定义为:

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

现在业务逻辑和无命名递归的结构剥离了出来.

将fact的代码泛化. 得到Y组合子.

(define Y
  (lambda (X)
    ((lambda (op)
       (X (lambda (arg) ((op op) arg))))
     (lambda (op)
       (X (lambda (arg) ((op op) arg)))))))

fact函数用Y来表达出来, 即:

(define fact (Y F*))

我们使用Y组合子定义findmax函数.

(define M
  (lambda (func-arg)
    (lambda (xs)
      (if (null? xs)
          'none
          (if (null? (cdr xs))
              (car xs)
              (max (car xs) (func-arg (cdr xs))))))))
(define findmax (Y M))