Bun, JavaScript, and TCO(onsclom.net)
onsclom.net
Bun, JavaScript, and TCO
https://www.onsclom.net/posts/javascript-tco
170 comments
If you replace the ternary with an if then it's easy to understand for anyone who knows what ... means (which imo every JS developer should know)
const count = (amount: number) => {
if (amount > 0) {
return [...count(amount - 1), amount]
} else {
return []
};
}You missed the point entirely I’m afraid. It’s not about replacing the if with …, it’s about complexity.
The ubiquitousness of c-style makes it more familiar. But that doesn't make it better syntactically. And of course what's faster or more memory efficient is an implementation detail ultimately, but moving away from the imperative style opens up the opportunity for new and interesting -- and potentially more grokkable, ultimately -- patterns. Rust is actually a great example of this, with things like match and pattern matching.
Don't be such a language grinch.
Don't be such a language grinch.
Talk to me about lifetimes of Boxed RC Mutex then… because last time I checked, I had to do some insane amount of <T> to get a concurrent collection synchronized. I’m all for functional. Just don’t over use it in places where a simple function would suffice and try not to use it when dealing with recursive allocations of temporary arrays. Rust has come a long way but I feel like some of their style choices were to feel superior rather than make something functional. Go is a great example of simple, functional, but not quite as robust - as Rust.
> Look, I’m all for being clever when cleverness is needed but some of you JS/TS folks take it to the extreme.
To be fair, this is very much a toy example meant to demonstrate tail recursion- although I do agree it's not a great example considering you need to understand the evaluation order of ternaries in order to understand why one version is tail-recursive and the other isn't.
That being said: generally speaking, one might argue that using recursion at all is "too clever" and algorithms should just stick to iteration altogether. ¯\_(ツ)_/¯
> While you can nest a recursive function in a tertiary statement coro, don’t.
Man, why do you gotta call me out like this? :D
To be fair, this is very much a toy example meant to demonstrate tail recursion- although I do agree it's not a great example considering you need to understand the evaluation order of ternaries in order to understand why one version is tail-recursive and the other isn't.
That being said: generally speaking, one might argue that using recursion at all is "too clever" and algorithms should just stick to iteration altogether. ¯\_(ツ)_/¯
> While you can nest a recursive function in a tertiary statement coro, don’t.
Man, why do you gotta call me out like this? :D
>algorithms should just stick to iteration altogether
Well, if your algorithm performs 2 or more recursive calls per function invocation (like, say, quicksort), at least one of them needs to be an actual recursive call that uses additional stack space, since TCO is only able to mitigate a single recursive call per function invocation. (You could simulate your own stack and use iteration... but the only reason to do so in practice would be to escape some artificial restriction on native stack size.)
Well, if your algorithm performs 2 or more recursive calls per function invocation (like, say, quicksort), at least one of them needs to be an actual recursive call that uses additional stack space, since TCO is only able to mitigate a single recursive call per function invocation. (You could simulate your own stack and use iteration... but the only reason to do so in practice would be to escape some artificial restriction on native stack size.)
>”Man, why do you gotta call me out like this?”
Because you lose the stack trace most of the time. Only God and you know where the Uncaught PromiseRejection happened. It’s just really hard to debug when things go south. This drives me bonkers with the AWS sdk.
Because you lose the stack trace most of the time. Only God and you know where the Uncaught PromiseRejection happened. It’s just really hard to debug when things go south. This drives me bonkers with the AWS sdk.
If one is well-versed in functional programming, they would understand the above function just fine, plus it comes with all the benefits of functional versus imperative styles, which I will not repeat here as there are lots of articles on this. Perhaps JS devs should spend more time in functional codebases rather than imperative ones and they'll also get used to such code, and I for one am glad to see TCO making this style more efficient compared to traditional for-loops.
This style isn't efficient in JS, though, because it produces a ton of garbage to collect. TCO doesn't really make it more efficient, just possible.
[deleted]
> Perhaps JS devs should spend more time in functional codebases rather than imperative ones
the pure functional version takes 700x longer to run than the imperative version; maybe the wins of functional programming just aren't there in JS engines today.
the pure functional version takes 700x longer to run than the imperative version; maybe the wins of functional programming just aren't there in JS engines today.
[deleted]
If one was well-versed in memory management and how the stack would blow up in production one would not have to repeat them here.
Also, if you have to justify cleverness, it’s not clever. Don’t defend the style by grandstanding on “functional is better” or “you don’t know func bro”, how about ask why I feel the imperative style is more legible? Why would this not be the best way to write this? Where can I write this way? Or even “I find this style to be legible to me, but I’m curious about why you think it’s not”.
Also, if you have to justify cleverness, it’s not clever. Don’t defend the style by grandstanding on “functional is better” or “you don’t know func bro”, how about ask why I feel the imperative style is more legible? Why would this not be the best way to write this? Where can I write this way? Or even “I find this style to be legible to me, but I’m curious about why you think it’s not”.
It's not "clever" though, it's simply how functional programming languages like OCaml and Haskell work. You think imperative is more legible because you learned primarily from imperative languages, I'm assuming. If you had learned functional programming from the start of your programming life, then you'd find it perfectly legible.
I think there are cases where the functional style is more legible, but also cases where imperative style is more legible. I really think the imperative style is more legible in this particular case.
This is why Haskell and OCaml allow imperative constructs when they're more legible. I'll take an example from Learn You a Haskell[1]. In Haskell, one can implement a quick and dirty stack like this:
This is why Haskell and OCaml allow imperative constructs when they're more legible. I'll take an example from Learn You a Haskell[1]. In Haskell, one can implement a quick and dirty stack like this:
type Stack = [Int]
-- Throws exception on empty list/Stack
pop :: Stack -> (Int, Stack)
pop (x:xs) = (x, xs)
push :: Int -> Stack -> ((), Stack)
push a xs = ((), a:xs)
stackManip :: Stack -> (Int, Stack)
stackManip stack = let
((), newStack1) = push 3 stack
(_, newStack2) = pop newStack1
in pop newStack2
import Control.Monad.State
stackManip :: State Stack Int
stackManip = do
push 3
_ <- pop
pop
In this case, imperative with spread would be just as slow and no more readable.
The real issue is that this should have been wired up with an iterator. At that point, you aren’t using a for loop and your iterator might actually be faster with property tail calls.
The real issue is that this should have been wired up with an iterator. At that point, you aren’t using a for loop and your iterator might actually be faster with property tail calls.
You don’t know me or what I’ve learned or know so why presume? The clever bit is the recursive nature of it in addition that it’s functional. I’m pretty sure monads have existed longer than JavaScript and I’m perfectly comfortable reading functional code. The code in the example hides several onion layers of inefficiencies I think need/should/deserve to be called out. I’m not saying everything should be a class man. I’m saying not everything should be a clever one liner.
I’m surprised no one has brought up the fact that this code has quadratic time complexity when the underlying algorithm could be linear.
And the fact that it’s allocation behaviour is horrible, leaving behind ‘count-1’ garbage objects, count-squared garbage memory, and forcing the GC to chase after the algorithm.
I can accept this example as a contrived scenario to talk about TCO… but even in the presence of TCO one would not want to implement the function this way.
And the fact that it’s allocation behaviour is horrible, leaving behind ‘count-1’ garbage objects, count-squared garbage memory, and forcing the GC to chase after the algorithm.
I can accept this example as a contrived scenario to talk about TCO… but even in the presence of TCO one would not want to implement the function this way.
I wasn’t even going to dive into the allocations and garbage this style brings but it’s orders of magnitude slower, with more garbage created, disposed of, than a simple if statement. I’m glad you opened the can of worms. There are times when this doesn’t matter. Reading a config json, or performing your startup bootstrap, but if this was executed during a request or during a frame then you’re going to have a bad time.
The article doesn't explain why (and it should) but it does mention that this version is very slow and offers a version that doesn't have the same problems.
(I work on Bun)
A neat thing about tail calls in JavaScriptCore: there’s an explicit bytecode intrinsic for it.
When using this intrinsic, if any of the arguments are incorrect or it cannot otherwise enable it, the entire process will probably crash. In debug builds of JSC it will have a nicer assertion failure but that is not enabled in release builds
Example code: https://github.com/WebKit/WebKit/blob/17351231b4dedb62d81721...
also happy to answer any questions about Bun
A neat thing about tail calls in JavaScriptCore: there’s an explicit bytecode intrinsic for it.
return @tailCallForwardArguments(MyConstructor, this);
When using this intrinsic, if any of the arguments are incorrect or it cannot otherwise enable it, the entire process will probably crash. In debug builds of JSC it will have a nicer assertion failure but that is not enabled in release builds
Example code: https://github.com/WebKit/WebKit/blob/17351231b4dedb62d81721...
also happy to answer any questions about Bun
When do you see AWS Lambda supporting Bun, if ever?
You can use it today with containers in Lambda or a custom Lambda runtime, but both approaches have embarrassingly slow cold start. Lambda has special optimizations for Node which are not possible without official support.
I have no idea when Lambda would add an official runtime layer. But if you work at Lambda and are interested, feel free to email me - [email protected]
I have no idea when Lambda would add an official runtime layer. But if you work at Lambda and are interested, feel free to email me - [email protected]
Love bun, thank you so much Mr. Sumner.
What is the priority of app router integration for NextJS?
What is the priority of app router integration for NextJS?
After Windows support is further along, but not that long from now
> What is the priority of app router integration for NextJS?
I'm not Jarred, but what do you mean by this? I'm using bun + app router + NextJS and everything seems to work just fine.
I'm not Jarred, but what do you mean by this? I'm using bun + app router + NextJS and everything seems to work just fine.
On https://bun.sh/guides/nextjs it says that bun currently does not implement the API to run the dev server.
Not OP, but interested: can you deploy on a vps having only bun and not node?
Yes
I don't think you're talking about what GP comment is.
For clarification, Bun can act as a package manager like npm (probably the case of "bun + app router + NextJS" comment), and it can act as a replacement to a node runtime a la Express on a VPS (I'm assuming this is what you mean by "yes"). But Bun currently does not implement enough of the Node API's to use Bun as the runtime for a Next.js app.
From Bun themselves: "The Next.js App Router currently relies on Node.js APIs that Bun does not yet implement. The guide below uses Bun to initialize a project and install dependencies, but it uses Node.js to run the dev server."
https://bun.sh/guides/ecosystem/nextjs
For clarification, Bun can act as a package manager like npm (probably the case of "bun + app router + NextJS" comment), and it can act as a replacement to a node runtime a la Express on a VPS (I'm assuming this is what you mean by "yes"). But Bun currently does not implement enough of the Node API's to use Bun as the runtime for a Next.js app.
From Bun themselves: "The Next.js App Router currently relies on Node.js APIs that Bun does not yet implement. The guide below uses Bun to initialize a project and install dependencies, but it uses Node.js to run the dev server."
https://bun.sh/guides/ecosystem/nextjs
[deleted]
I think this article actually does a really good job of explaining why TCO hasn't really been an important part of the JS ecosystem.
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.
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.
Tail calls also matter for code in continuation-passing style (CPS).
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!)
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!)
Regardless, it has been approved as part of JavaScript specification and Chrome folks refuse for political reasons to implement it, which given the market domination everyone has helped them achieve is a bummer.
Firefox have also chosen not to implement it, right? Indeed, my impression was that Firefox were far more against the whole thing than Chrome, who did implement TCO but then removed it for various reasons.
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.
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.
Firefox no longer matters, hence why I left it out.
1. Complain about market dominance.
2. Any 2% of the market doesn't matter.
3. …
2. Any 2% of the market doesn't matter.
3. …
Yes, those 2% only came to be because of folks pushing Chrome and Electron all over the place.
Now it is too late to save Firefox.
Now it is too late to save Firefox.
Right.
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?
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?
They said it was too hard, but now they’re adding it because of wasm, so their objection doesn’t matter.
I left the spidermonkey team a while back but was there when this issue came up and I was strongly against implementing support for it. For me it wasn’t about it being “too hard” (implementation difficulty wouldn’t have been that bad actually).
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?
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?
Most likely because FP languages that have as part of the language specification don't have special syntax for it, it just works, and the debuggers are able to provide a good debugging experience.
The only FP languages that require explicit syntax, target the JVM, which lacks the support.
The only FP languages that require explicit syntax, target the JVM, which lacks the support.
It wouldn't just work for javascript and the way it's used, though. It modifies semantics in a way that would affect the behaviour of existing programs in production environments. It would break things that currently work, and it would break tooling that currently works.
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.
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.
It might give different tooling output, but the tooling wouldn’t break. Likewise, the only side effect of the code itself is that some of it would get faster because functions wouldn’t need to return.
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.
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.
SpiderMonkey is still used in over 2% of the browser market share, and is used in non-Firefox applications too. I'd say it matters.
Sadly it doesn't, in many places being so low means the project acceptance matrix for target browsers no longer needs to contemplate Firefox.
Usually though when people make shit websites or products, needlessly not adhering to browser standards that would easily work in basically all modern browsers, because they cannot be bothered or don't have a clue what they are doing.
I find it surprising that the JS specification also includes optimizations an engine should implement. I'm not sure how difficult TCO is to implement, but I just checked if QuickJS supports it or not and it seems to be one of the few ES2020 omissions the author chose to make: https://bellard.org/quickjs/quickjs.pdf (3.1.1). This tells me it might be non-trivial to implement which if true makes the decision to make it a part of the specification all the more surprising, because that means the specification restricts the types of trade-offs implementers can make when attempting to achieve full compatibility. In other words, until today I was under the impression you could make a fully ES compatible engine, but choose to make it slow for implementation ease. Looks like the spec defines the floor for how (non)-performant the engine implementation can be in some cases. Is this common in other languages' specs?
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.
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.
There’s a bit of a naming confusion around tail calls, but in any case “proper tail calls”, let’s call them that, are not precisely an optimization: they are a guarantee that any number of recursive calls of a certain kind will result in constant and not linear memory consumption. This permits some kinds of programming that can otherwise be quite awkward. If your program takes advantage of them (as e.g. often happens in Scheme), having tail calls is not an optimization issue, it’s an implementation correctness issue.
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.)
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.)
TCO isn't really an optimisation per se, at least in the sense that optimisations typically aren't observable as part of the semantics of a language. TCO does affect the semantics; it says that a recursive function that recurses only using tail calls will never overflow the call stack. That's why it's something that might get specified in the specification rather than just left as an implementation detail: it's the sort of implementation detail that developers might actually rely on.
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.
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.
There's another consideration, you can introspect the stack using Error.stack (also Function.caller and friends?). It requires a spec change to say "it's okay to not not includes these stack frames in specific cases". This information would also presumably not show up in the devtools / debugger or sentry, etc.
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.
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.
This solvable enough by activating a shadow stack. You can also just note on the trace pretty cheaply that X function was called by a tail call function. This eliminates any ambiguity about what happened.
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.
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.
Scheme (what JavaScript was based on) also requires tail call optimizations as part of its spec.
> I find it surprising that the JS specification also includes optimizations an engine should implement.
Algorithmic complexity is an essential part of defining an interface.
Algorithmic complexity is an essential part of defining an interface.
[deleted]
What "political" reasons?
My understanding of the situation is that it's entirely technical issues that came up after implementing.
My understanding of the situation is that it's entirely technical issues that came up after implementing.
Yes, what's really important here is that TCO was added to the spec before the modern TC39 process was adopted. Had implementation and usage experience been required before it shipped in the spec, this conversation would have been concluded 9 years ago.
I think the most cited reason they give is diminished developer experience. That is when developers write a recursive function without intending it to be tail call optimized, they loose their call stack. In theory this makes debugging harder. However I don’t—and others interested in JavaScript design—don’t buy this reasoning. There is little—if any—data showing this happens to developers in real life.
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.
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.
Having worked on debuggers in JS land I can tell you that it would generate lots of bug reports.
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!
¯\_(ツ)_/¯
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!
¯\_(ツ)_/¯
Safari has enabled proper tail calls for 8-9 years now and they haven’t caused issues despite Safari having 20% of the worldwide browser market.
I guess Safari doesn’t have this large a share of developers, who are the main concern here. But I guess we will truly see if this is an issue as Bun increases in popularity.
The major Google "objection" was automated trace loggers. When something goes wrong, they grab the stack trace and ship it off to the developers.
In this particular case, devs definitely see the Safari traces when bugs pop up.
In this particular case, devs definitely see the Safari traces when bugs pop up.
I feel like it could be represented in the trace or the debugger or both and eliminate everyone issues.
Devs definitely don’t like surprises, but also absolutely hate their tools not telling the truth.
Devs definitely don’t like surprises, but also absolutely hate their tools not telling the truth.
Sadly I sense something amuck against the functional paradigm as well.
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.
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.
There were no technical arguments from Google. They implemented tail calls and performance was fine. Furthermore, wasm required them to add the functionality back to the jit.
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.
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.
Anything to do with tail calls in WASM is likely to be completely irrelevant to proper tail calls in ECMAScript: they’ll be separate pieces of code with different reasons and balances.
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.
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.
WASM runs in v8 on Chrome. If you have to implement the bytecode for one, it should work for both. Chrome used to have semantic tail calls for JS implemented too.
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.
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.
> Firefox complained that it was work
LOL, as they do.
LOL, as they do.
[deleted]
> an algorithm that elegantly fits a recursive relationship is rarely one that naturally fits the tail-call paradigm.
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'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 .
To be clear, I'm not talking about PTC/TCO in general in this comment, I'm talking about it specifically in the context of Javascript, and in the context of the common patterns of Javascript usage.
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.
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.
The article does not show much except TCO existing with Bun and JavaScriptCore. It uses a not very suitable mutable data structure to mutate it in each iteration. I would say for that example it is almost better to use the for loop, since it looks very imperative anyway and using recursion to do mutating procedure calls does not give much benefit. It is a not so well chosen example.
That's mostly the point I'm trying to make! What would you see as a more convincing example of TCO in this context?
Perhaps an example using a persistent functional data structure would be good, but probably also more complex.
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 ;)
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 ;)
I don’t think the example is particularly good. TCO is essential in functional programming, where recursion shines, but the example given is an impure function which mutates its input parameter by calling Array.prototype.push. Basically, this isn’t a demonstration of the paradigm for which TCO is required.
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.
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.
I agree that TCO is essential in functional languages where loops and mutability are disallowed or at least heavily discouraged, but Javascript is not one of those languages. In Javascript, both mutation and and loops are very simple, and as I think the article demonstrates, often the clearest ways to express an idea.
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.
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.
I agree with everything you wrote.
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.
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.
I don't think it's the lack of TCO that's the thing holding JS back from getting the next great functional language. There's no structural pattern matching, there's no immutable data structures, there's nothing in the way of convenient syntax sugar like currying.
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.
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.
TC39 hates FP.
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.
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.
It’s a shame, because records and tuples are enormously helpful when trying to optimize React, given how it uses reference equality on objects to bust memoization.
I think it’s not as widely recognized as it could be just how forward-looking ECMAScript was in introducing language updates in the mid 2010s. For instance, arrow functions make it natural to work with partial application, a currying-adjacent technique.
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.
const times = a => b => a * b
const double = times(2)
const twiceFour = double(4)
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 Haskell, all functions are syntactically and semantically curried. That is, a function that takes two arguments is essentially identical to a function that takes one argument, and returns a new function that returns a second argument. (In fairness, part of this is the laziness of Haskell, and a language like OCaml which also uses currying behaves slightly differently, but still similarly enough.) The `curry` function is not a library implementation of currying, it's a way of unpacking tuples into arguments.
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.
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.
JS works alright with currying, but I think manual currying is the best way to do it with the language (and it's not that inconvenient).
[deleted]
Shout out to F# in the browser via Fable too.
I was looking for an alternative to rescript and literally just started looking at Fable this week - and absolutely love it in conjunction with Elmish.
The real problem, of course, is that in the cases where compiler-based TCO is possible, the user can trivially refactor the function to use a loop.
This is not true.
The compiler can trivially turn this into a jump, but the developer doesn't have enough context to construct any kind of loop:
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); }>I think this article actually does a really good job of explaining why TCO hasn't really been an important part of the JS ecosystem.
Nicely put. TCO is a bit like a guitar solo: more fun to implement than it is useful/enjoyable to the intended recipients.
Nicely put. TCO is a bit like a guitar solo: more fun to implement than it is useful/enjoyable to the intended recipients.
> Recursion takes up precious memory on the call stack! There may be commands to increase the call stack size for your program, but there is only so much the OS will allow. Memory on the heap is much less restricted.
This reasoning implies that tail call optimization is some sort of memory-segmentation workaround. This isn't accurate.
A (non-TCO) recursive approach is more expensive because it uses O(n) bookkeeping memory, whereas the iterative approach uses O(1) memory. Naive recursion will allocate a stack frame for each "iteration", whereas the loop approach will not allocate anything per iteration.
So, the iterative approach simply uses much less memory for large iteration counts; the placement of the memory in stack space or heap space isn't the relevant factor.
This reasoning implies that tail call optimization is some sort of memory-segmentation workaround. This isn't accurate.
A (non-TCO) recursive approach is more expensive because it uses O(n) bookkeeping memory, whereas the iterative approach uses O(1) memory. Naive recursion will allocate a stack frame for each "iteration", whereas the loop approach will not allocate anything per iteration.
So, the iterative approach simply uses much less memory for large iteration counts; the placement of the memory in stack space or heap space isn't the relevant factor.
But without TCO, even if your function doesn't have any state of it's own, it will use memory on the call stack. I don't think anything about what they said implied memory segmentation was the problem.
It's pretty clear they mean each recusion increases the size of the call stack without TCO.
Agreed, I think the mention of heap space was more to answer the question of someone new to this topic of "but wait, I can allocate gigabytes of data in an array, why can't I allocate 100,000 stack frames?"
This is not actually about Tail Call Optimisation, which is more flexible and optional matter of optimisation, but about Proper Tail Calls, which are a guarantee made in the ECMAScript 6 specification (over implementer concerns objections)—in strict mode, calls in tail position must not create additional stack frames. This is the last piece of ECMAScript 6 that most engines haven’t implemented, because it’s rather controversial: it actually causes some performance problems, and makes debugging harder, and may have security issues (in 2016, Mozilla declared it impossible to implement across realm boundaries due to their security model).
https://github.com/tc39/proposal-ptc-syntax has a lot of useful information about it all, and a proposal to make it explicit in syntax, such as with `return continue …`, though I don’t believe that’s really gone anywhere. The practical situation is that this is the one part of the ECMAScript spec that most implementers ignore, and thus which you can’t depend on. Which says to me that it should either be made optional or be removed from the spec. Not sure if there are any other features similarly disregarded. ECMAScript specification policy was different in those days, they operated more independently of implementers. (HTML was like that once too—that’s roughly why WHATWG was formed, because the actual implementers weren’t happy with how things worked in W3C, so they took matters into their own hands.)
(Fun terminology problems here. The term TCO is commonly used for PTC, and PTC is very close to being a subset of TCO, but the mandatory stack frame elision which ruins debugging feels to me like it falls outside of TCO. In various situations, debuggers will mark things like “stack frame omitted” when they’ve optimised one out of existence, but you can generally compile things differently, or something like that, to prevent this. (Compiled/dynamic language variation showing up here.) But with PTC, it feels like the engine is kinda not even allowed to know that a stack frames may be absent. So I say PTC and TCO are a little distinct, though PTC is mostly just a subset of TCO. Reminds me of the terminology of tree-shaking versus dead code removal—where the former is essentially a subset of the latter, but that the effects are just slightly different, though I’d say it’s more slight in that case than this.)
https://github.com/tc39/proposal-ptc-syntax has a lot of useful information about it all, and a proposal to make it explicit in syntax, such as with `return continue …`, though I don’t believe that’s really gone anywhere. The practical situation is that this is the one part of the ECMAScript spec that most implementers ignore, and thus which you can’t depend on. Which says to me that it should either be made optional or be removed from the spec. Not sure if there are any other features similarly disregarded. ECMAScript specification policy was different in those days, they operated more independently of implementers. (HTML was like that once too—that’s roughly why WHATWG was formed, because the actual implementers weren’t happy with how things worked in W3C, so they took matters into their own hands.)
(Fun terminology problems here. The term TCO is commonly used for PTC, and PTC is very close to being a subset of TCO, but the mandatory stack frame elision which ruins debugging feels to me like it falls outside of TCO. In various situations, debuggers will mark things like “stack frame omitted” when they’ve optimised one out of existence, but you can generally compile things differently, or something like that, to prevent this. (Compiled/dynamic language variation showing up here.) But with PTC, it feels like the engine is kinda not even allowed to know that a stack frames may be absent. So I say PTC and TCO are a little distinct, though PTC is mostly just a subset of TCO. Reminds me of the terminology of tree-shaking versus dead code removal—where the former is essentially a subset of the latter, but that the effects are just slightly different, though I’d say it’s more slight in that case than this.)
Related: Guido van Rossum's argument for why there is no TCO in Python.
https://neopythonic.blogspot.com/2009/04/final-words-on-tail...
https://neopythonic.blogspot.com/2009/04/final-words-on-tail...
TCO in this article = Tail Call Optimization, not Total Cost of Ownership.
It makes the article more interesting!
It makes the article more interesting!
Actually, as a chiefly Java/C# person, I was hoping for the article to cover how Bun helps lower the Total Cost of Ownership of Javascript projects by helping to get off the hamster wheel of infinitely deep npm dependency trees, wild west of constant project deprecations and major version releases with immediate deprecation of previous versions, daily game of CVE alert whack-a-mole etc. Preferably, short of writing all the code yourself.
I also assumed the other TCO when I clicked through, which would have been an interesting take to read for sure (particularly since Bun is so new, so I was wondering how much data would be backing this analysis), but I'm not a strong functional programmer so any time someone covers functional-adjacent topics, it's interesting to me!
I'm with you on wanting to learn and explore more about Bun's main advantages though, the bundled tooling and some of the convenience APIs feel like well-planned time/effort/maintenance optimizations.
I'm with you on wanting to learn and explore more about Bun's main advantages though, the bundled tooling and some of the convenience APIs feel like well-planned time/effort/maintenance optimizations.
It's also not Tjänstemännens Centralorganisation, the largest white collar union in Sweden, and also the org behind the TCO labelling of computer monitors.
If you google TCO, at least where I am (North America), "Total Cost of Ownership" is the first result - and the dominant one on the first page of results.
It's also the main definition of TCO that most people are probably familiar with, me included.
This felt like a reasonable clarification to make.
It's also the main definition of TCO that most people are probably familiar with, me included.
This felt like a reasonable clarification to make.
I guess for anyone interested in Bun and Javascript, it would be more obvious.
User what does "TCO" mean in " Bun, JavaScript, and TCO"
ChatGPT "TCO" in "Bun, JavaScript, and TCO" refers to "Tail Call Optimization."
User what does "TCO" mean in " Bun, JavaScript, and TCO"
ChatGPT "TCO" in "Bun, JavaScript, and TCO" refers to "Tail Call Optimization."
Usually not for JS people, because they don't get to use recursion much, due to decisions by browser makers. More likely that people from other, usually FP languages think of the actual meaning it has in the article or in the computer programming world.
[deleted]
It's nice, but the downside is that relying on TCO can make your Bun-tested code unexpectedly break with stack overflow error if it ever gets run on Deno or Node. So probably a good idea to comment this part of the code and make sure if it's in a library to similarly warn the callers somehow.
Yes the O is more than an Optimisation,
it is a change in semantics.
Does serverside JS have anything similar to #ifdef?
Yes. You can define a constant (eg IS_SERVER) which your bundler (eg esbuild) replaces with a specific value depending on what environment you’re targeting. There are also ways to detect it using runtime globals that are only defined within the browser although that can be monkeypatched by your own code or 3p libraries you import (not common but could be a compat layer you add to make server side JS behave more like a browser).
Something like
if ('Bun' in globalThis) ...
if ('Deno' in globalThis) ...
if ('window' in globalThis) ...
That certainly works for Bun and Deno, not sure about what is effective in Node, though.
Checking for process.versions.{node,bun} works, not sure if Deno has an equivalent.
[deleted]
> [The tail call optimized] function is starting to look a lot like the orignal for loop solution. It’s not very succinct or elegant anymore.
(Brackets mine.)
I don't know about succinct but I definitely like how it looks a lot more. It's very readable, while the ternary operator one looks illegible at that length. It looks shoehorned in. It's the programming language equivalent of trying to mumble a whole sentence in two syllables.
(Brackets mine.)
I don't know about succinct but I definitely like how it looks a lot more. It's very readable, while the ternary operator one looks illegible at that length. It looks shoehorned in. It's the programming language equivalent of trying to mumble a whole sentence in two syllables.
Yes, every language should have if-expressions. Don't know what they were thinking with the ternary operator.
One reason I've heard for the statement vs expression distinction, where one deliberately makes a mess of the syntax uniformity, is that it helps diagnostics of programming errors.
That is, by demanding spurious restrictions on syntax and generally making code more annoying to write, you get to detect more constructs as probably bad.
Line noise - semicolons in C, colons in python - is the same idea. Earlier diagnostics of code that probably wasn't intended.
I don't find this remotely compelling as a language design choice but it's the best justification I've come across for why so many have the extra obfuscation between programmer and AST.
Specifically, why would one optimise for ease of reading invalid code instead of for ease of reading valid code. Madness. But popular.
That is, by demanding spurious restrictions on syntax and generally making code more annoying to write, you get to detect more constructs as probably bad.
Line noise - semicolons in C, colons in python - is the same idea. Earlier diagnostics of code that probably wasn't intended.
I don't find this remotely compelling as a language design choice but it's the best justification I've come across for why so many have the extra obfuscation between programmer and AST.
Specifically, why would one optimise for ease of reading invalid code instead of for ease of reading valid code. Madness. But popular.
ternary is not the important part here, could write it with if and early return too.
TCO should be table stakes. An interpreter can do it by noticing that the next thing is a call to itself (the interpreter), a compiler by reorganising the stack frame before the jump.
Lots of stuff gets in the way. Destructors, varying type signatures, calling conventions. But for the case where it can happen, it should be considered an implementation error that it does not. Very like a space leak.
edit: this ^ was evidently unclear - tail call support in an interpreter means recognising when the interpreter is about to call the interpreter and jumping there, e.g. in an eval-apply setup, you use one frame for the eval-apply-eval-apply skeleton and only spawn more for evaluation of function arguments.
Tail call support in an compiler involves changing the calling convention to clean up before jump. At that point it's all jumps, whether back to the top of a loop or to some other basic block, because all the world is SSA to a pretty good approximation.
Neither of those makes any meaningful distinction between calls-to-self, calls-to-sibling, calls-to-indirect and so forth. The TCO is easier on self calls idea comes from languages where it is hacked before the compiler backend in a setting where goto isn't allowed to cross function boundaries. Some C code will have a label at the top named "self" or similar and use `goto self;` to force the equivalent of a tail call, some compiler stacks implement TCO by a mechanical version of the same hack and thus can't deal with it crossing between different functions.
edit2: If you're compiling to a target with restrictions on calling convention that preclude cleanup before jump (and doesn't sort this out itself) you are out of luck. Pick a better target or live in the doomed world you've created. See e.g. https://v8.dev/blog/wasm-tail-call for some stuff on wasm trying to fix itself, I haven't kept up to date with whether they did or not.
Lots of stuff gets in the way. Destructors, varying type signatures, calling conventions. But for the case where it can happen, it should be considered an implementation error that it does not. Very like a space leak.
edit: this ^ was evidently unclear - tail call support in an interpreter means recognising when the interpreter is about to call the interpreter and jumping there, e.g. in an eval-apply setup, you use one frame for the eval-apply-eval-apply skeleton and only spawn more for evaluation of function arguments.
Tail call support in an compiler involves changing the calling convention to clean up before jump. At that point it's all jumps, whether back to the top of a loop or to some other basic block, because all the world is SSA to a pretty good approximation.
Neither of those makes any meaningful distinction between calls-to-self, calls-to-sibling, calls-to-indirect and so forth. The TCO is easier on self calls idea comes from languages where it is hacked before the compiler backend in a setting where goto isn't allowed to cross function boundaries. Some C code will have a label at the top named "self" or similar and use `goto self;` to force the equivalent of a tail call, some compiler stacks implement TCO by a mechanical version of the same hack and thus can't deal with it crossing between different functions.
edit2: If you're compiling to a target with restrictions on calling convention that preclude cleanup before jump (and doesn't sort this out itself) you are out of luck. Pick a better target or live in the doomed world you've created. See e.g. https://v8.dev/blog/wasm-tail-call for some stuff on wasm trying to fix itself, I haven't kept up to date with whether they did or not.
TCO is about more than self-recursive calls -- you should be able to handle mutual recursion:
Note that if I changed this to, say, 1 + g(x - 1), this would no longer fall under the purview of tail recursion, where the last instruction before the return is a recursive call.
The usual workaround I learned in my SICP days was to add a second variable for accumulating any results. And, indeed, that's how the blog post rewrites the recursive function.
(The recursive one-liner is still wildly inefficient because JS doesn't implement arrays as linked lists, so the spread operator results in a copy for each recursive call, resulting in a quadratic solution. It could be made more efficient by using Array.prototype.push, but then it's no longer a pure function.)
f = x => x > 0 ? g(x - 1) : 0;
g = x => x > 0 ? f(x - 1) : 0;
Note that if I changed this to, say, 1 + g(x - 1), this would no longer fall under the purview of tail recursion, where the last instruction before the return is a recursive call.
The usual workaround I learned in my SICP days was to add a second variable for accumulating any results. And, indeed, that's how the blog post rewrites the recursive function.
(The recursive one-liner is still wildly inefficient because JS doesn't implement arrays as linked lists, so the spread operator results in a copy for each recursive call, resulting in a quadratic solution. It could be made more efficient by using Array.prototype.push, but then it's no longer a pure function.)
I don’t think they picked the best example to showcase this, most JavaScript developers would write this simply as:
Array.from({ length: n }, (_, i) => i + 1)
TCO is broader than tail calls to the same function, but tail calls to the same function would certainly be a start.
Implicit tail-call elimination outside the context of tail-recursive algorithms causes behavior that is surprising to programmers working in languages where stack traces are used for debugging (i.e. it removes frames from the stack and obscures the path of execution).
the reason TCO is not implemented in V8, iirc, is because of developer experience and needing devtools to faithfully dump the call stack that hasnt been flattened, because that's what's expected of js DX.
does JSC's implementation solve this? do they exhaust the stack only when devtools are open, or smth? maybe they just keep the last 10 frames in memory for devtools? (that would make most sense to me)
does JSC's implementation solve this? do they exhaust the stack only when devtools are open, or smth? maybe they just keep the last 10 frames in memory for devtools? (that would make most sense to me)
This is a silly justification I think, in the sense that V8 could implement this in a way that can provide stack traces for all stacks that are short enough for a human to browse while also executing programs that use tail calls as goto correctly.
See [1] (Filip's commit message introducing ShadowChicken is also quite well written if a bit more technical [2]).
[1] https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-...
[2] https://bugs.webkit.org/attachment.cgi?id=274533&action=revi...
[1] https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-...
[2] https://bugs.webkit.org/attachment.cgi?id=274533&action=revi...
This is a solved problem on programming languages where it is part of the specification, like Scheme.
Basically the debugging info and what actually happens isn't 1:1, rather the logical model of the execution.
Basically the debugging info and what actually happens isn't 1:1, rather the logical model of the execution.
The performance difference is not just about TCO, but about creating a new array on each iteration instead of reusing the old one... in Lisp, because it uses cons cells which share structure, appending is very efficient, so the recursive code runs as fast as it can get... not so much with JS arrays.
ECMAScript continues to evolve and I suspect that there would have been an effort to make the spread operator into a sort of cons in JavaScript. It could have worked for both arrays and objects. However, after seeing that the entry-level bar of proper tail calls couldn’t make it out the door for Chrome and V8, they might have decided not to push it and risk further divergence from a major implementation.
Isn't prepending the efficient operation? Appending would require mutation or copying, prepending only requires a single new cons cell.
Appending to a linked list is fine if you can mutate and keep a pointer to the tail, but then again, extending mutable arrays is also amortized O(1) assuming a reasonable allocation scheme.
Appending to a linked list is fine if you can mutate and keep a pointer to the tail, but then again, extending mutable arrays is also amortized O(1) assuming a reasonable allocation scheme.
The common pattern in LISP is to prepend using cons and then reverse the list at the end if order matters.
Check this program as an example: http://www.norvig.com/java-lisp.html
Recursion is done with `(cons (nth-digit digits start) words)` and recursion ends with `(format t "~a:~{ ~a~}~%" num (reverse words))`.
Check this program as an example: http://www.norvig.com/java-lisp.html
Recursion is done with `(cons (nth-digit digits start) words)` and recursion ends with `(format t "~a:~{ ~a~}~%" num (reverse words))`.
Another common pattern is to keep track of the last cons and add there. This saves the reverse operation. (loop for i in some-list when (evenp i) collect i) will do something like that behind the scenes.
I don't understand how that works. (reverse) changes every cons cell in order to make each cell point in the "opposite" direction. Do you have a reference I can check?
Imagine, we want to write a function which returns a list of numbers from 0 below N. This is just an illustration of the iteration principles.
One could use a numeric loop, push each number to the front and return the reversed result list:
One could use a numeric loop, push each number to the front and return the reversed result list:
(defun iota (n &aux result)
(dotimes (i n (nreverse result))
(push i result)))
(defun iota (n &aux (result (list nil)) (pointer result))
(dotimes (i n (cdr result))
(setf (cdr pointer) (list i)
pointer (cdr pointer))))
Oh I see. You keep track of the last cons * on each iteration * :) (this last bit was missing). Interesting, thanks for showing it.
> Languages that rely on recursion like LISPs often specify that TCO must be implemented in their language spec.
This is inaccurate. As far as I can tell, it's only Scheme specifications like r5rs that have a hard requirement on tail-call optimization. The Common Lisp specification makes no mention of tail-call optimization, and Clojure -- arguably the most widely used Lisp today -- does not have it either (but it has special forms and macros that let you write recursive code and produce trampolines, thunks, etc. to avoid blowing up the stack).
With that said, at least in the case of Common Lisp, it is true that many compilers will implement TCO, even though it is *not* required at all to conform to the specification.
This is inaccurate. As far as I can tell, it's only Scheme specifications like r5rs that have a hard requirement on tail-call optimization. The Common Lisp specification makes no mention of tail-call optimization, and Clojure -- arguably the most widely used Lisp today -- does not have it either (but it has special forms and macros that let you write recursive code and produce trampolines, thunks, etc. to avoid blowing up the stack).
With that said, at least in the case of Common Lisp, it is true that many compilers will implement TCO, even though it is *not* required at all to conform to the specification.
Common Lisp is not a Lisp which 'relies on' recursion. It has various loop statements (DO, DOTIMES, DOLIST, ...), various mapping functions (map, mapcar, mapc, maphash, ...) and a complex LOOP. To prevent stack overflows those can all be built on top of a goto operator (tagbody + go). One of the reason was that compilation targets (cpus, virtual machines, other languages, ...) don't have native TCO support. For example the various Lisp Machines had no TCO support, and many C compilers did not support TCO for quite some time. C is a popular compilation target (KCL, AKCL, ECL, CLASP, CLICC, ... were (some are) all Lisp to C compilers).
> With that said, at least in the case of Common Lisp, it is true that many compilers will implement TCO, even though it is not required at all to conform to the specification.
The specification does not require it, it actually says nothing about it. TCO isn't even mentioned. Means, it also says nothing how a compiler should support it, if it wanted to. The language supports recursion, but something like tail recursion support is entirely an implementation specific optimization. Since TCO has some advantages (less stack space needed, possibly some faster loops, ...), many compilers implement it, but mostly no interpreter does it.
Also, most of them support GC, even though exactly nothing is said about it in the specification. ;-)
> With that said, at least in the case of Common Lisp, it is true that many compilers will implement TCO, even though it is not required at all to conform to the specification.
The specification does not require it, it actually says nothing about it. TCO isn't even mentioned. Means, it also says nothing how a compiler should support it, if it wanted to. The language supports recursion, but something like tail recursion support is entirely an implementation specific optimization. Since TCO has some advantages (less stack space needed, possibly some faster loops, ...), many compilers implement it, but mostly no interpreter does it.
Also, most of them support GC, even though exactly nothing is said about it in the specification. ;-)
While working on effection@v3 (https://github.com/thefrontside/effection) we spent a bunch of time ensuring that our delimited continuations could handle deep recursive call stacks in Deno.
PR: https://github.com/thefrontside/continuation/pull/11
TCO would have definitely simplified this issue.
What’s worse is hitting maximum memory callstack exception is very tricky to catch and is not reliable across runtimes. So when a user hits it it can be tricky to track down.
PR: https://github.com/thefrontside/continuation/pull/11
TCO would have definitely simplified this issue.
What’s worse is hitting maximum memory callstack exception is very tricky to catch and is not reliable across runtimes. So when a user hits it it can be tricky to track down.
This isn’t a good thing if your fancy recursion code works great on bun but is slow in other js runtimes.
Seems fine if you actually run it on bun.
TCO is cool. I remember how enlightening it felt when I studied Scheme and came to understand how it's implemented there.
If this is not what you're referring to, you might be interested in CHICKEN Scheme's implementation, which is unlike any other I've seen: instead of compiling tail calls to jumps, they are just regular calls, and the call stack is effectively garbage collected when it would overflow.
Agreed. Scheme taught me that function invocations didn't have to be sullied with the risk of stackoverflow, and in-fact what appeared to be recursive was actually iteration and loop constructs were not needed.
So the optimization here is that instead of creating a new array every time you call the count function recursively, you're only modifying a single array. Thus the new array recursive function is significantly slower because we're storing all those arrays in memory when calling the count function recursively. Do I have that right?
Based on the title, I was hoping for a TCO (Total Cost of Ownership) analysis on Bun/Javascript.
Or the cost of running a company’s architecture on a “new” (not really new, but quickly evolving re: frameworks) JavaScript.
Or the cost of running a company’s architecture on a “new” (not really new, but quickly evolving re: frameworks) JavaScript.
I gave bun a test with react apps and found that it installs node_modules much much faster, but starting up a react dev server took the same time
I spent the first year or two of my career thinking I needed to Do Recursion because thats what the textbooks said and hey, the language supports tail calls!
I learned, in the sense you learn by touching a hot stove, that:
A) you can't guarantee the compiler sees it as a tail call and optimizes it.
B) you are now open to a stack overflow appearing in your software at any given point due to compiler changes / your own changes that confuse the compiler, etc.
C) qed, don't do tail calls.
I learned, in the sense you learn by touching a hot stove, that:
A) you can't guarantee the compiler sees it as a tail call and optimizes it.
B) you are now open to a stack overflow appearing in your software at any given point due to compiler changes / your own changes that confuse the compiler, etc.
C) qed, don't do tail calls.
Both Scala3 and Kotlin allow you to annotate functions with @tailrec which will give you a compiler warning if the compiler can’t optimize. And if you use the xfatal-warn compiler flag the Scala code won’t compile if your function is not tail call.
Iterating over tree structures is a pain without recursion, but that's the only situation where I feel I need recursion.
I don't think you can use tail call recursion for tree walking unless you also manually maintain another stack. And at that point iterative code looks just as readable
>"I spent the first year or two of my career thinking I needed to Do Recursion because thats what the textbooks said"
Being an old fart I've learned long ago to not follow self declared prophets. Recursion is a trade off that comes with the cost. Sometimes it makes sense to use it and sometimes (most of the times) it does not. You do what makes you and your customers happy.
Being an old fart I've learned long ago to not follow self declared prophets. Recursion is a trade off that comes with the cost. Sometimes it makes sense to use it and sometimes (most of the times) it does not. You do what makes you and your customers happy.
Is it just me but I never use recursion in JS (or imperative languages generally) and it never really comes up as a need?
For example if you write a json deserializer that's generic over the struct you want to deserialize to (or one in JS that returns a JS object), you'll usually use some sort of recursion. My generic radix sort[0] also has recursion in it, which seems like the most straightforward way to write it, but of course any recursive function could be mechanically converted to one that does not use recursion.
[0]: https://github.com/alichraghi/zort/blob/main/src/radix.zig#L...
[0]: https://github.com/alichraghi/zort/blob/main/src/radix.zig#L...
We’re using recursion at $company to validate user inputs because it’s a user-defined tree of unknown depth.
Nitpick: JS is multi-paradigm.
Yeah I should have been more specific. I mean languages where recursion is idiomatic for many problems because the language is purely functional like Haskell.
Optimization and functional recursion is nice and all, but the unsung killer-feature of (mandatory) TCO is to (ab)use the stack as a state-machine. Each "state" is a function which tail-calls the next state, so it replaces the stack frame. Stack-traces now double as state-inspectors. Substates naturally follow from subroutines.
I regularly use this in Lua gameplay scripting, which has proper tail-calls in the language spec, not just as an implementation-optional detail.
I regularly use this in Lua gameplay scripting, which has proper tail-calls in the language spec, not just as an implementation-optional detail.
You can use a loop and a stack and can get recursion without adding all the overhead of a function call.
How is:
Succinct and better? It’s fewer lines. It uses recursion. But it’s obtuse and illegible syntax diarrhea that takes more time to grok.
The for loop example above, while simple, is easily understood. A junior engineer could fix it. Is it faster? No. Is it easier to understand? Yes. I like the final example as well.
Look, I’m all for being clever when cleverness is needed but some of you JS/TS folks take it to the extreme. I want to be able to read my codebase, not perform archaeological studies. I have the same issue with Rust syntax as well in places.
I will praise the article on this though, optimizations do matter and having something execute orders faster will improve your overall experience. It doesn’t have to be cuneiform. If you must be clever, wrap it in an abstraction that is well documented because you don’t live forever and neither will your code, make it easy(ier) on the next person. While you can nest a recursive function in a tertiary statement coro, don’t. Fire is cool but also burns.
Btw, bun is blazingly fast. I look forward to more.