A test for proper tail calls

Here are two versions of the same little function — or, I should say, almost the same little function:

function nonTail(n) {
    if (n > 0)
        nonTail(n - 1);
    return;
}

function tail(n) {
    if (n > 0)
        return tail(n - 1);
}

Neither function does anything particularly interesting, but it’s the way they do what they do that’s interesting. They’re both recursive, but only the second one is tail-recursive: it calls itself as the final result of a return statement. So even for very large values of n, in an implementation with proper tail calls, the tail-recursive function shouldn’t die with a stack overflow.

Here’s a test case to determine whether an engine supports proper tail calls. It should be fairly robust, even in the face of engines with different stack implementations and different VM limits: the first part of the test tries to determine experimentally what is a likely maximum stack depth for this function. (It’s doing a binary search, so it should be bounded above by about 31 × k stack frames, where k is the engine’s maximum stack depth for nonTail.) The second part then tries running the tail-recursive function with that depth and checks whether the engine throws an exception.

var lo = 0;
var hi = Math.pow(2, 31) - 1;

while (hi !== lo) {
    var mid = lo + (((hi - lo) / 2) | 0);
    try {
        nonTail(mid);
        lo = mid + 1;
    } catch (e) {
        hi = mid;
    }
}

var min = lo;

try {
    tail(min);
    tail(min * 2);
    print("test passed!");
} catch (e) {
    print("test failed!");
}

As we work on test suites for ECMAScript conformance, this kind of test should be useful for checking whether engines support proper tail calls.

PS I should point out that no current browser JS engines support proper tail calls, so right now this test will fail in all of them.

7 Responses to A test for proper tail calls

  1. As written, this test should not go into a test suite. A sufficiently intelligent optimizing compiler should detect that these functions both work tail-recursively (since they do nothing after the recursive call), and an even more intelligent one should figure out that they both do absolutely nothing.

  2. These are good points. It can be made more robust by having the function take in additional arguments; say, an object that the functions can mutate (to defeat dead code elimination) and a function to apply to the result (to defeat TCO on nonTail). The test should also make sure to observe the results of the mutation, in case of particularly intelligent dead code elimination. In principle, this isn’t perfect; sufficiently smart optimizers can probably do even better, but I think you should be able to make the test robust enough that it’s pretty unlikely to be defeated by even the most state-of-the-art optimizing compilers.

    Still, your point stands — this test isn’t robust enough as written.

    Dave

  3. Are those errors actually catchable (in all browsers)? For instance, memory limit errors can’t be caught. Other than that, sure, nice :)

    I’m still a little puzzled about the recent puff of dust about tail recursion. I mean, I know what it does, but why make a fuzz about it for the spec? Why not “just” implement it and boast about support? I’m not clear on why it should be specced at all, except perhaps only to guarantee the programmer that proper tail recursion is in. And if that’s indeed all a few simple lines of text should suffice.

    Shouldn’t matter how it’s exactly implemented, or does it?

  4. Good question about memory limit errors. I’m not sure — I’ll have to test more. :)

    As for the spec: the point of proper tail calls, is that they enable programmers to write in styles that *depends* on their proper implementation. If only some implementations support proper tail calls, then programmers can’t portably rely on them. For example, you can’t write in CPS if some browsers will blow stack.

    An analogy: imagine that on some implementations, for-loops pushed a stack frame on every iteration. Programmers wouldn’t be able to reliably use for-loops anymore, so they’d have to switch to using while-loops for everything. Now, in practice this isn’t a problem because no implementations do that, so it’s not really something we have to worry about in the spec. But no implementations support proper tail calls, so if we don’t mandate it, there won’t be enough pressure on implementations to implement them.

    That said, we will try to implement them in SpiderMonkey regardless of the spec, and hopefully that will set a good example.

    Dave

  5. Ah but that’s my point then :) I’m surprised no engine (at least so you say) has implemented ptc so far. It’s not something that could break anything, only improve. On that note it seems to me like a simple note about it would suffice. So I’m not sure why there was “bickering” over implementation details. Or maybe I read more into it than it really was. Well, thanks for clearing it up :) And good luck.

  6. Hmm. IMHO, it should still throw (even if the engine properly supports tail recursion and doesn’t actually degrade due to the calls) because I feel like optimizations shouldn’t affect program behaviour. Other than the obvious “it runs faster”, of course…

  7. IMHO, it should still throw (even if the engine properly supports tail recursion and doesn’t actually degrade due to the calls) because I feel like optimizations shouldn’t affect program behaviour.

    The key to proper tail calls are that they are not an optimization — they’re predictable, deterministic behavior.

    Even if the language spec doesn’t mandate proper tail calls, there’s no reason why proper tail calls should be considered invalid. Nothing about the language spec mandates stack overflow errors.

    Other than the obvious “it runs faster”, of course…

    Proper tail calls aren’t about going faster; they’re about space efficiency.

    Dave