Can tail-calls be adaptive?

[getify]

Is it possible (either with existing wording in spec or with changes) to allow an engine to support "tail calls" but not necessarily tail-call all of the calls?

IOW, imagine an engine defaults to always doing the first x (for some small x like 10-20) tail-call-eligible calls as just regular calls (with new stack frames), and only kick in the tail-call stack frame reusing after this x limit?

The reason I bring this up is as a potential compromise to the concerns around stack traces with telemetry and debugging... since the concern is elided stack frames, maybe we don't elide all stack frames. Since most of the time having the first x stack frames in your stack trace is going to be sufficient for tracking down errors, those stack frames would always be there.

For the times when a heavy recursion kicks in and quickly goes beyond that x limit, then the vast majority of the recursive frames will be elided, meaning memory didn't grow unbounded.

The other benefit would be the concerns that some engines have about regressing perf on existing function calls, since in the general case normal non-recursive call stacks aren't dozens of levels deep.

Another way of thinking about this could be that there'd be a rolling "window" of stack frames, such that an engine is allowed to keep the last x frames... meaning that it just tosses away "older" frames (that could be elided, of course) and is only ever keeping that x frames to show for telemetry/debugging purposes. Again, I'd think the vast majority of cases of telemetry/debugging would still work just fine if they always were guaranteed to have the last up-to-20 frames. The cases where you need 50, 100, or a thousand stack frames to track and fix an error have to vanishingly small.

[bobzhang]

this looks interesting, FYI, there is a blog https://blogs.janestreet.com/optimizing-list-map/ about doing it manually in OCaml

[rossberg]

The spec already allows that. Any implementation strategy that is observably equivalent to the spec is of course valid. And this one is, at least if done right (i.e., you have to be sure that you don't overflow the stack during those first few invocations).

Basically, all that the spec prescribes is that certain programs have observable O(1) stack usage, the constants don't matter.

[littledan]

As @rossberg-chromium says, ES5.1 and earlier already allow some tail calls to be eliminated on a reliable or unreliable basis. The STC proposal continues to allow implementations to do PTC or approximations of this if they wish; it simply doesn't require it. The proposition of PTC is whether it should be required strictly in all cases.

As far as this as a strategy for enabling debugging for PTC under the ES2015 specification--I think it would be hard to do a good job on this window strategy, as it's hard to tell which stack frames are OK to eliminate. Some tail calls will be loop-style, and some won't; you'll generally have a stack which is a mixture of these, with the loop ones "in the middle". The key would to get rid of those without getting rid of meaningful, non-loop-style calls on the top or the bottom. I'm not sure how to go about that. I bet the stack frames which happened before the loop was entered are meaningful, and the things that the loop calls out to in its base case are also meaningful.