41 ms·

Saying that Clojure and Scala don't do tail call optimization because of the JVM could be a little misleading. The JVM is a pretty general compilation target, I

Saying that Clojure and Scala don't do tail call optimization because of the JVM could be a little misleading. The JVM is a pretty general compilation target, I'm sure you could implement tail call optimization in a compiler targeting the JVM in any of the usual ways. If Clojure and Scala don't do it it must be for some other reason. If I had to guess I'd say it's probably (1) that the developers don't think TCO is that important (lots of language implementations don't have it and are perfectly usable), (2) for ease of implementation, (3) for better interop with Java libraries, or a mix of these reasons.

johncolanduoni 10y ago
You can implement tail recursion optimization on top of the JVM (which is far, far away from a general compilation target BTW), where the distinction is that the function may only call itself. These cases can always be trivially rewritten into loops, and I know at least Scala does this just fine. More generally tail call optimization allows you to avoid pushing a stack frame for any call in tail position. The JVM (or even LLVM) does not give you the necessary tools to implement this yourself, since you can't play games with your stack frame and return address directly.
- omaranto 10y ago
  I think you're implicitly thinking that a sensible compiler targeting the JVM would compile whatever functions the source language has to JVM methods and call them via the usual JVM method call instruction. That's certainly a good thing to do if you want have simple Java interop and to reuse the JVM's call logic instead of simulating your own calling convention with other instructions. I was implicitly thinking there's nothing forcing you to use the JVM calling convention. For example your compiler could transform the source to CPS. That probably would generate slow code and interop would be awkward (because normal Java libraries aren't already in CPS).
- omaranto 10y ago
  An example of a language implementation that does full TCO and targets the JVM: http://sisc-scheme.org/ http://sisc-scheme.org/ I couldn't find this right away, but vaguely recall reading SISC transforms to CPS to anable this (and call/cc). I think Kawa scheme supports two calling conventions: the standard JVM one and a second one for which it can do full TCO. The second one is a bit slower so the default in Kawa is not to do full TCO.

johncolanduoni 10y ago

You can implement tail recursion optimization on top of the JVM (which is far, far away from a general compilation target BTW), where the distinction is that the function may only call itself. These cases can always be trivially rewritten into loops, and I know at least Scala does this just fine. More generally tail call optimization allows you to avoid pushing a stack frame for any call in tail position. The JVM (or even LLVM) does not give you the necessary tools to implement this yourself, since you can't play games with your stack frame and return address directly.

omaranto 10y ago
I think you're implicitly thinking that a sensible compiler targeting the JVM would compile whatever functions the source language has to JVM methods and call them via the usual JVM method call instruction. That's certainly a good thing to do if you want have simple Java interop and to reuse the JVM's call logic instead of simulating your own calling convention with other instructions. I was implicitly thinking there's nothing forcing you to use the JVM calling convention. For example your compiler could transform the source to CPS. That probably would generate slow code and interop would be awkward (because normal Java libraries aren't already in CPS).
omaranto 10y ago
An example of a language implementation that does full TCO and targets the JVM: http://sisc-scheme.org/ http://sisc-scheme.org/ I couldn't find this right away, but vaguely recall reading SISC transforms to CPS to anable this (and call/cc). I think Kawa scheme supports two calling conventions: the standard JVM one and a second one for which it can do full TCO. The second one is a bit slower so the default in Kawa is not to do full TCO.