Proper tail calls in Harmony

In the last ECMAScript committee meeting, we promoted the proper tail calls proposal from “strawman” to official “proposal” status. There’s still work to do to make it into a polished spec, and it ain’t over till it ships, but I’m really excited that we could be making proper tail calls a guaranteed feature of JavaScript.

In short, proper tail calls make it possible for a function to delegate its result to a function call without allocating unnecessary space in the runtime system. In most languages, function calls always require allocating a stack frame, and stack frames are only deallocated on return. But this implementation approach isn’t necessary and even makes it impossible for programmers to write certain kinds of programs. Language implementations that guarantee proper tail calls promise that, whenever a function delegates to a function call to provide its final result (according to a fixed set of rules about what such delegation looks like syntactically), the runtime system will not indefinitely keep the caller’s frame allocated while the callee runs.

Why does this matter? For one, it makes it possible to break up large while or for loops into separate functions that tail-call one another, passing their state around as arguments instead of updating a shared piece of state. This makes it easier to understand the state and to build mock states in order to test the pieces of the algorithm independently. (I wonder if it might even open up opportunities to parallelize pieces of an algorithm into separate web workers. I’ve got another post coming on how some of Brendan’s recent ideas for Harmony might help with web workers.) Generally speaking, tail calls make it possible to modularize program control. Whether it’s just for the occasional one-off delegation (which proper tail calls makes as space-efficient as a goto), or for writing in full-on continuation-passing style (which, without proper tail calls, are more or less destined to blow the stack), this offers more flexibility for programmers to write more modular code.

The other people who stand to gain are compiler-writers. After all, compiling to JavaScript is getting more popular all the time. Tail calls make it possible to simulate lots of different kinds of control constructs in other programming languages. People have tried using setTimeout with a delay of 0, but browsers throttle these events with a minimum timeout of around 5 to 10 milliseconds (apparently, to support web pages that rely on the delay for animations). Having an officially guaranteed tail call mechanism makes it possible to compile control constructs like continuations, coroutines, threads, and actors. And, of course, it’s useful for compiling source languages with tail calls!

A word about stack traces: some people worry that tail calls interfere with getting useful stack traces. And it’s true that it can be useful to track the complete call history for stack traces, including tail calls. Now, when necessary, there are simple workarounds programmers can use for turning tail calls into non-tail calls. But a better answer is for VM writers to provide smarter stack traces which track only a finite number of the most recent tail calls in their stack traces. This satisfies the requirement of bounding the amount of allocation (since it’s a bounded amount of history) but still keeps useful diagnostic information in the stack trace. In the end, it’s true that this is a trade-off. In my experience, this cost is worth the benefit of being able to write better delegation and control abstractions.

2 Responses to Proper tail calls in Harmony

  1. It is not necessary that CPS without tail calls will blow the stack.

    I think that you are assuming that continuations are managed in the style of the Rabbit compiler. In Rabbit, every call is a tail call and all closure environments are heap allocated. So, if there are no tail calls, the stack movement is a giant series of pushes followed by all pops in the end. That will blow the stack.

    However, if continuations are managed in the style of the Orbit compiler, then the stack behavior of the CPS program is essentially the same as the behavior of the original direct-style program. Even without tail calls, the stack need not blow.

  2. Well, sure — I mean, you can use a spaghetti stack, or an incremental stack/heap strategy, and so on and so on. But really it’s an academic point; all JS implementations use a C-like stack. Anyway, notice I said “more or less,” and the point is simply that since it depends on the language implementation, programmers can’t use CPS.