NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/object/3223

Text File | 1992-08-16 | 29.4 KB | 613 lines

Newsgroups: comp.object
Path: sparky!uunet!decwrl!csus.edu!netcom.com!objsys
From: Bob Hathaway <[e-mail]>
Subject: Re: Type Conformance and Inheritance (was O.M() versus M(O) notation)
Message-ID: <[e-mail]>
Date: Mon, 17 Aug 92 05:32:58 GMT
Organization: Object Systems
Summary: Very long Definitonal and Tutorial posting
References: <[e-mail]> <[e-mail]>
Lines: 601

[After writing this long-winded article I noticed other responces.  I'll
 have to reply to them later.  This article is already over 600 lines.]

In article <[e-mail]>, [e-mail] (Piercarlo Grandi) writes:
> On 13 Aug 92 01:58:32 GMT, [e-mail] (Bob Hathaway) said:
>objsys> Type is well defined.
>
>Really? I see the word 'type' used with very different referents by
>different people at different times. At some of these times I get a
>strong suspicion that they themselves are not clear as to what they are
>talking about.

This is entirely possible but I strongly believe the notion of type is
easily justified.  I will use the term "abstract type" (as in Emerald
and Jade) to try to be more precise.  I elaborate further on the nature
and definition of type later in the posting.

>objsys> No mention is made of implementation since type systems only
>objsys> deal with types.
>
>Hardly surprising! If 'type systems' were dealing with blondes, than
>that would be news!

But this clearly shows type and implementation are separate!

  [Poor review of Kim and Lochovsky "OO Concepts, Databases and Applications"]

I think OO Concepts... is an excellent work although I view it as mostly of
historical significance.  Won Kim's work and reputation in the database
community and especially in the OODB domain is hardly equaled.  Your
comments make no specific points so I'll consider them semantically worthless
unless and or until justified.

>objsys> So "In the presence of dynamic binding it is (in general)
>objsys> impossible to determine statically the class of a variable, but
>objsys> with the appropriate type rules we can still perform
>objsys> type-checking."
>
>Another lot of meaningless, self referential verbiage. One could rewrite
>it as
>
>        "In the presence of type checking with deterministic type rules
>        it is in general appropriate to perform..."
>
>or any other permutation of this fine collection of buzz words, and the
>meaning would not change.

You must be a linguistic transformationalist!  Firstly and most required
seems to be a reading of the Emerald papers, something I notoriously leave
behind.  This paper describes abstract types and gives a clear description
of them although I don't agree with all of their philosophy.  I [bragging on]
stumbled across a similar notion of typing myself while considering a more
powerful domain and believe/discovered it is also applicable in the more
classical programming domain.  I later learned that this view of typing
was actually quite common, confirming my suspicion that this separation
is indeed desirable if not outright necessary.  [Bragging off].

I'll give a quick tutorial from the beginning, hopefully addressing all
of the issues raised thus far.  I'm not going to give references since
this is not a formal paper but any can be given if asked for.  I feel
it is necessary to go over and define the basics before any constructive
discussion can take place.  This will give a clear, precise, and
complete definition of all terms I have discussed and advocated thus far
which it is hoped will satisfy your up to now insatiable and much asked for
desire for such things.  Please read the entire discussion before commenting
on it in bits and pieces since examples are given after the discussion
which should help clarify the meaning (after which please feel free
to comment bitwise and piecewise).

First we have an abstract or real-world entity (which *can* be referred to
as an abstract or real world entity).  Now we need a design/programming
metaphor for them.  This requires a notation and within this notation this
metaphor can be referred to as a type.  We'll use the term "abstract type"
to help avoid confusion (although I prefer to use the term type).  Anyway
this "abstract type" notation really just describes its analogous counterpart
in some real-world or abstract-world domain (or classification scheme) and
*only* that counterparts properties/attributes/etc.  An abstract type can
also be thought of as a specification or interface or even protocol because
it so specifies the properties/attributes/etc. of its counterpart.  These
latter terms are often freely interchanged so they should not be used in
isolation.  As shown below, abstract types and classes each call for a
specification/interface/protocol.  Obviously an abstract or real world entity
can have any number of types because types are simply a description of
this entity.

