9 ms·

I'm puzzled: if Rust and Clojure won't support TCO and they are both cool, why is there such bitter complaining every time it comes up that Python won't support

by pekk 14y ago

I'm puzzled: if Rust and Clojure won't support TCO and they are both cool, why is there such bitter complaining every time it comes up that Python won't support TCO?

kyllo 14y ago
Because Rust and Clojure have have better excuses, maybe? Rust is supposed to be as fast as C/C++ and TCO will slow it down. Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines). Python doesn't support TCO because... it screws up stack traces?
- Rickasaurus 14y ago
  We'll just have to put Rust up against MLton and see if tail calls really are so expensive.
  - larsberg 14y ago
    If I understand it correctly, the Rust issue is that tail calls are expensive in the context of LLVM and the calling convention that they are using. MLton (like Manticore, which I work on) uses a different code generation backend and calling convention entirely. And neither of us worry about "destructors" or, in general, things that happen at every return point. Though, interestingly, in the context of a CPS-converted program, destructors would just be the next continuation called on the way to calling the procedure previously "returned to." Under our (Manticore) calling convention, we would just jump to each of those continuations and wouldn't have to grow stack (though in our case, it's keeping around heap frames, as we're not stack-based), and would have the same next allocation and instruction-level behavior as a tail call. That said, if you think tail calls are hard to debug, CPS-converted programs would destroy most people's will to live. No stack backtraces, except in debug modes, with 5-10x performance penalties.
    - Rickasaurus 14y ago
      I never thought tail calls were hard to debug, but can you can keep text offsets to the original tokens through the CPS transform? Usually with typed languages that's enough information to figure out what went wrong or at least what to log. Also, I'm not sure why the entire library needs the same calling convention when it's such bad form to expose all of your functions anyway.
      - larsberg 14y ago
        You can keep the original tokens. The challenge with debugging such programs is really the integration with the rest of the optimizations. CPS transformation turns your program into a ton of tiny functions. Then, any reasonable optimizer will do a huge amount of inlining. Attempting to do trace-based debugging bounces you from one subexpression in one function to another and so forth. Especially when you consider that Manticore (like MLton) is a whole-program optimizing compiler, you also get little chunks of library functions we've duplicated like map, foldr, etc. Worse, we liberally remove dead code, including unused arguments, branches of conditionals we can guarantee are never called, etc. And since it's a research compiler, there isn't really a "-O0". You can turn off individual optimization passes, but guessing what combination lead to something getting inlined or not requires some careful study. As to why they've chosen what they have with LLVM, I don't know enough to judge. Doing something like ML compilers do with a custom calling convention internally and then a C convention externally is pretty expensive, and ends up putting a massive penalty on C calls (oh, you want to call C? let me move the GC pointer out of the way, set up a fake stack frame for you, etc.). Further, doing it makes register allocation more of a challenge. Many ML compilers like to "pin" certain registers with their own values (e.g., the GC local heap limit pointer) so that we can write custom little blobs of assembly that get emitted in the right places without worrying about substituting in what the _real_ heap limit pointer is, etc. That pinning interacts badly with LLVM, as you can see from the Haskell/LLVM master's paper - they basically had to give up on it and just add their pinned values as extra arguments and then stop emitting code that relied on it being in a sane, typical place. Hope that helps! I've been thinking about these problems and talking only with other people who do the same for so many years I'm starting to forget which parts are and aren't obvious (or even published/documented).
