4 ms·

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 fu

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.

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 ago
  I can't see why the calling convention could matter. Can you give an example?
  - layer8 2mo 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 2mo 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.
      - uecker 2mo 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 2mo 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.
        layer8 2mo ago
        It's possible for calling conventions where the callee is responsible for stack cleanup before return.
        uecker 2mo ago
        Have your mind blown: https://godbolt.org/z/xnn3PPxvW https://godbolt.org/z/xnn3PPxvW
        fluoridation 2mo ago
        Extremely specific example is uncompelling.
        uecker 2mo ago
        It is a simple counterexample to your incorrect statement.
norir 2mo ago
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.
noelwelsh 2mo ago
> 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-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
- torginus 2mo ago
  I get that, but a lot of C interpreters use switch, for example Lua: https://www.lua.org/source/5.5/lvm.c.html#vmdispatch https://www.lua.org/source/5.5/lvm.c.html#vmdispatch
  - noelwelsh 2mo ago
    Switch is fine if you don't care about performance. If you do care about performance then direct threading is faster. Direct threading uses tail calls. More here: https://noelwelsh.com/posts/understanding-vm-dispatch/ https://noelwelsh.com/posts/understanding-vm-dispatch/
toast0 2mo 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 2mo 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.
  - sparkie 2mo ago
    That's not entirely true, but it's a valid reason to prefer using musttail. `register` is a hint if you don't specify which register you want to use - however, if you specify the register it will clobber it. noinline void bar() { register void *parent __asm__("r10"); ... } You can also use GCCs extended asm syntax to clobber a register for specific portions of code - such as the start of a function where you expect a register to have been given a value from the caller just before the call. Use `volatile` to prevent the compiler from making certain assumptions that might remove or reorder the instruction - as long as it is at the top it should execute immediately after the function prelude and before any of the function body. noinline void bar() { void *volatile parent; // set parent = %r10 before anything else. asm volatile ("mov{q}\t{%%r10, %0|%0, r10}" : "=r"(parent) : : "r10"); ... } Note that this will probably be less efficient than the former example, but maybe useful where you want to limit the scope in which `r10` is clobbered. In both cases you would set the register immediately before making the call, again using `volatile`. Since `r10` is not used by a typical call in SYSV - it's the static chain pointer in the SYSV convention, but otherwise usable as a GP register, a call will not overwrite it. void foo() { struct foo_frame { int x; } locals = { .x = 999 }; // Set `r10` to our function's local frame asm volatile("mov{q}\t{%0, %%r10|r10, %0}" : : "r"(&locals) : "r10") bar(); } That's pretty ugly but we can write a few macros to implement it more tersely - we can use this to have efficient closures in C without requiring an executable stack. (There's also `__builtin_call_with_static_chain`, but I've found it more troublesome to use than the manual way). Demo: https://godbolt.org/z/cM9d8e1r5 https://godbolt.org/z/cM9d8e1r5 For other registers which are part of the regular calling convention, we might be able to clobber them if they wouldn't normally be used for the call. Eg, if our function takes regular 2 arguments, they would be in `rdi` and `rsi` - so we could use `rdx`, `rcx`, `r8`, `r9` like the above, but if our function took 6 or more regular arguments we wouldn't be able to use any of these in this way. If we wanted a custom calling convention we could just make all functions have zero-arguments and perform all of the setting and capturing ourself - which gives us more control than using [[musttail]] - though less portable, and may prevent optimizations the compiler could otherwise make.
sparkie 2mo 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. [1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functions%20with%20Data%20-%20Closures%20in%20C.html#design-capture.functions https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...

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 ago
I can't see why the calling convention could matter. Can you give an example?
- layer8 2mo 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 2mo 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.
    - uecker 2mo 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 2mo 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.
        layer8 2mo ago
        It's possible for calling conventions where the callee is responsible for stack cleanup before return.
        uecker 2mo ago
        Have your mind blown: https://godbolt.org/z/xnn3PPxvW https://godbolt.org/z/xnn3PPxvW
        fluoridation 2mo ago
        Extremely specific example is uncompelling.
        uecker 2mo ago
        It is a simple counterexample to your incorrect statement.

norir 2mo ago

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.

noelwelsh 2mo ago

> 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-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

torginus 2mo ago
I get that, but a lot of C interpreters use switch, for example Lua: https://www.lua.org/source/5.5/lvm.c.html#vmdispatch https://www.lua.org/source/5.5/lvm.c.html#vmdispatch
- noelwelsh 2mo ago
  Switch is fine if you don't care about performance. If you do care about performance then direct threading is faster. Direct threading uses tail calls. More here: https://noelwelsh.com/posts/understanding-vm-dispatch/ https://noelwelsh.com/posts/understanding-vm-dispatch/

toast0 2mo 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 2mo 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.
- sparkie 2mo ago
  That's not entirely true, but it's a valid reason to prefer using musttail. `register` is a hint if you don't specify which register you want to use - however, if you specify the register it will clobber it. noinline void bar() { register void *parent __asm__("r10"); ... } You can also use GCCs extended asm syntax to clobber a register for specific portions of code - such as the start of a function where you expect a register to have been given a value from the caller just before the call. Use `volatile` to prevent the compiler from making certain assumptions that might remove or reorder the instruction - as long as it is at the top it should execute immediately after the function prelude and before any of the function body. noinline void bar() { void *volatile parent; // set parent = %r10 before anything else. asm volatile ("mov{q}\t{%%r10, %0|%0, r10}" : "=r"(parent) : : "r10"); ... } Note that this will probably be less efficient than the former example, but maybe useful where you want to limit the scope in which `r10` is clobbered. In both cases you would set the register immediately before making the call, again using `volatile`. Since `r10` is not used by a typical call in SYSV - it's the static chain pointer in the SYSV convention, but otherwise usable as a GP register, a call will not overwrite it. void foo() { struct foo_frame { int x; } locals = { .x = 999 }; // Set `r10` to our function's local frame asm volatile("mov{q}\t{%0, %%r10|r10, %0}" : : "r"(&locals) : "r10") bar(); } That's pretty ugly but we can write a few macros to implement it more tersely - we can use this to have efficient closures in C without requiring an executable stack. (There's also `__builtin_call_with_static_chain`, but I've found it more troublesome to use than the manual way). Demo: https://godbolt.org/z/cM9d8e1r5 https://godbolt.org/z/cM9d8e1r5 For other registers which are part of the regular calling convention, we might be able to clobber them if they wouldn't normally be used for the call. Eg, if our function takes regular 2 arguments, they would be in `rdi` and `rsi` - so we could use `rdx`, `rcx`, `r8`, `r9` like the above, but if our function took 6 or more regular arguments we wouldn't be able to use any of these in this way. If we wanted a custom calling convention we could just make all functions have zero-arguments and perform all of the setting and capturing ourself - which gives us more control than using [[musttail]] - though less portable, and may prevent optimizations the compiler could otherwise make.

sparkie 2mo 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. [1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functions%20with%20Data%20-%20Closures%20in%20C.html#design-capture.functions https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...