What would the jvm have to sacrifice in order to implement tail call optimisation?

Question

People say that the clojure implementation is excellent apart from the limitation of having no tail call optimisation - a limitation of the jvm not the clojure implementation.

http://lambda-the-ultimate.org/node/2547

It has been said that to implement TCO into Python would sacrifice

• stack-trace dumps, and
• debugging regularity.

http://stackoverflow.com/questions/890461/explain-to-me-what-the-big-deal-with-tail-call-optimization-is-and-why-python-nee

Would the same sacrifices have to be made for a jvm implementation of TCO? Would anything else have to be sacrificed?

Answer 1

Whilst different (in that the il instructions existed already) it's worth noting the additional effort the .Net 64 bit JIT team had to go through to respect all tail calls.

I call out in particular the comment:

The down side of course is that if you have to debug or profile optimized code, be prepared to deal with call stacks that look like they’re missing a few frames.

I would think it highly unlikely the JVM could avoid this either.

Given that, in circumstances where a tail call optimization was requested, the JIT should assume that it is required to avoid a stack overflow this is not something that can just be switched off in Debug builds. They aren't much use for debugging if they crash before you get to the interesting part. The 'optimization' is in fact is a permanent feature and an issue for stack traces affected by it.

It is worth pointing out that any optimization which avoids creating a real stack frame when doing an operation which the programmer conceptually describes/understands as being a stack operation (calling a function for example) will inherently cause a disconnect between what is presented to the user when debugging/providing the stack trace and reality.
This is unavoidable as the code that describes the operation becomes further and further separated from the mechanics of the state machine performing the operation.

Answer 2

Work is underway now to add tail calls to the JVM. There's a wiki page talking about some details.

Answer 3

Yes it is generally the case that implementing TCO will prevent you from getting full stack traces. This is inevitable because the whole point of TCO is to avoid creating additional stack frames.

It's also worth interesting to note that Clojure has an non-stack-consuming "recur" feature to get around this constraint on current JVM versions.

Example:

(defn triangle [n accumulator] 
  (if 
    (<= n 0)  
      accumulator
      (recur (dec n) (+ n accumulator))))

(triangle 1000000 0)

=> 500000500000     (note stack does not explode here!)