1. 6

  2. 3

    He doesn’t actually explain how to do general tail call elimination for an interpreter. He shows some code, then says “NOTE: we can not eliminate mutually recursive tail calls with this method.”

    In Curv, I use a standard tree-walking interpreter that directly interprets an AST. It wasn’t difficult to modify it to do general tail-recursion optimization. Unfortunately, I don’t have an essay or blog post that explains the transformation, written in a style suitable for publication.

    However, if you are interested, here are some design notes that I wrote for myself, before I started writing any code. The actual code turned out a bit differently. https://github.com/curv3d/curv/blob/master/ideas/compiler/Tail_Recursion

    And here is the actual commit that implements the change. https://github.com/curv3d/curv/commit/2f8ab85b406f6bab765cc21e96971d9a569a672a

    1. 1

      Is there a way to make stack traces more useful while still keeping the good bits of tail call optimization? Let’s set out some requirements.

      One idea I have always wanted to try out is to sample tail calls such that every rand() calls, you actually recurse and add a frame to the stack trace. Maybe this is done only when running under a debugger, and maybe those frames also have some extra information in them like the previous arguments, etc.