In this chapter we address the issues of coding from a PDL into various real imperative programming languages. The PDL stage described in the previous chapter contains a complete (imperative) solution to the original problem so that the coding can now be finished without reference to the original problem. The intention in this chapter is to show that the final code generation can be accomplished using coding templates. Coding templates are shown for a variety of programming languages in common use.

Templates

Coding templates are stylised translations of each feature of a PDL. The methodical application of the templates to the PDL solution will yield the final code.

For any particular final coding language, a set of (coding) templates is created to translate each feature of the PDL in use. This means for example that every ‘if’ statement in the PDL is translated in the same way. Each time the ‘if’ statement is met it is coded using the same pattern or template. The templates are different for each different final coding language. They are chosen more for generality than for elegance or efficiency. There may well be features of a final coding language that are not used in any template. In this methodology these features will never be used. This may seem an unacceptable loss at first sight. However the experience of the authors is that the features which are not used in templates are those which are less widely used anyway or not universally supported or inconsistently supported and so their omission leads to more portable programs.

So far we have only considered the construction of new programs, but of course there are very many programs which are already in existence and which we may need to use. Like much old electronics equipment they may or may not have been well-designed but in any case there is a great tendency to ‘leave well alone’ just in case they stop working.

When a program exists only in its object form (i.e. translated into machine code) little can be usefully done – decompilers, which translate a program back into a high-level language form, do exist but the resulting program is usually pretty unintelligible. Such (object only) programs should be candidates for rewriting as soon as time is available since in their current form they cannot be safely and quickly amended and this, in practice, is an ever-likely requirement.

Programs which exist in source form present a more approachable problem. Because of their age and the rapid development of programming methodology, it is likely that these programs will not have formal specifications from which their correctness could have been demonstrated. Also, in view of their preoccupation with making best use of slow and expensive hardware, it is very probable that the early programmers were not permitted the luxury of programming style. These economic factors served to encourage the production of unintelligible ‘spaghetti’ code which was very difficult to analyse and/or modify.

We have been discussing the specification of programs and the refinement of specifications. These are clearly processes that precede the coding into the final programming language. On the assumption that the final programming language will be imperative rather than declarative, we introduce another stage in the programming methodology before the final coding. This stage will use a PDL –a Program Development Language (or Program Design Language).

In this chapter we compare imperative languages and declarative languages and show why the transition from a declarative specification to final (imperative) code should be performed in two stages (i.e. via PDL). We then introduce one possible PDL but point out that a PDL should be chosen to suit a particular team or project. PDL versions of all the specifications in earlier chapters are shown as examples. Chapter 6 deals with the translation of PDL into various real imperative languages.

Imperative and declarative languages

The great majority of programs in existence are written in imperative style. This is because FORTRAN, COBOL, PL/1, Algol, Pascal, Ada and assembly languages are all imperative languages.

In case this seems to include the whole world of programming languages, let us point out that the alternative to the imperative languages is the use of declarative programming languages which include functional languages (e.g. (Pure) Lisp, KRC, Hope, Miranda, FP) and the logic languages (e.g. Prolog).

In this context the word imperative is intended to convey the sense of a command or instruction to do something straight away.

This text promotes the disciplined construction of procedural programs from formal specifications. As such it can be used in conjunction with any of the more conventional programming texts which teach a mixture of ‘coding’ in a specific language and ad hoc algorithm design.

The awareness of the need for a more methodical approach to program construction is epitomised by the use of phrases such as ‘software engineering’, ‘mathematical theory of programming’, and ‘science of programming’. The hitherto all-too-familiar practices of ‘designing’ a program ‘as you write it’ and ‘patching’ wrong programs being more appropriate to a cottage industry rather than a key activity in the current technological revolution.

The cost of producing hardware is decreasing while the production of software (programs) is becoming more expensive by the day. The complexity and importance of programs is also growing phenomenally, so much so that the high cost of producing them can only be justified when they are reliable and do what they are supposed to do – when they are correct.

No methodology can exist by which we can produce a program to perform an arbitrary task. Consequently that is not the aim of the book. What we shall do is to show how, by using a Program Design Language and templates for your chosen target language, you can develop programs from certain forms of specification.

Although programming is essentially a practical activity, the degree of formality adopted throughout the development process means that sufficient information is available to enable correctness proofs to be investigated if and when required.

In this chapter many kinds of diagram are discussed. They all show structure in some way. They may broadly be classified into program structure diagrams and data structure diagrams – but note that sometimes programs are data to other programs so the distinction is imprecise.

Diagrams used in the program development process

This section discusses the use of diagrams in the program development process.

There are many kinds of diagram and everyone has favourites. It is the intention of this chapter to demonstrate the usefulness of a disciplined approach to diagrams and to stress the similarities between kinds of diagrams rather than to advocate one particular diagramming technique above all others.

In computer programming, the main uses for diagrams are:

1. to show the flow of control in a program (= flowchart)

2. to show the structure of data (= data structure diagram), and

3. to show the structure of a programming language (= syntax diagram).

All these diagramming systems show structure in some way.

All the systems can be used intuitively and informally to organise initial ideas or they can be used formally as part of a disciplined design process.

In looking for the similarities rather than differences between different diagramming systems, the critical observation is that all systems have a way of showing

1. sequencing

2. selection

3. repetition

The diagram below shows the way these structure forms are drawn in three different diagramming systems.

