试着找出 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 🍰.