Now some form of implementation must be specified.  It shall be given that
multiple implementations should be available to satisfy an abstract type.
This has been found to be an axiom since implementations (also called
representations) are not fixed by the abstract type and because various
implementations may be desirable under various conditions and at various
times.  It is even highly desirable under very dynamic environmental
conditions for implementations to decide to "become" other implementations,
in other words for them to change their own representation.  Therefore some
means of defining implementations is required.  Object constructors can be
used in Emerald, the "class" construct is the means of specifying an
implementation in most "classical" object-oriented languages, by definition;
and objects are self-descriptive in prototyping languages.

I'll stay with the classical object-oriented languages for now and define
"class" to be an implementation construct which is in accord with the
available object-oriented literature.  Classes must then have a name or
means of reference and also group the assorted implementation constructs
to distinguish from among the infinite number of possible implementations.
But classes can satisfy many types in a similar fashion that types can be
satisfied by multiple implementations.  This is the basic subtyping or
inclusion polymorphism rule and will be given as an axiom.  A brief
explanation can begin with Smalltalk, a statically typeless language.
Smalltalk has no way of stating (specifying) that certain operations or
constraints are required by some instance (polymorphic parameter or
object).  These should be included in an instance's type allowing multiple
implementations and requiring inclusion polymorphism, or more simply put
that an implementation can satisfy multiple types.  This requires the
separation of abstract type from class, otherwise only one construct could
be used as with classical object-oriented languages.

An interesting theoretical issue is the role of abstraction.  Abstract types
are directly implemented by classes in real-world modeling since there are
no high-level abstractions such as "device" in the real-world, it is simply
a subjective classification and therefore I don't see the need for any
inclusion polymorphism but only the need for multiple implementations in
the RWM domain.  But in the abstract domains there is a great need for
abstractions, such as "device", and it is given as a later example.

Now we have a clear notion of entity, abstract type, and class.

Real or Abstract World entity:

  Our abstract concept of a stack
  or perhaps a stack of lunch trays (with a spring).

Abstract Type (one example, many per Real or Abstract World Entity):

  type Stack is
    push(T)
    pop() returns T
  end

Implementations (two examples, many per Abstract type):

class List_Stack: private List is      class Array_Stack is
public:
  push(int) ...                          push(int) ...
  pop() ... return (int) ...             pop() ... return (int) ...
private:                               private:
  ...                                     int    collection[100]
end                                    end

and etc.

Now reuse becomes an issue.  Inheritance and compositional approaches have
been suggested for the reuse of implementations.  As in the first example,
a class can be reused by inheriting from it.  An alternative is the
compositional approach as advocated by Jade.  I don't have the paper with
me but the basic idea is to allow finer grained reuse by making all
constructs (at least from the level of method and object in Jade) available
to programmers.  This can obviously be extended to all constructs but lets
stay at this level and use an informal notation (not necessarily Jade) for
simplicity.

  type Stack is
    push(T)
    pop() returns T
  end

Environment (whats expected to be out there)
  Array
  top
Component Array_Push(T element) is
  Array[top++] = element;
end

Environment
  Array
  top
Component T Array_Pop() is
  return Array[--top];
end

Then a stack implementation can be defined as:

class Array_Stack is
  push(T) <= Array_Push
  T pop() <= Array_Pop
end

If a queue is desired, Array_Push can be reused but pop will change:

Environment
  Array
  top
Component T Array_Remove() is
  ... // left to reader
end

  class Array_Queue is
    insert(T)  <= Array_Push
    T remove() <= Array_Remove
  end

A type should be declared for the new queue to be useful.  Perhaps even
a constraint could be added to the type specifying it is indeed a queue,
requiring all matching implementations to specify that they are a queue
to avoid any accidental type mismatches such as an object that has an insert
and remove operation but isn't really a queue.  This could be defined
formally but I'll stay with an informal constraint for user simplicity.
The Emerald approach is to define an operation such as queue_length making
all implementations implement that operation, but this approach is
arbitrary.

  type Queue is
    insert(T)
    T remove()
    Queue is a queue.
  end

