Birbla

Join the discussion

Write your take first — we'll ask for email only when you're ready to publish.

Sign in
  • Hacker News
  • GCC has had TCO since the 1980s I'm pretty sure. Since then it's been extended to work in more contexts.
    by throwaway81523
  • I recently played around with what I call "manual tail-call optimization": transform a tail call to a goto to the beginning of the function. Check it out: https://godbolt.org/z/3fY1v1oeW

      int factorial_loop_iterative(int n, int a){
    while(n > 0){
      a = a * n;
      n = n - 1;
    }
    return a;
  }
  
  int factorial_loop_recursive(int n, int a){
    if(n > 0){
      return factorial_loop_recursive(n - 1, a * n);
    }else{
      return a;
    }
  }
  
  int factorial_loop_manual(int n, int a){
  tailcall:
    if(n > 0){
      a = a * n;
      n = n - 1;
      goto tailcall;
    }else{
      return a;
    }
  }
  
  int (*factorial_loop)(int n, int a) = factorial_loop_manual;
  
  int factorial(int n){
    return factorial_loop(n, 0);
  }
    I recommend against, of course! Incorrectly sequencing the manual version results in bugs (swap the assignment for n and a), which the recursive version doesn't need to care about.
    by amavect
  • TFA assumes pre-C89 C, I think:

    > The caller could see the declaration int f();, the actual call could have n>0 arguments, and the actual function could have m≤n parameters.

    Certainly if `f()` were `int f(void);` then that wouldn't be the case. But even for `int f();` C17 6.5.2.2p6 says that "If the number of arguments does not equal the number of parameters, the behavior is undefined." Near as I can tell that was made UB in C89. So TFA is a) right about K&R C, b) just wrong for pretty much all post-K&R C. C23 makes `int f();` be the same as `int f(void);`.

    That calling a non-variadic function with more / fewer arguments than expected by its definition is UB is enough to make TCO possible for that function's body.

    The point about K&R C is well taken though: to turn a tail call into a jump, the caller needs to know how much to pop off the stack.

    For variadic if you `va_start()`, `va_arg()` as needed, then `va_end()` with no `va_copy()` left alive then you can still tail-call out correctly, otherwise you can't.

    For non-variadic functions post K&R C TCO should always be possible and not UB, provided you're not triggering UB to begin with by using the incorrect number of arguments.

    by cryptonector
  • What practical patterns are enabled by TCO in C? My impression is that every tail call can written as a loop much more naturally. Tail calls are important in functional languages where you don't have mutable loop variables.

    And imo they are an ugly hack even there - one of the few core constructs where its readily apparent you're not programming an abstract machine but a real, and limited computer. For example the most natural way to write factorial:

          let rec factorial n = if n <= 1 then 1 else n * factorial (n - 1)
    is not tail recursive, and will overflow if the compiler fails to optimize.
    by torginus
  • and TCO was added then removed from js! https://stackoverflow.com/a/54721813

    This leads to fun stack-overflow bugs too in a lot of js code (one solution is to flatten: https://joshua.hu/javascript-infinite-tail-call-recursion-st...)

    by mmsc
  • I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there!

    On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.

    by kenjin4096
  • 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.

    by drdexebtjl
  • > In 2001 Mark Probst implemented tail-call optimization in GCC

    That's me.

    The motivation back then was to allow compilers that target C to assume that tail calls will be "proper". That's different from an optimization, which is usually optional, and which compilers don't guarantee.

    The LWN post briefly sketches why this is hard: C allows variable-argument functions (like printf) where only the caller knows for sure how many arguments it passed, which means that only the caller can clean up the stack, unless the stack frame size is also communicated, which "normal" C calling conventions don't do. But when the callee does a proper tail call, the stack frame that returns to the callee is not the stack frame that the callee originally sent. This is explained in more detail in my thesis starting on page 16: https://hostr.flingit.run/s/proper-tail-calls.pdf

    by mark-probst

Explore Birbla archives