Set & Table hierarchy

[Mark S. Miller <mark>]

Abstract: Response to various points by Ravi about how to organize &
implement the Table and Set hierarchies.


   Date: Wed, 15 Nov 89 20:11:40 PST
   From: ravi (Ravi Pandya)

      Date: Tue, 14 Nov 89 12:23:56 PST
      From: mark (Mark S. Miller)

	 I find that the original argument for having immutables and mutables
	 be subclasses of scrutable is still compelling. 

      ....  My
      intuition is largely based on the Orgls vs Berts distinction.  It
      would seem silly to me to have Orgl & either {Bert, Hand, or Waldo}
      have a non-trivial common superclass.

   The only way I could see this making sense is if we went whole hog and
   made the state-value separation as thoroughly as in Berts & Orgls. In
   that case, there would be only one kind of Mu (Bert) and all
   implementation classes would be Immu's. The Mu's would only support
   protocol for storing and retrieving their Immu, so you would typically
   do "a->store (a->get ()->intersect (b->get ()))" instead of
   "a->intersect(b)".

   This would be one more oddity about the system that developer's would
   have to learn. It would also complicate the implementation, since
   efficient Immu's require fancy copy-on-write tricks to make them
   efficient (a case in point being your message about backwards deltas
   -- oy vey!). Given the way we are structuring the protocol, with Mu &
   Immu objects that hold comparable data, I think it makes sense to have
   a common superclass for accessing it.

As Dan Ingalls likes to say: "You can cheat as long as you don't get
caught.".  I'm thinking in terms of something like the following
analogies: 

ImmuTable   :   Orgl
MuTable     :   Waldo
Mu (??)     :   Bert or Hand

Notice that MuTables would *seem* to be wrappers of Bert-like-things
onto Orgl-like-things, but could have their own protocol identical to
the current MuTable protocol.  There doesn't actually have to *be* any
Bert-like-thing or Orgl-like-thing underneath until the client does
something for which these need to be shown.  I continue to think that
our plan to have all the implementation classes be the Mu ones is
good, and does not hinder convergence with an Orgls/Berts/Hands/Waldos
model.

Even without this, I don't see how to avoid the trick of
copy-on-write-use with backwards deltas.  Admittedly it is hairy, but
I don't see how any of the alternatives avoids this hair.  This hair
seems fundamental to the whole collection system as we've conceived of
it, independent of whether Immu's are subclasses of Scru's.

Besides, ImmuTable may want to be a subclass of Position.  If
ImmuTable is a subclass of ScruTable, then ScruTable may want to be
a subclass of Position, which seems grossly inapproriate.

Which brings up the question: Should ImmuTable be a subclass of
Position?  If not, what's the representation of a position in a
multi-dimensional coordinate space?

	   ....

      Agreed.  All implementation classes are Mu's.

   Not completely agreed. According to Hugh & Dean, if we use a certain
   kind of Immu a lot (e.g.  a WordVector) it might be more efficient to
   implement an Immu on a "shared" data array with all the sneaky
   copy-on-write tricks. I have very strong suspicions that the
   situations under which you can avoid having to do the copy will be so
   rare, and the contortions you have to go through to make it efficient
   so complex, that it will not be worthwhile.  The first implementations
   are all going to be Mu because it is much simpler.

I don't get this, but as we're agreed that the first implementations
as all Mu, feel free to postpone educating me.  Perhaps our
mis-communication is based on our differing views of the avoidability
of the copy-on-write-use-with-backwards-delta tricks.  Once again, I
am *not* advocating employing these tricks before performance
engineering phase, so this is also postponable.