The Sequential File Structure

The common characteristic of the data structures presented so far, namely, the array, the record, and the set structure, is that their cardinality is finite (provided that the cardinality of the types of their components is finite). Therefore, they present little difficulty for the implementor; suitable representations are readily found on any digital computer.

Most so-called advanced structures—sequences, trees, graphs, etc.—are characterized by their cardinality being infinite. This difference to the fundamental structures with finite cardinality is of profound importance, and it has significant practical consequences. As an example, we define the sequence structure as follows:

A sequence with base type $T_0$ is either the empty sequence or the concatenation of a sequence (with base type $T_0$) with a value of type $T_0$.

The sequence type $T$ thus defined comprises an infinity of values. Each value itself contains a finite number of components of type $T_0$, but this number is unbounded, i.e., for every such sequence it is possible to construct a longer one.

Analogous considerations apply to all other “advanced” data structures. The prime consequence is that the necessary amount of store to represent a value of an advanced structural type is not known at compile time; in fact, it may vary during the execution of the program. This requires some scheme35 of dynamic storage allocation in which storage is occupied as the respective values “grow” and is possibly released for other uses when values “shrink.” It is therefore plain that the question of representation of advanced structures is a subtle and difficult one and that its solution will crucially influence the efficiency of a process and the economy exercised on the usage of storage. A suitable choice can be made only on the basis of knowledge of the primitive operations to be performed on the structure and of the frequencies of their execution. Since none of this information is known to the designer of a language and its compiler, he is well advised to exclude advanced structures from a (general-purpose) language. It also follows that programmers should avoid their use whenever their problem can be treated by using fundamental structures only.

The dilemma of having to provide advanced data structuring facilities without information about their potential usage is circumvented in most languages and compilers by recognizing and using the fact that all advanced structures are composed either of unstructured elements or of fundamental structures. Arbitrary structures may then be generated by explicit, programmer specified operations, if facilities for the dynamic allocation of the components and for the dynamic linking and referencing of components are provided. Techniques for generating and manipulating these advanced structures are treated in Chapter 4.

There exists, however, one structure that is advanced in the sense that its cardinality is infinite, but which is used so widely and so frequently that its inclusion in the set of basic structures is almost mandatory: the sequence. In order to describe the abstract notion of sequence, the following terminology and notation are introduced:

1. $\langle\ \rangle$ denotes the empty sequence.

2. $\langle x_0 \rangle$ denotes the sequence consisting of the single component $x_0$; it is called a singleton sequence.

3. If $x = \langle x_1, \ldots, x_m \rangle$ and $y = \langle y_1, \ldots, y_n \rangle$ are sequences, then

   $$x \mathbin{\&} y = \langle x_1, \ldots, x_m, y_1, \ldots, y_n \rangle \tag{1.41}$$

   is the concatenation of $x$ and $y$.

4. If $x = \langle x_1, \ldots, x_n \rangle$ is a non-empty sequence, then

   $$\mathit{first}(x) = x_1 \tag{1.42}$$

   denotes the first element of $x$.

5. If $x = \langle x_1, \ldots, x_n \rangle$ is a non-empty sequence, then

   $$\mathit{rest}(x) = \langle x_2, \ldots, x_n \rangle \tag{1.43}$$

   is the sequence $x$ without its first component. As a consequence, we obtain the invariant relation

   $$\langle \mathit{first}(x) \rangle \mathbin{\&} \mathit{rest}(x) \equiv x \tag{1.44}$$

36 The introduction of these notations does not mean that they will be used in actual programs to be obeyed by real computers. In fact, it is essential that the concatenation operation is not used in its generality and that the handling of sequences is confined to the application of a carefully selected set of operators, which ensure a certain discipline of usage, but which are themselves defined in terms of the abstract notions of the sequence and of concatenation. A careful choice of the set of sequence operators enables implementors to find suitable and efficient representations of sequences on any given storage medium; this ensures that the associated mechanism of dynamic storage allocation can be sufficiently simple to enable the programmer to work without concern for its details.

In order to make it clear that the sequence to be introduced as a basic data structure permits only the application of a restricted set of operators that essentially allow only strictly sequential access to components, this structure is called a sequential file or, for short, simply file. In close analogy to the notations for array and set type definitions, a file type is defined by the formula

type T = file of T₀

expressing that any file of type $T$ consists of 0 or more components of type $T_0$.

