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

Question

我用C/C++的混合编写了一个小的Scheme解释器,但我还没有实现正确的尾调用.

我知道MTA算法上的经典切尼,但还有其他很好的实现方法吗？我知道我可以将Scheme堆栈放在堆上,但这仍然不能正确消除,因为标准表示应该支持无限数量的活动尾部调用.

我也摆弄了longjmps,但到目前为止,我认为它只适用于非相互递归尾调用.

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

Answer 1

比编写编译器和VM更简单的方法是注册和蹦出您的解释器.既然你有一个解释器而不是编译器(我假设),你只需要几个简单的转换来获得对尾调用的适当支持.

你必须先用延续传递方式编写所有内容,这在C/C++中可能很奇怪.Dan Friedman的ParentheC教程将指导您将高级递归程序转换为可机器转换为C的表单.

最后,你将基本上实现一个简单的VM,而不是使用常规函数调用来执行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;
    ...
  }
}

编辑:我使用JavaScript编写了我的业余爱好Scheme解释器的相同过程.我利用了很多匿名程序,但它可能有助于作为一个具体的参考.查看FoxScheme的提交历史,从2011-03-13(30707a0432563ce1632a)开始直到2011-03-15(5dd3b521dac582507086).

编辑^ 2:非尾递归仍会占用内存,即使它不在堆栈中.

Answer 2

在不知道您拥有什么的情况下，我认为最简单（也是最有启发性）的方法是实现 Dybvig 的“Scheme 的三个实现模型”中的方案编译器和 VM。
我在这里用 Javascript 完成了（Dybvig 的 PDF 副本也在那里）：https : //github.com/z5h/zb-lisp

检查 src/compiler.js: compileCons，以及 src/vm.js 中“操作代码”的实现

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