为什么 let 不允许相互递归定义，而 letrec 可以？

Question

我怀疑我从根本上误解了Scheme的求值规则。 let 和 letrec 的编码和计算方式是什么使得 letrec 能够接受相互递归定义而 let 不能？对他们的基本 lambda 表格提出上诉可能会有帮助。

Answer 1

让我们从大家最喜欢的相互递归示例的版本开始，even-or-odd。

(define (even-or-odd x)
  (letrec ((internal-even? (lambda (n)
                             (if (= n 0) 'even
                                 (internal-odd? (- n 1)))))
           (internal-odd? (lambda (n)
                            (if (= n 0) 'odd
                                (internal-even? (- n 1))))))
    (internal-even? x)))

如果你用 let 而不是 letrec 来写，你会得到一个 internal-even? in unbound 的错误。原因的描述性原因是 let 中定义初始值的表达式在绑定变量之前在词法环境中求值，而 letrec 首先创建具有这些变量的环境，只是为了让这个工作。

现在我们来看看如何使用 lambda 实现 let 和 letrec，以便您了解为什么会这样。

let 的实现相当简单。一般形式是这样的：

(let ((x value)) body)  -->  ((lambda (x) body) value)

所以 even-or-odd 用 let 写成：

(define (even-or-odd-let x)
  ((lambda (internal-even? internal-odd?)
     (internal-even? x))
   (lambda (n)
     (if (= n 0) 'even
         (internal-odd? (- n 1))))
   (lambda (n)
     (if (= n 0) 'odd
         (internal-even? (- n 1))))))

你能看到internal-even的尸体吗？和 internal-odd？在这些名称绑定的范围之外定义。出现错误。

为了在您希望递归工作时处理此问题，letrec 执行如下操作：