If an is_empty operation is needed (and the original interface must not
change), Jade requires users to redefine the entire interface in a new
type or class.  An alternative is to use inheritance (also called a
"differential programming style") in which this addition alone is added
in the new type or class, the rest is "inherited".  Thus inheritance reuses
the entire interface unless some parts of it are dropped as is possible in
Modula-3.  This is simpler although it requires the user to look at more
than one interface since it is shared.  This is criticized by the Jade
community because it seems to violate locality although it reduces the
size of such derived interfaces; these are moot points.  Not sharing
abstract type or even class interfaces can also cause problems due to
redundancy, as discussed later.  Inheritance is also a way of implementing
the is-a (or is-a-kind-of) relation as discussed below.  Many (in CS)
criticize this use of inheritance from a philosophical point of view while
others (in SE) praise it.  Another issue for reuse is an abstract class,
as discussed below.

The is-a relation by itself is very useful.  For example, devices have many
properties.  These can be put together into a device abstract type giving
the requirements for a class or abstract type to be a kind of device.  There
are various kinds of devices: mechanical, biological, electrical, etc.  All
of these kinds of devices share the properties of devices.  The entire
device interface would have to be duplicated with only a purely
compositional approach.  Inheritance saves the day by allowing abstract types
(and classes where inheritance also applies) to inherit the entire interface
from device.  If a device can do it, so can the various kinds of devices.  We
could create abstract subtypes or subclasses if certain kinds of devices have
a property and others don't or state that only some devices have the property;
this isn't considered important here.  Inheritance is considered important for
deep hierarchies since it would be undesirable to replicate parent interfaces
all the way down.  With a purely compositional approach all implicit subclass
interfaces would have to be changed if the interface of device were to change.
This is caused by the redundancy required by the purely compositional approach
which does not make the inheritance relation explicit and therefore does not
make use of the sharing provided by traditional inheritance.

Abstract classes also have a place since they can help define object
representations.  There are no "device" objects, the hierarchy would have
to be traversed to near its leaves to come across an instantiable entity.
However, inheritance can be used to define abstract classes which give
partial implementations of classes.  Composition can also be used as
above for a finer degree of reuse but abstract classes provide a more
comprehensive facility.  They are much like abstract types but are used
for implementation, not typing.

An interesting point is that there is no partial reuse of abstract types
as there is with abstract classes.  If an abstract type is reused by name
and certain parts are specified as being included and others are not,
this is inheritance.

Another point is that inheritance is not necessarily hierarchical,
it depends on your definition.  The is-a relation does not preclude
graphs although some implementations of class inheritance do.  For
instance, loops in an abstract type graph are trivially handled;
they only require traversal once to determine the entire required
interface (for lack of a better way of putting it).  A similar lack of
this ability can be found in Ada and especially Modula since module
definitions and package specifications must be hierarchical by decree
and not by necessity.  I have complained about and debated this myself
for years!  And as discussed in more detail below, abstract types
do not have difficulty with graphs but classes do, actually confirming
that combining abstract type and class together should be considered
harmful!

Delegation also allows loops, it is hoped the system would track them
with standard graph traversal algorithms although a little twist is
encountered if the class objects could change during traversal (but this
would be considered atypical).

So if a Description abstract type is a kind of Document and should contain
all of Documents behaviour and a Document is a kind of Description and should
contain all of Descriptions behavior, Document and Description should inherit
from each other.  The fact that this can get into a recursive types
entanglement with classes can actually be used as an argument for the
separation of classes from abstract type, since this should be and is
allowed with abstract types but is a mess with classes (their possible
implementations)!

>* why have 'type' have as referent the formal specification of a
>  mathematical entity and not the mathematical entity itself? You
>  seem to be saying that 'type' Unsigned is not the algebra of modulo
>  2^N naturals, but a formal specification of that algebra. There can be
>  many different formal specifications for that algebra. Which one is
>  meant by 'type' Unsigned?

