lisp - lisp中的定点组合器

Question

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

Answer 1

这里有一些相关的回答(由我):

• Y combinator discussion in "The Little Schemer"
• Unable to get implementation of Y combinator working
• In Scheme, how do you use lambda to create a recursive function?

基本上，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 内部“拉”出来，结果是(r f) 使用 y 参数调用。 IE。 (r f) 应用程序产生的 lambda 表达式主体中的任何调用 (f y) 都被转换回 (r f) y 即调用具有新参数 y 的同一主体。

重要的实现细节是它是相同的函数体，还是它的副本，但语义是相同的——我们能够进入相同的函数体具有新的参数值。

Y 组合器的本质是通过引用和自应用进行复制:我们通过相同的名称 引用同一事物两次；因此我们安排它接收它自己作为参数。

当没有引用时，如在纯 lambda 演算中，参数接收参数的文本副本 - 即通过文本重写完成归约 - 这仍然有效，因为 相同的副本 被复制并传递，作为参数提供给 self 以便在下一次迭代中可用，如果需要的话。

但是当共享引用可用时效率要高得多(所有使用相同名称 指的是相同的东西)。环境下自参照函数的评价模型创建很简单

(let ((fact #f)) 
  (set! fact 
        (lambda (n) (if (< 2 n) 1 
                               (* n (fact (- n 1)))))) 
  fact)

---

事实上，您的答案中的定义是应用顺序 Y 组合子的定义。使用正常顺序，可以应用 eta 缩减而不会导致无限循环，得到 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)))