11 ms·

I keep hearing that current JVM implementation prevents tail call optimizations [1]. Is it still the case nowadays? Kind of curious on that since there seem to

I keep hearing that current JVM implementation prevents tail call optimizations [1]. Is it still the case nowadays? Kind of curious on that since there seem to be lots of folks on HN use Clojure in production systems. [1] http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations http://stackoverflow.com/questions/105834/does-the-jvm-preve...

sbochins 15y ago
You use recur in clojure for tail optimization. Don't think the jvm has tail optimization support currently.
- dikbrouwer 15y ago
  Exactly, it doesn't. Only self-recursion with recur is tail optimized by the JVM
  - deleted 15y ago
    [deleted]
  - oconnor0 15y ago
    recur isn't tail-optimized by the JVM. It's converted by the Clojure compiler into a loop.
    - dikbrouwer 15y ago
      True, my bad
- bitsai 15y ago
  To add to this, Clojure also has "trampoline" for TCO in mutually recursive functions.
- cygwin98 15y ago
  Is recur kind of workaround? Any performance penalty? Please bear with me as I'm not familiar with Lisp family languages. I'm interested in ML languages. There is a project to port OCaml to JVM, but I don't see any sign of progress, so I thought it may be something on JVM to hold them back.
  - dminor 15y ago
    Recur is essentially just a loop - it doesn't use the stack at all.
  - awj 15y ago
    Recur relies on AST rewriting to turn self-recursion into a loop. The JVM doesn't play a part in this. My impression is that this is 50/50 language design (recur throws errors on non-tail calls) and compromise for the JVM as a platform. OCaml on the JVM would have the same problems, if not worse. Eliminating tail recursion is essential in the ML family, and doing that while sanely supporting Java interop seems to be difficult. I don't really keep up with it much, but I remember proposals to give some bytecode operations that would help here in the next Java version. Not sure if any of them made it past that stage.
  - jcromartie 15y ago
    I actually like the 'recur' better than implicit tail-call optimization. It does what it says on the tin. If you don't use recur, you get unoptimized recursion, and more importantly: where you can't make a function tail-recursive, you can't use 'recur', because it is a compiler error.
arohner 15y ago
A longer answer, because there seems to be a lot of confusion here. The JVM security model allows a function to goto anywhere inside the current function, but does not allow a goto to outside the current function. This means that JVM based languages can do tail call optimizations in self-recursive functions, but can't TCO in mutually recursive functions. With Clojure, Rich Hickey thought there was some accidental complexity here, so he added the recur special form. Recur guarantees the call is in the tail position, and throws an exception if it isnt. Recur can go to the top of the function, or an enclosing loop block inside the function. To do mutual recursion in Clojure, you use a trampoline. That looks like (declare even? odd?) (defn even? [x] (if (= x 0) true #(odd? (dec x))) (defn odd? [x] (if (= x 1) true #(even? (dec x))) (trampoline even? 100) What we're doing here is defining two mutually recursive functions, but instead of calling the other directly, we return a function of no arguments that calls the other function. Then call trampoline, passing the function and any arguments. Not the most elegant solution, but it works.
swannodette 15y ago
Clojure provides three solutions to work around the lack of TCO - recur, trampoline, and lazy sequences. In my experience these provide performance equal to recursive Racket code and I've been able to port Scheme code that expected TCO with little trouble to Clojure.
brlewis 15y ago
Yes, it's still the case that language implementors have to work around the JVM's lack of support for tail call optimization. It's not a big deal for most apps. I leave TCO turned off with Kawa Scheme not because it's a performance problem, but just because it's the default and I don't usually need it. The only code I have compiled with TCO enabled was for maze generation, and I don't think it slowed it down much: http://brlewis.com/amaze.brl http://brlewis.com/amaze.brl

sbochins 15y ago

You use recur in clojure for tail optimization. Don't think the jvm has tail optimization support currently.

dikbrouwer 15y ago
Exactly, it doesn't. Only self-recursion with recur is tail optimized by the JVM
- deleted 15y ago
  [deleted]
- oconnor0 15y ago
  recur isn't tail-optimized by the JVM. It's converted by the Clojure compiler into a loop.
  - dikbrouwer 15y ago
    True, my bad
bitsai 15y ago
To add to this, Clojure also has "trampoline" for TCO in mutually recursive functions.
cygwin98 15y ago
Is recur kind of workaround? Any performance penalty? Please bear with me as I'm not familiar with Lisp family languages. I'm interested in ML languages. There is a project to port OCaml to JVM, but I don't see any sign of progress, so I thought it may be something on JVM to hold them back.
- dminor 15y ago
  Recur is essentially just a loop - it doesn't use the stack at all.
- awj 15y ago
  Recur relies on AST rewriting to turn self-recursion into a loop. The JVM doesn't play a part in this. My impression is that this is 50/50 language design (recur throws errors on non-tail calls) and compromise for the JVM as a platform. OCaml on the JVM would have the same problems, if not worse. Eliminating tail recursion is essential in the ML family, and doing that while sanely supporting Java interop seems to be difficult. I don't really keep up with it much, but I remember proposals to give some bytecode operations that would help here in the next Java version. Not sure if any of them made it past that stage.
- jcromartie 15y ago
  I actually like the 'recur' better than implicit tail-call optimization. It does what it says on the tin. If you don't use recur, you get unoptimized recursion, and more importantly: where you can't make a function tail-recursive, you can't use 'recur', because it is a compiler error.

arohner 15y ago

A longer answer, because there seems to be a lot of confusion here. The JVM security model allows a function to goto anywhere inside the current function, but does not allow a goto to outside the current function. This means that JVM based languages can do tail call optimizations in self-recursive functions, but can't TCO in mutually recursive functions. With Clojure, Rich Hickey thought there was some accidental complexity here, so he added the recur special form. Recur guarantees the call is in the tail position, and throws an exception if it isnt. Recur can go to the top of the function, or an enclosing loop block inside the function. To do mutual recursion in Clojure, you use a trampoline. That looks like (declare even? odd?) (defn even? [x] (if (= x 0) true #(odd? (dec x))) (defn odd? [x] (if (= x 1) true #(even? (dec x))) (trampoline even? 100) What we're doing here is defining two mutually recursive functions, but instead of calling the other directly, we return a function of no arguments that calls the other function. Then call trampoline, passing the function and any arguments. Not the most elegant solution, but it works.

swannodette 15y ago

Clojure provides three solutions to work around the lack of TCO - recur, trampoline, and lazy sequences. In my experience these provide performance equal to recursive Racket code and I've been able to port Scheme code that expected TCO with little trouble to Clojure.

brlewis 15y ago

Yes, it's still the case that language implementors have to work around the JVM's lack of support for tail call optimization. It's not a big deal for most apps. I leave TCO turned off with Kawa Scheme not because it's a performance problem, but just because it's the default and I don't usually need it. The only code I have compiled with TCO enabled was for maze generation, and I don't think it slowed it down much: http://brlewis.com/amaze.brl http://brlewis.com/amaze.brl