> some targets fundamentally do not support tail call optimization
Can't any tail call be rewritten as a loop? Couldn't a WASM compiler without the tail call extension implement it this way?
Can't any tail call be rewritten as a loop? Couldn't a WASM compiler without the tail call extension implement it this way?
Doing it with a trampoline is probably slower than if C really had tail calls. On the other hand, adding "real" tail calls to C would probably require changing the ABI (e.g. to "tailcc" or "fastcc -tailcallopt"), and I think there's some reason to think this would probably impose a penalty everywhere (https://llvm.org/docs/CodeGenerator.html#tail-call-optimizat...).
But [[musttail]] does exactly this while respecting existing calling conventions: https://clang.llvm.org/docs/AttributeReference.html#musttail
It would be nice if the more relaxed rules of the LLVM musttail marker with tailcc could be exposed in clang (and gcc). I think that's basically what "return goto" would do.
function logAndCall(statement, func) { console.log(statement); return func(); }
Tail call optimization is actually possible here since we call func in "tail position". It might be unlikely to blow up the stack, but it can definitely happen if you do a lot of continuation passing.
Perhaps more commonly for C++/Rust, tail call optimization would be enormously valuable to have behind the scenes for destructors. It's actually very difficult to implement a linked list in safe Rust that doesn't explode the stack for large lists since no TCO is done for destroying subobjects. You can still avoid stack overflow, but you have to do things like manually enumerating the list.
And that's not a special case for passed-in function pointers; that's what a trampoline always does. Trampolines expect static-invoked tail-calls to be codegen'ed into function-pointer references too.
It's completely different than the story with tail recursion which can be essentially reduced to syntactic sugar over a normal loop (just change the parameters to be mutable variables).
No. In general tail calls cannot be rewritten into loops.
Consider a state machine where each state is a function, and you transition into a different state by tail-calling another function.
State machines can have arbitrarily complicated graphs, that would be hard to put into a simple loop.
(However, you can do something like a 'trampoline' to remove the mutual recursion.)