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?

I see a very similar question has been asked: http://stackoverflow.com/questions/5986058/how-does-one-implement-a-stackless-interpreted-language — csl, May 14 '11 at 16:25
I found that Peter Norvig's original JScheme implements this nicely with a simple trampoline. Scroll down to eval() at http://norvig.com/jscheme/Scheme.java — csl, Sep 19 '12 at 08:19

erjiang · Accepted Answer · 2011-05-15T01:56:32.150

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.

(Edit^2) I corrected the question with regards to what the standard says, thanks. — csl, May 15 '11 at 12:15

score 6 · Answer 2 · answered May 14 '11 at 20:44

6

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

answered May 14 '11 at 20:44

Mark Bolusmjak

23,606
10
74
129

I'm not using an underlying VM, at least not yet. I've got eprogn, eval and evlis. But it uses the C stack, so it blows up on recursive loops. But thanks for the recommendations! – csl May 16 '11 at 07:27
I agree about this, but supposing you do not want to have a compiler, only an interpreter. How would you implement the tail recursion in an interpreter written in C ? – alinsoar Jan 22 '20 at 17:01

score 6 · Answer 3 · answered May 15 '11 at 10:59

6

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.

answered May 15 '11 at 10:59

soegaard

30,661
4
57
106

4

+1 for the LiSP recommendation, but heads up to anyone who goes off and downloads the code from Queinnec's site: Several chapters rely heavily on Meroonet, a CLOS-like object system which is described at the end of the book. I struggled for days to get it to work in a modern Scheme before finding that someone has packaged Meroon, a related object system for use with Gambit. You can adapt the code very easily to run with Meroon instead of Meroonet, and it works without any fuss in Gambit. YMMV, natch. http://www.math.purdue.edu/~lucier/software/Meroon/ – okonomichiyaki May 15 '11 at 19:25
1

Thanks for the reading recommendations. I do have Queinnec's book, and I've looked at his first chapter eval and evlis solutions. Guess he also uses CPS in later chapter, which seems to be the de facto way of doing this. – csl May 16 '11 at 07:26

What are some good ways of implementing tail call elimination?

3 Answers3