[852] in java-interest
Re: Java implementations should be tail recursive
daemon@ATHENA.MIT.EDU (James C Deikun)
Fri Aug 11 12:01:57 1995
Date: Fri, 11 Aug 1995 04:39:07 -0400 (EDT)
From: James C Deikun <jcdst10+@pitt.edu>
To: "John D. Ramsdell" <ramsdell@linus.mitre.org>
cc: java-interest@java.sun.com, Pat Niemeyer <pat@icon-stl.net>,
ramsdell@linus.mitre.org
In-Reply-To: <199508101053.GAA03881@goblin.mitre.org>
On Thu, 10 Aug 1995, John D. Ramsdell wrote:
> The key to producing a tail recursive virtual machine is to split the
> action of invoking a method into two pieces. One piece pushes live
> variables and a return address onto the control stack. The second
> piece dispatches to a method without storing a return address. The
> second piece is essentially a goto with arguments.
>
> A non-tail recursive method invocation compiles into a pair of byte
> codes, but a tail recursive method invocation just does the dispatch
> without saving anything into the control stack.
The problem with this, of course, is that without saving the old stack
frame, it's impossible to tell who invoked the new method. This
unfortunately conflicts with many of the security methods that seem to be
used in Java, or with just about any rational sort of security for a
language that can safely and stably allow arbitrary runtime extension of
a system.
> It has long been known how to implement efficient byte code
> interpreters that are tail recursive. The Scheme48 virtual machine is
> an example and it is available at
> <http://www-swiss.ai.mit.edu/~jar/s48.html>. It uses a byte code
> roughly based on that described by William Clinger in "The Scheme 311
> Compiler An Exercise in Denotation Semantics" in the 1984 ACM
> Symposium on Lisp and Functional Programming, pp. 356-364.
>
> Dylan programmers are allowed to assume implementations of that
> language are tail recursive. Being object oriented does not bar tail
> recursive implementations.
Scheme and, as far as I can tell, Dylan, are examples of what I call
'single-producer' languages--that is, they only allow one person or
organization to safely program within a single system. These languages
provide no real way to protect part of a program from other, hostile
parts of the same program. This is fine, mostly, for single-programmer
or small-group projects, but if you're picking up all sorts of libraries
from heaven only knows where, or even if you have a large enough project
that no one person can keep careful track of all the intricacies of the
code, you need something more.
For that, you -need- to keep those stack frames that optimized
tail-recursion throws away.
So, only single-producer languages (which Java is not) can use TRO.
(If you can, pleasee prove me wrong. I love TRO, but it just seems to me
like one of those thingss one must give up.)
--
James "soy milk and vinegar?! NO WHEY!" Deikun
-
Note to Sun employees: this is an EXTERNAL mailing list!
Info: send 'help' to java-interest-request@java.sun.com
