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

Reviving proper tail calls? #23

Open
pygy opened this issue May 6, 2018 · 83 comments

Comments

@pygy
Copy link

@pygy pygy commented May 6, 2018

Hi all,

as much as some people love to hate Safari ("the new IE", yadda, yadda), I've yet to see a complain about their support for (implicit) proper tail calls in the wild. The debugging problems mentioned in this article seem to be non-issues in practice.

Maybe it is time to revisit the situation?

@pygy pygy changed the title Revivng proper tail calls? Reviving proper tail calls? May 6, 2018
@ljharb

This comment has been minimized.

Copy link
Member

@ljharb ljharb commented May 6, 2018

Since code using proper tail calls to avoid blowing the stack isn’t web-compatible, and would only work in Safari - which would imply that nobody is shipping it - how would you expect to see complaints about the implementation?

@Pauan

This comment has been minimized.

Copy link

@Pauan Pauan commented May 6, 2018

@ljharb Tail call optimization applies even if the programmer didn't intend for it to apply.

So let's say somebody debugged their code in Safari, and their debugging experience was fine (despite the unintended tail call optimization). Obviously they would not complain.

On the flip side, if somebody is debugging code in Safari and they experience weird behavior (such as call stacks being missing), then they would complain!

So the lack of complaints is (a little bit of) evidence that tail call optimization does not harm the debugging experience, and thus is acceptable to implement in other browsers as well.

@pygy

This comment has been minimized.

Copy link
Author

@pygy pygy commented May 6, 2018

I'd argue that, as far as debugging is concerned, accidentally optimized tail calls are the only ones that matter.

People who use them deliberately would not complain, they know what they are doing.

A third case would be someone who relies on a 3rd party library that uses tail calls internally. It may make it harder to debug said lib if it were buggy. If it is a real problem in practice, people will avoid such libs and give them a bad name (I'd be surprised if it happened though.)

@pygy

This comment has been minimized.

Copy link
Author

@pygy pygy commented May 6, 2018

Another thing I see raised against proper tail calls is perf issues.

They can be made fast in LuaJIT where the equivalent of

function _while(condition, body) {
  if (condition() && !body()) { // return true in the body to break
    return _while(condition, body);
  }
}

let a = 0;
_while(()=> a < 1000000000, () => {a++});
console.log(a);

is as fast as a

let a = 0;
while (a < 1000000000) a++;
console.log(a);

(and that has been the case since 2010).

What does JS have that makes the code above impossible to optimize?

Edit: FWIW, Safari is almost as good as LuaJIT here.

while 100000000 394 msec
_while() 100000000 526 msec

Putting both benchmarks in the same tick has the plain while loop slower than the functional version.

while 100000000 873
_while() 100000000 503

Edit2: well LuaJIT has both versions at 150 ms, actually :-) But still, the overhead of the functional verison over the plain loop is rather small in Safari.

@getify

This comment has been minimized.

Copy link

@getify getify commented May 6, 2018

@ljharb as I've pointed out multiple times, including in #4, tail calls are not web-incompatible. I have code shipped in production (that I wrote years ago) using that "adaptive" pattern, which ostensibly is working fine (as far as I know anyway) in non-PTC browsers, and in Safari has "progressively enhanced" to using tail calls.

Whether that pattern is common or not is a separate discussion. It is in fact web compatible and should therefore not be continually dismissed on such grounds.

@getify

This comment has been minimized.

Copy link

@getify getify commented May 6, 2018

Also, @Pauan is correct here:

Tail call optimization applies even if the programmer didn't intend for it to apply.

There must be tons of code (especially non-recursive) out in the wild that is unintentionally being tail-call'd by Safari. One would have to assume that if tail calls were such a problem (either for performance or debugging), then surely by now enough of a complaint would have been raised in the community as backlash against Safari, we'd certainly know it.

I'm not aware of any such backlash against Safari, and they clearly haven't changed their minds to back it out. More than a year in production strongly suggests the resistance to PTC was at least partially FUD and not grounded in fact.

@pygy

This comment has been minimized.

Copy link
Author

@pygy pygy commented May 6, 2018

@getify you phrased it better than I did, and I too think that the resistance is misguided, but I'd avoid throwing arounds terms like "FUD" (which I associate with wilful disinformation), it will not help our cause.

@ljharb

This comment has been minimized.

Copy link
Member

@ljharb ljharb commented May 7, 2018

@getify your code is not "web compatible PTC code". It's specifically web-incompatible PTC code, combined with a fallback mechanism to the true web-compatible code.

By saying PTC is not web compatible, I'm not saying that you can't write code that utilizes PTC. I'm saying that PTC code without a fallback is web incompatible.

The resistance to PTC is not solely based on debugging concerns; there's also the education aspect of implicit tail calls having magic behavior, but also, there's implementation concerns, where at least one of the major browsers is unable to implement PTC at all.

@getify

This comment has been minimized.

Copy link

@getify getify commented May 7, 2018

@ljharb seems like nitpicking on words. you used "not web compatible" as an excuse to dismiss the possibility that anyone may have deployed PTC code (or something demonstrably like it) and thus that was the reason for "silence" in terms of complaints.

