4 
;; 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 的公式。我怎么能记住它，并在我使用它很久之后重现它？

4

2 回答 2

2

到目前为止，我发现的最好的解释是在“The Little Schemer”一书的第 9 章。整章逐步解释了 Y-Combinator 的工作原理，以及如何从任意递归过程中推导出组合子.

于 2012-10-28T23:21:04.360 回答
2

这是一些相关的答案（由我）：

基本上，将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)))
于 2012-10-29T10:25:10.743 回答