5 ms·
I wince every time I see naive recursive fibonacci as a code example. It is a major turnoff because it hints at a lack of experience with tail call optimization
by norir 10mo ago
I wince every time I see naive recursive fibonacci as a code example. It is a major turnoff because it hints at a lack of experience with tail call optimization, which I consider a must have for a serious language.
- stouset 10mo agoWould someone please explain to me why TCO—seemingly alone amongst the gajillions of optimization passes performed by modern compilers—is so singularly important to some people?
- aaronblohowiak 10mo agofunctional programming background / SICP ?
- Rusky 10mo agoTCO is less of an optimization (which are typically best-effort on the part of the compiler) and more of an actual semantic change that expands the set of valid programs. It's like a new control flow construct that lives alongside `while` loops.
- oersted 10mo agoFor people that like functional style and using recursion for everything, TCO is a must. Otherwise there’s no way around imperative loops if you want decent performance and not having to worry about the stack limit. Perhaps calling it an “optimization” is misleading. Certainly it makes code faster, but more importantly it’s syntax sugar to translate recursion into loops.
- int_19h 10mo agoYou don't need full fledged TCO for that; see Clojure's recur for an example. Zig recently added something similar but strongly typed with match/continue. These all map exactly to a closed set of mutually recursive functions with a single entry point, which is quite sufficient (and then some) to fully replace iterative loops while still desugaring to the same exact code.
- oersted 10mo agoIndeed there are more explicit versions of such mechanisms, which I prefer, otherwise there’s always a bit of paranoia about recursion without assurance that the compiler will handle it properly.
- zephen 10mo agoIt virtue-signals that they're part of the hip functional crowd. (To be fair, if you are programming functionally, it is essential. But to flat-out state that a language that doesn't support isn't "serious" is a bit rude, at best.)
- mrkeen 10mo agoSupporting recursion only to a depth of 1000 (or whatever) is equivalent to supporting loops of up to 1000 iterations. If I put out a language that crashed after 1000 iterations of a loop, I'd welcome the rudeness.
- Ar-Curunir 10mo agoPlenty of languages, including very serious ones like C and Rust, have bounded recursion depth.
- mrkeen 10mo agoThen let me rephrase: If every iteration of a while-loop cost you a whole stack frame, then I'd be very rude about that language. This works, btw: #include <stdio.h> long calc_sum(int n, long acc) { return n == 0 ? acc : calc_sum(n-1, acc+n); } int main(void) { int iters = 2000000; printf("Sum 1...%d = %ld\n", iters, calc_sum(iters, 0)); return 0; }
- zephen 10mo ago> If every iteration of a while-loop cost you a whole stack frame, then I'd be very rude about that language. Well, sure, but real programmers know how to do while loops without invoking a function call.
- deleted 10mo ago[deleted]
- chuckadams 10mo agoWhen you have recursive data structures, it's nice when the algorithms have the same shape. TCO is also handy when you're writing fancy control flow operations and implement them with continuation-passing style.
- steveklabnik 10mo agoI only have basic constant folding yet in terms of optimizations, but I'm very aware of TCO. I haven't decided if I want to require an annotation to guarantee it like Rust is going to.
- int_19h 10mo agoPlease require some form of annotation like an explicit `tailcall` operator or something similar. TCO wrecks havoc on actionable backtraces, so it should be opt-in rather than opt-out.
- steveklabnik 10mo agoI am very sympathetic to this, for sure.
- airstrike 10mo ago"Well you can judge the whole world on the sparkle that you think it lacks. Yes, you can stare into the abyss, but it's staring right back"
- mrkeen 10mo agoPlease, it supports a hole at best. Maybe a pit. No way will this let you construct an abyss.
- dullcrisp 10mo agoPlus we all know that fibs = 1 : 1 : zipWith (+) fibs (tail fibs) is the only serious Fibonacci implementation.
- xpe 10mo agoWho thunk of that one?