Inheritance Styles (was "Question on Array semantics")

[Eric Dean Tribble <tribble>]

Abstract: I dislike MarkM's proposal for dealing with specializations
of general abstractions.  I describe a general version of the problem,
and a way of handling it.  Here's a simple description: we want to
have general abstractions *and* optimized implementations for
constrained versions of the abstraction.  Thus, Arrays are linear and
contiguous, while the basic MuTable abstraction requires neither.  I
propose that we accept the concept of specialization, and provide
exception behavior for the cases in which the constraints on the
specialization get violated.  At the end are some specific reactions
to markM's message.
----

Gack!  I shudder to imagine explaining the distinction you suggested
to someone who just wants to use an Array!  At the moment, I prefer to
have a broken class hierarchy.  Here's a fantasy design.  I don't
think we can implement it, but it's good to consider:

The MuTable protocol is defined exactly as now.  All the variants of
MuTable (Array, WordArray, etc.) just implement the MuTable type.
In my fantasy, storing a general object in a WordArray just turns the
WordArray into an Array.  Storing an object such that it makes a
whole in the domain of an Array just turns the array into a general
MuTable.  All the implementation classes become exactly that:
optimized implementations of the MuTable protocol.  

Let me state the problem with Tables in a general form, because it
will bite us in other places.  We want to optimize special and common
cases of some very general and powerful abstractions.  Those special
cases can be characterized by invariants and constraints extending the
protocol of the abstractions.  I think such specialization is
reasonable.

Two solutions:  
1) live with specialized implementations of general types.
2) Find a way to generalize them on the fly if the program violates the
constraints on a given specialization.  

I'm happy with #1 if we use BLAST(SpecializationViolation) in all the
appropriate places.  This actually makes sense.  An algorithm that
uses a specialization (Array, for instance) to optimize typical cases
should understand that it's optimization might not work and be
prepared to switch to a more general representation.  When an
algorithm is supplied with a specialization that it doesn't know
about, the exception properly passes out of the algorithm, because the
algorithm is not responsible for operating correctly when given a
specialization.  Presumably the caller is using the spcialization for
optimizing, and so falls into my first case.

One of the cases in #1 was orignally my hack implementation for #2.
The specialization-violation blast from a specialized object could
include a generalized version of the object that the calling algorithm
could then substitue.  This is sufficiently useless and hard to
understand that I prefer the principles in #1.

-------
Specific comments:

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

1) Non-extendable Arrays are real easy.  A superType of MuTable could
just define replace(key,value), fetch and get.  With this protocol,
the user cannot change the domain of the MuTable, only values to which
those domain elements are bound.

2) Note that in Pavel and Cardelli's type systems, if A is a superType of
B, 'store(A*)' is more general than 'store(B*)', but 'B* fetch()' is
more general than 'A* fetch()'.  Thus, WordArray and MuTable have no
single ordering.  Resolving this ordering problem requires multiple
*Types* for an object, not multiple *inheritance*.  Multiple
inheritance implies all the code copying issues which are independent
of super-type relationships.

3) The WordArray protocol has to support multiple wordSizes.
Requiring the same wordSize makes the WordArray abstraction useless
for representing text in mixed languages (in the last implementation I
heard).  We don't need to implement multi-wordSize WordArrays, but we
shouldn't rule them out unnecessarily.

dean