New types; also opacity without passkeys

[William D Clinger <will@ccs.neu.edu>]

Michael Blair asked concerning my earlier enigmatic remark:

> >--------------------------------------------------------------------------
> > On the other hand, the need for Blair's optimization would go
> > away if we made a couple of minor changes to his proposal.
> >--------------------------------------------------------------------------
> 
> Since I cannot figure out what minor changes you have in mind, could you
> please be more explicit?  At this point, I'd be willing to agree to almost
> anything.

My thought was that we could get rid of the optional <passkey>.
As our previous conversations have brought out, the <passkey>
provides security only if we also assume that the objects created
by OPAQUE-UP are sufficiently opaque.  If we are willing to make
a slightly different and more abstract assumption of opacity, then
we don't need the <passkey> at all.

I am more interested in the ability to generate new types than
in absolute opacity, so I will illustrate this idea by outlining
a proposal that doesn't explicitly require any opacity. I will
then mention a modification that makes it more similar to Blair's
proposal.

This is essentially the same as the various record proposals that
have been floating around for years, but restricted to records
with a single anonymous field.

MAKE-NEW-TYPE takes no arguments.  The result of MAKE-NEW-TYPE
is not a predicate, but a new type descriptor <type> that is
different from all existing type descriptors.  (This is made
more precise below.)

    (GET-NEW-CONSTRUCTOR <type>),
    (GET-NEW-SELECTOR <type>), and
    (GET-NEW-PREDICATE <type>)

respectively return a constructor U, a selector D, and a predicate P?
that satisfy the following constraints.

Let <object> be any object, and let <object2> be any object that
was not constructed by U.  Let <type2> be the result of a call
to MAKE-NEW-TYPE that is dynamically distinct from the call
that returned <type>.  Then

    (GET-NEW-CONSTRUCTOR <type>) = U       that is, successive
    (GET-NEW-SELECTOR <type>) = D          calls return the
    (GET-NEW-PREDICATE <type>) = P?        same procedures

    (P? (U <object>)) = #T

    (P? <object2>) = #F

    ((GET-NEW-PREDICATE <type2>) <object>) = #F
                                           this forces the constructor
                                           and predicate for <type> to
                                           be distinct from the
                                           constructor and predicate
                                           for <type2>; it also forces
                                           <type> and <type2> to be 
                                           distinct

    (D (U <object>)) = <object>            where the equality is to be
                                           interpreted as EQV?

    (D <object2>) is an error              so implementations are free
                                           to extend the domain of D
                                           to include all objects

Although this proposal does not explicitly require any opacity,
the requirement that the predicate P? returns #T if and only if
its argument was created by a call to U cannot be implemented
without some kind of opacity.  In particular, this proposal
cannot be implemented in R4RS Scheme.

Implementors that don't like opacity could implement this proposal
using the least amount of opacity that allows them to meet the
specification.  Implementors that like opacity could use enough
opacity to permit some serious optimizations.  To each their own.

For example, this proposal allows, but by no means requires, an
implementation to provide a UNIVERSAL-SELECTOR such that

    (GET-NEW-CONSTRUCTOR (MAKE-NEW-TYPE)) = UNIVERSAL-SELECTOR
and
    (UNIVERSAL-SELECTOR
     ((GET-NEW-CONSTRUCTOR (MAKE-NEW-TYPE))
      <object>)
    = <object>

for every <object>.  A proposal similar in spirit to Blair's could
be obtained by requiring a considerably greater degree of opacity.

I believe the opacity required to make this proposal comparable to
Blair's is essentially the same as the opacity required to make
Blair's proposed optimization correct.  I believe the optimization
required to make this proposal efficient is simpler than Blair's
proposed optimization, mainly because this proposal is more abstract
and talks about the essential operations instead of using passkeys
as surrogates for them.  This abstractness allows implementors to
match their implementation of this proposal to the strengths of
their particular compilers, instead of having to change their
compilers to match someone else's idea of what an optimizing
compiler should do.

Will