[concurrency-interest] A puzzle about recursive functions in CompletableFuture

Viktor Klang viktor.klang at gmail.com
Wed Dec 2 05:52:45 EST 2015


Isn't this "simply" trampolining on the submission queue of the Executor?

(I informally call it async tailcalls)

On Wed, Dec 2, 2015 at 11:34 AM, Millies, Sebastian <
Sebastian.Millies at softwareag.com> wrote:

> Hello there,
>
> I have thought of a way of doing tail-recursion elimination with
> CompletableFuture. It works, but I do not understand why. There must be
> some inter-thread communication going on about which I have not been able
> to find documentation. Perhaps someone here can enlighten me.
>
> This particular way of doing TRE is not in itself especially worthwhile,
> because it is almost trivial to transform a tail-recursive function into a
> loop manually. However, I think it’s still interesting. So, as an example
> let's use this tail-recursive definition of the Fibonacci series:
>
> public static BigInteger fibTailRecursive(int n) {
>     return n <= 2 ? ONE : fibTailRecursiveAux(n, ZERO, ONE);
> }
>
> private static BigInteger fibTailRecursiveAux(int n, BigInteger a,
> BigInteger b) {
>     return n <= 0 ? a : fibTailRecursiveAux(n - 1, b, a.add(b));
> }
>
> And here is the "optimized" version with TRE, in which the elementary case
> and recursive case are wrapped in methods that return a CompletableFuture:
>
> public static BigInteger fibCF(int n) {
>         return n <= 2 ? ONE : fibCF(n, ZERO, ONE).join();
> }
>
> private static CompletableFuture<BigInteger> fibCF(int n, BigInteger a,
> BigInteger b) {
>         return n <= 0 ? terminate(a) : tailcall(() -> fibCF(n - 1, b,
> a.add(b)));
> }
>
> This is similar to Pierre-Yves Saumont's approach (cf.
> http://www.javacodegeeks.com/2015/10/stack-safe-recursion-in-java.html).
> However, his implementation uses custom classes and an explicit while-loop.
> With TRE I can compute e. g. fibCF(5000), although the recursive version
> normally encounters a StackOverflowError at around n = 1550 on my machine.
>
> Finally, here are my problematic implementations of terminate() and
> tailcall():
>
> public static <T> CompletableFuture<T> terminate(T t) {
>         return completedFuture(t);
> }
>
> public static <T> CompletableFuture<T>
> tailcall(Supplier<CompletableFuture<T>> s) {
>         return CF.thenComposeAsync(_x -> s.get(), THREAD);
> }
>
> private static final CompletableFuture<?> CF = completedFuture(null);
> private static final Executor THREAD =
> Executors.newSingleThreadExecutor(new
> ThreadFactoryBuilder().setDaemon(true).build());
>
> (The ThreadFactoryBuilder is from Guava.)
>
> The interesting thing is that the recursive call is inside the lambda, so
> cannot be seen by the completion handler. It is essential that I use
> thenComposeAsync() and a dedicated thread. Using either thenCompose() or a
> current-thread Executor (Executor e = Runnable::run) will lead to the
> dreaded SOE. So there must be some implicit interaction between the current
> thread and the dedicated thread that prevents this.
>
> I suspect it may have to do with the fact that the "dummy" future CF is
> already completed, so the downstream task would by default be completed in
> the client thread, but is then somehow handed off to the explicitly
> required dedicated thread, with the "recursive" call being landed in the
> client thread again. But how would this prevent SOE?
>
> Could anyone explain to me, please, how my coding works?
>
> -- Sebastian Millies
>
>
>
>
> Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt,
> Germany – Registergericht/Commercial register: Darmstadt HRB 1562 -
> Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman),
> Eric Duffaut, Dr. Wolfram Jost, Arnd Zinnhardt; -
> Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas
> Bereczky - http://www.softwareag.com
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>



-- 
Cheers,
√
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20151202/524fab82/attachment.html>


More information about the Concurrency-interest mailing list