EXAMPLES

type text = file of char
type deck = file of card

The essence of sequential access is that at any time only a single, specific component of the sequence is immediately accessible. This component is specified by a current position of the access mechanism. It may be changed by the file operators, usually either to the next component or to the first of the entire sequence. We formally express the file position by regarding a file $x$ to consist of two parts, a part $x_L$ to its left and a part $x_R$ to its right. It is plain that the equation

expresses an invariant relationship.

A second, most important consequence of sequential access is that the processes of constructing and of scanning a sequence are distinct and cannot be mixed in arbitrary order. Thus, a file is constructed by repeatedly appending components (at its end), and it may subsequently be inspected by a sequential scan. It is therefore customary to consider a file as being in one of two states: either in the state of being constructed (written) or of being scanned (read).

37 The advantage of strictly sequential access is particularly pronounced if files are to be allocated on secondary storage media, that is, if transfers between different media are involved. The sequential access method is the only one in which the intricacies of mechanisms required by such transfers can be successfully hidden from the programmer. In particular, it allows for the application of simple buffering techniques that alone guarantee optimal usage of the various resources available in a complex computer system.

There exist certain storage media in which the sequential access is indeed the only possible one. Among them are evidently all kinds of tapes. But even on magnetic drums and disks each recording track constitutes a storage facility allowing only sequential access. Strictly sequential access is the primary characteristic of every mechanically moving device and of some other ones as well.

1.11.1 Elementary File Operators

We now proceed to formulate the abstract notion of sequential access through a set of concrete elementary file operators available to the programmer. They are defined in terms of the notions of sequence and concatenation. There is an operator to initiate the process of file generation, one to initiate the scan, one to append a component at the tail of the sequence, and one to proceed in scanning to the next component. The latter two are here postulated in a form in which they involve an implicit, auxiliary variable that represents a buffer. We assume that such a buffer is automatically associated with every file variable $x$, and we denote it by $x{\uparrow}$. Clearly, if $x$ is of type $T$, then $x{\uparrow}$ is of its base type $T_0$.

1. Constructing the empty sequence. The operation

   $$\mathit{rewrite}(x) \tag{1.47}$$

   stands for the assignment

   $$x := \langle\ \rangle$$

   This operation is used to overwrite the current $x$ and to initiate the process of constructing a new sequence, and corresponds to rewinding a tape.

2. Extending a sequence. The operation

   $$\mathit{put}(x) \tag{1.48}$$

   stands for the assignment

   $$x := x \mathbin{\&} \langle x{\uparrow} \rangle$$

   which effectively appends the value $x{\uparrow}$ to the sequence $x$.

3. Initiation of a scan. The operation

   $$\mathit{reset}(x) \tag{1.49}$$

   38stands for the simultaneous assignments

   $$\begin{aligned} x_L &:= \langle\ \rangle \\ x_R &:= x \\ x{\uparrow} &:= \mathit{first}(x) \end{aligned}$$

   This operation is used to initiate the process of reading a sequence.

4. Proceeding to the next component. The operation

   $$\mathit{get}(x) \tag{1.50}$$

   stands for the simultaneous assignments

   $$\begin{aligned} x_L &:= x_L \mathbin{\&} \langle \mathit{first}(x_R) \rangle \\ x_R &:= \mathit{rest}(x_R) \\ x{\uparrow} &:= \mathit{first}(\mathit{rest}(x_R)) \end{aligned}$$

   Note that $\mathit{first}(s)$ is defined only if $s \ne \langle\ \rangle$.

The operators rewrite and reset notably do not depend on the position of the file prior to their execution. They reposition the file in any case to its beginning.

When scanning a sequence, it is necessary to be able to recognize the end of the sequence, because otherwise the assignment

represents an undefined operation. Reaching the end of the file is evidently synonymous with the condition that the right part $x_R$ is empty. Therefore, we introduce the predicate

to mean that the end of the file is reached. The operation get(x) can therefore only be executed if the predicate eof(x) is false.

In principle it is possible to express all operations on files in terms of the four basic file operators. In practice, however, it is often natural to combine the operation of advancing the file position (get or put) with the access to the buffer variable. We therefore postulate two further procedures; they are expressible in terms of the basic operators. Let $v$ be a variable and $e$ an expression of the file component type $T_0$. Then

and