"Type" is already used in design and programming languages where the term
should be defined as above.  Abstract and real world entities should stand
for themselves.  There is a stack and there are natural numbers and so
their "type" (or abstract type if you wish) is a metaphor for them (actually
they are a metaphor for them if you prefer this world;-).  This answers your
next contention too, so it is elided.

>* If 'class' refers to the implementation of a 'type', does it refer to
>  the interface or to the code behind that interface or to the
>  assertions that decorate ? They are all 'implementation'! And if it
>  refers to all of them at the same time, how can I distinguish between
>  those orthogonal aspects?

As discussed above.  Since there are multiple implementations for an
abstract type there must be some construct and way of naming these
implementations.  As for the reuse of them, I have covered both
compositional and inheritance based approaches and it should be obvious
that they are not mutually exclusive.

>objsys> Perhaps this is a clue to the solution of the age old proverb:
>objsys>         Why not concrete data types?
>objsys> Types can be viewed as abstract data types, and classes (or
>objsys> whatever representational construct) can be viewed as concrete
>objsys> ones!
>
>More meaningless/fuzzy verbiage...

Perhaps without the complete (and quite verbose) description above but
since I have defined and justified all terminology from the beginning
perhaps now you can appreciate the humor.  The above verbiage is not
meaningless or fuzzy, it is funny:-)

>objsys> Perhaps we're confusing terminology;
>
>Ah, that's one of the few sure things in this discussion.

No longer...  If there are any unclear points where I have given imprecise
definitions please point them out.  Any discussion, alternatives, and
commentary is most welcome, too.

[On general definitional confusion]

I have defined all of the terms I have used so far; you are encouraged
do the same if you disagree.  But having a single standard should be
preferred.

>objsys> and Class (or whatever representational/implementation
>objsys> device as appropriate) defines the concrete structure of an
>objsys> object.
>
>So 'class' is only the structure of an object, not the implementation of
>operations on it?

No, it is both.  Thanks for pointing out my incompleteness.

>But the compiler never sees any of 'type' and 'type system'! The
>compiler only sees interfaces and implementations! Or, at best,
>assertions that decorate them and are derived from specifications.

As a compiler writer I work with this all the time.  Compilers do have type
checkers and they do enforce type-checking.  If not at compile-time then
thru meta-objects (or thru an RTS) at run-time.  The abstract type as
defined above is used exclusively for this purpose.  Classes (as defined)
define an object's structure and behaviour and external interface to their
world.  (Abstract) types therefore are used to insure that objects can
satisfy the required operations as defined by the types they must satisfy.
This is precisely ASU's definition.

>pcg> There is absolutely no reason to believe that structural reuse
>pcg> opportunities need to happen in a hierarchical fashion like with
>pcg> inheritance.
>
>objsys> Sure there is.  We do it all the time; its called
>objsys> classification.
>
>Yes, but all hierarchical taxonomies are inappropriate, in the sense
>that they always cause bad classifications.

No, they don't.  As discussed under devices, they can be quite appropriate.
And without an explicit inheritance relation there can be excessive
redundancy.  Since I believe your next example is in error (although I
did give an example where graphs are required), perhaps you could give
a counter example in terms of the device hierarchy if you have the time.
And as previously pointed out the is-a relation and inheritance does not
have to be hierarchical, although it often satisfies that constraint.

>                        Just consider the Unix
>filesystem; one is forced to choose between thse two organizations:
>
>        c_compiler/bin c_compiler/bin ada_compiler/man ada_compiler_man
>        bin/c_compiler bin/ada_compiler man/c_compiler man/ada_compiler
>
>when neither is really appropriate; the man page for the ada compiler is
>both a man page and part of the ada compiler package, and neither aspect
                     ^^^^^^^
You seem to be confusing aggregation (or composition) and inheritance.  The
Ada man-page can be an instance of man-page and a member of the compiler
package; nothing is wrong there.  This has nothing to do with a hierarchical
abstract type or class taxonomy.  If you disapprove of them then you must
give a relevant counter-example.

>prevails. Similarly in many data design instances. Hierarchical database
>models have fallen from favour because they forced people to do data
>designs that were strict taxonomies, that are inappropriate almost
>always, except for 'parts explosion' situations.

