TITLE: Various views on abstract data types

3 Dec 93

[ ABC = abstract base class
  ADT = abstract data type
  CDT = concrete data type     - adc ]


[RR] = rrowe@halcyon.com (Robin Rowe)
[ST] = pkt@lpi.liant.com (Scott Turner)
[JS] = maxtal@physics.su.OZ.AU (John Max Skaller)


[RR] What is an Abstract Data Type?

[ST]

There are two sides to abstract data types.  First, there's the sense
in which built-in types such as 'int' and pointers are abstract.  A
program uses them without reference to how they are implemented.
The interfaces of these types are sets of built-in operations
such as +, =, malloc, and &.

Then comes the capability within a program to define such an
interface using an arbitrary type name, and to associate an implementation 
with the interface.  [...]

A C++ class defines an interface and a static type.  Unless it is an 
abstract class, it also defines an implementation.  Any class can
be considered an ADT (see * below), but an "abstract class" is pure ADT
in that it has no implementation. [...]

[RR]

In "The C++ Programming Language, 2nd Ed." Stroustrup says, 
"The relationship between CDT's and ADT's will be discussed 
in 13.32." In section 13.32, he gives an example of a 'set' 
class and of a 'vector_set' class publicly derived from 'set' 
and privately derived from 'vector'. Is 'set' an ADT and 
'vector_set' is a CDT? 

[ST]

Stroustrup says 'set' is an ADT and 'vector_set' is a CDT,
but IMO the primary sense in which 'vector_set' is concrete 
is that it provides an implementation of 'set'.  [...]

[RR]

In "Advanced C++" Coplien says an ADT defines "the interface 
to a data abstraction without specifying the detail." [...]
He goes on to say that "Classes are used to create new user-defined 
types in a C++ program-- the types we call abstract data 
types." and "Classes are the language constructs used to 
create abstract data types, or user-defined types." Isn't 
this a bit misleading, or are ALL user-defined types really 
ADT's? 

[ST]

*  Any class can be considered an ADT, but a poorly designed
   class may fail to hide its implementation details properly.

[ST]

[..] A concrete class serves a dual role of interface and implementation.
An abstract class exists solely for its interface, hence its 
interface is typically better suited to re-use.

[RR]

Check out Meyer's Object-oriented Software Construction pgs 52-60 for
a logically complete and clear definition.  You can have fun trying to
reconcile the definition you find there with those in the references
you mentioned.  However, when in doubt, just go with Meyer's.

[JS]

	NOTE also there is a perhaps unfortunate but common
meaning in C++ of the term "ADT" quite distinct from that
given by Meyer (which is conceptual).

	I use the term "ADT" class to refer to a type which
is VALUE ORIENTED, or mathematical in nature. Such classes
are typically copyable, and there essence is encapsulated
in the contents of the objects memory. Objects of ADT classes
are immutable, except that the value of an object
can be change completely by assignment. (Or equivalent
operation)

	The other sort of class is what I call an
"Object Oriented Class". Such a class is typically not
copyable. The address of an OO object is significant,
and part of the properties of the object. You copy
OO classes by copying pointer to them. OO classes
are almost invariably mutable.

	Examples:

	ADT/Value oriented class:
		complex, matrix, string

	OO class:
		a node in a tree or linked list structure


C++ handles ADT/Value oriented classes very well, mainly
because of constructors/destructors. It does not handle
OO classes particularly well, however. If you examine
a book like Coplien you will see that a large amount
of effort goes into representing OO classes with
Value ones (handles).

There is a proposal before the committee which will allow
the programmer to DECLARE what type of class it is that
e is designing:

	class node { // object oriented class
	class complex const { // value oriented class

Semantically, the effect is that rvalue of the
value oriented class are treated as const, whereas
rvalue of object oriented class default to non-const
unless const on a return type overrides this:

	const node f() { .. }
	f().member(); // const member selected
	node().member(); // non-const member selected

	complex().member(); // const member selected
	complex g(); // same as "const complex g()"