The advantage of the use of read and write in place of get and put lies not only in brevity, but also in conceptual simplicity. For, it is now possible to39 ignore the existence of the buffer variable $x{\uparrow}$, whose value is sometimes undefined. The buffer variable may, however, be useful for the purpose of “looking ahead.”

The prerequisite conditions for the execution of the two procedures are

Upon reading, the predicate eof(x) becomes true as soon as the last element of the file $x$ has been read. These considerations are neatly incorporated in two program schemata for the sequential construction and processing of a file $x$. The statements $R$ and $S$ and the predicate $p$ are additional parameters of the schemata.

Writing a file $x$:

rewrite(x);
while p do
   begin R(v); write(x,v)
   end

Reading a file $x$:

reset(x);
while ¬eof(x) do
   begin read(x,v); S(v)
   end

1.11.2 Files with Substructure

In the majority of applications, large files require some kind of substructure. For instance, a book, although it may be regarded as a single sequence of characters, is subdivided into chapters or paragraphs. The purpose of the substructure is to provide some explicit points of reference, some coordinates, in order to facilitate orientation in the long sequence of information. Existing storage devices often provide some facilities for representing such points of reference (e.g., tape marks) and have the capability of locating them with greater speed than is obtained when all information in between such points is scanned.

In our framework of notation the natural way to introduce a first level of substructure is to regard such a file as a sequence of components which are themselves sequences, that is, as a file of files. Assuming that the ultimate components (or units) are of type $U$, the substructures are then of type

40 and the entire file is of type

It is plain that in this manner files can be constructed with a partitioning to an arbitrary depth of nesting. In general, a type $T_n$ can be defined by the recursive relation

and $T_0 = U$. Such files are often called multilevel files, and a component of type $T_i$ is said to be a segment of level $i$. An example of a multilevel file is a book in which the levels of segmentation correspond to chapters, sections, paragraphs, and lines. However, by far the most common case is, of course, the file with a single level of segmentation.

This single level segmented file is by no means identical to an array of files. After all, the number of segments is variable, and the file may still be extended only at its end. Remaining within the framework of our notation introduced so far, and assuming a file defined by

$x{\uparrow}$ denotes the currently accessible segment, $x{\uparrow\uparrow}$ the currently accessible unit component. Accordingly, put(x↑) and get(x↑) refer to a unit component, whereas put(x) and get(x) denote the operations of appending and proceeding to the next segment.

Segmented files are readily implemented on virtually all sequential storage devices including tapes. Their segmentation has not changed their primary characteristic of permitting only sequential access either to individual components or—by a possibly faster skipping mechanism—to segments. Other storage devices—notably magnetic drums and disks—usually contain a number of tracks, each of which represents a proper sequential device but is usually too short to accommodate an entire file. Consequently, files on disks are usually spread over several tracks and contain appropriate bookkeeping information linking the tracks. It is plain that the starting point of each track constitutes a natural segment marker, which might easily be accessed even more directly than markers on any purely sequential medium. An indexable table in primary store might, for instance, be used to address the tracks where segments begin, and to indicate the actual lengths of the segments (see Fig. 1.10).

This leads us to the so-called indexed files (sometimes also called direct access files). Actually, drums and disks are organized in a way that each track contains many physical marks at which the reading or writing may start. Therefore, it is not necessary for each segment to occupy a full track because it would result in a poor storage utilization if segments are short in comparison with the track length. The storage line between two marks is called a physical segment (or sector) in contrast to the logical segment which is a 41meaningful entity in the program’s data structure. Clearly, each physical segment houses one logical segment at most, and each logical segment occupies at least one physical segment (even if it is empty). It should be kept in mind that even if they are called “direct access” files, the average time to locate a segment, the so-called latency time, is half the revolution time of the disk.

Indexed files retain the essential characteristic that writing proceeds sequentially at its end. They are therefore particularly useful in applications in which changes occur relatively infrequently. Changes are made by either extending or by recopying and updating the entire file. Inspection may occur in a much more selective and faster manner via the index points. This is the typical situation for so-called data banks.

