Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tail-call optimization in C is relatively recent (2025)

lwn.net

Post reply on HN
Print view View original

91–100 of 140 posts

Re: Tail-call optimization in C is relatively recent (2025)

#91

Post by drdexebtjl »

layer8 wrote: post #75
mort96 wrote: post #56

Earlier quoted context omitted.

If the semantics of 'while (true)' was "will crash the program after an implementation-defined but often fairly low number of iterations", I would stop using 'while (true)'.

It’s precisely not the semantics of the program that will crash the program, but the behavior of the language implementation. It’s similar to when a program in a GC language fails with OOM because the language implementation uses a no-op collector. That’s usually not part of programming language semantics.

If you wrote a correct binary search algorithm and you observed that, under one language implementation, the time complexity scaled linearly with the size of the input instead of logarithmically, you would think the semantics of the program were changed.

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.

Re: Tail-call optimization in C is relatively recent (2025)

#92

Post by toast0 »

fluoridation wrote: post #90
toast0 wrote: post #87

Earlier quoted context omitted.

> But the compiler controls both the caller and callee. Why? In functional languages, it's common for an exported function from one compilation context to tail call into an exported function from another.

Functional languages may be designed to support TCO from the ground up, up to supporting it across module boundaries. C is not like that, and calling into an external module necessarily grows the stack.

> C is not like that, and calling into an external module necessarily grows the stack.

This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)

Re: Tail-call optimization in C is relatively recent (2025)

#93

Post by leni536 »

mort96 wrote: post #56
kevincox wrote: post #39

Earlier quoted context omitted.

It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program. However most optimizations are very hard to observe. The vast majority of optimizations only affect code size and runtime. TCO is one of the few exceptions. It affects memory usage, and more sensitive stack memory at that. This is why a missed optimization can be so much more catastrophic and it is worth consider…

If the semantics of 'while (true)' was "will crash the program after an implementation-defined but often fairly low number of iterations", I would stop using 'while (true)'.

Precisely. ISO C and C++ have a notion of various implementation limits, one of which is nested function calls due to exhausting the stack. TCO could be about a carveout on this limit.

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

Re: Tail-call optimization in C is relatively recent (2025)

#94

Post by fluoridation »

toast0 wrote: post #92
fluoridation wrote: post #90

Earlier quoted context omitted.

Functional languages may be designed to support TCO from the ground up, up to supporting it across module boundaries. C is not like that, and calling into an external module necessarily grows the stack.

> C is not like that, and calling into an external module necessarily grows the stack. This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)

Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?

Re: Tail-call optimization in C is relatively recent (2025)

#95

Post by StilesCrisis »

fweimer wrote: post #62
StilesCrisis wrote: post #35

Earlier quoted context omitted.

Clang tail-calls aren't guaranteed to work with all C++ code. If you have a non-trivial constructor, as you mention, it will tell you this and fail instead of silently letting you believe you have tail-calls when you don't.

There are far more cases. Some ABIs use callee-saved registers for parameter-passing under certain circumstances, for example. Usually, there are compatibility restrictions on the signatures of the current and tail-called functions beyond the return type, too. This is different from Scheme or the MLs (there as a quality-of-implementation feature) where tail calls into arbitrary functions are expected not to lead to s…

Right--if the tailing isn't possible, for any of these varied reasons, it will become a compile error.

Re: Tail-call optimization in C is relatively recent (2025)

#96

Post by amavect »

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.

Re: Tail-call optimization in C is relatively recent (2025)

#97

Post by toast0 »

fluoridation wrote: post #94
toast0 wrote: post #92

Earlier quoted context omitted.

> C is not like that, and calling into an external module necessarily grows the stack. This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)

Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?

With the right calling convention, tail calls could conform to the convention.

A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work.

In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.

Re: Tail-call optimization in C is relatively recent (2025)

#98

Post by 10000truths »

toast0 wrote: post #88
torginus wrote: post #57

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 mo…

> My impression is that every tail call can written as a loop much more naturally. Which is more natural? (please just assume my wonky pseudo code syntax makes sense) printall(List) -> foreach item in List { print_item(item) }. printall([Head | Tail]) -> print_item(Head), printall(Tail); printall([]) -> ok. IMHO, both of these need to be taught, neither is particularly more natural. In addition, as others have descri…

> TCO makes a lot of sense for interpreters and state machines.

The reason that performant implementations prefer TCO is because the only reliable knob that clang and gcc provide to control which locals are spilled to stack vs. kept in registers is via calling convention constraints. One could accomplish the same performance without TCO'd recursion if there existed an annotation for local variables designating them as spill/no-spill. But that doesn't exist in clang or gcc - the "register" keyword in the C standard was supposed to be for exactly that, but it's ignored in both compilers.

Re: Tail-call optimization in C is relatively recent (2025)

#99

Post by fluoridation »

toast0 wrote: post #97
fluoridation wrote: post #94

Earlier quoted context omitted.

Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?

With the right calling convention, tail calls could conform to the convention. A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work. In a callee cleanup convention, a tail caller…

>In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee.

You can still do that with a caller-cleanup convention. Suppose you have a convention like

* Set up stack

* Call

* Clean up stack

and you have functions f(), g(), and h(), where g() and h() use this convention and f() calls into g(), and g() into h(). The sequence of instructions from f() to h() without TCO would be

* f: Set up stack for g()

* f: Call g()

* g: Do work

* g: Set up stack for h()

* g: Call h()

* h: Do work

* h: Return

* g: Clean up stack

* g: Return

* f: Clean up stack

And with TCO:

* f: Set up stack for g()

* f: Call g()

* g: Do work

* g: Move things around on the stack so that h()'s arguments are written where g()'s were. This may require a temporary stack allocation that's released before the next step.

* g: Jump to h()

(At this point it looks as if f() called h() directly.)

* h: Do work

* h: Return

* f: Clean up stack

This is always possible as long as h()'s caller-managed stack allocation is no bigger than g()'s.

Post reply on HN