Java Tail Call Optimization
- What Is the Tail Call Optimization
- Reasons for Not Having Tail Call Optimization in Java
- Is There a Way to Simulate Tail Call Optimization in Java
This tutorial speaks about tail call optimization (also addressed as TCO) and its reasons for not existing in Java. We’ll also see some other ways that we can use to simulate TCO in Java.
What Is the Tail Call Optimization
The tail call optimization is a process where we can avoid allocating one new stack frame for a function because the calling function will return a value it receives from the called function.
One of the most common uses is the tail-recursion (a recursive function where a function calls itself at the end/tail), where the recursive method is written to take advantage of tail call optimization and can use constant stack space.
The Scheme is one of those programming languages that guarantee in the specification that any implementation must serve this optimization. So, the following are two examples of the factorial method in Scheme programming language.
Example Code One (without tail-recursive):
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
Example Code Two (with tail-recursive):
(define (factorial n)
(define (factorial-tail n accum)
(if (= n 0) accum
(factorial-tail (- n 1) (* n accum))))
(factorial-tail n 1))
In example code one, the function is not a tail-recursive. It is because whenever a recursive call is made (considering a factorial example), the method has to keep track of the multiplication it needs to do with results after the call returns.
As such, a stack looks as follows.
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
In contrast, the stack trace for a tail-recursive factorial would be as given below.
(factorial 3)
(factorial-tail 3 1)
(factorial-tail 2 3)
(factorial-tail 1 6)
(factorial-tail 0 6)
6
We are only required to keep track of the same data for each call to factorial-tail.
The reason is that we are returning a value that we get right through to a top which means, even if we were to call (factorial 1000000), we only need the same amount of space as it is required for (factorial 3).
This is not the case when we consider non-tail recursive factorial, and the big values may result in a stack overflow.
Reasons for Not Having Tail Call Optimization in Java
Currently, on the compiler level, Java tail call optimization is not supported in plain Java. Due to the inheritance’s presence, it might not be an easy job to find out a method being called.
Additionally, the present stack counting mechanism does not allow this kind of optimization to be implemented soon. There might be a reason to avoid the drastic change in how the language work every year.
The first reason is that Tail Call Optimization is pricey. Second, according to a rule in Java, we get the stack trace whenever we face an error.
And the stack traces are well-defined concepts that hardly can track one stack frame for every logical call. This will not be possible if tail call optimization exists in Java.
Third, tail call optimization as the model is the way of doing things but not the only way. Generally, it is not that hard to refactor into a loop-based non-recursive algorithm for anything that can be written as the TCO-recursive app.
So, what should we do? We can use the while or for loop instead.
Is There a Way to Simulate Tail Call Optimization in Java
Although Java, the Virtual Machine, has new features that can make things easier for others, non-Java programming languages compile into the class files to execute on a Java runtime to support tail call optimization.
We suggest you watch the following two videos to understand things in the big picture because not every feature is always justified, particularly when the language is one of the most popular languages.
So, we are not sure what approach should be used for using TCO in Java; it is well-explained in the proposal of Project Loom.
However, we think there are still some other ways that we can use to simulate tail call optimization in Java. The first is to use some other JVM language, for instance, Scala.
The second solution can be using the lambda expression. Or, if you dare, you can try something dangerous, like this one.
