Java Fun : Recursive concurrency the easy way
Trampolines allow us to convert recursive loops into iterative ones by swapping stack space for heap space. In Trampolining: a practical guide for awesome Java Developers we showed how Trampolines work, and how we can use them in our code to implement algorithms recursively, in Java without blowing the stack.
Trampolines can also be used to interleave the execution of algorithms, so that they execute concurrently. In our previous article we showed how this can be done by passing Trampoline instances as continuations to methods, but there is an easier and more powerful way to execute Trampoline based methods — without using threads, and that is to zip them.
Zipping Trampolines : easier concurrency
Runar Oli Bjarnason’s paper ‘Stackless Scala with Free Monads’, shows how zipping Trampolines can be used to interleave their execution. For example, we can interleave the execution of two very simple recursive loops which each print out a different marker on each iteration simply by zipping the returned Trampolines.
Calling the interleave method will result in output such as
Zipping recursive data types
Many core cyclops-react data types support stack free recursion (for example Eval, Maybe, Try, Either, Either3, Either4 and Either5), this allows us to define recursive algorithms in terms of these types so long as the recursive call is the last call made within the function supplied to map / flatMap. For example the even / odd looping algorithm from the Herding Cats tutorial converted to work with cyclops-react Maybe types.
The cyclops-types that support tail recursion are easily converted to trampolines (via the toTrampoline method). Which means we can executed them concurrently using the Trampoline zip method.
Defining some simple recursive algorithms
The fibonacci sequence can be defined recursively in a manner that won’t blow the stack like so
The algorithm to calculate the greatest common divisor for two numbers can similarly be defined recursively, in a manner that won’t result in StackOverflowExceptions as follows
We can execute calls to both algorithms concurrently, on the same thread via toTrampoline and zip.
Generalizing concurrent execution
We can make use of zipping functionality on Trampolines to execute recursive algorithms defined in terms of Trampoline in parallel. Trampolines themselves can be implemented in terms of Free Monad (where the Functor type is a Supplier). We can generalize Trampoline zipping to zipping programs (whether recursive or not) defined in custom DSLs for the Free Monad. Which in turn will allow us to execute our Free programs concurrently without recourse to threading. We will cover this option in more detail in DSLs with the Free Monad in Java 8 : part III
Further reading :