Unless the language can guarantee TCO, I don’t feel comfortable writing tail recursive code and being at the compiler’s/interpreter’s mercy.
I think the framing of TCO as an optimization has been very unfortunate.
I think the framing of TCO as an optimization has been very unfortunate.
I can only think of a few other optimizations that affect memory usage. Register spilling (arguably not really an optimization but a necessity), Rust's niche filling for enum discriminants and C++'s std::vec<bool> (a language-level optimization, arguably a different thing entirely).
I often think about how few memory optimizations we have. The reason is most likely that they tend to be non-local so are much harder to apply than CPU optimizations that generally have no effect outside of the function they are in.
Depends on the semantics of the programming language itself. For some languages, it is truly an optimization, for some, it is required, and does meaningfully change observed semantics.
It doesn't matter if it's local since it's a VM, it's doing it at runtime and can change an entire call stack of non local code for an optimization.
Which exactly in this subject varies a lot between implementations, on how well escape analysis is done, if there is a JIT cache between JVM executions, or AOT compilation.
Additionally Valhalla is finally getting added to the language with a new EA made available last week, thus value classes will add yet another way to have stack values.
Value classes are not a compiler optimization, and I wasn't talking about the standard, I was talking about an implementation.
It’s that it makes memory usage bounded when it’s on, and unbounded when it’s off.
In languages that have guaranteed tail call eliminations, the semantics of tail recursion is the same as that of a loop. So you can express the same iterative algorithm without using iterative code.
If std::vector<bool> was an optimisation we couldn't write C++ which blows up because it's actually a bitset, it would be semantically transparent - but that's easy to do even by accident because it's not transparent at all.
In fact the existing std::vector<bool> should just be named std::growable_bitset or something and then std::vector<bool> would make what you actually wanted like Rust's Vec<bool> does.
But also, I wouldn't rely on a compiler to remove empty 'while (true)' loops.
Both languages continue to have examples of slightly more complicated loops that can be assumed to terminate in the absence of side effects, but `while(true)` isn't one of those any longer.
If you used an in-place sort algorithm and observed memory requirements that scale super-linearly with the size of the input, you would think the semantics of the program were changed.
In languages with such tail call guarantees, tail recursion _is_ a loop. It semantically encodes constant space complexity.
Having said that the standards give way too much leeway for the limits, so a conforming implementation might have arbitrary limits for loops as well (at least in C++, I'm not that familiar with the C standard's wording).
Which means that "whether this naively-recursive code is actually recursive in practice" is a semantic difference, in that there is an error/failure-mode (stack overflow) that can be statically guaranteed to not happen (at least for a given compilation target) if TCO gets applied; but which cannot be guaranteed to not happen without TCO applied.
---
Tangent: you could of course try to write code defensively, to guarantee that a stack overflow won't occur, by bounding recursion separately (e.g. via a passed-and-decremented recursion-limit parameter), so that in the non-TCO case, you get a software exception thrown (which you'd hopefully then handle... somehow), rather than triggering a stack overflow.
And for many more-traditional recursive algorithms, this works!
But doing so for the types of algorithms that are "canonically" expressed in terms of tail-calls (even in a non-tail-call-idiomatic language like C), almost always requires poking holes in the C abstract machine to see through to the micro-architectural details underneath.
You can't just use something like a recursion-limit parameter as a general solution for these algorithms, as TCO is used in things like continuation-passing or threaded-code VM implementations — i.e. things that look less like visiting trees and more like visiting unboundedly-non-terminal infinite-state-machine states ["infinite" because the states are dynamic function pointers to JITted code, and more of them can appear at runtime.]
You need to not track the "number of invocations deep" you are into the algorithm, but rather, how big the stack actually is at the moment. Which means you need to actually do math on addresses of the stack base pointer vs either the stack pointer, or the address of a local stack-allocated variable. There's no version of that that doesn't require writing non-portable inline assembly.
Java has string interning. I think that’s a hack that shouldn’t exist in an ideal world. Reason is that, as a library writer, you cannot make the call whether to intern strings (requiring more instructions for string access, thus slowing down code, but decreasing memory usage, and, because of that, possibly speeding up the code again) or not.
Wait, why would interned immutable strings require more instructions when doing regular string access? You can still point to the start of a zero-terminated C-string, it just requires storing extra metadata like lenght and a string hash somewhere. Which can be done at the negative indices of said pointer.
Or do you refer to the extra rolling-hash pass needed when concatenating two strings to verify if it would result in an already-interned one? Because yes, that's one extra rolling hast pass over the appended string the first time a string is constructed, but after that doing so again likely saves memory and construction time, because any concatenation that would result in an already interned string would avoid actual memory allocation and copying of the string's characters.
Plus string comparisons become cheap O(1) pointer comparisons this way, which is really nice in many use-cases.
And that's not even considering more advanced tricks like interning short strings in the 64-bit word of the pointer to the string itself, relying on the fact that modern memory allocators never return an address with the lsb set, so it can be used to flag it as such[0].
Java automatically interns static strings (e.g. from class files), but does not automatically intern dynamically-allocated strings, e.g. new String(charArray)
If you want it interned, you have to intentionally call e.g. new String(...).intern(). If you do this on every string you work with, you can then reliably use reference equality instead of value equality, e.g. given char[] abc = {'a','b','c'}; then new String(abc) != new String(abc) != "abc" but new String(abc).intern() == new String(abc).intern() == "abc"
But if you're interning every string, you're doing extra work to maintain that string pool, and adding extra pressure on the GC, and potentially you'll be re-interning strings a lot depending on how many times they end up no longer referenced by the time GC runs.
Just to clarify where I started from: JS has the notion of String Primitives and String Objects[0], and concatenating two string primitives results in another string primitive. It's as if it always calls .intern(). Except, since from a user perspective there is no option to not intern it, JS implementations are free to do optimizations that don't seem available to Java. Like avoiding heap allocation for provably short-lived strings in the first place, and not interning them if they are never compared (I don't actually know if it does those optimizations, but I imagine it shouldn't be too hard to prove these things with many short functions).
[0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
Sorry, I wasn’t precise. Accessing them won’t take more instructions, but setting them up does.
> Or do you refer to the extra rolling-hash pass needed when concatenating two strings to verify if it would result in an already-interned one?
I don’t think the JVM does that.
it is guaranteed in Scheme, and it affects the semantics of programs in a completely positive way.
Much of computer science is "pure" and "abstract" like mathematics. However, programmers are still taught to use loops to calculate factorial rather than recursion in order to avoid stack overflow. In Scheme you can use recursion without flinching. That is a semantic difference.
It does when you use them as a feature and not an optimization. Like in interpreters, state machines, parsers, etc.
Calling tail calls an optimization set computer science back 40 years.
There is a "tail" prefix in the intermediate language (IL) bytecode that F# uses but Roslyn, the C# compiler, never emits.
So unlike F#, whether the same algorithm written in C# becomes a loop depends on JIT behaviour. This means if you're coming to a function cold in C# you can overflow the stack, while if you enter the same function fresh after it's been warmed up, it may have been optimised away by RyuJIT and if so you are able to call it safely for what would be large numbers of recursions.
> More than 20 programming tools vendors offer some 26 programming languages — including C++, Perl, Python, Java, COBOL, RPG and Haskell — on .NET.
https://news.microsoft.com/source/2001/10/22/massive-industr...
MSIL thus had to support all of them.
Those differences between language semantics is why CLS was also a thing back then.
https://learn.microsoft.com/en-us/dotnet/standard/language-i...
But yes, framing TCO as an optimization is unfortunate.
As well as an effort to get it standardized: https://isocpp.org/files/papers/D3939R0.html (in C++).
Of course it's nowhere near a guarantee that it would land in the stable language, but it's still an opportunity to try it in practice.
https://gcc.gnu.org/onlinedocs/gcc-15.1.0/gcc/Statement-Attr...