Tail Call Recursion?

[clay]

Is tail call recursion support coming to JVM?

Many algorithms are most elegantly expressed in a recursive nature. Textbooks and academics typically use the most appropriate and elegant notation available, but a JVM programmer is expected to manually avoid recursive code due to the lack of internal optimization.

I've heard Scala is working on this optimization at the language compiler level, but also that it would be more efficiently implemented at the VM level. Secondly, it would be nice if the flagship JVM language, Java, supported this.

If Jigsaw is being postponed from JDK 8, this would be another big potential feature to have.

[Kevin Wright]

Scala has already been doing it for quite some time now, but just within a single method.

It will happen by default where possible.  If you want to be certain then use the @tailrec annotation on your method, which will force the compiler to emit an exception if it can't be done.

For anything "bigger", such as tail recursing across two or more methods, you'll need something like the trampoline functionality that scalaz provides.

--
You received this message because you are subscribed to the Google Groups "Java Posse" group.
To view this discussion on the web visit https://groups.google.com/d/msg/javaposse/-/VknSiMzz9kUJ.
To post to this group, send email to java...@googlegroups.com.
To unsubscribe from this group, send email to javaposse+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/javaposse?hl=en.

[clay]

Wow, I didn't realize Scala had already completed this. If I may ask, what is the advantage of JVM level support?

One of my Scala expert colleagues said this was the only feature he could think of in addition to Jigsaw that was needed at the JVM level.

[Ricky Clarkson]

JVM-level support would allow for tail recursion between two methods in otherwise unrelated classes to happen.  Trampolining is a good workaround (or even implementation technique) but at the JVM level it would likely be a lot faster.  Right now recursive algorithms pay a prohibitive penalty on the JVM, forcing programmers to choose between readable and fast.

--

You received this message because you are subscribed to the Google Groups "Java Posse" group.

To view this discussion on the web visit https://groups.google.com/d/msg/javaposse/-/cdKdk3n1vu0J.

[Kevin Wright]

Scala can only do it by transforming the recursive call into a jump at compile time - hence the single method restriction.

We *could* do better in theory, but only at the unacceptable expense of compatibility with other languages on the platform.

If the JVM did it, however, then this wouldn't be a problem.

You may also want to point your colleague in the direction of every improvement that John Rose has ever suggested. Fixnum's would be a pretty beneficial addition as well!

--

You received this message because you are subscribed to the Google Groups "Java Posse" group.

To view this discussion on the web visit https://groups.google.com/d/msg/javaposse/-/cdKdk3n1vu0J.

[Ricky Clarkson]

The other expense if Scala did it better would be separate compilation (being able to compile X and Y separately or together and getting the same bytecode out) unless it introduced a special Scala classloader, which I'm pretty sure was ruled out years ago.

[Kevin Wright]

Well, yes, there is that as a minor inconvenience as well :)

[Philip Schwarz]

Java is unable to do tail-call optimisation (TCO), so in Java all recursive functions are stack-consuming. Other languages, e.g. Haskell and Scheme, are able to do automatic TCO and so tail recursive functions are not stack-consuming.

It is not just Java that is unable to perform automatic TCO: As Stuart Halloway says in 'Programming Clojure', "no language that runs directly on the JVM can perform automatic TCO".

While Clojure (which runs on the JVM) is not able to do automatic TCO, id does support TCO: In Clojure you can explicitly tell the compiler that a function is tail-recursive by replacing the name of the function in the tail-recursive call with the 'recur' keyword.

Here is an example of a tail recursive Fibonacci function

(defn recur-fibo [n]
    (letfn [(fib
                [current next n]
                (if (zero? n)
                    current
                    (recur next (+ current next) (dec n))))]
        (fib 0 1 n)))

The recur-fibo will not consume stack as it calculates Fibonacci numbers, and can calculate Fib(N) for large N if you have the patience.

Philip

[Reinier Zwitserloot]

Implicit tail recursion (Where it's done anytime it looks like it is possible, vs. where it is only done if explicitly requested by the programmer) is not worth it. The actual number of recursive functions out there today is vanishingly small (though in these kinds of: 'Let's see what's out there now' approaches, there's always a bit of the tail wagging the dog: It is likely that more recursive functions would exist in the larger java ecosystem if TCO was part of the JVM!)... and it's not just a matter of realizing you can toss the current stack frame entirely right before jumping to the next method in line (or, as is usually the case, the same method, recursing):

