6 ms·

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

171 points by prakashqwerty 2mo ago

mmsc 2mo ago
and TCO was added then removed from js! https://stackoverflow.com/a/54721813 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-stack-overflow https://joshua.hu/javascript-infinite-tail-call-recursion-st...)
- pfdietz 2mo ago
  Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.
  - tialaramex 2mo ago
    This footgun is the reason I'm so enthusiastic about the Rust `become` keyword. This proposal would give Rust a specific keyword which says that you intend TCO and so two things happen: 1. The compiler goes to more length to deliver TCO even where it wouldn't "just work" and 2. If it cannot deliver TCO your code doesn't compile, because you asked for TCO.
    - StilesCrisis 2mo ago
      Sounds like clang::must_tail?
      - tialaramex 2mo ago
        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 would say "implements Drop". These both mean that naively the "tail call" wasn't actually the last thing to happen, the destructor / Drop::drop happen at the end of the function, after the tail call. The proposed become keyword tries to core::mem::drop any such variables, if it succeeds now that tail call is last and we can do TCO, if it fails [e.g. because the variables it wants to drop are needed for the tail call] we can diagnose the problem. I believe the Clang attribute doesn't have this behaviour.
        im3w1l 2mo ago
        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 temp file where dropping them out of order leads to issues.
        tialaramex 2mo ago
        That Rust was in fact always unsound if it would cause problems to core::mem::drop(a); and the `become` call just drops things so it's the same. Safe-but-undesirable outcomes are acceptable. For example maybe our tail call ends up reverting a database transaction and we wish it were otherwise. But if the code did compile but wasn't memory safe as a result of this new drop then it was always unsound and shouldn't have existed. Just as the guts of some STL classes are very complicated in order to deliver the promised exception safety promises, the guts of unsafe Rust code are often tricky for similar reasons, you are mandated to deliver safety, it's not up to you to say "That's stupid, don't do that" either ensure it won't compile or safely cope.
        steveklabnik 2mo ago
        > 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 super real compelling argument to choose one direction over the other in the abstract, and "be the same as C++" was not considered important enough to risk breaking unsafe code that relied on the (what was at the time) implementation defined behavior.
        tialaramex 2mo ago
        > 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.
    - chriswarbo 2mo ago
      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.
      - tialaramex 2mo ago
        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 discussion of "always" optimising to a loop which is a bad sign. Tail recursion is an elegant way to write some loops but that's not the only thing it's useful for, and it seems as though Scala just doesn't care about other cases, at least for @tailrec One thing you want TCO for in a language like Rust with lots of monomorphisation is to avoid function call overhead for the deliberately out-of-line slow path in some code. So in this case there was never an implied loop and we're not averting a stack overflow, we wanted to do a single instruction pointer change instead of an expensive function call wrapper. Seems like @tailrec isn't for that.
        chriswarbo 2mo ago
        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!
        pjmlp 2mo ago
        Scala is in the way to get capture checking for effects, which will allow to do RAII like stuff, or borrow checker like stuff for that matter.
    - jmalicki 2mo ago
      Does 1 really happen? I would never trust a compiler where 1 was a possibility. If it can work it should.
  - guenthert 2mo ago
    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 https://0branch.com/notes/tco-cl.html
    - pfdietz 2mo ago
      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.
      - guenthert 2mo ago
        > 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 map to go along a list. Not going to argue with seasoned lispers here, but IMHO recursive code makes most sense when accessing recursive data structures.
        pfdietz 2mo ago
        One place where this shows up is in parse trees. The grammar for a list of things may involve productions that look like list constructors. This, directly translated into a data structure, would give a very long chain of parse tree nodes dangling off to the right. It's a recursive data structure, but a very deep one for large lists, and traversing it recursively can use a lot of stack. This can also be seen as an argument against building parse trees that way. Instead, have a node with an unbounded number of children, the elements of the list.
        ux266478 2mo ago
        > 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.
  - pjmlp 2mo ago
    Mostly because they forget Scheme is one of the few languages where TCO is part of the language standard, making it a required feature for any compliant implementation. This has always been an issue regarding TCO support across programming languages.
    - pfdietz 2mo ago
      Well, and also because of the "I've been told in Scheme you should do it this way, so by gum I'm going to do it this way!"