Systems that allow selective rewriting of parts in the middle of a file are generally difficult and hazardous to use because the new portions of information must be of the same size as the old ones that they replace. Moreover, in applications involving large amounts of data, selective updating is not recommended because of the basic rule that upon any failure—be it caused by an erroneous program or by malfunctioning equipment—there should be a state of the data on which to fall back in order to resume and repeat the process that failed. Therefore, updating is usually made in toto, such that the old file is replaced by the new, updated copy, only after subsequent verification has established that the new file is valid. For the purpose of updating, the sequential organization is by far the best from the point of view of reliability. It is to be much preferred over more sophisticated organizations of large data sets, which may be more efficient, but often result in a total loss of data upon failure of the equipment.

1.11.3 Texts

Files whose components are of type char play an especially important role in computing and data processing: They constitute the interface between the computing machines and their human users. The legible input provided by programmers as well as the legible output representing the computed results42 are sequences of characters. This data type shall therefore be given a standard name:

type text = file of char

Communication between a computing process and its human inventor is ultimately established by an interface that can be represented as two textfiles. One of them contains the input to the computing process, the other the computed results called output. We shall henceforth assume the existence of these two files in all programs, and their declaration as being

var input, output: text

With due regard to the assumption that these files represent the standard input and output media of a computer system (such as a card reader and a line printer), we will assume that the file input can be read only and the file output can be written only.

Since the two standard files are used predominantly, we postulate that if the first parameter of the procedures read and write is not a file variable, then input and output shall be assumed by default. Moreover, we take the liberty of providing the two standard procedures with an arbitrary number of arguments. These notational conventions can be summarized as follows:

read(x1, ..., xn)  stands for  read(input, x1, ..., xn)
write(x1, ..., xn)  stands for  write(output, x1, ..., xn)
read(f, x1, ..., xn)  stands for
   begin read(f,x1); ... ; read(f,xn) end
write(f, x1, ..., xn)  stands for
   begin write(f,x1); ... ; write(f,xn) end

Texts are typical examples of sequences displaying a substructure. The usual units of substructure are the chapters, paragraphs, and lines. An often-used method of representing this substructure in textfiles is the use of special separator characters. The blank character is the best-known example, but similar separators may be used to mark the ends of lines, paragraphs, and chapters. For instance, the widely used ISO character set (including its American version ASCII) contains several such elements, called control characters (see Appendix A).

In this book, we refrain from using specific separator characters and specifying a definite method of substructure representation. Instead, we think of a text as a file consisting of sequences of character sequences representing individual lines. Also, we constrain the discussion to a single level of substructure, namely, the line. However, instead of looking at texts as files of files of printable characters, we regard them as files of characters, and we introduce additional operators and predicates to manipulate, i.e., mark and recognize lines. Their effects may best be understood if one assumes that lines are separated43 by (hypothetical) separator characters (not belonging to the type char) and if their task is considered to be the insertion and recognition of such separators. Additional operators are the following:

writeln(f) Append a line marker to the file $f$.

readln(f) Skip characters on file $f$ up to the one immediately following the next line marker.

eoln(f) A Boolean function. True, if the file position had been advanced to a marker; false otherwise. (We postulate that if eoln(f) is true, then f↑ = blank.)

We are now in a position to formulate two program schemata for writing and reading texts similar to those for “writing” and “reading” other files [see (1.52) and (1.53)]. These schemata assume a textfile $f$ and pay due attention to the generation and recognition of line structure. Let $R(x)$ be a statement assigning a value to $x$ (of type char) and defining conditions $p$ and $q$ with meanings “this was the last character of the line” and “this was the last character of the file.” Let $U$ be a statement to be executed at the beginning of each line read, $S(x)$ a statement to be executed for each character $x$ of the file, and $V$ a statement executed at the end of each line.

Writing a text $f$.

rewrite(f);
while ¬q do
   begin
      while ¬p do
         begin R(x); write(f,x)
         end ;
      writeln(f)
   end

Reading a text $f$.

reset(f);
while ¬eof(f) do
   begin U;
      while ¬eoln(f) do
         begin read(f,x); S(x)
         end ;
      V; readln(f)
   end

44 There are cases in which the line structure of a text does not represent any particularly relevant information. Our assumption about the buffer variable’s value upon encountering a line marker [see definition of eoln(f)] allows a simple program schema to be used in these situations. Note that according to the definition of eoln each end of a line appears as an additional blank character.

while ¬eof(f) do
   begin read(f,x); S(x)
   end