- groovy2shoes 14y ago
  > Rust is supposed to be as fast as C/C++ and TCO will slow it down. TCO doesn't slow programs down. If anything, it might even make them a tiny bit faster. But speed isn't the reason you'd want TCO: you want it as a stack optimization so that tail-recursive functions use constant stack space. Furthermore, although the C specification places no TCO requirement on implementors, it's actually a very reasonable optimization even in C. GCC actually does do TCO in some cases (I'm using 4.5.3, and tail-call elimination occurs with -O2 and higher). > Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines). This is true. There was a time when TCO support was slated for Java 7. That time has come and gone; unofficially, it looks like it may make an appearance in Java 9 at the earliest. > Python doesn't support TCO because... it screws up stack traces? That's the cited reason, but it's horseshit. As others have pointed out on this thread, it's feasible to simply disable TCO when doing debugging if you need a stack trace. Even fancier, there are algorithms to recover the stack even after the calls have been eliminated (see Lua for example).
  - pasquinelli 14y ago
    "TCO doesn't slow programs down. If anything, it might even make them a tiny bit faster." right, but i think they were saying that, in this case, because of dependencies out of the rust team's control, they would have to use a different, slower calling convention to support proper tail calls.
    - fhars 14y ago
      Well, according to a quick perusal of the LLVM documentation, the only llvm calling convention that allows TCO on all platforms seems to be fastcc, whose main purpose is to have calls that are a fast as possible, at the cost of not being compatible with the slower, but more common calling conventions of C. http://llvm.org/docs/LangRef.html#calling-conventions http://llvm.org/docs/LangRef.html#calling-conventions
      - qznc 14y ago
        What does fastcc do when there are more arguments than registers? These cases are the reason for Pascal-convention according to Walton. https://mail.mozilla.org/pipermail/rust-dev/2012-January/001281.html https://mail.mozilla.org/pipermail/rust-dev/2012-January/001...
- mcguire 14y ago
  Well, technically, "it screws up stack traces" is the usual excuse given for why the JVM doesn't support it.
andolanra 14y ago
I can't speak for Clojure, but Rust's rationale for omitting TCO is based on sound engineering issues (as articulated) whereas Guido's sole reason for omitting it (as far as I've seen) is that you lose stack trace information, which is considered something of a red herring (as you can always selectively disable TCO for debugging, and there are ways of retaining stack information anyway.) Note that the original article here is quite disappointed that they can't include TCO, because it would be a valuable tool and allow for different, efficient styles of programming.
- tsewlliw 14y ago
  Amusingly, "losing stack trace information" is among the reasons the JVM doesn't do TCO -- it needs to keep it around for the security manager to do its thing. Its especially annoying there because references are held by higher stack frames and prevent GC, and the destructor excuse isn't present.
  - happy_dino 14y ago
    > it needs to keep it around for the security manager to do its thing Haha. As if the JVM needed proper tail calls to get owned every other week. :-) Anyway, the discussion is pretty much moot, because "JVM" doesn't really refer to specific implementation. If one cares about proper tail calls, use an implementation which supports it.
    - douglasisshiny 14y ago
      Does the JVM get 'owned every other week'? Or are you thinking of the JRE?
    - pjmlp 14y ago
      > Haha. As if the JVM needed proper tail calls to get owned every other week. :-) Correction, the JVM that is made available by Oracle, and most people wrongly think it is the only one. There are tons of JVM vendors out there.
papsosouid 14y ago
Who says they are both cool? HN isn't a single person. It is quite possible that group A thinks rust and clojure are "cool", and group B thinks that languages without TCO (including python, clojure and rust) are bad.
kragen 14y ago
I imagine the same people who complain about lack of TCO in Python are also complaining about lack of TCO in rust and Clojure.
TheCoelacanth 14y ago
Python doesn't optimize any tail calls at all. Rust optimizes sibling calls, which includes all self-tail calls. It's only tail calls to a different function that Rust doesn't eliminate.

by pekk 14y ago

I'm puzzled: if Rust and Clojure won't support TCO and they are both cool, why is there such bitter complaining every time it comes up that Python won't support TCO?

kyllo 14y ago

Because Rust and Clojure have have better excuses, maybe? Rust is supposed to be as fast as C/C++ and TCO will slow it down. Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines). Python doesn't support TCO because... it screws up stack traces?

Rickasaurus 14y ago
We'll just have to put Rust up against MLton and see if tail calls really are so expensive.
- larsberg 14y ago
  If I understand it correctly, the Rust issue is that tail calls are expensive in the context of LLVM and the calling convention that they are using. MLton (like Manticore, which I work on) uses a different code generation backend and calling convention entirely. And neither of us worry about "destructors" or, in general, things that happen at every return point. Though, interestingly, in the context of a CPS-converted program, destructors would just be the next continuation called on the way to calling the procedure previously "returned to." Under our (Manticore) calling convention, we would just jump to each of those continuations and wouldn't have to grow stack (though in our case, it's keeping around heap frames, as we're not stack-based), and would have the same next allocation and instruction-level behavior as a tail call. That said, if you think tail calls are hard to debug, CPS-converted programs would destroy most people's will to live. No stack backtraces, except in debug modes, with 5-10x performance penalties.
  - Rickasaurus 14y ago
    I never thought tail calls were hard to debug, but can you can keep text offsets to the original tokens through the CPS transform? Usually with typed languages that's enough information to figure out what went wrong or at least what to log. Also, I'm not sure why the entire library needs the same calling convention when it's such bad form to expose all of your functions anyway.
    - larsberg 14y ago
      You can keep the original tokens. The challenge with debugging such programs is really the integration with the rest of the optimizations. CPS transformation turns your program into a ton of tiny functions. Then, any reasonable optimizer will do a huge amount of inlining. Attempting to do trace-based debugging bounces you from one subexpression in one function to another and so forth. Especially when you consider that Manticore (like MLton) is a whole-program optimizing compiler, you also get little chunks of library functions we've duplicated like map, foldr, etc. Worse, we liberally remove dead code, including unused arguments, branches of conditionals we can guarantee are never called, etc. And since it's a research compiler, there isn't really a "-O0". You can turn off individual optimization passes, but guessing what combination lead to something getting inlined or not requires some careful study. As to why they've chosen what they have with LLVM, I don't know enough to judge. Doing something like ML compilers do with a custom calling convention internally and then a C convention externally is pretty expensive, and ends up putting a massive penalty on C calls (oh, you want to call C? let me move the GC pointer out of the way, set up a fake stack frame for you, etc.). Further, doing it makes register allocation more of a challenge. Many ML compilers like to "pin" certain registers with their own values (e.g., the GC local heap limit pointer) so that we can write custom little blobs of assembly that get emitted in the right places without worrying about substituting in what the _real_ heap limit pointer is, etc. That pinning interacts badly with LLVM, as you can see from the Haskell/LLVM master's paper - they basically had to give up on it and just add their pinned values as extra arguments and then stop emitting code that relied on it being in a sane, typical place. Hope that helps! I've been thinking about these problems and talking only with other people who do the same for so many years I'm starting to forget which parts are and aren't obvious (or even published/documented).
