对比scheme中的Y-bang和Y

写在前面

《the seasoned schemer》chapter16 中提到了Y-bang,后面给到一个biz函数,来比较两者的不同,但是作者赶着去吃炒蛋和煎饼,没有明确指出不同之处在哪里😆。

用作者的话来说,既然都能推导出Y combinator,自然也就能理解 Y 和 Y-bang 的不同​​。

After you have worked through the definition of the Y combinator, nothing will ever affect your hat size again. not even an attempt to understand the difference between Y and Yi.

既是如此,自己便试着推导了下,算是初步理清了两者的不同。

开始之前,建议在桌前备上一瓶肥仔水,你会需要它的😆。

定义

先看两者的定义:

; define Y-bang
;
(define Y-bang
  (lambda (f)
    (letrec
      ((h (f (lambda (arg) (h arg)))))
      h)))
;

; Y combinator from chapter 09, old friend.
;
(define Y
  (lambda (le)
    ((lambda (f)
      (f f))
      (lambda (f)
        (le (lambda (x)
              ((f f) x)))))))
;

推导过程

Y-bang的推导较简单,可以参看《the seasoned schemer》chapter 16 ,这里不妨再过一遍:

故事依然从length开始:

; define length
;
(define length
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (length (cdr l)))))))
;

使用let 和 set! 来重新定义length:

; using let and set! to get another version of length
;
(define length
  (let ((h (lambda (l) 0)))
    (set! h
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (h (cdr l)))))))
    h))
;

这里我们来定义一个函数L,用来简化这个新版本length的定义:

; define L
;
(define L
  (lambda (length)
    (lambda (l)
      (cond
        ((null? l) 0)
        (else (add1 (length (cdr l))))))))
;

这个 L 函数,接受一个函数length做为参数,返回结果是一个lambda函数。

利用 L,来简化 length:

(define length
  (let ((h (lambda (l) 0)))
    (set! h
      (L (lambda (arg) (h arg))))
    h))

如果你看懂了这步,可跳过下面的推导细节。


为什么可以这样简化? 我们将 L 换成 定义的lambda函数:

; replace L with its definition

((lambda (length)
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (length (cdr l))))))) (lambda (arg) (h arg)))
;
; replace length with (lambda (arg) (h arg)), we can get those below:

(lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 ((lambda (arg) (h arg)) (cdr l))))))
;

; the result of ((lambda (arg) (h arg)) (cdr l)) is (h (cdr l))
;
(lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (h (cdr l))))))

最后得到的(L (lambda (arg) (h arg))) 的结果就是:

(lambda (l)
  (cond
   ((null? l) 0)
   (else (add1 (h (cdr l))))))

这时,替换(L (lambda (arg) (h arg))) ,得到的length如下:

(define length
  (let ((h (lambda (l) 0)))
    (set! h
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (h (cdr l)))))))
    h))
;

利用新定义的length,可以推导出Y-bang.

; we get Y-bang
;
(define Y-bang
  (lambda (f)
    (letrec
      ((h (f (lambda (arg) (h arg)))))
      h)))
;

Y 稍微复杂了些 ,如果你看《the little schemer》chapter 09 时仍是懵逼状,可参考之前这篇scheme中有关Y combinator 的推导

两者对比

当调用的函数符合一定的”模式”时,两者没什么大的区别。

看一个depth* 的例子:

; define D
;
(define D
  (lambda (depth*)
    (lambda (s)
      (cond
        ((null? s) 1)
        ((atom? (car s)) (depth* (cdr s)))
        (else
          (max
            (add1 (depth* (car s)))
            (depth* (cdr s))))))))
;

使用Y-bang 和 Y 来定义 depth*:

(define depth* (Y-bang D))

(depth* (quote (c (b (a b) a) a)))
;Value: 3

(define depth* (Y D))

(depth* (quote (c (b (a b) a) a)))
;Value: 3

使用(Y-bang D)(Y D) 来定义 depth*,得到的结果相同。

