6 ms·

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 th

by 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).
      - Rickasaurus 14y ago
        Very helpful, thank you! I guess another problem would be that people often complain about how slow these kinds of compilers can be, and if you keep around enough to reconstruct good error messages it would probably make it that much slower.
        14y ago
  - cwzwarich 14y ago
    If you don't have any interesting control operators like call/cc, prompt/control, etc. then it should be possible to track stack-like control patterns after CPS conversion through the compiler and through DWARF (or a custom debugging format). Unless I am missing something it seems that the control operators are the problem, not CPS.
    - larsberg 14y ago
      Certainly, that's true! As I mentioned in my other far-too-wordy response, though, if you just CPS convert and run a program, it will be far too slow (5x the funcalls != 5x the fun...). So, it's the combination of CPS conversion and later optimizations --- paired with whole-program compilation --- that make it so hard to debug.
  - burntsushi 14y ago
    > (like Manticore, which I work on) Nice! I have had envious eyes for Manticore as a modern replacement for Concurrent ML. Are you guys intending for it to be available for general use or more of a research language?
    - larsberg 14y ago
      It's still a research language today. Honestly, we would need to make a fairly major push --- which would freeze all resarch work and publications --- to get to a point where it is ready for general use. We're working on some grant proposals along those lines, because frankly without NSF support (in the context of making it ready for wider use in classes such as CMU's new intro curriculum), it's unlikely we can justify the massive amount of work required to take it from something that PL experts to use to something that, say, MLton or SML/NJ users could pick up and use. I hate to sound mercenary, but frankly if we can't significantly increase the project from the current number of developers (myself and two part-time undergrads), it's difficult to see how we can make it more generally available. Especially when I lose a couple of months of work every time we double the number of processors in a server-class machine, as there's always either a GC bug or some scalability issue still lurking in the runtime...
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.

by kyllo 14y ago

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).
    - Rickasaurus 14y ago
      Very helpful, thank you! I guess another problem would be that people often complain about how slow these kinds of compilers can be, and if you keep around enough to reconstruct good error messages it would probably make it that much slower.
      - 14y ago
- cwzwarich 14y ago
  If you don't have any interesting control operators like call/cc, prompt/control, etc. then it should be possible to track stack-like control patterns after CPS conversion through the compiler and through DWARF (or a custom debugging format). Unless I am missing something it seems that the control operators are the problem, not CPS.
  - larsberg 14y ago
    Certainly, that's true! As I mentioned in my other far-too-wordy response, though, if you just CPS convert and run a program, it will be far too slow (5x the funcalls != 5x the fun...). So, it's the combination of CPS conversion and later optimizations --- paired with whole-program compilation --- that make it so hard to debug.
- burntsushi 14y ago
  > (like Manticore, which I work on) Nice! I have had envious eyes for Manticore as a modern replacement for Concurrent ML. Are you guys intending for it to be available for general use or more of a research language?
  - larsberg 14y ago
    It's still a research language today. Honestly, we would need to make a fairly major push --- which would freeze all resarch work and publications --- to get to a point where it is ready for general use. We're working on some grant proposals along those lines, because frankly without NSF support (in the context of making it ready for wider use in classes such as CMU's new intro curriculum), it's unlikely we can justify the massive amount of work required to take it from something that PL experts to use to something that, say, MLton or SML/NJ users could pick up and use. I hate to sound mercenary, but frankly if we can't significantly increase the project from the current number of developers (myself and two part-time undergrads), it's difficult to see how we can make it more generally available. Especially when I lose a couple of months of work every time we double the number of processors in a server-class machine, as there's always either a GC bug or some scalability issue still lurking in the runtime...

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.