The Concept of Data Type

In mathematics it is customary to classify variables according to certain important characteristics. Clear distinctions are made between real, complex, and logical variables or between variables representing individual values, or sets of values, or sets of sets, or between functions, functionals, sets of functions, and so on. This notion of classification is equally important, if not more important, in data processing. We will adhere to the principle that every constant, variable, expression, or function is of a certain type. This type essentially characterizes the set of values to which a constant belongs, or which can be assumed by a variable or expression, or which can be generated by a function.

In mathematical texts the type of a variable is usually deducible from the typeface without consideration of context; this is not feasible in computer programs. For there is usually one typeface commonly available on computer equipment (i.e., Latin letters). The rule is therefore widely accepted that the associated type is made explicit in a declaration of the constant, variable, or function, and that this declaration textually precedes the application of that constant, variable, or function. This rule is particularly sensible if one considers the fact that a compiler has to make a choice of representation of the object within the store of a computer. Evidently, the capacity of storage allocated to a variable will have to be chosen according to the size of the range of values that the variable may assume. If this information is known to a compiler, so-called dynamic storage allocation can be avoided. This is very often the key to an efficient realization of an algorithm.

The primary characteristics of the concept of type that is used throughout this text, and that is embodied in the programming language PASCAL, thus are the following [1.2]:

1. A data type determines the set of values to which a constant belongs, or which may be assumed by a variable or an expression, or which may be generated by an operator or a function.
2. The type of a value denoted by a constant, variable, or expression may be derived from its form or its declaration without the necessity of executing the computational process.
3. Each operator or function expects arguments of a fixed type and yields a result of a fixed type. If an operator admits arguments of several types (e.g., $+$ is used for addition of both integers and real numbers), then the type of the result can be determined from specific language rules.

As a consequence, a compiler may use this information on types to check the compatibility and legality of various constructs. For example, the assignment of a Boolean (logical) value to an arithmetic (real) variable may be5 detected without executing the program. This kind of redundancy in the program text is extremely useful as an aid in the development of programs, and it must be considered as the primary advantage of good high-level languages over machine code (or symbolic assembly code). Evidently, the data will ultimately be represented by a large number of binary digits, irrespective of whether or not the program had initially been conceived in a high-level language using the concept of type or in a typeless assembly code. To the computer, the store is a homogeneous mass of bits without apparent structure. But it is exactly this abstract structure which alone is enabling human programmers to recognize meaning in the monotonous landscape of a computer store.

The theory presented in this book and the programming language PASCAL specify certain methods of defining data types. In most cases new data types are defined in terms of previously defined data types. Values of such a type are usually conglomerates of component values of the previously defined constituent types, and they are said to be structured. If there is only one constituent type, that is, if all components are of the same constituent type, then it is known as the base type.

The number of distinct values belonging to a type $T$ is called the cardinality of $T$. The cardinality provides a measure for the amount of storage needed to represent a variable $x$ of the type $T$, denoted by $x : T$.

Since constituent types may again be structured, entire hierarchies of structures may be built up, but, obviously, the ultimate components of a structure must be atomic. Therefore, it is necessary that a notation is provided to introduce such primitive, unstructured types as well. A straightforward method is that of enumeration of the values that are to constitute the type. For example, in a program concerned with plane geometric figures, there may be introduced a primitive type called shape, whose values may be denoted by the identifiers rectangle, square, ellipse, circle. But apart from such programmer defined types, there will have to be some standard types that are said to be predefined. They will usually include numbers and logical values. If an ordering exists among the individual values, then the type is said to be ordered or scalar. In PASCAL, all unstructured types are assumed to be ordered; in the case of explicit enumeration, the values are assumed to be ordered by their enumeration sequence.

With this tool in hand, it is possible to define primitive types and to build conglomerates, structured types up to an arbitrary degree of nesting. In practice, it is not sufficient to have only one general method of combining constituent types into a structure. With due regard to practical problems of representation and use, a general-purpose programming language must offer several methods of structuring. In a mathematical sense, they may all be equivalent; they differ in the operators available to construct their values and to select components of these values. The basic structuring methods presented6 here are the array, the record, the set, and the sequence (file). More complicated structures are not usually defined as “static” types, but are instead “dynamically” generated during the execution of the program during which they may vary in size and shape. Such structures are the subject of Chap. 4 and include lists, rings, trees, and general finite graphs.

Variables and data types are introduced in a program in order to be used for computation. To this end, a set of operators must be available. As with data types, programming languages offer a certain number of primitive, standard (atomic) operators, and a number of structuring methods by which composite operations can be defined in terms of the primitive operators. The task of composition of operations is often considered the heart of the art of programming. However, it will become evident that the appropriate composition of data is equally fundamental and essential.

The most important basic operators are comparison and assignment, i.e., the test for equality (and order in the case of ordered types) and the command to enforce equality. The fundamental difference between these two operations is emphasized by the clear distinction in their denotation throughout this text (although it is unfortunately obscured in such widely used programming languages as Fortran and PL/I, which use the equal sign as assignment operator).

These fundamental operators are defined for most data types, but it should be noted that their execution may involve a substantial amount of computational effort if the data are large and highly structured.

Apart from test of equality (or order) and assignment, a class of fundamental and implicitly defined operators are the so-called transfer operators. They are mapping data types onto other data types. They are particularly important in connection with structured types. Structured values are generated from their component values by so-called constructors, and the component values are extracted by so-called selectors. Constructors and selectors are thus transfer operators mapping constituent types into structured types and vice versa. Every structuring method owns its particular pair of constructors and selectors that clearly differ in their denotation.

Standard primitive data types also require a set of standard primitive operators. Thus, along with the standard data types of numbers and logical values, we also introduce the conventional operations of arithmetic and propositional logic.