Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Abstract Data Types

A variable in a procedural programming language such as Fortran , Pascal , C , and C++ , is an abstraction. The abstraction comprises a number of attributes --name , address , value , lifetime , scope , type , and size . Each attribute has an associated value. E.g., if we declare an integer variable in C++, int x, we say that the name attribute has value ``x'' and that the type attribute has value ``int''.

Unfortunately, the terminology can be somewhat confusing: The word ``value'' has two different meanings--in one instance it denotes one of the attributes and in the other it denotes the quantity assigned to an attribute. E.g., after the assignment statement x = 5, the value attribute has the value five.

The name of a variable is the textual label used to refer to that variable in the text of the source program. The address of a variable denotes is location in memory. The value attribute is the quantity which that variable represents. The lifetime of a variable is the interval of time during the execution of the program in which the variable is said to exist. The scope of a variable is the set of statements in the text of the source program in which the variable is said to be visible . The type of a variable denotes the set of values which can be assigned to the value attribute and the set of operations which can be performed on the variable. Finally, the size attribute denotes the amount of storage required to represent the variable.

The process of assigning a value to an attribute is called binding . When a value is assigned to an attribute, that attribute is said to be bound to the value. Depending on the semantics of the programming language, and on the attribute in question, the binding may be done statically by the compiler or dynamically at run-time. E.g., in C++ the type of a variable is determined at compile time--static binding . On the other hand, the value of a variable is usually not determined until run-time--dynamic binding .

In this chapter we are concerned primarily with the type attribute of a variable. The type of a variable specifies two sets:

a set of values; and,
a set of operations.

For example, when we declare a variable, say x, of type int, we know that x can represent an integer in the range

(assuming 32-bit integers) and that we can perform operations on x such as addition, subtraction, multiplication, and division.

The type int is an abstract data type in the sense that we can think about the qualities of an int apart from any real thing having that quality. In other words, we don't need to know how ints are represented nor how the operations are implemented to be able to be able to use them or reason about them.

In designing object-oriented programs, one of the primary concerns of the programmer is to develop an appropriate collection of abstractions for the application at hand, and then to define suitable abstract data types to represent those abstractions. In so doing, the programmer must be conscious of the fact that defining an abstract data type requires the specification of both a set of values and a set of operations on those values.

Indeed, it has been only since the advent of the so-called object-oriented programming languages that the we see programming languages which provide the necessary constructs to properly declare abstract data types. E.g., in C++, the class construct is the means by which both a set of values and an associated set of operations is declared. Compare this with the struct construct of C or Pascal's record , which only allow the specification of a set of values!