* The stack trace is going to get completely screwed up. There will be an unexplainable break in the flow, where line X+1 of the stack trace is pointing to a call to a method that is _NOT_ the method on line X of the stack trace. What's actually happening is that there are a number of calls that have been ejected due to TCO. The last progress on JVM TCO still tracks these even across TCO jumps so that the stack trace is sensible. However, this does mean that, with this approach, you do eventually run out of memory anyway, because every TCO jump still has to keep track of a StackTraceElement. One easy way out is to make it explicit, both in that the programmer has to request it, and that the previous stack trace is marked as involving TCO when a TCO jump happens, so that in a stack trace you at least _SEE_ why there is a break in flow there.

* Resource Management (i.e. try/finally blocks) instantly kill TCO. The requirement that some method remains TCOable is a gigantic pain in the behind for code maintainers.

* The actual mechanics of writing a method that is TCO-able is complicated and not something the average java programmer understands. Why is 'return x;' TCO-able, but 'return x + 3;' isn't? This is not particularly hard to pick up, but, it's an entirely different can of worms that java programmers do not currently have to know about. Functional languages lack a bunch of baggage that java does have, but as java is not going to just take away features, adding this increases the total size of what you need to know to understand java. This is very bad.

My personal opinion on TCO is that it is an academic boondoggle that nobody needs and only functional junkies care about, but then I'm tempering that rather arrogant opinion based on the fact that I've never managed to really get into the functional mindset, so maybe I just haven't seen the light yet. Still, rewriting a recursive method into a loop-based construct with i.e. a stack is so trivial, I just don't understand why people consider TCO to be such a big deal.

As far as I know, TCO is not currently being worked on by Oracle for roughly the same reasons: It is not at all trivial, some awkward questions need to be answered, and the costs just don't seem worth it in the slightest. The primary reason work was done in the first place was to support other languages on the JVM better, which is a very valid reason to do it (as I tried to mention in the last point, in java TCO is a silly idea but in many other languages it's a key part of the language, and it would be nice if these languages don't have to hack together a class file that emulates it).

[Ben Schulz]

Am Sonntag, 22. Juli 2012 06:52:02 UTC+2 schrieb Reinier Zwitserloot:

My personal opinion on TCO is that it is an academic boondoggle that nobody needs and only functional junkies care about, but then I'm tempering that rather arrogant opinion based on the fact that I've never managed to really get into the functional mindset, so maybe I just haven't seen the light yet. Still, rewriting a recursive method into a loop-based construct with i.e. a stack is so trivial, I just don't understand why people consider TCO to be such a big deal.

Guy Steele posted a nice essay on why rewriting it using loop-constructs is not trivial and why TCO is such a big deal (and frankly more than an optimization). It was originally posted on the Project Fortress blog [1], but that's no longer around. You can still find it in the archives [2], and then there's the always valuable discussions over at LTU [3].

[1]: http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion
[2]: http://wayback.archive.org/web/*/http://projectfortress.sun.com/Projects/Community/blog/ObjectOrientedTailRecursion
[3]: http://lambda-the-ultimate.org/node/3702

[Kevin Wright]

On 22 July 2012 05:52, Reinier Zwitserloot <rein...@gmail.com> wrote:

Implicit tail recursion (Where it's done anytime it looks like it is possible, vs. where it is only done if explicitly requested by the programmer) is not worth it. The actual number of recursive functions out there today is vanishingly small (though in these kinds of: 'Let's see what's out there now' approaches, there's always a bit of the tail wagging the dog: It is likely that more recursive functions would exist in the larger java ecosystem if TCO was part of the JVM!)... and it's not just a matter of realizing you can toss the current stack frame entirely right before jumping to the next method in line (or, as is usually the case, the same method, recursing):

It's not just the methods, it's the data structures.  For example, recursion makes a LOT of sense for iterating over an immutable linked list, and is often one of the first techniques taught within LISP.  The need seems less apparent in an imperative/mutable paradigm, but I think it's fair to predict that we'll see less and less of this style as core counts follow the inevitable curve of Moore's law and as technologies like OpenCL become integrated into the Java ecosystem (NVidia's flagship GTX 690 has 3072 cores, and we're seeing this tech creeping back into CPUs...)

 

