[1576] in java-interest
Re: Java implementations should be tail recursive
daemon@ATHENA.MIT.EDU (John D. Ramsdell)
Fri Sep 8 09:09:08 1995
To: James C Deikun <jcdst10+@pitt.edu>
CC: java-interest@java.sun.com, ramsdell@mitre.org
In-reply-to: Your message of "Wed, 23 Aug 1995 02:41:13 EDT."
<Pine.3.89.9508230259.B27946-0100000@unixs2.cis.pitt.edu>
Date: Fri, 08 Sep 1995 06:07:45 -0400
From: "John D. Ramsdell" <ramsdell@linus.mitre.org>
I've studied Sun's implementation of the Java virtual machine. It
seems possible to make the implementation tail recursive without too
much hassle. See if you agree.
Recall that in a tail recursive implementation, a method invocation
that immediately precedes a return is replaced with an optimized
method invocation that does not push a stack frame onto the control
stack. The invoked method returns not to the invoking method, but
directly to the method that created the parent frame of the invoking
method.
When implementations are known to be tail recursive, programmers can
write efficient routines the directly reflect the structure of the
algorithm. For example, let the class Pair be the obvious class used
to implement lists as linked lists of pairs, with method first() for
obtaining the first element in the list and method rest() for
obtaining the rest of the list. In a tail recursive implementation,
the predicate for deciding if two lists are the same can be written in
this straightforward way:
private static boolean pair_same(Pair p0, Pair p1) {
if (p0 == null)
return p1 == null;
else
return p1 != null
&& p0.first().same(p1.first())
&& pair_same(p0.rest(), p1.rest());
}
In the current Java implementation, efficiency concerns motivate the
transmogrification of the routine into the following form:
private static boolean pair_same(Pair p0, Pair p1) {
for (;;)
if (p0 == null)
return p1 == null;
else
if (p1 == null || !p0.first().same(p1.first()))
return false;
else {
p0 = p0.rest();
p1 = p1.rest();
}
}
James C Deikun speculated that security is the reason the current Java
implementation is not tail recursive. He worried that stack frames
needed for making security decisions could be popped prematurely.
My study of Sun's implementation reveiled that the stack is scanned
while making security decisions. A thread is untrusted, and therefore
subject to different access privileges, if its control stack contains
a frame used to load code from the network by a special class loader.
Since this loader is trusted code, one can reliably write it in a way
that will ensure its frame stays on the stack when it should. It
seems that security requirements do not preclude tail recursive
implementations.
Let me suggest a way of creating a tail recursive implementation
without adding instructions other than five pseudo instructions. The
idea is to add the following five pseudo instructions:
Tail Recursive Instruction Original Instruction
-------------------------- --------------------
tailinvokevirtural_quick invokevirtural_quick
tailinvokevirturalobject_quick invokevirturalobject_quick
tailinvokenonvirtual_quick invokenonvirtual_quick
tailinvokestatic_quick invokestatic_quick
tailinvokeinterface_quick invokeinterface_quick
During the rewriting of the instructions invokevirtural,
invokenonvirtural, invokestatic, and invokeinterface, into their quick
forms, the interpreter would check the next bytecode. If the bytecode
is some form of return instruction, the tail recursive versions of the
pseudo instructions would be used, otherwise, the original versions of
the instructions would be used. The bytecode compiler might have to
be changed so as to ensure that a return instruction directly follows
every method invocation which is a tail call.
The interpretation of a tail recursive invocation instruction would be
very similar to its original invocation instruction. The difference
would be that, rather than calling the procedure that is in the
invoker field of a methodblock, the tail recursive version would call
the procedure in a new field of a methodblock called the tailinvoker.
The contents of the tailinvoker field would be identical to the
contents of the invoker field except in the case in which the invoker
field contains invokeJavaMethod (from classruntime.c). Instead it
would contain tailinvokeJavaMethod, which instead of pushing a new
stack frame, would simply reshuffle the stack.
Does this appear to be reasonable approach to creating a tail
recursive implementation?
John
-
Note to Sun employees: this is an EXTERNAL mailing list!
Info: send 'help' to java-interest-request@java.sun.com
