Annotated tail call syntax (still valid es6/5)

[bobzhang]

There is a drawback of current syntax tail call proposal, it is not valid ES6/5 syntax. which means people will not take it serious for years. Even a transpiler could not take advantage of it.

Suppose we have some syntax like this( I know this is a horrible syntax, but hope my ideas are clear):

function sum (acc, n){
  if(n === 0} { return acc}
  else {  /*tail*/return sum (acc +n , n -1); 
}

The code above is still valid code under any JS engine, it just happens to more efficient when tailcall enabled.

FWIW, ocaml has a tailcall attribute like this

let rec sum acc n = 
   if n = 0 then acc else sum (acc + n) (n - 1) [@tailcall]

I believe having a valid es6/5 syntax will help the adoption of tailcall, all transpilers(including babel or typescript) will beneift from it

[bobzhang]

btw, I think it maybe a proper time to introduce annotations in Javascript, annotations are particular useful hints for compiler optimizations, but does not change its semantics significantly

[bterlson]

PTC is about making sum above actually work for large n and not for making function calls faster. It is not clear (see #7) that PTC will result in noticeable speedups and in fact may result in perf losses in some implementations and some invocations.

You would not implement sum today like that because browsers without PTC would throw errors for large n. Same story with STC, except the error occurs earlier (and is a syntax error) rather than later as an out of memory error.

[bobzhang]

@bterlson of course, it is a toy example, any decent transpiler can make self recursive call into a loop. The real case is for mutual tailcall. I believe it will be helpful to make JS a better backend

[bobzhang]

Currently when we compile OCaml into Javascript, in some cases, it will cause stackoverflow(Ocaml support tailcall properly), I believe other transpiler will suffer the same issue.

Having annotated valid ES6/5 syntax tail call will make JS a better functional language backend.

[bterlson]

The OCaml case is interesting... If an OCaml transpiler emitted a return continue, it wouldn't work in browsers that don't support tail calls. If it instead emitted ES6 PTC syntax, then it might work in browsers that don't support tail calls. Seems like both amount to the same - don't emit that code unless you can target only browsers that support it. I don't have a sense of how common OOM errors are for typical OCaml programs, though...

[getify]

I believe having a valid es6/5 syntax will help the adoption of tailcall, all transpilers(including babel or typescript) will beneift from it

I've already made this case here: #1 (comment)

And here: #4

In both cases, the tone of the responses in the threads seems to suggest doubt/disagreement that this position matters (much). :/

[bobzhang]

@bterlson Here is an example of stackoverflow due to lack of tailcall support on the JS backend: https://github.com/ejgallego/jscoq/issues/13
We do quite smart analysis even for mutual tail call( and I believe typescript/babel can do this too) but can not provide any guarantee without ES6 tailcall support.
Tail call is an essential feature of functional programming, it makes JS more expressive to do fancy CPS programming, in my opinion it is one of two features in ES6 to make JS more powerful( the other is Typedarray).

tailcall is an advanced feature that I don't mind a verbose explicit syntax, but it would be much helpful to make it valid ES6/5 Syntax, since it takes time for browser to catch up

[bobzhang]

A bunch of transpilers would appreciate a valid syntax (not just ocaml), like scalajs, typescript, babel, clojurescript, purescript, elm etc.

[littledan]

I don't believe that ignoring the tail aspect is a valid implementation. It changes behavior by making the space complexity asymptotically lower, which is a significant, non-backwards-compatible change, both for browsers with fixed and variable sized stacks (and both of these are widespread). Using an invalid syntax for tail calls is, therefore, a feature, not a bug.

Independent of STC vs PTC: Developers should not write code using tail calls unless they are executing in an environment which will eliminate the stack frame. Transpilers should not eliminate continue or translate tail calls from other languages as a simple return for current browsers, as this is an invalid translation which does not preserve behavior and instead breaks users' code. STC/PTC will be only really usable across browsers when it is implemented across browsers as a proper tail call, and doing a normal function invocation will not be a usable transition path.

[bobzhang]

Tailcall is an essential feature in functional language, think about in c you don't have loop. Introducing an incompatible syntax will make it not relevant in next 3 years IMHO.

We can have something like

 /**tailcall**/ return ... 

The transpiler can do it best to convert tailcall into loop offline, which means in most old browsers, it still work, but in modern browsers, it can handle larger data.

[bterlson]

What is the difference between tailcall return and return continue (grammar aside)?

Fwiw, no one here is contesting the utility of tail calls. We recognize that this is essential for some languages. What I don't yet understand is why it's valuable that PTC syntax is valid non-PTC syntax (ie. why ES6 syntax and semantics are preferable to those proposed here).

[bobzhang]

@bterlson thanks for recognizing the importance of tailcall !

For a functional language which tries to target JS as a backend, it will typically do two things: first it will try to pin-point which functions are (mutual)recursive functions and try to convert it into a loop.

However, when it can not (some mutual recursive tail calls can get really complex), it can emit code like this

/*@taicall@*/ return ...

Note that it's not that user can choose not to use tailcall, since in pure functional languages, recursion is the only proper control flow.

It helps a lot if it's still valid ES5 syntax, since transpilers don't need maintain two backends.
If here we introduce a new syntax, we will maintain two backends, but that's not the worst thing, the deployment cost is huge, we have to figure out the client's capability to deploy proper code.

As I said before, maybe it is time to introduce a comment based annotation syntax.

FYI, ocaml itself supports tailcall, no matter user have [@tailcall] annotation or not, however, [@tailcall] helps when user write down tailcall but it is not actually in the tailcall position, the compiler would complain in that case.

[efaust]

I'm not sure I understand. Even with no syntax at all, you /still/ have to figure out when it's safe to deploy code that relies on tail calls, since it just WON'T RUN without an engine's implementation of PTC. There is no way to cheat around that, regardless of syntax, if the loop conversions don't work in all cases.

[bterlson]

Specifically, "we have to figure out the client's capability to deploy proper code" is true in either proposal. Either you have to test whether a client has PTC (presumably by calling a recursive function a suitable number of times to observe whether PTC is enabled) or STC (presumably by detecting if return continue foo() is a syntax error). You cannot simply emit ES5 code and hope clients have PTC because those that don't (most clients) will get errors.

[bobzhang]

Basically it is impossible to compile proper functional languages into Javascript without tailcall support(unless you go with trampoline, which is too slow in practice).

However, given the smartness the transpiler can be, it is not a problem in practice (especially when the data is not too large), so for functional languages which rely on tailcall, it will do its best effort on old browsers which does not support tailcall, but it expects modern browsers eventually catch up.

[littledan]

I don't think best effort makes much sense here. It would only work for toy programs, not real applications. Until it is supported natively in the target browser, it is important that cross-compilers use a trampoline or other strategy when the user code calls for a tail call.

[bobzhang]

Even the whole ocaml compiler is bootstrapped in browser, I don't think if it is toy program
http://bloomberg.github.io/bucklescript/js-demo/
The fact is that in most cases, compilers of functional programming languages can do offline transformation to make it a loop, for too complex cases, we wish browsers could catch up
eventually.
I think tailcall is mostly a feature for transpilers to take advantage of. If the user has to know
when to pass return continue properly, I think it is too difficult for average developers to master

[rossberg]

@bobzhang, the counter argument is that syntactic tail calls actually help the users, because it gives them a way to have their assumptions checked. That should particularly aid those who have not fully mastered tail calls yet.

[bobzhang]

@rossberg-chromium That's fair. May major concern is that introducing a new syntax means we can not write or generate future-proof code.
It is fine to have explicit annotation for tailcall, my best wish is that such explicit annotation can still be accepted by browsers which don't support it.(like asm.js)

If you have a look at es6 vs es5 from the traspiler's point of view, the only major language semantic differences is tailcall. It is a pity that we step back on this point.

[ljharb]

@bobzhang and WeakMap, and Proxy, and Symbol, and all the new syntax ES6 already introduced…

[bobzhang]

@ljharb that's runtime feature, not language feature :-)

[littledan]

ES2015 includes tons of core language semantics changes. Basic operations like instanceof, reading local and global variables, const, and property access have different semantics from previously.

If you want to write future-proof code, and are OK with current browsers, then you can simply continue to not use the tail call feature.