Tables

[Mark S. Miller <mark>]

Date: Tue, 17 Oct 89 13:36:43 PDT
   From: heh (Hugh Hoover)

     I've got a new table hierarchy laid out (in Smalltalk) and I thought I'd
   present it for criticism (or awe :->) before finalizing it.
     There are 2 main abstract classes:
   CLASS(ROTable,Heaper)
   CLASS(Table,ROTable)

   and 2 sort-of abstract:
   CLASS(SEFTable,ROTable)
   CLASS(TableView,ROTable)

   ROTable is Read-Only Table.  It provides basic read access protocol.
   Table is your basic TableBang - it adds write protocol.
   SEFTable is Side Effect Free Table.  It is ReadOnly with the additional
					constraint of not being side-effectable.

Looks real good.  EVERYONE: Please come up with better names than
ROTable and SEFTable!  Now is the time!  Remember the old Xanadu
tradition: "Don't abbreviate, pun".  Just think of our denigrator's
potential slogan: "Xanadu's type system is rot-able" ;-]

Heh, please include a "coordinateSpace()" message in ROTable, and have
all keys be of type "Position" instead of type "Heaper".  In order to
make this work, you'll also need to define the class HeaperAsPosition
(as we've discussed).  Would it be appropriate to make Orgl a subclass
of ROTable?  If so, then old orgl functions like addressMap, orglMap,
dataMap, etc. could just be TableViews of Orgls.  An example of where
type checking by languages is far from adequate is that it'd be nice
to automatically have a TableView of a SEFTable itself also be
SEFTable, but a TableView of a nonSEFTable is just ROTable.  This
would all go a long way towards implementing the protocol reduction we
all talked about!  Congratulations and thanks.

   In addition to having the standard access routines, tables will also respond
   to a run protocol, where a run is defined as:
   a Charming sequence of equal objects.

   Charming is our (weak) definition of contiguous - ask MarkM or Dean for
   details, but for all our early purposes, it works just fine.

Charming is actually stronger than contiguous, in that all charming
sets are contiguous, but not all contiguous sets are charming.
Charming is formally the property that, given a set S of elements and
a partial ordering over S, a subset of S called R is charming iff

for all X, Y, Z in S, if X, Z are in R, and X <= Y <= Z according to
the partial ordering, then Y is necessarily in R.

Note that for full orderings, charming and contiguous are identical.
We use the above definition of charming for basic coordinate spaces
where S is the basic coordinate space type, X, Y, Z are positions in
that coordinate space, and the partial ordering is defined occording
to how the positions (which are necessary instances of
PartiallyOrdered, since the coordinate space is basic) respond to
the "isGE" message.  We extend the notion of Charming to
multi-dimensional coordinate spaces as follows:

A subset R of a coordinate space S is charming if S = Sa X Sb, and R =
Ra X Rb, and Ra is a charming subset of Sa, and Rb is a charming
subset of Sb.

Note that we said "if" above, not "iff".  The above is a sufficient
condition for multi-dimensional charm.  It isn't necessarily
necessary.  Whether it is a necessary condition is left unspecified
until we figure out what all we're doing with charm, and what we need
it for.  Note that, if we do decide that it's necessary, then a
rectangle lined up with the X/Y axes would be charming, but circles,
and non-aligned rectangles would not be.

For those mathematicians among you, is there a mathematical definition
that's close to charming?  What do mathematicians use it for?

Charm was orginally defined to serve as a defining property for
regions.  It is now similarly proposed as a defining property of
enclosures.  For either of these there is controversy, as I can't make
a clear case as to why I want to impose this seemingly arbitrary
restriction.  The intuition is that charming regions of basicSpaces
can fully described by describing their upper and lower bounds (yes,
plural.  Also whether each is inclusive or exclusive), and that
charming regions of compositeSpaces can be described in terms of
charming regions of the component spaces.  Admittedly, this may be an
arbitrary restriction to impose on regions or enclosures.  However, IT
IS EXACTLY WHAT I THINK WE MEAN BY A RUN!

Q: What is the difference between Xanadu and pantyhose?

A: In Xanadu, runs are charming.