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

101–110 of 139 posts

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

#101

Post by throwaway81523 »

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.

You can rely on it now in gcc and clang, in the sense that they support a [[musttail]] attribute that tells the compiler to report an error if a call can't be TCO'd. The language doesn't guarantee TCO but can implement it at its option. If your program uses the attribute and still compiles, it means it has compiled with proper TCO.

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

#102

Post by mpyne »

cmovq wrote: post #63
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)'.

Note that compilers are more than happy to delete 'while (true)' if the loop doesn't have side-effects.

I think this is no longer true. C++26 implemented a change to make trivial loops like these defined behavior (and therefore will loop endlessly as you'd expect). And this example was always defined behavior in C.

Both languages continue to have examples of slightly more complicated loops that can be assumed to terminate in the absence of side effects, but `while(true)` isn't one of those any longer.

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

#103

Post by uecker »

pjmlp wrote: post #86
uecker wrote: post #83

Earlier quoted context omitted.

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.

IMHO gcc has better warnings and support for safety. Industry mostly wants a BSD-licensed toolchain. I could not care less.

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

#104

Post by qsera »

lilbigdoot wrote: post #51
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 my program crashes without it, that's a semantic difference no?

You program did not ask for the crash via the language constructs..semantics is defined by the language, rest is the implementation details. That is how it makes sense to me. I don't understand other people in this thread who think otherwise.

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

#105

Post by vanderZwan »

Someone wrote: post #89
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…

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

> requiring more instructions for string access

Wait, why would interned immutable strings require more instructions when doing regular string access? You can still point to the start of a zero-terminated C-string, it just requires storing extra metadata like lenght and a string hash somewhere. Which can be done at the negative indices of said pointer.

Or do you refer to the extra rolling-hash pass needed when concatenating two strings to verify if it would result in an already-interned one? Because yes, that's one extra rolling hast pass over the appended string the first time a string is constructed, but after that doing so again likely saves memory and construction time, because any concatenation that would result in an already interned string would avoid actual memory allocation and copying of the string's characters.

Plus string comparisons become cheap O(1) pointer comparisons this way, which is really nice in many use-cases.

And that's not even considering more advanced tricks like interning short strings in the 64-bit word of the pointer to the string itself, relying on the fact that modern memory allocators never return an address with the lsb set, so it can be used to flag it as such[0].

[0] https://squoze.org/

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

#106

Post by teo_zero »

fluoridation wrote: post #99
toast0 wrote: post #97

Earlier quoted context omitted.

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…

h() can't have more arguments than g(): that's an important limitation.

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

#107

Post by sparkie »

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?

Continuation Passing Style - an important construction for interpreters, but which is also useful for compilers as it's a nice way to do control flow analysis, data flow analysis and more.

The missing feature is closures - functions which capture values from their static environment, which are basically needed to make CPS useful. GCC has nested functions, but they cannot capture without making the stack executable, which is terrible. There's a proposal[1] to get closures into C, but at present you need to simulate the capturing yourself, which is cumbersome, but can be done efficiently.

[1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...

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

#108

Post by fsckboy »

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…

>It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program

it is guaranteed in Scheme, and it affects the semantics of programs in a completely positive way.

Much of computer science is "pure" and "abstract" like mathematics. However, programmers are still taught to use loops to calculate factorial rather than recursion in order to avoid stack overflow. In Scheme you can use recursion without flinching. That is a semantic difference.

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

#109

Post by fluoridation »

teo_zero wrote: post #106
fluoridation wrote: post #99

Earlier quoted context omitted.

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

h() can't have more arguments than g(): that's an important limitation.

Consider what was being discussed originally, though. If h() has fewer arguments than g() and is in a different module (e.g. a static library) from h() such that the calling convention was necessary, how would h() recurse back to g()?

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

#110

Post by cryptonector »

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.

Post reply on HN