- groundzeros2015 2mo ago
  Js really should have it. I think the shift in style from functional and manual prototype chains to Java classes is quite disappointing.
  - chuckadams 2mo ago
    Technically TCO is still in the spec, TC39 deadlocked over modifying it. TC39 really does not fill me with confidence in general.
  - webstrand 2mo ago
    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.
    - groundzeros2015 2mo ago
      Yes but the syntax encourages patterns which would be uncommon in pre-ES6 JS. I can’t rely on TCO if chromium doesn’t have it.
kenjin4096 2mo ago
I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there! On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.
- pjmlp 2mo ago
  It still doesn't, this is a compiler specific language extension. You won't find anything on ISO/IEC 9899:2024 about tail calls, like it happens on Scheme. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf Section 3.5 of R7RS. https://standards.scheme.org/official/r7rs.pdf https://standards.scheme.org/official/r7rs.pdf
  - wahern 2mo ago
    A formal technical specification (TS) extension is already being drafted: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3582.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3582.pdf That's a step up from the usual proposals. I'm not sure what criteria is used to decide whether to first create a TS vs just incorporating a change into the working draft of the next standard.[1] _Defer also seems to be taking the TS route.[2] 1. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3886.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3886.pdf 2. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3928.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3928.pdf
    - pjmlp 2mo ago
      Well, even if that lands on the official standard, that means C29 as probable release year for C2y, plus adoption of the exact form across compilers to be able to rely on it being available.
      - Someone 2mo ago
messe 2mo ago
> 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 is the earliest I see on Compiler Explorer, released March 2006). [1]: https://godbolt.org/z/vvcnn54oM https://godbolt.org/z/vvcnn54oM
- derdi 2mo ago
  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".
  - adrian_b 2mo ago
    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.
- coliveira 2mo ago
  For people who passed their 30s, everything that happened after their 20th birthday is recent. For me, September 11 is recent memory, as well as the 2008 great recession.
nyeah 2mo ago
>That quote is the article, and it's a little surprising that it's buried so far into the content Is it really surprising in 2026? Today's online writing style is not primarily designed to communicate. It's designed to keep the reader 'engaged' for as long as possible. The reader's time is a resource to be extracted. I'm absolutely not poking this author individually. It's the writing style of the net.
- derdi 2mo ago
  I was wondering what this was in reference to; it's not in reference to TFA here. It's a quote from https://bytecode.news/posts/2026/08/because-it-s-not-fun-enough https://bytecode.news/posts/2026/08/because-it-s-not-fun-eno..., so presumably you meant to post this over at https://news.ycombinator.com/item?id=49242245 https://news.ycombinator.com/item?id=49242245.
  - nyeah 2mo ago
    Oh, good point, thanks.
deleted 2mo ago
[deleted]
swiftcoder 2mo ago
> In 2001 Mark Probst implemented tail-call optimization in GCC MSVC didn't add tail-call optimisation until sometime in the 2010s, IIRC. I distinctly remember sending a tail-recursive C++ program to someone who developed on Windows, and it crashing, in the late mid-to-late 2000s.
- throw-qqqqq 2mo ago
  MSVC stands for MicroSoft Visual C++ compiler AFAIK. It famously doesn’t support a few features of C99. They don’t really seem to care much about regular C support (non-C++).
  - pjmlp 2mo ago
    They officially saw no need for C support going forward. https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-and-c99 https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an... Note, "If you really need either of the following.....then we recommend that you consider using a different compiler such as Intel or gcc (short-term) and/or pressure your standards committee representatives to have ISO C++ include more of the C standard (longer-term)." Which is kind of why nowadays clang is part of Visual Studio as well. However, after Satya got into the whole Microsoft <3 FOSS, this changed a bit, https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-support-arriving-in-msvc https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-... There are a few blogs after that, so at least up to C17 minus the optional parts from C11, the support is there. It remains to be seen if anything C23 or later will ever come into MSVC, and then again, clang is part of VS installer.
    - throw-qqqqq 2mo ago
      TIL, thanks for updating me on this! I read Herb Sutter’s post many years ago, but didn’t know they had picked up the work again. I see that VLAs are still not supported, which is a shame IMO, but the C-support seems much better than it used to be at least.
      - 2mo ago
hnfvovpje4 2mo ago
[flagged]
drdexebtjl 2mo ago
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.
- LukeShu 2mo ago
  GCC has `[[gnu::musttail]] return`. But yes, framing TCO as an optimization is unfortunate.
  - vinkelhake 2mo ago
    And there's also [[clang::musttail]] and [[msvc::musttail]]. As well as an effort to get it standardized: https://isocpp.org/files/papers/D3939R0.html https://isocpp.org/files/papers/D3939R0.html (in C++).
- kevincox 2mo ago
  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 considering things like `musttail` attributes so that the code fails to compile rather than misses the optimization. I can only think of a few other optimizations that affect memory usage. Register spilling (arguably not really an optimization but a necessity), Rust's niche filling for enum discriminants and C++'s std::vec<bool> (a language-level optimization, arguably a different thing entirely). I often think about how few memory optimizations we have. The reason is most likely that they tend to be non-local so are much harder to apply than CPU optimizations that generally have no effect outside of the function they are in.
  - steveklabnik 2mo ago
    > It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program. Depends on the semantics of the programming language itself. For some languages, it is truly an optimization, for some, it is required, and does meaningfully change observed semantics.
steveklabnik 2mo ago
(2025)
torginus 2mo ago
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 <= 1 then 1 else n * factorial (n - 1) is not tail recursive, and will overflow if the compiler fails to optimize.
- adrian_b 2mo ago
  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.
  - fluoridation 2mo ago
    I can't see why the calling convention could matter. Can you give an example?
    - layer8 2mo ago
      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.
amavect 2mo ago
I recently played around with what I call "manual tail-call optimization": transform a tail call to a goto to the beginning of the function. Check it out: https://godbolt.org/z/3fY1v1oeW https://godbolt.org/z/3fY1v1oeW int factorial_loop_iterative(int n, int a){ while(n > 0){ a = a * n; n = n - 1; } return a; } int factorial_loop_recursive(int n, int a){ if(n > 0){ return factorial_loop_recursive(n - 1, a * n); }else{ return a; } } int factorial_loop_manual(int n, int a){ tailcall: if(n > 0){ a = a * n; n = n - 1; goto tailcall; }else{ return a; } } int (*factorial_loop)(int n, int a) = factorial_loop_manual; int factorial(int n){ return factorial_loop(n, 0); } I recommend against, of course! Incorrectly sequencing the manual version results in bugs (swap the assignment for n and a), which the recursive version doesn't need to care about.
- zamadatix 2mo ago
  Seems like a complex way to write a normal looped version. Apart from factorial_loop_manual() being one in design, its name even says as much.
throwaway81523 2mo ago
GCC has had TCO since the 1980s I'm pretty sure. Since then it's been extended to work in more contexts.
cryptonector 2mo ago
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.
reindeer2 2mo ago
[flagged]
mark-probst 2mo ago
> 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 how many arguments it passed, which means that only the caller can clean up the stack, unless the stack frame size is also communicated, which "normal" C calling conventions don't do. But when the callee does a proper tail call, the stack frame that returns to the callee is not the stack frame that the callee originally sent. This is explained in more detail in my thesis starting on page 16: https://hostr.flingit.run/s/proper-tail-calls.pdf https://hostr.flingit.run/s/proper-tail-calls.pdf
- deleted 2mo ago
  [deleted]
- anitil 2mo ago
  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
  - kazinator 2mo ago
    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 <= M, then you can just place the new N parameters in the same space on the stack where you received your M parameters, and jump to that function. That function will return to your original caller, which will remove the M parameters, not caring that some of them are not the originals that it passed. 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 tail-callee arguments into the variadic space and proceed accordingly. For 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.
