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?

[getify]

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

It was really a side note more than anything else.

But it does support my overall thesis in that it refutes one of the above concerns, namely that if you opt a function into being PTC-eligible (with the function level sigil) it means that all PTC-formatted calls have to be tail calls, even if there are cases where that hurts perf. IOW, that might not necessarily have to always be true.

Combined with the fact that a developer can intentionally "opt out" of the tail call by grammatically changing to not match as a PTC, I think it's possible in a general sense for developers to assume, expect, and have some confidence that a function-level-PTC function will tail call the PTCs that they want and not tail call ones that shouldn't.

The main argument in favor is still the second paragraph of my OP.

[getify]

Put another way: function-level syntax could be framed as less direct and explicit about expectations of each and every call site inside the function. That means it leaves open more of a gap for the engines to monitor and figure out what really will benefit from a tail call and what won't. Imagine describing the feature not as "unconditional tail calls always" but as "can do tail calls when it needs to and when it will benefit your program".

OTOH, call-site level syntax much more clearly signifies, "I want this one right here tail-called, don't argue with me", which in general could tie the hands of the engines a slight bit more.

[claudepache]

I think that a function-level syntax is a bad idea for the user, for the following reasons:

• When you read the code, even in case of function-level syntax, you have to look at call-sites anyway in order to determine whether a tail-call is triggered. Plus, it is easier to a recognize a tail-call by looking for an explicit syntax than by analysing a grammatical tail-position.
• Having to mark explicitly each tail call could make debugging experience better, because the parser could statically detect occurrences of required but impossible tail calls.

[dilijev]

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

These sorts of patterns are the type of thing that engines will try to optimize into the shape of a PTC. Making some kind of an exception for that pattern or patterns like it (or essentially assuming the developer meant to disable tail-call if they did anything other than the trivial pattern) seems counter-intuitive from an engine development perspective. (We have to make assumptions about developer intent instead of doing optimizations we identify as being worthwhile.)

[getify]

@dilijev the general direction of discussion here seems to clearly be moving away from engines having the freedom that decide implicitly what is and is not a tail call. The explicit syntax, and especially the call-site syntax most here seem to favor, don't give the engine the option of just rearranging some code to be a tail call if that's not what the dev wrote.

Especially from the perspective of the impact a tail call may have on debugging (eliding stack frames), I don't think having no way to opt-out is going to fly.

If the explicit call-site syntax wins out, surely you're not suggesting that a non-grammatically-tail-call call site would just get implicitly promoted to a tail call? That sounds entirely inconsistent with the spirit of this feature as being discussed, and also violates uaer expectation.

I cannot imagine any shape of tail calls prevailing, even the version that's currently in the ES2015 spec, that doesn't afford both opt-in and opt-out, even if one is implicit and the other is explicit, or vice versa.

[getify]

@claudepache

occurrences of required but impossible tail calls.

Can you please give an example of such, that could be statically identified before runtime?

function-level syntax is a bad idea for the user

what about my OP claim that call-site syntax is bad for the user? specifically, my concern of having two or more call-sites that you want to tail-call but accidentally only getting the explicit syntax in some of those call-sites and not others.

what I claim is that call-site syntax is "pit of failure" design. it will lead to a greater evil because it will be much harder to spot such a problem visually -- this will be new syntax JS devs are not used to doing, so until we're all seasoned with it, it'll be more natural to forget or not recognize. you potentially won't catch that you've made this mistake until much later when you run the code. amd that debugging experience will be quite awkward since some call-sites will have stack frames elided and others won't.

---

furthermore, unless I'm missing something, I don't see how tools (linters, etc) could statically analyze that you intended a call-site to be tail-called but that it isn't b/c you forgot the explicit syntax. In the cases where I have left out the explicit tail-call-site syntax on purpose -- probably the majority of call-sites in my code -- I certainly wouldn't want noisy warnings on all of them second guessing me like, "did you mean to tail-call here?"... "no, I left it out on purpose, just hush."

[dilijev]

If the explicit call-site syntax wins out, surely you're not suggesting that a non-grammatically-tail-call call site would just get implicitly promoted to a tail call? That sounds entirely inconsistent with the spirit of this feature as being discussed, and also violates uaer expectation.

Yes, if we go with explicit syntax then we should expect the developer to declare their intent and do so in a proper position. However, if we were not going with the explicit syntax this might be a concern.

[getify]

Why would you want to second guess (with code rewriting) in a function-level tail call world but not in a call-site world? I claim they're both explicit conditions, as compared to the purely implicit condition in ES2015.

IOW, why would I get an opt-out for call-site but not for function-level? if I mark my function as tail-call'y, i would want the engine to tail call all call-sites that are legitimately tail calls, and leave everything else alone.

[dilijev]

With trivial bytecode optimizations in the engine, there would be no difference in the bytecode between let x = foo(); return x; and return foo();, that's all. So semantically, if the decision about tail call were made at parse time, then you're absolutely right that the decision could be made based on how the code looks, but if it were made anytime later, it's not as easy.

