9 ms·

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

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.
    - happy_dino 14y ago
      Which I more or less already said with > If one cares about proper tail calls, use an implementation which supports it. Right?
      - pjmlp 14y ago
        I would say yes, but your remark about getting owned is Oracle specific hence my comment.
rit 14y ago
I can't answer fully for Clojure's reasons for not supporting TCO, but it will at least be fundamentally rooted in the fact that the JVM, as a platform, does NOT support TCO. Scala is usually the language brought up as a counter argument here, but Scala has the same limitations as Clojure - the JVM can't do the TCO. Scala's compiler tries, with certain types of tail calls, to optimize via (I believe) a trampoline – it reduces those calls into a loop, so they are no longer a function call. But, only certain types of calls (specifically, the last line of code in a recursive function must be a call to the hosting function) can be TCO in Scala. There is an annotation, scala.annotation.tailrec, which can be placed above a method you want to tail recurse. @tailrec does not, however, "force" the compiler to do TCO – it simply forces compilation to fail if the method in question cannot be Tail Call Optimized. It's a developer hook for saying "I realize the compiler tries to do TCO where possible, but I require this method to be trampolined". If it can't be, you'll get a compilation error with details on why the TCO failed.
- fhars 14y ago
  Scala compiles direct tail recursion the a jump to the start of the function (jumps within a method are possible on the JVM) without any trampoline. So @tailrec tells the compiler to compile this call to an unconditional jump.
- derleth 14y ago
  > the JVM, as a platform, does NOT support TCO. And the x86, as a platform, does? What, specifically, does the JVM do to make TCO more difficult than it would be in the machine code of your choice?
  - smosher 14y ago
    > And the x86, as a platform, does? "It's complicated." http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations http://stackoverflow.com/questions/105834/does-the-jvm-preve...
  - kragen 14y ago
    Yes, the x86 instruction that implements TCO is called JMP. The JVM doesn't have an equivalent instruction; you can only jump around inside a single method, not to the beginning of another method.
bcoates 14y ago
A debugging switch that, when enabled, turns a valid program into an invalid one is madness. Python has decided to place very conservative requirements on what an implementation's stack must be capable of. This might indicate a certain lack of ambition but it's a justifiable engineering tradeoff.
- andolanra 14y ago
  There are better alternatives to said debugging switch for examining the stack of tail-call-optimized programs, c.f. Clements and Felleisen's 2004 paper, "A Tail-Recursive Machine with Stack Inspection." The debugging switch is merely the simplest naïve option. Essentially, your engineering tradeoff boils down to, "It's easier (for implementers) to omit TCO." That is actually a very reasonable and rational position, as simpler implementations are less likely to have bugs and have a lower creation cost. However, I still hold that the advantages of TCO outweigh the concern about its implementation. (Also, I do not believe that Python does place conservative requirements on an implementation's stack, as a conformant Python implementation must also implement generators; I regard this as roughly on par with TCO's complexity.)
  - kragen 14y ago
    Complexity and stack space usage are two very different things. CPython does indeed place (very!) conservative limits on stack depth, and it also implements generators. I haven't looked at the generator implementation, but it has a number of limits that make it easy to implement — the main one is that generators don't have their own stacks, so can't yield from inside a function they call, the way e.g. Lua coroutines or (effectively) Icon generators can.
    - andolanra 14y ago
      I'm sorry, I made something of a terminological error. When I said 'complexity', I was referring to complexity of implementation, not algorithmic time or space complexity. My intention was to assert that implementing generators and implementing tail-call optimization are both endeavors of roughly the same order of engineering difficulty (as the mechanism used to implement TCO is quite simple) and not to compare the stack space required by each. I also should clarify that at this point, it's likely not reasonable to expect Guido or the Python community to ever turn around and decide to implement TCO, as the current engineering effort required to add TCO to all active implementations of Python is much larger in comparison to the engineering required to add it at an earlier stage. I regard this as a failure of the langauge design from the start, but having made their decision I don't fault the Python community for sticking to it.

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.
  - happy_dino 14y ago
    Which I more or less already said with > If one cares about proper tail calls, use an implementation which supports it. Right?
    - pjmlp 14y ago
      I would say yes, but your remark about getting owned is Oracle specific hence my comment.