In most programming languages it is customary to admit arguments of type integer or real to read and write procedures. This generalization would be straightforward if the types integer and real were defined as arrays of characters whose elements would denote the individual digits of the numbers. Languages strongly oriented towards commercial applications do indeed adhere to such definitions, and they require a representation of numbers in terms of decimal digits and of the decimal number system. The significant advantage of introducing the data types integer and real as fundamental types is that such detailed specifications may be omitted and that a computing system may use different representations of numbers which may be much more suitable to its purpose. In fact, systems oriented toward scientific calculations invariably choose a binary representation that is in most respects superior to the decimal representation.

This implies, however, that a programmer cannot assume that numbers can be read from or written onto textfiles without accompanying conversion operations. It is customary to hide these conversion operations behind read and write statements with arguments of numeric types. The professional programmer, however, is aware that such statements (so-called I/O statements) incorporate two distinct functions: data transfer between different storage media and transformations of data representation. The latter may be quite complex and time-consuming.

In the subsequent chapters of this book, read and write statements with numeric arguments will be used according to the rules of the programming language PASCAL. These rules allow for a certain kind of format specification to control the transformation process. The format specification indicates the number of desired digits in the case of write statements. This number of characters, also called “field width,” is written immediately after the argument as follows:

write(f, x: n)

The argument $x$ is to be written on file $f$; its value is converted into a sequence of (at least) $n$ characters; if necessary, the digits are preceded by a sign and a suitable number of blanks.

45 Further details are unnecessary for understanding the later program examples of this book. Two examples of routines for the conversion of number representation are included here (Programs 1.3 and 1.4), however, for the sake of exhibiting the costly complexity of such operations which are usually assumed implicitly in write statements. The two procedures represent the conversion of real numbers from decimal representation to an arbitrary “internal” representation and vice versa. (The constants in the headings are determined by the properties of the floating-point number format of the CDC 6000 computer: 11-bit binary exponent and 48-bit mantissa. The function expo (x) denotes the exponent of $x$.)

procedure readreal (var f: text; var x: real);
   { read real number x from file f}
   {the following are system dependent constants}
   const t48 = 281474976710656;     {= 2**48}
      limit  =  56294995342131;     {= t48 div 5}
      z = 27;      {= ord('0') }
      lim1 = 322;       { maximum exponent }
      lim2 = -292;    { minimum exponent }
   type posint = 0 .. 323;
   var ch: char; y: real; a,i,e: integer;
      s,ss: boolean;      { signs }
   function ten(e: posint): real; { = 10**e, 0<e<322 }
      var i: integer; t: real;
   begin i := 0; t := 1.0;
      repeat if odd(e) then
         case i of
         0: t := t * 1.0E1;
         1: t := t * 1.0E2;
         2: t := t * 1.0E4;
         3: t := t * 1.0E8;
         4: t := t * 1.0E16;
         5: t := t * 1.0E32;
         6: t := t * 1.0E64;
         7: t := t * 1.0E128;
         8: t := t * 1.0E256
         end ;
         e := e div 2; i := i+1
      until e = 0;
      ten := t
   end ;
   begin
      {skip leading blanks}
      while f↑=' ' do get(f);
      ch := f↑ ;
      if ch = '-' then
         begin s := true; get(f); ch := f↑
         end else
         begin s := false;
            if ch = '+' then
            begin get(f); ch := f↑
            end
         end ;
      if ¬(ch in ['0' .. '9']) then
      begin message (' DIGIT EXPECTED'); halt;
      end ;
      a := 0; e := 0;
      repeat if a < limit then a := 10*a + ord(ch)-z else e := e+1;
         get(f); ch := f↑
      until ¬(ch in ['0' .. '9']);
      if ch = '.' then
      begin { read fraction } get(f); ch := f↑;
         while ch in ['0' .. '9'] do
         begin if a < limit then
               begin a := 10*a + ord(ch)-z; e := e-1
               end ;
            get(f); ch := f↑
         end
      end ;
      if ch = 'E' then
      begin { read scale factor } get(f); ch := f↑;
         i := 0;
         if ch = '-' then
         begin ss := true; get(f); ch := f↑
         end else
         begin ss := false; if ch = '+' then
            begin get(f); ch := f↑
            end
         end ;
         while ch in ['0' .. '9'] do
         begin if i<limit then begin i := 10*i + ord(ch)-z end;
            get(f); ch := f↑
         end ;
         if ss then e := e-i else e := e+i
      end ;
      if e < lim2 then
         begin a := 0; e := 0
         end else
      if e > lim1 then
      begin message(' NUMBER TOO LARGE '); halt end;
      { 0 < a < 2**49 }
      if a ≥ t48 then y := ((a+1) div 2) * 2.0 else y := a;
      if s then y := -y;
      if e < 0 then x := y/ten(-e) else
      if e ≠ 0 then x := y*ten(e) else x := y ;
      while (f↑ = ' ') ∧ (¬eof(f)) do get(f);
