Re: Topes

[William Clinger <will@skinner.cs.uoregon.edu>]

Oh, fretch.  I apologize for my last message.  References are an old
idea, and I stopped reading Durieux's original posting after its third
paragraph.  I jumped to the incorrect conclusion that Durieux proposed
to add references to Scheme, leaving Scheme's existing assignable
variables unchanged.  No, he proposed to replace assignable variables
with references.

There are basically two ways to add references to Scheme: with or
without automatic dereferencing.  Durieux's proposal features automatic
dereferencing, which is needed if first class references are to subsume
Scheme's existing assignable variables without requiring any changes to
existing programs:

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

The problem with automatic dereferencing is that Scheme is a dynamically
typed language, so the problem of determining which arguments must be
dereferenced is statically undecidable.  Thus a dynamic test is required
to evaluate almost every subexpression.  This is just not practical if
an efficient language is one of our goals.

For example, I defined the following trivial loop:

    (def 'sum
      '((func (sum)
              (set! sum (func (n)
                              (if (zero? n) 0 (+ n (sum (- n 1))))))
              sum)
        (tope 'dummy)))

Each execution of this loop requires 11 calls to DETOPE in Durieux's
interpreter, plus 6 calls for the base case.  This could probably be
reduced through static analysis.  To determine how much it could be
reduced would require some investigation.  Even if the dynamic overhead
could be reduced to zero for typical cases, which I doubt, we are
talking about adding a substantial amount of optimization to Scheme
compilers just to recover the efficiency we already have with the
existing language.  The effort required could go instead toward making
compilers better than they are now.  Are the benefits of references
great enough to justify this major redirection of effort by compiler
writers?

No.

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

William Clinger