rit 14y ago

I can't answer fully for Clojure's reasons for not supporting TCO, but it will at least be fundamentally rooted in the fact that the JVM, as a platform, does NOT support TCO. Scala is usually the language brought up as a counter argument here, but Scala has the same limitations as Clojure - the JVM can't do the TCO. Scala's compiler tries, with certain types of tail calls, to optimize via (I believe) a trampoline – it reduces those calls into a loop, so they are no longer a function call. But, only certain types of calls (specifically, the last line of code in a recursive function must be a call to the hosting function) can be TCO in Scala. There is an annotation, scala.annotation.tailrec, which can be placed above a method you want to tail recurse. @tailrec does not, however, "force" the compiler to do TCO – it simply forces compilation to fail if the method in question cannot be Tail Call Optimized. It's a developer hook for saying "I realize the compiler tries to do TCO where possible, but I require this method to be trampolined". If it can't be, you'll get a compilation error with details on why the TCO failed.

fhars 14y ago
Scala compiles direct tail recursion the a jump to the start of the function (jumps within a method are possible on the JVM) without any trampoline. So @tailrec tells the compiler to compile this call to an unconditional jump.
derleth 14y ago
> the JVM, as a platform, does NOT support TCO. And the x86, as a platform, does? What, specifically, does the JVM do to make TCO more difficult than it would be in the machine code of your choice?
- smosher 14y ago
  > And the x86, as a platform, does? "It's complicated." http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations http://stackoverflow.com/questions/105834/does-the-jvm-preve...
- kragen 14y ago
  Yes, the x86 instruction that implements TCO is called JMP. The JVM doesn't have an equivalent instruction; you can only jump around inside a single method, not to the beginning of another method.

bcoates 14y ago

A debugging switch that, when enabled, turns a valid program into an invalid one is madness. Python has decided to place very conservative requirements on what an implementation's stack must be capable of. This might indicate a certain lack of ambition but it's a justifiable engineering tradeoff.

andolanra 14y ago
There are better alternatives to said debugging switch for examining the stack of tail-call-optimized programs, c.f. Clements and Felleisen's 2004 paper, "A Tail-Recursive Machine with Stack Inspection." The debugging switch is merely the simplest naïve option. Essentially, your engineering tradeoff boils down to, "It's easier (for implementers) to omit TCO." That is actually a very reasonable and rational position, as simpler implementations are less likely to have bugs and have a lower creation cost. However, I still hold that the advantages of TCO outweigh the concern about its implementation. (Also, I do not believe that Python does place conservative requirements on an implementation's stack, as a conformant Python implementation must also implement generators; I regard this as roughly on par with TCO's complexity.)
- kragen 14y ago
  Complexity and stack space usage are two very different things. CPython does indeed place (very!) conservative limits on stack depth, and it also implements generators. I haven't looked at the generator implementation, but it has a number of limits that make it easy to implement — the main one is that generators don't have their own stacks, so can't yield from inside a function they call, the way e.g. Lua coroutines or (effectively) Icon generators can.
  - andolanra 14y ago
    I'm sorry, I made something of a terminological error. When I said 'complexity', I was referring to complexity of implementation, not algorithmic time or space complexity. My intention was to assert that implementing generators and implementing tail-call optimization are both endeavors of roughly the same order of engineering difficulty (as the mechanism used to implement TCO is quite simple) and not to compare the stack space required by each. I also should clarify that at this point, it's likely not reasonable to expect Guido or the Python community to ever turn around and decide to implement TCO, as the current engineering effort required to add TCO to all active implementations of Python is much larger in comparison to the engineering required to add it at an earlier stage. I regard this as a failure of the langauge design from the start, but having made their decision I don't fault the Python community for sticking to it.