Can topes be fast?

["J. A. Durieux" <xerox@cs.vu.nl>]

U> Date: Fri, 7 May 93 12:06:09 -0700
U> From: William Clinger <will@skinner.cs.uoregon.edu>

U> ... reading Durieux's original posting ...

OOPS!  I hope I have not offended anybody by using first names in
addressing.  English is not my native language, and I am accustomed
to the rule that the way one signs off is the way one wants to be
addressed.  So I addressed Mr. (or Ms.?) Jaffer as "Aubrey", and
possibly did the same to others.  Now I see that is not necessarily
a valid assumption in a foreign language and culture.  Please accept
my apologies!

U> Durieux's proposal features automatic dereferencing ...

Yes, my proposal is top-level dereferencing of at most one step (i.e.
no nested dereferencing, hence the "1" in "untope1") internally, and
one-step dereferencing at all levels (e.g. the car of a list) for
output, so that no topes are visible in the output in classical cases.

A classical case, or program, is one that corresponds to a case or
program that may occur in current Scheme.

I> Output is in general untope1-ed at all levels before printing, as are
I> arguments to primitive functions like + and substring.

In many cases, untope1-ing at top level suffices, depending on what the
primitive procedure actually does.

U> [..show how for a simple loop many untopes are needed..]

U> Each execution of this loop requires 11 calls to (UNTOPE1) in
U> Durieux's interpreter, plus 6 calls for the base case.

[My interpreted didn't need DETOPE, merely UNTOPE1, but I had forgotten
to change this before I sent my code out - sorry.
(define (untope1 arg) (if (tope? arg) (untope arg) arg)))]

Actually, the required number is a little less, since I untope argument
lists, which is only necessary in case of a call to "apply", but that's
not the point.

My thesis is, that this untoping does not cost anything extra.

To find an object (given a variable location, a half cell, a vector unit,
etc.) one needs either zero, or one, or more than one untope.

The case of more than one untope does not occur in classical programs,
so it need not be fast to compete with current Scheme.  My proposal is,
that at most one untope is performed, and that if the result still is
a tope, this tope is to be taken as the intended argument.  If one
wants to dereference further, one will have to code this explicitly.

This leaves the case of one and zero untopes.  In classical programs,
only the one-untope case occurs, the location where the pointer (or
direct representation) is stored being mutable, i.e. a tope.

Tope-Scheme must be able to deal with both cases, but this comes
automatically: even if, theoretically, there is no tope, there still
is the physical location where the pointer or the direct represen-
tation is stored.  So the interpreter simply takes the contents of
this location, without bothering whether this location represents
a tope or not.
I suppose a bit "mutable" associated with the location will have to
be ignored, but while I know next to nothing about low-level
programming, I suppose this can be done fast.

There is a performance hit associated with set!, since it has to
check for the bit, but if this bit is part of the type tag for topes,
there would be no problem here, either, except that in a compiler
dynamic type testing would be necessary, as it is now for e.g.
set-car!.


Does this make sense?  I have not programmed this out for myself, so
it may be that I overlooked some serious flaw somewhere.


U> For those of you who might want to run Durieux's interpreter, watch out
U> for the unquoted empty lists and the assumption that SET! returns the
U> new value of the variable being assigned.

Yes.  Accepting unquoted () was done because I believe in evaluating to
oneself.  Having set! return the new value was a hack; if I hadn't done
that, I would have needed sequences in lambda bodies to define recursive
functions (see your example, or mines at the end of my interpreter), and
I wanted to keep the code minimal.

I now realise that 
(1) I also rely on () evaluating to itself in the underlying Scheme, and
(2) by replacing set! by a function, my hack now depends on vector-set!
    returning the new value in the underlying Scheme.
Both problems are trivial to repair, though.
Thanks for pointing them out!

                                                   Biep Durieux