Pointers or References

The characteristic property of recursive structures which clearly distinguishes them from the fundamental structures (arrays, records, sets) is their ability to vary in size. Hence, it is impossible to assign a fixed amount of storage to a.recursively defined structure, and as a consequence a compiler cannot associate specific addresses to the components of such variables. The technique most commonly used to master this problem involves a dynamic allocation of storage, i.e., allocation of store to individual components at the time when they come into existence during program execution, instead of at translation time. The compiler then allocates a fixed amount of storage to hold the address of the dynamically allocated component instead of the component itself. For instance, the pedigree illustrated in Fig. 4.2 would be represented by individual—quite possibly non-contiguous—records, one for each person. These persons are then linked by their addresses assigned to the respective “father” and “mother” fields. Graphically, this situation is best expressed by the use of arrows or pointers (see Fig. 4.3).

It must be emphasized that the use of pointers to implement recursive structures is merely a technique. The programmer need not be aware of their existence. Storage may be allocated automatically the first time a new component is referenced. However, if the technique of using references or pointers is made explicit, more general data structures can be constructed than those definable by purely recursive data definition. In particular, it is then possible to define “infinite” or circular structures and to dictate that certain structures are shared. It has therefore become common in advanced programming languages to make possible the explicit manipulation of references to data in addition to the data themselves. This implies that a clear notational distinction must exist between data and references to data and that167 consequently data types must be introduced whose values are pointers (references) to other data. The notation we use for this purpose is the following;

The type declaration (4.4) expresses that values of type 7, are pointers to data of type T. Thus, the arrow in (4.4) is verbalized as “pointer to.” It is fundamentally important that the type of elements pointed to is evident from the declaration of T,. We say that T, is bound to T. This binding distinguishes pointers in higher-level languages from addresses in assembly codes, and it is a most important facility to increase security in programming through redundancy of the underlying notation.

Values of pointer types are generated whenever a data item is dynamically allocated. We will adhere to the convention that such an occasion be explicitly mentioned at all times. This is in contrast to the situation in which the first time that an item is mentioned it is automatically (assumed to be) allocated. For this purpose, we introduce the intrinsic procedure new. Given a pointer variable p of type T,, the statement

effectively allocates a variable of type 7, generates a pointer of type T, referencing this new variable, and assigns this pointer to the variable p (see Fig. 4.4). The pointer value itself can now be referred to as p(i.e., as the value of the pointer variable p). In contrast, the variable which is referenced by p is denoted by p}. This is the dynamically allocated variable of type T.

It was mentioned above that a variant component is essential in every recursive type to ensure finite cardinality. The example of the family predigree is of a pattern that exhibits a most frequently occurring constellation [see (4.3)], namely, the case in which the tagfield is two-valued (Boolean) and in which its value being false implies the absence of any further components. This is expressed by the declaration schema (4.6).

S(T) denotes a sequence of field definitions which includes one or more fields of type 7, thereby ensuring recursivity. All structures of a type patterned after (4.6) will exhibit a tree (or list) structure similar to that shown in Fig. 4.3. Its peculiar property is that it contains pointers to data components with a tagfield only, i.e., without further relevant information. The implementation technique using pointers suggests an easy way of saving storage space by168 letting the tagfield information be included in the value of the pointer itself. The common solution is to extend the range of values of a type 7, by a single value that is pointing to no element at all. We denote this value by the special symbol nil, and we understand that nil is automatically an element of all pointer types declared. This extension of the range of pointer values explains why finite structures may be generated without the explicit presence of variants (conditions) in their (recursive) declaration.

The new formulations of the data types declared in (4.1) and (4.3)—based on explicit pointers—are given in (4.7) and (4.8), respectively. Note that in the latter case (which originally corresponded to the schema (4.6)) the variant record component has vanished, since p}.known = false is now expressed as p = nil. The renaming of the type ped to person reflects the difference in the viewpoint brought about by the introduction of explicit pointer values. Instead of first considering the given structure in its entirety and then investigating its substructure and its components, attention is focused on the components in the first place, and their interrelationship (represented by pointers) is not evident from any fixed declaration,

The data structure representing the pedigree shown in Figs. 4.2 and 4.3 is again shown in Fig. 4.5 in which pointers to unknown persons are denoted by nil. The ensuing improvement in storage economy is obvious.

Again referring to Fig. 4.5, assume that Fred and Mary are siblings, i.e., have the same father and mother. This situation is easily expressed by replacing the two nil values in the respective fields of the two records. An implementation that hides the concept of pointers or uses a different technique of storage handling would force the programmer to represent the records of Adam and Eva twice each. Although in accessing their data for inspection it does not matter whether the two fathers (and the two mothers) are duplicated or represented by a single record, the difference is essential when selective updating is permitted. Treating pointers as explicit data items instead of as hidden implementation aids allows the programmer to express clearly where storage sharing is intended.

A further consequence of the explicitness of pointers is that it is possible to define and manipulate cyclic data structures. This additional flexibility yields, of course, not only increased power but also requires increased care by the programmer because the manipulation of cyclic data structures may easily lead to non-terminating processes.

This phenomenon of power and flexibility being intimately coupled with the danger of misuse is well-known in programming, and it particularly recalls the goto statement. Indeed, if the analogy between program structures and data structures is to be extended, the purely recursive data structure could well be placed at the level corresponding with the procedure, whereas the introduction of pointers is comparable to the use of goto statements. For, as the goto statement allows the construction of any kind of program pattern (including loops), so do pointers allow for the composition of any kind of data structure (including cycles). The parallel development of corresponding program and data structures is shown in concise form in Table 4.1.

In Chap. 3 it was shown that iteration is a special case of recursion and

where P, is a statement not involving P, is equivalent to and replaceable by the iterative statement

The analogies outlined in Table 4.1 reveal that a similar relationship holds between recursive data types and the sequence. In fact, a recursive type defined according to the schema

where T, is a type not involving T, is equivalent and replaceable by the sequential data type

This shows that recursion can be replaced by iteration in program and data definitions if (and only if) the procedure or type name occurs recursively only once at the end (or the beginning) of its definition.

The remainder of this chapter is devoted to the generation and manipulation of data structures whose components are linked by explicit pointers. Structures with specific simple patterns are emphasized in particular; recipes for handling more complex structures may be derived from those for manipulating basic formations. These are the linear list or chained sequence—the most simple case—and trees. Our preoccupation with these “building blocks” of data structuring does not imply that more involved structures do not occur in practice. In fact, the following story which appeared in a Ziirich newspaper in July 1922 is a proof that irregularity may even occur in cases which usually serve as examples for regular structures, such as (family) trees. The story tells of a man who describes the misery of his life in the following words: