10.1 System Structures: Abstract Data Types (ADTs)

Data abstraction is a powerful programming tool. It is the conceptual approach of combining a data type with a set of operations on that data type. Furthermore, data abstraction is the philosophy that we can use such data types without knowing the details of their representation in the underlying computer system.

Data abstraction enables us to consider the data objects needed and the operations that must be performed on those objects, without being concerned with unnecessary details. Indeed, data abstraction is an important part of object-oriented programming.

You have already practiced data abstraction--you have used the Float data type to represent decimal numbers, without knowing much about the internal representation of that data type on a computer. In fact, floating-point representations vary considerably from one computer to another. In some cases there are no hardware instructions for floating-point arithmetic; it is all done with calls to subprograms. The point is that you have used floating-point literals, variables, and operations with confidence, without knowing or even caring how they are represented.

The most important thing in data abstraction is the familiar definition of type: a set of values and a set of operations appropriate for those values. Each one of the types you have used so far, whether predefined or user-defined, has values but also operations. In Ada, the compiler ensures that all operations applied to a value are appropriate for that value. Ada provides powerful facilities for defining your own types--your own data abstraction--and with careful design, you can guarantee that all operations applied to values of your own types are appropriate for those values.

Ada's Specification for Predefined Types: Package Standard

Ada has a convenient way of specifying all the predefined types-- Integer, Float, Boolean, Character, and so on--and their operations. Because Ada programmers learn very quickly to understand package specifications, the designers of the language chose to specify these things with a package specification! This package specification, called Standard, appears as Appendix C. Figure 10.1 shows the section of Standard that describes Float. Notice that the arithmetic and relational operators are specified as functions. For example,

FUNCTION "+"  (Left, Right : Float) RETURN Float;

tells us concisely that "+" takes two Float operands and returns a result of type Float. Mathematically, an operator is really just a certain kind of function, so this notation is appropriate. You will see later in this chapter that Ada also gives you the ability to specify new operators in this manner.

Figure 10.1
Section of the Package Standard Describing Float

PACKAGE Standard IS

  ...

 -- Section of package Standard that defines the type Float and its
 -- operations. Excerpted and reformatted from the Ada 95 RM Sect. A.1.

  TYPE Float IS DIGITS Implementation_Defined;
  -- "Implementation_Defined" means that the Standard does not 
  -- specify the details, because they depend on the computer's 
  -- arithmetic system.

-- The predefined operators for this type are as follows:

  FUNCTION "="  (Left, Right : Float) RETURN Boolean;
  FUNCTION "/=" (Left, Right : Float) RETURN Boolean;
  FUNCTION "<"  (Left, Right : Float) RETURN Boolean;
  FUNCTION "<=" (Left, Right : Float) RETURN Boolean;
  FUNCTION ">"  (Left, Right : Float) RETURN Boolean;
  FUNCTION ">=" (Left, Right : Float) RETURN Boolean;

  FUNCTION "+"  (Right : Float) RETURN Float;
  FUNCTION "-"  (Right : Float) RETURN Float;
  FUNCTION "ABS"(Right : Float) RETURN Float;

  FUNCTION "+"  (Left, Right : Float) RETURN Float;
  FUNCTION "-"  (Left, Right : Float) RETURN Float;
  FUNCTION "*"  (Left, Right : Float) RETURN Float;
  FUNCTION "/"  (Left, Right : Float) RETURN Float;

  FUNCTION "**" (Left : Float; Right : Integer) RETURN Float;

  ...

END Standard;

As another example from Standard, consider Figure 10.2, which shows the specification for the predefined type Integer. Notice the style in which all the familiar integer operations are listed.

Figure 10.2.
Section of the Package Standard Describing Integer

PACKAGE Standard IS

-- This is the section of the package Standard that describes
-- the predefined type Integer.
-- Excerpted and reformatted from the Ada 95 RM, Section A.1.

  ...

  TYPE Integer IS RANGE Implementation_Defined;

-- The predefined operators for this type are as follows:

  FUNCTION "="  (Left, Right : Integer) RETURN Boolean;
  FUNCTION "/=" (Left, Right : Integer) RETURN Boolean;
  FUNCTION "<"  (Left, Right : Integer) RETURN Boolean;
  FUNCTION "<=" (Left, Right : Integer) RETURN Boolean;
  FUNCTION ">"  (Left, Right : Integer) RETURN Boolean;
  FUNCTION ">=" (Left, Right : Integer) RETURN Boolean;

  FUNCTION "+"   (Right : Integer) RETURN Integer;
  FUNCTION "-"   (Right : Integer) RETURN Integer;
  FUNCTION "ABS" (Right : Integer) RETURN Integer;

  FUNCTION "+"   (Left, Right : Integer) RETURN Integer;
  FUNCTION "-"   (Left, Right : Integer) RETURN Integer;
  FUNCTION "*"   (Left, Right : Integer) RETURN Integer;
  FUNCTION "/"   (Left, Right : Integer) RETURN Integer;
  FUNCTION "REM" (Left, Right : Integer) RETURN Integer;
  FUNCTION "MOD" (Left, Right : Integer) RETURN Integer;

  FUNCTION "**"  (Left : Integer; Right : Integer) RETURN Integer;

  ...

