Hacker News Reader

Comment by cygwin98 | Hacker News Reader

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-preve...

View on HN

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.

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.

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

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

Exactly, it doesn't. Only self-recursion with recur is tail optimized by the JVM

recur isn't tail-optimized by the JVM. It's converted by the Clojure compiler into a loop.

True, my bad

To add to this, Clojure also has "trampoline" for TCO in mutually recursive functions.

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.

Recur is essentially just a loop - it doesn't use the stack at all.

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.

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.

Reply on news.ycombinator.com