Only 48 hours left in the trailboss' kickstarter!

New rewards and stretch goals. CLICK HERE!



  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Functional Programming in Java: Tail Call Optimization (TCO)  RSS feed

 
Pho Tek
Ranch Hand
Posts: 782
Chrome Python Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If my memory serves me right, the JVM does not optimize tail calls. Has that changed with Java 8 ?
 
Tim Cooke
Marshal
Posts: 3631
183
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alas no. Another JVM language Scala supports it though.
 
Jason Bullers
Ranch Hand
Posts: 111
8
Clojure IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tim Cooke wrote:Alas no. Another JVM language Scala supports it though.

Indeed it does. For clarity though, that's through compile time magic and not any nice JVM feature.

Maybe some day...
 
Tim Cooke
Marshal
Posts: 3631
183
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, an important distinction. Thanks Jason.
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The JVM does not support TCO, and this is even more of a problem because the stack size is the same for all threads. This means that increasing the stack size to allow for deeper recursion is a waste of memory.

However, it is easy to implement TCO in Java. The trick is to build a (linked) list of computational steps, until the terminal condition is found. then, we just have to execute the steps in reverse order. Here is how it may be implemented:

First, we define a class for representing the computational steps:



The TailCall abstract class has two realisations: the Suspend class represent in intermediate step (when the current processing is "suspended" in order to make the next recursive call), and the Return class representing the terminal computation.

Suppose we want to create a method computing the sum of all positive integers below a given value. We could define it as:



The sum method calls a recursive helper method. This will work for about 3000 to 5000 steps (depending upon the system since the default stack size is system dependent). For higher values, it will overflow the stack.

We can use the TailCall class to make this method stack safe:



Now you can call the sum method with any argument value without blowing the stack.
 
Pho Tek
Ranch Hand
Posts: 782
Chrome Python Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Pierre for the implementation.

From Tim's comment, I found that scala has a @tailrec annotation.
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Note however that the @tailrec notation does not do anything beside telling the compiler that you believe the annotated function to be tail recursive (thus being candidate for tail call elimination). Without the annotation, the compiler will silently optimize the function if possible, and proceed without optimizing if not. Adding the annotation is a way to ask the compiler to warn you if you were wrong believing the function is tail call recursive.
 
Tim Cooke
Marshal
Posts: 3631
183
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pho Tek wrote:I found that scala has a @tailrec annotation.

Be aware that the @tailrec annotation does not have any functional purpose, i.e. it does not make your tail call optimised when it otherwise is not. All it does is cause the compiler to raise an error if your function is not in the correct format required for optimisation.

Pierre-Yves, what a fascinating solution you posed there. I shall most certainly be implementing this myself just to play with it. I can see how you avoid blowing the stack, but I wonder about Object creation on the heap for very deep recursion? I think some experimentation is in order. However, definitely worthy of a cow.
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I can see how you avoid blowing the stack, but I wonder about Object creation on the heap for very deep recursion?


Sure, this involves the creation of many objects. Eventually, for very deep recursion, it might blow the heap. I have never see this happening for up to several millions of recursive steps, but of course, it depends about many factors.
 
Pho Tek
Ranch Hand
Posts: 782
Chrome Python Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Pierre,

My understanding is that your code snippet is implementing a trampoline. Am I correct ? I'm basing this on this article Tail calls, @tailrec and trampolines in scala
 
Pierre-Yves Saumont
Author
Ranch Hand
Posts: 98
17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, it is a trampoline implementation.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!