Not only is my code pattern a counter-example that excepts that reasoning, but you also don't account for web code that's affirmatively using PTC (for recursion or otherwise) but is deployed in a safari-only way, such as in web views in iOS apps.

I still maintain your reasoning is faulty, no matter what label we bikeshed on to label it.

@pygy

This comment has been minimized.

Copy link
Author

@pygy pygy commented May 7, 2018

@ljharb I'm surprised that the architecture of one of the VMs is incompatible with PTC.

I'm going to suppose it is Edge we're talking about, since Brendand Eich had started working on the Firefox implementation (I assume he had a general idea of the path forward when he wrote the parser patch), and V8 had it done before it was unshipped.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented May 7, 2018

TL;DR: +1, but with some more details:

  1. First of all: I completely agree with the point of this issue. It's even better than splitting the fine hair splittage of what's proper web code or not. The bottom line is that JS code cannot for the most part rely on tail calls for "random web stuff", so the safari move would get developers no real benefits due to portability, but it would get them into the diminished debugging experience that many people are afraid of. The fact that people did not complain is a good indicator that these fears are unfounded.

  2. I have said in the past that of all languages, JS should be extremely ready for having tail call elimination (even under a misguided "PTC" name...) -- a quick way to see this is the fact that JS programmers are notoriously using callback-rich code, as well as being comfortable with tricks like deferring code to a timeout which essentially destroys the stack context it originally has. Yet even JS developers are worried about the bad effects on debugging.

  3. I think that "FUD" is a very peroper term to use here. There are no hard facts about debugging problems so people are definitely left with uncertainty, there is definitely a fear of hurting productivity as a result, and the very existence of the idea in this repo or the pulling-out of tail call elimination from v8 are making it clear that there is no shortage of doubts. It's not FUD that is actively encouraged by some company, but I think that it is FUD.

  4. To make this a bit more concrete: see this reply in that v8 thread as a perfect example of the FUD effect, and later on the same person goes on to conclude that tail calls "kill debugging and profiling". And this is coming from a person who self-identified as someone who's working on DevTools.

    These are exactly the claims that would anticipate some developer backlash against an implementation. Apparently in the safari case such backlash didn't happen, so it looks like "kills debugging and profiling" is much exaggerated.

  5. As a side note, I seriously hope that this proposal for an explicit syntax will die. The thing about tail calls is that they are something that affects control flow, and as such there could be issues that are a result of using some 3rd-party library with higher-order functions (ie, callbacks). The main point of making tail calls implicitly is that in most cases such libraries are fine as they are, without me asking the developers of such libraries to change their code (which, if the explicit syntax is used, will undoubtedly lead to redundant arguments with people who would refuse to make such changes worrying about hurting debugging).

@PinkaminaDianePie

This comment has been minimized.

Copy link

@PinkaminaDianePie PinkaminaDianePie commented May 7, 2018

Can it be implemented vice versa? Use proper TCO by default, and in case of greater need use some explicit keyword/expression/directive what else like debugger, which will deoptimize code and generate low-performance version, but with proper call stack? It would be much better to optimize by default and deoptimize on demand for debugging purposes only. Is it possible or such way also break some compatibility?

"education aspect" just makes me laugh, in that case, we can never add anything to standard because people will need to learn something, we should never create any new tools, libraries, frameworks etc, it will take an effort to learn them! In reality, anyone who will face with "broken" call stack will spend 30 seconds to read first entry from google search and will find solved question on StackOverflow with lots of links, and people who don't like to learn anything will still make mistakes like they do right now with any other language features. "some people won't like to learn something new" - it's totally not a valid reason to take it into consideration.

Only reason which can be valid, is the complexity of implementation in browser engines. But if it's not an issue - all other issues can be solved without introducing explicit keyword "optimize me please".

@getify

This comment has been minimized.

Copy link

@getify getify commented May 8, 2018

Can it be implemented vice versa?

I've thought about a similar path, too. For example, for any libs that want to collect (error).stack in the background, we could have a static boolean property like Error.stack to opt-in to full stack traces. This isn't really a deopt like stopping tail calls, but just indicating to the engine that the shadow stackframes should be collected. If it's not set, it's up to the engine if they want to collect, but if it's set the engine knows the page's code wants that data if possible so it should collect if it can.

For the open devtools use case, it could automatically set that same flag to trigger the same behavior.

@Othreumaru

This comment has been minimized.

Copy link

@Othreumaru Othreumaru commented May 10, 2018

TCO is just an optimization, stacktraces which are smaller in size than the limit of a stack in browsers which is usually few thousand may not be optimized at all, the optimization should imho trigger when the stack reaches this limit. At this point stack would be overflown anyway with exception. Usecases where TCO is useful are when code is running recursion over huge number of function calls something like billions or possibly infinity.

@getify

This comment has been minimized.

Copy link

@getify getify commented May 10, 2018

@Odrinwhite disagree. PTC (not necessarily TCO) is important even without recursion. Recursion is an obvious and acute use case but certainly not the only one.

