Function-level annotation rather than per call site

[getify]

As I described here, I would like to register dislike to the idea of this explicit PTC syntax being call-site oriented. I would like the syntax opt-in to be an annotation on the function itself.

I won't repeat myself from that thread of messages, but the TLDR is that I expect there will be more, potentially many more, PTC call-sites than PTC-containing functions, so requiring call-site syntax means more places to have to do it (cluttering the code) and thus more places to forget. Depending on your coding patterns, you may not be able to directly tell that you forgot to opt-in one of your PTC call sites.

Conversely, opting-out of PTC inside a function annotated for such is quite easy: just don't format it as a PTC. There's a variety of grammar/syntactic tricks you could use to accomplish that.

Function-level annotation still keeps PTC fairly explicit for developers and readers of code, still gives engines the ability to limit the scope of PTC changes that they expect to impact existing code (still entirely opt-in), but minimizes the developer burden of both the opt-in and opt-out paths.

Here were the ideas I started out with:

#function foo() { .. }
#function *bar() { .. }
let x = #function *baz() { .. }
x = {
   #bam() { .. },
   #["qux"]() { .. }
};

Or

rec function foo() { .. }
tail function foo() { .. }
function rec foo() { .. }
function tail foo() { .. }

[getify]

And I know this is likely to evoke several strong objections, but what about an annotation similar to "use strict", but only per function, like:

function foo() {
   "use tail calls";
   // ..
}

It would remain to be seen how that would interact with actual "use strict", but I don't think that's a huge issue since PTC only works for strict mode anyway. IOW, the easy solution is that "use tail calls" would imply "use strict".

[littledan]

In general, I'm cautious but not entirely opposed to function-level marking. You are basically saying, "this is a function which plans to recurse; I don't care about its stack frame starting from some point". It seems like it would be fairly easy to implement within V8. It is nice to solve the arrow function problem this way. However, I do have some reservations:

• I think we should consider # as taken by the private state proposal (modulo any sigil shakeup that @wycats may propose). This doesn't affect rec function foo() though (which has the complexity of being yet another contextual keyword, but the saving grace of the exact same syntax as async).
• "use tail calls" is a bit difficult to square with strict mode. Should that declaration imply "use strict" as well? If not, where do you put the "use strict" if you want it? What about our current prohibition on complex destructuring in that case?
• Different return sites may actually be different in terms of developer intuition for whether the stack should be popped. A base case return should ideally not be a tail call site, so that the unsuspecting function call can still have its caller seen on the stack, when it's not important for constant/linear stack usage.
• Chatting around with various people thinking about PTC/STCs, it seems like most people expected the syntax to be on the return, rather than the function. That was my intuition as well, that whether to pop the caller stack frame is a property of the return site, rather than the function as a whole.

[ljharb]

@getify if the syntax was on the return, but it opted in the entire function call (and any functions that called, in turn), would that cover your concerns? if so, then @littledan, would that be reasonable?

[efaust]

@ljharb So then a given function would have to treat all tail-position calls as tail calls optionally based on which syntax was used to call it? That seems even less intuitive than what we have now, at least to my first thought.

[ljharb]

@efaust my thinking was that the "eligibility for tail calls" would be determined at call-time, not at definition time - since it already depends on which syntax was used to call it. However, if it seems less intuitive, that's a strong signal that it probably is :-)

[efaust]

Yeah, OK. I think that's both worse for implementors and worse for users.

It also seems like it precludes being able to call a function that has to make tail calls from a non-tail position, which is very odd. Regardless of my intuitions about user-friendliness in general, I think this concern (still assuming I correctly understand) is lethal.

[getify]

@littledan

I think we should consider # as taken by the private state proposal

Am I missing a grammatical issue with reusing #? We have all kinds of places where some operator means different things in different contexts. For example, the extreme overloading of { / }, the lvalue/rvalue context of ..., etc.

Anyway, I don't care that much what the sigil would be. I do think it would be nice if it was obviously different, and the word form is not, IMO, as obviously different at a glance.