end {readreal}

procedure writereal (var f: text; x: real; n: integer);
   {write real number x with n characters in decimal flt.pt. format}
   {the following constants depend on the underlying floating-point representa-
   tion of real numbers}
   const t48 = 281474976710656; {= 2**48; 48 = size of mantissa}
         z = 27;     { ord('0') }
   type posint = 0 .. 323;     {range of decimal exponent}
   var c,d,e,e0,e1,e2,i: integer;

   function ten(e: posint): real;      { 10**e, 0<e<322 }
      var i: integer; t: real;
   begin i := 0; t := 1.0;
      repeat if odd(e) then
         case i of
          0: t := t * 1.0E1;
          1: t := t * 1.0E2;
          2: t := t * 1.0E4;
          3: t := t * 1.0E8;
          4: t := t * 1.0E16;
          5: t := t * 1.0E32;
          6: t := t * 1.0E64;
          7: t := t * 1.0E128;
          8: t := t * 1.0E256
         end ;
         e := e div 2; i := i+1
      until e = 0;
      ten := t
   end { ten } ;
begin { at least 10 characters needed: b+9.9E+999 }
   if x = 0 then
   begin repeat write(f,' '); n := n-1
         until n ≤ 1;
      write(f, '0')
   end else
   begin
      if n ≤ 10 then n := 3 else n := n-7;
      repeat write(f, ' '); n := n-1
      until n ≤ 15;
      { 1 < n ≤ 15,  number of digits to be printed }
      begin { test sign, then obtain exponent }
         if x < 0 then
            begin write(f, '-'); x := -x
            end else write (f, ' ');
         e := expo (x);  {e = entier(log2(abs(x)))}
         if e ≥ 0 then
            begin e := e*77 div 256 +1; x := x/ten(e);
               if x ≥ 1.0 then
                  begin x := x/10.0; e := e+1
                  end
            end else
            begin e := (e+1)*77 div 256; x := ten(-e)*x;
               if x < 0.1 then
                  begin x := 10.0*x; e := e-1
                  end
            end ;
         { 0.1 ≤ x < 1.0 }
         case n of     { rounding }
           2: x := x+0.5E-2;
           3: x := x+0.5E-3;
           4: x := x+0.5E-4;
           5: x := x+0.5E-5;
           6: x := x+0.5E-6;
           7: x := x+0.5E-7;
           8: x := x+0.5E-8;
           9: x := x+0.5E-9;
          10: x := x+0.5E-10;
          11: x := x+0.5E-11;
          12: x := x+0.5E-12;
          13: x := x+0.5E-13;
          14: x := x+0.5E-14;
          15: x := x+0.5E-15
         end ;
         if x ≥ 1.0 then
            begin x := x * 0.1; e := e+1;
            end ;
         c := trunc(x,48); {= trunc(x*(2**48))}
         c := 10*c; d := c div t48;
         write(f, chr(d+z), '.');
         for i := 2 to n do
         begin c := (c - d*t48) * 10; d := c div t48;
            write(f, chr(d+z))
         end ;
         write(f, 'E'); e := e-1;
         if e < 0 then
            begin write(f, '-'); e := -e
            end else write(f, '+');
         e1 := e * 205 div 2048; e2 := e - 10*e1;
         e0 := e1 * 205 div 2048; e1 := e1 - 10*e0;
         write(f, chr(e0+z), chr(e1+z), chr(e2+z))
      end
   end
end {writereal}

1.11.4 A File Editing Program

As an example of an application of sequential structures, we pose the following problem, which moreover serves to demonstrate a method of developing and explaining programs. This method is called stepwise refinement [1.4, 1.6] and will be used to explain many algorithms throughout this book.

The problem is to develop a program which edits a text $x$ into a text $y$. Editing means deleting or replacing specific lines or inserting new lines. Editing is governed by a sequence of editing instructions represented by the standard text input as follows:

