244 Chapter 6 Data Types
T
his chapter first introduces the concept of a data type and the characteristics
of the common primitive data types. Then, the designs of enumeration and
subrange types are discussed. Next, the details of structured data types—
specifically arrays, associative arrays, records, tuples, lists, and unions—are investi-
gated. This section is followed by an in-depth look at pointers and references.
For each of the various categories of data types, the design issues are stated
and the design choices made by the designers of some common languages are
described. These designs are then evaluated.
The next three sections provide a thorough investigation of type checking,
strong typing, and type equivalence rules. The last section of the chapter briefly
introduces the basics of the theory of data types.
Implementation methods for data types sometimes have a significant impact on
their design. Therefore, implementation of the various data types is another impor-
tant part of this chapter, especially arrays.6.1 Introduction
A data type defines a collection of data values and a set of predefined operations
on those values. Computer programs produce results by manipulating data.
An important factor in determining the ease with which they can perform this
task is how well the data types available in the language being used match the
objects in the real-world of the problem being addressed. Therefore, it is crucial
that a language supports an appropriate collection of data types and structures.
The contemporary concepts of data typing have evolved over the last
55 years. In the earliest languages, all problem space data structures had to be
modeled with only a few basic language-supported data structures. For example,
in pre-90 Fortrans, linked lists and binary trees were implemented with arrays.
The data structures of COBOL took the first step away from the Fortran I
model by allowing programmers to specify the accuracy of decimal data values,
and also by providing a structured data type for records of information. PL/I
extended the capability of accuracy specification to integer and floating-point
types. This has since been incorporated in Ada and Fortran. The designers of
PL/I included many data types, with the intent of supporting a large range of
applications. A better approach, introduced in ALGOL 68, is to provide a few
basic types and a few flexible structure-defining operators that allow a program-
mer to design a data structure for each need. Clearly, this was one of the most
important advances in the evolution of data type design. User-defined types
also provide improved readability through the use of meaningful names for
types. They allow type checking of the variables of a special category of use,
which would otherwise not be possible. User-defined types also aid modifiabil-
ity: A programmer can change the type of a category of variables in a program
by changing a type definition statement only.
Taking the concept of a user-defined type a step further, we arrive at
abstract data types, which are supported by most programming languages
designed since the mid-1980s. The fundamental idea of an abstract data type