* The stack trace is going to get completely screwed up. There will be an unexplainable break in the flow, where line X+1 of the stack trace is pointing to a call to a method that is _NOT_ the method on line X of the stack trace. What's actually happening is that there are a number of calls that have been ejected due to TCO. The last progress on JVM TCO still tracks these even across TCO jumps so that the stack trace is sensible. However, this does mean that, with this approach, you do eventually run out of memory anyway, because every TCO jump still has to keep track of a StackTraceElement. One easy way out is to make it explicit, both in that the programmer has to request it, and that the previous stack trace is marked as involving TCO when a TCO jump happens, so that in a stack trace you at least _SEE_ why there is a break in flow there.

Only if tools are not adapted to show the presence of TCO in a stack trace.  Which seems highly unlikely if this becomes a core JVM optimisation.

 

* Resource Management (i.e. try/finally blocks) instantly kill TCO. The requirement that some method remains TCOable is a gigantic pain in the behind for code maintainers.

Try/finally blocks mess with almost any declarative/parallel technique available.  This is why Scala has `Either`, Haskell has `Maybe` and Akka's futures will trap and return an Exception instead of throwing it. As increasing core counts drive concurrency, we'll see these kind of control blocks changed for other reasons - at around the same time as the growing use of immutable data structures makes recursion (and hence TCO) become a lot more relevant.

 

* The actual mechanics of writing a method that is TCO-able is complicated and not something the average java programmer understands. Why is 'return x;' TCO-able, but 'return x + 3;' isn't? This is not particularly hard to pick up, but, it's an entirely different can of worms that java programmers do not currently have to know about. Functional languages lack a bunch of baggage that java does have, but as java is not going to just take away features, adding this increases the total size of what you need to know to understand java. This is very bad.

Not least, the `return` statement itself.  In almost all function languages the final expression evaluated in a function becomes the return.  More than anything else, I've found this makes it far easier to reason about what can (and what can't) be optimised using tail-calls.

 

My personal opinion on TCO is that it is an academic boondoggle that nobody needs and only functional junkies care about, but then I'm tempering that rather arrogant opinion based on the fact that I've never managed to really get into the functional mindset, so maybe I just haven't seen the light yet. Still, rewriting a recursive method into a loop-based construct with i.e. a stack is so trivial, I just don't understand why people consider TCO to be such a big deal.

Just wait until you're running on 100 cores in your personal laptop, or you begin working very heavily with an asynchronous programming model.  Once you get past that first plateau, this stuff really begins to make some serious sense!

 

As far as I know, TCO is not currently being worked on by Oracle for roughly the same reasons: It is not at all trivial, some awkward questions need to be answered, and the costs just don't seem worth it in the slightest. The primary reason work was done in the first place was to support other languages on the JVM better, which is a very valid reason to do it (as I tried to mention in the last point, in java TCO is a silly idea but in many other languages it's a key part of the language, and it would be nice if these languages don't have to hack together a class file that emulates it).

Quite!  Oracle chose their priorities, and decided (at the time) that a modularisation effort would be more beneficial to the language.  I've never seen them simply rule it out, and suspect it'll get a bit more attention once lambdas arrive.

[Mark Derricutt]

On 22/07/12 11:02 PM, Ben Schulz wrote:
> Guy Steele posted a nice essay on why rewriting it using
> loop-constructs is not trivial and why TCO is such a big deal (and
> frankly more than an optimization). It was originally posted on the
> Project Fortress blog [1], but that's no longer around. You can still
> find it in the archives [2], and then there's the always valuable
> discussions over at LTU [3].
>

Interestingly - I've been playing with Frege ( a Haskell for the JVM )
which compiles its TCO down to while loops - now I just wish I knew
Haskell :)

[Cédric Beust ♔]

On Sun, Jul 22, 2012 at 3:31 PM, Kevin Wright <kev.lee...@gmail.com> wrote:

This is why Scala has `Either`, Haskell has `Maybe`

Not Maybe, it's called Data.Either in Haskell as well.

-- 

Cédric

[Reinier Zwitserloot]

