"Optimization" is a misnomer with TCO. Optimization implies that only execution speed is affected without the optimization. Without TCO, potentially infinite mutually tail-recursive algorithms (or code transformed into continuation-passing style) can't be implemented without emulating tail recursion using a heap-allocated stack/linked list of states or manually transforming the mutually recursive functions into a trampoline variant of continuation passing style.
function factorial(n, accumulator=1) {
if (n <= 1) {
if (n < 0) throw "Arument must not be negative";
return accumulator;
}
return factorial(n-1, n * accumulator);
}
TCO doesn't just affect the speed of this factorial implementation, it greatly affects the largest value that can be computed.
It's not to tricky to manually convert tail recursion into a loop, but for mutually recursive functions, you'd probably be best off manually transforming your mutually recursive functions into a trampoline variant of continuation passing, where each function returns a tuple of function and arguments to a trampoline loop that just repeatedly invokes the returned function on the returned arguments.
function trampoline(f, ... args) {
while (true) {
f, args = f(*args);
if (args == null) { return f; }
}
}
function fatorial_impl(n, accumulator)
if (n <= 1) {
if (n < 0) throw "Arument must not be negative";
return [accumulator, null];
}
return [factorial_impl, [n-1, n * accumulator]];
}
function factorial(n) {
return trampoline(factorial_impl, n, 1);
}
It's all very mechanical, and you'd prefer that the compiler does it. The main argument against TCO is that it's easy for an unobservant programmer to accidentally make a change that prevents TCO. Ideally, the language would have a construct allowing a programmer to cause a given return site to be a syntactic error if it's not a TCO-able tail call.
> "optimization" does not imply that only execution speed is impacted.
No but "optimisation" implies the normally observable semantics are not altered, which is not the case at all with TCE (aka "guaranteed TCO"). Removing TCE from a language makes it a completely different language e.g. Erlang would be severely restricted as it has no imperative loops.
Fair enough, but in most people's minds, it suggests that the correctness of an implementation doesn't depend on which optimizations are applied, and in this sense, TCO isn't an optimization.
TCO isn't merely an optimisation in the same sense of local/global value numbering/common sub-expression elimination , dead-code elimination, loop-invariant expression hoisting, etc.
It's not to tricky to manually convert tail recursion into a loop, but for mutually recursive functions, you'd probably be best off manually transforming your mutually recursive functions into a trampoline variant of continuation passing, where each function returns a tuple of function and arguments to a trampoline loop that just repeatedly invokes the returned function on the returned arguments.
It's all very mechanical, and you'd prefer that the compiler does it. The main argument against TCO is that it's easy for an unobservant programmer to accidentally make a change that prevents TCO. Ideally, the language would have a construct allowing a programmer to cause a given return site to be a syntactic error if it's not a TCO-able tail call.