[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

Set & Table hierarchy

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

   What do the "mutable" & "immutable" messages to a ScruSet mean?  

I meant them to mean asMuSet and asImmuSet, and I agree that they
should be renamed as such. All three (Mu/Scru/Immu) should be defined
in ScruSet so that they can be used polymorphically.  Likewise for

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

   ....  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.)

We might as well call these Filters, since that is what they are; they
are not general predicates. Specific kinds of filters and ways of
combining them will be available, depending upon what the backend can
do efficiently. The other exceptions is Dsps, which replace UnaryFns,
and are restricted again to operations that are appropriate to the
back end data structures.

      (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 +=).

Agreed.  I think "To" or "Into" seems to have the wrong directionality
(e.g. a->unionInto(b) seems to change b, not a). "With" is pretty
good, except that we already use "unionWith" because "union" is a
reserved word. Other suggestions: Verb vs. noun distinction --
intersect, subtract, unite vs. intersection, difference, union;
Diferent words entirely -- keepOnly, removeAll, mergeAll vs.
intersect, minus, unionWith. 

A related issue is whether Mu's will support Immu protocol as well. I
don't think that they need to -- you can just say

      .... while the uses of S&M's are bound to be dominated by the fact
      that they have state.  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

[Nobody noticed. Too subtle, I guess]

      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

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.


   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.

      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. ....

   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.

You're right, this logic is flawed. There is no circumstance under
which an Immu can avoid making a copy of its Mu.  In which case
finalization is a moot point.

   ....  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.
   ....  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.

I'm not yet convinced that there is much to be gained by the
convergence, especially if we go in the direction of mangling people's
notions of tables & sets to make them more like orgls & berts. Time
will tell.

    Date: Tue, 14 Nov 89 20:47:51 PST
    From: mark (Mark S. Miller)

       Date: Thu, 9 Nov 89 10:43:27 PST
       From: ravi (Ravi Pandya)

       All mutables should implement a copy() message.

    I take it the following equation should hold:

    MuTable * p;

    p->copy() === p->asImmuTable()->asMuTable()


Yes, the two expressions should have the same effect.

       NullSet is a subclass of ScruSet.

    I don't get this?  Why ScruSet?

I just wanted a special class for EmptySet like we have now, and it
should be read-only since it can't be changed. On reflection, it
should probably be Immu (if it's worth doing at all).