Inheritance Styles (was "Question on Array semantics")

[Mark S. Miller <mark>]

Abstract: Our Table system is taken as opportunity to pontificate
about types as contracts and the proper use of inheritance in
object-oriented programming.  I also recommend some reconception of
our Table system (without any significant changes to the code).



   Date: Thu, 16 Nov 89 15:07:46 PST
   From: heh (Hugh Hoover)

   An Array is defined to have an integer coordinate space starting at zero,
   and is constrained to have no empty space (i.e. get() for a legal key will
   always succeed).

Quibble: this is meaningless until you say what you mean by "legal".

     Because of the constraint, I believe that remove() and wipe() should blast
   for Arrays - otherwise you could end up with an improperly formed Array.
   Also, any introduce must occur at the current upper bound (the position one
   past the last filled-in element).  (BTW a create (construction) of an Array
   with a specified size (say 10) does imply the upperBound is at that size,
   the last filled element defines the upperBound).

   I'm implementing with these assumptions - any disagreements?

   --Hugh

In rereading this, I find I'm confused over what you mean by "upper
bound".  Do you mean the maximal position that is currently filled in
for a given array, or the maximum position that *may* be filled in?


During a conversation I had with Dean, Ken Kahn, and Udi Shapiro last
Tuesday the issue of proper inheritance style came up.  Ken was
advocating a code-sharing view of inheritance.  Dean & I were
advocating a strict subtyping view.  We claimed (correctly I believe)
that it is the case without exception that in *all* the code we've
written at Xanadu, if A is a subclass of B, then A's contract/protocol
is strictly upwards compatable with B's contract/protocol.  This is an
important constraint, as satisfying A's contract is what we mean when
we say that an object is a "kind of A".  If everything that is a kind
of B is also a kind of A, then strict upwards compatability follows.

It is this strict upwards compatability that gives compile time type
checking value in object oriented languages--it says what assumption
are being made by a client that specifies "A *" of something he's
interacting with, and guarantees that these assumptions are satisfied
if B correctly fulfils the A contract.

It wasn't until that conversation that either of us noticed just how
rare actually sticking to this principle is among object-oriented
programmers.  I think much of the power and simplicity of our code
derives from our strict adherence to this principle.  I would say that
our code demonstrates that this is good practice (especially in
contrast to the SmallTalk-80 libraries), and that one can painlessly
stick to this principle without exception in writing a pratical
realistic large system.  This is also something to emphasize when
explaining our code--once the reader knows he can universally count on
this contraint, understanding and using existing code becomes much
simpler.  I would speculate that this practice isn't common mostly
because compile time type checking hasn't historically been common
among object oriented programmers.

