Edit: Oh, seeing the sibling comment, are TCO and "tail calls" different things? If so, I remain unclear on the status of TCO support in QuickJS.
Now tail calls are quite annoying to implement in C on top of a compiler that doesn’t (and in fact I don’t think any mainstream platform has a C ABI that would allow a C compiler to natively support them between functions of arbitrary types). That has always been a (solvable) issue for Scheme-to-C translators, and it was probably a consideration for QuickJS. Chrome’s V8, though, is so far away from interpreting things in C or even translating them to C that I expect that any difficulties the developers have are of a completely different nature.
(As an example, LuaJIT does support tail calls but kind of sucks at inferring hot loops written using them, so has really impressively draconian limits on how many you can have before the JIT aborts. They otherwise work, though, as is required for a valid Lua implementation.)
While in practice it probably improves the performance to have tail calls, theoretically, the spec isn't making a point about performance here, only semantics. It would, for example, be allowed to have a spec-compliant JS implementation that handled tail calls very slowly, as long as they are correctly don't increase the stack.
As to why various implementations don't do TCO, my impression is that it's a combination of complexity and usability issues that have kept it from being implemented. And if some of the major browsers won't implement it, then I can see why other, smaller implementations don't see it as a priority.
I personally more agree with not implementing it implicitly (although I think there was some discussion about having a special syntax) just because of the potential for confusion during debugging. E.g. if all tail calls are elided, then you could have stack frames that don't "make sense" (how did function A call function C? well, through function B but that frame is gone, and this could be really difficult in deep stacks). Alternatively, you could use a heuristic but that just raises even more questions.
It’s not a different issue from async functions not having a stack trace and JS devs survived for decades without async traces just fine.
Algorithmic complexity is an essential part of defining an interface.
My impression is that this is less an issue with any particular implementor, and more with the feature not being fully thought through at the beginning. A lot of the browsers (including the Edge team at the time) ended up running into issues, on top of the UX/explanatory problems. That's why there was the alternative proposal for explicit tail calls, but those didn't go anywhere.
2. Any 2% of the market doesn't matter.
3. …
It was more that it forced the implementation to elide stack frames whenever calls occurred in tail position.
That’s a semantic change to program behaviour. And one that messed with the expectations of developers.
I would have been fine with some explicit syntax for invoking that behaviour, but it seems the standards process that got it approved never really consulted developers or implementors.
Do you know why the standard committee rejected adding explicit syntax for tail returns and instead went the route of declaring that all calls in tail position must lead to stack elision? I never really bothered to find out.
Also is spidermonkey now adding TCO to JS because of wasm, or are they adding TCO to wasm?
The only FP languages that require explicit syntax, target the JVM, which lacks the support.
Common tooling for production error tracking (e.g. Sentry) would be greatly affected by such a behavioural change.
Functional languages "just work" with those semantics because those expectations were set up ahead of time, and tooling and developer expectations were molded around them. But JS isn't one of those languages. The tooling and developer expectations, and gargantuan amounts of existing code, has been written with the expectation that calls create stack frames.
> The only FP languages that require explicit syntax, target the JVM, which lacks the support.
Support could be added to the JVM just the same as the JSVM though - via a spec change. And just as with the JSVMs, it would be a semantic change that would alter the behaviour of existing programs in ways that would break existing tooling and make developers lives worse. It's why both of them resist it.
The percentage of sites affected by automated stack tools is far less than the number of other sites that would benefit from tail calls.
More importantly, this breakage already happened 8 YEARS ago in Safari and 20% of all web users already break those expectations, so companies should have already adjusted. At this point, it only serves to split the web.
Now it is too late to save Firefox.
And apparently, the best way to reverse that situation is to ignore Mozilla (or any other player with single digit market share) at the W3C?
And do what instead? Side with Apple/Microsoft as long it hurts Google?
My understanding of the situation is that it's entirely technical issues that came up after implementing.
MS complained that windows APIs made it slow, but first, they should fix their OS. Second, chrome didn’t have those same issues on windows. Third, they now use chrome, so it’s no longer an objection.
Firefox complained that it was work, but they’re also doing it for wasm.
This only leaves the stack trace argument, but the biggest cases for tail calls are where you’d already be forced to a loop and nobody complains that loops don’t have stack traces.
Further, you already have the same issues with async stack traces and activating shadow stacks in debug mode works just as well as those async traces.
It’s all about chrome devs digging in their heels because they took a side dumb argument and won’t just swallow their pride and implement what developers want and the spec demands.
LOL, as they do.
Moreover, tail call elimination is explicit in WASM. The initially-defined call and call_indirect instructions aren’t allowed to do tail call elimination, and the tail-call proposal added return_call or return_call_indirect which require it. The situation is thus more like the (now inactive) TC39 Syntactic Tail Calls proposal. No need to worry about the debugging or performance implications.
> Firefox complained that it was work, but they’re also doing it for wasm.
They said it was impossible to implement across realms with their membrane-based security model. That is: “we could do it in most cases, but you’ve said we have to do it in all cases and we can’t do that without replacing a fundamental and pervasive part of our engine, which we certainly don’t want to do for something we and others aren’t convinced is even a good idea”. But in WASM, any tail calls are to the same WASM program, where this isn’t a problem.
FF runs WASM on Spidermonkey. If the security model is broken by JS, there's not a great reason to believe it won't also be broken for the same JIT when running WASM.
I also believe that Google’s representatives at TC-39 (and Mozilla’s to a lesser extent) knows this. Meaning they have other reasons for not implementing TCO. My personal theory is that they are very much against expending the functional paradigm in JavaScript. TC-39 has been very hostile towards any proposals which would expand the functional paradigm in JavaScript. The decision to advance the hack style pipeline operator (which uses a placeholder) over the F# (functional/tacit) operator is a prime example of this.
This, I believe, is purely political.
Paul Graham wrote back in 2001 that Lisp was a secret weapon for building a startup due to the developer productivity gains. https://paulgraham.com/avg.html
As a corollary, the more lisp-like JavaScript is, the more it reduces barriers to entry for launching a tech company, promoting more software engineers into potential new competitors.
Could it be that Java and Python are taught in universities because some members of the industry prefer making it more cumbersome for new grads to launch a company? Having significant barriers to entry is business strategy 101.
Does the developer expect a call stack?
Does the developer NOT expect a call stack? Maybe they want to see if the optimization was activated.
Bug reports either way.
That said, all sorts of weird changes happen when a debugger is enabled.
The jit will eliminate various pieces of code and remove variables from scopes, but you better put them back if the debugger stops! This one I remember in Firebug. Oops!
¯\_(ツ)_/¯
In this particular case, devs definitely see the Safari traces when bugs pop up.
Devs definitely don’t like surprises, but also absolutely hate their tools not telling the truth.
We’ll never know how big of a role TCO could have played in JavaScript over the past several years, because it hasn’t been available outside of some narrow contexts.
Where recursion is clearer (for example, when dealing with recursively nested data structures), the clearest expression of a function usually isn't tail recursive - that often requires rewriting the function to put more state into the function arguments.
This means that tail recursion rarely matches with patterns used regularly in Javascript. That's not to say it's useless - if you want to keep to a particular functional style, or if you're compiling to Javascript from a language that emphasises recursion, then it's a useful tool to have. But in the former case, you're generally going to struggle with browser engines not being optimised for this style, and in the latest case, you're probably better off targeting WASM directly.
There’s an element in this that gets at why V8’s omission of TCO feels to me like suppression of functional programming. JavaScript is an incredible widely used multi-paradigm language, to the point that I would recommend for universities to replace Python and Java with JavaScript in their curriculums. It’s just so practical for building software systems, has amazing tooling, connects you to a rich community, and allows you to cover so much academic ground. JavaScript has been a rocket fuel for promoting a vibrant, diverse software engineering ecosystem.
Although you can choose to write a loop and do things imperatively in JavaScript, you don’t have to. The ECMAScript spec is inclusive toward the functional programming paradigm by requiring that engines provide for proper tail calls. Functional programmers should be allowed to have their cake and eat it too! But TCO isn’t implemented in V8, and the workaround is to just switch from functional to imperative programming.
You can mimic all of that, but it's painful, it's not something that Javascript is that great at. Which is fair enough, it doesn't need to be perfect at everything, that's why there's different languages. If you want functional programming in the browser, try using Elm or ReasonML. Both of those are fairly easy to use, I think there are even online playgrounds for both to get started.
const times = a => b => a * b
const double = times(2)
const twiceFour = double(4)
As a language feature, a function to curry a given function is different from proper tail calls in that it can be implemented as a JavaScript function rather than needing to be built into the JavaScript engine. Similarly, Haskell’s own curry function is imported from its standard prelude. Leaving this detail up to language users allows a diversity of approaches and vibrancy in the community. Lodash has had an implementation for a while: https://github.com/lodash/lodash/blob/0843bd46ef805dd03c0c8d.... (Edit, found better example.)Structural pattern matching can be very elegant and it would be nice if ECMAScript offered it. Object destructuring has been added to the language, and that feature could be seen as a stepping stone for adding structural pattern matching in a later version. Proper tail calls however are more fundamental to the paradigm of functional programming, since they are necessary for iterative algorithms to work as well functionally as they do imperatively.
In Javascript, a function that accepts two arguments is meaningfully different from a function that accepts one argument and returns a new function that accepts a second argument. Both semantically, but more importantly syntactically. It's possible to overcome this at the library level as you say, but it usually has performance and usability issues - error messages start looking very funky! It also often doesn't play well with other Javascript features, such as the famous `map(parseInt)` issue.
That's not to say that currying isn't possible in Javascript, just that it's a feature that doesn't play well with the rest of Javascript. If you really want currying when you're coding, you're probably better off choosing another language - currying will work so much better, and you will have so many more advantages.
What I've said is specific to currying, but in my experience, this is generally true. You can use certain functional idioms in Javascript (particularly higher order functions), but it isn't really a functional programming language. Adding features to make Javascript more functional makes the language a lot more complex, but it won't magically turn Javascript into a good functional language. Therefore, it doesn't make sense to include things in Javascript just because they're useful in a functional context, it's first important to validate that these features are useful in a standard Javascript context.
They have a stage 2 record/tuple proposal. Records are far more optimizable than JS classes since they enforce concrete types and can’t add/remove fields.
Instead, they spent massive amounts of time on private fields which most devs didn’t want (most pushback any JS feature has ever received by a large margin) AND one that completely breaks proxies which are used by all kinds of libraries.
Even Java is getting pattern matching before JS.
They’ve decided pipe operators are either going to be an abomination or they will be cancelled entirely. So of this completely disregards the opinions and use cases of the FO devs that will be using them.
This applies to all the FP proposals on their list. They get delayed, canceled, and neutered while niche or even bad features get implemented instead.
The compiler can trivially turn this into a jump, but the developer doesn't have enough context to construct any kind of loop:
function ap(f, v) { return f(v); }This matters for some styles of programming (callbacks/promises/monads/etc), but it's also very useful for code emitted by compilers and DSLs. It's much easier to encode complex control flow with CPS than just with the basic constructs JavaScript supports.
Even for hand-written code it can be pretty important. It's easy to imagine rewriting simple tail-recursive functions in an imperative style, but it quickly gets much harder, especially if your problem naturally decomposes into mutually recursive functions: that is, instead of a function calling itself, you have multiple functions calling each other, often with a bunch of additional computation between each call. I've run into this when writing parsers as well as custom algorithms for constraint-satisfaction kinds of problems. (Which are pretty common!)
That's because tail calls are structured gotos (with arguments). They're not really about recursion or even iteration.
> what is the advantage of [proper tail calls]?
There's a loss of expressiveness [1] without them, similar to the loss of expressiveness when there's no garbage collector.
> if [using proper tail calls] is almost always less performant, it probably isn't a very useful choice.
Don't assume PTC is less performant. There's no intrinsic reason for it to be. After all, the machine should be doing (slightly) less work: a goto instead of a call. Retrofitting it to an existing system can of course lead to a poor implementation, but it is not inherently a slow construct.
[1] Felleisen, Matthias. “On the Expressive Power of Programming Languages.” Science of Computer Programming, vol. 17, no. 1--3, 1991, pp. 35–75, https://doi.org/10.1016/0167-6423(91)90036-W .
That is, PTC doesn't just need to be powerful than other forms of call, it needs to be more useful day-to-day than other ways of writing the same logic. I think this article shows that, at least with the common recursive examples, that's rarely the case - it is pretty much always clearer and significantly quicker to use loops and Array methods than it is to rely on PTC and recursion.
You make a good point that there are uses for PTC outside of recursion, and that there are things you can do with it that can't be done with existing constructs. I'm sure that's true, but in my experience, the things people want to do with these tools tend not to fit well with the other features of Javascript, such as the high degree of mutation, and the dynamic nature of the language. At which point, it's probably more useful to create a compile-to-Javascript language instead that uses these sorts of features internally.
But with the rise of WASM (which has PTC as a proposal that I believe some groups have already implemented), it makes a lot more sense to use WASM as a target instead. There, you have a lot more control over exactly what gets executed and how, along with generally smaller and faster code. The exception right now is obviously DOM manipulation, but with the GC work being done right now, the path is opening up to getting easier access to the DOM directly in WASM.
Instead you could do some simpler example like factorial or fibonacci, which would usually run into a stack overflow, but due to Bun being based on JavaScriptCore not running into one.
At first I wanted to suggest to implement Dijkstra's algorithm for finding shortest paths from a specific node to all other nodes, but then I found a mutation in my own implementation for updating the distances and routes to nodes tables, so I did not want to suggest something I hadn't fully done myself.
But maybe, if you had something like functional hashes or similarly usable for the problem, you could do it. So I will link it here: https://notabug.org/ZelphirKaltstahl/guile-algorithms/src/83...
Note, that I put a "warning" in there, at the place, where it still uses mutation. Potentially this could hinder parallelization. Not sure if applicable in this specific problem, but in general, if you want to parallelize an algorithm, it not having any mutation makes it much easier to parallelize it and use our modern machines, which have multiple cores.
So shame on me for not having a mutation-free version yet ;)
Nicely put. TCO is a bit like a guitar solo: more fun to implement than it is useful/enjoyable to the intended recipients.
There's a lot of situations where recursive algorithms are really neat and clear. I don't know if this is the best example, but it shows the benefit of being able to split logic into a base case and a recurrence case.
But, in my experience, an algorithm that elegantly fits a recursive relationship is rarely one that naturally fits the tail-call paradigm. Often part of the benefit of recursion is that you can store state in the stack - the very thing you need to avoid to use TCO.
This means you often need to put in effort to create a tail recursive algorithm. But that often ends up looking a lot like the imperative case anyway - an accumulator outside the loop that you either mutate manually, or update in a tail call. And in my experience, the mutating, imperative version is usually then the easier to read and write (assuming you can keep mutations to a given scope, and not have that state leak all over the place). (In fairness, this might be more familiarity, though.)
In the light of this, what is the advantage of TCO? In functional languages without mutation, it's pretty important to allow for functions to act on arbitrarily-sized inputs without constantly growing the stack. But if we have mutation, it's really just a different way of writing the same code. And if that different way is generally less clear and almost always less performant, it probably isn't a very useful choice.
Which is why I think TCO hasn't really caught on in the other JS engines. It's a cool idea, and there's definitely a handful of cases where it's the useful way to go, but usually you'll be better served by writing things in the more traditional JS way.