递归尾部优化是如何工作的？

Question

对于从调用堆栈中放置/删除的内容，递归尾部调用优化如何工作？专门针对类似 LISP 的语言？组装级别的任何见解都会有所帮助。

我先展示下图。我假设调用函数是否有递归调用作为 IF 的第三个参数，本地参数可以从堆栈中删除，因为递归调用不需要它们。另外，我假设像 LET 创建一个单独的堆栈这样的函数。

Answer 1

很久以前，我为 RCA 1802 编写了程序（我还没有那么老，但它的抗辐射版本对我们来说很有趣）。

1802年是原始的。特别是它不支持子例程调用和返回。相反，如果您想要子例程，您需要决定哪个寄存器是堆栈指针，然后

调用例程

然后就送你回来

（可能细节有误，已经很久了。）

负责该事物代码的每个人都必须就哪个寄存器是 SP（实际上哪个寄存器是 PC）以及堆栈在哪里等等达成一致。

我们正在开发的系统内存非常非常少（在某个时候，来自美国的人想买我们的东西，并说所有软件都必须是 Ada 或 FORTRAN 语言。我们笑了）。一些聪明人想出了以下技巧：

如果您的子例程要调用另一个例程然后返回，您可以避免上述整个过程：您可以直接转到您想要调用的子例程的地址。这节省了所有指令、堆栈空间和时间。

我们不知道这一点，但我们刚刚重新发明了尾调用消除。

当然，你教编译器这样做：当它意识到即将编译对函数的调用（这是它正在编译的函数中发生的最后一件事）时，它可以只编译跳转。

在像 Common Lisp 这样的语言中，对此有一些警告。例如，考虑编译类似的东西

(defun foo (x)
  (let ((*v* x))
    (declare (special *v*))
    (bar (1+ x))))

对

bar

的调用可能是也可能不是尾部调用，因为它可能是也可能不是

foo

所做的最后一件事，具体取决于特殊变量的实现方式。类似的事情也适用于，例如，

(defun foo (x)
  (handler-case
      (bar x)
    ...))

对

bar

的调用很可能不是尾部调用，因为条件处理程序需要在返回时撤消。

最后，很多 Lisp 编译器传统上只在直接递归调用时处理尾部调用消除，因为编译器可以更多地了解被调用的函数如何工作。另一方面，方案要求消除所有尾部调用。