scheme - 为什么方案中的所有实现都需要尾递归？

Question

尾递归更有效，因为它重用相同的堆栈帧而不是创建新的堆栈帧，但为什么方案中的所有内容都需要这样做？

Answer 1

Scheme 没有goto，因此所有循环最终都是使用尾递归完成的。如果没有适当的尾递归保证，就没有可靠的方法在 Scheme 中提供循环。

---

更新：我想解释一下“最终使用尾递归”的意思。让我们看一下do宏，因为@newacct 提到了它。例如：

(do ((i 1 (+ i 1)))
    ((> i 10))
  (display i)
  (newline))

正如我所提到的，Scheme 没有goto，所以它必须从某个地方得到它的循环。它实际上宏扩展为（类似）：

(let loop ((i 1))
  (unless (> i 10)
    (display i)
    (newline)
    (loop (+ i 1))))

请注意，loop这里不是关键字或内置函数。它是一个命名函数，由命名†</sup> 创建，并在^表单let^{底部被调用（通过尾递归） 。unless}

实际上，Scheme 中的所有标准循环形式都使用尾递归。没有办法摆脱它。

---

† 以下是命名let（松散地说^‡）宏扩展为：</sup>

(letrec ((loop (lambda (i)
                 (unless (> i 10)
                   (display i)
                   (newline)
                   (loop (+ i 1))))))
  (loop 1))

‡ 严格来说，它宏观扩展为：

((letrec ((loop (lambda (i)
                  (unless (> i 10)
                    (display i)
                    (newline)
                    (loop (+ i 1))))))
   loop)
 1)

Answer 2

尾递归是由语言规范强制要求的。引用 R6RS 的第5.11节：

Scheme 的实现必须是适当的尾递归。在称为尾上下文的某些句法上下文中发生的过程调用是尾调用。如果 Scheme 实现支持无限数量的活动尾调用，则它是正确的尾递归。如果被调用的过程仍可能返回，则调用处于活动状态。请注意，这包括常规返回以及通过稍后调用的 call-with-current-continuation 捕获的延续返回。在没有捕获的延续的情况下，调用最多只能返回一次，而活动调用将是那些尚未返回的调用。正确尾递归的正式定义可以在 Clinger 的论文 [5] 中找到。识别来自 (rnrs base (6)) 库的结构中的尾调用的规则在第 11.20 节中描述。

这样做的实际原因是尾递归允许使用递归实现有效的循环。

Answer 3

没有 TR 保证call/cc将无法使用。循环本身可以通过which 是语言的一部分来实现。do

编辑：事实证明这是不正确的。请参阅 John Clements 在该问题上的评论。一种语言可以具有非 TR 函数调用机制，但具有用于调用延续的特殊单独机制。