4 ms·

And it's not just about linked lists vs arrays, but also about the actual call stack. FP code tends to be heavy on recursive algorithms, which means you need m

And it's not just about linked lists vs arrays, but also about the actual call stack. FP code tends to be heavy on recursive algorithms, which means you need mutually tail recursive functions. And laziness. Somebody mentioned the State monad and the IO type. Well, these are lazy abstractions with a memory-safe bind/flatMap operation that makes them tick. Well, the problem with these abstractions is that they'll require building a data structure that cannot be an array. And in the case of languages like Scala or Clojure that don't have real tail recursion because of the JVM, you need to manage your own trampoline as well. We now have the Free monad, which is awesome, except that it is very heap unfriendly. Actually for FP you need persistent data structures everywhere, not just lists, like maps, hashes, vectors and all known implementations are some sort of trees. And this is an active area of research, but building cache friendly trees is a hard problem.

gengstrand 10y ago
It appears that your claim "Scala or Clojure that don't have real tail recursion because of the JVM" is in error. http://stackoverflow.com/questions/1677419/does-scala-support-tail-recursion-optimization http://stackoverflow.com/questions/1677419/does-scala-suppor... http://clojure.org/reference/special_forms#recur http://clojure.org/reference/special_forms#recur
- tel 10y ago
  It's not exactly an error. Neither language offers enough tail recursion to handle complex cases though they both offer simple support.
- bad_user 10y ago
  I specifically mentioned mutually tail recursive functions. Self-recursive functions, like what you're describing, are much less useful or interesting. I say that as a Scala developer that loves Scala and the JVM - the lack of tail calls optimization at the JVM level is a pain in the ass, because in order to work around it you have to effectively build your own call stack.
- lmm 10y ago
  As your own link makes clear, Scala does not have real tail recursion because of the JVM. It has a very limited form of tail recursion.
omaranto 10y ago
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.

gengstrand 10y ago

It appears that your claim "Scala or Clojure that don't have real tail recursion because of the JVM" is in error. http://stackoverflow.com/questions/1677419/does-scala-support-tail-recursion-optimization http://stackoverflow.com/questions/1677419/does-scala-suppor... http://clojure.org/reference/special_forms#recur http://clojure.org/reference/special_forms#recur

tel 10y ago
It's not exactly an error. Neither language offers enough tail recursion to handle complex cases though they both offer simple support.
bad_user 10y ago
I specifically mentioned mutually tail recursive functions. Self-recursive functions, like what you're describing, are much less useful or interesting. I say that as a Scala developer that loves Scala and the JVM - the lack of tail calls optimization at the JVM level is a pain in the ass, because in order to work around it you have to effectively build your own call stack.
lmm 10y ago
As your own link makes clear, Scala does not have real tail recursion because of the JVM. It has a very limited form of tail recursion.

omaranto 10y ago

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.