A Structured Programming Approach to Data

Frontmatter

1. An Overview of Program Design

Abstract

The last decade has seen the recognition of programming as an area of study in its own right. It was only a few years ago that programming techniques could be summarised as the optimisation of loops by the removal of statements unaffected by the progress of the iteration. The concern then was largely one of efficiency. Today efficiency and optimisation are seen as secondary to the problem of reliability and correctness. Indeed Michael Jackson, an authority on program design proposes the following golden rules for optimisation.

Derek Coleman

2. Program Design Notation

Abstract

In this chapter we introduce a vehicle for expressing the structure and content of programs as we design them using the process of stepwise refinement. The notation for doing this may be called an abstract programming language because programs written in the notation are not intended to be run directly on a computer, they have to be coded into a real programming language. An abstract programming language performs the same role that in earlier times flowcharting was supposed to do; it is an informal notation to be used during program design. The abstract language used here is an informal extension of the language Pascal. It should be easily readable by anyone familiar with Pascal or any other Algol-like language. The notation is of necessity informal and is introduced by explaining features as and when they occur in the exposition. The essence of structure is organisation. The two dynamically related parts of a program — flow of control and accessing of data — must be organised in a simple and consistent manner. The structuring concepts applicable to each are considered in turn.

Derek Coleman

3. Arrays

Abstract

Array structures are the most common form of data structure and are familiar to most programmers. Arrays in programming languages originated from the mathematical concept. In mathematics a set of related variables a₁, a₂, …, an is referred to as the vector a, in programming such a structure is known as an array and would be declared in Algol as array a [1: n].

Derek Coleman

4. Simple Data Structuring

Abstract

A simple structured type can be formed by the set product† of two or more unstructured types. The result is known as a record type. A familiar example is the type complex number, which consists of all possible ordered pairs of real numbers. Thus

$$ \begin{gathered} \hfill type\,complex=record \\ \hfill realpart: real \\ \hfill imagpart : real \\ \hfill end \\ \end{gathered} $$

or more briefly

$$ \begin{gathered} \hfill type\,complex = record \\ \hfill realpart, imagpart:real \\ \hfill end \\ \end{gathered} $$

define complex numbers to be records with realpart and imagpart components, and each components is of type real.

Derek Coleman

5. On Program Design

Abstract

Chapter 1 introduced the concept of designing programs by the method of stepwise refinement. In essence, we try to decompose a problem into a simple series of subproblems. Given a problem P, we try to discover a set of smaller problems P₁, P₂, P₃, …, such that solving first P₁, then P₂ and so on will be a solution to the original P. This approach is then applied to each of the subproblems P₁, P₂, P₃, …, producing a set of sub-subproblems whose solutions taken together are a solution to P₁. We continue this process until the problems are sufficiently small to be capable of solution directly. It is the continual outside-in analysis of the problem which develops the solution to the problem. This analysis and thus the structure of the solution can be usefully represented and guided by a development tree as shown in figure 5.1.

Derek Coleman

6. Set Structures

Abstract

So far we have only considered the simple data structuring operations of forming records with or without variants. Although these operations are adequate for many problems they are, by themselves, incapable of expressing clearly the full range of abstractions that can occur in programming.

Derek Coleman

7. The Class Construct

Abstract

The process of stepwise refinement produces programs as a series of levels of abstraction, and at each level the designer is encouraged to ignore the details of the lower levels. Prior to this chapter we have concentrated on the refinement of control structures. But when designing programs, especially large ones, it is also necessary to refine the structure of the data hand in hand with control.

Derek Coleman

8. Dynamic Data Structures

Abstract

Much of our experience in both programming and the real world concerns the manipulation of the ‘small rather than the large’. For this we are to be thankful, for once we depart the realm of the small, many trivial operations take on a frightening complexity requiring painstaking organisation. The lifting of an object weighing 1 kg is trivial, 50 kg is difficult but possible, 2500 kg is, for the average human, impossible. A ‘mere’ quantitative change causes a qualitative change in the nature of the problem. We must expect therefore that once we include the ‘large’ in a problem we are most likely introducing with it a number of difficulties. This certainly applies to data structures which are in some sense ‘large’.

Derek Coleman

9. Sequences

Abstract

At the end of the last chapter it was pointed out that when processing set structures we are not concerned with the order in which elements are stored or accessed. Frequently, however, the ordering is significant; thus character strings are more than sets of characters — the ordering is vital

$$ 'tea', 'eat', and 'ate'$$

are all distinguishable as strings whereas

$$ (t,e,a),(e,a,t)and(a,t,e) $$

are equivalent as sets.

Derek Coleman

10. Simple Searching Techniques

Abstract

For a mapping or function to be represented by an array it is necessary that the domain type be both finite and of small enough cardinality to allow the allocation of a unique part of store for each array element. Likewise set structures, which have a small enough base type, are capable of an efficient bitstring representation in which an individual bit is allocated to each possible set element. Exceeding the restriction, as in the case of integer sets, necessitates an altogether different representation. However, in many applications the programmer cannot avoid requiring a structure representation for a function with large or infinite domain or for a set with large or infinite base type. A structural representation is only possible for sets that have only a small number of domain elements and for functions that map only a few values into significant range values. By ‘significant’ we mean differing from a specified null or default value. Such structures are known as sparse sets and arrays

$$ \begin{gathered} type\,S = sparse\,set\,of\,T \hfill \\ type\,A\, = sparse\,array\,D\,of\,R \hfill \\ \end{gathered} $$

Derek Coleman

11. Hashing Techniques

Abstract

Previously we have looked at the methods of implementing sparse mappings which conduct searches according to some preplanned scanning strategy. In this chapter we discuss a family of methods where the position of an entry in a directory is related to the value of its key; these methods are known as hashing techniques. Because hashing involves explicitly computing the position of an entry from its key, the technique is only applicable where there is fixed upper bound on the number of directory entries. Hashed directories will therefore be considered as array structures

$$ array\,[0..n]\,of\,entry $$

though in essence it is immaterial whether the array is held in main store or on backing store as a randomly accessible file.

Derek Coleman

12. Recursion and Recursive Algorithms

Abstract

Before continuing with the treatment of search methods a full discussion of recursion is needed to prepare the ground for the next chapter on binary trees.

Derek Coleman

13. Binary Search Trees

Abstract

Chapter 10 on search methods postponed discussion of binary search directories which may vary dynamically. We shall now remedy that omission. To calculate the average search length of a binary search the set of possible paths through the directory was represented by a binary tree (figure 13.1).

Derek Coleman

14. Designing Programs from Data Structures

Abstract

Dijkstra (1973) has remarked that to the processing unit of a computer, the sequence of millions of program instructions it performs in a short period of time is extremely monotonous: it just performs instructions one after the other. He proceeds to explain that if we dare to interpret the whole happening as meaningful, it is only because we have mentally grouped sequences of instructions in such a way, that we can distinguish a structure in the whole happening. In other words we can say the structure of an object is really how an observer (processor) relates to that object; to give meaning to an amorphous sequence of instructions or data, the rules governing its structure have to be known. In the case of data, it is type that defines and expresses structure.

Derek Coleman

Backmatter