4 ms·

I understand what Guido is saying to some extent. I thought through it, and my logic seems to go as follows. 1. Compilers are not perfect. In fact, they are

I understand what Guido is saying to some extent. I thought through it, and my logic seems to go as follows. 1. Compilers are not perfect. In fact, they are incredibly dumb and get things wrong all the time. Add in the fact that the compiler often does not have enough information to properly make an optimization, the output goes from "retarded" to "braindead." 2. If you make certain types of optimizations and tell people that it is fine to rely on them--even if those optimizations will not always work--performance on average will get worse. Tail recursion seems like a classic case of an optimization which, if one relied on it but the optimization failed, would have catastrophic results (a crash due to running out of stack space). In a very simple language like Scheme, relying on tail recursion is probably not a problem because of how simple such an optimization is. But with something of the complexity of python, it might not be as safe. Given the catastrophic number of regressions in compilers these days, imagine what would happen if your program was made for Python 2.5, which had tail recursion optimization, and then you updated to 2.6, and due to a change in optimization code, it failed to do tail recursion optimization on one particular function? Your program would crash. I think in general it is never safe to make the assumption that an optimizer will make a particular "good decision". Compilers and optimizers are incredibly stupid, and relying on them to be smart is a sure way to end up with all sorts of problems. Yet with something like a C compiler and loop unrolling, the consequences of such a thing can never be too bad: even in the worst case, you only lose performance. But with tail recursion, a failure could mean an actual crash.

silentOpen 18y ago
Garbage collected languages are good examples of places where people regularly trust complex abstractions. Compiler behavior is analogous.
- DarkShikari 18y ago
  Which is often equally dangerous--applications which rely on garbage collection often use vastly more memory than applications that don't. A particularly analogous situation, however, would be a C application that relies on a non-guaranteed GC, i.e. one that is not guaranteed to garbage collect all objects. In such a case, you're almost sure to eventually run out of memory. This is as opposed to the Java GC, which, while potentially inefficient, will (AFAIK) GC all objects. Another analogous situation would be an application built to run on a server with 2 gigabytes of memory. The application uses 1.6 gigabytes and uses GC. A change in GC results in the program actually needing 2.4 gigabytes despite the actual internal memory usage never changing, and your servers grind to a halt.
  - silentOpen 18y ago
    I wouldn't want my pacemaker running a garbage-collected language and yet most web apps are written with GC. Google uses GC languages. GC can be done correctly and efficiently. TCO is not very hard to implement in a compiler/interpreter if considered from the beginning. Unless your compiler/interpreter was designed very poorly, it probably isn't very hard to implement later, either. Given this, it doesn't really make sense to not trust TCO because it's somehow black magic. There may be other arguments against wanting TCO in your language of choice ("I really need backtraces all the time and I can't sacrifice simple, provable interpreter optimizations!") but reliability can't be it.
    - DarkShikari 18y ago
      Given this, it doesn't really make sense to not trust TCO because it's somehow black magic. I wouldn't say it's black magic at all--it's just that from my experience you can rarely even trust compilers with the most basic of things, let alone black magic.
      - silentOpen 18y ago
        If you're doubting your compiler for the most basic things, you may want to get a new compiler.
    - mcav 18y ago
      > I wouldn't want my pacemaker running a garbage-collected language and yet most web apps are written with GC. I'd prefer GC over memory leaks...
      - silentOpen 18y ago
        You don't need either in a pacemaker, though. If you're dynamically allocating memory in a pacemaker, something's wrong.
