I'm replying more-or-less randomly to this message among all messages debating whether TCO is a JVM implementation detail or not.
My stance is that it is, in the same sense as GC is. See, memory management is not specified *at all* in the JVM specification. A JVM would be a valid JVM even if it didn't have any GC at all, and thus never reclaimed heap memory, and simply stopped the programs with OutOfMemoryError when it run out of heap. Granted, such a JVM would of course be of limited utility and could only correctly run a subset of programs that terminate normally before they exhaust the allocated memory. If you think a JVM without a GC is absurd, let me tell you that such JVM actually existed about a decade ago - the JVM for the LEGO microcontroller computer didn't have memory management, so you had to take care of working with only a finite set of objects, preferrably preallocated at program startup. It was limited, but as far as I can remember, some schoolkids actually won a NASA competition for a program to be run on a LEGO robot sent to ISS, and they wrote it in Java that run on this JVM. TCO is just the same in my eyes. I believe there should be no changes to the class file format, and the JVM should just optimize tail calls automatically whenever they spot a combination of an INVOKE instruction immediately followed by a RETURN instruction, and are not in a try block. (Mind you, due to the way it is compiled, this'll prevent calls in a synchronized block to be optimized, as synchronized blocks are always in a try although if the whole method has the synchronized attribute, it should be fine). For programs written to assume TCO, only a subset of them terminating before they exhaust the stack will work on JVMs with no TCO. See, this is quite analogous to saying "for programs written to assume GC, only a subset of them terminating before they exhaust the heap will work on JVMs with no GC". If Sun introduced automatic TCO in the JVM that goes in the Java 7 JRE, then programs written with assumption of TCO would just have to specify "requires Java 7" in the same way as programs written with assumption of concurrent collection classes had to specify "requires Java 5" back in the day when Java 1.3 was still widespread. Throwable#fillInStackTrace is indeed a bit of a problem. It would be possible to maintain a "logical" stack trace separate from the "physical" one, but with a deep enough tail recursion, it'd blow memory away. At least for simple recursive call-to-self, it'd be possible to just add a counter of how many times that frame repeats logically; for more complex mutually recursive calls this wouldn't work and the idea of having a pattern-based compressor for stack traces kind of scares me, and you could probably still come up with a pathological example that'd defeat it... Then again, can you imagine really wanting to print a stack trace of a TCOd call chain containing few millions of calls? Maybe it'd be better to alter the specification of stack frame listing instead... Attila. -- twitter: http://twitter.com/szegedi On 2009.04.02., at 18:33, John Cowan wrote: > > On Thu, Apr 2, 2009 at 10:36 AM, kirk <kirk.pepperd...@gmail.com> > wrote: >> why do they have to be exposed? Isn't tail recursion and >> implementation >> detail? And an optimization at that? > > No. > > Being able to rely on tail recursion is not an implementation detail; > Scheme programmers routinely write programs that tail-call heavily and > would blow up without it. A state machine implementation where state > transition codelets, expressed as functions, are tail-called by the > dispatcher and tail-call it in turn is a classic example. "Lambda: > the ultimate goto." > > And since Java exposes the call stack via Exception#fillInStack, the > *presence* of tail recursion is unfortunately not an implementation > detail either. > > -- > GMail doesn't have rotating .sigs, but you can see mine at > http://www.ccil.org/~cowan/signatures --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "JVM Languages" group. To post to this group, send email to jvm-languages@googlegroups.com To unsubscribe from this group, send email to jvm-languages+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en -~----------~----~----~----~------~----~------~--~---
