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

61–70 of 141 posts

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

#61

Post by eterm »

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.

C# is an interesting case because it shares a common runtime with F#, and F# guarantees TCO in most circumstances ( try / catch can stop it ) .

There is a "tail" prefix in the intermediate language (IL) bytecode that F# uses but Roslyn, the C# compiler, never emits.

So unlike F#, whether the same algorithm written in C# becomes a loop depends on JIT behaviour. This means if you're coming to a function cold in C# you can overflow the stack, while if you enter the same function fresh after it's been warmed up, it may have been optimised away by RyuJIT and if so you are able to call it safely for what would be large numbers of recursions.

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

#62

Post by fweimer »

StilesCrisis wrote: post #35
tialaramex wrote: post #18

Earlier quoted context omitted.

I am not a Clang expert, but first, obviously that's a C++ attribute and so while Clang can decide what it means in Clang in the programming language itself it has no semantic weight because the ISO document says attributes are always ignorable. Secondly however in these languages you often won't naively get TCO because you have at least one local variable which C++ would say has a "non-trivial destructor" or Rust wo…

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

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

#63

Post by cmovq »

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

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

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

#64

Post by adrian_b »

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…

Not every tail call is for a loop.

You can have a set of mutually recursive functions, which tail call each other.

In C you can write state machines using "goto" (the implementations with "switch" are typically much more inefficient), but in languages with guaranteed tail call optimizations you can write a state machine where each state is a function.

In general, it is frequent enough to call another function as the last step of a function, even when there is no recursion involved. It is quite stupid for a compiler to use a CALL in such instances, instead of using a JMP. The only problem is that the function calling convention must be compatible with this optimization, while traditionally the C language used an inefficient calling convention that is not compatible with optimizations. That convention is a residue of the time when functions could be used without being declared and it should never be used by modern compilers.

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

#65

Post by fluoridation »

adrian_b wrote: post #64
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…

Not every tail call is for a loop. You can have a set of mutually recursive functions, which tail call each other. In C you can write state machines using "goto" (the implementations with "switch" are typically much more inefficient), but in languages with guaranteed tail call optimizations you can write a state machine where each state is a function. In general, it is frequent enough to call another function as the…

I can't see why the calling convention could matter. Can you give an example?

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

#66

Post by throwaway_95283 »

mort96 wrote: post #60
guenthert wrote: post #9

Earlier quoted context omitted.

Only if they are using an insufficiently smart compiler. SBCL handles TCO just fine, as do a number of other implementations, see : https://0branch.com/notes/tco-cl.html

If it's not encoded in the language's specification, it's not a feature of the language but just an optimization. You can't rely on optimizations for correctness.

in theory, no, in practice, yes.

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

#67

Post by webstrand »

groundzeros2015 wrote: post #13
mmsc wrote: post #2

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

Js really should have it. I think the shift in style from functional and manual prototype chains to Java classes is quite disappointing.

ES6 class syntax is still mostly just syntax sugar overtop prototypical inheritance.

JS _does_ still have TCO (called Proper Tail Calls), Safari's JavaScriptCore implements it, and is technically the only conforming interpreter.

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

#68

Post by pjmlp »

jmalicki wrote: post #46
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…

JVM does a lot of escape analysis to turn heap allocated memory into stack local variables. It doesn't matter if it's local since it's a VM, it's doing it at runtime and can change an entire call stack of non local code for an optimization.

Some fact correcting, first of all while most people refer to "The JVM", most likely impling OpenJDK, Java is a standard and there are many implementations.

Which exactly in this subject varies a lot between implementations, on how well escape analysis is done, if there is a JIT cache between JVM executions, or AOT compilation.

Additionally Valhalla is finally getting added to the language with a new EA made available last week, thus value classes will add yet another way to have stack values.

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

#69

Post by mort96 »

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.

Of course. I wasn't talking about empty loops.

But also, I wouldn't rely on a compiler to remove empty 'while (true)' loops.

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

#70

Post by pjmlp »

eterm wrote: post #61
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.

C# is an interesting case because it shares a common runtime with F#, and F# guarantees TCO in most circumstances ( try / catch can stop it ) . There is a "tail" prefix in the intermediate language (IL) bytecode that F# uses but Roslyn, the C# compiler, never emits. So unlike F#, whether the same algorithm written in C# becomes a loop depends on JIT behaviour. This means if you're coming to a function cold in C# you…

The interesting case is the Common Language Runtime, not C#.

> More than 20 programming tools vendors offer some 26 programming languages — including C++, Perl, Python, Java, COBOL, RPG and Haskell — on .NET.

https://news.microsoft.com/source/2001/10/22/massive-industr...

MSIL thus had to support all of them.

Those differences between language semantics is why CLS was also a thing back then.

https://learn.microsoft.com/en-us/dotnet/standard/language-i...

Post reply on HN