4 ms·

I assume you mean that without TCO the stack might overflow for certain inputs and it is easy to miss those cases during testing. Is that actually a real probl

by qznc 14y ago

I assume you mean that without TCO the stack might overflow for certain inputs and it is easy to miss those cases during testing. Is that actually a real problem? I never hear C/C++/Java/Python/Ruby/Javascript/D/Go/Clojure programmers complain about such bugs. On a Linux/Windows/OS X system the stacks are big enough to practically never hit such bugs. Whenever I get a stack overflow, I coded an infinite loop, which is actually easier to find without TCO, because the program is terminated.

jacquesm 14y ago
C/C++ etc don't have that problem because they have loops. TCO is a way to turn a recursion into a loop. If for every situation where you would elegantly use recursion you'd end up with real recursion and all its overhead you'd indeed end up overflowing the stack. For a C/C++ etc program it would not matter whether your loop iterator would be 10 or 10,000,000,000, the program would just run a little slower. The rust/clojure program (coded up without knowledge of the underlying mechanisms, so 'naively') would likely run out of memory. With TCO such a naive implementation would run just fine. 10,000,000,000 is merely large, not infinite and should all things otherwise being equal not come with a huge memory penalty if all you're doing is writing elegant code in the most applicable idiom for a certain language.
- kibwen 14y ago
  I can't speak for Clojure, but the idiomatic Rust code that I've seen does tend toward C-style iteration (though that iteration is discreetly accomplished via closures and higher-order functions) rather than Lisp-style recursion. So I wouldn't expect recursive memory exhaustion to be a common concern in idiomatic Rust, though that's obviously no consolation if you were hoping to code in a recursive style. Though perhaps you'll be happy to hear that Rust stacks are growable (Go-style) rather than fixed, so stacks are typically small and running out of stack is (afaict) theoretically less of a concern than in C/C++.
- pcwalton 14y ago
  The most applicable idiom for Rust is to use looping with higher-order functions. Rust code doesn't really favor recursion.
  - jacquesm 14y ago
    Yes, but that may very well be because it does not do TCO... What's idiomatic in a language is usually the result of how efficiently that language implements certain constructs.
    - pcwalton 14y ago
      Even if we implemented TCO, I doubt it would be idiomatic because destructors reduce the number of tail call positions so dramatically.
      - jacquesm 14y ago
        Right, because any destructor would break your ability to do TCO assuming that it runs before the tail call... So as soon as you use an object mechanism that will invoke a destructor at some point your ability to use TCO is gone. Interesting, isn't there a possible transformation where you would be able to move the constructor/destructor pairs out of the generated loop construct without breaking the function? After all a tail call is just a fancy go-to under the hood.

by qznc 14y ago

jacquesm 14y ago

C/C++ etc don't have that problem because they have loops. TCO is a way to turn a recursion into a loop. If for every situation where you would elegantly use recursion you'd end up with real recursion and all its overhead you'd indeed end up overflowing the stack. For a C/C++ etc program it would not matter whether your loop iterator would be 10 or 10,000,000,000, the program would just run a little slower. The rust/clojure program (coded up without knowledge of the underlying mechanisms, so 'naively') would likely run out of memory. With TCO such a naive implementation would run just fine. 10,000,000,000 is merely large, not infinite and should all things otherwise being equal not come with a huge memory penalty if all you're doing is writing elegant code in the most applicable idiom for a certain language.

kibwen 14y ago
I can't speak for Clojure, but the idiomatic Rust code that I've seen does tend toward C-style iteration (though that iteration is discreetly accomplished via closures and higher-order functions) rather than Lisp-style recursion. So I wouldn't expect recursive memory exhaustion to be a common concern in idiomatic Rust, though that's obviously no consolation if you were hoping to code in a recursive style. Though perhaps you'll be happy to hear that Rust stacks are growable (Go-style) rather than fixed, so stacks are typically small and running out of stack is (afaict) theoretically less of a concern than in C/C++.
pcwalton 14y ago
The most applicable idiom for Rust is to use looping with higher-order functions. Rust code doesn't really favor recursion.
- jacquesm 14y ago
  Yes, but that may very well be because it does not do TCO... What's idiomatic in a language is usually the result of how efficiently that language implements certain constructs.
  - pcwalton 14y ago
    Even if we implemented TCO, I doubt it would be idiomatic because destructors reduce the number of tail call positions so dramatically.
    - jacquesm 14y ago
      Right, because any destructor would break your ability to do TCO assuming that it runs before the tail call... So as soon as you use an object mechanism that will invoke a destructor at some point your ability to use TCO is gone. Interesting, isn't there a possible transformation where you would be able to move the constructor/destructor pairs out of the generated loop construct without breaking the function? After all a tail call is just a fancy go-to under the hood.