Functional Programming in Java: Tail Call Optimization (TCO)

[Pho Tek]

If my memory serves me right, the JVM does not optimize tail calls. Has that changed with Java 8 ?

[Tim Cooke]

Alas no. Another JVM language Scala supports it though.

[Jason Bullers]

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]

Yes, an important distinction. Thanks Jason.

[Pierre-Yves Saumont]

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:

import java.util.function.Supplier;

public abstract class TailCall<T> {

  public abstract TailCall<T> resume();

  public abstract T eval();

  public abstract boolean isSuspend();

  private TailCall() {}

  public static class Return<T> extends TailCall<T> {

    private final T t;

    private Return(T t) {
      this.t = t;
    }

    @Override
    public T eval() {
      return t;
    }

    @Override
    public boolean isSuspend() {
      return false;
    }

    @Override
    public TailCall<T> resume() {
      throw new IllegalStateException("Return has no resume");
    }
  }

public static class Suspend<T> extends TailCall<T> {

  private final Supplier<TailCall<T>> resume;

  private Suspend(Supplier<TailCall<T>> resume) {
    this.resume = resume;
  }

  @Override
  public T eval() {
    TailCall<T> tailRec = this;
    while(tailRec.isSuspend()) {
      tailRec = tailRec.resume();
    }
    return tailRec.eval();
  }

    @Override
    public boolean isSuspend() {
      return true;
    }

    @Override
    public TailCall<T> resume() {
      return resume.get();
    }
  }

  public static <T> Return<T> ret(T t) {
    return new Return<>(t);
  }

  public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) {
    return new Suspend<>(s);
  }
}

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:

public static int sum(int arg) {
  return sum(arg, 0);
}

private static int sum(int arg, int acc) {
  return arg == 0 
      ? acc 
      : sum(arg - 1, acc + arg);
}

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:

public static int sum(int arg) {
  return sum(arg, 0).eval();
}

private static TailCall<Integer> sum(int arg, int acc) {
  return arg == 0
      ? TailCall.ret(acc)
      : TailCall.sus(() -> sum(arg - 1, acc + arg));
}

Now you can call the sum method with any argument value without blowing the stack.

[Pho Tek]

Thanks Pierre for the implementation.

From Tim's comment, I found that scala has a @tailrec annotation.

[Pierre-Yves Saumont]

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]

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]

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]

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]

Yes, it is a trampoline implementation.

[M Mistroni]

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]

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.