Allow asm.js code to use proper tail call optimization in the future

[mnieper]

asm.js should not only be a compile-target for languages with C-like semantics. To effectively compile languages with proper tail calls, first-class continuations, etc., asm.js also needs to support proper tail call optimization.

At the moment, this is a wish for the future because the underlying language, ES5 does not have proper tail calls. However, this changes with ES6, which will be a perfect compilation target.

Sadly, the way the asm.js spec is currently written, it seems that it prevents the use of proper tail calls that come to ES6. The general construct to tail-call another function f is return f(args). A return statement like this one, however, is currently only valid for return float values.

Thus I strongly propose to allow return statements of the form return f(args) in asm.js functions whenever `f`` is another function of the module (and validation succeeds). This should not clash with the usage of this statement to mark the function's return type to be float.

Also, by the same reason, function table calls should be allowed in tail position. This should also pose no problem to the static type system of asm.js.

[ghost]

I think you're right we should allow tail-calls in asm.js as it would make asm.js a better compilation target, esp. for functional languages. The only rub is picking the return type in situations like:

function f() { return f() }

One very simple rule would be to say that a "return f()" statement does not count as the "final return statement" required by the spec so that you'd have to write:

function f() { return f(); return 0 }

A slightly more complicated but still simple-enough rule would be to say that there must be at least one non-tail-call call in the function, which includes the above case but, also:

function f(i) { i=i|0; if (!i) return 0; return f((i-1)|0) }

since the 'return 0' establishes the return type.

Anyhow, this is on the list: https://wiki.mozilla.org/Javascript:SpiderMonkey:OdinMonkey#Possible_asm.js_extensions_that_don.27t_require_new_JS_features although not a major priority atm.

[hikari-no-yume]

Couldn't compilers replace tail calls with loops, when targeting asm.js? Is there actually a need for explicit asm.js tail call support?

[dcecile]

Here's one example, written in JavaScript:

var x = {};
var y = {};
x.execute =  function (i, j) { return y.execute(this, i - 1, j * 2); };
y.execute = function (helper, i, j) { return i === 0 ? j : helper.execute(i, j * j); };

Because the compiler doesn't know which object will be passed in as the helper for y.execute (any object that satisfies the interface would be fine), there's no way for the compiler to match up these 2 tail-recursive methods and put them together in a single loop.

So, to answer the second question, as far as I understand, the only real substitute for native tail-call optimization would be for a compiler to implement tail-calls optimization from scratch by turning all function calls into GOTOs (issue #80).