In Chapter 7 we discussed the desired logical relationships between segments of program and their specifications. In that discussion it was sufficient to take for granted all the common properties of integers, etc., and to concentrate on the more important (deductive) issues. However, in order to make our arguments mathematically sound we must explain how these ‘facts’ are introduced into a programming system. The method, outlined below, not only gives a foundation for the mathematical manipulations that are central to our methodology, but also provides a set of requirements against which implementations can be checked, and can also be applied to (abstract) data types which may not be native to the target computer system.

We begin, in Section 10.1, with a look at probably the most fundamental data type, Boolean. Objects and expressions of type Boolean are required in one form or another in all programming languages to control the flow of a computation. They are also used to manipulate tests associated with other, more explicitly data-related, types and since the type has only two data values we can defer consideration of problems associated with large, potentially infinite, sets of data values.

Next, in Section 10.2, we look at lists. Constructing a list-of-something is one of the more familiar ways of building a new type from an existing one. Although a set of lists may be infinite, lists provide a vehicle for the introduction of more facilities of our definition system before going on to discussing problems associated with numeric types in Section 10.3.

The purpose of this chapter is to caution the reader about straying from the templates given in Chapter 6; to explicitly state the semantic assumptions inherent in our basic PDL, and to highlight factors which must be checked when extending PDL or devising templates for target languages not mentioned in this text.

PDL is a very small language, having relatively few fundamental operations and processes. Moreover the semantics, the meanings, of these components relate directly and simply to corresponding features in implemented languages. Proper definition of programming language semantics is a non-trivial task and definitely far too involved to be adequately discussed here. However, since we want our programs to actually carry out computations, and not be purely static objects represented by symbols on paper or on a screen, we cannot totally avoid semantics; so what do we do?

Recall that an implementation of an operation is correct if all its required external characteristics are described by its specification. It would therefore be true to say that the semantics of the operation can be fully described/ defined by the inter-relationship between input/state and output/state of an appropriate specification. So what is the problem? The problem is that very few implementations of programming languages are defined adequately enough to enable us to use the definition in a formal way.

The nature of a specification

The task of solving a problem using a computer can be reduced to the outline

1. given THIS,

2. produce THAT

or expanding, a little,

1. given some DATA,

2. produce some RESULTS

3. which are the proper results for that data.

The results are either the ‘proper’ results for that data, or they are not. A specification can be viewed as a test that has been devised to check for ‘proper’ results. It does not need to show HOW the results are to be obtained although it may. Thus the task of solving a problem using a computer may be regarded in general as

1. given d,

2. produce r

3. such that S(d,r) is True

where S(d,r) is a test (or predicate) which, given the data d and the results r produced from it, delivers the answer True or False, i.e. the results are acceptable (or not) for that data.

Example

1. Let d be 169,

2. let r be 13

3. and suppose Sl(d,r) IS_DEFINED_TO_BEd=r⋆r.

(As is conventional in computing we are using ‘⋆’ to mean multiply. IS_DEFINED_TO_BE is an example of our use of a word or a phrase where a mathematical symbol would have been more concise. However we do not want unfamiliarity with symbols to prevent easy reading at this stage so we obtain clarity at the expense of brevity. The words in the phrases are always joined by underline and should be regarded as a single unit. In later chapters we will introduce the more concise notation.)

An appraisal of the current situation.

Is anything the matter?

In the early days of computing the machines were not very powerful, there were not many of them and few people had high expectations of them. All that has changed. Computers seem to have become an essential part of everyday society and large numbers of people are employed in supporting existing computer systems and creating new ones.

Although the use of computers is widespread the public image of computers and the computing profession is in need of improvement. Everyone has their own story to tell of the time when their enquiry was rejected with the excuse that ‘it's not possible since we installed the computer system’. There have been some well-publicised disasters with new computing systems.

Yes, something is the matter!

What is wrong with computing today?

Is it the machines? Well they are cheaper, smaller, faster and more reliable than they used to be. No, they do not seem to be the problem.

Is it the programs then? Software today is more expensive, more complex, but no more reliable than it used to be.

Why should this be? Is it the fault of the programmer teams? Are they not as clever as they used to be? No, they have been asked to do the impossible. It is like asking a child who has built toy houses out of Lego bricks to design and build tower blocks for people to live in.

The specification of functions and processes by means of pre-conditions and post-conditions requires that any repetitive or accumulative aspects of the computation must be indicated by recursion. Now, although many modern procedural programming languages support recursion and hence allow programming in a functional style, the run-time overhead of large amounts of stack manipulation imposed by the related control mechanism is unacceptable in certain applications.

Throughout this book, our central premise has been that to make best use of programmer efforts we should concentrate on correctness and ignore run-time efficiency considerations. Of course, to spend much time and effort developing a correct program only to have its correctness violated by the introduction of some slick trick which substantially reduces execution time – but does not quite always work – is to invalidate the whole exercise. Consequently all such transformations and optimisations must also be proven correct and, if appropriate, programmed into the system so as to protect them from human error.

As noted in Chapter 9 we already trust hardware extensions to the minimal set of arithmetic functions which, for instance, compute integer sums and products without recursive recourse to the increment and decrement instructions. On the software side, we showed in Chapter 7 how certain dataflow charts can be unwound into iterative control flowcharts.

The recursion-to-iteration transformation given in Chapter 7 is particularly useful in that it is widely applicable.