来看个不一样的例子:

; define biz
;
(define biz
  (let ((x 0))
    (lambda (f)
      (set! x (add1 x))
      (lambda (a)
        (if (= a x)
            0
            (f a))))))

调用biz:

((Y biz) 5)
; Value: 0

((Y-bang biz) 5)
; no answer

此时((Y-bang biz) 5)没有结果,因为调用((Y-bang biz) 5)时,只执行了一次(set! x (add1 x)) ,x 一直是1,进入了一个无限的死循环。

为什么会是这样的?

来看一下(Y-bang biz) 是什么:

; define Y-bang
;
(define Y-bang
  (lambda (f)
    (letrec
      ((h (f (lambda (arg) (h arg)))))
      h)))
; define biz
;
(define biz
  (let ((x 0))
    (lambda (f)
      (set! x (add1 x))
      (lambda (a)
        (if (= a x)
            0
            (f a))))))
;
; now, we want know what (Y-bang biz) is.
;
; first, replace Y-bang, biz with their definition.
;
((lambda (f)
    (letrec
      ((h (f (lambda (arg) (h arg)))))
      h)) (let ((x 0))
        (lambda (f)
          (set! x (add1 x))
          (lambda (a)
            (if (= a x)
                0
                (f a))))))
;
; then, replace f with biz's definition

(letrec
  ((h ((let ((x 0))
          (lambda (f)
            (set! x (add1 x))
            (lambda (a)
              (if (= a x)
                  0
                  (f a))))) (lambda (arg) (h arg)))))
  h)
;
; and, replace f in biz with (lambda (arg) (h arg))

(letrec
  ((h ((let ((x 0))
          (lambda (f)
            (set! x (add1 x))
            (lambda (a)
              (if (= a x)
                  0
                  ((lambda (arg) (h arg)) a))))))))
  h)
;
; the result of ((lambda (arg) (h arg)) a) is (h a)
; finally, we get it.
(letrec
  ((h ((let ((x 0))
         (set! x (add1 x))
         (lambda (a)
           (if (= a x)
               0
               (h a)))))))
  h)

最后得到的结果中,可以看出,第一次调用递归函数 h 时,x 初始化为零,然后执行 add1, x 为1,此后递归时,不再执行 (lambda (a) ....) 外的表达式,x的值一直没变化,保持为1,((Y-bang biz) 5) 自然是无结果的。

我们可以测试一下,既然 x 的值一直是1,那么((Y-bang biz) 1) 应该有结果, 且为0:

((Y-bang biz) 1)
; Value: 0

我们可以修改一下biz函数,让((Y-bang biz) 5) 得到结果0。

; redefine biz
;
(define biz
  (lambda (f)
    (let ((x 0))
      (lambda (a)
        (set! x (add1 x))
        (if (= a x)
            0
            (f a))))))
;
((Y-bang biz) 5)
; Value: 0

至此,(Y-bang biz) 部分结束。

惭愧的是,一直无法推导出(Y biz) 的最终样子,将biz 的定义带入Y 中时,卡在(f f)这里,简直就是一个无限死循环。

算是一个未填的坑,留待猴年马月再填。

初步猜测(Y biz)最终的结果类似这样:

(lambda (a)
  (let ((x 0))
    (letrec
      ((h
        (lambda (a)
          (set! x (add1 x))
          (if (= a x)
              0
              (h a)))))
      (h a))))

另,这里不推荐使用pp 来输出(Y biz)(Y-bang biz)的结果,因为输出的结果中,两者相同:

(pp (Y biz))

; result
;
(lambda (a)
  (if (= a x)
      0
      (f a)))

(pp (Y-bang biz))

;result
;
(lambda (a)
  (if (= a x)
      0
      (f a)))

可以看到,输出的结果中已经弃掉了(set! x (add1 x)), 使得两者看着好像是一样的,但其实并不相同,这样的结果容易误人子弟啊。

OK,Time for 🍰.

参考

《the seasoned schemer》