I want (in FP) to make multiple wrapping layers of functions on top of functions, preserving parameters at each level, via closure, and I don't want there to be a deeper call stack as a result. In that perspective, function wrapping calls being exposed in the call stack is only extra noise for debugging and is thus a leaky implementation.

@Pauan

This comment has been minimized.

Copy link

@Pauan Pauan commented May 10, 2018

@Odrinwhite The strategy of "wait until the stack overflows and then activate TCO" is used in Chicken Scheme (and other compilers as well).

It is a valid way of implementing TCO, so browsers can use that implementation strategy if they wish.

But that has nothing to do with the spec: the spec does not specify how browsers achieve TCO, it merely mandates that they use some method of achieving TCO.

@getify That can be easily handled by having the browser record which frames are tail-call frames, so it can hide them from the debugger. So there's nothing stopping browsers from implementing the Chicken Scheme style of TCO. I doubt that browsers will actually do that, since there are downsides to it, but they could if they wanted to.

@getify

This comment has been minimized.

Copy link

@getify getify commented May 10, 2018

@Pauan of course, I don't only care about the debugger output... that was just one convenient illustration of a non-recursion use case.

What I actually want is all those wrapped FP functions to not actually cost function calls. And BTW, "cost" is not as much wanting to save CPU cycles in those calls, but wanting to minimize all the memory/GC churn of all those extra stack frame allocations/deallocations.

IMO the entire theory of FP rests on being able to assume there's no "penalty" (memory or otherwise) for an extra wrapping layer of function. In JS we just whistle along, merrily wrapping all these calls, and just winking and nodding to pretend it's OK... that what is conceptually one function call is actually 9 calls... because the cost of the extra 8 calls is generally still small so who cares?

But as soon as you wire up such a wrapped abstraction as a transducer, and hook that up to a continual stream of data events, each one firing every few hundred milliseconds, and run that on a user's mobile device for hours on end, you start wondering if FP is actually worth all that. memory burn.

I'm just trying ensure it's on record, because it seems all too easily lost/ignored/overlooked in these discussions, that the need for PTC goes well beyond recursion.

You can "solve" the lack of tail call recursion with a trampoline and even a code transform or macro... but you can't prevent all my extra function wrappings in FP from churning memory... unless you give me PTC.

Sorry I'm being so persistent/insistent in this thread. It's frankly quite frustrating to have spent basically 5 years campaigning for this vital feature and yet people still casually discount it as niche or suggest narrow work-arounds that aren't relevant to the broader perspective.

@Othreumaru

This comment has been minimized.

Copy link

@Othreumaru Othreumaru commented May 10, 2018

@getify Don't get me wrong I would like to see your version implemented but I think the argument that it breaks the web may be valid here for some people. And not breaking web was a big deal in designing ES6 so my proposition is to get the foot into the doors and allow people write TCO in some code which may not need to be very efficient but still fun to do. And with more people trying and using this style of programming a better or more aggressive solution can be established.

@PinkaminaDianePie

This comment has been minimized.

Copy link

@PinkaminaDianePie PinkaminaDianePie commented May 10, 2018

@Odrinwhite proper TCO doesn't break the web itself. Only some ways of implementation break it, and only in some cases. So instead of rejecting standard, it's better to find other ways of implementation, which will be acceptable. One proposal was to give developer possibility to deoptimize code on demand and see a proper stack trace. We will have proper TCO, developers will be able to check stack trace. Why not to go this way?

@Pauan

This comment has been minimized.

Copy link

@Pauan Pauan commented May 10, 2018

@getify What I actually want is all those wrapped FP functions to not actually cost function calls. And BTW, "cost" is not as much wanting to save CPU cycles in those calls, but wanting to minimize all the memory/GC churn of all those extra stack frame allocations/deallocations.

That is not guaranteed by the spec, the spec only guarantees amortized behavior. In general the spec doesn't say much about performance.

Also, stack allocations/deallocations are not the same as heap allocations: stack allocations are not managed by the garbage collector, and they are generally free (zero-cost). There is no performance penalty to using the stack.

Things get more complicated with JS, because browsers might have shadow stacks, or put additional information onto the stack/heap, etc. But the general principles of stack vs heap still applies.

Also, trying to guarantee no-extra-stack-frames-ever can actually make the performance worse, not better. Performance is complicated.

that what is conceptually one function call is actually 9 calls... because the cost of the extra 8 calls is generally still small so who cares?

That's not how Chicken Scheme works. It doesn't actually pay any performance penalty for the function calls.

It doesn't say "oh we'll create extra stack frames because the cost is low". Instead it says "we do normal function calls without any performance penalty, but then once in a while (when the stack overflows) we have to do garbage collection of the stack (which is slow, but not as slow as heap garbage collection)".

It's similar to how vectors/arrays work: when you insert elements into an array, most of the time it is extremely fast. But sometimes it has to resize the array, which is very slow. The idea is that because the resizing happens very rarely (usually exponentially rarely), it "averages out" to be very fast in practice. The same principle applies to hash tables. Amortized performance is extremely common.

I'm just trying ensure it's on record, because it seems all too easily lost/ignored/overlooked in these discussions, that the need for PTC goes well beyond recursion.

