Search code examples
pythonclojurejvmstack-tracetail-call-optimization

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


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.

Explain to me what the big deal with tail call optimization is and why Python needs it

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


Solution

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