I think your file system example is off entirely.  I'll contend directories
are classes, subdirectories are subclasses, and files are instances of their
containing directory.  Instances linked into several directories simply have
several parents (piece of cake for me or prototyping systems).  Directories
linked into more than one subdirectory also have several parents (multiple-
nheritance and BSD).  Directory loops in the filesystem form non-hierarchical
graphs in the class lattice (watch your recursive programs!).  Dynamic
inheritance is the rule and delegation works as well since inheritance can
be viewed as nothing more than structured delegation with cloning (or
inversely put delegation can be not-so-elegantly viewed as reference parents).
No lack of anything here...

>objsys> Once wants the ability (my favourite peeve) to independently
>objsys> reuse interfaces, specifications, and implementations, and a
>objsys> general purpose algebra for all of thse things.
>
>objsys> Some systems with inheritance may not provide this but I don't
>objsys> see any inherent restrictions.
>
>Well, except that you insist otherwise that type systems should be
>hierarchical. Isn't that a fairly large inherent restriction?

No I don't and never have.  As pointed out above, the is-a relation does
not have a hierarchical restriction and indeed further justifies the
separation of type and class.  I defended classification, not strict
hierarchies.

>Here we are back to 'type' as 'abstract specification', not 'interface
>specification'.

No difference, these terms can be used interchangeably as discussed above.
Since I have now defined abstract type and class perhaps any confusion
will be reduced.

>Still, I am puzzled by your insistence that 'type'
>should refer to the specification itself, and not the mathematical
>entity described by the specification.

Actual entities stand for themselves - why give them another name?  And
many abstract types are in fact truly abstract and are simply used for
classification as discussed under inclusion polymorphism; they have no
metaphor to match.  So it seems most natural to use the term "type" as a
metaphor (actually vice-versa) for abstract and real world entities.

>objsys> class as an implementation construct, and abstract class as an
>objsys> incomplete implementation construct.
>
>What do you mean by 'complete' and 'incomplete' here?  You may be
>referring to the fact that unfortunately in most (improperly designed)
>OO languages one cannot describe indepdently interfaces and
>implementations, so 'classes' force you to define both together, and
>'abstract classes' are 'incomplete' in the sense that they stand in for
>a proper and separate interface definition facility. If so, I think it
>stinks...

No, I like Jade's compositional approach for fine-grained reuse too but
it doesn't handle the usual case of defining a partial implementation.
There's too much literature on this subject to present the case (see
any C++ or Eiffel reference) but quite a few people (actually the majority)
in the object-oriented community will think you stink too if you want to
take away their partial implementation facility;-)  Given that both
facilities can coexist and the standard definition of an abstract class,
do you still argue against abstract classes?

>objsys> To what extent are these constructs interchangeable?  Can or
>objsys> should types be used as abstract classes?
>
>Here I might be lost completely. Certainly the specification of a
>mathematical structure is in a different domain from a language idiom
>like an abstract class, and the two are not interchangeable at all.

Opps, definitional problems.  We should have cleared this up.  It seemed
as though you were advocating the highest degree of "interoperability"
between abstract types and classes, perhaps it was the definitional problem.
Perhaps you can answer the question again now that you have had a taste of
abstract types and classes.  One basic question is how many syntactic
constructs are required for all the semantic notions of abstract type,
class, and abstract class?  And if more than one, to what degree are they
interchangeable, if at all?  I'm genuinely interested in your response.
It appears to me that abstract types only have a public interface for
what is required whereas classes have a public interface for what they
provide and a private interface for internal use.  Emerald has a type
operation which can be applied to classes giving the maximal type it can
satisfy and I believe with their orthogonal (almost) first-class type system
this type is usable.  Should this type be named and then reused or should
it have been defined in the first place (or should there even be separate
syntactic constructs for the various semantic constructs required)?

>objsys> What do you think???
>
>... but surely it would be better if interfaces, specificationa nd
>implementations could be defined _separately_, and there existed
>notation to combine them with each other into a 'class'.  So a 'class'
>would be built out of quite separately defined interfaces,
>implementations and specifications, and only if all three elements were
>present (possibly empty, but this should be documented) it would be
>instantiatable.

