5 ms·
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 "go
by 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 agoI can't see why the calling convention could matter. Can you give an example?
- layer8 2mo agoWhen 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 2mo agoBut 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.
- uecker 2mo agoIt is usually assumed that it does not control the callee and the jump has to preserve the calling convention for a call.
- fluoridation 2mo agoIf 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.
- layer8 2mo agoIt's possible for calling conventions where the callee is responsible for stack cleanup before return.
- uecker 2mo agoHave your mind blown: https://godbolt.org/z/xnn3PPxvW https://godbolt.org/z/xnn3PPxvW
- fluoridation 2mo agoExtremely specific example is uncompelling.
- uecker 2mo agoIt is a simple counterexample to your incorrect statement.
- fluoridation 2mo agoIt's still impossible in the general case, where not all arguments are passable by registers.
- uecker 2mo ago