3 ms·

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

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.
netheril96 4y ago
> The exact same argument could be made for any compile-time optimization. No. For other optimization, the difference is the speed of execution. For tail call optimization, the difference can be normal execution and stack overflow.
- MereInterest 4y ago
  Any optimization that removes an unnecessary stack allocation could also be the difference between normal execution and stack overflow, due to decreasing the size of the stack frame.
  - netheril96 4y ago
    But the effect is much more likely in tail recursive cases.
quietbritishjim 4y ago
That is exactly why tail call "optimisation" is not, in fact, an optimisation. Indeed much of this discussion, including the title and text of the original post, carefully avoids using the word "optimisation". Somehow it got introduced at some point in these comments. To flip it the other way: consider a normal (non-tail-call) program and choose a local variable in a routine that happens to be called quite a lot. Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash. Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug. That's exactly the situation in a program created with the assumption of tail calls that is then used in an environment without them.
- MereInterest 4y ago
  > Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash. I had to think on this example a bit, but I believe these programs exist and are quite common. This is an accurate description of any program in which memory is allocated and never explicitly freed. Some languages include runtimes that perform garbage collection, but until the garbage collection runs, the program is leaking memory and would crash without the garbage collection. Which is to say, I think I agree with you, but had to chew over the example a bit. That it isn't a quantitative difference in speed or memory usage, but a qualitative difference in the types of programs that are acceptable in a language. Thank you for it.
- haberman 4y ago
  > Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug. Yes, a program that depends on tail call optimization, despite having no guarantee of tail call optimization being performed, has a bug. That doesn't mean that tail call optimization is not an optimization. In languages that allow, but do not guarantee, tail call elimination, it is an optimization performed by the optimizer that makes a program run more optimally than it would have otherwise. There is a long history of referring to it as an optimization, for example in the docs of LLVM: https://llvm.org/docs/LangRef.html#call-instruction https://llvm.org/docs/LangRef.html#call-instruction I don't think it makes sense to redefine the word "optimization" such that it excludes examples where a program could erroneously depend on a certain optimization being performed.

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.

netheril96 4y ago

> The exact same argument could be made for any compile-time optimization. No. For other optimization, the difference is the speed of execution. For tail call optimization, the difference can be normal execution and stack overflow.

MereInterest 4y ago
Any optimization that removes an unnecessary stack allocation could also be the difference between normal execution and stack overflow, due to decreasing the size of the stack frame.
- netheril96 4y ago
  But the effect is much more likely in tail recursive cases.

quietbritishjim 4y ago

That is exactly why tail call "optimisation" is not, in fact, an optimisation. Indeed much of this discussion, including the title and text of the original post, carefully avoids using the word "optimisation". Somehow it got introduced at some point in these comments. To flip it the other way: consider a normal (non-tail-call) program and choose a local variable in a routine that happens to be called quite a lot. Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash. Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug. That's exactly the situation in a program created with the assumption of tail calls that is then used in an environment without them.

MereInterest 4y ago
> Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash. I had to think on this example a bit, but I believe these programs exist and are quite common. This is an accurate description of any program in which memory is allocated and never explicitly freed. Some languages include runtimes that perform garbage collection, but until the garbage collection runs, the program is leaking memory and would crash without the garbage collection. Which is to say, I think I agree with you, but had to chew over the example a bit. That it isn't a quantitative difference in speed or memory usage, but a qualitative difference in the types of programs that are acceptable in a language. Thank you for it.
haberman 4y ago
> Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug. Yes, a program that depends on tail call optimization, despite having no guarantee of tail call optimization being performed, has a bug. That doesn't mean that tail call optimization is not an optimization. In languages that allow, but do not guarantee, tail call elimination, it is an optimization performed by the optimizer that makes a program run more optimally than it would have otherwise. There is a long history of referring to it as an optimization, for example in the docs of LLVM: https://llvm.org/docs/LangRef.html#call-instruction https://llvm.org/docs/LangRef.html#call-instruction I don't think it makes sense to redefine the word "optimization" such that it excludes examples where a program could erroneously depend on a certain optimization being performed.