Haven't noticed it being mentioned here yet: In the actor-concurrency vein, Clojure is vaguely like Elang, but targeting the JVM. Some comparisons vs. Erlang have been made.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Tail recursion vs. JVM bytecode

There was an interesting discussion relating to Clojure on the PLT Scheme list, starting with a message from Geoff Knauth.

Benjamin L. Russell then observed that Clojure has no tail-call optimization — understandably since it compiles to JVM bytecode — and "instead" provides recur and loop forms which can be used to do certain kinds of recursion. This led to a discussion of the limitations of this approach, with Shriram Krishnamurthi asking to see a Clojure version of his automaton example.

This led Benjamin to conclude that:

It is not clear how to perform mutual recursion in Clojure.

Since there is no letrec, a combination of let, loop, and recur apparently must be used. However, by definition, all three special forms bind sequentially, so it is not clear how to create mutually recursive definitions. Without mutually recursive definitions, it does not seem possible to translate your procedure into Clojure.

Some workarounds were discussed, such as Robby Findler's suggestion of using a single loop to avoid mutual recursion, and Henk Boom's code, which has not yet been shown to work.

Java 7 - nope

There's an unofficial list of the proposals for the next version of Java and the JVM. TCO isn't on the list. This is particularly strange since one of the hot topics for Java 7 is closures which, if implemented, will naturally lead people to experiment with functional control structures.

Apparently Scala solves the tail call issue in its actors by using exception throwing under the hood as a form of trampolining.

Actors that Unify Threads and Events -

When the receiving closure terminates, control is returned to the sender by throwing a special exception that unwinds the receiver’s call stack.

However, that doesn't solve the general problem. In my ongoing tutorial on monads in Scala I ported Haskell's IO monad but got burned by the lack of TCO. That's solvable, but messy.

In other Lisps, SISC uses its own heap based stack (with a performance penalty) and Kawa optionally uses a trampolining system (also with a performance hit).

Java 7 - not so fast

Actually James, tail-call optimization has been discussed and is on the list, just a bit hidden under the JSR 292 invokedynamic category, which is kind of serving as a catch-all for JVM enhancements.

John Rose at Sun is leading the charge in this area. He's blogged about tail calls in the past as well. Actually, he's started a new OpenJDK project called the Multi-Language VM project, which will be used specifically to flesh out new ideas for JSR 292 such as invokedynamic and tail call optimization. You can read a little more here or in this mailing list post.

Oops, thanks

Oops, didn't think read beyond the title "invokedynamic." Thanks for the pointer.

TCO & security

It'd be interesting to know what's planned related to the security issue connected to TCO (Java's security policy apparently depends on stack inspection). There was previously some discussion of this in connection with Clements & Felleisen's A Tail-Recursive Machine with Stack Inspection.

Limited TCO?

After chasing all the links that puredanger posted I found very little substantiative in the way of plans. In fact, JSR 292 is still only about invokedynamic. Tail calls are only unofficially discussed in other spots. The appearance is that at best this is in the very early stages and at worst it's not a real contender for the next version.

I have seen discussions of two alternatives:

1) Implement a system like the paper you reference. This likely means a significant overhaul of the security code in the JVM.
2) Implement something more along the lines of what the CLR does: only optimize away stack frames that don't have security implications.

I wouldn't be surprised if the near term answer is #2 since that's likely a much more conservative change to the JVM code base. However, it does lead to some real difficulty in determining why one piece of tail calling code still causes stack growth and overflow while a another apparently similar bit of code is well behaved.

Java Closures

Not sure if it's worth mentioning that Neil Gafter has a prototype implementation of Java closures available. On my list of things to check out.

Clojure does support mutual recursion

Clojure does support mutual recursion in top-level functions, but not letrec, although I might yet add it. I posted an idiomatic version in Clojure.


I posted an idiomatic version in Clojure.

It's surprisingly clean especially given that you didn't define new macros to do it. I haven't studied Clojure yet it's pretty clear and probably clear to anybody with any Lisp experience.

Clojure does support mutual recursion in top-level functions

When you say top level functions can be mutually recursive, do you mean that they can be mutually recursive without growing the stack, or do you just mean they can be defined in terms of each other without confusion? If the former, how did you implement it?

No TCO in Clojure

Just the latter I'm afraid. As discussed above, Clojure shares with Java a lack of TCO.

Tail recursion in OpenQuark

IIUC, OpenQuark compiles to JVM bytecodes and implements TCO with no special constructs in the language.


The docs say:

In addition, the CAL runtime has the following optimizations:

• compiles tail recursive functions as loops

Which is not the same thing as global tail call optimization.

Of course it's possible to do TCO on the JVM, providing one is willing to superimpose some language-specific trampoline/CPS/heap-based-stack/interpretive/etc mechanism on top of the native calling mechanism of the JVM. This may involve tradeoffs with performance and/or interoperability.

For languages which use the native call mechanism, TCO will have to come from the JVM itself. I await it eagerly!