6.1 Introduction 245is that the interface of a type, which is visible to the user, is separated from the
representation and set of operations on values of that type, which are hidden
from the user. All of the types provided by a high-level programming language
are abstract data types. User-defined abstract data types are discussed in detail
in Chapter 11.
There are a number of uses of the type system of a programming language.
The most practical of these is error detection. The process and value of type
checking, which is directed by the type system of the language, are discussed
in Section 6.12. A second use of a type system is the assistance it provides for
program modularization. This results from the cross-module type checking
that ensures the consistency of the interfaces among modules. Another use of
a type system is documentation. The type declarations in a program document
information about its data, which provides clues about the program’s behavior.
The type system of a programming language defines how a type is associ-
ated with each expression in the language and includes its rules for type equiva-
lence and type compatibility. Certainly, one of the most important parts of
understanding the semantics of a programming language is understanding its
type system.
The two most common structured (nonscalar) data types in the impera-
tive languages are arrays and records, although the popularity of associative
arrays has increased significantly in recent years. Lists have been a central part
of functional programming languages since the first such language appeared
in 1959 (LISP). Over the last decade, the increasing popularity of functional
programming has led to lists being added to primarily imperative languages,
such as Python and C#.
The structured data types are defined with type operators, or constructors,
which are used to form type expressions. For example, C uses brackets and
asterisks as type operators to specify arrays and pointers.
It is convenient, both logically and concretely, to think of variables in terms
of descriptors. A descriptor is the collection of the attributes of a variable. In
an implementation, a descriptor is an area of memory that stores the attributes
of a variable. If the attributes are all static, descriptors are required only at
compile time. These descriptors are built by the compiler, usually as a part of
the symbol table, and are used during compilation. For dynamic attributes,
however, part or all of the descriptor must be maintained during execution. In
this case, the descriptor is used by the run-time system. In all cases, descrip-
tors are used for type checking and building the code for the allocation and
deallocation operations.
Care must be taken when using the term variable. One who uses only
traditional imperative languages may think of identifiers as variables, but that
can lead to confusion when considering data types. Identifiers do not have data
types in some programming languages. It is wise to remember that identifiers
are just one of the attributes of a variable.
The word object is often associated with the value of a variable and the space
it occupies. In this book, however, we reserve object exclusively for instances
of user-defined abstract data types, rather than for the values of variables of