1

我目前正在阅读Mike Vanier关于 Y-combinator 的这篇文章。 在 Y-combinator 推导的过程中，这段代码：

(define (part-factorial self)
  (lambda (n)
    (if (= n 0)

      1
      (* n ((self self) (- n 1))))))

((part-factorial part-factorial) 5) ==> 120
(define factorial (part-factorial part-factorial))
(factorial 5) ==> 120

被制定为：

(define (part-factorial self)
  (let ((f (self self)))
    (lambda (n)
      (if (= n 0)
        1
        (* n (f (- n 1)))))))

(define factorial (part-factorial part-factorial))
(factorial 5) ==> 120

在那之后，文章指出：

这在惰性语言中可以正常工作。在严格的语言中，(self self)let 语句中的调用会将我们送入无限循环，因为为了计算(part-factorial part-factorial)（在阶乘的定义中），您首先必须计算（部分阶乘部分阶乘）（在let表达式中） .

然后读者受到挑战：

为了好玩：弄清楚为什么这不是以前的定义的问题。

在我看来，我已经弄清楚了原因，但我想确认一下：

  1. 我的理解是正确的。
  2. 据我了解，我不会错过任何关键点。

我的理解是：在第一个代码片段中，(self self)调用不会导致无限循环，因为它被包含（包装）lambda为一个part-factorial函数，因此被评估为lambda (n)直到实际进行调用(self self)，这仅发生在n > 0. 因此，在(= n 0)评估为之后#t，无需调用(self self)。

4

2 回答 2

3

是的，这是正确的答案。事实上，在为应用顺序语言定义 Y 时，这个技巧（包装一些本来会在 lambda 中递归的东西）是至关重要的，我认为他的文章谈到了这一点（顺便说一句，这是一篇好文章）。

于 2018-03-21T11:38:26.537 回答
3

是的，第二个定义中的“let-over-lambda”

(define (part-factorial self)
  (let ((f (self self)))        ; let above the
    (lambda (n)                    ; lambda
      (if (= n 0)
        1
        (* n (f (- n 1)))))))

导致应用程序在返回(self self)之前被触发(lambda (n) ...)。

这提出了另一种避免循环的方法：将有问题的自我应用程序本身放在它自己的 lambda后面：

(define (part-factorial self)
  (let ((f (lambda (a) ((self self) a))))
    (lambda (n)
      (if (= n 0)
        1
        (* n (f (- n 1)))))))

现在这也有效。它被称为“eta-expansion”（或“eta-conversion”，因为它的对偶是“eta-contraction”）。

这种方式是通常的“应用顺序 Y 组合器”定义中实际使用的方式。

在第一个定义中，(self self)应用程序仅在实际需要其结果时才被触发——但代价是我们不得不以某种“不自然”的风格编写它，这在任何情况下都与我们想要编写的不同，即只是 f用来指代以某种方式在幕后为我们递归的函数。

有了明确的自我应用，负担就落在了我们身上，而且众所周知，我们人类会犯错。毕竟，犯错是人的事，就像宽恕一样——神圣的；但是我们的计算机还没有处于完全宽容的阶段。

所以，这就是 Y 的原因。让我们直接写出来，不用担心，把细节分解出来，安全地抽象出来。

而显式自申请的负担就不再赘述。

于 2018-03-24T20:29:55.250 回答