I agree with that: PTC is not merely an optimization, it is a feature of the language which enables new kinds of programs to be written (including, but not limited to: state machines, CPS transforming compilers, new flow control constructs, call-with-continuation, async code, etc.)


@Odrinwhite Don't get me wrong I would like to see your version implemented but I think the argument that it breaks the web may be valid here for some people.

As far as I can tell, TCO/PTC does not break the web, as indicated by Safari. The resistance to PTC is not about breaking the web, it is because PTC makes the JS engines more complicated, and it possibly has some performance penalties as well.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented May 19, 2018

It seems to me that it will be helpful to clarify the purpose of tail call elimination: the main goal is not to reduce runtime, but to reduce memory use --- and the actual stack frames are not the main concern there. When I write this code:

function foo(x) {
  let y = ...;
  return bar();
}

then having PTC means that when bar() is called I want to know that the x and y bindings no longer exists, and can be GCed.

[This is the main thing that Guido missed (or more likely chose to miss) in his shutting down of tail calls --- the example he uses makes it a requirement to keep x and y for debugging. So if the "imperative viewpoint" is to keep this information for the sake of debugging, then the "functional view" would raise an eyebrow and ask why is the old value of x after x = f(x) is not preserved by the same coin. (Or more practically, view saving these values as a debugger de-optimization.)

It's also interesting to see Guido's initial bottom line, "After all TRE only addresses recursion that can easily be replaced by a loop", is something that is clearly questionable to modern JS programmers (for example, trying to convert a tail-recursive promise loop into a while), and that's besides the added fragility of an imperative loop over using tail calls.]

@glathoud

This comment has been minimized.

Copy link

@glathoud glathoud commented Jun 25, 2018

Here is one possibility for developers to use fast tail calls today, without needing extra keywords in JavaScript: https://github.com/glathoud/fext

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Nov 4, 2018

+@douglascrockford

recent jslint versions have 2 tail-call "bugs" where it raises RangeError in certain cases in v8/nodejs/chrome (but not safari) [1], [2]. these bugs were closed by the author as "wont fix" (under assumption bugs will go away when engines eventually fall inline with ptc-spec).

will that assumption happen in the forseeable future? yes/no/maybe? an authoritative answer would provide clarity/guidance to development-roadmap of jslint.

[1] jslint-issue - RangeError when linting excessive leading-newlines
douglascrockford/JSLint#244

[2] jslint-issue - RangeError when linting json with large string-values
douglascrockford/JSLint#239

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Nov 4, 2018

oh also, firefox doesn't seem to have jslint tail-call issues under normal use-cases - because it has a ridiculously large callstack-depth limit (~100,000 vs. chrome's measly ~12,000). you can get these numbers by running the script below in the respective browser's console.

maybe a happy-medium/short-term solution is for v8/chakra to raise their callstack depth-limit to the same level as firefox?

function computeMaxCallStackSize() {
    try {
        return 1 + computeMaxCallStackSize();
    } catch (e) {
        // Call stack overflow
        return 1;
    }
}
computeMaxCallStackSize()

screen shot 2018-11-05 at 12 11 52 am

screen shot 2018-11-05 at 12 11 17 am

@slikts

This comment has been minimized.

Copy link

@slikts slikts commented Nov 4, 2018

Why would you use jslint, though.

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Nov 6, 2018

@slikts because eslint is too slow on the ultra-portable laptop i use while backpacking. javascript product-development should not follow java's model where the only reason you need powerful laptops (with poor battery-life) is because of bloated-tooling.

also i don't have strong feelings about PTC either way. i'm just unhappy that jslint is currently in a state thats not ideal for production-use, and wish its author and nodejs/tc39 can come to some compromise to resolve that. raising v8's stackcall-limit to firefox's seems like something reasonable to me.

@ljharb

This comment has been minimized.

Copy link
Member

@ljharb ljharb commented Nov 6, 2018

This repo isn’t the place to complain about, or seek change in, any of those things. jslint’s author by their own admission doesn’t care about web reality, only what’s in the spec; file a bug on Firefox if you want them to implement something; use something other than eslint if you like, just be aware that eslint is the de facto standard for “product-development” in the entire JS community.

While PTC is in the spec, STC (this proposal) is untenable, and there’s nothing of use to discuss here.

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Nov 6, 2018

@ljharb, my understanding is this thread is about PTC (not STC), and i'm bringing up a PTC issue in the wild.

@ljharb

This comment has been minimized.

Copy link
Member

@ljharb ljharb commented Nov 6, 2018

The thread is also not appropriate for this repo, since this entire repo is about removing PTC and replacing it with STC.

You’ll have to to take it up with each engine that has chosen not to ship PTC if you want PTC “revived”, or with the one engine that has if you want it removed.

@Pauan

This comment has been minimized.

Copy link

@Pauan Pauan commented Nov 9, 2018

@concavelenz I'm obviously not an expert on the Webkit code, but I took a glance over at their shadow stack implementation, and as far as I can see it is always enabled. However, that is an old patch, so maybe things have changed since then.

