• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

Functional Programming in Java: Tail Call Optimization (TCO)

 
Ranch Hand
Posts: 782
Python Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If my memory serves me right, the JVM does not optimize tail calls. Has that changed with Java 8 ?
 
Marshal
Posts: 5409
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Alas no. Another JVM language Scala supports it though.
 
Ranch Hand
Posts: 115
11
IntelliJ IDE Clojure Java
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 5409
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, an important distinction. Thanks Jason.
 
Author
Posts: 161
31
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Python Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 161
31
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 5409
326
IntelliJ IDE Python Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 161
31
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Python Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 161
31
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, it is a trampoline implementation.
 
Ranch Hand
Posts: 66
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Pierre
i m currently reading your book FP in Java, it's really cool!
One question for you though.. on the fibonacci implementation with two accumulators
Why , even wtih two accumulators, the code will still end up with a STackOverflow error? is it because java still use the stack even though the last call in the function is a call to itself?
From previous page, i understood that if the last call of a recursive function is a call to itself, nothing needs to be put on the stack?

thanks in advance and regards
Marco
 
Pierre-Yves Saumont
Author
Posts: 161
31
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Marco,

Yes, it is because although the version using two accumulators is tail recursive, Java does not implement TCE (Tail Call Elimination). So to use recursion in Java, you have the following solutions (some may be combined):

- Ensure that the number of steps will be low. This can be the result of some business condition. It could theoretically blow the stack, but you believe it won't happen with normal data.

- Use recursion for cases that can't blow the stack. For example on a balanced binary tree. As the number of objects will be equal to 2 at the power of the recursion depth (something like 2^ 3000), it'll blow the heap long before it exhausts the stack.

- Configure a larger stack. But this is a waste of space in most cases, and anyway, you can go very far in this direction.

- Use the trampoline implementation and tail recursion as I explained. But some recursive computations may not be replaced with tail recursive one.

- Use a language that implements TCO/TCE. This does not mean you have to switch to another language. You could put you tail recursive functions in a library written in Scala and call it from your Java code. Or (much) better, you can write your recursive code in Kotlin. This is not to say that Kotlin is better than Scala, but Kotlin code may be mixed with Java code in the same module. Using IntelliJ for editing and Gradle for Building, you can have Kotlin source files along with Java files in your project. Using Kotlin that way is no different from using any library (besides the fact that you have to learn a different syntax).

- Apply recursion to lazily evaluated collections. There is a strong relationship between the trampoline implementation and laziness. The trampoline is, in fact, a lazy computation. The trampoline can't be used for right-folding a list. However, under some conditions, a lazy-list, may be right-folded without any problem as I described in chapter 9 of my book due to the fact that no actual computation occurs. It will still blow the stack if the full lazy list is eventually evaluated. But often, it will not be the case because the number of elements will have been reduced before the data is evaluated.
 
There are 29 Knuts in one Sickle, and 17 Sickles make up a Galleon. 42 tiny ads in a knut:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic