On 22 July 2012 05:52, Reinier Zwitserloot <reini...@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. > > On Friday, July 20, 2012 10:31:31 PM UTC+2, clay wrote: >> >> 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. >> > -- You received this message because you are subscribed to the Google Groups "Java Posse" group. To post to this group, send email to javaposse@googlegroups.com. To unsubscribe from this group, send email to javaposse+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/javaposse?hl=en.