(letrec (x value) body)  -->  ((lambda (x) (set! x value) body) #f)

[注意：可能有更好的方法来实现 letrec 但这就是我想出的办法。无论如何，它会给你灵感。]

现在 even-or-odd? 变成：

(define (even-or-odd-letrec x)
  ((lambda (internal-even? internal-odd?)
     (set! internal-even? (lambda (n)
                (if (= n 0) 'even
                    (internal-odd? (- n 1)))))
     (set! internal-odd? (lambda (n)
               (if (= n 0) 'odd
                   (internal-even? (- n 1)))))
     (internal-even? x))
   #f #f))

现在 internal-even? 和 internal-odd? 被用于它们已被绑定并且一切正常的上下文中。

Answer 2

let 不能以任何明显的方式创建 mutually-recursive 函数，因为您总是可以将 let 变成 lambda:

(let ((x 1))
  ...)
-->
((λ (x)
   ...)
 1)

对于多个绑定也类似：

(let ((x 1)
      (y 2))
  ...)
-->
((λ (x y)
   ...)
 1 2)

在这里和下面，--> 表示 'can be translated into' 甚至 'could be macroexpanded into'。

好的，现在考虑 x 和 y 是函数的情况：

(let ((x (λ (...) ...))
      (y (λ (...) ...)))
  ...)
-->
((λ (x y)
   ...)
 (λ (...) ...)
 (λ (...) ...))

现在很清楚为什么这对递归函数不起作用：

(let ((x (λ (...) ... (y ...) ...))
      (y (λ (...) ... (x ...) ...)))
  ...)
-->
((λ (x y)
   ...)
 (λ (...) (y ...) ...)
 (λ (...) (x ...) ...))

好吧，让我们更具体地看看出了什么问题：让我们考虑一个单个递归函数：如果它有问题，那么肯定会有问题相互递归函数。

(let ((factorial (λ (n)
                   (if (= n 1) 1
                       (* n (factorial (- n 1)))))))
  (factorial 10))
-->
((λ (factorial)
   (factorial 10))
 (λ (n)
   (if (= n 1) 1
       (* n (factorial (- n 1))))))

好的，当您尝试评估表格时会发生什么？我们可以使用 SICP 中描述的环境模型。特别考虑在 e 环境中评估此表单，其中没有 factorial 的绑定。表格如下：

((λ (factorial)
   (factorial 10))
 (λ (n)
   (if (= n 1) 1
       (* n (factorial (- n 1))))))

好吧，这只是一个带有单个参数的函数应用程序，因此要对其进行评估，您只需按某种顺序评估函数形式及其参数即可。

从函数形式开始：

(λ (factorial)
  (factorial 10))

这只是计算一个函数，调用时将：

创建一个环境 e' 扩展 e 并绑定 factorial 到函数的参数；
使用参数 10 和 return 结果调用绑定到 factorial 的任何内容。

所以现在我们必须再次在环境 e:

中评估参数

(λ (n)
  (if (= n 1) 1
      (* n (factorial (- n 1)))))

这计算为一个参数的函数，调用时将：

建立一个环境 e'' 扩展 e 绑定 n 到函数的参数；
如果参数不是 1，将尝试调用一些绑定到名为 factorial 的变量的函数，在 e''[=185 中查找此绑定=].

稍等：什么功能？ e中没有绑定factorial，e''扩展了e（特别是，e'' 不扩展 e')，但通过添加 e' 的绑定=37=]，而不是 factorial。因此 factorial 在 e'' 中没有绑定。所以这个函数是一个错误：你要么在它被评估时得到一个错误，要么在它被调用时得到一个错误，这取决于实现的智能程度。

相反，您需要做这样的事情才能使这项工作：

(let ((factorial (λ (n) (error "bad doom")))) (set! factorial (λ (n) (if (= n 1) 1 (* n (factorial (- n 1)))))) (factorial 10)) --> ((λ (factorial) (set! factorial (λ (n) (if (= n 1) 1 (* n (factorial (- n 1)))))) (factorial 10)) (λ (n) (error "bad doom")))

现在可以使用了。同样，它是一个函数应用程序，但这次所有的操作都发生在函数中：

(λ (factorial) (set! factorial (λ (n) (if (= n 1) 1 (* n (factorial (- n 1)))))) (factorial 10))

因此，在 e 中对其求值会产生一个函数，该函数在调用时将：

创建一个环境 e'，扩展 e，其中有一个 factorial 的绑定到它的任何参数是；

改变factorial在e'中的绑定，给它赋不同的值；

在 e' 中调用 factorial 的值，使用参数 10，return 计算结果。

所以有趣的步骤是（2）：factorial的新值就是这种形式的值，在e':
中求值
(λ (n) (if (= n 1) 1 (* n (factorial (- n 1)))

好吧，这又是一个函数，调用时将：

创建一个环境，e''，扩展 e'（注意！），绑定 n ;

如果 n 的绑定值不是 1，则在 e'' 中调用任何绑定到 factorial 的值环境。

现在这将起作用，因为是 factorial 在 e'' 中的绑定，因为，现在, e'' extends e' 并且在 e'[=185= 中有一个 factorial 的绑定].而且，进一步，在函数被调用时，e' 将发生变化，因此绑定是正确的：它是函数本身。

这实际上是 more-or-less letrec 的定义方式。形式如

(letrec ((a <f1>) (b <f2>)) ...)

首先，变量 a 和 b 绑定到一些未定义的值（引用这些值是错误的）。 Then <f1> 和 <f2> 在生成的环境中按某种顺序进行评估（此评估不应引用 a 和 b 有那个点），并且这些评估的结果分别分配给 a 和 b，改变它们的绑定，最后 body 在生成的环境中进行评估。

例如参见 [=75=]（其他报告类似但更难参考，因为其中大部分是 PDF）：

The <variable>s are bound to fresh locations, the <init>s are evaluated in the resulting environment (in some unspecified order), each <variable> is assigned to the result of the corresponding <init>, the <body> is evaluated in the resulting environment, and the values of the last expression in <body> are returned. Each binding of a <variable> has the entire letrec expression as its region, making it possible to define mutually recursive procedures.

这显然类似于 define 必须做的事情，事实上我认为很明显，至少对于内部 define，你总是可以将 define 变成 letrec:

(define (outer a) (define (inner b) ...) ...) --> (define (outer a) (letrec ((inner (λ (b) ...))) ...))

也许这是一样的作为

(letrec ((outer (λ (a) (letrec ((inner (λ (b) ...))) ...)))))

但我不确定。

当然，letrec 不会给你带来计算能力（define 也不会）：你可以在没有它的情况下定义递归函数，只是不太方便：

(let ((facter (λ (c n) (if (= n 1) 1 (* n (c c (- n 1))))))) (let ((factorial (λ (n) (facter facter n)))) (factorial 10)))

或者，为了纯洁的心：

((λ (facter) ((λ (factorial) (factorial 10)) (λ (n) (facter facter n)))) (λ (c n) (if (= n 1) 1 (* n (c c (- n 1))))))

这非常接近 U 组合器，或者我一直认为它是。

最后，将 quick-and-dirty letrec 编写为宏相当容易。这是一个名为 labels 的（请参阅对此答案的评论）：

(define-syntax labels (syntax-rules () [(_ ((var init) ...) form ...) (let ((var (λ x (error "bad doom"))) ...) (set! var init) ... form ...)]))

这将适用于符合要求的用途，但它不能使引用变量的初始绑定是错误的：调用它们是错误的，但它们可能会泄漏。例如，Racket 做了一些魔法，使它成为一个错误。

Answer 3

下面是even?没有let或者letrec：

(define even? ( (lambda (e o) <------. ------------. (lambda (n) (e n e o)) -----* | ) | (lambda (n e o) <------. <---+ (if (= n 0) #t (o (- n 1) e o))) -----* | (lambda (n e o) <------. <---* (if (= n 0) #f (e (- n 1) e o))))) -----*

这里定义了名称even?来指代对(lambda (e o) (lambda (n) (e n e o)) )表达式求值返回的对象对另外两个lambda求值产生的两个对象的应用求值结果表达式，参数位置中的表达式。

每个参数 lambda 表达式的格式都很好，特别是没有对未定义名称的引用。每个只引用它的个参数。

下面同even?，为了方便写成let：

(define even?-let- (let ((e (lambda (n e o) <------. <---. (if (= n 0) #t (o (- n 1) e o)))) -----* | (o (lambda (n e o) <------. <---+ (if (= n 0) #f (e (- n 1) e o)))) -----* | ) | (lambda (n) (e n e o)) )) ----------------------------*

但是如果我们不将这些 e 和 o 值作为参数传递呢？

(define even?-let-wrong- ^ ^ (let ((e (lambda (n) <-----------------|--|-------. (if (= n 0) #t (o (- n 1))))) --* | | (o (lambda (n) | | (if (= n 0) #f (e (- n 1))))) --* | ) | (lambda (n) (e n)) )) ---------------------------*

o和e里面两个lambda的if表达式现在引用的两个名字是什么？

它们没有引用这段代码中定义的任何内容。它们 “超出范围”。

为什么？可以在基于 equivalent lambda 的表达式中看到，类似于我们开始的内容，上面：

(define even?-wrong- ^ ^ ( (lambda (e o) <----. ----|---|---------. (lambda (n) (e n)) --* | | | ) | | | (lambda (n) | | <------+ (if (= n 0) #t (o (- n 1)))) ---* | | (lambda (n) | <------* (if (= n 0) #f (e (- n 1)))))) -----*

这定义了名称even?-wrong-来指代评估应用(lambda (e o) (lambda (n) (e n)) )表达式返回的对象到通过评估另外两个lambda产生的两个对象的评估结果表达式，参数位置中的表达式。

但是它们中的每一个都包含一个自由变量，一个在其范围 中不引用任何定义的名称。一个包含未定义的 o，另一个包含未定义的 e.

为什么？因为在应用程序(<A> <B> <C>)中，每三个表达式<A>，<B> 和 <C> 在同一范围内进行评估 - 应用程序本身出现的范围；封闭范围。然后然后将结果值相互应用（换句话说，进行函数调用）。

A "scope" 只是代码中的文本区域。

然而我们需要第一个参数 lambda 中的 o 来引用第二个参数 lambda，而不是其他任何东西（或者更糟的是，根本没有）。与第二个参数lambda中的e相同，我们需要指向第一个参数lambda。

let 在 首先包含 whole let 表达式的范围，然后创建一个新的环境框架，其变量名称绑定到结果值从那些评价中。同样的事情发生在等效的 three-lambdas 表达式求值中。

letrec，另一方面，首先创建新的环境框架，其变量名称绑定为yet-undefined-values（这样引用这些值肯定会导致错误），然后它在 这个新的 self-referential 中计算它的 init 表达式 frame，然后将结果值放入对应名称的绑定中。

这使得 lambda 表达式中的名称引用内部整个letrec 表达式的范围中的名称。与 let 引用 outer 范围相反：

^ ^ | | (let ((e | | (... o ...)) | (o | (............ e .........))) .....)

不有效；

.----------------. | | (letrec ((e <--|--------. | (..... o ...)) | | (o <-----------|-------* (.............. e .........))) .....)

工作正常。

这里有一个例子可以进一步说明：

1。考虑 ((lambda (a b) ....here a is 1.... (set! a 3) ....here a is 3....) 1 2)

现在考虑 ((lambda (a b) .....) (lambda (x) (+ a x)) 2)。

两个 a 是 不同的 -- 参数 lambda 是 ill-defined。

现在考虑 ((lambda (a b) ...(set! a (lambda (x) (+ a x))) ...) 1 2)。

这两个 a 现在是一样的了。

所以现在有效。

为什么 let 不允许相互递归定义，而 letrec 可以？

Why does let not allow mutually recursive definitions, whereas letrec can?

evaluation

scheme

let

letrec