I find it absolutely hilarious that you mention linked lists in the same breath as the need to work with multicore processors. You realize that linked lists, by their very nature, are 100% impervious to parallelizing? At least with array lists you can split em up into blocks and hand off each block. Scala and/or functional programming aren't some sort of magic faerie dust that makes everything work just peachy in multicore world. Splitting jobs at the highest of levels, there's your magic faerie dust. Fortunately it's something your web servlet dispatcher is probably already doing for you. Yay for frameworks.

On Monday, July 23, 2012 12:31:44 AM UTC+2, KWright wrote:

It's not just the methods, it's the data structures.  For example, recursion makes a LOT of sense for iterating over an immutable linked list, and is often one of the first techniques taught within LISP.  The need seems less apparent in an imperative/mutable paradigm, but I think it's fair to predict that we'll see less and less of this style as core counts follow the inevitable curve of Moore's law and as technologies like OpenCL become integrated into the Java ecosystem (NVidia's flagship GTX 690 has 3072 cores, and we're seeing this tech creeping back into CPUs...)

 

Only if tools are not adapted to show the presence of TCO in a stack trace.  Which seems highly unlikely if this becomes a core JVM optimisation.

This kind of complication is exactly why it's not worth it. It's not a simple matter of finding 'blank' calls into another method and replacing the subroutine call with a 'ditch my frame, then goto' approach.

 

 

* Resource Management (i.e. try/finally blocks) instantly kill TCO. The requirement that some method remains TCOable is a gigantic pain in the behind for code maintainers.

Try/finally blocks mess with almost any declarative/parallel technique available.  This is why Scala has `Either`, Haskell has `Maybe` and Akka's futures will trap and return an Exception instead of throwing it.

Yet more distracting bullpucky on how parallel programming is somehow forcing us into doing entirely different things. try/finally isn't going away - resources need managing, period. There's no link between TCO and parallelism, no matter how much you try to make one. Languages which traditionally have looked at the functional approach have also tended to like TCO. Similarly, recursion is still completely irrelevant here. If I want to, for example, optimize the ability to let's say determine the maximum value in a list (using multiple cores), I'd write something like:

int maxVal = myList.par().reduce(Aggregates::max);

two observations:

(A) What in the flying blazes does this have to do with recursion and TCO?

(B) I sure hope that myList is NOT a linked list, because if it was, performance is going to suck.

Do you have clue as to why a linked list is just end of the line, performance wise? How crazy you sound here? The tracker objects of a linked list are just _HORRIBLE_ from a modern CPU architecture point of view, and any data structure which can only be traversed accumulation style is the WORST possible thing you could ever have for a parallelism point of view. It needs to be trivially easy to take any given data structure and split it into X roughly equal pieces. Assuming each piece is itself such a data structure, you can hardcode X to any value you please so long as it is larger than 1. For example, a conclist is trivially splittable into 2 roughly equally sized conclists. To parallelize a job on a conclist, you check if you are the singleton or void list and return the appropriate number, and if not, you ask your left child to go figure out the answer for itself in a separate thread, and then you ask the right side to go figure out the answer in this thread, then when that returns you wait for left, and then you can trivially provide an answer. conslists (i.e. LinkedLists) are not trivially splittable into 2 batches. They are therefore stupid, from a parallelism perspective.

 

Not least, the `return` statement itself.  In almost all function languages the final expression evaluated in a function becomes the return.  More than anything else, I've found this makes it far easier to reason about what can (and what can't) be optimised using tail-calls.

Yes, you are a scala junkie. No, this STILL doesn't mean that the rest of the java community thinks like you. Which part of: The current crop of java programmers do not think like you, and do not understand what is and is not TCO-able, is hard to understand?

[Kevin Wright]

This is a straw-man argument.

Yes, it's true that a linked list isn't inherently parallelisable, and yes it's not the the structure I'd choose if I wanted to use as many cores as possible when sorting a single list, or converting it to uppercase, etc. etc.  As a counterpoint, many fork-join approaches can benefit from TCO, and fork-join *is* an effective technique for performing parallel operations within a single data structure.

But even in a highly concurrent application, linked-lists can make sense when working with a great many of them.  It's a particularly lightweight and *immutable* structure, which makes it especially suited for passing around between threads/actors/whatever.  If I'm serving up the same list of names to two web clients, and one of them wants it converted to uppercase, then there's no risk of accidentally mutating the list that the other client wants.  Nor do I have to worry about ConcurrentModification exceptions - so I'm also avoiding a try/catch block.