"use tail calls" is a bit difficult to square with strict mode. Should that declaration imply "use strict" as well

As I said, IIUC tail calls only happen in strict mode anyway. So yeah, "use tail calls" would definitely just imply strict mode, with all that implies. In fact, I think I would be entirely OK if the spec actually said that the entire file/program has to be strict for any tail calls to happen.

Strict mode has been around for over 6 years and is clearly the future of the language, so by now I'm having far less concern for trying to adapt these new functionalities into loose/mixed mode programs. If the entire file had to be strict to use any tail calls in it, then this "implied strict mode" thing is moot, as is the prohibition on complex args stuff.

Different return sites may actually be different in terms of developer intuition

Yeah, I definitely recognize the need to be able to "opt-out". I think there's plenty of grammatical options for altering your call so that it's not a matching PTC and thus opted out.

The simplest is to let x = foo(); return x; instead of return foo();.

IMO, developer intuition here isn't the main concern -- I think the wrong mindset (trying to intuit/outsmart the internal mechanisms of the engine) is at work. I personally would rather the engine attempt to tail call all of my PTCs, and then I'd be responsible for profiling my app to make sure that the default decisions of the engine were in fact the best ones. If I found that a certain call was problematic perf wise, I'd want then to opt it out.

I know we don't like to call PTC an "optimization", but in my opinion, PTC shares a lot with the mindset of other perf optimizations. Generally I try not to outguess the engine with my own micro-optimizations, but in specific cases profiling identifies narrow places I have to do different stuff. I would treat this case with PTCs exactly the same.

Also, ideally, over time the engines would get smart enough to spot places where the tail calls are slower and opt those out in those cases. At the very least, it'd be a great future devtools feature to identify places where PTCs would help, are helping, and are hurting.

A base case return should ideally not be a tail call site

If I understand you correctly, most of my "base case return"s are not actually PTCs. My base case returns are usually of some concrete value, not another function call, so PTC wouldn't apply. If for whatever reason it was a PTC, again the let x = foo(); return x; form is easy enough to opt-out.

it seems like most people expected the syntax to be on the return

I have no doubt that in isolation, the more intuitive form is at the call-site. I completely agree. But the bigger concerns I've raised here are what I think tips (narrowly) the balance to a function-level annotation.

[getify]

@ljharb

if the syntax was on the return, but it opted in the entire function call

I think surely you mean "at the call-site", because otherwise someone wouldn't be able to call your recursive foo function as just foo(..).

But the problem with pushing the sigil to the outer call-site is that you're shifting the burden and footguns to the users of code rather than authors. If I write a function that uses recursion, I don't necessarily want the user of that function to have to know that and to have to opt it into tail calls at their own call site. That should be an encapsulated implementation detail.

[ljharb]

@getify no, i'd meant inside the function's return value (ie, where the tail positioned call occurred), but #5 (comment) convinces me that it's not a good idea.

[bterlson]

I don't think a function sigil is a good idea. Tail-callishness is a property of the call site so it seems critical to me that the sigil for opting into it is very close to the call site. I disagree that this conceptual mismatch is something we shouldn't worry about. This is proposing some sort of mode switch for the PTC proposal we already have and solves some problems but not others. Getting into specifics:

#function

I don't think we will succeed in advancing any function sigil. This is very constrained syntactic space and I don't think it's a good idea to use up a sigil for this purpose. There are many possible conflicts to worry about with the many sigils we are considering on the horizon.

"use tail calls"

Directive prologues have not been a good experience IMO. We should not be adding any more of these unless absolutely necessary, especially not at the function level. "use asm" has the benefit of not combining with other prologues. I don't want to start a precedent where we have all sorts of these prologues.

So yeah, "use tail calls" would definitely just imply strict mode, with all that implies.

That implies that a function that has a "use tail calls" prologue would not be able to use a non-simple parameter list. This doesn't seem acceptable to me.

I know we don't like to call PTC an "optimization", but in my opinion, PTC shares a lot with the mindset of other perf optimizations.