Actually, this sounds like jibberish to me since I'm not clear
on your definition of interface, specification, and implementation.
Protocol has made it in there too.  Since abstract type and class
have been well defined, perhaps we could agree to communicate in those
terms in this newsgroup?  I believe the terms as I have defined them
are in their canonical form even if the languages and notations which
delineate them are considered under the heading of "alternative
approaches".  I think I approve of and have even covered what you're
advocating, though.

>pcg> * given a deque interface, derive stack and queue interfaces by
>pcg>   _subtracting_ the appropriate elements;
>
>objsys> there's only theoretical arguments against it.
>
>Mathematicians do this all the time. We can do it as well. Especially in
>finite domains typical of computing.

So the inheritance solution (grab the class (or whatever) and add/delete
part of it) does work.  Another solution is to rearrange the class
(or whatever) lattice to more accurately reflect the new structure.

pcg> * given two deque implementations, one with lists and the other
pcg>   with resizable arrays, attach one to a stack interface, and one to
pcg>   a queue interface;

[I don't like my last quick answer, so I'll try again.]

Jade's compositional approach does this directly.  This shows a finer
degree of reuse can be justified but is not a counter-example to
inheritance; I still contend they are not mutually exclusive and are
both desirable.  The Jade paper (I'll try to give a reference later) lists
many reasons against the use of inheritance but many are outright incorrect
and several are questionable (cases where composition may cause even more
trouble).  If I had more time or if anyone would like to repost them I could
easily defend some form of inheritance against their charges.

>pcg> * given a specification of a variable size deque, derive from it a
>pcg>   fixed size deque specification by adding the specification of a size
>pcg>   constraint;
>
>objsys> Just adding a constraint?  Sounds like behavioural inheritance a
>objsys> la DRAGOON.
>
>Yes, again, little bits of what I am saying appear here in there, in
>more or less contrived forms. Modula-3 and to some extent ADA and other
>have got some form of interface specification, and DRAGOON and Eiffel
>and a few others may have got some form of assertion reuse. But we are
>talking of contrivances, not of clear, clean, direct descriptive
>devices. Programming is already hard enough in the substance, to afford
>distraction caused by inappropriate terminology of notation.

Well, complain aloud.  If anything is missing I'd love to hear about it.
While deficiencies should clearly be pointed out, proposing feasible
solutions is preferred.  This still doesn't show inheritance has any
problems, though.

>objsys> This may be lacking in most OO notations but I don't see it as a
>objsys> fundemental flaw in inheritance.
>
>Well, if by 'inheritance' you mean 'a fully general (including all
>the "obvious" set operations like union, intersection, ...) way to
>independently reuse separately defined interfaces, implementations,
>assertions' then we are entirely agreed. My point precisely.

Good.  Actually I believe the correct use of inheritance is to implement
the is-a relation and don't believe that this relation precludes anything
so far discussed or enforces unnecessary hierarchical restrictions (except
as discussed above with classes for the latter).  The set operations sound
interesting though: set union sounds like multiple inheritance.

>Unfortunately you have expressed, if I interpreted what you said
>correctly, the notion that 'type systems' should be hierarchical,
>because classification systems should be hierarchical.

No, you misunderstood me.  I simply was trying to point out that
classification has a place in our programming systems, it appeared to
me you felt it didn't.  Inheritance is simply a way to perform
classification and modern variants can handle all possible cases, as
I believe I have shown.

>Just for entertainment, I have collected here some of your statements on
>what the word 'type' stands for.

  ...

I don't see any problems or contradictions in the elided list at all and
after giving an adequate presentation of my terminology, I hope you don't
either!

>--
>Piercarlo Grandi                   | JNET: [e-mail]
>Dept of CS, University of Wales    | UUCP: ...!mcsun!ukc!aber-cs!pcg
>Penglais, Aberystwyth SY23 3BZ, UK | INET: [e-mail]

bob
[e-mail]