Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Tail Call Optimisation in Java

As of Java 8, Java does not provide Tail-Call Optimization (TCO). On researching about it, I came to know the reason which is:

In JDK classes [...] there are a number of security sensitive methods that rely on counting stack frames between JDK library code and calling code to figure out who's calling them.

However Scala, which is based on JVM, has support for Tail-Call Optimisation. Scala does tail recursion optimisation at compile time. Why can't Java use the same approach?

PS: Not sure whether the latest version (Java 11 as of now) of Java now has TCO. Would be great if some who knows can share this also.

Notes:

  1. I know TCO is at backlog and is of lower priority but want to know why can't Java make changes in compile time similar to Scala.

  2. Java doesn't have tail call optimization for the same reason most imperative languages don't have it. Imperative loops are the preferred style of the language, and the programmer can replace tail recursion with imperative loops. (Source)

like image 551
Rishabh Agarwal Avatar asked Nov 17 '18 19:11

Rishabh Agarwal


People also ask

What is tail optimization Java?

Tail recursion is a compile-level optimization that is aimed to avoid stack overflow when calling a recursive method. For example, the following implementation of Fibonacci numbers is recursive without being tail-recursive. The Scala compiler has a built-in tail recursion optimization feature, but Java's one doesn't.

How does tail call optimization work?

Tail call optimization happens when the compiler transforms a call immediately followed by a ret into a single jmp . This transformation saves one instruction, and more importantly it eliminates the implicit push/pop from the stack done by call and ret .

Does Java use tail recursion?

Java supports tail-recursive calls, but AFAIK it doesn't optimize them away.

Why does Java support tail recursion?

Tail-Call Optimisation(TCO) lets us convert regular recursive calls into tail calls to make recursions practical for large inputs, which was earlier leading to stack overflow error in normal recursion scenario. With Scala, making a tail recursive function is easy.


2 Answers

Why can't Java use the same approach ?

I can't say which approach will be used, but it's better-explained in Project Loom's proposal:

As adding the ability to manipulate call stacks to the JVM will undoubtedly be required, it is also the goal of this project to add an even lighter-weight construct that will allow unwinding the stack to some point and then invoke a method with given arguments (basically, a generalization of efficient tail-calls). We will call that feature unwind-and-invoke, or UAI. It is not the goal of this project to add an automatic tail-call optimization to the JVM.

As far as I've heard, work has not yet begun on tail calls, as Fibers and Continuations seem to currently be a higher priority.

like image 89
Jacob G. Avatar answered Oct 05 '22 19:10

Jacob G.


I read a very nice blog post here about how to achieve tail recursion in Java: Knoldus blog post on Java tail recursion

However, the code on their blog doesn't compile so I created a small repo with their code but fixed the syntax so it compiles. Github repo with working code

Hope this is useful to someone, I found the ideas presented at the Knoldus blog post very interesting.

EDIT: actually I found out later that the ideas presented in the blog post are originally Venkat Subramaniam's. He discusses these subjects in his talk here.

like image 36
Jonck van der Kogel Avatar answered Oct 05 '22 20:10

Jonck van der Kogel