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

这是我的一些相关答案：

\n\n

\n
• 《小阴谋家》中的 Y 组合器讨论
\n
• 无法实现 Y 组合器的工作
\n
• 在Scheme中，如何使用lambda创建递归函数？
\n

\n\n

基本上，当Y定义为 时\xce\xbbr.(\xce\xbbh.h h) (\xce\xbbg.r (\xce\xbbx.(g g) x))，应用程序Y r减少为

\n\n

Y r\n(\xce\xbbw.(\xce\xbbh.h h) (\xce\xbbg.w (\xce\xbbx.(g g) x))) r\n(\xce\xbbh.h h) (\xce\xbbg.r (\xce\xbbx.(g g) x))\nh h\n    ;where\n        h = (\xce\xbbg.r (\xce\xbbx.(g g) x))       <----\\\n                                           |\n(\xce\xbbg.r (\xce\xbbx.(g g) x)) h                      |\nr (\xce\xbbx.(g g) x)             <-------------- | ----------\\\n    ;where                                 |           |\n        g = h                         -----/           |\n        ;so that                                       |\n        (g g) = (h h) = r (\xce\xbbx.(g g) x)           ------/\n

\n\n

因此r必须期待两个参数 - 第一个代表要调用的递归函数，第二个 - 实际参数：

\n\n

        r = \xce\xbbf (\xce\xbbx. ....x.....(f y)...... )\n

\n\n

这样就(Y r) x 减少了

\n\n

(r (\xce\xbbx.(g g) x)) x\n(r f) x\n    ;where\n        f   = (\xce\xbbx.(g g) x) \n        f y = (\xce\xbbx.(g g) x) y = (g g) y = (r f) y  ; f is "fixed point" of r\n

\n\n

定义f = (\xce\xbbx.(g g) x)意味着，当f y被调用时，(g g) y将被调用，此时 g将被自我应用，r从内部“拉出”并使用参数调用g的结果。即，由应用程序产生的 lambda 表达式主体中的任何调用都会被转换回即使用新参数调用同一主体。(r f)y(f y)(r f)(r f) yy

\n\n

重要的实现细节是它是否是相同的函数体或其副本，但语义是相同的 - 我们能够使用新的参数值输入相同的函数体。

\n\n

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

\n\n

当没有引用时，就像在纯 lambda 演算中一样，并且参数接收参数的文本副本（即通过文本重写完成减少），这仍然有效，因为相同的副本会被复制并传递，作为参数传递给 self，因此如果需要的话，它可以在下一次迭代中使用。

\n\n

但是当共享引用可用时（所有使用相同名称的都引用相同的事物），它的效率要高得多。在评价环境模型下创建自参照函数很简单：

\n\n

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

\n\n\n\n

事实上，您答案中的定义是应用阶 Y 组合器的定义。对于正常顺序，可以应用 eta 归约而不会导致无限循环，以获得Ynorm = (\xce\xbbw.(\xce\xbbh.h h) (\xce\xbbg.w (g g)))规范地写为

\n\n

Ynorm = (\xce\xbbf.(\xce\xbbx.f (x x)) (\xce\xbbx.f (x x)))\n

\n\n

的确

\n\n

Ynorm g\n= (\xce\xbbx.g (x x)) (\xce\xbbx.g (x x))\n= g ((\xce\xbbx.g (x x)) (\xce\xbbx.g (x x)))\n

\n