3 ms·

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 jus

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 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.

basil-rash 3y ago
Scheme (what JavaScript was based on) also requires tail call optimizations as part of its spec.
mananaysiempre 3y ago
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.)
MrJohz 3y ago
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.
- EE84M3i 3y ago
  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.
  - hajile 3y ago
    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.
deleted 3y ago
[deleted]
bsdpufferfish 3y ago
> 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.

basil-rash 3y ago

Scheme (what JavaScript was based on) also requires tail call optimizations as part of its spec.

mananaysiempre 3y ago

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.)

MrJohz 3y ago

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.

EE84M3i 3y ago
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.
- hajile 3y ago
  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.

deleted 3y ago

[deleted]

bsdpufferfish 3y ago

> 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.