4 ms·

A C standard proposal exists for tail call [0], in the form of "return goto (expression);". What I like about it, over standardizing [[musttail]], is that life

by fuhsnn 2y ago

A C standard proposal exists for tail call [0], in the form of "return goto (expression);". What I like about it, over standardizing [[musttail]], is that lifetimes of local objects are guaranteed to end. This makes it possible to implement without extensive escape analysis. [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5-tail-call-elimination https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...

nxobject 2y ago
As an aside, I’m excited - but also with lots of trepidation - about the new energy in adding new functionality to C. Excited because there are changes and additions that are crying to be made, even clarifying ideas… trepidation because C++’s gung ho update cadence has somehow ended up in wart patched over wart. Especially when feature reacts with feature in an unfelicitous way far earlier than anticipated. I hope the standards process finds a way to be very conservative, really thoroughly test features in large and diverse codebases, rather than just relying on rationales alone, when choosing to include feature.
- pjmlp 2y ago
  What new energy? We have had C89, C99, C11, C17, C23 And yet, no fix in sight for proper strings, arrays, or at very least bounds checked slices, like Dennis Ritchie originally proposed to ANSI/ISO.
haberman 2y ago
Thanks for the pointer, I'll have to check this out. Can you elaborate on how "return goto" is easier to implement? [[musttail]] also ends the lifetime of local objects AFAICS. One thing I'll mention from a quick scan: > [The] function called in tail position must have identical type to the callee. This ensures both that the return value does not require any conversion, and also that argument passing space is available and calling convention (if relevant) is maintained. One complaint I've seen repeatedly about [[musttail]] (which I implemented in Clang) is that this constraint is unnecessarily strict, since some architectures will allow tail calls even for functions that do not perfectly match: https://github.com/llvm/llvm-project/issues/54964 https://github.com/llvm/llvm-project/issues/54964 "But then the code would be nonportable." True, but tail call optimization is inherently nonportable, since some targets fundamentally do not support tail call optimization (eg. WASM without the tail call extension).
- tines 2y ago
  > 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?
  - metadat 2y ago
    Only with the aforementioned escape analysis. The function call stack frames serve a critical purpose in most nontrivial logic.
  - tonyg 2y ago
    > Can't any tail call be rewritten as a loop? No. In general tail calls cannot be rewritten into loops.
    - cobbal 2y ago
      More specifically, tail recursion is usually easy to turn into a loop. Tail calls can be difficult to turn into loops when they call a different function, or worse a function passed in as a variable.
      - eru 2y ago
        To give the standard example: 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.)
  - slaymaker1907 2y ago
    It can't be rewritten as loop due to function pointers. Using JS notation to avoid noise: 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.

by fuhsnn 2y ago

nxobject 2y ago

As an aside, I’m excited - but also with lots of trepidation - about the new energy in adding new functionality to C. Excited because there are changes and additions that are crying to be made, even clarifying ideas… trepidation because C++’s gung ho update cadence has somehow ended up in wart patched over wart. Especially when feature reacts with feature in an unfelicitous way far earlier than anticipated. I hope the standards process finds a way to be very conservative, really thoroughly test features in large and diverse codebases, rather than just relying on rationales alone, when choosing to include feature.

pjmlp 2y ago
What new energy? We have had C89, C99, C11, C17, C23 And yet, no fix in sight for proper strings, arrays, or at very least bounds checked slices, like Dennis Ritchie originally proposed to ANSI/ISO.

haberman 2y ago

Thanks for the pointer, I'll have to check this out. Can you elaborate on how "return goto" is easier to implement? [[musttail]] also ends the lifetime of local objects AFAICS. One thing I'll mention from a quick scan: > [The] function called in tail position must have identical type to the callee. This ensures both that the return value does not require any conversion, and also that argument passing space is available and calling convention (if relevant) is maintained. One complaint I've seen repeatedly about [[musttail]] (which I implemented in Clang) is that this constraint is unnecessarily strict, since some architectures will allow tail calls even for functions that do not perfectly match: https://github.com/llvm/llvm-project/issues/54964 https://github.com/llvm/llvm-project/issues/54964 "But then the code would be nonportable." True, but tail call optimization is inherently nonportable, since some targets fundamentally do not support tail call optimization (eg. WASM without the tail call extension).

tines 2y ago
> 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?
- metadat 2y ago
  Only with the aforementioned escape analysis. The function call stack frames serve a critical purpose in most nontrivial logic.
- tonyg 2y ago
  > Can't any tail call be rewritten as a loop? No. In general tail calls cannot be rewritten into loops.
  - cobbal 2y ago
    More specifically, tail recursion is usually easy to turn into a loop. Tail calls can be difficult to turn into loops when they call a different function, or worse a function passed in as a variable.
    - eru 2y ago
      To give the standard example: 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.)
- slaymaker1907 2y ago
  It can't be rewritten as loop due to function pointers. Using JS notation to avoid noise: 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.