CHAPTER 10

ABSTRACT DATA TYPES

THE CONCEPT OF ABSTRACTION

· Abstraction allows one to collect instances of entities into groups in which their common attributes need not be considered.

· Two kinds of abstractions in programming languages are process abstraction and data abstraction.

· The concept of process abstraction is one of the oldest. All subprograms are process abstractions because they provide a way for a program to specify that some process is to be done, without providing the details of how it is to be done.

· Process abstraction is crucial to the programming process. The ability to abstract away many of the details of algorithms in subprograms makes it possible to construct, read, and understand large programs.

· All subprograms, including concurrent subprograms, and exception handlers, are process abstractions

ENCAPSULATION

· Encapsulation is a grouping of subprograms and the data that they manipulate

· An encapsulation provides an abstracted system and a logical organization for a collection of related computations

· They are often placed in libraries and made available for reuse in programs other than those for which they are written

INTRODUCTION TO DATA ABSTRACTION

· An abstract data type is simply an encapsulation that includes only the data representation of one specific data type and the subprograms that provide the operations for that type

· An instance of an abstract data type is called an object

· Object-oriented programming is an outgrowth of the use of data abstraction

FLOATING-POINT AS AN ABSTRACT DATA TYPE

· All built-in types are abstract data types, even those of FORTRAN I

· Floating-point types employ a key concept in data abstraction: information hiding. The actual format of the data in a floating-point cell is hidden from the user.

USER DEFINED ABSTRACT DATA TYPES

· The concept of user-defined abstract data types is relatively recent

· They should provide:

- A type definition that allows program units to declare variables of the type but hides the representation of these variables

- A set of operations for manipulating objects of the type

· An abstract data type is a data type that satisfies two conditions

- The representation, or definition, of the type and the operations are contained in a single syntactic unit

- The representation of objects of the type is hidden from the program units that use the type, so only direct operations possible on those objects are those provided in the type’s definition

· Program units that use a specific abstract data type are called clients of that type.

· A benefit of information hiding is increased reliability. This is because clients cannot change the underlying representations of objects directly, either intentionally or by accident, thus increasing the integrity of the object

DESIGN ISSUES

· A facility for defining abstract data types in a language must provide a syntactic unit that can encapsulate the type definition and subprogram definitions of the abstraction operations

· Concurrent Pascal, Smalltalk, C++, and Java directly support abstract data types

· Some design issues beyond encapsulation are whether the kinds of types that can be abstract should be restricted, whether abstract data types can be parameterized, and what access controls are provided, and how such controls are specified

LANGUAGE EXAMPLES

· Simula 67

- Data abstraction, although incomplete by definition, appeared in the class construct of Simula 67.

- Simula classes are heap-dynamic, meaning that they are created dynamically on the heap at the request of the user program

- Simula 67’s contribution to data abstraction is the encapsulation of the class construct.

- Variables declared in a Simula 67 class are not hidden from the clients that create objects of that class, violating the information-hiding requirement of the definition of an abstract data type.

- Simula 67’s classes are far less reliable than a true abstract data type because of the violation.

- Although Simula 67’s class construct provides encapsulation it does not however, provide information hiding.

· Ada

- Ada provides encapsulation facilities that can be used to simulate abstract data types, including the ability to hide their representations.

- The encapsulation constructs in Ada are called packages.

- Each package contains two parts.

- First, is the specification package, which provides the interface of the encapsulation

- Second, is the body package, which provides the implementation of the entities, named in the specification.

- The user can choose to make an entity visible to clients or provide only the interface information.

· Modula-2

- The modules of Modula-2 are similar to the packages of Ada, so they provide a similar level of support for abstract data types

- The primary difference between the two is that in Modula-2, all types whose representations are hidden in modules must be pointers.

· C++

- Unlike, Ada and Modula-2, which provide encapsulation that can used to simulate abstract data types, C++ provides the class, which more directly support abstract data types

- The data defined in a class are called data members; the functions defined in a class are called member functions.

- Classes may contain both hidden and visible entities.

· Java

- Java’s support for abstract data types is similar to C++

- There are however a few differences, such as, all user-defined data types in Java are classes and all objects are allocated from the heap and accessed through reference variables and the support for abstract data types in Java can only be defined in classes

- Java also includes packages as one of its encapsulation constructs.

PARAMETERIZED ABSTRACT DATA TYPES

· A parameterized abstract data type means that the data type is generic

· Both Ada and C++ allow for generic or parameterized abstract data types

· These generic types are considered templates