The Record Structure

The most general method to obtain structured types is to join elements of arbitrary, possibly themselves structured, types into a compound. Examples from mathematics are complex numbers, composed of two real numbers, and coordinates of points, composed of two or more real numbers according to the dimensionality of the space spanned by the coordinate system. An example from data processing is describing people by a few relevant characteristics, such as their first and last names, their dates of birth, sex, and marital status.

In mathematics such a compound type is called the Cartesian product of its constituents types. This stems from the fact that the set of values defined by this compound type consists of all possible combinations of values, taken one from each set defined by each constituent type. Thus, the number of such combinations, also called n-tuples, is the product of the number of elements in each constituent set, that is, the cardinality of the compound type is the product of the cardinalities of the constituent types.

In data processing, composite types, such as descriptions of persons or objects, usually occur in files or “data banks” and record the relevant characteristics of a person or object. The word record has therefore become widely accepted to describe a compound of data of this nature, and we adopt this nomenclature in preference to the term Cartesian product.

In general, a record type $T$ is defined as follows:

type T = record s₁: T₁;
                s₂: T₂;
                 ...
                sₙ: Tₙ
         end

(1.19)

\text{Cardinality}\ (T) = \text{cardinality}\ (T_1) * \cdots * \text{cardinality}\ (T_n)

Examples

type Complex = record re: real;
                      im: real
               end

type Date = record   day: 1 .. 31;
                   month: 1 .. 12;
                    year: 1 .. 2000
            end

type Person = record name: alfa;
                     firstname: alfa;
                     birthdate: Date;
                     sex: (male, female);
                     marstatus: (single, married,
                        widowed, divorced)
              end

A value of type $T$ may be constructed by a record constructor and subsequently assigned to a variable of that type:

x := T(x_1, x_2, \ldots, x_n) \tag{1.20}

where the $x_i$ ’s are values of the constituent types $T_i$ .

Given record variables

z: Complex
d: Date
p: Person

particular values may be assigned, for example, as follows (see Fig. 1.3):

z := Complex (1.0,-1.0)
d := Date (1,4,1973)
p := Person (‘WIRTH’, ‘CHRIS’, Date (18,1,1966), male, single)

Fig. 1.3 Records of the types *complex*, *date*, and *person*. — **Fig. 1.3** Records of the types *complex*, *date*, and *person*.

The identifiers $s_1, \ldots, s_n$ introduced by a record type definition are the names given to the individual components of variables of that type, and they are used in record selectors applied to record structured variables. Given a variable $x\colon T$ , its $i$ th component is denoted by

\boxed{x.s_i} \tag{1.21}

Selective updating of $x$ is achieved by using the same selector denotation on18 the left side in an assignment statement:

x.s_i := x_i

where $x_i$ is a value (expression) of type $T_i$ .

Given the record variables

z: Complex
d: Date
p: Person

the following are selectors of components of $z$ , $d$ , and $p$ :

z.im               (of type real)
d.month            (of type 1 .. 12)
p.name             (of type alfa)
p.birthdate        (of type Date)
p.birthdate.day    (of type 1 .. 31)

The example of the type Person shows that a constituent of a record type may itself be structured. Thus, selectors may be concatenated. Naturally, different structuring types may also be used in a nested fashion. For example, the $i$ th component of an array $a$ being a component of a record variable $r$ is denoted by

r.a[i] ,

and the component with the selector name $s$ of the $i$ th record structured component of the array $a$ is denoted by

a[i].s

It is a characteristic of the Cartesian product that it contains all combinations of elements of the constituent types. But it must be noted that in practical application not all of them may be “legal,” i.e., meaningful. For instance, the type Date as defined above contains the values

(31,4,1973) \quad \text{and} \quad (29,2,1815)

which are both dates of days that never occurred. Thus, the definition of this type does not mirror the real-world situation; but it is close enough for practical purposes, and it is the responsibility of the programmer to ensure that meaningless values never occur during the execution of his program.

The following short excerpt from a program shows the use of record variables. Its purpose is to count the number of “Persons” represented by the array variable $a$ which are both female and single:

var a: array[1 .. N] of Person;
    count: integer;
count := 0;
for i := 1 to N do
   if (a[i].sex = female) ∧ (a[i].marstatus = single) then
      count := count+1

(1.22)

The relevant loop-invariant is

\mathit{count} = C(i)

where $C(i)$ is the number of single, female members of the subset $a_1 \ldots a_i$ .

A notational variant of the above statement uses a construct that is called a with-statement:

for i := 1 to N do
   with a[i] do
      if (sex = female) ∧ (marstatus = single) then
         count := count+1

(1.23)

The meaning of with r do s is that selector names of the type of the variable $r$ may be used without prefix within the statement $s$ and are taken to refer to the variable $r$ . The with-statement thus serves to abbreviate the program text as well as to prevent re-evaluation of the storage address of the indexed component a[i].

In a further example, we assume that (possibly in order to find them more quickly) certain groups of persons in the array $a$ are linked together. The linking information is represented by an additional component of the record structure Person, named link. The links connect records into a linear chain so that each person’s successor and predecessor may be found easily. The interesting property of this linking technique is that the chain may be traversed in both directions on the basis of a single number stored in each record. The technique works as follows.

Assume that the indices of three consecutive members of the chain are $i_{k-1}, i_k, i_{k+1}$ . The link value of the $k$ th member is chosen to be $i_{k+1} - i_{k-1}$ . Traversing the chain in the forward direction, $i_{k+1}$ is determined from the two current index variables $x = i_{k-1}$ and $y = i_k$ as

i_{k+1} = x + a[y].\mathit{link}\ ,

whereas traversing the chain in the backward direction, $i_{k-1}$ is determined from $x = i_{k+1}$ and $y = i_k$ as

i_{k-1} = x - a[y].\mathit{link}

An example is linking all persons of equal sex in a table (see Table 1.2).

Table 1.2. Array with elements of type *Person*. — **Table 1.2.** Array with elements of type *Person*.

The record structure and the array stucture have the common property that both are “random-access” structures. The record is more general in the sense that there is no requirement that all constituent types must be identical. In turn, the array offers greater flexibility by allowing its component selectors to be computable values (represented by expressions), whereas the selectors of record components are fixed identifiers declared in the record type definition.