Hacker News Reader

Comment by norir | Hacker News Reader

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.

View on HN

Would 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?

functional programming background / SICP ?

TCO 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.

For 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.

You 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.

Indeed 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.

It 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.)

Supporting 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.

Plenty of languages, including very serious ones like C and Rust, have bounded recursion depth.

Then 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;
  }

> 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.

When 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.

I 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.

Please 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.

I am very sympathetic to this, for sure.

Plus we all know that fibs = 1 : 1 : zipWith (+) fibs (tail fibs) is the only serious Fibonacci implementation.

Who thunk of that one?

"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"

Please, it supports a hole at best. Maybe a pit. No way will this let you construct an abyss.

Reply on news.ycombinator.com