groovy2shoes 14y ago
> Rust is supposed to be as fast as C/C++ and TCO will slow it down. TCO doesn't slow programs down. If anything, it might even make them a tiny bit faster. But speed isn't the reason you'd want TCO: you want it as a stack optimization so that tail-recursive functions use constant stack space. Furthermore, although the C specification places no TCO requirement on implementors, it's actually a very reasonable optimization even in C. GCC actually does do TCO in some cases (I'm using 4.5.3, and tail-call elimination occurs with -O2 and higher). > Clojure can't have TCO because the Java Virtual Machine doesn't support it. So they have a workaround (trampolines). This is true. There was a time when TCO support was slated for Java 7. That time has come and gone; unofficially, it looks like it may make an appearance in Java 9 at the earliest. > Python doesn't support TCO because... it screws up stack traces? That's the cited reason, but it's horseshit. As others have pointed out on this thread, it's feasible to simply disable TCO when doing debugging if you need a stack trace. Even fancier, there are algorithms to recover the stack even after the calls have been eliminated (see Lua for example).
- pasquinelli 14y ago
  "TCO doesn't slow programs down. If anything, it might even make them a tiny bit faster." right, but i think they were saying that, in this case, because of dependencies out of the rust team's control, they would have to use a different, slower calling convention to support proper tail calls.
  - fhars 14y ago
    Well, according to a quick perusal of the LLVM documentation, the only llvm calling convention that allows TCO on all platforms seems to be fastcc, whose main purpose is to have calls that are a fast as possible, at the cost of not being compatible with the slower, but more common calling conventions of C. http://llvm.org/docs/LangRef.html#calling-conventions http://llvm.org/docs/LangRef.html#calling-conventions
    - qznc 14y ago
      What does fastcc do when there are more arguments than registers? These cases are the reason for Pascal-convention according to Walton. https://mail.mozilla.org/pipermail/rust-dev/2012-January/001281.html https://mail.mozilla.org/pipermail/rust-dev/2012-January/001...
mcguire 14y ago
Well, technically, "it screws up stack traces" is the usual excuse given for why the JVM doesn't support it.

andolanra 14y ago

I can't speak for Clojure, but Rust's rationale for omitting TCO is based on sound engineering issues (as articulated) whereas Guido's sole reason for omitting it (as far as I've seen) is that you lose stack trace information, which is considered something of a red herring (as you can always selectively disable TCO for debugging, and there are ways of retaining stack information anyway.) Note that the original article here is quite disappointed that they can't include TCO, because it would be a valuable tool and allow for different, efficient styles of programming.

tsewlliw 14y ago
Amusingly, "losing stack trace information" is among the reasons the JVM doesn't do TCO -- it needs to keep it around for the security manager to do its thing. Its especially annoying there because references are held by higher stack frames and prevent GC, and the destructor excuse isn't present.
- happy_dino 14y ago
  > it needs to keep it around for the security manager to do its thing Haha. As if the JVM needed proper tail calls to get owned every other week. :-) Anyway, the discussion is pretty much moot, because "JVM" doesn't really refer to specific implementation. If one cares about proper tail calls, use an implementation which supports it.
  - douglasisshiny 14y ago
    Does the JVM get 'owned every other week'? Or are you thinking of the JRE?
  - pjmlp 14y ago
    > Haha. As if the JVM needed proper tail calls to get owned every other week. :-) Correction, the JVM that is made available by Oracle, and most people wrongly think it is the only one. There are tons of JVM vendors out there.

papsosouid 14y ago

Who says they are both cool? HN isn't a single person. It is quite possible that group A thinks rust and clojure are "cool", and group B thinks that languages without TCO (including python, clojure and rust) are bad.

kragen 14y ago

I imagine the same people who complain about lack of TCO in Python are also complaining about lack of TCO in rust and Clojure.

TheCoelacanth 14y ago

Python doesn't optimize any tail calls at all. Rust optimizes sibling calls, which includes all self-tail calls. It's only tail calls to a different function that Rust doesn't eliminate.