4 ms·

does some JS idiom rely on TCO or is this for transpiled languages?

by hnav 4y ago

ISV_Damocles 4y ago
It would help any recursively-defined code, parsers of some input format are often more naturally represented that way, for instance, where rewriting as an imperative loop requires mixing of different logical states, eg, a JS JSON parser might determine if the current character is for an object, array, or leaf type, and then pass the input along to whichever that is, and if it was an array, for instance, would then pass back to that initial function one character over to determine what the first type of the first element of the array is. This is easy in a recursive style and would require all of this logic to be mixed in the same function with some state tracking variable to decide which branch to use in imperative style. You can use trampolines[1] to get around this, but there's a performance penalty versus TCO and other recursive optimizations. [1]: https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3/ https://blog.logrocket.com/using-trampolines-to-manage-large...
MrJohz 4y ago
Honestly, the impression I get is that it seemed like a cool thing to have, rather than something that came out of genuine need. I very rarely see recursive functions in the wild, and while I quite like them and probably use them more often than average, I rarely write tail-recursive functions. Specifically, Javascript has pretty good iteration tools, so the basic recursion-as-iteration stuff isn't necessary, and usually pretty inefficient. Which means recursion tends to only get used when you're dealing with a recursive data structure of some description, or doing something naturally recursive. But in my experience these cases of natural recursion tend not to lend themselves to tail recursion - in the general case, you need a stack argument somewhere to allow the tail recursion to work, at which point you might as well just write a non-recursive, loop-based version. The result of this is that truly tail-recursive functions are fairly rare in "idiomatic" Javascript code, which means implementation effort spent there is going to affect relatively little code. I could imagine that transpiled code might use this technique more often, but then the rise of WASM probably means that fewer languages are going to see Javascript as their primary compilation target, and instead choose WASM.
- int_19h 4y ago
  Natural recursion that stems from data structures will be tail-recursive if they themselves are recursive in this manner. Thus e.g. walking a linked list is a problem that naturally translates to tail recursion, but walking a binary tree isn't. But also, part of the reason why you don't see much deeply recursive code in the wild is because there's no guarantee that it'll be tail-call-optimized, which means that it'll likely fail on large inputs, and will be written iteratively to begin with.
  - MrJohz 4y ago
    Even many operations performed on a linked list will not be tail recursive if you do them naively. For example, a naive sum function might look like: const sum = (node: Node): number => { if (!node.tail) return node.value; return node.value + sum(node.tail); } Even if tail call optimisation were a thing, I'd still expect most recursive functions to be written in a non-tail-recursive fashion, and only later optimised to be tail recursive. But in practice, it's already possible to rewrite those functions in an imperative way when they do become a performance issue. So in practice, I can see why implementors don't prioritise TCO in Javascript, coming from both directions: there's not a lot of free wins available, because tail calls are rarely the most natural way to express a recursive algorithm; and even if you want to explicitly optimise for them, there's already plenty of ways to optimise an inefficient recursive algorithm if that's necessary. That said, I can see the value a lot more in a language that's being used as a compilation target, which it probably made more sense when there was more buzz around compile-to-JS languages, and why it makes more sense now with WebAssembly.

does some JS idiom rely on TCO or is this for transpiled languages?

by hnav 4y ago

does some JS idiom rely on TCO or is this for transpiled languages?

It would help any recursively-defined code, parsers of some input format are often more naturally represented that way, for instance, where rewriting as an imperative loop requires mixing of different logical states, eg, a JS JSON parser might determine if the current character is for an object, array, or leaf type, and then pass the input along to whichever that is, and if it was an array, for instance, would then pass back to that initial function one character over to determine what the first type of the first element of the array is. This is easy in a recursive style and would require all of this logic to be mixed in the same function with some state tracking variable to decide which branch to use in imperative style. You can use trampolines[1] to get around this, but there's a performance penalty versus TCO and other recursive optimizations. [1]: https://blog.logrocket.com/using-trampolines-to-manage-large-recursive-loops-in-javascript-d8c9db095ae3/ https://blog.logrocket.com/using-trampolines-to-manage-large...

MrJohz 4y ago

Honestly, the impression I get is that it seemed like a cool thing to have, rather than something that came out of genuine need. I very rarely see recursive functions in the wild, and while I quite like them and probably use them more often than average, I rarely write tail-recursive functions. Specifically, Javascript has pretty good iteration tools, so the basic recursion-as-iteration stuff isn't necessary, and usually pretty inefficient. Which means recursion tends to only get used when you're dealing with a recursive data structure of some description, or doing something naturally recursive. But in my experience these cases of natural recursion tend not to lend themselves to tail recursion - in the general case, you need a stack argument somewhere to allow the tail recursion to work, at which point you might as well just write a non-recursive, loop-based version. The result of this is that truly tail-recursive functions are fairly rare in "idiomatic" Javascript code, which means implementation effort spent there is going to affect relatively little code. I could imagine that transpiled code might use this technique more often, but then the rise of WASM probably means that fewer languages are going to see Javascript as their primary compilation target, and instead choose WASM.

int_19h 4y ago
Natural recursion that stems from data structures will be tail-recursive if they themselves are recursive in this manner. Thus e.g. walking a linked list is a problem that naturally translates to tail recursion, but walking a binary tree isn't. But also, part of the reason why you don't see much deeply recursive code in the wild is because there's no guarantee that it'll be tail-call-optimized, which means that it'll likely fail on large inputs, and will be written iteratively to begin with.
- MrJohz 4y ago
  Even many operations performed on a linked list will not be tail recursive if you do them naively. For example, a naive sum function might look like: const sum = (node: Node): number => { if (!node.tail) return node.value; return node.value + sum(node.tail); } Even if tail call optimisation were a thing, I'd still expect most recursive functions to be written in a non-tail-recursive fashion, and only later optimised to be tail recursive. But in practice, it's already possible to rewrite those functions in an imperative way when they do become a performance issue. So in practice, I can see why implementors don't prioritise TCO in Javascript, coming from both directions: there's not a lot of free wins available, because tail calls are rarely the most natural way to express a recursive algorithm; and even if you want to explicitly optimise for them, there's already plenty of ways to optimise an inefficient recursive algorithm if that's necessary. That said, I can see the value a lot more in a language that's being used as a compilation target, which it probably made more sense when there was more buzz around compile-to-JS languages, and why it makes more sense now with WebAssembly.