Re: java & tail recursion

Thorsten Altenkirch <alti@tcs.informatik.uni-muenchen.de> writes (in comp.compilers):
> Can anybody tell me whether there are any java compilers which do tail
> recursion optimisation.
> I.e. the following program should not lead to a stack overflow (or
> memory error) for large n
>
> public class RecTest {
> static int ct=0;
> static void f(int i) {
> ct++;
> if(i<=0) return;
> f(i-1);
> }
>
> public static void main(String [] args) {
> int n=Integer.parseInt(args[0]);
> f(n);
> System.out.println(ct);
> }
> }
>
> The jdk compiler certainly doesn't optimize. A quick web search on
> "java" and "tail recursion" returned a pointer to an old discussion in
> comp.compilers with the result that it should be possible.


Ah yes, the lack of support for tail calls in the JVM continues to
grieve the functional language community and other proponents of
sensible languages (of which I'm one).


I believe if you use the IBM JIT JVM you will get the desired tail
recursive behaviour (though I haven't tried it myself.) In other
words, the support is in how the JVM instructions are translated into
native machine code instructions. There was an overview article about
this JIT in IBM Systems Journal, vol 39, no 1, 2000 (the entire issue
is about Java, available on the web somewhere, I forgot exactly where,
presumably on some IBM page) It isn't clear if general tail calls are
supported (My guess is that they might if inlining happens to turn it
into the *tail recursion* case).


There has been some discussion in comp.lang.java.machine about tail
recursion and Java / JVMs in the past som I'm cross-posting.


I'd be very interested to hear from the IBM JIT team to confirm or
deny this! (Or from anyone else for that matter.)


--Thomas Johnsson

Return to the comp.compilers page.
Search the comp.compilers archives again.