I'm reminded of the oft-quoted example about adding people to a project: "You can't use 9 women to make a baby in one month".  This is true, but it's also a perfect textbook case of what to do if you want to make as many babies as possible within 9 months...

*none* of this is specific to Scala of course.  It's not even specific to functional programming per-se, as both immutable structures and recursion are useful techniques even if you don't have functions as first class entities (the reverse isn't true, I'd find it hard to do functional programming without immutability).  The single-entry-single-exit principle that you malign as being the product of a "Scala Junkie" was first established in the 60s, as part of Dijkstra's structured programming, though I'm not lost on the irony that structured programming really came to light with his famous "goto statement considered harmful" letter, whereas TCO is typically implemented as a goto (behind the scenes though, where it isn't harmful).

p.s. A immutable linked-list is just a series of "cells", each one holding a value and the rest of the list.  All except the last one.  Unless your mention of "tracker objects" is simply a synonym for these tail objects, then I suspect you may have misunderstood how the structure is implemented.

--
You received this message because you are subscribed to the Google Groups "Java Posse" group.

To view this discussion on the web visit https://groups.google.com/d/msg/javaposse/-/DRqmKhIqs44J.

To post to this group, send email to java...@googlegroups.com.
To unsubscribe from this group, send email to javaposse+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/javaposse?hl=en.

--
Kevin Wright
mail: kevin....@scalatechnology.com
gtalk / msn : kev.lee...@gmail.com

quora: http://www.quora.com/Kevin-Wright

google+: http://gplus.to/thecoda

twitter: @thecoda

vibe / skype: kev.lee.wright

steam: kev_lee_wright

"My point today is that, if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent": the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger" ~ Dijkstra

[Kevin Wright]

blast! You're quite right of course.  This is clearly a wake-up call that it's been far too long since I last did any Haskell coding :)

[Reinier Zwitserloot]

No, _THIS_ post is a strawman post. You jump from cliche to cliche without explaining how these cliches are in any way relevant to TCO. What the heck does the '9 pregnant women can't produce a baby in 1 month' schtick have to do with TCO? What does 'goto considered harmful' have to do with any of this? Neither scala nor java has gotos, so.... huh?!?????

You're just naming random programming koans here.

On Monday, July 23, 2012 9:27:33 AM UTC+2, KWright wrote:

p.s. A immutable linked-list is just a series of "cells", each one holding a value and the rest of the list.  All except the last one.  Unless your mention of "tracker objects" is simply a synonym for these tail objects, then I suspect you may have misunderstood how the structure is implemented.

Have a look at the implementation of java.util.LinkedList. 1 tracker object per cell.

I suspect _you_ may have misunderstood how the structure is implemented.

 

[Ricky Clarkson]

Now, now, children.  It's clear to this bystander that Reinier's 'tracker object' is the same as Kevin's 'tail object'.  It's also clear that there's nobody on this list/group who doesn't know what a linked list is so there's no real need to accuse each other of that.

--

You received this message because you are subscribed to the Google Groups "Java Posse" group.

To view this discussion on the web visit https://groups.google.com/d/msg/javaposse/-/708D8_CoHygJ.

[Kevin Wright]

Not entirely so!

The "tracker" is another level of indirection, purposely added to the structure with the intent of making it mutable.

I'm quite sure that I was referring to immutable linked lists.  Immutability isn't simply mutability with extra runtime exceptions, when a framework is built with immutability at it's core it works very differently.

The only place I know that does this in Java (the Lang) is joda time. Even guava lies by claiming that an immutable list is a subclass of a mutable one.

[Ricky Clarkson]

Mutability in a singly linked list does not require any extra objects or fields.

Another example of immutability-first, http://functionaljava.googlecode.com/svn/artifacts/3.0/javadoc/fj/data/List.html and its nested mutable counterpart, Buffer.

[Kevin Wright]

Hmm, Last I looked at the java LinkedList implementation, a LinkedList<E> comprised a number of Entry<E> nodes, each of which contained an element of type E, plus previous and next pointer.  So the Node types are distinct from the containing List type.

But you're quite right, a (Singly) Linked List could be implemented with a mutable tail, although that would prevent the data sharing that's one of the more useful properties of the structure.