> 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]
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."
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.
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.
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".
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.
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.
Are there any good heuristics for adding trampolines if the underlying architecture does not support tail calls? (With the closed-world assumption.) Maybe breadth-first search on the callgraph, inserting trampolines at the first circle? And then somehow restart and deal with the remaining cycles, until none are left?
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...