Rendered at 22:44:26 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
drdexebtjl 8 hours 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.
kevincox 7 hours 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.
derefr 4 hours ago [-]
I think the problem with considering it a "pure optimization" is that code that is written to use tail-calls, if not optimized, is almost always unbounded recursive code. And modern OSes tend to have relatively small stack-size limits (relative to the kinds of huge data structures modern software slings around, incl. not only individually-"wide" structures, but also "deep" trees and graphs.)
Which means that "whether this naively-recursive code is actually recursive in practice" is a semantic difference, in that there is an error/failure-mode (stack overflow) that can be statically guaranteed to not happen (at least for a given compilation target) if TCO gets applied; but which cannot be guaranteed to not happen without TCO applied.
---
Tangent: you could of course try to write code defensively, to guarantee that a stack overflow won't occur, by bounding recursion separately (e.g. via a passed-and-decremented recursion-limit parameter), so that in the non-TCO case, you get a software exception thrown (which you'd hopefully then handle... somehow), rather than triggering a stack overflow.
And for many more-traditional recursive algorithms, this works!
But doing so for the types of algorithms that are "canonically" expressed in terms of tail-calls (even in a non-tail-call-idiomatic language like C), almost always requires poking holes in the C abstract machine to see through to the micro-architectural details underneath.
You can't just use something like a recursion-limit parameter as a general solution for these algorithms, as TCO is used in things like continuation-passing or threaded-code VM implementations — i.e. things that look less like visiting trees and more like visiting unboundedly-non-terminal infinite-state-machine states ["infinite" because the states are dynamic function pointers to JITted code, and more of them can appear at runtime.]
You need to not track the "number of invocations deep" you are into the algorithm, but rather, how big the stack actually is at the moment. Which means you need to actually do math on addresses of the stack base pointer vs either the stack pointer, or the address of a local stack-allocated variable. There's no version of that that doesn't require writing non-portable inline assembly.
steveklabnik 7 hours 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.
fsckboy 3 minutes ago [-]
>It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program
it is guaranteed in Scheme, and it affects the semantics of programs in a completely positive way.
Much of computer science is "pure" and "abstract" like mathematics. However, programmers are still taught to use loops to calculate factorial rather than recursion in order to avoid stack overflow. In Scheme you can use recursion without flinching. That is a semantic difference.
mort96 5 hours ago [-]
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)'.
leni536 2 hours ago [-]
Precisely. ISO C and C++ have a notion of various implementation limits, one of which is nested function calls due to exhausting the stack. TCO could be about a carveout on this limit.
Having said that the standards give way too much leeway for the limits, so a conforming implementation might have arbitrary limits for loops as well (at least in C++, I'm not that familiar with the C standard's wording).
layer8 4 hours ago [-]
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.
drdexebtjl 3 hours ago [-]
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 program were changed.
In languages with such tail call guarantees, tail recursion _is_ a loop. It semantically encodes constant space complexity.
mort96 4 hours ago [-]
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.
cmovq 5 hours ago [-]
Note that compilers are more than happy to delete 'while (true)' if the loop doesn't have side-effects.
mpyne 52 minutes ago [-]
I think this is no longer true. C++26 implemented a change to make trivial loops like these defined behavior (and therefore will loop endlessly as you'd expect). And this example was always defined behavior in C.
Both languages continue to have examples of slightly more complicated loops that can be assumed to terminate in the absence of side effects, but `while(true)` isn't one of those any longer.
mort96 4 hours ago [-]
Of course. I wasn't talking about empty loops.
But also, I wouldn't rely on a compiler to remove empty 'while (true)' loops.
Someone 3 hours ago [-]
> I can only think of a few other optimizations that affect memory usage
Java has string interning. I think that’s a hack that shouldn’t exist in an ideal world. Reason is that, as a library writer, you cannot make the call whether to intern strings (requiring more instructions for string access, thus slowing down code, but decreasing memory usage, and, because of that, possibly speeding up the code again) or not.
vanderZwan 21 minutes ago [-]
> requiring more instructions for string access
Wait, why would interned immutable strings require more instructions when doing regular string access? You can still point to the start of a zero-terminated C-string, it just requires storing extra metadata like lenght and a string hash somewhere. Which can be done at the negative indices of said pointer.
Or do you refer to the extra rolling-hash pass needed when concatenating two strings to verify if it would result in an already-interned one? Because yes, that's one extra rolling hast pass over the appended string the first time a string is constructed, but after that doing so again likely saves memory and construction time, because any concatenation that would result in an already interned string would avoid actual memory allocation and copying of the string's characters.
Plus string comparisons become cheap O(1) pointer comparisons this way, which is really nice in many use-cases.
And that's not even considering more advanced tricks like interning short strings in the 64-bit word of the pointer to the string itself, relying on the fact that modern memory allocators never return an address with the lsb set, so it can be used to flag it as such[0].
If my program crashes without it, that's a semantic difference no?
qsera 37 minutes ago [-]
You program did not ask for the crash via the language constructs..semantics is defined by the language, rest is the implementation details. That is how it makes sense to me. I don't understand other people in this thread who think otherwise.
layer8 4 hours ago [-]
Not in the sense of formal programming-language semantics, usually.
jmalicki 7 hours ago [-]
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.
pjmlp 4 hours ago [-]
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.
tialaramex 6 hours ago [-]
std::vector<bool> is just a terrible specialisation, it isn't an optimisation.
If std::vector<bool> was an optimisation we couldn't write C++ which blows up because it's actually a bitset, it would be semantically transparent - but that's easy to do even by accident because it's not transparent at all.
In fact the existing std::vector<bool> should just be named std::growable_bitset or something and then std::vector<bool> would make what you actually wanted like Rust's Vec<bool> does.
drdexebtjl 6 hours ago [-]
The main difference is not that it affects memory usage, imo.
It’s that it makes memory usage bounded when it’s on, and unbounded when it’s off.
In languages that have guaranteed tail call eliminations, the semantics of tail recursion is the same as that of a loop. So you can express the same iterative algorithm without using iterative code.
throwaway81523 56 minutes ago [-]
You can rely on it now in gcc and clang, in the sense that they support a [[musttail]] attribute that tells the compiler to report an error if a call can't be TCO'd. The language doesn't guarantee TCO but can implement it at its option. If your program uses the attribute and still compiles, it means it has compiled with proper TCO.
LukeShu 8 hours ago [-]
GCC has `[[gnu::musttail]] return`.
But yes, framing TCO as an optimization is unfortunate.
vinkelhake 6 hours ago [-]
And there's also [[clang::musttail]] and [[msvc::musttail]].
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.
pjmlp 4 hours ago [-]
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.
Some languages have TCO annotation, it throws compiler error if TCO fails. You want stronger type system, not smart compiler guarantees or promises!
mort96 5 hours ago [-]
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.
torginus 5 hours 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.
sparkie 15 minutes ago [-]
> What practical patterns are enabled by TCO in C?
Continuation Passing Style - an important construction for interpreters, but which is also useful for compilers as it's a nice way to do control flow analysis, data flow analysis and more.
The missing feature is closures - functions which capture values from their static environment, which are basically needed to make CPS useful. GCC has nested functions, but they cannot capture without making the stack executable, which is terrible. There's a proposal[1] to get closures into C, but at present you need to simulate the capturing yourself, which is cumbersome, but can be done efficiently.
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 4 hours ago [-]
I can't see why the calling convention could matter. Can you give an example?
layer8 4 hours 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.
fluoridation 4 hours ago [-]
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.
toast0 3 hours ago [-]
> But the compiler controls both the caller and callee.
Why? In functional languages, it's common for an exported function from one compilation context to tail call into an exported function from another.
fluoridation 3 hours ago [-]
Functional languages may be designed to support TCO from the ground up, up to supporting it across module boundaries. C is not like that, and calling into an external module necessarily grows the stack.
toast0 3 hours ago [-]
> C is not like that, and calling into an external module necessarily grows the stack.
This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)
fluoridation 2 hours ago [-]
Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?
toast0 2 hours ago [-]
With the right calling convention, tail calls could conform to the convention.
A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work.
In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.
fluoridation 1 hours ago [-]
>In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee.
You can still do that with a caller-cleanup convention. Suppose you have a convention like
* Set up stack
* Call
* Clean up stack
and you have functions f(), g(), and h(), where g() and h() use this convention and f() calls into g(), and g() into h(). The sequence of instructions from f() to h() without TCO would be
* f: Set up stack for g()
* f: Call g()
* g: Do work
* g: Set up stack for h()
* g: Call h()
* h: Do work
* h: Return
* g: Clean up stack
* g: Return
* f: Clean up stack
And with TCO:
* f: Set up stack for g()
* f: Call g()
* g: Do work
* g: Move things around on the stack so that h()'s arguments are written where g()'s were. This may require a temporary stack allocation that's released before the next step.
* g: Jump to h()
(At this point it looks as if f() called h() directly.)
* h: Do work
* h: Return
* f: Clean up stack
This is always possible as long as h()'s caller-managed stack allocation is no bigger than g()'s.
teo_zero 20 minutes ago [-]
h() can't have more arguments than g(): that's an important limitation.
uecker 3 hours ago [-]
It is usually assumed that it does not control the callee and the jump has to preserve the calling convention for a call.
fluoridation 3 hours ago [-]
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.
toast0 3 hours ago [-]
> 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 described, TCO makes a lot of sense for interpreters and state machines.
10000truths 2 hours ago [-]
> TCO makes a lot of sense for interpreters and state machines.
The reason that performant implementations prefer TCO is because the only reliable knob that clang and gcc provide to control which locals are spilled to stack vs. kept in registers is via calling convention constraints. One could accomplish the same performance without TCO'd recursion if there existed an annotation for local variables designating them as spill/no-spill. But that doesn't exist in clang or gcc - the "register" keyword in the C standard was supposed to be for exactly that, but it's ignored in both compilers.
noelwelsh 4 hours ago [-]
> What practical patterns are enabled by TCO in C?
It is simple to convert factorial to tail recursive form. In lua, which has tco:
local factorial do
local function impl(n, acc)
if n == 1 then
return acc
else
return impl(n - 1, acc * n)
end
end
factorial = function(n)
if n < 0 then
error("factorial input is negative")
elseif n <= 1 then
return 1
else
return impl(n - 1, n)
end
end
end
You could replace impl with an imperative loop:
local acc = 1
repeat
acc = acc * n
n = n - 1
until n == 1
return acc
Personally, I find this ugly compared to the tail recursive solution. The loop version only seems more natural if you primarily think in loops. Tail recursion is strictly more powerful than looping since every imperative loop can trivially be converted to a tail recursive function, but the reverse is not true.
kenjin4096 10 hours 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 9 hours 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.
A formal technical specification (TS) extension is already being drafted: 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]
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 9 hours ago [-]
Plus the fact that an implementation that recognizes the new syntax and produces an error whenever it encounters it will be conforming.
On such an implementation, the feature is available but useless.
kenjin4096 7 hours ago [-]
Woops, I meant to write tail call optimization not tail calls. Shouldn't have used the term interchangeably. Yeah I'm aware that C doesn't have proper tail calls. Thanks for the correction though.
amavect 2 hours 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
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.
throwaway81523 60 minutes ago [-]
GCC has had TCO since the 1980s I'm pretty sure. Since then it's been extended to work in more contexts.
Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.
tialaramex 10 hours 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.
chriswarbo 10 hours 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 8 hours 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 6 hours 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 4 hours 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.
StilesCrisis 10 hours ago [-]
Sounds like clang::must_tail?
tialaramex 9 hours 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.
StilesCrisis 8 hours ago [-]
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.
fweimer 5 hours ago [-]
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.
StilesCrisis 2 hours ago [-]
Right--if the tailing isn't possible, for any of these varied reasons, it will become a compile error.
tialaramex 4 hours ago [-]
I have to say that at least knowing if I didn't get what I wanted is most of the value for me.
im3w1l 8 hours 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.
steveklabnik 7 hours 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 6 hours 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.
steveklabnik 5 hours ago [-]
I was talking about regular old today's Rust, not the specifics about become.
tialaramex 7 hours 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.
jmalicki 7 hours ago [-]
Does 1 really happen? I would never trust a compiler where 1 was a possibility. If it can work it should.
guenthert 10 hours 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
pfdietz 10 hours 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 10 hours 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.
ux266478 6 hours 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.
pfdietz 9 hours 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.
mort96 5 hours ago [-]
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.
throwaway_95283 4 hours ago [-]
in theory, no, in practice, yes.
pjmlp 9 hours 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 9 hours 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 10 hours 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 7 hours ago [-]
Technically TCO is still in the spec, TC39 deadlocked over modifying it. TC39 really does not fill me with confidence in general.
webstrand 4 hours 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 4 hours 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.
nyeah 10 hours 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.
"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,
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 7 hours 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.
pjmlp 4 hours ago [-]
They never will, as mentioned they have decided not to support what became optional in C11.
If C23 ever comes to land on MSVC, which I have my doubts given the radio silence on C support, I assume they might add the VLAs part that made it again back into C23.
uecker 3 hours ago [-]
If you care about C, use gcc.
pjmlp 3 hours ago [-]
As proven by industry adoption of clang, that isn't an option in many platforms.
Additionally clang is driving C extensions for safety that should have long been part of the language.
uecker 42 minutes ago [-]
IMHO gcc has better warnings and support for safety. Industry mostly wants a BSD-licensed toolchain. I could not care less.
10 hours ago [-]
steveklabnik 7 hours ago [-]
(2025)
messe 10 hours 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).
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.
derdi 9 hours 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 6 hours 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.
I think the framing of TCO as an optimization has been very unfortunate.
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.
Which means that "whether this naively-recursive code is actually recursive in practice" is a semantic difference, in that there is an error/failure-mode (stack overflow) that can be statically guaranteed to not happen (at least for a given compilation target) if TCO gets applied; but which cannot be guaranteed to not happen without TCO applied.
---
Tangent: you could of course try to write code defensively, to guarantee that a stack overflow won't occur, by bounding recursion separately (e.g. via a passed-and-decremented recursion-limit parameter), so that in the non-TCO case, you get a software exception thrown (which you'd hopefully then handle... somehow), rather than triggering a stack overflow.
And for many more-traditional recursive algorithms, this works!
But doing so for the types of algorithms that are "canonically" expressed in terms of tail-calls (even in a non-tail-call-idiomatic language like C), almost always requires poking holes in the C abstract machine to see through to the micro-architectural details underneath.
You can't just use something like a recursion-limit parameter as a general solution for these algorithms, as TCO is used in things like continuation-passing or threaded-code VM implementations — i.e. things that look less like visiting trees and more like visiting unboundedly-non-terminal infinite-state-machine states ["infinite" because the states are dynamic function pointers to JITted code, and more of them can appear at runtime.]
You need to not track the "number of invocations deep" you are into the algorithm, but rather, how big the stack actually is at the moment. Which means you need to actually do math on addresses of the stack base pointer vs either the stack pointer, or the address of a local stack-allocated variable. There's no version of that that doesn't require writing non-portable inline assembly.
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.
it is guaranteed in Scheme, and it affects the semantics of programs in a completely positive way.
Much of computer science is "pure" and "abstract" like mathematics. However, programmers are still taught to use loops to calculate factorial rather than recursion in order to avoid stack overflow. In Scheme you can use recursion without flinching. That is a semantic difference.
Having said that the standards give way too much leeway for the limits, so a conforming implementation might have arbitrary limits for loops as well (at least in C++, I'm not that familiar with the C standard's wording).
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 program were changed.
In languages with such tail call guarantees, tail recursion _is_ a loop. It semantically encodes constant space complexity.
Both languages continue to have examples of slightly more complicated loops that can be assumed to terminate in the absence of side effects, but `while(true)` isn't one of those any longer.
But also, I wouldn't rely on a compiler to remove empty 'while (true)' loops.
Java has string interning. I think that’s a hack that shouldn’t exist in an ideal world. Reason is that, as a library writer, you cannot make the call whether to intern strings (requiring more instructions for string access, thus slowing down code, but decreasing memory usage, and, because of that, possibly speeding up the code again) or not.
Wait, why would interned immutable strings require more instructions when doing regular string access? You can still point to the start of a zero-terminated C-string, it just requires storing extra metadata like lenght and a string hash somewhere. Which can be done at the negative indices of said pointer.
Or do you refer to the extra rolling-hash pass needed when concatenating two strings to verify if it would result in an already-interned one? Because yes, that's one extra rolling hast pass over the appended string the first time a string is constructed, but after that doing so again likely saves memory and construction time, because any concatenation that would result in an already interned string would avoid actual memory allocation and copying of the string's characters.
Plus string comparisons become cheap O(1) pointer comparisons this way, which is really nice in many use-cases.
And that's not even considering more advanced tricks like interning short strings in the 64-bit word of the pointer to the string itself, relying on the fact that modern memory allocators never return an address with the lsb set, so it can be used to flag it as such[0].
[0] https://squoze.org/
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.
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.
If std::vector<bool> was an optimisation we couldn't write C++ which blows up because it's actually a bitset, it would be semantically transparent - but that's easy to do even by accident because it's not transparent at all.
In fact the existing std::vector<bool> should just be named std::growable_bitset or something and then std::vector<bool> would make what you actually wanted like Rust's Vec<bool> does.
It’s that it makes memory usage bounded when it’s on, and unbounded when it’s off.
In languages that have guaranteed tail call eliminations, the semantics of tail recursion is the same as that of a loop. So you can express the same iterative algorithm without using iterative code.
But yes, framing TCO as an optimization is unfortunate.
As well as an effort to get it standardized: https://isocpp.org/files/papers/D3939R0.html (in C++).
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.
> 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...
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:
is not tail recursive, and will overflow if the compiler fails to optimize.Continuation Passing Style - an important construction for interpreters, but which is also useful for compilers as it's a nice way to do control flow analysis, data flow analysis and more.
The missing feature is closures - functions which capture values from their static environment, which are basically needed to make CPS useful. GCC has nested functions, but they cannot capture without making the stack executable, which is terrible. There's a proposal[1] to get closures into C, but at present you need to simulate the capturing yourself, which is cumbersome, but can be done efficiently.
[1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...
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.
Why? In functional languages, it's common for an exported function from one compilation context to tail call into an exported function from another.
This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)
A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work.
In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.
You can still do that with a caller-cleanup convention. Suppose you have a convention like
* Set up stack
* Call
* Clean up stack
and you have functions f(), g(), and h(), where g() and h() use this convention and f() calls into g(), and g() into h(). The sequence of instructions from f() to h() without TCO would be
* f: Set up stack for g()
* f: Call g()
* g: Do work
* g: Set up stack for h()
* g: Call h()
* h: Do work
* h: Return
* g: Clean up stack
* g: Return
* f: Clean up stack
And with TCO:
* f: Set up stack for g()
* f: Call g()
* g: Do work
* g: Move things around on the stack so that h()'s arguments are written where g()'s were. This may require a temporary stack allocation that's released before the next step.
* g: Jump to h()
(At this point it looks as if f() called h() directly.)
* h: Do work
* h: Return
* f: Clean up stack
This is always possible as long as h()'s caller-managed stack allocation is no bigger than g()'s.
Which is more natural? (please just assume my wonky pseudo code syntax makes sense)
IMHO, both of these need to be taught, neither is particularly more natural. In addition, as others have described, TCO makes a lot of sense for interpreters and state machines.The reason that performant implementations prefer TCO is because the only reliable knob that clang and gcc provide to control which locals are spilled to stack vs. kept in registers is via calling convention constraints. One could accomplish the same performance without TCO'd recursion if there existed an annotation for local variables designating them as spill/no-spill. But that doesn't exist in clang or gcc - the "register" keyword in the C standard was supposed to be for exactly that, but it's ignored in both compilers.
It's important in interpreters. Here's an example: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
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.
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
Section 3.5 of R7RS.
https://standards.scheme.org/official/r7rs.pdf
1. 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
On such an implementation, the feature is available but useless.
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...)
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.
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.
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.
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!
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.
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.
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.
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.
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.
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.
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.
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.
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.
This has always been an issue regarding TCO support across programming languages.
JS _does_ still have TCO (called Proper Tail Calls), Safari's JavaScriptCore implements it, and is technically the only conforming interpreter.
I can’t rely on TCO if chromium doesn’t have it.
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.
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.
It famously doesn’t support a few features of C99.
They don’t really seem to care much about regular C support (non-C++).
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-...
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.
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.
If C23 ever comes to land on MSVC, which I have my doubts given the radio silence on C support, I assume they might add the VLAs part that made it again back into C23.
Additionally clang is driving C extensions for safety that should have long been part of the language.
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
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.