I, $m$. Insertion of text after the $m$th line.

D, $m$, $n$. Deletion of lines $m$ to $n$.

R, $m$, $n$. Replacement of lines $m$ to $n$.

E. Terminate the editing process.

Each instruction is written as a line in the standard file input, which we call50 the instruction file. $m$ and $n$ are decimal line numbers, and insertion texts are to follow the $I$ and $R$ instructions immediately. They are terminated by an empty line.

We postulate that editing instructions are issued (sequenced) with strictly increasing line numbers. This rule immediately suggests a strictly sequential processing of the input text $x$. It is plain that the state of the process must be characterized by the current position of $x$ in terms of the number of the line currently under investigation.

Let us now assume that the editing program is to be used in an interactive fashion and that therefore the instruction file represents, for instance, the data originating at a keyboard terminal. In this mode of operation it is highly desirable that the operator receives some sort of feedback. An appropriate and useful form of feedback is the text of that line to which the last instruction caused the process to advance. We call this line the current line. An important consequence of the new requirement to print the current line after each instruction is that the current line must be represented by an explicit variable in which the line is buffered after reading it from $x$ and before writing it onto $y$. This technique is called “lookahead.” The editing program can now be formulated as follows:

program editor (x, y, input, output);
var lno: integer;     {number of current line}
    cl : line;        {current line}
    x,y: text;
begin read instruction;
   repeat interpret instruction;
          write line;
          read instruction
   until instruction = 'E'
end.

We now proceed to specify the various statements in greater detail. Refining read instruction and interpret instruction, we note that an instruction generally consists of three parts: the instruction code and two parameters. We therefore introduce the three variables code, $m$, and $n$ intended for communication between the two routines.

var code,ch: char;
    m,n: integer

Read instruction:

read(code,ch);
if ch = ',' then read(m,ch) else m := lno;
if ch = ',' then read(n) else n := m;

51 This formulation caters to the acceptance of instructions with 0, 1, or 2 parameters, substituting appropriate default values for “missing” specifications.

Interpret instruction:

copy;
if code = 'I' then
begin putline;
      insert;
end else
if code = 'D' then skip else
if code = 'R' then
begin insert;
      skip
end else
if code = 'E' then copyrest else Error

In a second step of refinement we express the statements copy, insert, and skip used in (1.59) in terms of operations involving single lines only, i.e., in terms of getline and putline. Their common characteristic is the repetitive structure. Copy serves to copy lines from $x$ to $y$, starting with the current line, and terminating with the $m$th line. Skip reads lines from $x$ without copying up to the $n$th line.

Copy:     while lno < m do
          begin putline;
                getline
          end

Skip:     while lno < n do getline

Insert:   readline;
          while noend do
             begin putline; readline
             end;
          getline;

Copyrest: while ¬eof(x) do
             begin putline; getline
             end;
          putline

In the third and last step of refinement we express the operations getline, putline, readline, and writeline in terms of operations on single characters. We note that until now all operations dealt exclusively with entire lines and52 that no specific assumptions were made about the detailed substructure of a line. We know that lines themselves are sequences of characters. It would be tempting to declare the variable cl (holding the current line) as a sequence

var cl: file of char

However, recall the advice that a structure with infinite cardinality should never be used if a fundamental structure (such as an array) is adequate. Indeed, we are well advised to use an array structure in the present case. This is feasible, if we limit the line length to, say, 80 characters. Hence we specify

var cl: array[1 .. 80] of char

The four routines use an index variable $i$ with this array, which, in fact, is used locally and could well be declared local to each routine; moreover, it now becomes necessary to introduce a global variable $L$ to denote the length of the current line.

Getline:   i := 0; lno := lno + 1;
           while ¬eoln(x) do
              begin i := i+1; read (x, cl[i])
              end ;
           L := i; readln(x)

Putline:   i := 0;
           while i < L do
              begin i := i+1; (write y, cl[i])
              end ;
           writeln(y)

Readline:  i := 0;
           while ¬eoln(input) do
              begin i := i+1; read(cl[i])
              end ;
           readln

Writeline: i := 0; write (lno);
           while i < L do
              begin i := i+1; write(cl[i])
              end ;
           writeln

The condition noend in the routine insert is now readily expressed as

This concludes the development of this file editing program.