[getify]

So in ES2015 (the way things currently are), you would turn let x = foo(); return x; into a return foo(), and thus then you'd implicitly tail-call it? That seems to violate the spirit of the ES2015 spec as far as I can tell. I interpret it as you're supposed to tail call actual PTCs as written, not code that an optimizer made look like a tail call.

If you implicitly tail-call something that the developer didn't actually write as a PTC form, you're running the big risk of violating their expectations when they look for stack frames that you've elided.

And doesn't that then create some sort of arms-race between developer and engine, where they look for progressively more and more divergent-from-PTC-form code patterns so that they can try to opt-out of what they don't want you to do? "I wonder if I put a + 0 on the end of this, will the engine optimize that away? what If I do !! on it? etc etc?"

[littledan]

ES2015 specifies based on surface syntax the set of constructs that are tail calls. It would not require that usage to be a tail call. However, the spec does not prohibt engines from optimizing that.

[getify]

@littledan but clearly the engines eliding stack frames in those cases would violate user expectation, as this concern has been so vocally raised in other threads here. I didn't claim it was restricted by the explicit wording of the spec, but I think it would violate the spirit of the spec ("principle of least surprise").

In any case, I think it's a particularly weak argument that function-level syntax couldn't offer an opt-out via grammatical forms. At a minimum, I think the new spec wording would have to allow for the opt-out, thereby more explicitly stating, "hey, engines, don't get too clever and violate user wishes here."

[dilijev]

I could have been more clear about my concern here. I'm indicating that because the spec doesn't prevent us from turning those constructs into tail calls, and because it would be a matter of jumping through hoops to get the "expected" semantics when that is an optimizable construct, I'm making a point in favor of explicit syntax to more closely capture developer expectation: Do a STC if specified, and otherwise a PTC won't happen.

[getify]

I can see many angles on why explicit call-site syntax makes it easier for engines to do tail calls. My point continues to be that I think this is more troublesome for developers (pit of failure). So if an engine could do what I'm suggesting, I think that's enough for the proposal to stand on, even if it would be harder (more hoops) for the engine to achieve.

I don't want any explicit syntax. I think it's a terrible idea. But if there has to be explicit opt-in syntax, I'd like it to be as little susceptible to developer mistake as possible. It's a compromise I've proposed here between call-site explicit and totally implicit.

[rossberg]

@getify, in fact, explicit tail calls are more work for engines. Not by a large margin, though.

[claudepache]

In one sense, ES2015 contains already a function-level annotation for enabling PTC, namely "use strict"... although that directive also enable other features (mainly, more strict error conditions).

[littledan]

#5 (comment) points out a significant disadvantage of that style of declaration: we would not be able to use non-simple parameters.

[getify]

Quoting myself from above:

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.

I don't think the function-level syntax has to opt a function into strict mode. I think the function-level syntax could be an early error if the entire file/program wasn't already in strict mode.

PTC already requires the function itself to be strict, and I don't think we need to support mixed-mode where tail-called functions are strict and other functions in the file aren't strict. It seems entirely reasonable to just force you to upgrade your program to strict to take advantage of tail calls.

[dfahlander]

I might be late in the game, but if anyones opinions may matter, I would like weigh in my opinion here as well.

I totally agree with what @getify suggest - to be able to opt-in per scope instead of each call site. I was actually about to write the same suggestion until I found this issue.

If I was an FP fundamentalist, (which I'm not, but I could imagine their feelings...), I would love to be able to write pure, pretty and clear javascript, exact the same way I would do in erlang, lisp or F#.

I think javascript language would gain better traction from the FP community if allowing that kind of clean code without cluttering it with keywords or sigills. A scope-level opt-in would mark the scope as safe for functional-style programming no matter whether you put it inside a function, a module or globally for the entire program. Having to explicit opt-in at every call site impacts code prettiness, and code prettiness matters (at least for code readability).

Remender, the original proposal was PTC to be implicit globally... (!) Even though this turned out to be troublesome, the issues has not really been about inconsistent code behaviour. It's rather about "meta-behaviors", such as debuggers and Error.stack.

Why don't just go the middle-way?

Future JS code will likely be all module based and opting in per module / function sounds reasonable.

"use tail calls";

export const factorial = (n, acc = 1) =>
  n === 1 ?
    acc :
    factorial (n - 1, acc * n);

export const myOtherGreatFPStyleFunction =
   (x, y) => ...;

...

It's also about mathematical clearness.

[ljharb]

Explicit indicators at each coal site are much prettier to me, because explicit is always prettier than implicit - so clearly that’s subjective.

[dfahlander]

I've been thinking about this for a while since I wrote my long view of it and I've come to the conclusion that I might be wrong about this. Explicit indicators are good as it indicates the bevaiour more clearly. "continue" is a nice keyword for this, as it explains what actually happens. Also, there would be issues with code snippets taken out on stackoverflow etc, or copied/pasted from a module would work differently with the "use tail calls".