It should not. I would not encourage others to share a similar mindset. Use PTC/STC when you have a recursive algorithm that requires PTC/STC to work correctly. Otherwise, don't.

Also, ideally, over time the engines would get smart enough to spot places where the tail calls are slower and opt those out in those cases

PTC spec does not allow us to do this.

[getify]

That implies that a function that has a "use tail calls" prologue would not be able to use a non-simple parameter list. This doesn't seem acceptable to me.

First, that seems inconsistent with the decision TC39 already made to put that restriction on "use strict" in the first place. I didn't like it, many others didn't either. But it's a fact. That fact has costs.

Secondly, and more importantly:

In fact, I think I would be entirely OK if the spec actually said that the entire file/program has to be strict for any tail calls to happen.

That resolves all those concerns.

PTC spec does not allow us to do this.

Given that we're discussing changing the spec, and as you and others keep pointing out, PTC hasn't shipped, I don't think it's really relevant what the current spec allows or disallows. I think it should allow it. The spec allows all sorts of leeway for implementations, so it doesn't seem unreasonable to me that the spec could allow implementations to preserve the ability to write tail-call oriented code while also reserving that some calls can be detected to run better without it.

The engines do all sorts of crazy things for optimizations, like trying one compilation of a function, then monitoring it, then throwing it out and trying another, etc. It seems entirely reasonable that engines could eventually try a tail call by default, but over the run of the program, if that call is having a net performance detriment, then it falls back to some other strategy while still maintaining the memory constraints.

Engine devs are fantastically smart folks. No spec should try to outsmart them, especially in perpetuity.

[bterlson]

First, that seems inconsistent with the decision TC39 already made to put that restriction on "use strict" in the first place.

It's not. "use strict" is not useful at function granularity except for IIFE's which don't need non-simple parameter lists. We're talking about something specifically for function-level opt-in.

Given that we're discussing changing the spec, and as you and others keep pointing out, PTC hasn't shipped, I don't think it's really relevant what the current spec allows or disallows. I think it should allow it.

I disagree. If a call is in tail position the assumption that you get constant stack space usage should also be true in practice.

if that call is having a net performance detriment, then it falls back to some other strategy while still maintaining the memory constraints.

What is this "other strategy" that gives the same benefits while being faster than PTC? We should be proposing this instead.

[getify]

If a call is in tail position the assumption that you get constant stack space usage should also be true in practice.

I don't think most developers thinking about recursion are necessarily worried about (or even know how to use devtools to exactly profile) that there's literally only one stack frame allocated, as they are that the recursive function call will just use O(1) stack space in general, that they'll not run out of memory no matter how long their recursion runs. That leaves a small door open for optimizations of the sort I suggested.

[ I am not an engine developer. So I'm purely conjecturing here, but with some developer-oriented intuitions. ]

If for example the first or last call in that "stack" was not tail-called, but everything in between was, the developer still gets the outcome they care about, which is they can call an unbounded recursion without running out of memory. Or maybe it's the first five that are normal and then it switches to tail calls, or whatever. Maybe it's conceptually similar to adaptive sorting algorithms that do different things with small lists versus large lists.

Anyway, in such a case, I am theorizing that the engine could have realized that this call or this fixed set of calls actually was slower if literally tail-called, and so it switches to doing only that work as a normal separate allocation with everything else tail called.

If the memory usage is two (or five) stack frames instead of one, it's still in spirit O(1) memory usage, and never runs the risk of run-away memory. And it allows the engine the freedom to monitor if there are cases where they get more performance and trade out a fixed/constant amount of memory usage to do it.

---

Frankly, I don't really care how realistic my description above may or may not map to a engine dev's reality. It's conjecture. What I do know is that engine devs have pulled off far more conceptually amazing feats as precedent, such as type inference, JITing, etc. I would assume there's fertile ground for their creativity here.

And more to address your point, I think there's room here for the assumptions of normal developers to be preserved while still giving the engines a chance to tweak.

[bterlson]

Can you explain how the ability to do such tricks argues in favor of function-level sigil?