Representation of Array, Record, and Set Structures

The essence of the use of abstractions in programming is that a program may be conceived, understood, and verified on the basis of the laws governing the abstractions and that it is not necessary to have further insight and knowledge about the ways in which the abstractions are implemented and represented in a particular computer. Nevertheless, it is helpful for a successful programmer to have an understanding of widely used techniques for representing the basic concepts of programming abstractions, such as the fundamental data structures. It is helpful in the sense that it might enable the programmer to make sensible decisions about program and data design in the light not only of the abstract properties of structures, but also of their realizations on actual computers, taking into account a computer’s particular capabilities and limitations.

The problem of data representation is that of mapping the abstract structure into a computer store. Computer stores are—in a first approximation—arrays of individual storage cells called words. The indiceso f the words are called addresses.

var store: array[address] of word

(1.31)

The cardinalities of the types address and word vary from one computer to another. A particular problem is the great variability of the cardinality of the word. Its logarithm is called the wordsize, because it is the number of bits that a storage cell consists of.

1.10.1 Representation of Arrays

A representation of an array structure is a mapping of the (abstract) array with components of type $T$ onto the store which is an array with components of type word.

The array should be mapped in such a way that the computation of addresses of array components is as simple (and therefore efficient) as possible. The address or store index $i$ of the $j$ th array component is computed by the linear mapping function

i = i_0 + j * s \tag{1.32}

where $i_0$ is the address of the first component, and $s$ is the number of words that a component “occupies.” Since the word is by definition the smallest individually accessible unit of store, it is evidently highly desirable that $s$ be a whole number, the simplest case being $s = 1$ . If $s$ is not a whole number (and this is the normal case), then $s$ is usually rounded up to the next larger integer $\lceil s \rceil$ . Each array component then occupies $\lceil s \rceil$ words, whereby $\lceil s \rceil - s$ words are left unused (see Figs. 1.5 and 1.6). Rounding up of the number of words needed to the next whole number is called padding. The storage utilization factor $u$ is the quotient of the minimal amounts of storage needed to represent a structure and of the amounts actually used:

