4 ms·

> Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit If an implementation really want

> Implementations are required to have every call consume some abstract resource towards exhausting some abstract finite limit If an implementation really wanted to, they could get around this by incrementing a "function call counter" that traps at, say, 2^64, rendering it effectively moot. I feel like these kinds of situations are where being practical might make more sense than being mathematically precise. Something like "each function call must consume at least N bits of memory" or something concrete like that. Or heck, "implementations may not perform tail-call optimization" or even "implementations must be able to reconstruct the full logical call stack at any point".

wyager 4y ago
> each function call must consume at least N bits of memory This is going to be a problem for any long-running recursive program. Why would we mandate this?
- Retr0id 4y ago
  It is implicitly already mandated, depending on how finite your finite limit is.
- dragonwriter 4y ago
  The reason for the existing mandate is to be a problem for recursive programs, so it is a feature, not a bug, of the proposed refinement that it more reliably achieves that. (Specifically, to prevent one implementation getting an optimization for them that leads people to rely on it, making code that blows up in practical use on other implementations, despite both being nominally correct implementations of the same spec.)
- haberman 4y ago
  You don't want it to be implementation-specific whether tail call optimization is performed or not. The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO. You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motivation for the clang:musttail attribute in C/C++ (I implemented musttail in Clang): https://clang.llvm.org/docs/AttributeReference.html#musttail https://clang.llvm.org/docs/AttributeReference.html#musttail
  - MereInterest 4y ago
    This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altogether out of a desire for consistency. To me, I'd see a distinction between code that requires a specific optimization and code that could benefit from that optimization. If the standard forbids an optimization to avoid the former, it also removes the latter.
    - haberman 4y ago
      Most optimizations only offer constant factor improvements. Tail call optimization is the difference between O(1) and O(N) stack size.
      - phkahler 4y ago
        Tail calls can be optimized at the source code level too. When I first read about them decades ago I thought it was a stupid notion due to me not understanding how a good compiler can optimize them away. Then I wondered why certain people felt the need to write code that way. I still wonder that.
        haberman 4y ago
        I wrote an article about my motivation for it: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
        phkahler 4y ago
        Thanks for that. Having written a threaded interpreter before that immediately made sense. It does seem like you used some other hints to the compiler as well so this would fall under "experts only" type of code and that's OK. I still wonder how well good old "goto" might do, but once you move away from a huge switch/case to individual functions I can see how it might help a bit. I still don't understand why some people seem to like the idea of iterating simpler things with recursion using a tail call.
- dataangel 4y ago
  Try writing a loop over all 64 bit values. The computer will break before the loop finishes.

wyager 4y ago

> each function call must consume at least N bits of memory This is going to be a problem for any long-running recursive program. Why would we mandate this?

Retr0id 4y ago
It is implicitly already mandated, depending on how finite your finite limit is.
dragonwriter 4y ago
The reason for the existing mandate is to be a problem for recursive programs, so it is a feature, not a bug, of the proposed refinement that it more reliably achieves that. (Specifically, to prevent one implementation getting an optimization for them that leads people to rely on it, making code that blows up in practical use on other implementations, despite both being nominally correct implementations of the same spec.)
haberman 4y ago
You don't want it to be implementation-specific whether tail call optimization is performed or not. The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO. You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motivation for the clang:musttail attribute in C/C++ (I implemented musttail in Clang): https://clang.llvm.org/docs/AttributeReference.html#musttail https://clang.llvm.org/docs/AttributeReference.html#musttail
- MereInterest 4y ago
  This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altogether out of a desire for consistency. To me, I'd see a distinction between code that requires a specific optimization and code that could benefit from that optimization. If the standard forbids an optimization to avoid the former, it also removes the latter.
  - haberman 4y ago
    Most optimizations only offer constant factor improvements. Tail call optimization is the difference between O(1) and O(N) stack size.
    - phkahler 4y ago
      Tail calls can be optimized at the source code level too. When I first read about them decades ago I thought it was a stupid notion due to me not understanding how a good compiler can optimize them away. Then I wondered why certain people felt the need to write code that way. I still wonder that.
      - haberman 4y ago
        I wrote an article about my motivation for it: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
        phkahler 4y ago
        Thanks for that. Having written a threaded interpreter before that immediately made sense. It does seem like you used some other hints to the compiler as well so this would fall under "experts only" type of code and that's OK. I still wonder how well good old "goto" might do, but once you move away from a huge switch/case to individual functions I can see how it might help a bit. I still don't understand why some people seem to like the idea of iterating simpler things with recursion using a tail call.
dataangel 4y ago
Try writing a loop over all 64 bit values. The computer will break before the loop finishes.