(self self) 在 let 语句中调用，用严格的语言

Question

我目前正在经历 this article on Y-combinator by Mike Vanier。
顺着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

之后，文章指出：

This will work fine in a lazy language. In a strict language, the (self self) call in the let statement will send us into an infinite loop, because in order to calculate (part-factorial part-factorial) (in the definition of factorial) you will first have to calculate (part-factorial part-factorial) (in the let expression).

然后reader受到挑战：

For fun: figure out why this wasn't a problem with the previous definition.

在我看来我已经找到原因了，尽管我想确认一下：

我的理解是正确的。
在我的理解中，我没有遗漏任何关键点。

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

Answer 1

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

Answer 2

是的，第二个定义中的"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) ...) 之前被触发。

这提出了另一种避免循环的方法：将有问题的 self-application 本身放在 它自己的 后面 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"）。

这种方式是通常"applicative-order Y-combinator"定义中实际使用的方式。

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

有了明确的 self-application 负担就落在了我们身上，众所周知我们人类会犯错。毕竟，犯错是人之常情，宽恕是神圣的；但是我们的计算机还没有all-forgiving阶段。

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

显式self-application的负担不再赘述

(self self) 在 let 语句中调用，用严格的语言

(self self) call inside the let statement, in strict language

lambda

scheme

lisp

let

y-combinator