None of this implies any change to the Array design above.  However,
it requires us to be careful about what we consider to be the contract
associated with the type "MuTable".  The way we (or at least I) *had*
been considering the definition of MuTable, a "store" of any key-value
pair in which the key is a position in the appropriate coordinate
space would necessarily succeed, with resulting constraints on the
behaivior of "fetch" (that "fetch" would return the most recently
"store"d value for a provided key).  This is not true of Array::store,
because the array feels free to reject "store"s to a key that is
outside its bounds (to prevent holes in the Table's domain).  If the
Array does accept the store, then all the MuTable obligations on
resulting behavior do still follow.

The behavior of WordArray::store is even more restrictive.  Here a
"store" that would have been acceptable to Array can be rejected
because of an innapropriate range element.  Unless we reconceive what
we're doing, MuTable-Array-WordArray will become a specialization
hierarchy instead of a subtyping hierarchy.

Pavel's thesis at PARC on a type system for a strongly typed SmallTalk
suggests that perhaps we want to invert the subtype hierarchy--since
MuTable::store is upwards compatable from Array::store, which is in
turn upwards compatable from WordArray::store.  What you would then
get is subtyping relationships that form an inverted hierarchy (the
speciallization hierarchy upside down).  Besides the fact that we
can't do this without multiple inheritance, I now think that it
wouldn't be appropriate anyway.

If we just look at the contract for "store", then Pavel's inverted
hierarchy seems plausible.  However, Array does define a new
contractual obligation that is not in MuTable's contract, and so
MuTables are also not upwards compatable from Arrays.  The new
obligation of anything that is a kind of Array is that one's integer
domain must have no holes, and span from zero upwards.  A MuTable with
an integer domain doesn't necesarily satisfy this requirement, as a
kind of MuTable is perfectly allowed to have holes in its domain.  (An
individual MuTable instance may happen to satisfy the Array contract.
However, being a MuTable doesn't itself *obligate* one to.)

Therefore, the same "no holes in domain" clause would seem to argue us
into both "MuTable is a subtype of Array" (because of "store"
behavior) and "Array is a subtype of MuTable" (because of "fetch"
behavior).  How do we resolve this?  I propose the following
hierarchy:


CLASS(MuTable,ScruTable) {
	In addition to ScruTable's contract, a MuTable must provide a
set of change messages (like "store").  A MuTable is allowed to BLAST
in response to any of these messages, or to accept any of these
messages (given that certain other preconditions are satisfied, e.g.,
for "introduce").  (Acceptance is defined by not BLASTing.)  However,
if the MuTable does accept any of these messages, the resulting
obligations on subsequent behavior is well defined.  Note that a
MuTable which BLASTs on all change messages still fulfils its
contract.  (Given this, we may want to consider merging ScruTable &
MuTable.  An EscorTable would then be a ScruTable/MuTable which was
obligated to BLAST on all these change messages.)  
};


CLASS(Array,MuTable) {
	An Array is obligated to only represent contiguous integer
domains starting at zero and proceeding upwards.  It *follows* that an
Array is obligated to reject "store"s that would create holes.  An
Array is not obligated to accept "store"s that it may accept.  It also
follows that an empty array's domain is the interval from 0
(inclusive) to 0 (exclusive).  
};


CLASS(WordArray,Array) {
	The range elements of a WordArray must all be PackOBits of the
same word size as each other.  
I think it is reasonable to require that this wordsize be
pre-specified, that it be available as WordArray::wordSize(), and that
it not change over the life of an individual WordArray.  Given this,
we say instead: 
The range elements of a WordArray must all be PackOBits of the
same word size as this->wordSize(), which doesn't change during the
lifetime of the WordArray.  Any change which WordArray's contract
allows it to accept it must accept.
};


CLASS(NonDiscretionaryArray,Array) {
	Any change message my Array contract allows me to accept I
must accept.  
};


CLASS(NonDiscretionaryMuTable,MuTable) {
	Any change message my MuTable contract allows me to accept I
must accept.  
};
	

ScruTable
    ImmuTable
    MuTable
	Array
	    WordArray
	    NonDiscretionaryArray
	NonDiscretionaryMuTable


Perhaps we don't really have to introduce the latter two type
distinctions.  The main point is to weaken the obligations of MuTable
and Array so our class hierarchy is also a valid subtype hierarchy.
This requires no new code, or even any change to our code.  Just care
in our documentation, and in what properties are being assumed in code
that interacts with something that it only knows to be a MuTable
(since such code must still work when given an Array).


P.S.  I hate the prefix "NonDiscretionary".  Hopefully we can improve
on this term if we indeed introduce these types.


P.P.S.  I think a rigorous notion of upwards compatability is going to
be important in the future for Stubble, so that we can distinguish
which changes to our FeBe protocol are upwards compatable from the
previous release.  It would be especially nice if changes to our
protocol which were upwards compatable in terms of C++ declarations
were also upwards compatable through Stubble without recompiling or
relinking the front-ends.  With the addition Michael's proposal that
Stubble use mangled message names, I believe we already achieve this!
(Indeed, I think this was Michael's motivation in proposing it.)