END Standard;

The Nature of an ADT

An abstract data type, or ADT, is really just a formal name for a type: a set of values and a set of operations that are appropriately applied to those values.

A program that uses an abstract data type is called a client program. A client program can declare and manipulate objects of the data type and use the data type's operators without knowing the details of the internal representation of the data type or the implementation of its operators; these details are hidden from the client program (this is called information hiding by computer scientists). In this way we separate the use of the data and operators (by the client program) from the representation of the type and implementation of the operators (by the abstract data type). This provides several advantages. It allows us to implement the client program and abstract data type independently of each other. If we decide to change the implementation of an operator (function or procedure) in the abstract data type, we can do this without affecting the client program. Finally, because the internal representation of a data type is hidden from its client program, we can even change the internal representation at a later time without modifying the client.

An ADT is an important kind of reusable software component. ADTs are written so as to be usable by a variety of client programs. An ADT needs to have no knowledge of the client programs that will use it; the client programs needs to have no knowledge of the internal details of the ADT. Ideally, ADTs are thought of as analogous to the various integrated electronic components used in modern computers and other devices: One needs to understand only the interface to an ADT to "plug it in" to a program, the way electronic components are plugged into a circuit board.

ADTs facilitate programming in the large because they reside in ever-larger libraries of program resources. Having large libraries of general resources available makes the client programs much simpler because their writers do not have to "reinvent the wheel." The modern software industry is devoting much time and effort to the development of component libraries; your study of ADTs will give you a taste of how this development is done.

In brief, ADTs are built in Ada using packages. The remainder of this chapter introduces concepts of ADTs and discusses four ADTs in particular: the predefined package Ada.Calendar and four user-written packages for calendar dates, currency quantities, employee records, and multiple spiders.

The Structure of an ADT

Abstract data types are a general concept in programming, independent of any particular programming language. An ADT consists of the specification of one or more data types and a set of operations applicable to the type or types. Generally the type is a composite type, often a record of some kind. The operations can be classified into several classes:

Constructor: A constructor creates, or constructs, an object of the type by putting its component parts together into a unified whole.
Selector: A selector selects a particular component of an object.
Inquiry: An inquiry operation asks whether an object has a particular property, for example, whether it is empty.
Input/output: As usual, an input/output operation is the communication link between the value of an object and the world outside the program, usually a human operator at the terminal or a disk file or printer.

Ada Features for ADTs

Ada provides many capabilities to help us develop ADTs. Here is a summary of the abstraction features we use in this book. We will make use of the first six in this chapter; the last two will be introduced in Chapter 11 and used to advantage in the remaining chapters.

Ada provides subtypes. This feature allows us to define a class of numeric or enumeration values and attach range constraints to it. This allows the compiler to make certain that we never assign an out-of-range value to a variable.
Ada provides record field initialization. This allows us to define a record type in such a way that each field in each variable of that type is initialized to a predetermined value.
Ada provides packages. As we have seen throughout this book, a package is an ideal way of grouping together resources--types, functions, procedures, important constants, and so on--and making them available to client programs. A package specification acts as a "contract" between the writer of the package and the writer of the client program. Furthermore, the compiler checks to make sure that the contract is followed: Everything promised in the specification must be delivered in the package body, and client programs must use the package resources correctly, for example, by calling procedures only with the correct parameters.
Ada provides private types. The private type capability enables us to write a package that provides a new type to client programs, in such a way that the client program cannot accidentally misuse values of the type by referencing information that is most properly kept private, that is, restricted for the internal use of the package body only.
Ada provides operator overloading. This allows us to write new arithmetic and comparison operators for new types and use them just as we use the predefined operators.
Ada provides user-defined exceptions. This enables the writer of a package to provide exceptions to client programs in order to signal to a client when it has done something inappropriate with the package. The writer of the client program can write exception handlers for user-defined exceptions that work exactly like the handlers we write for the predefined exceptions like Constraint_Error.
Ada provides attributes like the First and Last attributes we have used frequently thus far. Attributes make it possible to write subprograms that manipulate data structures without knowing all their details. This is especially useful in the case of arrays, where a subroutine that manipulates an array parameter can be written without knowing the array bounds: All it needs to do is inquire about the array bounds by asking for the First and Last attributes. This will be used to great advantage starting in Chapter 11.
Finally, Ada provides generic definition. Generic definition allows us to write subprograms and packages that are so general that they do not even have to know all the details of the types they manipulate; these types can be passed to the generic unit as parameters when the generic unit is instantiated. We have seen generic instantiation so far only with respect to the Ada.Text_IO libraries. Chapter 11 will introduce more about generics and show you how to write generic units of your own.

Exercises for Section 10.1

Self-Check

Explain the various kinds of operations in an ADT.