alt Hacker NewsWhat 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)
Replies
> 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.
[1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...
> 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.
> What practical patterns are enabled by TCO in C?
It's important in interpreters. Here's an example: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
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
local acc = 1
repeat
acc = acc * n
n = n - 1
until n == 1
return acc
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.