brooke2k 2mo ago
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
- cryptonector 2mo ago
  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.

171 points by prakashqwerty 2mo ago

mmsc 2mo ago

and TCO was added then removed from js! https://stackoverflow.com/a/54721813 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-stack-overflow https://joshua.hu/javascript-infinite-tail-call-recursion-st...)

pfdietz 2mo ago
Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.
- tialaramex 2mo ago
  This footgun is the reason I'm so enthusiastic about the Rust `become` keyword. This proposal would give Rust a specific keyword which says that you intend TCO and so two things happen: 1. The compiler goes to more length to deliver TCO even where it wouldn't "just work" and 2. If it cannot deliver TCO your code doesn't compile, because you asked for TCO.
  - StilesCrisis 2mo ago
    Sounds like clang::must_tail?
    - tialaramex 2mo ago
      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 would say "implements Drop". These both mean that naively the "tail call" wasn't actually the last thing to happen, the destructor / Drop::drop happen at the end of the function, after the tail call. The proposed become keyword tries to core::mem::drop any such variables, if it succeeds now that tail call is last and we can do TCO, if it fails [e.g. because the variables it wants to drop are needed for the tail call] we can diagnose the problem. I believe the Clang attribute doesn't have this behaviour.
      - im3w1l 2mo ago
        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 temp file where dropping them out of order leads to issues.
        tialaramex 2mo ago
        That Rust was in fact always unsound if it would cause problems to core::mem::drop(a); and the `become` call just drops things so it's the same. Safe-but-undesirable outcomes are acceptable. For example maybe our tail call ends up reverting a database transaction and we wish it were otherwise. But if the code did compile but wasn't memory safe as a result of this new drop then it was always unsound and shouldn't have existed. Just as the guts of some STL classes are very complicated in order to deliver the promised exception safety promises, the guts of unsafe Rust code are often tricky for similar reasons, you are mandated to deliver safety, it's not up to you to say "That's stupid, don't do that" either ensure it won't compile or safely cope.
        steveklabnik 2mo ago
        > 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 super real compelling argument to choose one direction over the other in the abstract, and "be the same as C++" was not considered important enough to risk breaking unsafe code that relied on the (what was at the time) implementation defined behavior.
        tialaramex 2mo ago
        > 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.
  - chriswarbo 2mo ago
    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.
    - tialaramex 2mo ago
      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 discussion of "always" optimising to a loop which is a bad sign. Tail recursion is an elegant way to write some loops but that's not the only thing it's useful for, and it seems as though Scala just doesn't care about other cases, at least for @tailrec One thing you want TCO for in a language like Rust with lots of monomorphisation is to avoid function call overhead for the deliberately out-of-line slow path in some code. So in this case there was never an implied loop and we're not averting a stack overflow, we wanted to do a single instruction pointer change instead of an expensive function call wrapper. Seems like @tailrec isn't for that.
      - chriswarbo 2mo ago
        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!
      - pjmlp 2mo ago
        Scala is in the way to get capture checking for effects, which will allow to do RAII like stuff, or borrow checker like stuff for that matter.
  - jmalicki 2mo ago
    Does 1 really happen? I would never trust a compiler where 1 was a possibility. If it can work it should.
- guenthert 2mo ago
  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 https://0branch.com/notes/tco-cl.html
  - pfdietz 2mo ago
    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.
    - guenthert 2mo ago
      > 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 map to go along a list. Not going to argue with seasoned lispers here, but IMHO recursive code makes most sense when accessing recursive data structures.
      - pfdietz 2mo ago
        One place where this shows up is in parse trees. The grammar for a list of things may involve productions that look like list constructors. This, directly translated into a data structure, would give a very long chain of parse tree nodes dangling off to the right. It's a recursive data structure, but a very deep one for large lists, and traversing it recursively can use a lot of stack. This can also be seen as an argument against building parse trees that way. Instead, have a node with an unbounded number of children, the elements of the list.
      - ux266478 2mo ago
        > 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.