But I suspect they do have it always enabled, even with the devtools closed, otherwise Error.prototype.stack would break (which means we would have heard complaints about bad debugging on Safari).

It would be good to have some Safari/Webkit devs confirm whether it's always enabled or only selectively enabled.

As for the performance of shadow stacks, any claims about significant slowdown should be backed up by benchmarks proving that statement. Clearly Safari/Webkit isn't suffering from poor performance.

@PinkaminaDianePie

This comment has been minimized.

Copy link

@PinkaminaDianePie PinkaminaDianePie commented Nov 9, 2018

According to http://gs.statcounter.com Safari market share is about 15%. Have you seen a lot of bug reports from lib/framework developers? Website developers who collect stack traces? Do 15% of users have "broken web" experience? I can't actually decide for myself if it's funny or annoying to hear lots of times that PTC will break the web - 15% of users have PTC for months (or even years, I don't remember when it was shipped) and everything works for them. There is a way to implement PTC without performance loss and without "breaking the web", so it's not an excuse to refuse the standard. If browser vendors will do what they want and refuse standard even when it's clear that it can be implemented, we will return to IE times, when the web was broken just because every browser had its own set of features.

@concavelenz

This comment has been minimized.

Copy link

@concavelenz concavelenz commented Nov 10, 2018

(1) To be clear PTC only applies to strict mode code, it would break arguments.caller in non-strict code. A lot of the web today doesn't run 'strict'. So saying 15% is an great overestimate. PTC doesn't "break the web" (pages still render) but it does make maintaining complex application harder and for folks running servers on Node having lousy stack traces is a real concern. I personally remember when it was impossible to get stack traces and it wasn't pleasant.

(2) There is no reason to guess about the Safari behavior, it is simple to try out. If you do, it is easy to see the broken stacks with this snippet in Safari:

function f(a) {
  'use strict'
  if (a > 10) throw new Error();
  return f(a + 1);
}

try {
  f(0);
} catch (e) {
  alert('value = ' + e.stack)
}

You only see only the last call to f. If you remove 'use strict' and are not in a strict context (not in an ES6 class or es6 module or otherwise in a 'use strict' file, you will see the entire chain of calls leading to the exception.

(3) There were many changes to the ES2015 spec after it was released based on the feedback from the browser vendors and other implementors. The initial version had many problems, and they had to be resolved to create a compatible web. Saying "it is in the spec, you must do it" seems a weak argument to me when there are clear and reasonable objections.

(4) The spec is silent about the effects on the Error 'stack' property because it has never been standardized but it is critical to the code health of the ecosystem that it exists. This to me is the key problem with how PTC was added.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented Nov 12, 2018

@concavelenz: Your two point in (1) are greatly exaggerated. First, it is the market share of Safari (15% or whatever it is): if only 50% of "the web" is in non-strict mode, then it's half that, but it's also half the problem in Chrome. (In other words, the distribution of non-strict sites does not depend on the agent used.)

Second, I keep being amazed at these claims in the spirit of "lousy stack traces". This is really nowhere near the actual damage to developing that you get from no stack traces at all.

I'm probably repeating myself way too much, but here are a few points:

  1. You only lose tail calls that were eliminated --- these are in most cases part of some kind of a loop, and therefore having one frame is as good as having many. Your example is an instance of that.

  2. You currently lose the whole stack whenever you delay some code using a timer or something similar, yet this doesn't seem to be a deterrent for doing so. (E.g., I've seen many intro JS texts advocating setTimeout and friends, and none of them had some big warning saying "note that by doing so you lose stack information so development will be harder".)

  3. Another thing to consider here are profiler "flame graphs". I argue that these graphs will become better, since you will see more information immediately instead of indirectly. For example, consider A (non-tail) calling B, which does some work and (tail) calls itself 3 times. You will see one of these:

            {--B--}        
        {----B----}        
    {------B------}        {-B-}{-B-}{-B-}
    {------A------}        {------A------}
    

    I argue that the right visualization is more helpful. If A tail calls B, then it will be on the same level as the Bs and its length would be proportional to the actual work done in A --- which is, again, more useful.

  4. Practically the main objection is the Guido-style rejection based on losing information, to translate that example:

    if (somethingHoldsFor(x))
      return some_call(z);
    else
      return 42;
    

    But the flip side of this is that x is expensive (lots of memory, open file handle, etc): this is exactly the kind of things that tail call elimination gets you. (I have actually seen at least one place in Real Code where a similar problem lead to a weird-looking x = null before the call.)

  5. Finally, and most importantly, JS developers have already "discovered" the functional style, and they are using it heavily. I have seen multiple places where there's some use of a modern promise-based API that implements a "loop" which would have been a proper loop if only tail calls were mandated. Instead, such code should be converted to a form that uses some while loop and that is far from a natural or easy thing to do, and it is definitely something that makes "maintaining complex application harder".

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Nov 12, 2018

@elibarzilay, asynchronous recursion using callbacks/promises/generators/etc is O(1) with the [single] caller-frame discarded after the process-tick. PTC is irrelevant in this case.

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Nov 12, 2018

