;; compute the max of a list of integers
(define Y
(lambda (w)
((lambda (f)
(f f))
(lambda (f)
(w (lambda (x)
((f f) x)))))))
((Y
(lambda (max)
(lambda (l)
(cond ((null? l) -1)
((> (car l) (max (cdr l))) (car l))
(else (max (cdr l)))))))
'(1 2 3 4 5))
我想了解这个结构。有人可以对此代码给出清晰简单的解释吗？
例如，假设我忘记了 Y 的公式。我怎么能记住它，并在我使用它很久之后重现它？
到目前为止，我发现的最好的解释是在“The Little Schemer”一书的第 9 章。整章逐步解释了 Y-Combinator 的工作原理，以及如何从任意递归过程中推导出组合子.
这是一些相关的答案（由我）：
基本上，将Y定义为λr.(λh.h h) (λg.r (λx.(g g) x))，应用程序Y r减少为
Y r
(λw.(λh.h h) (λg.w (λx.(g g) x))) r
(λh.h h) (λg.r (λx.(g g) x))
h h
;where
h = (λg.r (λx.(g g) x)) <----\
|
(λg.r (λx.(g g) x)) h |
r (λx.(g g) x) <-------------- | ----------\
;where | |
g = h -----/ |
;so that |
(g g) = (h h) = r (λx.(g g) x) ------/
所以r必须期待两个参数 - 第一个表示要调用的递归函数，第二个 - 一个实际参数：
r = λf (λx. ....x.....(f y)...... )
所以(Y r) x 减少为
(r (λx.(g g) x)) x
(r f) x
;where
f = (λx.(g g) x)
f y = (λx.(g g) x) y = (g g) y = (r f) y ; f is "fixed point" of r
定义的f = (λx.(g g) x)意思是，当f y被调用时，(g g) y将被调用，此时 g将被自我应用，r从内部“拉”，并且是带参数调用g的结果。即，由应用程序产生的 lambda 表达式主体中的任何调用都被转换回即使用新参数调用同一主体。(r f)y(f y)(r f)(r f) yy
重要的实现细节是它是相同的函数体还是它的副本，但语义是相同的——我们可以使用新的参数值输入相同的函数体。
Y组合器的本质是引用复制和自我应用：我们通过同名引用同一事物，两次；因此我们安排它接受自己作为论据。
当没有引用时，如在纯 lambda 演算中，并且参数接收参数的文本副本 - 即通过文本重写完成缩减 - 这仍然有效，因为相同的副本被复制并传递，作为参数提供给 self 所以它是可用的如果需要，在下一次迭代中。
但是当共享引用可用时效率更高（所有相同名称的使用都引用相同的东西）。在环境模型下创建自引用函数的评价很简单：
(let ((fact #f))
(set! fact
(lambda (n) (if (< 2 n) 1
(* n (fact (- n 1))))))
fact)
实际上，您的答案中的定义是应用顺序 Y 组合器的定义。使用正常顺序，可以应用 eta-reduction 而不会导致无限循环，以获得Ynorm = (λw.(λh.h h) (λg.w (g g)))规范地写为
Ynorm = (λf.(λx.f (x x)) (λx.f (x x)))
确实
Ynorm g
= (λx.g (x x)) (λx.g (x x))
= g ((λx.g (x x)) (λx.g (x x)))