Re: Classes vs Tagged Types - Terminology

[stt@spock.camb.inmet.com (Tucker Taft)]

In article <17255@goanna.cs.rmit.oz.au> 
  ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:

>In article <C4AGp4.1Fw@clw.cs.man.ac.uk>, 
>  chl@clw.cs.man.ac.uk (Charles Lindsey) writes:
>...
>> CLASSes come in two flavours:
>> 	Without INHERITANCE
>> 	With INHERITANCE
>...
>> It is generally agreed that you need INHERITANCE to do any serious
>> "Object Oriented Programming".
>
>Where have you _been_, mate?  There are quite a few OO languages
>based on delegation rather than inheritance.  . . .

It seems that the more fundamental distinction is with or without
(run-time) polymorphism.  If you look at a C++ class that
has no virtual member functions (and hence no polymorphism),
it is little more than an abstract data type that uses
prefix notation for referring to its operations.
You can inherit from it, but that is not particularly ``interesting''
without virtual member functions.
Ada 83 also has this limited kind of inheritance, where you
can derive from a type to create a new type.

More important than inheritance (even with type extension), 
in my view, is the ability to have multiple implementations of 
a given abstraction.  This is what separates an "object-oriented"
language (like Ada 9X or C++) from an "abstraction-oriented"
language (like Ada 83 or CLU).  In an "abstraction-oriented"
language, each abstraction interface has exactly one implementation,
and hence all calls on operations of the interface can be
statically bound.  

In an "object-oriented" language, a given
abstraction interace may have many implementations (typically
organized into some kind of inheritance hierarchy, though that
is not essential), and each object carries around some identification
of which particular implementation it originates from.

In other words, to be a true object-oriented language, objects
have to be "self-identifying" (or "type-identifying") in some way, 
so that even though various objects may all be treated as supporting
a single abstract interface, the appropriate implementation can
be executed when a given operation of the interface is invoked.

It is misleading to associate polymorphism with the term "class,"
since in both C++ and Simula-67, it is the virtual functions
that provide (run-time) polymorphism.  Without virtual functions,
a class is just a capsule for an abstract data type.  One thing that is
rightly associated with the term "class" is the property of
"subclass matching."  That is, if a formal parameter is of
a given class, then an entity belonging to any subclass of
that class is acceptable as the actual parameter.  

In Ada 9X, it is only class-wide types (named "T'Class") that provide
subclass matching.  Specific types (like "T") do not provide
subclass matching.  And of course, it is "private" that signals that
a type is an abstract data type in Ada (83 or 9X).  
We considered using "virtual" on subprograms as the signal for 
polymorphism, but it is relatively easy to prove that types
with some virtual and some non-virtual primitive subprograms have 
some undesirable properties that make thorough testing very difficult.  
For example, imagine a type T that has three operations, A, B, and C,
where A and B are virtual, but C is not.  We could test how A, B, and
C work together on T, and each derivative of T (T2, T3, T4, etc.),
but still not know whether they work together properly when
we use dynamic binding, since with dynamic binding, we would execute
the "C" of the nominal (static) type of the parameter, and 
the "A" and "B" of the actual (dynamic) type of the parameter, 
a combination that had never been tested.  

In other words, if you have N types in a hierarchy,
with some operations virtual and some not, there are N*N/2 cases
(approximately) to test, representing the various combinations
of nominal (static) type and actual (dynamic) type of a given parameter.
However, so long as the operations are either all virtual, or all
non-virtual, this quadratic explosion of test cases doesn't occur.

Given the above phenomenon, we concluded that it was better
to mark the type by saying that all of its (primitive) operations
are "virtual" (aka dynamically bound, aka "dispatching"), rather
than to mark each operation individually.  Since the objects
of a type hierarchy with dynamically bound operations must be 
self-identifying, we chose the term "tagged" in analogy with
"tagged architecture" to indicate that all operations of the
type are dynamically bound.  We also considered "polymorphic"
(too many meanings), "extensible" (the objects aren't extensible,
the set of types is), "dynamic", etc.  None of them seems as
suggestive and unambiguous as "tagged," which also has
a nice connection to the fact that we are moving the concept
of "tagged architectures" into software.

It is intereseting to note that the ANSI C++ committee is currently 
considering providing some kind of run-time-checked type casting.  
However, as currently proposed, this will only be provided for classes 
with at least one virtual member function.  Hence, they recognize
that they have two kinds of C++ classes, those whose objects
don't identify themselves, and those whose objects do.  Much
as in Ada 9X, we will have two kinds of abstract data types
(private types), those whose objects don't identify themselves
(untagged), and those whose objects do (tagged).

An example of a C++ class that would probably have no
virtual member functions, and hence be effectively untagged 
would be "complex," since there is little advantage in having 
virtual member functions for such an abstract data type.  
Similarly, in Ada 9X, a private type "complex"
would have no particular reason to be tagged.

In any case, the Ada term for "C++ class" is essentially 
"package-with-a-private-type."  Both of these terms correspond
to the more general concept of an "abstraction" as developed
by Guttag and Liskov in the late 70's. 
The term "tagged" in Ada 9X takes the place of having to write 
(in C++) "virtual" on each member function (primitive
operation) of the abstract data type, and indicates
that the corresponding objects are "self-identifying."

NOTA BENE:  The above is admittedly a technical discussion,
not a marketing one.  If you want to talk marketing, please
start a different thread of discussion.  (Charles Lindsey's note
was trying to focus on the underlying technical issues, not 
the marketing ones, and this response has tried to keep that focus.)

S. Tucker Taft   stt@inmet.com
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138