THACO
Tail Call Optimisation Explained
TCO is a favourite feature of functional languages, because it works very well with recursion on function data structures. The classic example is rewriting a simple loop.
for (i=0;i<10;i++) {
printf("%s\n", some_list[i]);
}
can be rewritten recursively
void * printRecursive(int i, some_list) {
if (i<10) {
printf("%s\n", some_list[i++]);
printRecursive(i,some_list);
}
}
If you don't have experience with functional languages, then this all seems a bit pointless. It's longer, harder to understand, and is vulnerable to a stack overflow*. TCO fixes the stack overflow problem. If the function is recursive, the compiler can re-use the original function's memory (stack space) for each extra function call, rather than allocating new memory for each recursive call.
This only works if the recursive call is the last call in the function (the tail call). In our example, this seems a bit pointless. The original loop is smaller, and might be faster. The real benefit comes from more complex cases that require recursion.
Most parsers benefit from TCO. An HTML parser, for instance, has to recursively build a data structure. And because there is no limit to how many tags a HTML page can have, the parser has to be able to cope with a page that has 1 million nested DIV tags. You could still argue a loop is better, but what about a page that looks like this?
<span>
<div>
<span>
<div>
...
the easiest way to cope with this is recursive functions.
function parseDIV (html) {
parseSPAN(html)
}
function parseSPAN(html) {
parseDIV(html)
}
TCO doesn't just work for self-recursive functions, it also works for mutually recursive functions. So it is possible to parse millions of nested tags, while only using the memory of one.
- C programmers learn that recursive functions are bad, which is a shame because GCC now has TCO optimisations.
TCO in Throff
Throff excels at Tail Call Optimisations.
Instead of the more usual ways of interpreting a program, like a parse tree, Throff uses a stack. A program to be executed is pushed, one instruction at a time, onto the code stack. For each "step" of the interpreter, one instruction is popped off the stack and activated.
When Throff activates a function, there is no "stack frame". Throff pushes all the instructions of that function onto the code stack, and then execution continues as usual. Throff gets to the end of the function by executing all the instructions that were pushed onto the code stack. There is no clear marker to indicate "the stack ends here".
The effect of this is that no matter how complicated the function is, Throff always performs a correct TCO. Normally, this requires some analysis of the function to identify the "tail" position, and there are situations where it is very difficult to detect it correctly.
Using a code stack gets TCO for free, and was a major reason in choosing a code stack in the first place.