4 ms·

Functional languages may be designed to support TCO from the ground up, up to supporting it across module boundaries. C is not like that, and calling into an ex

Functional languages may be designed to support TCO from the ground up, up to supporting it across module boundaries. C is not like that, and calling into an external module necessarily grows the stack.

toast0 2mo ago
> C is not like that, and calling into an external module necessarily grows the stack. This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)
- fluoridation 2mo ago
  Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?
  - toast0 2mo ago
    With the right calling convention, tail calls could conform to the convention. A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work. In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.
    - fluoridation 2mo ago
      >In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. You can still do that with a caller-cleanup convention. Suppose you have a convention like * Set up stack * Call * Clean up stack and you have functions f(), g(), and h(), where g() and h() use this convention and f() calls into g(), and g() into h(). The sequence of instructions from f() to h() without TCO would be * f: Set up stack for g() * f: Call g() * g: Do work * g: Set up stack for h() * g: Call h() * h: Do work * h: Return * g: Clean up stack * g: Return * f: Clean up stack And with TCO: * f: Set up stack for g() * f: Call g() * g: Do work * g: Move things around on the stack so that h()'s arguments are written where g()'s were. This may require a temporary stack allocation that's released before the next step. * g: Jump to h() (At this point it looks as if f() called h() directly.) * h: Do work * h: Return * f: Clean up stack This is always possible as long as h()'s caller-managed stack allocation is no bigger than g()'s.
      - teo_zero 2mo ago
        h() can't have more arguments than g(): that's an important limitation.
        fluoridation 2mo ago
        Consider what was being discussed originally, though. If h() has fewer arguments than g() and is in a different module (e.g. a static library) from h() such that the calling convention was necessary, how would h() recurse back to g()?
        teo_zero 2mo ago
        The example you set up was about f() calling into g() calling into h(). Why do you mention h() calling into g() now? The whole thread is about how the traditional calling convention makes it difficult to implement TCO in C. Functions with different arity having different stack layout is indeed one of the roadblocks, so I think we agree here, no?

toast0 2mo ago

> C is not like that, and calling into an external module necessarily grows the stack. This is because of the calling convention, yes? (and to some extent, if you want an accurate stack trace, but I find it acceptable that TCO also includes stack trace erasure)

fluoridation 2mo ago
Yyyyes... But like I said, TCO cannot make use of the calling convention, because it doesn't involve calling. That means you can't have TCO loops crossing module boundaries (or function pointers for that matter). So we're back to my original question: what does it matter what the calling convention is if the compiler has the liberty to compile both functions however it pleases?
- toast0 2mo ago
  With the right calling convention, tail calls could conform to the convention. A tail call certainly can't use a CALL instruction, because it would set the wrong return address. But that doesn't mean it's not a call; architectures without CALL/RETURN instructions exist, but you can still call into functions and return from them, the compiler just has to do different work. In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. The original caller and the tail callee would be none the wiser. I don't know enough to really evaluate calling conventions against each other, but it's pretty clear that caller cleanup makes tail call optimization more intrusive.
  - fluoridation 2mo ago
    >In a callee cleanup convention, a tail caller could adjust the stack and jump to an unaware tail callee. You can still do that with a caller-cleanup convention. Suppose you have a convention like * Set up stack * Call * Clean up stack and you have functions f(), g(), and h(), where g() and h() use this convention and f() calls into g(), and g() into h(). The sequence of instructions from f() to h() without TCO would be * f: Set up stack for g() * f: Call g() * g: Do work * g: Set up stack for h() * g: Call h() * h: Do work * h: Return * g: Clean up stack * g: Return * f: Clean up stack And with TCO: * f: Set up stack for g() * f: Call g() * g: Do work * g: Move things around on the stack so that h()'s arguments are written where g()'s were. This may require a temporary stack allocation that's released before the next step. * g: Jump to h() (At this point it looks as if f() called h() directly.) * h: Do work * h: Return * f: Clean up stack This is always possible as long as h()'s caller-managed stack allocation is no bigger than g()'s.
    - teo_zero 2mo ago
      h() can't have more arguments than g(): that's an important limitation.
      - fluoridation 2mo ago
        Consider what was being discussed originally, though. If h() has fewer arguments than g() and is in a different module (e.g. a static library) from h() such that the calling convention was necessary, how would h() recurse back to g()?
        teo_zero 2mo ago
        The example you set up was about f() calling into g() calling into h(). Why do you mention h() calling into g() now? The whole thread is about how the traditional calling convention makes it difficult to implement TCO in C. Functions with different arity having different stack layout is indeed one of the roadblocks, so I think we agree here, no?