7 ms·

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 situation

by MrJohz 3y ago

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.

pjmlp 3y ago
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.
- deleted 3y ago
  [deleted]
- MrJohz 3y ago
  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.
  - pjmlp 3y ago
    Firefox no longer matters, hence why I left it out.
    - trashburger 3y ago
      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.
      - pjmlp 3y ago
        Sadly it doesn't, in many places being so low means the project acceptance matrix for target browsers no longer needs to contemplate Firefox.
        zelphirkalt 3y ago
        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.
    - ncruces 3y ago
      1. Complain about market dominance. 2. Any 2% of the market doesn't matter. 3. …
- tomashubelbauer 3y ago
  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.)
- spankalee 3y ago
  What "political" reasons? My understanding of the situation is that it's entirely technical issues that came up after implementing.
  - runarberg 3y 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.
    - odyssey7 3y ago
      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 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.
      - jart 3y ago
        Are you saying that knowing LISP makes you like an instant Paul Graham? If only.
odyssey7 3y ago
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.
- MrJohz 3y ago
  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.
  - odyssey7 3y ago
    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.
tikhonj 3y ago
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!)
tonyg 3y ago
> 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 https://doi.org/10.1016/0167-6423(91)90036-W .
- MrJohz 3y ago
  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.
akoboldfrying 3y ago
>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.

by MrJohz 3y ago

pjmlp 3y ago

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.

deleted 3y ago
[deleted]
MrJohz 3y ago
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.
- pjmlp 3y ago
  Firefox no longer matters, hence why I left it out.
  - trashburger 3y ago
    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.
    - pjmlp 3y ago
      Sadly it doesn't, in many places being so low means the project acceptance matrix for target browsers no longer needs to contemplate Firefox.
      - zelphirkalt 3y ago
        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.
  - ncruces 3y ago
    1. Complain about market dominance. 2. Any 2% of the market doesn't matter. 3. …
tomashubelbauer 3y ago
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.)
spankalee 3y ago
What "political" reasons? My understanding of the situation is that it's entirely technical issues that came up after implementing.
- runarberg 3y 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.
  - odyssey7 3y ago
    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 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.
    - jart 3y ago
      Are you saying that knowing LISP makes you like an instant Paul Graham? If only.

odyssey7 3y ago

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.

MrJohz 3y ago
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.
- odyssey7 3y ago
  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.

tikhonj 3y ago

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

tonyg 3y ago

> 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 https://doi.org/10.1016/0167-6423(91)90036-W .

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

akoboldfrying 3y ago

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