20

我用 C/C++ 的邪恶组合编写了一个小型 Scheme 解释器，但我还没有实现正确的尾调用。

我知道MTA 算法中的经典切尼，但是还有其他很好的实现方法吗？我知道我可以将 Scheme 堆栈放在堆上，但这仍然不是适当的消除，因为标准规定应该支持无限数量的活动尾调用。

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

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

4

3 回答 3

13

Simpler than writing a compiler and VM is to registerize and trampoline your interpreter. Since you have an interpreter and not a compiler (I assume), you only need a couple straightforward transformations to get proper support for tail calls.

You'll have to first write everything in continuation-passing style, which may be weird to think about and do in C/C++. Dan Friedman's ParentheC tutorial steps you through transforming a high-level, recursive program into a form that is machine-translatable to C.

In the end, you'll essentially implement a simple VM where instead of using regular function calls to do eval, applyProc, etc., you pass arguments by setting global variables and then do a goto to the next argument (or use a top-level loop and program counter)...

return applyProc(rator, rand)

becomes

reg_rator = rator
reg_rand = rand
reg_pc = applyProc
return

That is, all of your functions that normally call each other recursively are reduced to a pseudo-assembly in which they are just blocks of code that don't recur. An top-level loop controls the program:

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

Edit: I went through the same process for my hobby Scheme interpreter, written in JavaScript. I took advantage of a lot of anonymous procedures, but it might help as a concrete reference. Look at FoxScheme's commit history starting from 2011-03-13 (30707a0432563ce1632a) up through 2011-03-15 (5dd3b521dac582507086).

Edit^2: Non-tail recursion will still consume memory, even if it's not in the stack.

于 2011-05-15T01:50:36.767 回答
6

如果您对解释器的实现技术感兴趣，那么没有办法绕过 Christian Queinnec 的《LiSP - Lisp in Small Pieces》一书。它用完整的代码非常彻底地解释了实施方案系统的所有方面。这是一本很棒的书。

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

于 2011-05-15T10:59:43.833 回答
6

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

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

于 2011-05-14T20:44:40.850 回答