Tail-call optimization in C is relatively recent (2025) • Hacker News Board

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

#81

Post by derefr » Mon, Aug 10, 2026, 7:10 PM UTC

kevincox wrote: post #39

drdexebtjl wrote: post #33

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.

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…

I think the problem with considering it a "pure optimization" is that code that is written to use tail-calls, if not optimized, is almost always unbounded recursive code. And modern OSes tend to have relatively small stack-size limits (relative to the kinds of huge data structures modern software slings around, incl. not only individually-"wide" structures, but also "deep" trees and graphs.)

Which means that "whether this naively-recursive code is actually recursive in practice" is a semantic difference, in that there is an error/failure-mode (stack overflow) that can be statically guaranteed to not happen (at least for a given compilation target) if TCO gets applied; but which cannot be guaranteed to not happen without TCO applied.

---

Tangent: you could of course try to write code defensively, to guarantee that a stack overflow won't occur, by bounding recursion separately (e.g. via a passed-and-decremented recursion-limit parameter), so that in the non-TCO case, you get a software exception thrown (which you'd hopefully then handle... somehow), rather than triggering a stack overflow.

And for many more-traditional recursive algorithms, this works!

But doing so for the types of algorithms that are "canonically" expressed in terms of tail-calls (even in a non-tail-call-idiomatic language like C), almost always requires poking holes in the C abstract machine to see through to the micro-architectural details underneath.

You can't just use something like a recursion-limit parameter as a general solution for these algorithms, as TCO is used in things like continuation-passing or threaded-code VM implementations — i.e. things that look less like visiting trees and more like visiting unboundedly-non-terminal infinite-state-machine states ["infinite" because the states are dynamic function pointers to JITted code, and more of them can appear at runtime.]

You need to not track the "number of invocations deep" you are into the algorithm, but rather, how big the stack actually is at the moment. Which means you need to actually do math on addresses of the stack base pointer vs either the stack pointer, or the address of a local stack-allocated variable. There's no version of that that doesn't require writing non-portable inline assembly.

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

#82

Post by noelwelsh » Mon, Aug 10, 2026, 7:11 PM UTC

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…

> What practical patterns are enabled by TCO in C?

It's important in interpreters. Here's an example: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

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

#83

Post by uecker » Mon, Aug 10, 2026, 7:18 PM UTC

pjmlp wrote: post #74

throw-qqqqq wrote: post #44

Earlier quoted context omitted.

TIL, thanks for updating me on this! I read Herb Sutter’s post many years ago, but didn’t know they had picked up the work again. I see that VLAs are still not supported, which is a shame IMO, but the C-support seems much better than it used to be at least.

They never will, as mentioned they have decided not to support what became optional in C11. If C23 ever comes to land on MSVC, which I have my doubts given the radio silence on C support, I assume they might add the VLAs part that made it again back into C23.

If you care about C, use gcc.

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

#84

Post by uecker » Mon, Aug 10, 2026, 7:26 PM UTC

fluoridation wrote: post #80

layer8 wrote: post #77

Earlier quoted context omitted.

When the calling convention is such that the caller owns the function arguments, the callee can’t remove/replace them on the stack, but has to keep them across the tail call. In turn, it means that the callee has to clean up the arguments to the tail call, and thus can’t actually make a tail call, unless the argument list happens to be identical to the original call.

But the compiler controls both the caller and callee. It doesn't need to respect any calling convention during a TCO. In fact it won't; it'll jump instead of calling.

It is usually assumed that it does not control the callee and the jump has to preserve the calling convention for a call.

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

#85

Post by fluoridation » Mon, Aug 10, 2026, 7:31 PM UTC

uecker wrote: post #84

fluoridation wrote: post #80

Earlier quoted context omitted.

But the compiler controls both the caller and callee. It doesn't need to respect any calling convention during a TCO. In fact it won't; it'll jump instead of calling.

It is usually assumed that it does not control the callee and the jump has to preserve the calling convention for a call.

If it doesn't control both then TCO is impossible, because the stack will grow with each recursive step, as it's just performing a normal call.

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

#86

Post by pjmlp » Mon, Aug 10, 2026, 7:40 PM UTC

uecker wrote: post #83

pjmlp wrote: post #74

Earlier quoted context omitted.

They never will, as mentioned they have decided not to support what became optional in C11. If C23 ever comes to land on MSVC, which I have my doubts given the radio silence on C support, I assume they might add the VLAs part that made it again back into C23.

If you care about C, use gcc.

As proven by industry adoption of clang, that isn't an option in many platforms.

Additionally clang is driving C extensions for safety that should have long been part of the language.

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

#87

Post by toast0 » Mon, Aug 10, 2026, 7:44 PM UTC

fluoridation wrote: post #80

layer8 wrote: post #77

Earlier quoted context omitted.

When the calling convention is such that the caller owns the function arguments, the callee can’t remove/replace them on the stack, but has to keep them across the tail call. In turn, it means that the callee has to clean up the arguments to the tail call, and thus can’t actually make a tail call, unless the argument list happens to be identical to the original call.

But the compiler controls both the caller and callee. It doesn't need to respect any calling convention during a TCO. In fact it won't; it'll jump instead of calling.

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

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

#88

Post by toast0 » Mon, Aug 10, 2026, 7:48 PM UTC

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 described, TCO makes a lot of sense for interpreters and state machines.

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

#89

Post by Someone » Mon, Aug 10, 2026, 7:49 PM UTC

kevincox wrote: post #39

drdexebtjl wrote: post #33

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.

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…

> I can only think of a few other optimizations that affect memory usage

Java has string interning. I think that’s a hack that shouldn’t exist in an ideal world. Reason is that, as a library writer, you cannot make the call whether to intern strings (requiring more instructions for string access, thus slowing down code, but decreasing memory usage, and, because of that, possibly speeding up the code again) or not.

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

#90

Post by fluoridation » Mon, Aug 10, 2026, 7:50 PM UTC

toast0 wrote: post #87

fluoridation wrote: post #80

Earlier quoted context omitted.

But the compiler controls both the caller and callee. It doesn't need to respect any calling convention during a TCO. In fact it won't; it'll jump instead of calling.

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