Live data from Hacker News

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

lwn.net

121–130 of 132 posts

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

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

If the callee is an exported symbol, the compiler has no choice but to adhere to the calling convention. For the C model of translation units that's the default, only local (declared "static") functions are exempted, and usually also only if their address is not taken. More generally, when the tail call crosses the boundaries of modularization that are supported by separate compilation, a recompilation step at the module-linking level would be required. The other complication is function pointers, which assume a specific calling convention, so either you have to have different function-pointer types with different calling conventions, or the compiler has to generate thunks or similar that translate between different calling conventions.

Of course, a language implementation can arrange for all that; but clearly, calling conventions are relevant here.

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

#122
post #84

Earlier quoted context omitted.

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.

It's possible for calling conventions where the callee is responsible for stack cleanup before return.

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

#123
post #78
post #75

Earlier quoted context omitted.

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.

The specification allows implementations to have limits on maximum call stack depth and all sorts of other things. It's absolutely semantically meaningful in C to allocate a new stack frame.

The details of how a stack is managed isn't normally part of programming language semantics.

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

#124
post #75

Earlier quoted context omitted.

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

Programming language semantics as in https://en.wikipedia.org/wiki/Semantics_(programming_languag... is usually decoupled from space complexity. An interpreter or emulator is considered to preserve language semantics even if it changes time or space complexity.

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

#125

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…

> because it doesn't affect the semantics of the program

It does when you use them as a feature and not an optimization. Like in interpreters, state machines, parsers, etc.

Calling tail calls an optimization set computer science back 40 years.

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

#126
post #75
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.

Tail call elimination often is part of the language semantics though, for the reason others in this thread have described. E.g. Scheme specifies when a conformant implementation is required to eliminate tail calls: https://conservatory.scheme.org/schemers/Documents/Standards...

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

#127
post #121

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.

If the callee is an exported symbol, the compiler has no choice but to adhere to the calling convention. For the C model of translation units that's the default, only local (declared "static") functions are exempted, and usually also only if their address is not taken. More generally, when the tail call crosses the boundaries of modularization that are supported by separate compilation, a recompilation step at the mo…

Do you often find yourself doing mutual recursion between functions crossing compilation units/modules? I'm not going to say it can't happen, I just don't see it as much of a problem.

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

#128

> In 2001 Mark Probst implemented tail-call optimization in GCC That's me. The motivation back then was to allow compilers that target C to assume that tail calls will be "proper". That's different from an optimization, which is usually optional, and which compilers don't guarantee. The LWN post briefly sketches why this is hard: C allows variable-argument functions (like printf) where only the caller knows for sure…

That is a very cool contribution, I actually didn't know that it required a new calling convention! I look forward to reading your thesis

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

#129
post #124

Earlier quoted context omitted.

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

Programming language semantics as in https://en.wikipedia.org/wiki/Semantics_(programming_languag... is usually decoupled from space complexity. An interpreter or emulator is considered to preserve language semantics even if it changes time or space complexity.

We're talking about the same thing. I disagree. Such interpreter or emulator would preserve _some_ language semantics, but not all.

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

#130
post #128

> In 2001 Mark Probst implemented tail-call optimization in GCC That's me. The motivation back then was to allow compilers that target C to assume that tail calls will be "proper". That's different from an optimization, which is usually optional, and which compilers don't guarantee. The LWN post briefly sketches why this is hard: C allows variable-argument functions (like printf) where only the caller knows for sure…

That is a very cool contribution, I actually didn't know that it required a new calling convention! I look forward to reading your thesis

Let's assume that parameter are all the same size and put on a stack.

If you know that you are an M-parameter function being called, and you want to tail cal an N-parameter function, where N Suppose N > M. Things start to get tricky. There isn't space in our original argument space for N. If we increase the space, the original caller won't clean it up properly. If we just allocate a new space of N, we are not making a tail call.

Because we want to make a tail call, it means we don't expect to execute any code in this function any more, and are free to trash the local variables. We can move the stack down a bit to make room for N arguments above where previously we were given M by our caller. To solve the problem that our caller wants to clean up M, but we need it to clean up N could be solved by a trampoline. We prime the stack such that when the tail-called function we are targeting returns, it will not go to our caller directly but to a stub function. That stub function will clean up the N-M words of the stack, leaving M, and then return to the original caller, which cleans up M.

In this situation, we are benefiting from knowing that the caller passed M to us. In the case of a variadic function, we don't know at all. It could just be the fixed arguments (parameters before the ellipsis) like printf("hello\n'), or any number. There is a run-time protocol to discover what parameters there are; the application logic figures it out from the arbitrary conventions. That's too late and too ad hoc for compile time.

I think yuo can reason about it similarly to above. If we are a variadic with M fixed parameters, we know we are called with at least M arguments, so we can place N M, we can extend to make up the difference and use the trampoline to clean up and return to the original caller.

sThese trampolines are not closures; they are behind-the-scenes that can be generated as static code; no executable heaps or stacks required.

Post reply on HN