tbh, i'm slightly anti-PTC (but not strongly), because when troubleshooting hard-to-diagnose integration-level bugs, i'm paranoid about magic messing with stack-traces and screwing-up telemetry (regardless of assurances otherwise).

PTC doesn't add value to my personal use-cases for recursion which are exclusively either O(1) (async), or O(log(n)) (depth-first tree-traversals).

for O(n**constant), my personal preference is to use traditional loops.

for O(2**n), most use-cases are not proper-tail-calls anyway, so PTC doesn't apply.

i find jslint's PTC-based lexer slightly harder to reason with and debug, than if it had stayed with more traditional looping. its not a deal-breaker, and i would be happy with either PTC or non-PTC resolution to its current issues.

@concavelenz

This comment has been minimized.

Copy link

@concavelenz concavelenz commented Nov 12, 2018

@elibarzilay
RE: Strict mode
My point is that measuring the impact, you need to be aware of whether the code is strict and you should expect that the percentage of impacted code will only increase over time as folks ship more and more ES2015 code native (without transpiling ES6 class and ES6 module). If you don't know how much of your code is strict, you don't know how much this could impact you. Saying Safari has 15% of the market isn't useful for measuring impact.

RE: 1. You don't only lose frames that were part of a loop. You lose all calls that are in the return position. That is the difference between PTC and TCO. PTC says all such call frame must be eliminated.

RE: 2. Timers etc.
It has always been this way, and there are ways to record context for these, so those that need this information have built solutions. PTC eliminates frames for existing code, with no way to distinguish between code that requires PTC to operator properly and code that does not, so there is no trivial way to transform code to preserve stack traces. (var a = f(); return a;)

RE: Profiler
Generally, sampling profilers rely on accurate call stacks. With PTC that information is destroyed, you must create a shadow stack in order to get accurate profiling information. That changes the profiler from being purely "sampling" to something that introduces additional overhead (the general drawback of an instrumented profile). Here don't get the benefit you describe. If you did you wouldn't be able to distinguish these call chains (assuming all calls were in the tail position):

f -> g -> h -> i
f -> x -> y -> i

RE: value lifetime
The VM doesn't need to preserve anything it isn't going to use after the call. PTC isn't required for this. In most cases this is handle without intervention by the VMs register allocator. In my experience, you would only need to set "x = null" due to closures and PTC doesn't help you at all there as the context still need to be preserved even if the stack frame is eliminated.

Lastly, for my information, what is what is "Guido-style rejection" ?

@getify

This comment has been minimized.

Copy link

@getify getify commented Nov 12, 2018

PTC says all such call frame must be eliminated.

That is not actually what's required. Here's the relevant part of the spec:

A tail position call must either release any transient internal resources associated with the currently executing function execution context before invoking the target function or reuse those resources in support of the target function.

First, this doesn't require elimination of a frame. It only talks about freeing up resources. That's a subtle but important difference, which implementations like Safari seem to have taken to allow things like the Shadow Stack.

But further, I maintain that rather than being concerned about the letter of the law, the spirit of the law is the most important thing here. What the spec is getting at is less that there must strictly not be any extra resource allocation, but rather that the allocation growth must be O(1) instead of O(n). I would like TC39 to reword this section in this respect, as it would clear the way for lots of other creative ways of accomplishing the bigger goal of tail-calls, which is that I could make any depth of call stack in my program without fear of running my device out of memory.

That's why people want tail calls, not that they explicitly want every single non-essential stack frame thrown away.

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Nov 12, 2018

Lastly, for my information, what is what is "Guido-style rejection" ?

python's creator [in]famously rejected TCO in a 2006 blog-post [1]:

"This is also the reason why Python will never have continuations, and even why I'm uninterested in optimizing tail recursion."

