Tail Call Recursion in Java with ASM (2023)

I mean, in the particular case demonstrated in this blog post it can only be an optimization, because semantically guaranteeing it would require language features that Java doesn't have.

In a weird way it kinda reminds me of `exec` in sh (which replaces the current process instead of creating a child process). Practically, there's little difference between these two scripts:

    #!/bin/sh
    foo
    bar

vs

    #!/bin/sh
    foo
    exec bar

And you could perhaps imagine a shell that does "tail process elimination" to automatically perform the latter when you write the former.

But the distinction can be important due to a variety of side effects and if you could only achieve it through carefully following a pattern that the shell might or might not recognize, that would be very limiting.

Sigh. I have been kicking this horse forever as well: an "optimization" implies just a performance improvement.

Tail call elimination, if it exists in a language, allows coding certain (even infinite) loops as recursion - making loop data flow explicit, easier to analyze, and at least in theory, easier to vectorize/parallelize, etc

But if a language/runtime doesn't do tail call elimination, then you CAN'T code up loops as recursion, as you would be destroying you stack. So the WAY you code, structure it, must be different.

Its NOT an optimization.

I have no idea who even came up with that expression.

One of the issues with Java is that it is two levels of language. You compile Java into Java Byte code which is further compiled into native machine code. There is no concept of tail call recursion in Java Byte code. So, it is difficult to propagate the semantics. So it really has to be a programmer or compiler optimization to implement the tail call optimization into the generated intermediate bytecode before that is further compiled.

.NET is an interesting contrast. The equivalent of Java Bytecode in .NET (CIL) does have the concept of tail calls. This allows a functional language like F# to be compiled to the intermediate form without losing the tail call concept. It is still up to the first level compiler though. C# for example does not support tail calls even though it’s intermediate target (CIL) does.

Parroting something i have heard at a Java conference several years ago, tail recursion remove stack frames but the security model is based on stack frames, so it has to be a JVM optimization, not a compiler optimization.

I've no idea if this fact still holds when the security manager will be removed.

In general, tail recursion destroys stacktrace information, e.g. if f calls g which tail calls h, and h crashes, you won't see g in the stacktrace, and this is bad for debuggability.

In lower level languages there are also a bunch of other issues:

- RAII can easily make functions that appear in a tail position not actually tail calls, due to destructors implicitly running after the call;

- there can be issues when reusing the stack frame of the caller, especially with caller-cleanup calling conventions;

- the compiler needs to prove that no pointers to the stack frame of the function being optimized have escaped, otherwise it would be reusing the memory of live variables which is illegal.

My bigger issue with tail call optimization is that you really want it to be enforceable since if you accidentally deoptimize it for some reason then you can end up blowing up your stack at runtime. Usually failure to optimize some pattern doesn’t have such a drastic effect - normally code just runs more slowly. So tail call is one of those special optimizations you want a language annotation for so that if it fails you get a compiler error (and similarly you may want it applied even in debug builds).

In theory, if all you do is implement algorithms, this sounds fine. But most apps implement horrible business processes, so what would one do with missing stacktraces? Maybe in languages that can mark functions as pure.

This was delivered in JDK 24 as the "Class-File API"

https://openjdk.org/jeps/484

Kotlin as well, with the "tailrec" keyword, e.g. "tailrec fun fibonacci()"

https://kotlinlang.org/docs/functions.html#tail-recursive-fu...

Kotlin also has a neat other tool, "DeepRecursiveFunction<T, R>" that allows defining deep recursion that is not necessarily tail-recursive.

Really useful if you wind up a problem that is most cleanly solved with mutual recursion or similar:

https://kotlinlang.org/api/core/kotlin-stdlib/kotlin/-deep-r...

Finally.

The ANTLR guys went through terrible contortions for their parsers.

Never felt like working those details out for ABCL.

This isn't a _general_ tail call optimization--just tail recursion. The issue is that this won't support mutual tail recursion.

e.g.:

(defun func-a (x) (func-b (- x 34)) (defun func-b (x) (cond ((<= 0 x) x) ('t (func-a (-x 3))))

Because func-a and func-b are different (JVM) functions, you'd need an inter-procedural goto (i.e. a tail call) in order to natively implement this.

As an alternative, some implementations will use a trampoline. func-a and func-b return a _value_ which says what function to call (and what arguments) for the next step of the computation. The trampoline then calls the appropriate function. Because func-a and func-b _return_ instead of actually calling their sibling, the stack depth is always constant, and the trampoline takes care of the dispatch.