- pjmlp 2mo ago
  Mostly because they forget Scheme is one of the few languages where TCO is part of the language standard, making it a required feature for any compliant implementation. This has always been an issue regarding TCO support across programming languages.
  - pfdietz 2mo ago
    Well, and also because of the "I've been told in Scheme you should do it this way, so by gum I'm going to do it this way!"
groundzeros2015 2mo ago
Js really should have it. I think the shift in style from functional and manual prototype chains to Java classes is quite disappointing.
- chuckadams 2mo ago
  Technically TCO is still in the spec, TC39 deadlocked over modifying it. TC39 really does not fill me with confidence in general.
- webstrand 2mo ago
  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.
  - groundzeros2015 2mo ago
    Yes but the syntax encourages patterns which would be uncommon in pre-ES6 JS. I can’t rely on TCO if chromium doesn’t have it.

kenjin4096 2mo ago

I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there! On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.

pjmlp 2mo ago
It still doesn't, this is a compiler specific language extension. You won't find anything on ISO/IEC 9899:2024 about tail calls, like it happens on Scheme. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf Section 3.5 of R7RS. https://standards.scheme.org/official/r7rs.pdf https://standards.scheme.org/official/r7rs.pdf
- wahern 2mo ago
  A formal technical specification (TS) extension is already being drafted: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3582.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3582.pdf That's a step up from the usual proposals. I'm not sure what criteria is used to decide whether to first create a TS vs just incorporating a change into the working draft of the next standard.[1] _Defer also seems to be taking the TS route.[2] 1. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3886.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3886.pdf 2. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3928.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3928.pdf
  - pjmlp 2mo ago
    Well, even if that lands on the official standard, that means C29 as probable release year for C2y, plus adoption of the exact form across compilers to be able to rely on it being available.
    - Someone 2mo ago

messe 2mo ago

> 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 is the earliest I see on Compiler Explorer, released March 2006). [1]: https://godbolt.org/z/vvcnn54oM https://godbolt.org/z/vvcnn54oM

derdi 2mo ago
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".
- adrian_b 2mo ago
  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.
coliveira 2mo ago
For people who passed their 30s, everything that happened after their 20th birthday is recent. For me, September 11 is recent memory, as well as the 2008 great recession.

nyeah 2mo ago

>That quote is the article, and it's a little surprising that it's buried so far into the content Is it really surprising in 2026? Today's online writing style is not primarily designed to communicate. It's designed to keep the reader 'engaged' for as long as possible. The reader's time is a resource to be extracted. I'm absolutely not poking this author individually. It's the writing style of the net.

derdi 2mo ago
I was wondering what this was in reference to; it's not in reference to TFA here. It's a quote from https://bytecode.news/posts/2026/08/because-it-s-not-fun-enough https://bytecode.news/posts/2026/08/because-it-s-not-fun-eno..., so presumably you meant to post this over at https://news.ycombinator.com/item?id=49242245 https://news.ycombinator.com/item?id=49242245.
- nyeah 2mo ago
  Oh, good point, thanks.

deleted 2mo ago

[deleted]

swiftcoder 2mo ago

> In 2001 Mark Probst implemented tail-call optimization in GCC MSVC didn't add tail-call optimisation until sometime in the 2010s, IIRC. I distinctly remember sending a tail-recursive C++ program to someone who developed on Windows, and it crashing, in the late mid-to-late 2000s.

throw-qqqqq 2mo ago
MSVC stands for MicroSoft Visual C++ compiler AFAIK. It famously doesn’t support a few features of C99. They don’t really seem to care much about regular C support (non-C++).
- pjmlp 2mo ago
  They officially saw no need for C support going forward. https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-and-c99 https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an... Note, "If you really need either of the following.....then we recommend that you consider using a different compiler such as Intel or gcc (short-term) and/or pressure your standards committee representatives to have ISO C++ include more of the C standard (longer-term)." Which is kind of why nowadays clang is part of Visual Studio as well. However, after Satya got into the whole Microsoft <3 FOSS, this changed a bit, https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-support-arriving-in-msvc https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-... There are a few blogs after that, so at least up to C17 minus the optional parts from C11, the support is there. It remains to be seen if anything C23 or later will ever come into MSVC, and then again, clang is part of VS installer.
  - throw-qqqqq 2mo ago
    TIL, thanks for updating me on this! I read Herb Sutter’s post many years ago, but didn’t know they had picked up the work again. I see that VLAs are still not supported, which is a shame IMO, but the C-support seems much better than it used to be at least.
    - 2mo ago

