Comment by eru
1 day ago
> Of course, this means that the same implementation could also be directly expressed logically in a way that is mutable/iterative.
Yes, compilers exist.
> There is no real "advantage" to, or reason to "sell" anybody on tail call recursion if you are able to easily and clearly represent both implementations, IMO.
Avoiding mutation avoids headaches.
> [0] EXCEPT in practice all implementation differences/optimizations introduce observable side effects that can otherwise impact program correctness or semantics. For example, a program could (perhaps implicitly) rely on the fact that it errors out due to stack overflow when recursing > X times, and so enabling TCO could cause the program to enter new/undesirable states; or a program could rely on a functin F making X floating point operations taking at least Y cycles in at least Z microseconds, and not function properly when F takes less than Z microseconds after enabling vectorization. This is Hyrum's Law [2].
These programs are likely not standards compliant. (And that's not just true for the C++ standard but for basically any language with a standard.)
> And just like TCO, RVO is neat but IMO slightly dangerous because it relies on implicit compiler/runtime optimizations that can be accidentally disabled or made non-applicable as code changes:
Who says TCO has to be always implicit? In eg Scheme it's explicit in the standard, and in other languages you can have annotations.
(Whether a call is in tail position is more or less a property you can ascertain syntactically, so your annotation doesn't even have to be understood by the compiler: the linter is good enough. That would catch your 'accidental changes' part.
Things get more complicated, when you have implicit clean-ups happen after returning from the function. Like calling destructors in C++. Then the function call is arguably not in a tail position anymore, and so TCO doesn't apply. Whether this is detectable reliably at compile time depends on the details of your language.)
Avoiding mutation avoids headaches, but the real headaches are actions (mutations) at a distance, and tail recursion vs loops make no difference there.
No mutation (and no side-effects in general) means no action at a distance.
Loops need mutation to work. The mutation might be benign or it might be headache-inducing. Without further analysis you don't know. If there's no mutation, no need for analysis. Lowering the cognitive load.
Well, replacing loops with tail calls is one tool to get rid of some mutations.
It's basically the same reasoning people give you for not using goto in your program: yes, there are ways to use gotos responsible, and there's ways to end up with spaghetti code.
If you use goto, the reader has to analyse and figure out whether you made spaghetti (and the reader can never be quite sure she understood everything and didn't miss an important caveat). If you express yourself without goto, the need for that analysis largely goes away.
I have a similar attitude about const in C++, I use it almost whenever possible. Less (possible) mutation to worry about. But I also let go of it fairly easily when it gets in the way. And... well... tail recursion doesn't feel very idiomatic in C++.
If you iterate by const reference over a const container, and you make every assign-once variable in the loop body const (or in Rust: just not mut), is there any advantage to tail recursion except someone on the internet said it's the proper functional style?