How to write a test case for this

Question

I have been asked to remove the stack overflow exception that occurs on running the following code - when heavy data is supplied. That is all I am told. Sadly, I am not sure how I can write a junit test case around it as I dont really understand what is happening here. Could some one help me understand this :

public interface FolderMaster<T, U>{        
U foldIt(U u, Queue<T> list, FunctionBi<T,U,U> bidi);    
}

public interface FunctionBi<T, U, R>{        
R applyIt(T t, U u);    
}

public class CommonFolder<T, U> implements FolderMaster<T, U>{
    public U foldIt(U u, Queue<T> ts, FunctionBi<T, U, U> bidi){
        if(u == null || ts == null || bidi == null)
            throw new IllegalArgumentException();

        if (ts.isEmpty()) {
            return u;
        }

        return foldIt(bidi.applyIt(ts.poll(), u), ts, bidi);
       }
}

Since the FunctionBi is closely matching java.util.functoin.BiFunction I looked up the java doc, but it just has an interface method apply. Are there any classes which demonstrate the usage of this class ? I guess am just lost with understanding how the code above works.

Maybe you should start with creating some meaningful variable names. If you know the context this is done in, you'll find it a lot easier to actually understand it. — Jeroen Vannevel, Oct 19 '13 at 18:34
this might be of use: http://en.wikipedia.org/wiki/Fold_(higher-order_function) — Mateusz Dymczyk, Oct 19 '13 at 18:36
The problem here is that sometimes the queue passed to foldIt is too long, so foldIt will call itself lots of times and eventually throw a stack overflow exception. You can remove the exception by removing the recursion — Matthew Mcveigh, Oct 19 '13 at 18:36
@JeroenVannevel The variable naming wasn't upto me. I was basically given this code and asked to investigate. — AussieMoss, Oct 19 '13 at 19:22
@MatthewMcveigh Would you know of any examples which show what could substitute the process of recursion ? — AussieMoss, Oct 19 '13 at 19:22
Variable names are fine BTW. This appears to be completely general library code - as such, generic names for generically typed values is fine (good, in fact). — Paul, Oct 25 '13 at 14:38

Mateusz Dymczyk · Accepted Answer · 2013-10-20T03:22:17.550

As I posted in the comment this basically is a well know function "fold" from functional programming.

What is fold? It's called fold because it "folds" a given data structure using some base value and some function. In your case the data structure to be folded is the Queue. The base value is the first argument of foldIt (u), the bidi function is the function that will tell you how to fold it. It's generalized using 3 types because it takes in 2 types and computes a result of the 3rd type.

Ok, what? Very basic example of folding would be:

u = 1;

queue = (2,3,4)

bidi(t,u) = return (t+u)

Here first foldIt(u, queue, bidi) would add 1+2=3 and then call foldIt(3,(3,4),bidi). So as you can see the base value of the next step is the result of the previous step's bidi. It goes on till there are elements to be folded and returns the accumulated (folded) value.

The problem: Now the problem here is that someone tried to implement it in a functional fashion on the JVM which does not fully support functional style programming (even in Java8). Well ok the JVM does support it (for instance Scala does it), but Java does not support it (for reasons which aren't necessarily good).

Because the return statement is a call to the foldIt() method and nothing more this is called a tail recursion. Tail recursions are nice because you do not need a new stack frame for each new call, you can reuse the current stack frame as there are no local variables that have to be persisted during the recursion.

Unfortunately Java does not support tail-call optimization and it will create a new stack frame for each invocation of foldIt().

The solution to this problem was already posted by @Tassos Bassoukos and you simply need to replace the recursive invocation to foldIt() with an iteration. How is it done usually? Well basically what the computer does when you use recursion (or any method invocation) is it creates a new stack frame for each invocation that holds information about it (local variables, some pointers etc.) and push it to the current stack of execution. So to overcome this you can make an iteration and push needed values onto your own stack, that might save you some space (you dont need to store pointers required by the computer to know to where in the memory it needs to go back from the recursive call etc.). In this case (tail recursion) it's even better because you have no local variables and you can skip the stack! Something like this:

public class CommonFolder<T, U> implements FolderMaster<T, U>{
    public U foldIt(U u, Queue<T> ts, FunctionBi<T, U, U> bidi){
        if(u == null || ts == null || bidi == null)
            throw new IllegalArgumentException();

        while (!ts.isEmpty()) {
            u = bidi.applyIt(ts.poll(), u);
        }

        return u;
    }
}

Here you are not invoking anything recursively so you won't have too many new stack frames (well only a constant amount for isEmpty() and applyIt()) and no stackoverflow.

Dont have the rep to upvote it but Thank you for this answer. It has helped me understand better. I will need to read this a few times though and work around a few examples. — AussieMoss, Oct 19 '13 at 20:52

score 0 · Answer 2 · answered Oct 19 '13 at 19:03

0

Manual tail-call elimination; you need to convert the recursion into a loop; covered in any CS degree.

answered Oct 19 '13 at 19:03

Tassos Bassoukos

16,017
2
36
40

1

Looks like JVM doesn't support it : http://stackoverflow.com/q/3616483/2570213 Could you please point me to any examples which could help me with this ? – AussieMoss Oct 19 '13 at 19:23
@AussieMoss JVM does support it, Java does not. You need to manually change the recursion into an iteration as Tassos said. – Mateusz Dymczyk Oct 19 '13 at 19:30

How to write a test case for this

2 Answers2