Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Response to the proposal to add explicit tail call syntax to ECMAScript #535

Open
msaboff opened this issue Apr 12, 2016 · 89 comments
Open

Response to the proposal to add explicit tail call syntax to ECMAScript #535

msaboff opened this issue Apr 12, 2016 · 89 comments

Comments

@msaboff
Copy link
Contributor

@msaboff msaboff commented Apr 12, 2016

After some discussion with other JavaScriptCore team members, we at Apple cannot support the suggested change to make tail calls explicit via syntax due to the expected web incompatibilities those changes will create.

Given that tail calls are currently part of the ES6 and draft ES7 specification, a compliant implementation should implement tail calls as described in those specifications. Compliance with any proposed changes would not occur for almost two years since the earliest that any proposed tail call changes could be adopted would be for the ES2017 (ES8?) specification. In the mean time web pages and Javascript applications will be created that are susceptible to future breakage.

In addition to the current JavaScriptCore implementation, it is likely that other browser venders will implement Tail Calls compliant with the current standard. Let’s consider the changes to tail calls as suggested at the March 2016 TC-39 meeting and the impact it would have on Safari and any other compliant implementations that will be shipped this year. I’d like to cover what I understood was being presented at the March meeting, but I will also cover two other reasonable variants of that proposal and my assessment of their suitability.

  1. Tail calls based on tail position are optional. Tail calls based on opt-in syntax are required.
    There will be web pages and web applications developed starting this year that take advantage of tail calls as currently specified. Those web pages would become susceptible to breakage should we change the specification. Consider web pages that take advantage of tail calls as intended in the current specification. The Javascript written for such a web page assumes unlimited tail calls. Obviously, those pages won't work on an implementation that doesn’t support tail calls. If one browser decides to stop supporting implicit tail call behavior, they break that class of web pages. Therefore early adopters like us need to continue to support the currently specified behavior. The implication of this is that ES6 tail call behavior cannot be made optional without compatibility issues for Safari. Other early adopting browsers have the same issue.

    If another browser decided to not support implicit tail calls, but waits for the proposed change and only implements explicit tail calls, they introduce cross browser incompatibilities. Certainly such a browser is not compatible when running a web page that depends on implicit tail calls and likely never will be. In addition, there would be at least another class of incompatibilities. Consider a web page that inadvertently makes infinite recursive calls. For browsers that waited for explicit tail calls, that web page could throw an out of memory exception that might be silently caught, after which the web page proceeds as expected. For Safari and other browsers that support implicit tail calls, that web page is stuck in an infinite loop. The error is in the web page, but the handling of the error by each browsers is vastly different depending on their support of implicit tail calls. We have seen this type of issue in the past and reduced our stack size to maintain cross browser compatibility.

    Approval of this proposal also encourages browser vendors to wait to implement the current ES6 specified tail call behavior. This selective delay by some implementations diminishes the purpose of the ECMAScript standard and the features contained therein. Selective support by various implementations will cause developers to delay their adoption of the programming patterns tail calls was designed to address. Again this only impacts early adopting browsers like Safari.

    The main problem with this proposal is that it relaxes normative behavior and makes it optional, effectively eliminating that behavior from the standard. After we work through the early adopter problems described above, we’d introduce a new problem: Developers don’t know if they can use tail calls based on tail position or not, since implementations vary. Feature testing for the optional tail call behavior would be difficult and cumbersome, given the current specification. Optional behavior without a feature test has little place in the standard and cannot be relied upon by implementors and developers alike.

    Given these web compatibility issues and related developer concerns, we reject this type of proposal.

  2. Tail calls based on tail position are forbidden. Tail calls based on opt-in syntax are required.
    A proposal based on this option requires that early adopting implementations, like Safari, need to change and stop supporting implicit tail calls. Those changes break web pages designed for the current spec as described above. It not only breaks those web pages, it would require that they be rewritten. The web breakage and subsequent rework by web developers caused by this option is much worse than with the first option.

    There will also be web pages that accidentally took advantage of and benefited from implicit tail calls. With this proposal, those web pages could break due to running out of stack space. These breakages would be confusing at best to the web page implementers and likely damage the perceived quality of Safari.

    Due to the breakage this imposes on Safari and web pages developed to use implicit tail calls, we also reject this type of proposal.

  3. Tail calls based on tail position are required. New syntax for verifying tail position is required.
    This is the only proposal that wouldn’t cause breakage. This proposal would be to add syntax to signify a tail call is intended, but wouldn’t change the normative nature of tail calls as currently specified. If the call is not in tail position, a syntax error is issued. Implicit tail calls as currently defined would still be normative and must be implemented by conforming implementations. This change is backward compatible. Pages developed to take advantage of proper tail calls without the new syntax would continue to work. Javascript code developed with the new syntax get additional checking and the added benefit that tail calls appear different in the source code. The usefulness of this change is minimal though as it adds optional syntax with little corresponding semantic changes.

    We recommend against this proposal, but our objection is not as strong as our objections to (1) and (2), since this proposal would not harm web compatibility. Our main concern is that this proposal could add confusion with very little benefit.

@bterlson
Copy link
Member

@bterlson bterlson commented Apr 12, 2016

Interop is about how actual implementations match and how well they run code that exists. As far as I am aware there is no actual interop concern with regard to tail calls as tail calls are not implemented interoperably in browsers and will not be for some time. It is possible (and has occurred before) that a change to a ratified specification results in more interoperability rather than less. See for example myriad changes to functions in sloppy mode or removal of Proxy's enumerate trap (something Edge had already shipped). Can you clarify what websites that exist today or in the near future would break as a result of adopting a proposal like (1)?

An implementation can do implicit tail calls without violating the spec, though I agree developers would not choose to rely on the implicit tail calls as there is no guarantee they will work. That's exactly the case they're in today and will be until they can support only browsers that support tail calls. A syntactic sigil would actually help developers feature detect an otherwise very difficult to test for feature.

@getify
Copy link
Contributor

@getify getify commented Apr 12, 2016

A syntactic sigil would actually help developers feature detect

How do you propose they do that? With try..catch and Function(..) or eval(..)? What would happen if a browser landed this syntax (to support annotations of developer intent) but refused to actually optimize some tail calls for any of various reasons? Developers still wouldn't be able to rely upon the optimization, even if the syntax test passed.

My point is merely that feature-testing is a weak argument for the syntax addition, when what's already at stake here is that a standard was developed, voted upon, and began to be implemented, and then browsers started backing off from their commitments to it. I don't see how adding syntax (that we can hackily "feature test" for, at best) is going to give us developers any more reliability on PTC than we have in ES2015, which is to say, not much.

Side Note: I proposed real feature tests for stuff like this, through an API, and it was largely shot down.

I also suggested a hackish pattern for meta-programming with PTC wherein you structure your recursive code to attempt PTC recursion, but if the env kills it because of no TCO, then you just detect and restart. I had hoped this was nothing more than an interim sort of hack until PTC was guaranteed, but it sure sounds from the tone of discussion as if it may never be.

Feature-testing with syntax (that can as easily be ignored as implicit PTC) is not any more compelling to me. It won't buy me anything I don't already get with ES2015 and -- if it's call-site based instead of function-signifier based -- will make more footguns for my recursive programming, in the cases where I forget to add it.

@bterlson
Copy link
Member

@bterlson bterlson commented Apr 12, 2016

@getify let's try to keep this thread focused on Apple's objections to hearing proposals that alleviate other implementers' concerns. I've set up a GitHub repo where we can discuss the myriad other questions/issues involved. Feel free to start a new OP (I will also be opening issues to discuss some of the questions we know we have).

@wycats
Copy link
Contributor

@wycats wycats commented Apr 12, 2016

There's something I'm trying to understand about this conversation:

"Proper Tail Calls" is the feature that is included in the ES2015 spec. It specifies a list of productions and requires engines to implement those productions as tail calls.

"Tail Call Optimization" is an alternative that opportunistically implements certain productions as tail calls, but offers no guarantees about when it happens.

From the perspective of ES5, nothing is stopping an engine from implementing TCO today. The additional debuggability constraint makes implementations less willing to ship it, but that's not something the spec directly addresses.

