尾递归函数是否重用Scheme中的单个环境？

Question

我目前正在学习函数式编程的本科课程，我们刚刚了解了Scheme 中的环境。据我了解，环境是执行函数的上下文，即每个函数调用都会创建一个新环境（现有环境的子环境），并为函数体添加附加符号绑定。

我的问题特别是关于尾递归函数。 Scheme 规范保证尾递归调用使用 O(1) 空间。然而，我遇到了关于如何实现的两种不同的解释：

1. 当前环境在尾部调用时被新环境替换（这似乎更有效）。
2. 为每个尾部调用创建一个新环境，但旧环境被垃圾收集，使整体空间复杂度保持在 O(1)。

第二种解释似乎效率较低，我想知道这是否是尾递归在实践中如何工作的准确描述。我查看了 R5RS 规范，但在这一点上我找不到明确的答案。

此行为是实施细节吗？如果是这样，流行的Scheme实现如何在环境管理方面处理尾递归函数调用？

Answer 1

我认为你不能仅仅因为进行尾部调用就真正破坏父环境。确实，递归调用不需要返回它，但如果递归函数在进行递归调用之前创建了一个闭包，那么它可能是另一个环境的父环境。这通常发生在“连续传递风格”（CPS）中。

这是一个如何发生这种情况的示例。假设我们与树木一起工作。我们用空列表表示一棵空树，用一个三元素列表表示一棵非空树，其中包含节点的值、左子节点和右子节点。我们需要一个函数来告诉我们从根到最左边叶子的路径上的所有节点。

(define (path-to-leftmost-leaf k t)
  (cond ((null? t) (k '()))
        (else (let ((x (car t))
                    (left (cadr t)))
                (path-to-leftmost-leaf (lambda (path) (k (cons x path)))
                                       left)))))

我们积累了一个“延续”，

k

，它将构建结果列表。要调用此函数，您需要向其传递一个延续；如果您不想使用结果列表调用其他 CPS 函数，则

(lambda (x) x)

适合。例如：

> (path-to-leftmost-leaf (lambda (x) x) '(k (l (l () ())) (r () ())))
(k l l)

如果对

path-to-leftmost-leaf

的递归调用将其环境替换为新环境，那么各种

k

函数将位于何处？

---

上面的讨论，以及你的问题，都是在“环境模型”的背景下。它被称为模型，因为它并不（必然）反映编译器/解释器的实际工作方式，而是为您提供了一种方法来推断给定程序将产生什么结果。解释器可以自由地以更有效的方式做事，只要这种方式仍然产生预期的结果。我不是专家，但我认为在实践中现代Scheme实现并没有真正使用环境链，因此销毁或替换环境的问题并没有真正出现。