(self self)在let语句中使用严格的语言进行调用 [英] (self self) call inside the let statement, in strict language

问题描述

我目前正在通过迈克·范尼尔.
沿Y组合器推导的方式，此代码:

I am currently, going through this article on Y-combinator by Mike Vanier.
Along the way of Y-combinator derivation, this code:

(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

此后，文章指出:

这在懒惰的语言中可以很好地工作.用严格的语言来说，let语句中的(self self)调用将使我们陷入无限循环，因为要计算(part-factorial part-factorial)(在阶乘的定义中)，您首先必须计算(部分阶乘部分阶乘)(在let表达式中).

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).

然后挑战读者:

好玩:找出为什么以前的定义不是问题.

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

在我看来，我想出了原因，尽管我想确认一下:

It seems to me I've figured out why, though I would like to confirm that:

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

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

My understanding is: in the first code snippet (self self) call won't result into infinite loop, because it is contained (wrapped) into lambda as a part-factorial function, and thus evaluated to lambda (n) until the call to (self self) is actually made, which happens only for n > 0. Thus, after (= n 0) evaluates to #t, there is no need in calling (self self).

推荐答案

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

Yes, the "let-over-lambda" in the second definition

(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) ...)之前被触发.

causes the application (self self) to be triggered before the (lambda (n) ...) can be returned.

这建议了另一种避免循环的方法:将有问题的自我应用程序本身放在自己的 lambda中:

This suggests another way to avoid the looping: put the problematic self-application itself behind its own 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").

and now this works, too. It is known as "eta-expansion" (or "eta-conversion" in general, as its dual is "eta-contraction").

这种方法是通常在应用级Y组合器"定义中实际使用的方法.

This way is what's actually used in the usual "applicative-order Y-combinator" definition.

在第一个定义中，仅当实际需要其结果时才触发(self self)应用程序.但是这样做的代价是我们不得不以某种不自然"的风格来编写它，无论如何它都与我们想要编写的风格不同，即仅使用f来引用以某种方式制作的函数为我们在后台递归.

In the first definition the (self self) application is only triggered when its result is actually needed — but the cost to it is that we had to write it in a somewhat "unnatural" style, which is in any case different from what we'd like to write, i.e. just use f to refer to the function which is somehow made recursive for us behind the scenes.

有了明确的自我运用，负担就加在我们身上，众所周知我们的人类会犯错.毕竟，犯错是人类的原谅—神但是我们的计算机还没有完全容忍.

With the explicit self-application the burden is on us, and we humans are known to err. To err is human, after all, as to forgive — Divine; but our computers are not at that all-forgiving stage quite yet.

因此，这是Y的原因.为了让我们直接编写它，而无后顾之忧，将细节分解出来并安全地抽象出来.

So, this is the why of Y. To let us write it straight, without worries, with the details factored out and abstracted safely away.

并且不再提及显式自我应用的负担.

And the burden of explicit self-application shall be mentioned no more.

这篇关于(self self)在let语句中使用严格的语言进行调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！