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

151–160 of 160 posts

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

#151

Post by kazinator »

cryptonector wrote: post #146
mark-probst wrote: post #142

Earlier quoted context omitted.

- The vararg function doesn't even know exactly how many args it's been passed, it only knows a lower bound (the non-variable declared args). - The trampoline is another stack frame, so putting that in would make the tail call not "proper" anymore. You could still consume an unbounded amount of stack with tail-call-only recursion. Maybe I misunderstand your idea?

The trampoline must indeed be a closure, but let's say you have a chain of main() calling f() tail-calling g() tail-calling... in all cases needing a trampoline, and some being [mutually, even] recursive, and even variadic: there is only ever one live closure: the return to the main() call site to f(), so there is no unbounded stack growth due to tail-call recursion. The trampoline would replace the {main retaddr, ma…

We have to avoid the situation whereby we have a tail calling loop, in the course of which a growing chain of these fixup thunks is accumulating, such that when we return to the original caller, a cascade of these goes off. That will clearly cause accumulation of something on the stack. Maybe we just need one global thunk. When a function sees that its return address points to the tail fixup thunk, it avoids installing another one, but instead updates some word at a well-known frame offset location to inform that thunk that more words need to be cleaned up. All of this obviously does relate to trampoline-based tail calling.

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

#152

Post by cryptonector »

brooke2k wrote: post #150

what makes TCO so difficult to implement? it feels like it should be a very simple "if the final instruction before RET is CALL, then eliminate the call" but clearly I'm missing something

In particular it's that if you return the result of a function call, then it's a tail call. For example, in `return f() + g();` neither the call to f() nor the call to g() are tail calls because they return into an expression (`+`) other than `return`.

If you scroll up you'll see a discussion of how the caller does the popping of arguments it pushed, so it has to be the case that if a different number of arguments were needed for a tail call then the caller will still pop the correct number of arguments, and that is where the complexity lies: because the caller does not actually know anything about the called function's tail call details, so how does one cause the correct thing to happen? One way is by changing the calling conventions radically to ensure that either the called function cleans up the arguments before returning, or that the number of bytes to pop is effectively part of the return signature of the function (with the caller somehow being careful to check that the advertised number wouldn't destroy its frame), or just arrange to leave exactly the number of bytes on the stack that the caller expects even if one tail-calls a function that would leave a different number of bytes.

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

#153

Post by cryptonector »

kazinator wrote: post #151
cryptonector wrote: post #146

Earlier quoted context omitted.

The trampoline must indeed be a closure, but let's say you have a chain of main() calling f() tail-calling g() tail-calling... in all cases needing a trampoline, and some being [mutually, even] recursive, and even variadic: there is only ever one live closure: the return to the main() call site to f(), so there is no unbounded stack growth due to tail-call recursion. The trampoline would replace the {main retaddr, ma…

We have to avoid the situation whereby we have a tail calling loop, in the course of which a growing chain of these fixup thunks is accumulating, such that when we return to the original caller, a cascade of these goes off. That will clearly cause accumulation of something on the stack. Maybe we just need one global thunk. When a function sees that its return address points to the tail fixup thunk, it avoids installi…

Yes, of course, the tail-calling function must recognize that its continuation is a trampoline closure, pop it, then push either a new trampoline or the original closure (if no trampoline would be needed for the particular tail-call being performed).

Do it right and there should only ever be one trampoline closure on the stack for any chain of tail calls, making the scheme O(1) in space.

So the whole protocol is that when the compiler recognizes that a call is a tail call, and one that can be turned into a jump instead of call, then the compiler must emit code to

a) pop the current continuation (which will either be the original or a trampoline that embeds the original, and from which the original can be recovered),

b) pop all the previous arguments and push all the new ones (possibly some are the same, so there is room for optimization here),

and

c) push a new continuation that is either the same as the previous current continuation or else a new continuation closure that is the correct trampoline corresponding to -and embedding- the original continuation, where the original is recovered from (a).

The trampoline recovers the original continuation, fixes the stack depth to what the caller expects, and executes a return to the original continuation.

For variadic functions it has to be the case that they have used `va_start()`, consumed all variadic arguments with `va_arg()`, then called `va_end()`, leaving no active copy of the `va_list`, then the compiler can arrange to keep a hidden local variable count of stack words used by the variadic arguments that it can use to implement the above protocol correctly.

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

#154

Post by layer8 »

fluoridation wrote: post #127
layer8 wrote: post #121

Earlier quoted context omitted.

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.

The point is that the compiler has to deal with it and has to check if the function is exported or its address is taken. So it’s a problem when implementing the compiler and adjacent tooling, you can’t just add it naively. You also have to document the side conditions under which TCO will or won’t happen, which the programmer will have to take into account.

If on the other hand the regular calling convention is compatible with TCO, then everything becomes much simpler, because it fits in with the existing model.

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

#155

Post by layer8 »

mort96 wrote: post #141
layer8 wrote: post #123

Earlier quoted context omitted.

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

No, but "this action consumes a potentially exhaustible resource and could therefore fail" is normally part of programming language semantics

Any function call can fail due to resource exhaustion (unless the language specification includes a mechanism to guarantee success, which hardly any language does). The specifications of the semantics of a programming language are usually silent on the behavior of programs under such resource failures; it’s outside of what is specified.

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

#156

Post by layer8 »

drdexebtjl wrote: post #129
layer8 wrote: post #124

Earlier quoted context omitted.

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.

I’m talking about how a programming language specification specifies the semantics of the programming language. It usually does not specify the time and space complexity of its basic operations, be it function calls or arithmetic operators. For example, multiplication could be implemented as O(n) repeated addition instead of in constant time. That would probably be a bad implementation (even on CPUs that only support addition), but it wouldn’t violate the semantics of the programming language.

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

#157

Post by fluoridation »

layer8 wrote: post #154
fluoridation wrote: post #127

Earlier quoted context omitted.

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.

The point is that the compiler has to deal with it and has to check if the function is exported or its address is taken. So it’s a problem when implementing the compiler and adjacent tooling, you can’t just add it naively. You also have to document the side conditions under which TCO will or won’t happen, which the programmer will have to take into account. If on the other hand the regular calling convention is compa…

>The point is that the compiler has to deal with it and has to check if the function is exported or its address is taken.

Like I said in a different comment below, these are not obstacles for TCO. The compiler can simply emit a second copy of the function that doesn't need to honor a calling convention.

>So it’s a problem when implementing the compiler and adjacent tooling

Yeah, implementing a compiler is difficult work. Who ever said otherwise? I originally responded to a comment talking about TCO being incompatible with certain calling conventions. I.e. if your platform uses a certain calling convention then TCO is impossible. That's what it means for two things to be incompatible: you can have either one or the other, but not both at the same time.

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

#158

Post by torginus »

toast0 wrote: post #88
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 descri…

The first one, in that it expresses intent, not implementation, which is why most languages you have `filter` and `map` methods that abstract over recursion, and most people use `foreach` instead of `for(int i=0;...` in procedural ones

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

#159

Post by torginus »

noelwelsh wrote: post #82
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...

I get that, but a lot of C interpreters use switch, for example Lua:

https://www.lua.org/source/5.5/lvm.c.html#vmdispatch

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

#160

Post by mort96 »

layer8 wrote: post #155
mort96 wrote: post #141

Earlier quoted context omitted.

No, but "this action consumes a potentially exhaustible resource and could therefore fail" is normally part of programming language semantics

Any function call can fail due to resource exhaustion (unless the language specification includes a mechanism to guarantee success, which hardly any language does). The specifications of the semantics of a programming language are usually silent on the behavior of programs under such resource failures; it’s outside of what is specified.

Yes, any function call can fail due to resource (i.e stack space) exhaustion. Other things, like integer addition or a while loop, can not. This is semantically relevant.
Post reply on HN