Aside: The Ruby VM has support for TCO, but requires you to use the "VM" interface, supply an extra flag, and compile the code separately, because the Ruby core team has concerns about debuggability. Because they have implemented the feature, we know that their concern is not implementation difficulty, but rather the impact on backtraces (and that they aren't using that as a smokescreen to avoid doing work).

Here's what I'm trying to understand:

  1. Since nothing is stopping JSC from implementing TCO in the absence of a spec blessing, there is no reason for JSC to revert the work, even if we completely removed PTC from JavaScript.
  2. Since other browsers haven't yet implemented PTC, there is no way for a web developer to rely on the behavior when writing recursive programs.
  3. There is nothing stopping Safari from making additional guarantees about PTC, so that Safari can avoid breaking developers who have come to rely on this functionality.

In addition, if we define an explicit syntax for PTC, that means that we, TC39, commit to keeping PTC in our critical path, and should avoid us regressing on engines that want to make an additional promise of PTC in the absence of an explicit opt-in.

@getify
Copy link
Contributor

@getify getify commented Apr 12, 2016

there is no way for a web developer to rely on the behavior when writing recursive programs.

One of my above points is that I don't believe this to necessarily be true, depending on what we may mean by "rely". If "rely" is a binary feature test, yes true. But if "rely" is "hope for" progressive enhancement optimization, not true.

In the latter sense, the snippet I linked to above suggests that (at least some) recursive code can be written to attempt PTC and assume/hope for TCO of it, but catch if the engine has to kill it for no TCO, and then restart and repeat the process. Code that falls into the non-TCO path will inevitably run slower/less efficiently, but still run. And developers can indeed rely on (hope for) -- because ES2015 promised it -- that "slower" code to get to the "faster" path eventually.

This is not just theory, I actually did exactly this awhile back. And it's my current strategy for bridging from non-TCO to TCO.

@wycats
Copy link
Contributor

@wycats wycats commented Apr 12, 2016

This is not just theory, I actually did exactly this awhile back. And it's my current strategy for bridging from non-TCO to TCO.

If at least one engine promises PTC (as Safari is doing), that's still a reasonable strategy :)

And if a lot of people use it, that will put pressure on the other engines to make the same promises. In other words, don't try to accomplish by force what we can accomplish with less risk by persuasion.

@wycats
Copy link
Contributor

@wycats wycats commented Apr 12, 2016

And it's my current strategy for bridging from non-TCO to TCO

Just so I'm sure I'm understanding, you mean PTC ("guaranteed TCO") not "more TCO in general" right?

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 12, 2016

Interop is about how actual implementations match and how well they run code that exists.

This is the crux of our argument.

As far as I am aware there is no actual interop concern with regard to tail calls as tail calls are not implemented interoperably in browsers and will not be for some time. It is possible (and has occurred before) that a change to a ratified specification results in more interoperability rather than less. See for example myriad changes to functions in sloppy mode or removal of Proxy's enumerate trap (something Edge had already shipped).

Our point is that the proposed change would decrease interoperability. Some implementations will do implicit PTC and eventually all will do Syntactic Tail Calls (STC). But as @getify points out, feature testing for either difficult and kludgy at best. Adding STC complicates matters as both PTC and STC would need to be tested.

Can you clarify what websites that exist today or in the near future would break as a result of adopting a proposal like (1)?

There are no known websites that would break with proposal (1), optional PTC + future STC. There are also no known current websites that will break with ES6 PTC alone. My point is that one can easily envision a website written to take advantage of PTC that would break without them. Remember that the PTC feature was added to enable a pattern that doesn't work today. Part of the objection to (1) is that future cross browser compatibility could force WebKit/JavaScriptCore to eliminate PTC and only support STC. In the process we break websites written assuming PTC.

An implementation can do implicit tail calls without violating the spec, though I agree developers would not choose to rely on the implicit tail calls as there is no guarantee they will work. That's exactly the case they're in today and will be until they can support only browsers that support tail calls.

A spec compliant implementation would need to support PTC. Without broad support across major browsers, we introduce confusion that @getify points out.

@getify
Copy link
Contributor

@getify getify commented Apr 12, 2016

you mean PTC ("guaranteed TCO") not "more TCO in general" right?

Yes, sorry for the imprecise wording.

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 12, 2016

@getify let's try to keep this thread focused on Apple's objections to hearing proposals that alleviate other implementers' concerns.

I think these comments are focused on our objection. Developers do not have a way to feature test support for PTC. In my opinion, the addition of STC doesn't make things better, it makes them worse.

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 12, 2016

There's something I'm trying to understand about this conversation:

"Proper Tail Calls" is the feature that is included in the ES2015 spec. It specifies a list of productions and requires engines to implement those productions as tail calls.

"Tail Call Optimization" is an alternative that opportunistically implements certain productions as tail calls, but offers no guarantees about when it happens.

What we are talking about here is "Proper Tail Calls" (PTC).

In addition, if we define an explicit syntax for PTC, that means that we, TC39, commit to keeping PTC in our critical path, and should avoid us regressing on engines that want to make an additional promise of PTC in the absence of an explicit opt-in.

At that March '16 meeting, TC39 agreed to support PTC. The problem is that the adoption of STC coupled with changing PTC from normative to optional will likely necessitate that Safari and other WebKit based implementations will need to change to follow what other implementations do. If the optional behavior is only implemented by Safari, it will likely be problematic to be different than other browsers. In the process we will likely break web pages and applications written between now and then.

@wycats
Copy link
Contributor

@wycats wycats commented Apr 12, 2016

At that March '16 meeting, TC39 agreed to support PTC. The problem is that the adoption of STC coupled with changing PTC from normative to optional will likely necessitate that Safari and other WebKit based implementations will need to change to follow what other implementations do. If the optional behavior is only implemented by Safari, it will likely be problematic to be different than other browsers. In the process we will likely break web pages and applications written between now and then.

Can you explain why Safari will feel that it needs to remove an optimization (TCO) simply because it's optional, and why Safari would not be able to make a strong claim to developers that on Safari PTC is guaranteed?

@allenwb
Copy link
Member

@allenwb allenwb commented Apr 12, 2016

Before we pour too much energy into this we should remember that PTC is in the ECMAScript specification because there was consensus among all the TC39 members to included it. To remove it would require a similar consensus. Is there any chance of TC39 getting such a consensus in the short term? Based upon may recollection of the March meeting discussion and this (and related) threats we seem to be far from having a removal consensus or any other concrete proposal for changing PTC portions of the language specification.

Perhaps our energy would be better spent on helping concerned implementors understand how they can successfully (and economically) deal with the standard as it currently exists.

(and regarding optional TCO, PTC is in the spec. because we (the TC39 delegates) know that JS programmers could not interoperably depend upon optional TCO and that we could not depend upon all implementation to bother implementing such an optional feature. We know there would be implementation push back and that is why it was specified as PTC and not TCO. We should not fold on this point with the first push back. Rather we should let this play out in the market for as long as it takes to resolve itself.)

@bterlson
Copy link
Member

@bterlson bterlson commented Apr 12, 2016

I think these comments are focused on our objection. Developers do not have a way to feature test support for PTC. In my opinion, the addition of STC doesn't make things better, it makes them worse.

Sorry, I did not get that from your original post, and I was trying to keep the conversation focused. In that case, can you elaborate on how STC makes feature detection harder?

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 12, 2016

Can you explain why Safari will feel that it needs to remove an optimization (TCO) simply because it's optional, and why Safari would not be able to make a strong claim to developers that on Safari PTC is guaranteed?

We are not talking about removing an optimization (TCO) we are talking about removing Proper Tail Calls (PTC). What the JavaScriptCore team has implemented is ES6 compliant PTC. Whether or not we or any web developer considers it also an optimization is moot and immaterial for this discussion.

I think I outlined in the initial post why we might feel compelled to eliminate PTC at some point after STC are implemented.

@wycats
Copy link
Contributor

@wycats wycats commented Apr 12, 2016

We are not talking about removing an optimization (TCO) we are talking about removing Proper Tail Calls (PTC).

We are talking about making TCO optional without an explicit opt-in. We are not talking about disallowing PTC.

What the JavaScriptCore team has implemented is ES6 compliant PTC.

Yes. That is true.

Whether or not we or any web developer considers it also an optimization is moot and immaterial for this discussion.

Can you please explain why JSC would feel that they need to remove their PTC implementation if other engines did not implement PTC?

Concretely, what are the interop concerns?

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 12, 2016

I think these comments are focused on our objection. Developers do not have a way to feature test support for PTC. In my opinion, the addition of STC doesn't make things better, it makes them worse.

Sorry, I did not get that from your original post, and I was trying to keep the conversation focused. In that case, can you elaborate on how STC makes feature detection harder?

During various TC-39 discussion, it has been made clear the there should never be the need for feature testing Spec'ed ES normative behavior. In ES6 (and draft ES7) PTC are normative. If a future version of ES made currently normative PTC optional, then developers need a PTC feature test. That is what proposal (1) would do, add the need for a PTC feature test. About the best way to feature test for PTC is to overflow the stack and catch. Note that the kangax ES 6 compatibility webpage makes recursive calls 1 million levels deep to feature test for PTC a total of three times. The kangax method is too simplistic as a browser might increase their stack size for other reasons. Having written an out-of-stack corner case test, I can tell you it takes some time to execute and a straightforward implementation would block execution during detection. There would be a brief growth industry for developers to write the best PTC feature test. Some of these feature tests might trigger latent bugs in various browsers.

The STC proposal could be amended to include a feature test capability, but it is my sense that there wouldn't be TC-39 committee support for such an amendment. Certainly adding a PTC feature test to a future version of ES, when PTC were made optional, seems problematic and would require developer rework of ES6 compliant web applications.

As @getify points out above, having STC doesn't solve the feature test, as an implementation may implement the syntax without making a true tail call. Eval'ing some code to see if is throws a SyntaxError seems a little weird to check for the absence of a feature. Yet it may not be sufficient to indicate an implementation supports STC. To be complete one might need / want to test that both PTC and STC actually make a true tail call. All 4 combinations could exist in deployed browser implementations.

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 12, 2016

We are not talking about removing an optimization (TCO) we are talking about removing Proper Tail Calls (PTC).

We are talking about making TCO optional without an explicit opt-in. We are not talking about disallowing PTC.

Let's be very clear what we are talking about here. PTC are required for ES6 compliance. Some implementations are not planning on implementing PTC. Instead they are proposing the addition of STC and make PTC optional.

Neither I nor do I think those proposing STC are talking about TCO. The ES6 spec only talks about reusing stack space.

@getify
Copy link
Contributor

@getify getify commented Apr 12, 2016

Just a quick clarification question (especially since I'm already guilty in this thread of imprecise wording): PTC is an optimization, right, in the sense that it prevents growth of the stack as the calls pile up? I am guilty of not really understanding the extent that TCO is different from PTC. In other words, proper tail calls, from a grammatical standpoint, seem irrelevant/pointless if they aren't implying the constant-stack-size thing on such calls, and that is the optimization I have in mind when I say TCO. So what additional optimization am I missing that TCO implies that PTC does not?

@allenwb
Copy link
Member

@allenwb allenwb commented Apr 12, 2016

@getify no PTC is not an optimization. It is instead part of the required semantics of certain calls.

An "optimization" is generally something unobservable (ie, semantic preserving) that an implementation might (ie, optionally) do to to enhance performance or some other interesting metric. That difference between PTC and TCO is that PTC is required (and observable) semantics. TCO is just an optimization (assuming that you don't consider stack overflow on unbounded recursion part of the semantics of call)

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 13, 2016

Just a quick clarification question .... So what additional optimization am I missing that TCO implies that PTC does not?

Proper Tail Calls as specified in ES6 only require reusing stack space. A Tail Call Optimization might also use different instructions to make and/or return from a call. It might have different prologue / epilogue code that would eliminate the saving and restoring of registers. Argument count and type checking code might be bypassed when tail calling to the same function. A good compiler could turn a tail call to self into a loop. As @allenwb says, these are unobservable performance enhancements beyond the observable stack space reuse.

@getify
Copy link
Contributor

@getify getify commented Apr 13, 2016

@allenwb @msaboff thanks for the clarifications.

@bterlson
Copy link
Member

@bterlson bterlson commented Apr 13, 2016

During various TC-39 discussion, it has been made clear the there should never be the need for feature testing Spec'ed ES normative behavior

I don't believe this is true - in fact, it seems like the opposite to me. Can you elaborate or link to notes?

I still am missing something critical here, though, so please forgive me. I don't understand how feature detection with PTC is easier than with STC. Scenario: I'm a dev who wants to use either my PTC/STC-dependent algorithm or a less efficient one (possibly transpiled). Basically only option with PTC is recurse a bunch of times and look for an error, unreliable as you say. If we have STC, the situation is at most just as bad, but can be made easier by taking advantage of the fact that no one will actually ship a browser with STC syntax but without STC semantics. Testing for syntax seems like a very easy litmus test that will be valuable in practice. Thoughts?

@getify
Copy link
Contributor

@getify getify commented Apr 13, 2016

no one will actually ship a browser with STC syntax but without STC semantics

So you say, but I don't think there's anything that developers could actually rely on there. For example, the Mozilla folks might not want to honor a STC on a cross-realm call. AFAIK, the jury is still out on whether that case would cause an affirmative catchable error or just a warning. If it turns out to be a warning, for example, then a developer may not be able to rely on just a general feature test for STC as they'd need to check specific STC cases in tests.

Also, IIUC, a call-site may possibly not obviously look cross-realm but actually be cross-realm, so developers would have to be a lot more careful about the assumptions they make from FTs.

Bottom line, introducing STC alongside PTC would, in general, lead to the need to test both. I think that was @msaboff's point (at least I hope I got it right).

@bterlson
Copy link
Member

@bterlson bterlson commented Apr 13, 2016

In a world where Mozilla ships with just a warning, a library author that wants to feature detect the presence of STC has two options: 1, simply test syntax and not explicitly support cross realm calls (very reasonable, cross realm calls are in practice very rare today, and not something developers typically code defensively against as there are other complexities involved), or 2) do exactly what you have to do today with PTC and actually set up a cross-realm call chain and see what happens. So unless I'm missing something (probably am), at worst STC seems as bad as PTC for feature detection, but at best allows a very simple feature detection method that will in practice work for most people.

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented Apr 13, 2016

During various TC-39 discussion, it has been made clear the there should never be the need for feature testing Spec'ed ES normative behavior

I don't believe this is true - in fact, it seems like the opposite to me. Can you elaborate or link to notes?

I don't know if it is in the notes, but I suggested at one point feature testing some other feature and the response was that the committee wasn't going to go back to that kind of world. Besides, normative behavior doesn't need a feature test.

I still am missing something critical here, though, so please forgive me. I don't understand how feature detection with PTC is easier than with STC. Scenario: I'm a dev who wants to use either my PTC/STC-dependent algorithm or a less efficient one (possibly transpiled). Basically only option with PTC is recurse a bunch of times and look for an error, unreliable as you say. If we have STC, the situation is at most just as bad, but can be made easier by taking advantage of the fact that no one will actually ship a browser with STC syntax but without STC semantics. Testing for syntax seems like a very easy litmus test that will be valuable in practice. Thoughts?

Feature testing for PTC or STC would be about the same if a developer wanted to make sure that each really made the tail calls they expected. Having to feature test for both and deciding what to do based on the combinations complicates things. Consider Safari version N supports PTC but not STC. Later, version N+1 supports both PTC and STC. It is likely that other browsers will support only STC. At some point, good web apps will need to check for PTC and STC, and select among three broad code paths. This seems unruly for developers. That's one way that STC makes tail call feature testing more complicated. Given this complexity, a developer decides to only checks STC syntax and drops their PTC check and corresponding path. The result is that we'll lose out for users with Safari N due to the complexity of checking and coding for both PTC and STC.

@bterlson
Copy link
Member

@bterlson bterlson commented Apr 13, 2016

Besides, normative behavior doesn't need a feature test.

Maybe we're talking about different things. Feature detection is most frequently used to detect whether an implementation supports some normative behavior so that they can, for eg., use built-in WeakMap when available, otherwise a polyfill.

I see what you are saying now about the difficulty, though! I was comparing the cost of STC by itself rather than in addition to PTC.

@rossberg
Copy link
Member

@rossberg rossberg commented Apr 13, 2016

On 13 April 2016 at 01:30, Michael Saboff notifications@github.com wrote:

We are not talking about removing an optimization (TCO) we are talking
about removing Proper Tail Calls (PTC).

We are talking about making TCO optional without an explicit opt-in. We
are not talking about disallowing PTC.

Let's be very clear what we are talking about here. PTC are required for
ES6 compliance. Some implementations are not planning on implementing PTC.
Instead they are proposing the addition of STC and make PTC optional.

Note that TC39 agreed to adopt the "train model", or the "living spec".
That is, we continuously improve the spec, and only put stamps on it once a
year, mainly for bureaucratic reasons.

One side effect of this is that we do not do errata anymore. If we find
problems with a version of the spec, we just fix it in the next one. We
have done so before, see e.g. the changes around proxies or local functions.

In the old world, we might have put changes like the one under discussion
into the erratum category, but we got rid of that device, under the
assumption that everybody agreed to the above model.

I don't see the interop issue or any complication with feature testing if
we replace PTC with STC -- quite the opposite, in fact. The only way we
could practically get into a situation is if some browser shipped a
semantics before we have resolved this discussion. That's why Chrome has
pulled PTC from v51, although it was ready.

@allenwb, agreed with your description of the past, but as we all know, the
ES6 proposal process was utterly inadequate. By the current process,
several of the features in the current spec (and that includes tail calls)
would barely be at stage 3. So I think there is no shame in taking some
liberty to revisit some of the decisions where it is not too late.

@getify
Copy link
Contributor

@getify getify commented Apr 13, 2016

@rossberg-chromium There is already production code (which I wrote) that is expecting eventually for PTC to "optimize" (aka improve the efficiency of) it. If I thought of that adaptive pattern (see above), there's a chance others have too, and I imagine it would be difficult to find in code searches. This is not a zero-cost change to revisit and do away with PTC in favor of STC more than a year after the spec was finalized.

A change from PTC to STC means that one cannot feasibly write adaptive recursive code the way I've suggested that merely progressively enhances once a browser lands the support. It means that the code in question absolutely has to be changed (and I'm not on that project anymore). Either that code path will have to be forked, with some sort of hard feature-test to select the STC or the non-recursive, or it has to be made entirely un-recursive until some magical future date when all supported browsers have STC.

That is a much less friendly path to migration to tail calls. If your usual "cost models" only involve looking at existing deployed code that will break, I would suggest you also have to consider the additional migration cost of syntax-annotated versus implied "optimization".

@bterlson
Copy link
Member

@bterlson bterlson commented Apr 13, 2016

I don't see the interop issue or any complication with feature testing if we replace PTC with STC -- quite the opposite, in fact. The only way we could practically get into a situation is if some browser shipped a semantics before we have resolved this discussion.

Yeah that's the part I was having trouble understanding as well. @msaboff is Safari shipping imminently with PTC enabled?

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented May 5, 2016

Since much of this discussion is based on assumptions with very little data, I decided to instrument JSC and see what happens on real webpages. I added compile time and runtime counters, basically to determine what percent of calls end up as PTC at compile time and then determine what percent of actual calls are PTC versus normal calls. The runtime result fit my gut instinct at ~5%. The percent of calls that get compiled to PTC surprised me on the low side, typically much less than 1%. I did not include true constructor calls in the data.

I performed 2 broad tests, first loading the top ~1000 Alexa sites, and then navigating specific sites that are high on the Alexa list that I could access without an account or with my own account. First the Alexa data, with raw numbers:

At compile time there were 6,683,375 calls of which 24,393 where PTCs (0.36%). While executing, 179,610,729 calls were made of which 8,396,396 where PTCs (4.67%).

Here is summary data for the specific sites:

site compiled PTCs actual PTCs
google.com 0.24% 4.14%
facebook.com 2.14% 4.93%
youtube.com 0.06% 0.90%.
wikipedia.org 0.90% 3.54%
amazon.com 0.12% 1.39%
ebay.com 0.19% 6.08%
paypal.com 0.66% 0.19%
apple.com 0.20% 3.30%

For sake of discussion, let's summarize this data with about .4% of calls in javascript source in the wild will be PTC's. At runtime, these paths seem to be more prominent and account for ~5% of actual paths.
There are several things this data says to me:

  1. Very little code, less than .4%, are PTCs.
  2. PTCs occur along paths that are somewhat common as those paths are 10x likely to get executed.
  3. Given items 1. and 2., it would seem to me that PTCs exist in some common javascript libraries. If this is true, then the debugging and telemetry issue are much more localized.
  4. Performance concerns are not as much of an issue given that only 5% of actual calls are PTCs. If a browser's PTC implementation is 10% slower that a standard call, that will only have a .5% impact overall on the typical webpage.
  5. The STC tax discussed earlier appears to have a higher price in that we will require programmers to opt in to tail calls to mitigate an issue in .4% of the current source. Seems like a high price to pay for an arguable small problem. Even considering the facebook.com data, the source prevalence of PTC's for that site is ~2%.
@littledan
Copy link
Member

@littledan littledan commented May 5, 2016

@msaboff Thanks for collecting this data. Interesting to see that less frequently called code does fewer tail calls.

4+% of runtime calls sounds like plenty of calls to me, and I would be concerned about losing nearly 1 in 20 stack frames for debugging. This seems to confirm my fears.

@littledan
Copy link
Member

@littledan littledan commented May 5, 2016

About point 5., I don't think any of the existing calls should be changed to make a tail call. Instead, STC should be used in new code which wants to take advantage of a feature which was not previously present at all, which is to allow tail-recursive loops without very low restrictions on the number of the number of iterations. STC and PTC are not performance features; it is important that we document this for users.

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented May 5, 2016

About point 5., I don't think any of the existing calls should be changed to make a tail call. Instead, STC should be used in new code which wants to take advantage of a feature which was not previously present at all, which is to allow tail-recursive loops without very low restrictions on the number of the number of iterations. STC and PTC are not performance features; it is important that we document this for users.

My point is that because there are concerns that PTCs will cause issues, it is suggested that we introduce STCs. I have no expectation that programmers will go back and add the appropriate syntax for STC at any of the current PTC sites. In fact given that they'll most likely want their code to run on older browsers, I expect that number to be close to 0. If we abandon PTC in favor of STC though, every programmer that wants to use tail calls must add whatever syntax STC requires specifically because we are worried about the .4% of PTCs in source code today. That is a high future tax for an arguable a small problem today.

@jeffmo
Copy link
Member

@jeffmo jeffmo commented May 5, 2016

I have no expectation that programmers will go back and add the appropriate syntax for STC at any of the current PTC sites

I think this is a source of the disagreement: The notion that any calls that exist in tail position today will necessarily benefit from being picked up as a PTC tomorrow.

I suspect proponents of the STC proposal would argue that, because no code today needs PTC, there is little benefit (and clearly a change in semantics) to retroactively instituting it for that code. Moreover, the basis of the STC proposal seems to be that tail calls are only meant to be intentional and shouldn't be accidental -- thus retrofitting the behavior into existing code is really a non-goal.

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented May 6, 2016

After discussion with colleagues and some reflection, I'd like to add a couple more points that I believe are relevant to this thread.

  1. Given the data says there is a 10x likelihood that a current PTC gets called compared to a standard call, we suspect that the majority of those PTCs are commonly called wrapper or forwarding functions.
  2. Typically telemetry systems match the top one to few stack frames, and only rarely if ever depend on the rest of the stack for anything, since a bug in a function can be triggered by multiple different call sites. Are there any known examples of telemetry systems that depend on matching the whole call stack?
  3. Telemetry systems already bucket by browser since some errors are particular to specific browsers, some expected API invocations differ between browsers, and error.stack formatting differs across browsers. So, it doesn’t matter if new browsers elide frames that old browsers included — telemetry systems will be self-consistent within browsers versions as they always have needed to be.

Taken together the data would suggest that the impact of current in the wild PTCs on telemetry systems would be quite low.

@concavelenz
Copy link

@concavelenz concavelenz commented May 6, 2016

RE: 1. PTC doesn't dictate that the method is trivial.

A method could easily end with trivial check and the interesting method would be lost.

return ThrowIfNullOrUndefined(result);

RE: 2. The interesting data can be arbitrarily deep. Often we see 4 or 5 frames of logging infrastructure.

RE: 3. That different browser report different frames isn't particularly important, but that interesting frames are lost is the issue. PTC requires that you "get lucky" to preserve the correct stack frames.

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented May 6, 2016

RE: 1. PTC doesn't dictate that the method is trivial.

Of course. I wrote that I speculated that the PTC calling methods are wrappers.

RE: 3. That different browser report different frames isn't particularly important, but that interesting frames are lost is the issue. PTC requires that you "get lucky" to preserve the correct stack frames.

Since the frames lost are PTC callers, they don't contain the reporting code, but are on the path to the reporting code. IF they are wrapper functions, losing those frames from the stack trace is a very small lose of information.

@concavelenz
Copy link

@concavelenz concavelenz commented May 10, 2016

I meant to ask, if you are only count "strict" code where PTC is active or
if you are counting non-strict code.

On Fri, May 6, 2016 at 3:26 PM, Michael Saboff notifications@github.com
wrote:

RE: 1. PTC doesn't dictate that the method is trivial.

Of course. I wrote that I speculated that the PTC calling methods are
wrappers.

Right, and I'm stating I don't believe there is any reason to believe that.

RE: 3. That different browser report different frames isn't particularly
important, but that interesting frames are lost is the issue. PTC requires
that you "get lucky" to preserve the correct stack frames.

Since the frames lost are PTC callers, they don't contain the reporting
code, but are on the path to the reporting code. IF they are wrapper
functions, losing those frames from the stack trace is a very small lose of
information.

I think we are using different meanings of "reporting". Here I mean the
path to the function that is causing the stack trace to be collected, which
may not be source of the "error" but just some bit of the logging
infrastructure:

function report(msg) {
var record = createReportRecord(msg); // add a stack trace
sendReport(record);
}

function doStuff() {
...
if (...) {
...
return result;
}
report("failed")
}


You are receiving this because you commented.
Reply to this email directly or view it on GitHub
#535 (comment)

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented May 10, 2016

I meant to ask, if you are only count "strict" code where PTC is active or
if you are counting non-strict code.

I counted all code. I wanted to measure how common PTC are across all web pages.

As far as likelihood of a PTC being elided from a stack trace that gets reported via telemetry, you and I are both speculating. Maybe we can agree that ~5% of frames will not appear in the stack trace. As far as what those elided functions look like, we don't know without further investigation.

@bterlson
Copy link
Member

@bterlson bterlson commented May 10, 2016

@msaboff Do you know what percent of calls are syntactically tail calls but not only due to containing code being sloppy?

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented May 10, 2016

Do you know what percent of calls are syntactically tail calls but not only due to containing code being sloppy?

I do not. I put my compile counters at the point where the parser is issuing a call byte code, which is after where we've determined whether or not it is a PTC and for your question WHY we determined it is or isn't a PTC.

@littledan
Copy link
Member

@littledan littledan commented May 10, 2016

Seems like we might expect this number to increase a bit over time as strict mode usage increases.

@bterlson
Copy link
Member

@bterlson bterlson commented May 10, 2016

Either a bit or a lot, maybe, depending on how prevalent strict mode is today. I haven't seen numbers for a couple years, but last I checked sloppy was by far the most prevalent mode.

@claudepache
Copy link
Contributor

@claudepache claudepache commented May 11, 2016

There is a fear that useful debugging info (stack trace report) would be degraded with PTC. The fear is valid, but pushing back PTC as possible remedy looks backwards. Since the issue is with stack trace, not with PTC per se, stack trace should be improved rather than PTC degraded.

For example, I imagine that a given stack frame could keep track, for debugging purpose, not only of the function that is currently using the frame, but also of the first function that used it (the one whose call induced the creation of the frame), and of the number of PTC that has occurred for that frame. Then, experience would show if more debugging info is needed.

@rossberg
Copy link
Member

@rossberg rossberg commented May 11, 2016

@claudepache, TCE doesn't mean reusing stack frames, if that's what you're thinking. That wouldn't be possible in most cases, because functions differ in their number of arguments, of local variables, calling conventions, or even general stack frame layouts, e.g. in the presence of different optimisation tiers. You can even tail-call functions that are not JavaScript at all, and vice versa.

What a tail call generally does is removing the current stack frame before it performs an ordinary call. The reuse you imagine is a possible optimisation in only a few special cases (mostly self recursion).

@bterlson
Copy link
Member

@bterlson bterlson commented May 11, 2016

I found the data I alluded to above (see my presentation): http://wiki.ecmascript.org/doku.php?id=meetings:meeting_jan_29_2013. In early 2013 I found that only ~4% of sites contained some strict code. I suspect this has increased lately but I'm not sure how much.

@msaboff it would be really helpful to know what percent of strict calls are also tail calls if you can find out somehow :)

