提问人：nmukh 提问时间：6/20/2023 更新时间：6/30/2023 访问量：143
什么是 （Y Y），即应用于自身的 Y 组合器？
What is (Y Y), the Y-combinator applied to itself?
问：
在《小阴谋家》的第 9 章中，作者介绍了 Y 组合器，倒数第二个问题问道：“什么是”。他们回答说：“谁知道呢，但它非常努力。(Y Y)
我试着对此进行推理，但很难过。我认为这只会导致无限循环，但也许我错过了一些东西。高阶定点运算器是否有趣？
本书将 Y 组合器定义为：
(define Y
(lambda(le)
((lambda(f) (f f))
(lambda(f)
(le (lambda(x) ((f f) x)))))))
但是，对我来说，使用 let-binding 更清晰：
(define Y (lambda(exp)
(let ([a (lambda(f)
(exp (lambda(x) ( (f f) x))))])
(a a))))
并且模拟长度函数工作正常。
((Y (lambda(s)
(lambda(lat)
(cond
((null? lat) 0)
(else (add1 (s (cdr lat)))))))) '(1 2 4))
=> 3
当我尝试在Dr Racket IDE中进行评估时，程序崩溃并耗尽内存。
我如何使用上面的 let 绑定来逐步完成并推理我在哪里定义 Y？(Y Y)(Y Y)
答：
3赞
sparusaurata
6/20/2023
#1
也许用 λ 微积分写它会有所帮助：Y = λf。（λx.f（xx））（λx.f（xx））。它具有以下β减少（又名执行）：
Y f → f（Y f） → f（f（Y f）） → ...
因此，YY → Y（YY） → （YY）（Y（YY）），您可以继续减少，使术语的大小以及参数的数量爆炸。基本上，你递归地将期望一个函数的东西应用到自己身上，并以递归方式应用它......
1赞
Will Ness
6/28/2023
#2
当将组合器符号放入混音中时，这更容易遵循。用
U x = x x ; U = ^x. x x
你
(define Y
(lambda (le)
((lambda(f) (f f))
(lambda(f)
(le (lambda(x) ((f f) x)))))))
成为
Y g = U (^f. g (^x. (f f) x))
如果我们定义
H g f = g (^x. (f f) x) = g (U f) = B g U f ; H = CBU
然后我们可以把它写成
Y g = U (H g) ; Y = BUH = BU(CBU)
= H g (H g) ; Y = SHH
= g (^x. ((H g) (H g)) x)
= g (^x. (Y g) x)
Y Y = Y (^x. (Y Y) x)
= (^x. (Y Y) x) (^x. (Y (^x. (Y Y) x)) x)
= (Y Y) (^x. (Y (^x. (Y Y) x)) x)
= (^x. (Y Y) x) (^x. (Y (^x. (Y Y) x)) x) (^x. (Y (^x. (Y Y) x)) x)
= ...
所以，为我们写作，我们看到它是Q(^x. (Y (^x. (Y Y) x)) x)
Y Y = Y Y Q
= Y Y Q Q
= Y Y Q Q Q
= Y Y Q Q Q Q
= ...
并且还原序列永远不会停止。
评论
let(Y Y)