Is this proposal dead?

[mathiasbynens]

https://github.com/rwaldron/tc39-notes/blob/master/es7/2016-05/may-24.md#syntactic-tail-calls-bt

It seems like this proposal is no longer making progress. If this is the case, could a note saying as much be added to the README?

Ref. https://twitter.com/esosanderelias/status/891931088817463296

[SanderElias]

Also, if this is dead, what's the alternative?

[ljharb]

It's currently marked as inactive https://github.com/tc39/proposals/pull/56/files#r126664543

[getify]

Do the objecting browsers (ff, edge) just intend to willfully violate the spec and not implement ptc as spec'd? Would be nice to have an update.

[SanderElias]

@getify You can add chrome to that list. It has pulled the code for PTC out for turbofan.

[lukewlms]

Quote for Turbofan removal of PTC - looks like indeed, even the --harmony-tailcalls flag is being removed.

The tail call implementation is hidden behind the --harmony-tailcalls
flag, which is off-by-default (and has been unstaged since February).
It is known to be broken in a variety of cases, including clusterfuzz
security issues (see sample Chromium issues below). To avoid letting
the implementation bitrot further on trunk, this patch removes it.

https://bugs.chromium.org/p/v8/issues/detail?id=4698

[littledan]

There are two things here:

• IIRC Firefox, Chrome and Edge have all said they don't have plans to implement ES2017 implicit tail calls in JavaScript.
• This proposal for explicit tail calls encountered some resistance in TC39.

I think this proposal is revive-able. A parallel discussion about tail calls is happening in WebAssembly, where the same killer ABI issues come up. I don't see what the difference should be between JS and WASM here, but I am happy to see that, in the WASM meeting notes, there is a bunch of frank discussion of implementation constraints.

The logic for rejecting this proposal while keeping implicit tail calls never made sense to me. I still don't really understand it. It seemed to be based on, implementation constraints mean something different whether you explicitly ask for something vs whether it's implicitly there based on the position. I'd think, if we do implicit tail calls, then putting something in tail position is exactly as strong a guarantee as if you use the syntax in this proposal.

In discussing this proposal, it seems to have come out that the ES2015 design was based on a lack of solidity on what the explicit tail call syntax should be. This proposal provides such an explicit syntax, and I'm not aware of any problems with the syntax itself (more higher-level problems on whether we want explicit tail calls).

I'd prefer to consider this proposal "inactive" rather than withdrawn. In my opinion, it's still a better design than the ES2015 implicit tail calls design. It's just not currently being pushed in committee.

EDIT: Added a link to the WASM TCO discussion notes

[getify]

TC39 should remove implicit tail calls from the spec if (some) browsers are refusing to implement it.

As it stands, this is a failed process and is extremely disappointing to those of us who care deeply about recursion techniques.

[getify]

then putting something in tail position is exactly as strong a guarantee as if you use the syntax in this proposal.

Definitely some concern about people accidentally opting into speed-harmful (but memory-improving) naive tail calls. There were several suggestions to mitigate this with TCO options on top of PTC where the tail calls only kick in after a certain depth of call stack or whatever. Seems like it was easier to reject than do those.

[littledan]

It seems pretty complicated to make a system which is, "TCO not all of the time, but enough of the time that it's as if it's happening all the time." I understand if implementers are a little worried of the prospect of providing that sort of guarantee.

[SanderElias]

