What are some good ways of implementing tail call elimination?

Question

I've written a small Scheme interpreter in an unholy mix of C/C++, but I have yet to implement proper tail calls.

I am aware of the classic Cheney on the MTA algorithm, but are there other nice ways of implementing this? I know I could put the Scheme stack on the heap, but that would still not be proper elimination, as the standard says one should support an unlimited number of active tail calls.

I've also fiddled with longjmps, but so far I think it'll only work well for non-mutual recursive tail calls.

How do the major C-based Schemes implement proper tail recursion?

Answer 1

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.

Answer 2

Without knowing what you have, I'd say the easiest (and most enlightening) way to do it is to implement the scheme compiler and VM from Dybvig's "Three Implementation Models for Scheme".
I've done it here in Javascript (a copy of Dybvig's PDF is there too): https://github.com/z5h/zb-lisp

check src/compiler.js: compileCons, and the implementation of the "op codes" in src/vm.js

Answer 3

If you are interested in implementation techniques of interpreters, there is no way around the book "LiSP - Lisp in Small Pieces" by Christian Queinnec. It explains all aspects of implementing a Scheme system very thoroughly with complete code. It is a wonderful book.

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

But don't forget to check out the papers on ReadScheme.org.

The section

Compiler Technology/Implementation Techniques and Optimization http://library.readscheme.org/page8.html

has quite a few papers on tail call optimization.

Among others you will find a link to Dybvig's thesis (a classic), which is very well written. It explains and motivates everything in a very clear manner.