<div dir="ltr">Sadly, as the JVM (still) does not support tail call optimization so it has to grow the stack instead.</div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 2, 2015 at 12:18 PM, Millies, Sebastian <span dir="ltr"><<a href="mailto:Sebastian.Millies@softwareag.com" target="_blank">Sebastian.Millies@softwareag.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div lang="EN-GB" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">if that were all there is to it, should it not work also when using the current thread executor? What would then be different about the trampolining?<u></u><u></u></span></p>
<p><u></u><span style="font-size:11.0pt;font-family:Wingdings;color:#1f497d"><span>n<span style="font:7.0pt "Times New Roman""> 
</span></span></span><u></u><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d">Sebastian<u></u><u></u></span></p>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal"><b><span lang="DE" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="DE" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Viktor Klang [mailto:<a href="mailto:viktor.klang@gmail.com" target="_blank">viktor.klang@gmail.com</a>]
<br>
<b>Sent:</b> Wednesday, December 02, 2015 11:53 AM<br>
<b>To:</b> Millies, Sebastian<br>
<b>Cc:</b> <a href="mailto:concurrency-interest@cs.oswego.edu" target="_blank">concurrency-interest@cs.oswego.edu</a><br>
<b>Subject:</b> Re: [concurrency-interest] A puzzle about recursive functions in CompletableFuture<u></u><u></u></span></p><div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">Isn't this "simply" trampolining on the submission queue of the Executor?<br>
<br>
(I informally call it async tailcalls)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Wed, Dec 2, 2015 at 11:34 AM, Millies, Sebastian <<a href="mailto:Sebastian.Millies@softwareag.com" target="_blank">Sebastian.Millies@softwareag.com</a>> wrote:<u></u><u></u></p>
<p class="MsoNormal">Hello there,<br>
<br>
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.<br>
<br>
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:<br>
<br>
public static BigInteger fibTailRecursive(int n) {<br>
    return n <= 2 ? ONE : fibTailRecursiveAux(n, ZERO, ONE);<br>
}<br>
<br>
private static BigInteger fibTailRecursiveAux(int n, BigInteger a, BigInteger b) {<br>
    return n <= 0 ? a : fibTailRecursiveAux(n - 1, b, a.add(b));<br>
}<br>
<br>
And here is the "optimized" version with TRE, in which the elementary case and recursive case are wrapped in methods that return a CompletableFuture:<br>
<br>
public static BigInteger fibCF(int n) {<br>
        return n <= 2 ? ONE : fibCF(n, ZERO, ONE).join();<br>
}<br>
<br>
private static CompletableFuture<BigInteger> fibCF(int n, BigInteger a, BigInteger b) {<br>
        return n <= 0 ? terminate(a) : tailcall(() -> fibCF(n - 1, b, a.add(b)));<br>
}<br>
<br>
This is similar to Pierre-Yves Saumont's approach (cf. <a href="http://www.javacodegeeks.com/2015/10/stack-safe-recursion-in-java.html" target="_blank">
http://www.javacodegeeks.com/2015/10/stack-safe-recursion-in-java.html</a>). 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.<br>
<br>
Finally, here are my problematic implementations of terminate() and tailcall():<br>
<br>
public static <T> CompletableFuture<T> terminate(T t) {<br>
        return completedFuture(t);<br>
}<br>
<br>
public static <T> CompletableFuture<T> tailcall(Supplier<CompletableFuture<T>> s) {<br>
        return CF.thenComposeAsync(_x -> s.get(), THREAD);<br>
}<br>
<br>
private static final CompletableFuture<?> CF = completedFuture(null);<br>
private static final Executor THREAD = Executors.newSingleThreadExecutor(new ThreadFactoryBuilder().setDaemon(true).build());<br>
<br>
(The ThreadFactoryBuilder is from Guava.)<br>
<br>
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.<br>
<br>
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?<br>
<br>
Could anyone explain to me, please, how my coding works?<br>
<br>
-- Sebastian Millies<br>
<br>
<br>
<br>
<br>
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 -
<a href="http://www.softwareag.com" target="_blank">http://www.softwareag.com</a><br>
<br>
<br>
_______________________________________________<br>
Concurrency-interest mailing list<br>
<a href="mailto:Concurrency-interest@cs.oswego.edu" target="_blank">Concurrency-interest@cs.oswego.edu</a><br>
<a href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest" target="_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><u></u><u></u></p>
</div>
<p class="MsoNormal"><br>
<br clear="all">
<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<p class="MsoNormal">-- <u></u><u></u></p>
<div>
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#222222">Cheers,<u></u><u></u></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Arial","sans-serif";color:#222222">√<u></u><u></u></span></p>
</div>
</div>
</div>
</div>
</div>
</div></div></div>
</div>

</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><span style="border-collapse:separate;color:rgb(0,0,0);font-family:Times;font-variant:normal;letter-spacing:normal;line-height:normal;text-align:-webkit-auto;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;font-size:medium"><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13.333333969116211px">Cheers,</div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:13.333333969116211px">√</div></span></div></div></div>
</div>