Abstractions -- The Building Substance of Programming Languages

                           Data Abstraction
                            << abstract >>
                                  A
                                  |
         .------------------------+------------------------.
         |                        |                        |
 Data Type Abstraction     Object Abstraction     2-D Data Abstraction
 (abstract data types)     (object-based OO)
                           has dynamic dispatch
     A           A             A       A
     :           |             |       |
     :           `-----. .-----'       `------. + cloning
     :   + dyn overload| |  + generators      |
     :  (+ receiver    | | (+ method          |
     :      syntax)    | |    suites)         |
     :                 | |              Prototype-based
     :            Class Instances    (e.g. actor systems?)
     :                  A                     A
     :                  |                     |
     :                  |                     | + delegation
     :           ``classical OO''             |
     :                                  Delegation-based
     :................................. (with traits)

``Data Abstraction refers to a range of techniques for defining and manipulating data in an abstract fashion.'' [OO/AD, 155]

Besides general data abstract, abstract data types and object abstractions are ``two distinct techniques for implementing abstract data'' [OO/AD, 152]. There is a ``duality [in the categorial sense] between abstract object types on the one hand and abstract data types on the other hand'' [CoAlg, 4]: ``Whereas abstract data types in the initial approach may be formalized as minimal soulutions (fixed points) of recursive type equations, object types may be understood as maximal solutions (fixed points) of recursive type equations'' [CoAlg, 2].
More generally: ``The distinction between algebra and coalgebra pervades computer science and has been recognized by many people in many situations, usually in terms of data versus machines. A modern, mathematical precise way to express the difference is in terms of algebras and coalgebras. The basic dichotomy may be described as construction versus observation'' [TCACI, 4].
``The initial algebras and terminal coalgebras ... can be described in a canonical way: an initial algebra can be obtained from the closed terms (i.e. from those terms which are generated by iteratively appluing the algebra's constructor operations), and the terminal coalgebra can be obtained from the pure observations'' [TCACI, 3].

• 1A. 2-D Data Abstraction can be seen ``as being organized around the original multi-dimensional specification of a data abstraction. This matrix is not decomposed ... but is managed as a whole by the system. In this scheme, representational structures and operations are relatively independent entities'' [OO/AD, 174]. ``[T]he message is viewed as an operation on a collection of arguments, and any or all of the arguments may play a part in determining which method to run'' [OO/AD, 173f].
  Examples: CLOS, Dylan[?].
  The programming technique data-directed programming (presented in Scheme) ``handles generic operations ... by dealing explicitly with operation-and-type tables'' to map the operation's name and the data's type to a procedure.

  1B. In programming with Abstract Data Types (user-defined algebraic data types) ``concrete algebras are used to represent data and [data]type abstraction provides information hiding'' [OO/AD, 174] [emphasis added].
  ``An abstract data type implementation is an algebra; that is, it is a set together with operations on that set ... A signature is a type that classifies algebras. It must not be confused with the sort t of the algebra which is ... the type of abstract values manipulated by the implementation. A third type is ... the [data]type of the concrete representation of the abstract type values. ... Signature types are especially useful if ADT implementations are first-class values'' [OO/AD, 168]. (formal definition of algebra and signature). In principle, ADTs can be multisorted. Then the ADT actually is a collection of data abstractions. One of them is the principal data abstraction. Rules relate it with values from the other data abstractions. [DAOOC++, 34]

  (1) ``The specification of an abstract data type describes in which way the elements of that data type may be generated and under which conditions different generation schemes generate equal elements'' [CoAlg, 2].
  If you wonder what is about the observations then consider: ``[O]n an initial algebra X one may have operations of the form X -> A, obtained by initiality. An example is the length function on lists. Such operations are derived, and are not an initial part of the (definition of the) algebra [TCACI, 8].
  For the user ``the data is abstract by virtue of an opque type'' [OO/AD, 152]. This type is also called the sort of the ADT. The user only knows that the values are of some datatype. User code can work with them without needing to know which one it is -- this is called existential type quantification. How clients use ADTs, see also dot vs open.

  (2) ``The type definition specifies the representation ... and a set of primitive operations'' [DT/PD]. ``The connection between the constructors and the observations is via a shared representation... [which] is hidden from the client'' [OO/AD, 157]. ``The representation is defined as a labelled union [data]type'' [OO/AD, 158]. ``Each observation is formed into an independent operation which returns the appropriate result when applied to any of the constructors' values'' [OO/AD, 157]. As a consequence the definition of how a value created by each constructor behaves is spread across the definition of the observations.
  In principle, there may be different implementations for the same signature, one algebra could implement several signatures, and algebras (like signatures) could be organized in sub-signature-hierarchies. (But this does not impose a relationship between their sorts; data values from these implementations cannot be intermixed!) For instance, a signature for types of complex numbers, and two implementations (algebras, also called structures, or packages) [adapted from ATDN]:

  signature Complex = opaque C make : Real x Real -> C re,im : C -> Real mul : C x C -> C

  structure cartesian : Complex = datatype C = { x, y: Real } make(r,i) = return { x=r; y=i } re(c) = return c.x ...

  structure polar : Complex = datatype C = { x, y: Real } make(r,i) = return { x=sqrt(r*r-i*i); y=arctan(i/r) } re(c) = return c.x * cos(c.y) ...

  Examples: Modula-2, CLU, ML.

  Besides data abstraction the concept of abstract data types usually also includes a set of axioms to specify the relative behavior of the operations. Model theory investigates the algebras which satisfy these axioms. ``Initial'' models are seen as the standard models of ADTs.

  1C. In object-based programming Object Abstraction is used (called ``procedural data abstraction'' in [OO/AD], ``procedural data structures'' in [DT/PD]). It is closely connected with message-passing models of computation.

  (1) The data is represented by the observation procedures (methods) applicable to the object abstraction. The object is seen as a record of procedures (methods), closed over a common state, inaccessible to others. All method invocations are intrinsically dispatched dynamically.
  ``[P]rocedural data structures provide a decentralized form of data abstraction'' [DT/PD] where ``the mechanism for producing the observed value needs to be hidden from the client'' [OO/AD, 160] to let it only depend on what can be observed, to allow (adding) definitions of constructors (prototype objects or classes, see below) of objects of a certain object type (i.e. having all the methods) anywhere in the program, and to allow that ``[e]ach part of the program which creates procedural data will specify ist own form of representation...'' [DT/PD]. As a consequence the definition of how an observation behaves is spread across the definition of the constructors.

  (2) ``The specification of an abstract object type describes the attributes and methods that can be used by an object instance of that type'' [CoAlg, 2]. ``The interface to a procedural data value is a type that specifies the names, arguments, and return values of each procedure in the value'' [OO/AD, 169].
  The interface of procedures (methods) provides information hiding, that is, ``the data is abstract because it is accessed through a procedural interface -- although all of the types involved may be known to the user'' [OO/AD, 152]. ``All we can describe about a particular state [of an object] is its behaviour, which arises by making successive obervations. This will lead ot the notion of bisimilarity of states: it expresses of two states that we cannot distinguish them via the operations that are at our disposal, i.e. that they are "equal as far as we can see". But this does not mean that these states are also identical as elements of [the object's state space]. Bisimilarity is an important, and typically coalgebraic, concept'' [TCACI, 8].

  Examples: ActiveX components. And without interface specification: Smalltalk; Self (see also below).

• 2a. The ADT perspective explains objects and classes without needing an object abstraction by the following correspondences:

  An interface type I	= Signature I' where the declared sort S is the sort of object states, and where self is added as a by-reference parameter of sort S to all methods of I.
  A class C implementing I	= Algebra A with signature I'
  An object o, instance of C	= Variable o' with an S value operated upon by A's operations

  Several classes can have operations with the same name. The binding of a name to an algebra's operation which depends on the class of the object is explained as (dynamic) overloading on the ``self parameter.''

• 2b. From the object abstraction perspective a class is a generator of, or a template (``cookie-cutter'') for object(-abstraction)s:
  ``The primary function of classes ... is as extensible generators of objects.'' [LOOM Modules] ``The class construct ... can be viewed as a special mechanism for creating closures of records'' [OO/AD, 160]. ``Each constructor is converted into a template, or class, for constructing procedural data values, or objects'' [OO/AD, 159].
  [ThO] calls this the ``naive storage model:'' every class instance contains (pointers to) each of its methods.

The class concept allows to extend each direction of data abstraction by aspects of the other one [OO/AD]:

Abstract Data Types:

Object Abstraction:

Specialization of the state representation: The state is defined independently in a subclass, and then ``translated'' to the superclasses state representation by a mapping. Examples: List comprehension and recursive data values in Haskell and Gofer. Intermixing of objects from different classes: Allow sorts from different implementations to be the same type or subtype and select implementation of observation operation based on type tags attatched to the abstract values (``single dispatch''). Examples: only subtypes and only in combination with inheritance: Ada95, KOOL in [OOPUA].

Sharing of representation among objects is achieved by making the encapsulation of the representation class-based, not object-based. Then object types are just partially abstract interfaces [OO/AD, 170]. As a compromise with object-based encapsulation, parts of the representation might be object-wide and another part might be class-wide accessable. Example Eiffel: object-based ``export NONE'' and (sub)class-based ``export MyClass.''

3. Prototype-based OO

• To add new observations to an old representation the representation needs to be shared with subclass objects, too.
  To balance this with class-based encapsulation, part of the representation might be class-wide and another part might be inheritance-wide accessable.
  Example C++: class-wide ``private'' and subclass-wide ``protected.''
• To make use of old observation operations in the subclass (new observations may be added), the old representation must also be inherited (and may be extended). Compared to ``adding observations'' it is essential that some of the inherited observation operations may be overriden.

«Delegation was introduced [by Lieberman 1981] as a message forwarding mechanism. The basic idea of delegation is to forward messages that cannot be handled by an object to another object called its parent in Self or proxy in Act1 ... Indeed, the key-point of delegation is that the pseudo-variable "self" still points to the original receiver of the message, even if the method used to answer the message is found in one of its parent[!]» [PBL, 203]