@saambarati
Copy link

@saambarati saambarati commented May 13, 2016

@claudepache @rossberg-chromium Regardless of the mechanism used to accomplish this, there are methods for keeping around the interesting bits of the stack in a world with tail calls. I.e, keeping the top X frames when the debugger is enabled.
This will solve almost every interesting debugging scenario in a world with tail calls:
-- Your program is not written with PTC in mind and is not knowingly using PTC.
This means that in any given stack trace, there will be very few frames that would have
been elided because of tail calls. This means that smart debugger integration will show
all those frames that would have been elided because it will almost always be less than X.
-- Your program is written to take advantage of PTC and will have many loops written using
recursion. In such a scenario, the debugger will show you the top X tail called frames (along
with the rest of the not tail-call elided frames). This is almost always a good solution because
the most interesting frame is the top frame. All other X - 1 frames are just nice to have. And sometimes,
having these frames will just cause clutter. It's not obvious that a program written to utilize PTC
that has a loop written as recursion will always want to see X iterations of the loop in the call
stack. It may even be beneficial to have the debugger intelligently compact frames that are
obviously part of a tail recursive loop.

@ljharb
Copy link
Member

@ljharb ljharb commented May 13, 2016

@saambarati what about the cases where one wants to introspect the stack frames at runtime, sans any debugger being present?