kylec 18y ago
I think that compiler optimizations should be classified into "leaky" and "non-leaky" (much like Joel's leaky abstractions). Basically, a "leaky" optimization would be where the compiler looks for basic patterns that can be optimized away, but where sufficiently complicated and convoluted code can cause the compiler not to recognize the optimization. A "non-leaky" optimization would be one where the compiler can always optimize away a specific coding pattern. Though, to some, tail-call elimination is dark magic, in reality the optimization can always be performed. As alluded to in the article, all that's necessary is to replace the existing stack frame when returning a value.
- DarkShikari 18y ago
  Even so, you need to be able to make a very specific formal declaration of exactly what constructs result in the optimization being non-leaky. It needs to be completely straightfoward and easy enough to understand that no programmer gets into the situation where they think a leaky optimization is non-leaky. And once you make an optimization non-leaky, it cannot ever become leaky again in any particular situation whatsoever, or it could break existing programs.
shiro 18y ago
This is why I don't like people referring proper tail recursion as tail call optimization. It leads to an assumption that it is somewhat optional, or something that doesn't change meaning of programs but only affects performance. Proper tail recursion is much more fundamental property of language. Whether you have a guaranteed proper tail recursion or not affects the behavior of the program in terms of complexity (as discussed in Joe's article). Consequently it affects your choice of algorithms and coding styles. An example is that you start feeling very natural to represent state machine in terms of function calls (function = state, tail call = transition). I don't claim that proper tail recursion is the only correct answer. It is a design choice. But if you opt out, you'd better understand what you're trading. That said, I agree with you that optional TCO which you can't rely on isn't very useful. The proper tail recursive language, like Scheme, defines exactly what are tail calls so programmers can rely on it.

silentOpen 18y ago

Garbage collected languages are good examples of places where people regularly trust complex abstractions. Compiler behavior is analogous.

DarkShikari 18y ago
Which is often equally dangerous--applications which rely on garbage collection often use vastly more memory than applications that don't. A particularly analogous situation, however, would be a C application that relies on a non-guaranteed GC, i.e. one that is not guaranteed to garbage collect all objects. In such a case, you're almost sure to eventually run out of memory. This is as opposed to the Java GC, which, while potentially inefficient, will (AFAIK) GC all objects. Another analogous situation would be an application built to run on a server with 2 gigabytes of memory. The application uses 1.6 gigabytes and uses GC. A change in GC results in the program actually needing 2.4 gigabytes despite the actual internal memory usage never changing, and your servers grind to a halt.
- silentOpen 18y ago
  I wouldn't want my pacemaker running a garbage-collected language and yet most web apps are written with GC. Google uses GC languages. GC can be done correctly and efficiently. TCO is not very hard to implement in a compiler/interpreter if considered from the beginning. Unless your compiler/interpreter was designed very poorly, it probably isn't very hard to implement later, either. Given this, it doesn't really make sense to not trust TCO because it's somehow black magic. There may be other arguments against wanting TCO in your language of choice ("I really need backtraces all the time and I can't sacrifice simple, provable interpreter optimizations!") but reliability can't be it.
  - DarkShikari 18y ago
    Given this, it doesn't really make sense to not trust TCO because it's somehow black magic. I wouldn't say it's black magic at all--it's just that from my experience you can rarely even trust compilers with the most basic of things, let alone black magic.
    - silentOpen 18y ago
      If you're doubting your compiler for the most basic things, you may want to get a new compiler.
  - mcav 18y ago
    > I wouldn't want my pacemaker running a garbage-collected language and yet most web apps are written with GC. I'd prefer GC over memory leaks...
    - silentOpen 18y ago
      You don't need either in a pacemaker, though. If you're dynamically allocating memory in a pacemaker, something's wrong.

kylec 18y ago

I think that compiler optimizations should be classified into "leaky" and "non-leaky" (much like Joel's leaky abstractions). Basically, a "leaky" optimization would be where the compiler looks for basic patterns that can be optimized away, but where sufficiently complicated and convoluted code can cause the compiler not to recognize the optimization. A "non-leaky" optimization would be one where the compiler can always optimize away a specific coding pattern. Though, to some, tail-call elimination is dark magic, in reality the optimization can always be performed. As alluded to in the article, all that's necessary is to replace the existing stack frame when returning a value.

DarkShikari 18y ago
Even so, you need to be able to make a very specific formal declaration of exactly what constructs result in the optimization being non-leaky. It needs to be completely straightfoward and easy enough to understand that no programmer gets into the situation where they think a leaky optimization is non-leaky. And once you make an optimization non-leaky, it cannot ever become leaky again in any particular situation whatsoever, or it could break existing programs.

shiro 18y ago

This is why I don't like people referring proper tail recursion as tail call optimization. It leads to an assumption that it is somewhat optional, or something that doesn't change meaning of programs but only affects performance. Proper tail recursion is much more fundamental property of language. Whether you have a guaranteed proper tail recursion or not affects the behavior of the program in terms of complexity (as discussed in Joe's article). Consequently it affects your choice of algorithms and coding styles. An example is that you start feeling very natural to represent state machine in terms of function calls (function = state, tail call = transition). I don't claim that proper tail recursion is the only correct answer. It is a design choice. But if you opt out, you'd better understand what you're trading. That said, I agree with you that optional TCO which you can't rely on isn't very useful. The proper tail recursive language, like Scheme, defines exactly what are tail calls so programmers can rely on it.