4 ms·

> This trick is called tail-call optimization (TCO) [2]. Scheme has been doing it since the 1970s - indeed, since Scheme encourages programmers to write recursi

> This trick is called tail-call optimization (TCO) [2]. Scheme has been doing it since the 1970s - indeed, since Scheme encourages programmers to write recursive algorithms, TCO is at the core of the language. More modern languages are catching up too - Lua supports TCO and JavaScript will too, once ES6 becomes the de-facto universal version. Alas, it's 2024, and of the leading browsers/implementations, only Safari/Webkit has managed to support JavaScript TCO. [1] [1] https://compat-table.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) https://compat-table.github.io/compat-table/es6/#test-proper...

neilv 2y ago
For terminology in Scheme, rather than "TCO", some people have suggested "PITCH" (Proper Implementation of Tail Call Handling). I think the reason for different terminology might be that, in most languages, TCO is the compiler thinking, "Oh, I see the programmer is doing recursion here, and I can actually optimize that particular one; though they'll probably never know, just like they don't know that their program is fast because of how I do register allocation and inlining; just another underappreciated silent optimization, but I take pride in my work, and don't need external validation." In Scheme, the compiler instead is thinking, "OK, those language designers encouraged programming with recursion in place of iteration constructs, and told everyone about tail position, and guaranteed that could not exhaust resources, so I'd better compile this entire named-`let` correctly, if I want to keep my job."
- odyssey7 2y ago
  That's useful background information. In ECMAScript 2015, it's referred to as "proper tail calls," rather than TCO, indicating that this is important in the language's design, rather than a mere performance optimization. Having proper tail calls expands the set of functions you can write without fear of overflowing the stack, so it fundamentally expands the expressiveness of the language for production use cases.
- quietbritishjim 2y ago
  Agreed that it's more than just an optimisation if it's documented behaviour in the language, because then code is allowed to depend on its existence (which is not something you're allowed to do for a mere optimisation). There's a name that's both more accurate than TCO and more diplomatic than PITCH, which is TCE (tail call elision). That's certainly the name commonly used in the Python community when discussing (and rejecting!) it.
- unconed 2y ago
  I think you also just described why browsers don't offer any useful way to give the garbage collector hints, like say, after every animation frame / GPU dispatch. It is exceedingly obvious that you have very regular idle times for it to do its thing, and yet, no way for it to make use of that. I don't think it's so much "pride in my silent work" tho as "has never actually talked to the users of their own software".
weinzierl 2y ago
Rust has had a reserved keyword for proper TCO for a very long time but at the moment it looks very unlikely it will ever be implemented for more than one reason. https://web.archive.org/web/20230605150233/https://mail.mozilla.org/pipermail/rust-dev/2013-April/003557.html https://web.archive.org/web/20230605150233/https://mail.mozi... (It's kinda sad that even with a relatively short history like Rust we need to resort to archive.org for this kind of documentation)
- odyssey7 2y ago
  Ah, that’s a shame. So neither Python, JavaScript, nor Rust have fully adopted proper TCO across their communities. Whichever one gets there, I think that would be a strong point in favor of it being taught in university instruction, since recursion is one of the big concepts students explore.

neilv 2y ago

For terminology in Scheme, rather than "TCO", some people have suggested "PITCH" (Proper Implementation of Tail Call Handling). I think the reason for different terminology might be that, in most languages, TCO is the compiler thinking, "Oh, I see the programmer is doing recursion here, and I can actually optimize that particular one; though they'll probably never know, just like they don't know that their program is fast because of how I do register allocation and inlining; just another underappreciated silent optimization, but I take pride in my work, and don't need external validation." In Scheme, the compiler instead is thinking, "OK, those language designers encouraged programming with recursion in place of iteration constructs, and told everyone about tail position, and guaranteed that could not exhaust resources, so I'd better compile this entire named-`let` correctly, if I want to keep my job."

odyssey7 2y ago
That's useful background information. In ECMAScript 2015, it's referred to as "proper tail calls," rather than TCO, indicating that this is important in the language's design, rather than a mere performance optimization. Having proper tail calls expands the set of functions you can write without fear of overflowing the stack, so it fundamentally expands the expressiveness of the language for production use cases.
quietbritishjim 2y ago
Agreed that it's more than just an optimisation if it's documented behaviour in the language, because then code is allowed to depend on its existence (which is not something you're allowed to do for a mere optimisation). There's a name that's both more accurate than TCO and more diplomatic than PITCH, which is TCE (tail call elision). That's certainly the name commonly used in the Python community when discussing (and rejecting!) it.
unconed 2y ago
I think you also just described why browsers don't offer any useful way to give the garbage collector hints, like say, after every animation frame / GPU dispatch. It is exceedingly obvious that you have very regular idle times for it to do its thing, and yet, no way for it to make use of that. I don't think it's so much "pride in my silent work" tho as "has never actually talked to the users of their own software".

weinzierl 2y ago

Rust has had a reserved keyword for proper TCO for a very long time but at the moment it looks very unlikely it will ever be implemented for more than one reason. https://web.archive.org/web/20230605150233/https://mail.mozilla.org/pipermail/rust-dev/2013-April/003557.html https://web.archive.org/web/20230605150233/https://mail.mozi... (It's kinda sad that even with a relatively short history like Rust we need to resort to archive.org for this kind of documentation)

odyssey7 2y ago
Ah, that’s a shame. So neither Python, JavaScript, nor Rust have fully adopted proper TCO across their communities. Whichever one gets there, I think that would be a strong point in favor of it being taught in university instruction, since recursion is one of the big concepts students explore.