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

Question

我怀疑我从根本上误解了Scheme的评估规则。是什么让let和letrec的编码和评估方式使letrec能够接受相互递归的定义，而let不能？诉诸其基本lambda表格可能会有所帮助。

Answer 1

以下内容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)) ))      ---------------------------*

现在两个 lambdaif表达式中的o和e两个名称指的是什么？

它们不引用这段代码中定义的任何内容。它们"超出范围"。

为什么？它可以在等效的基于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>三个表达式中的每一个都在相同的范围内求值 - 应用程序本身出现的范围;封闭范围。然后将结果值相互应用(换句话说，进行函数调用)。

">范围"只是代码中的一个文本区域。

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

---

let首先在整个let表达式的封闭范围内计算其变量的init 表达式，然后创建一个新的环境框架，其变量名称绑定到这些计算产生的值。等效的三 lambda 表达式计算也会发生同样的事情。

另一方面，letrec首先创建一个新的环境框架，其变量的名称绑定到尚未定义的值(这样引用这些值肯定会导致错误)，然后在这个新的自引用框架中计算其init 表达式，然后将结果值放入其相应名称的绑定中。

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

^        ^
|        |
(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)

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

这两个a是不同的- 参数lambda定义不明确。

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

这两个a现在是一样的。

所以现在它工作了。

Answer 2

let不能以任何明显的方式创建相互递归函数，因为您始终可以将let转换为lambda：

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

同样，对于多个绑定：

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

在这里和下面，-->的意思是"可以翻译成"甚至"可以宏观扩展成"。

好的，现在考虑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 中所述的环境模型。 特别要考虑在环境中评估此形式，例如，在该环境中，factorial没有约束力。这是表格：

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

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

从函数形式开始：

(λ (factorial)
(factorial 10))

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

1. 创建一个环境e'，该环境将 E 与函数参数的factorial绑定扩展到e;
2. 调用与参数10绑定factorial的任何内容并返回结果。

所以现在我们必须再次在环境e中评估参数：

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

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

1. 建立一个环境e''，该环境将e与函数参数的n绑定扩展到 e;
2. 如果参数不是1，将尝试调用绑定到factorial变量的函数，在e''中查找这个绑定。

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

相反，您需要执行以下操作才能完成此操作：

(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中对此进行计算会产生一个函数，该函数在调用时将：

1. 创建一个环境 e'，扩展e，其中factorial绑定到任何参数;
2. 改变e'中factorial的绑定，为其分配不同的值;
3. 调用e'中的factorial值，参数10，返回结果。

所以有趣的步骤是(2)：factorial的新值是这个形式的值，在e'中计算：

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

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

1. 创建一个环境e''，它扩展e'(注意！) 与n的绑定;
2. 如果n的绑定值不1，则调用e''环境中绑定到factorial的任何内容。

现在这将起作用，因为在e''中存在factorial的绑定，因为现在e''扩展了e'，并且在e'中存在factorial的绑定。此外，当函数被调用时，e'将被改变，因此绑定是正确的：它是函数本身。

事实上，这或多或少是letrec的定义方式。 以类似的形式

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

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

例如参见R6RS(其他报告类似，但更难参考，因为它们中的大多数是PDF)：

<变量>绑定到新位置，在生成的环境中(以某种未指定的顺序)计算，将每个<变量>分配给相应的结果，在生成的环境中计算，并返回中最后一个表达式的值。<变量>的每个绑定都将整个letrec表达式作为其区域，从而可以定义相互递归的过程。

这显然类似于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组合器非常接近，或者我一直认为是。

---

最后，将快速而肮脏的letrec编写为宏相当容易。 这是一个叫做labels(见这个答案的评论)：

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

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

Answer 3

让我们从我最喜欢的相互递归示例的版本开始，偶数或奇数。

(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?未绑定。 其描述性原因是，在绑定变量之前，定义let中初始值的表达式在词法环境中进行评估，而letrec首先使用这些变量创建一个环境，只是为了完成这项工作。

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

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

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

因此，用let写even-or-odd将变为：

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

你可以看到，内部偶数？和内部奇数？的主体是在这些名称绑定的范围之外定义的。 它得到一个错误。

为了在希望递归工作时处理此问题，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?正在它们被绑定的上下文中使用，并且一切都有效。