Set & Table hierarchy

[Mark S. Miller <mark>]

Date: Thu, 9 Nov 89 10:33:36 PST
   From: ravi (Ravi Pandya)

   ...

   ISSUES:

   (1) The ImmuSet class in the previous message is really Predicate,
   since with a non-enumerable set, all you can do is test for
   membership.  Having the abstract superclass doesn't get us any useful
   polymorphism: Region->union(Region) should be a Region, and
   ESet->union(ESet) should be an ESet, etc.

   We could put Sets and Regions under Predicate, and Tables and Dsps
   under UnaryFn, but again I don't think that having the abstract
   superclass gets us any useful polymorphism. It would also mangle the
   names of set combination messages. (and=intersect, implies=subset, ...)

Agreed.  It seems (as we discussed before) that UnaryFn and Predicate
can both be declared obsolete.  (The only exception to this would seem
to be the use of Predicates within the backFollow-to-links protocol,
so we should reexamine this protocol.)

   (2) Note that scrutables don't have any protocol for changing
   themselves.  In order to do so, you have to make a decision as to
   whether they are going to to be mutable or immutable. I would like to
   hear what you think about this policy.

Previous message about "+=".  Sorry that that message didn't take the
above paragraph into account (I forgot).  I think that leaving this
protocol out of Scru's is appropriate, and the messages should look
very different for Mu's and Immu's (being a distinction analogous to
that between + and +=).

   (3) The complete separation of immutables from scrutables & mutables
   was due to MarkM. He felt that immutables are purely mathematical
   objects, while the uses of S&M's are bound to be dominated by the fact
   that they have state. The former would be used when the important issue
   is membership, the latter when the issue is reference or containment
   (as in dependency models).

   I find that the original argument for having immutables and mutables
   be subclasses of scrutable is still compelling. I think that this is a
   case where the abstract superclass really does buy you something. Both
   mutables and immutables can take scrutables as arguments to messages
   like intersect(), since all they need is to be able to find out the
   contents of the other object.

Mumble.  Let's go with these being polymorphic for now.  We can then
look later to see what use we've made of this polymorphism.  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.  Kind of a ScruOrgl (as opposed
to Orgls which would be considered an ImmuOrgl).  Do you think this
would be a reasonable thing to do with Orgls & Berts?  It may be that
I just think it's silly because I'm stuck in an old way of thinking
about these.

   (4) Clearly, we don't want to have three different implementations of
   every kind of Set & Table -- scrutable, mutable, and immutable. MarkM
   suggested implementing mutables in terms of immutables with the use of
   copy-on-write. This is counter to my intuition that the basic
   implementation should be mutable, since that is most efficient.

   You can make a scrutable out of a mutable by simply casting it to the
   superclass, thereby hiding all the protocol to change it.

Agreed.  All implementation classes are Mu's.

   If an immutable can know that it is the only one pointing at its
   mutable, and that there is only one pointer to itself, then it can
   simply change the mutable. Otherwise, it makes a copy of the mutable,
   changes it, returns a new immutable pointing to that.  I don't believe
   that this runs into any of the immediate finalization problems that
   the other copy-on-write scheme does.

If there is a pointer to the ImmuTable, then it cannot "simply change
the mutable(sic)".  What if someone accesses that same ImmuTable
through that one pointer?  I also don't see how this would avoid any
immediate finalization problems.

   Thus scrutables are pure abstract classes, and ImmuTables and ImmuSets
   are concrete leaf classes holding onto a mutable. All actual
   algorithms and data structures are in mutable subclasses.

Yup.  Looks good.

   (5) Dsps and regions are defined to immutable and have copy-on-write
   built into the algorithms. This corresponds to what I think will be
   the actual usage, both formally (they are mathematical objects) and
   practically (they will be used a lot, so efficiency really matters).

Agreed, but terminology quibble.  You can't write an Immu structure.

   Well, I think that is enough for one mail message. The next one will
   about the issues that are still unresolved. There aren't many!
	   --ravi

Yes, congratulations!  The convergence of all this stuff is very
encouraging.  By having the Orgls & Berts/Hand/Waldos stuff eventually
converged with X++ Tables etc... then, when we open the Orgls&Berts
layer to our users, it'll also be useful as a high class Table server.
As I've discussed with Dean, I don't think we should try to make these
actually converge in a strong sense (e.g. Orgl be a subclass of Table)
for first product.  However, we can evolve their protocol to be more
and more similar to each other incrementally as a way of exploring the
hypothesis that they should converge.