3 ms·

> 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

by 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.
- zelphirkalt 3y ago
  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.
  - MrJohz 3y ago
    That's mostly the point I'm trying to make! What would you see as a more convincing example of TCO in this context?
    - zelphirkalt 3y ago
      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/839bb8a0d502727feab238e5ebaebb5f128c0891/graphs/lib/algorithms/dijkstra.scm 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 ;)

by tonyg 3y ago

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.

zelphirkalt 3y ago
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.
- MrJohz 3y ago
  That's mostly the point I'm trying to make! What would you see as a more convincing example of TCO in this context?
  - zelphirkalt 3y ago
    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/839bb8a0d502727feab238e5ebaebb5f128c0891/graphs/lib/algorithms/dijkstra.scm 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 ;)