Recursive Data Types

In Chap. 2 the array, record, and set structures were introduced as fundamental data structures. They are called fundamental because they constitute the building blocks out of which more complex structures are formed and because in practice they do occur most frequently. The purpose of defining a data type, and of thereafter specifying that certain variables be of that type, is that the range of values assumed by these variables, and thereby their storage pattern, is fixed once and for all. Hence, variables declared in this way are said to be static. However, there are many problems which involve far more complicated information structures. The characteristic of these problems is that their structures change during the computation. They are therefore called dynamic structures. Naturally, the components of such structures are—at some level of detail—static, i.e., of one of the fundamental data types. This chapter is devoted to the construction, analysis, and management of dynamic information structures.

It is noteworthy that there exist some close analogies between the methods used for structuring algorithms and those for structuring data. As with all analogies, there remain some differences (otherwise they would be identities), but a comparison of structuring methods for programs and data is nevertheless illuminating.

The elementary, unstructured statement is the assignment. Its corresponding member in the family of data structures is the scalar, unstructured type. These two are the atomic building blocks for composite statements and data types. The simplest structures, obtained through enumeration or sequencing,163 are the compound statement and the record structure. They both consist of a finite (usually small) number of explicitly enumerated components, which may themselves all be different from each other. If all components are identical, they need not be written out individually: we use the for statement and the array structure to indicate replication by a known, finite factor. A choice among two or more variants is expressed by the conditional or the case statement and by the variant record structure, respectively. And finally, a repetition by an initially unknown (and potentially infinite) factor is expressed by the while or repeat statements. The corresponding data structure is the sequence (file), the simplest kind which allows the construction of types of infinite cardinality.

The question arises whether or not there exists a data structure that corresponds in a similar way to the procedure statement. Naturally, the most interesting and novel property of procedures in this respect is recursion. Values of such a recursive data type would contain one or more components belonging to the same type as itself, in analogy to a procedure containing one or more calls to itself. Like procedures, such data type definitions might be directly or indirectly recursive.

A simple example of an object that would most appropriately be represented as a recursively defined type is the arithmetic expression found in programming languages. Recursion is used to reflect the possibility of nesting, i.e., of using parenthesized subexpressions as operands in expressions. Hence, let an expression here be defined informally as follows:

A data type whose values represent such expressions can easily be described by using the tools already available with the addition of recursion:

Hence, every variable of type term consists of two components, namely, the tagfield ¢ and, if ¢ is true, the field id, or of the field subex otherwise.

These expressions may be visualized by the patterns in Fig. 4.1, which exhibit their nested, recursive structure, and they determine the layout or mapping of these expressions onto a store.

A second example of a recursive information structure is the family pedigree: Let a pedigree be defined by (the name of) a person and the two pedigrees of his parents. This definition leads inevitably to an infinite structure. Real pedigrees are bounded because at some level of ancestry information is missing. This can be taken into account by again using a variant structure as shown in (4.3).

(Note that every variable of type ped has at least one component, namely, the tagfield called known. If its value is true, then there are three more fields; otherwise, there are none.) The particular value denoted by the (recursive) record constructor

is depicted in Fig. 4.2 in a way that may suggest a possible storage pattern. (Since only a single record type is involved, we have omitted the type identifier ped preceding each constructor).

The important role of the variant facility becomes clear; it is the only means by which a recursive data structure can be bounded, and it is therefore an inevitable companion of every recursive definition. The analogy between program and data structuring concepts is particularly pronounced in this case. A conditional statement must necessarily be part of every recursive procedure in order that execution of the procedure can terminate. Termination of execution evidently corresponds to finite cardinality.