@msaboff
Copy link
Contributor Author

@msaboff msaboff commented May 17, 2016

it would be really helpful to know what percent of strict calls are also tail calls if you can find out somehow :)

@bterlson, I found the time to collect some "strict mode call" numbers. I added another counter at compile time. If we generate a "call" byte code and we are currently in strict mode, I bump the new counter. Again I ran the top 1100 Alexa sites and collected the data. I then went to a smaller set of individual pages, navigated around them and collected data for each of those sites.

For the Alexa tests, at compile time there were 7,703778 calls of which 28,906 were PTCs (0.38%). 716,931 of all calls where found in strict code (9.31% of all calls are strict and 4.03% of strict calls are PTC). While executing, 161,758,015 calls were made of which 8,194,931 where PTCs (5.07%).

For the individual sites I navigated, my process was less scientific. I didn't record how I navigated around each site the first time, so I likely hit different paths this time. Here is summary data for the specific sites:

site compiled PTCs compiled strict strict that are PTC actual PTCs
google.com 0.13% 9.31% 6.58% 3.91%
facebook.com 2.01% 41.07% 4.90% 4.86%
ebay.com 0.21% 6.59% 3.13% 4.93%
paypal.com 0.53% 19.93% 2.68% 2.46%
apple.com 0.26% 6.18% 4.25% 3.90%

Facebook and PayPal for the win on using strict mode!

It is interesting to note that in most cases the incidence of PTC in strict source is fairly close to the percent of actually called PTC. For the Alexa run, 4% of compiled strict calls are PTC while at run time 5% of calls are PTC.

@concavelenz
Copy link

@concavelenz concavelenz commented May 19, 2016

Thanks for getting some numbers regarding strict mode. But I'm not really
sure what conclusions I can draw from these updated numbers.

As an FYI, plus.google.com (not classic) and photos.google.com should be
almost entirely strict. In contrast, I'm surprised google.com has any
strict code.

@hax
Copy link
Member

@hax hax commented Dec 12, 2016

Any conclusion?

@YurySolovyov
Copy link

@YurySolovyov YurySolovyov commented Nov 15, 2017

With Firefox launches like Electrolysis and Quantum, are there any changes with respect to Tail Calls ?
Asking because I remember sandbox or process model as the reason FF can't have Tail Calls

@hashseed
Copy link

@hashseed hashseed commented Nov 15, 2017

iiuc none of these affect SpiderMonkey, which iirc requires stack frames for security checks.

@enright
Copy link

@enright enright commented Jan 17, 2018

I write functional ES6 code that depends on proper tail call implementation according to the spec. Use my code in Node v6 with harmony flag...works fine. Use my code in Node v8...blows out the stack. This is stupid.

Why in the world should I have to put up with non-conformance? Are you kidding me?

@glathoud

This comment was marked as off-topic.

@glathoud

This comment was marked as off-topic.

@leobalter

This comment was marked as off-topic.

@glathoud

This comment was marked as off-topic.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
You can’t perform that action at this time.