一些实现尾调用优化的好方法是什么？

Question

我用 C/C++ 的混合方式编写了一个小的 Scheme 解释器，但是我还没有实现 proper tail calls 。

我知道经典的 Cheney on the MTA algorithm ，但是是否有其他好的方法来实现这个呢？我知道我可以将 Scheme 堆栈放在堆上，但仍然不是 proper elimination，因为标准规定应支持无限数量的主动尾部调用。

我已经尝试过 longjmps，但迄今为止，我认为它只适用于非相互递归的尾部调用。

主流的基于 C 的 Scheme 如何实现正确的尾递归呢？

- csl

---

我看到有一个非常类似的问题被问到了：https://dev59.com/CW025IYBdhLWcg3weF6S - csl

我发现Peter Norvig的原始JScheme使用简单的跳板(trampoline)很好地实现了这一点。请在http://norvig.com/jscheme/Scheme.java向下滚动到eval()。 - csl

Answer 1

比写编译器和虚拟机更简单的方法是将你的解释器进行注册和跳转。因为你有一个解释器而不是编译器（我假设），所以你只需要进行几个简单的转换，就可以获得对尾调用的正确支持。首先，您需要使用延续传递样式编写所有内容，这可能在C/C++中思考和实现时会有些奇怪。Dan Friedman的ParentheC教程指导您将高级递归程序转换为可翻译成C的形式。最终，您将实现一个简单的虚拟机，其中您不使用常规函数调用来执行eval、applyProc等操作，而是通过设置全局变量来传递参数，然后执行goto到下一个参数（或使用顶层循环和程序计数器）...

return applyProc(rator, rand)

变成

reg_rator = rator
reg_rand = rand
reg_pc = applyProc
return

也就是说，所有通常彼此递归调用的函数都被简化为伪汇编语言中的代码块，它们不再递归。顶层循环控制程序：

for(;;) {
  switch(reg_pc) {
    case EVAL:
      eval();
      break;
    case APPLY_PROC:
      applyProc();
      break;
    ...
  }
}

编辑：我为我的Scheme爱好解释器做了同样的过程，它是用JavaScript编写的。 我利用了很多匿名过程，但它可能作为一个具体的参考有所帮助。 查看FoxScheme的提交历史，从2011-03-13（30707a0432563ce1632a）开始，一直到2011-03-15（5dd3b521dac582507086）。

编辑^2：非尾递归仍会消耗内存，即使不在堆栈中。

- erjiang

---

（编辑^2）我已根据标准进行了更正，谢谢。 - csl

Answer 2

没有了解你手头有什么资源，但我认为最简单（也是最有启发性的）方法是实现Dybvig的“ Scheme的三种实现模型” 中的计划编译器和VM。
我已经在JavaScript中完成了这个过程（Dybvig的PDF的副本也在那里）: https://github.com/z5h/zb-lisp
请查看src/compiler.js：compileCons，以及src/vm.js中“op codes”的实现。

- Mark Bolusmjak

---

我目前还没有使用底层虚拟机。我有eprogn、eval和evlis。但它使用C堆栈，所以在递归循环中会崩溃。但是感谢您的建议！ - csl

我同意这一点，但是假设您不想要编译器，只想要解释器。您如何在C语言编写的解释器中实现尾递归呢？ - alinsoar

Answer 3

如果您对解释器的实现技术感兴趣，那么绕不过去的就是Christian Queinnec的《LiSP - Lisp in Small Pieces》一书。它非常详细地解释了实现Scheme系统的各个方面，并提供了完整的代码。这是一本很棒的书。

http://www.amazon.com/exec/obidos/ASIN/0521562473/qid=945541473/sr=1-2/002-2995245-1849825

但不要忘记查看ReadScheme.org上的论文。

这个部分

编译器技术/实现技术和优化 http://library.readscheme.org/page8.html 有很多关于尾调用优化的论文。

其中包括Dybvig的论文链接（一个经典），写得非常好。它以非常清晰的方式解释和阐述了所有内容。

- soegaard

---

对于推荐使用LiSP，我给予+1的支持。但是提醒那些前往Queinnec网站下载代码的人：有几章内容严重依赖于Meroonet，这是一种类似于CLOS的对象系统，该系统在书的结尾进行了介绍。我花了好几天时间在现代Scheme中使它正常工作，最后才发现有人将相关的对象系统Meroon打包供Gambit使用。您可以很容易地调整代码以在Meroon而不是Meroonet上运行，并且在Gambit中没有任何麻烦就可以运行。当然，您的情况可能会有所不同。 http://www.math.purdue.edu/~lucier/software/Meroon/ - okonomichiyaki

谢谢阅读建议。我有Queinnec的书，也看过他第一章的eval和evlis解决方案。猜想他在后面的章节中也使用了CPS，这似乎是事实上的做法。 - csl