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

51–60 of 139 posts

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

#51

Post by lilbigdoot »

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…

If my program crashes without it, that's a semantic difference no?

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

#52

Post by chriswarbo »

tialaramex wrote: post #34
chriswarbo wrote: post #10

Earlier quoted context omitted.

Sounds similar to @tailrec in Scala I personally use the phrase "tail call elimination" when it's a requirement that can be relied on; and "tail call optimisation" when it might be implementation-dependent, context-dependent, limited (e.g. to immediate self-calls), etc.

I am definitely not a Scala expert. As I wrote in a sibling comment, the key benefit here is the extra work from the compiler to deliver what you wanted, on top of the diagnostic if it can't. I don't know if Scala has the problem that `become` addresses (C++ calls this RAII, but I have no idea what Scala would call it if they have the same idea) However in my brief attempt to validate what Scala does do here, I found…

I jsut did some digging and it seems you're right, it's only for methods which call themselves (which indeed get compiled into a loop, as an entirely local transformation). So not hugely useful.

Apologies, I've not written Scala for many years; I just recalled that there was a way to annotate tail calls which the compiler checks. I didn't realise it was so limited!

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

#53

Post by adrian_b »

derdi wrote: post #24
messe wrote: post #5

> In 2001 Mark Probst implemented tail-call optimization in GCC with a separate calling convention; he lists the limitations of the then-existing tail-call optimization in GCC in section 6.4, among them: "It cannot handle indirect calls" (which would have been used in tail calls for interpreter dispatch). Relatively recent being a quarter of century? Or at least a fifth of a century for indirect calls[1] (GCC 3.4.6 i…

Given that GCC was first released in 1987, that would mean that tail call optimization, including of indirect calls, has been around for more than half of GCC's lifetime. So it's indeed fair for the parent article to say that "[GCC has] had tail-call optimizations for most of [its] existence".

That is not exactly true, because for a long time tail call optimizations had a lot of restrictions in gcc, so they could be used only seldom.

What is said in TFA is correct in the sense that only in recent years the support for tail call optimization became good enough to be able to rely on it, if you use appropriate compilation options.

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

#54

Post by ux266478 »

guenthert wrote: post #14
pfdietz wrote: post #11

Earlier quoted context omitted.

Even SBCL doesn't do TCO at all times. Compiling at (debug 3) means no TCO. Another related footgun is deep recursion of other kinds, for example when recursively traversing down lists. For long lists it's easy to exceed the stack size limit. The common idiom is to recur on list elements, but iterate or map to go along a list.

> Even SBCL doesn't do TCO at all times. Compiling at (debug 3) means no TCO. Presumably one intends to debug the code, when setting (debug 3). Then it'll be helpful to see the stack, no? > Another related footgun is deep recursion of other kinds, for example when recursively traversing down lists. For long lists it's easy to exceed the stack size limit. The common idiom is to recur on list elements, but iterate or m…

> Presumably one intends to debug the code, when setting (debug 3). Then it'll be helpful to see the stack, no?

You don't necessarily need to give up TCO to do that though. You just do some bookkeeping and synthesize virtual stack frames. DWARF has native facilities to handle this.

CL goes the route it does mostly out of history, which includes the fact it has its own debugging ecosystem, more than any fundamental technical reason. There are technical hurdles with doing this in an image-based dynamic compilation model, but it's very far from intractable. Especially if you just do what GHC did and add a DWARF workflow. Most CL users wouldn't ever touch it though, because that's a drastically different debugging model that costs them a lot of ergonomic power, which may even be the reason they're working in CL to begin with.

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

#55

Post by tialaramex »

steveklabnik wrote: post #45
im3w1l wrote: post #32

Earlier quoted context omitted.

Reordering destructors is not safe in C++, as it's fairly common to rely on objects being destroyed in reverse order and doing stuff like A a; B b(&a); In rust the borrow checker would guard against reordering such things, but a caveat is that there might be unsafe code relying on drop-order which the borrow checker would be oblivious to. There could also potentially be objects representing external resources like a…

> In rust the borrow checker would guard against reordering such things It doesn't even get that far: Rust guarantees that things drop in reverse order of declaration, full stop. One interesting wrinkle here: for struct members, Rust does the opposite of what C++ does. We debated changing it to match, but > there might be unsafe code relying on drop-order which the borrow checker would be oblivious to. There was no s…

> It doesn't even get that far: Rust guarantees that things drop in reverse order of declaration, full stop.

The drops happen (if implemented) in the same order, but in a different place, half the point of become is to put any needed drops first before the call, as otherwise it's not in tail position and we can't do the optimisation.

So the borrowck can become involved if our become foo(bar, &baz) borrows baz but baz's type impl Drop - the diagnostics aren't great today, but then the feature isn't finished so it's not a priority.

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

#56

Post by mort96 »

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…

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

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

#57

Post by torginus »

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
is not tail recursive, and will overflow if the compiler fails to optimize.

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

#58

Post by mort96 »

throw838489448 wrote: post #43
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.

Some languages have TCO annotation, it throws compiler error if TCO fails. You want stronger type system, not smart compiler guarantees or promises!

That's not a type system thing... Whether a call gets TCO'd isn't represented in the type system if it's just an annotation on a return statement.

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

#59

Post by steveklabnik »

tialaramex wrote: post #55
steveklabnik wrote: post #45

Earlier quoted context omitted.

> In rust the borrow checker would guard against reordering such things It doesn't even get that far: Rust guarantees that things drop in reverse order of declaration, full stop. One interesting wrinkle here: for struct members, Rust does the opposite of what C++ does. We debated changing it to match, but > there might be unsafe code relying on drop-order which the borrow checker would be oblivious to. There was no s…

> It doesn't even get that far: Rust guarantees that things drop in reverse order of declaration, full stop. The drops happen (if implemented) in the same order, but in a different place, half the point of become is to put any needed drops first before the call, as otherwise it's not in tail position and we can't do the optimisation. So the borrowck can become involved if our become foo(bar, &baz) borrows baz but baz…

I was talking about regular old today's Rust, not the specifics about become.

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

#60

Post by mort96 »

guenthert wrote: post #9
pfdietz wrote: post #3

Earlier quoted context omitted.

Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.

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.
Post reply on HN