@littledan Then STC makes even more sense. As an user explicitly asks for TCO, the lexer can check that there is only a single function call following that statement (regardless of the syntax that it's going to get!) and error out when it's not.

For the debugging part, document that using STC will produce a 'flattened' error stack trace. If it's possible, a number of iterations can come in handy. If a dev needs to debug, they can temporary switch to the default return in stead of STC.

I do agree with @getify that if only one browser is gonna support TCO it should be taken out of the standard. The current situation is strange, ES5 requires TCO, but almost none of the browsers confirm to that.

[getify]

"TCO not all of the time, but enough of the time that it's as if it's happening all the time."

That's not the guarantee of PTC from the perspective of the user (end-developer), or at least that's not what the guarantee has to be interpreted as.

The only guarantee necessary is that a program using tail calls will not grow the stack frame memory usage at O(n) but at O(1). Of course, O(5) or O(20) or O(1000) are all acceptable as long as all those are lower than whatever arbitrary RangeError limit the system would normally have to enforce to prevent a runaway memory situation.

There's no reason the guarantee would have to be so strict as to appear as "happening all the time", because developers couldn't reliably benchmark memory usage so precisely to the point where they were ensuring a literal stack frame size of 1 anyway.

Those of us who want to rely on tail calls really only want a system which can run an algorithm in fixed memory without the RangeError (and of course without actually exhausting system memory). That's really it. It would be nice if these situations weren't slower, but that's neither required by the spec nor strictly part of the use cases that PTC necessarily implies. Developers make tradeoffs in memory vs speed all the time, and there's no reason they couldn't responsibly do so with PTC as well.

My understanding is that PTC is just that idea of tail calls in the sense of fixed memory usage, while TCO (a whole range of various optimizations that make it practical) is left entirely up to the browsers to figure out and implement (or not) as they see fit.

Safari shipped PTC and ostensibly has some form of TCO in it to make it practical. So it is possible in modern browser architecture. It's not only possible, but practical enough that we're not hearing any widespread, "ZOMG my code all of a sudden runs unacceptably too slow in Safari because PTC has slowed down every function call" complaints. I think those fears were not as warranted as was claimed.

[hax]

TC39 should remove implicit tail calls from the spec if (some) browsers are refusing to implement it.

Apple (Safari team) say no to STC which make this proposal inactive, they can also refuse to remove PTC from the spec, can they?

[elijahdorman]

Something needs to happen one way or the other. If the spec committee cannot agree, then perhaps it is time to reach out to the larger developer community.

Have both sides make written arguments explaining the drawbacks and advantages of each position. Let developers vote on which solution best matches their needs. Spread this to as many sources as possible and stress that the result is final. After a period of a couple of months, collect the results and either implement the current PTC spec or revise the spec and proceed with the STC proposal.

[backspaces]

I agree with @elijahdorman. I just naively started testing Javascript as a FP language with this lambda:

const sum = x => x === 0 ? 0 : x + sum(x-1)

My unit testing failed for large inputs. I had assumed that most of es2015 was implemented. Checked Safari and Chrome. One failed, the other worked.

JS is supposed to be an ECMA standard. It clearly is not. Lets either remove it from the standard, or provide reasonable implementations.

I am far less concerned about "pure" FP and much more concerned about JS as a standard.

[mgol]

@backspaces Your example doesn’t have a tail call so even on Safari it will fail for a reasonably large x.

[SanderElias]

@mgol You are right, Doesn't really matter for the discussion. He is right that something should start moving here.
You really can't use JS in a truly functional way, because of lack of good recursion support.
I know one can hack is way in by using trampolines and stuff. but that's not a proper solution to the problem.
Something like:

Function addThemUp(i,sum=0) {
   if (i === 0 ) return sum
   if (sum + i > Number.MAX_VALUE) throw new Error('Maxium vaulue reached!')
   return addThemUp(i-i,sum+i)
}

Should work for any size of number. (Might take a while, but that's not the issue!), and not require additional helpers that make the logic more complex.
I like the simplicity of contructs like this way over conventional loopings.

[backspaces]

Hi @mgol, thanks for the tip. Is it not a tail call because it is a lambda expression? I.e. does not use a "return"?

I've been using http://2ality.com/2015/06/tail-call-optimization.html as a guide but it's a bit dated. Any pointers much appreciated!

[elijahdorman]

@backspaces

A proper tail call only happens when the return of the function is a function. In your example, rather than returning a function, you return the result of an addition.

var sum = x => {
  var innerSum = (x, n) => x === 0 ? n : innerSum(x-1, n+1);
  return innerSum(x, 0);
};```

[backspaces]

OK, I am compulsive :). I stared at the examples above and built a tiny html file to test both the function() form and the lambda form (=>)
http://backspaces.net/temp/tailcall.html

On Sierra Version 10.1.1 (not High Sierra, could be the difference), Safari actually does apparently implements PTC.

Running this on Chrome latest exceeds the stack limit between 1,000 & 10,000 while Safari labors up to 1,000,000,000. It does run slowly with the console open .. faster to run closed then open when the progress bar halts.

And yes, according to the Good Doctor Axel, the lambda expression should work. http://2ality.com/2015/06/tail-call-optimization.html

But back to the topic .. it seems that the standard is implementable, but may have performance issues. Is it only corner cases that cause the problem motivating STC? Certainly having every function ending in a function call (not itself) would be extreme.

The code is:

'use strict'
// function sum(i, acc = 0) {
//    if (i === 0 ) return acc
//    return sum(i - 1, acc + i)
// }
const sum = (i, acc = 0) => i === 0 ? acc : sum(i - 1, acc + i)

const tens = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
const powers = tens.map(i => 10 ** i)
for (const i of powers) {
  const num = sum(i)
  console.log(i, i.toExponential(1), num, num.toExponential(1))
}

[Pauan]

@backspaces Is it only corner cases that cause the problem motivating STC?

No, the performance problems are quite pervasive: they affect all/most function calls.

Certainly having every function ending in a function call (not itself) would be extreme.

It doesn't require every function call to be in tail position. The determination of whether it is a tail call or not is based upon each individual function call:

function foo() {
    if (someCondition) {
        // Guaranteed to be a tail call, will *not* grow the stack
        return bar();

    } else {
        // *Not* a tail call, it might grow the stack!
        return bar() + 1;
    }
}

As you can see, a single function might contain a mixture of tail calls and non-tail calls. When making a tail call, it is guaranteed that it will not create a new stack frame, whereas when making a non-tail call it might create a new stack frame (and thus eventually get a stack overflow).

As a general rule of thumb, if you have a function foo, and foo calls a function bar, and foo returns the value of bar(...), then the function call is in tail position, otherwise it isn't. (Of course the same rules apply when foo calls itself)

So in the above example, return bar() obviously returns the value of bar(), therefore it is in tail position.

On the other hand, return bar() + 1 does not return the value of bar(), because it has to add 1 to it before returning, therefore it is not in tail position.

It might be easier to understand if you view it as return (bar() + 1) instead.

Also, the determination of whether a function call is a tail call or not is based upon the syntax, not the semantics:

function foo() {
    // This is *not* a tail call!
    let a = bar();
    return a;
}

function foo() {
    // This *is* a tail call
    return bar();
}

As you can see, even though the two examples above have the same behavior, one of them is a tail call and the other one is not.

The same rules apply to the short lambda syntax, you just have to imagine an implicit return ... in the lambda body.

This is how tail call optimization has worked for decades in other languages (e.g. Scheme). You can read more about it here.

[backspaces]

So would it help, in terms of a compromise, if PTC was limited to only the case of a function calling itself?

I was surprised to see the definition of PTC including any function.

There is still the overhead of determining there is no closure state, global variables, and so on. But I'd presume that limiting it to the tail call being to itself would be potentially simplifying.

[getify]

@backspaces I wouldn't be satisfied with that, as one of the most important use cases I currently face is not recursion but simply wanting for all the tail calls in the multiple layers of function wrapping of FP to not grow the stack.

[backspaces]

Hi @getify (thank you for your work!) So you mean literally reuse the stack for functions whose tail is another function call of any sort?

I had thought most FP (like D3) returned an object for further chaining. But then I've learned D3 is not really FP, even tho quite nice.

But doesn't this make debugging difficult? No stack trace?

Hmm.. maybe this could actually be easier to implement .. simply use this everywhere? My bet that it would have to have an opt-int. Oh wait, STC of some sort! Doh, finally He Gets It.

Re: Performance: it is a one-time, compilation hit, I believe, thus not a per-call cost?

[getify]

@backspaces I mean something like this:

function f(x,...args) {
   return x(...args);
}

function p(y,z,...args) {
   return y(...args);
}

f(p,x=>x+1,12,13);

IME with FP, I'm often creating these multiple abstracted layers of function calls with various operations on the arguments being performed in the intervening steps. If I had an environment that supported tail calls, I would try to make as many of these calls as possible in PTC form (or STC or whatever) to reduce the overhead of the calls in the resulting call stacks.

I think one of the "theories" of FP is that function call wrapping of this sort is kinda "free", but when you don't have the benefit of a fully AOT compiled language to optimize away such abstractions, those calls can add up when there's thousands of them strewn through your data flow logic.

The point I'm making is, tail calls are just as important for non-recursion as for recursion.

[hax]

@backspaces 's example shows that STC may be the better solution for most js developers who not very familiar with tail calls 😅

The only problem is how to convince Apple to change their mind. There is no technical issue at all. Sigh...

[trgwii]

The refusal to implement this is beyond frustrating... Syntactic tail calls (or implicit tail calls) would also simplify generator functions greatly, by allowing recursive generators.

Iterative approach:

function* numbers(init = 0) {
  while (true) {
    yield init;
    init++;
  }
}

With tail calls:

function* numbers(init = 0) {
  yield init;
  return yield* numbers(init + 1);
}

[glathoud]

Until STC is implemented, here's a possibility to use tail calls - including mutual recursion - in today's JavaScript, get rid of stack overflow problems and obtain excellent performance: http://glat.info/fext

(for "normal" functions, not generator functions).

[mgol]

@glathoud the link is 404

[glathoud]

@mgol fixed, thanks

[lazarljubenovic]

Such a shame to see this ship sink. 😢 Should someone close the repo since this is definitely dead? I got my hopes up because the repo was still around when I searched for this.

[hax]

I still think this proposal is the right way to go. The question is whether there is any TC39 delegate like to retry advance this proposal and the essential problem is whether Apple delegates willing to reconsider their position after 6 years.