it caused some brouhaha back in the day (similar to what's going on in this thread) [2].

[1] original-quote from python-creator's 2006 blog-post "Language Design Is Not Just Solving Puzzles"
https://www.artima.com/weblogs/viewpost.jsp?thread=147358

[2] backlash to [1] on [Python-Dev] mailing-list
https://mail.python.org/pipermail/python-dev/2006-May/064817.html

[3] python-creator's response to backlash (with further community "feedback" in the comments-section)
http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented Nov 12, 2018

@kaizhu256: it might be that some promises are forced in async-ly in a different tick and therefore there is no problem with tail calls, but that might not always be the case. For example, this code (or some similar variant):

const loop = n =>
  new Promise((res,rej) => res((n > 0) ? loop(n-1) : Promise.resolve(n)));

should be a loop even though there's no such deferring. But more generally, in the simple case of

const loop = n => foo(() => loop(n-1));

I'm relying on foo to call my callback in a tail position, and if syntactic tail calls are a thing, that means that I now need to ask foos author nicely to fix the code.

@concavelenz: (1) yes, that was the point I made later: losing bindings from tail-calles is the feature of reducing resource use; (2) if there are "ways to record context", then wonderful -- tail calls could use the same tools.

For (3), quite the opposite. The statistical sampling fits perfectly with tail calls, if f does almost nothing before tail calling g it will not be shown -- at this point the developer is concerned about runtime and g (the main focus) is still just as visible. If, OTOH, f does a non-tail-call to g (or of no tail call elimination is done), then you get what you have today: you would have an f block and on top of that a g block that is the same width, and you need to infer from that that f is noise and the real runtime hit is from g.

Finally, in those let a = f(); return foo(); cases the runtime does need keep a, because it might be used in a stack trace. A tail call means that it can be GCed.

@concavelenz / @kaizhu256: yes, it's that mess that I'm referring to, but IIRC the relevant post had some "final" in its title and that's when Guido dropped a concrete lid on it.

@concavelenz

This comment has been minimized.

Copy link

@concavelenz concavelenz commented Nov 13, 2018

@getify I fully understand why folks want tail recursion. The text requires that everything be reused or released, nothing remains of the stack frame. The implementation of the shadow stack has nothing to do with that text.

@elibarzilay RE: (2) recording the context for every function that has a call in the tail position is impractical, as it involves recording the stack trace, which is expensive. Doing this for timer, which are far rarer, is sometimes reasonable.

RE: (3) You imply that a you only care about the runtime of a function, but in my experience how you reach the function (why it was invoked at all) is usually as important that the cost of the function proper.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented Nov 13, 2018

Well, you brought it up... It can be expensive, but you have mentioned the optional shadow stack thing...

And in that context I obviously cared only about runtime, since I was talking about one common concern about the usability of flame graphs. (And further, in a statistical profiler context you generally don't care about precise information which is why the random stack polling works fine.) The "why it was invoked" can be addressed using tools that were mentioned many times in this thread; tools that can be used for the sake of skeptics who don't believe functional programmers who say that in practice this is not a problem. (Discussing why it's not a problem in practice will further derail this thread so I'll avoid doing that.)

@hax

This comment has been minimized.

Copy link
Member

@hax hax commented Nov 20, 2018

This thread is very unfortunate that nothing we (programmers) can do except waiting. But I still want to share my thought about PTC vs STC.

  1. I agree that any action is better than no action.
  2. I think tail call is important for FP, without it, JS can never have real support FP even we add many FP features like pipeline operator.
  3. I prefer STC. The problem of PTC is, it's too implicit. If someone write a code rely on PTC, it could be easily ruined by others because we don't know whether a tail call is intentionally.

Example:

function f() {
  if (x > max) return
  ++x
  return f()
}

This is a valid PTC code. Consider if we introduce consistent-return rule, ESLint will complain. How to fix? Someone will just change return f() to f(), and break PTC, and may introduce a potential bug which normal test cases can never find --- even you have a test case for it, you need a correct max to trigger stack overflow, it should be big enough, but not too big (for speed of test running, especially if you run tests on low-end mobile devices). You may need config different max for different user agent, and new versions of them could just increase their stack and fail you...

@sbuller

This comment has been minimized.

Copy link

@sbuller sbuller commented Dec 18, 2018

'consistent-return' seems a little misguided here. Proper type checking reveals that the types remain consistent in your example.

I regularly notice when my code would benefit from TCO, and it's disappointing to know that there's this misguided resistance to it. There's a long history to TCO, and its absence in JS is a serious deficiency.

@pygy

This comment has been minimized.

Copy link
Author

@pygy pygy commented Dec 18, 2018

What more, the technical reason for not adding them (the ChakraCore engine having the wrong calling conventions hardwired) is soon going away since MS is co-opting Chromium.

The other technical problem isn't really one (cross-realm calls can't be eliminated in Firefox) since that can be spec'ed around.

@jswalden

This comment has been minimized.

Copy link
Collaborator

@jswalden jswalden commented Jan 9, 2019

Last I heard, ChakraCore will continue to exist as a JS engine for use in any number of projects not including a browser, so that point doesn't quite work out that way.

@sarimarton

This comment has been minimized.

Copy link

@sarimarton sarimarton commented Jun 15, 2019

Once PTC starts to spread in practice due to its actual availability, and it eventually becomes a problem to identify TCs in code, IDEs will very quickly kick in with syntax highlight help - just as they do with dead code by fading it.

@hax

This comment has been minimized.

Copy link
Member

@hax hax commented Jun 15, 2019

@sarimarton Not everyone in a team use same IDE/editor. And lightweight editors, tools may not identify TCs easily without full AST parsed.

@kaizhu256

This comment has been minimized.

Copy link

@kaizhu256 kaizhu256 commented Jun 15, 2019

i write code exclusively in vim (and use a customized version of jslint that allows ignoring foreign code-blocks)

@littledan

This comment has been minimized.

Copy link
Member

@littledan littledan commented Jun 15, 2019

I have a feeling that we might be able to make more progress on explicit tail call syntax in JavaScript. If everyone able to think through and agree on a syntax, I think it'd be worth bringing back to TC39 to see if we can get consensus on pursuing this proposal.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented Jun 17, 2019

@sarimarton, yes -- identifying tail calls is in most cases extremely simple, almost to the point of regexp-ing it. With a parser it becomes straightforward.

@littledan, the problem is not in agreeing on a syntax -- the real problem is the fact that "opt-in" syntax is going to nullify much of the point of tail calls. See the last bullet in my original post above.

@littledan

This comment has been minimized.

Copy link
Member

@littledan littledan commented Jun 17, 2019

Well, if we can't agree on a syntax, I imagine the current situation will remain as is.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented Jun 17, 2019

@littledan, please see that comment that I pointed to: the problem is not the syntax, it's the fact that you'll need to modify code to "opt into" a tail call, which would lead to situations like what I describe there. (IOW, this is an objection to any explicit syntax for tail calls.)

@ljharb

This comment has been minimized.

Copy link
Member

@ljharb ljharb commented Jun 17, 2019

I'm still not clear on why that's an obstacle - libraries needing to change their code is a temporary problem, as new code would theoretically be written with the explicit syntax where desired.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented Jun 17, 2019

I'll try to explain it with an actual (but very simple) example.

  • I implement a useful text-lines library, which has:

    // calls f on a list of lines from the file
    function withLines(file, f) {
      let lines = file2lines(file);
      return f(lines);
    }
    
  • You use this libray in:

    function waitUntilItsOK() {
      withLines("some-file", lines => isOK(lines) || continue waitUntilItsOK());
    }
    
  • Your code is perfectly fine, except that it's broken because my code doesn't use continue. You'll ask me nicely, but I don't want to complicate my code with strange keywords, or I need the code to work on older JS engines, or my company won't allow me to invest time to change code that already works, or I don't like this new "PTC" feature, or I heard that it code run slower, or whatever. You're now stuck.

In a theoretical world where none of these reasons hold, everyone would eventually add continue at all places that matter — but then what was the point of adding an extra keyword in the first place?

The only "real" answer to that is to make it easier to verify that what you think is a tail call, is ineed one. IMO, this makes exactly the same sense that the "capture clause" in C++ lambdas does. And for all I know, you might like that feature (maybe because you're doing C++ at google). But like I said previously, in the current non-theoretical world, the much likelier result is that tail calls will not be widely used (if only because of the natural bias against longer code).

@ljharb

This comment has been minimized.

Copy link
Member

@ljharb ljharb commented Jun 17, 2019

You could also imagine the syntax enabling proper tail calls for the entire stack it generates - avoiding the need to add the keyword all the way down.

@elibarzilay

This comment has been minimized.

Copy link

@elibarzilay elibarzilay commented Jun 17, 2019

That sounds interesting, but it's not what's suggested in this proposal...

(Sidenote: I imagine that you're talking about something that happens at the beginning of the stack since going the other way is impossible. Something that I thought could work is some "use strict and tail" declaration where all code under it creates a dynamic stack context that makes all later calls be tail calls. If that's what you're talking about then that sounds like great idea. Again, regardless of actual syntax: I don't really care if it's a top "use strict and tail" or some (()=> continue { ... }) wrapper around my whole file.)

@PinkaminaDianePie

This comment has been minimized.

Copy link

@PinkaminaDianePie PinkaminaDianePie commented Jun 17, 2019

Enabling the entire stack it generates? Why not go other way and have PTC but provide unfolded stack trace when required? So my app will have PTC, but if i'll struggle with something, I will be able to enforce unfolded stack trace, debug my app, and disable it back again? But having ETC keyword which enables PTC for stack trace is fine enough if I will be able to do it once at the root of my app (e.g. in index.js) and work with PTC everywhere. Anyway, explicit TC, which I will be able to use only once at the top of app will be good thing, but have it explicit everywhere will be much much worse

@getify

This comment has been minimized.

Copy link

@getify getify commented Jun 17, 2019

I prefer "implicit PTC" (current spec) but with revised wording that would widen the possibilities for various engine implementations, as discussed earlier in this thread.

However, it seems almost impossible for that to ever happen from the current state. The years-long stalemate is bad for JS and for engines.

As for whether TC39 could remove PTC without consensus, I have changed my mind from earlier positions: I now strongly feel that TC39 can, and should, remove PTC from the spec. This needs to happen first before any possible progress on tail calls can happen.

The webkit folks don't have standing to object to the removal, as this doesn't betray or invalidate their implementation at all. Had PTC never been added, I believe webkit could have added this "feature" as an optimization without being in spec violation. So even if the spec part is removed, that doesn't harm webkit.

I believe the editor of the spec should make an executive decision that any spec'd feature (or typo or bug or wording or ..) which is later openly defied by implementation(s) -- irreconcilably so -- is a post facto veto, and therefore can and must be removed, retroactively stricken from the standard.

I imagine there may be some "legal" objection (ECMA, etc) to that, so in effect the next best thing is just to inline the change in the next spec revision without need for consensus.

In any case, we need to do a reset on this topic so we can then have productive discussion about any possible path forward.

@ljharb

This comment has been minimized.

Copy link
Member

@ljharb ljharb commented Jun 17, 2019

That is not within the power of an editor - every delegate has standing to block anything for any reason, including removing PTC from the spec. Consensus is required for normative changes, which is why we’re in the stalemate we’re now in.

I agree that no progress can be made until PTC is removed.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.