u = \frac{s}{s'} \doteq \frac{s}{\lceil s \rceil} \tag{1.33}

Fig. 1.5 Mapping an array onto a store. — **Fig. 1.5** Mapping an array onto a store.

Fig. 1.6 Padded representation of a record. — **Fig. 1.6** Padded representation of a record.

Since an implementor will have to aim for a storage utilization as close to31 1 as possible, and since accessing parts of words is a cumbersome and relatively inefficient process, he will have to compromise. Following are the considerations to be made:

Padding will decrease storage utilization.
Omission of padding may necessitate inefficient partial word access.
Partial word access may cause the code (compiled program) to expand and therefore to counteract the gain obtained by omission of padding.

In fact, considerations 2 and 3 are usually so dominant that compilers will always use padding automatically. We notice that the utilization factor will always be $u > 0.5$ , if $s > 0.5$ . However, if $s \le 0.5$ , the utilization factor may be significantly increased by putting more than one array component into each word. This technique is called packing. If $n$ components are packed into a word, the utilization factor is (see Fig. 1.7)

u = \frac{n \cdot s}{\lceil n \cdot s \rceil} \tag{1.34}

Fig. 1.7 Packing six components into one word. — **Fig. 1.7** Packing six components into one word.

Access to the $i$ th component of a packed array involves the computation of the word address $j$ in which the desired component is located and involves the computation of the respective component position $k$ within the word.

\begin{aligned} j &= i \ \textbf{div}\ n \\ k &= i \ \textbf{mod}\ n = i - j * n \end{aligned} \tag{1.35}

In most programming languages the programmer is given no control over the representation of the abstract data structures. However, it should be possible to indicate the desirability of packing at least in those cases in which more than one component would fit into a single word, i.e., when a gain of storage economy by a factor of 2 and more could be achieved. We introduce the convention to indicate the desirability of packing by prefixing the symbol array (or record) in the declaration by the symbol packed.

EXAMPLE

type alfa = packed array [1 .. n] of char

This feature is particularly valuable on computers with large words and relatively convenient accessibility of partial fields of words. The essential property of this prefix is that it does in no way change the meaning (or correctness) of a program. This means that the choice of an alternative representation can be easily indicated with the implied guarantee that the meaning of the program remains unaffected.

32 The cost of accessing components of a packed array can in many cases be drastically reduced if the entire array is unpacked (or packed) at once. The reason is that an efficient sequential scan over the entire array is possible, making it unnecessary to evaluate a complicated mapping function for each individual component. We therefore postulate the existence of two standard procedures pack and unpack as defined below. Assume that there are variables

u : array [a .. d] of T
p : packed array [b .. c] of T

where $a \le b \le c \le d$ are all of the same scalar type. Then

\mathit{pack}(u, i, p), \qquad (a \le i \le b-c+d) \tag{1.36}

is equivalent to

p[j] := u[j+i-b], \qquad j = b \ldots c

and

\mathit{unpack}(p, u, i), \qquad (a \le i \le b - c + d) \tag{1.37}

is equivalent to

u[j + i - b] := p[j], \qquad j = b \ldots c

1.10.2 Representation of Record Structures

Records are mapped onto a computer store (allocated) by simply juxtaposing their components. The address of a component (field) $r_i$ relative to the origin address of the record $r$ is called the component’s offset $k_i$ . It is computed as

k_i = s_1 + s_2 + \cdots + s_{i-1} \tag{1.38}

where $s_j$ is the size (in words) of the $j$ th component. The fact that all components of an array are of equal type has the consequence that

s_1 = s_2 = \cdots = s_n

and therefore

k_i = s_1 + \cdots + s_{i-1} = (i - 1) \cdot s

The generality of the record structure does not allow such a simple, linear function for offset address computation in general, and it is therefore the very reason for the requirement that record components be selectable only by fixed identifiers. This restriction has the desirable consequence that the respective offsets are known at compile time. The resulting greater efficiency of record field access is well-known.

The problem of packing may arise if several record components can be fitted into a single storage word (see Fig. 1.8). We will again assume that the desirability of packing may be indicated in a declaration by prefixing the symbol record by the symbol packed. Since offsets are computable by a compiler,33 the offset of a component within a word may also be determined by a compiler. This means that on many computers the packing of records will cause a decrease in access efficiency considerably smaller than that caused by the packing of arrays.

Fig. 1.8 Representation of a packed record. — **Fig. 1.8** Representation of a packed record.

1.10.3 Representation of Sets

A set $s$ is conveniently represented in a computer store by its characteristic function $C(s)$ . This is an array of logical values whose $i$ th component specifies the presence or absence of the value $i$ in the set. The size of the array is determined by the set type’s cardinality.

C(s_i) \equiv (i \ \textbf{in}\ s) \tag{1.39}

As an example, the set of small integers

s = [1, 4, 8, 9]

is representable by the sequence of logical values F (false) and T (true),

C(s) = (\mathit{FTFFTFFFTT})

if the base type of $s$ is the integer subrange 0 .. 9. In a computer store the sequence of logical values is represented as a so-called bitstring (see Fig. 1.9).

Fig. 1.9 Representation of a set as a bitstring. — **Fig. 1.9** Representation of a set as a bitstring.

The representation of sets by their characteristic function has the advantage that the operations of computing the union, intersection, and difference of two sets may be implemented as elementary logical operations. The following equivalences, which hold for all elements $i$ of the base type of the sets $x$ and $y$ , relate logical operations with operations on sets:

\begin{aligned} i \ \textbf{in}\ (x+y) &\equiv (i \ \textbf{in}\ x) \lor (i \ \textbf{in}\ y) \\ i \ \textbf{in}\ (x*y) &\equiv (i \ \textbf{in}\ x) \land (i \ \textbf{in}\ y) \\ i \ \textbf{in}\ (x-y) &\equiv (i \ \textbf{in}\ x) \land \neg(i \ \textbf{in}\ y) \end{aligned} \tag{1.40}

34 These logical operations are available on all digital computers, and moreover they operate concurrently on all corresponding elements (bits) of a word. It therefore appears that in order to be able to implement the basic set operations in an efficient manner, sets must be represented in a small, fixed number of words upon which not only the basic logical operations, but also those of shifting are available. Testing for membership is then implemented by a single shift and a subsequent (sign) bit test operation. As a consequence, a test of the form

x \ \textbf{in}\ [c_1, c_2, \ldots, c_n]

can be implemented in a much more efficient manner than the equivalent conventional Boolean expression

(x = c_1) \lor (x = c_2) \lor \cdots \lor (x = c_n)

A corollary is that the set structure should be used only in the case of small base types. The limit of the cardinality of base types for which a reasonably efficient implementation can be guaranteed is determined by the wordlength of the underlying computer, and it is plain that computers with large wordlengths are preferred in this respect. If the wordsize is relatively small, a representation using multiple words for a set may be chosen.