hnfvovpje4 2mo ago

[flagged]

drdexebtjl 2mo ago

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.

LukeShu 2mo ago
GCC has `[[gnu::musttail]] return`. But yes, framing TCO as an optimization is unfortunate.
- vinkelhake 2mo ago
  And there's also [[clang::musttail]] and [[msvc::musttail]]. As well as an effort to get it standardized: https://isocpp.org/files/papers/D3939R0.html https://isocpp.org/files/papers/D3939R0.html (in C++).
kevincox 2mo ago
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 considering things like `musttail` attributes so that the code fails to compile rather than misses the optimization. I can only think of a few other optimizations that affect memory usage. Register spilling (arguably not really an optimization but a necessity), Rust's niche filling for enum discriminants and C++'s std::vec<bool> (a language-level optimization, arguably a different thing entirely). I often think about how few memory optimizations we have. The reason is most likely that they tend to be non-local so are much harder to apply than CPU optimizations that generally have no effect outside of the function they are in.
- steveklabnik 2mo ago
  > It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program. Depends on the semantics of the programming language itself. For some languages, it is truly an optimization, for some, it is required, and does meaningfully change observed semantics.

steveklabnik 2mo ago

(2025)

torginus 2mo ago

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 <= 1 then 1 else n * factorial (n - 1) is not tail recursive, and will overflow if the compiler fails to optimize.

adrian_b 2mo ago
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.
- fluoridation 2mo ago
  I can't see why the calling convention could matter. Can you give an example?
  - layer8 2mo ago
    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.

amavect 2mo ago

I recently played around with what I call "manual tail-call optimization": transform a tail call to a goto to the beginning of the function. Check it out: https://godbolt.org/z/3fY1v1oeW https://godbolt.org/z/3fY1v1oeW int factorial_loop_iterative(int n, int a){ while(n > 0){ a = a * n; n = n - 1; } return a; } int factorial_loop_recursive(int n, int a){ if(n > 0){ return factorial_loop_recursive(n - 1, a * n); }else{ return a; } } int factorial_loop_manual(int n, int a){ tailcall: if(n > 0){ a = a * n; n = n - 1; goto tailcall; }else{ return a; } } int (*factorial_loop)(int n, int a) = factorial_loop_manual; int factorial(int n){ return factorial_loop(n, 0); } I recommend against, of course! Incorrectly sequencing the manual version results in bugs (swap the assignment for n and a), which the recursive version doesn't need to care about.

zamadatix 2mo ago
Seems like a complex way to write a normal looped version. Apart from factorial_loop_manual() being one in design, its name even says as much.

throwaway81523 2mo ago

GCC has had TCO since the 1980s I'm pretty sure. Since then it's been extended to work in more contexts.

cryptonector 2mo ago

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.

reindeer2 2mo ago

[flagged]

mark-probst 2mo ago

> 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 how many arguments it passed, which means that only the caller can clean up the stack, unless the stack frame size is also communicated, which "normal" C calling conventions don't do. But when the callee does a proper tail call, the stack frame that returns to the callee is not the stack frame that the callee originally sent. This is explained in more detail in my thesis starting on page 16: https://hostr.flingit.run/s/proper-tail-calls.pdf https://hostr.flingit.run/s/proper-tail-calls.pdf

deleted 2mo ago
[deleted]
anitil 2mo ago
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
- kazinator 2mo ago
  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 <= M, then you can just place the new N parameters in the same space on the stack where you received your M parameters, and jump to that function. That function will return to your original caller, which will remove the M parameters, not caring that some of them are not the originals that it passed. 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 tail-callee arguments into the variadic space and proceed accordingly. For 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.

brooke2k 2mo ago

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

cryptonector 2mo ago
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.