实现尾部呼叫消除的一些好方法是什么？

Question

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

我知道经典的Cheney on the MTA algorithm，但是还有其他很好的实现方法吗？我知道我可以将Scheme堆栈放到堆中，但这仍然不是正确的消除，因为标准说应该支持无限数量的活动尾调用。

我也使用了长tail，但到目前为止，我认为它只在非互递归尾调用中才能很好地工作。

主要的基于C的方案如何实现适当的尾递归？

Answer 1

比编写编译器和VM更简单的是注册和蹦床您的解释器。由于您有一个解释器，而没有编译器(我假设)，您只需要几个简单的转换就可以得到对尾调用的适当支持。

您必须首先以连续传递的方式编写所有东西，这在C/C++中考虑和执行可能很奇怪。Dan的教程引导您将一个高级递归程序转换为一种可被机器翻译到C.

最后，您将实现一个简单的VM，在这里，您将通过设置全局变量传递参数，然后执行一个goto到下一个参数(或者使用顶级循环和程序计数器)，而不是使用常规函数调用来执行eval、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;
    ...
  }
}

编辑：--我的业余爱好计划解释器也经历了同样的过程，用JavaScript编写。我利用了很多匿名程序，但作为具体参考，它可能会有所帮助。看看从2011-03-13 (30707a0432563ce1632a)开始到2011-03-15年间的 (5dd3b521dac582507086)。

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

Answer 2

在不知道您拥有什么的情况下，我想说最简单(也是最有启发性的)方法是实现Dybvig的“三个方案实现模型”中的方案编译器和VM。

我在这里用Javascript做的(Dybvig的PDF的副本也在那里)：https://github.com/z5h/zb-lisp

检查src/piler.js: compileCons，以及src/vm.js中"op代码“的实现。

Answer 3

如果您对解释器的实现技术感兴趣，就没有办法绕过克里斯蒂安·奎因内克( Christian Queinnec )的书"LiSP - Lisp分片“。它用完整的代码非常彻底地解释了如何实现一个计划系统的所有方面。这是一本很棒的书。

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的论文(经典)，它写得很好。它以非常清晰的方式解释和激励一切。