Programming Principles

Programming is a skill best acquired by practice and example rather than from books. The remarks given here are therefore quite inadequate. [The word ``inadequate'' is very faint in the ms., and may have been deliberately whited out.]

If it is desired to give a definition of programming, one might say that it is an activity by which a digital computer is made to do a man's will, by expressing this will suitably on punched tapes, or whatever other input medium is accepted by the machine. This is normally achieved by working up from relatively simple requirements to more complex ones. Thus for instance if it is desired to do a Fourier analysis on the machine it would be as well to arrange first that one can calculate cosines on it. For each process that one wishes the machine to be able to carry out one constructs a `routine' for the process. This consists mainly of a set of instructions, which are obeyed by the machine in the process. It is not usual however to reckon all the instructions obeyed in the process as part of the routine. Many of them will belong to other routines, previously constructed and carrying out simpler processes. Thus for instance the Fourier analysis process would involve obeying instructions in the routine for forming cosines as well as ones in the analysis routine proper. In a case like this the cosines routine is described as a `subroutine' of the analysis routine. The subroutines of any routine may themselves have subroutines. This is like the case of the bigger and lesser fleas. I am not sure of the exact meaning the poet attached to the phrase `and so ad infinitum', but am inclined to think that he meant there was no limit that one could assign to the length of a parasitic chain of fleas, rather than that he believed in infinitely long chains. This certainly is the case with subroutines. One always eventually comes down to a routine without subroutines.

[The previous paragraph would have to be amended somewhat in the light of modern practice. Currently, digital Fourier analysis generally uses FFT algorithms which do not involve any explicit evaluations of cosines (or other trigonometric functions); evidently Turing was not familiar with these approaches, though the basic idea has been traced back to the 19th century. Likewise, his final statement that ``One always eventually comes down to a routine without subroutines'' needs some modification in the case of recursive routines, or sets of mutually recursive routines -- one always eventually comes down to a routine which does not invoke any subroutines (at least if the computation ever terminates!) but that is a somewhat different thing.]

What is normally required of a routine is that a certain function of the state of the machine shall be calculated and stored in a given place, the majority of the content of the store being unaffected by the process, and the routine not being dependent on this part having any particular content. It is usual also for the other part of the store to be divided into a part which is altered in the process but not greatly restricted as to its original content, and a part which is unaltered in its content throughout, and such that the correct working of the routine depends on this part having a particular content. The former can be described as `the working space for the routine' and the latter as `the space occupied by the routine'.

Applying this to the Mark II machine, the routines usually `occupy' various tracks of the magnetic store. The working space includes all the electronic store, with the exception of PERM, which can equally well be reckoned as working space which is never really altered, or as a part common to all routines. The first two pages of the electronic store are also somewhat exceptional, if normal conventions are used, as they are only altered when one is copying new routines from the magnetic store onto them.

These definitions do not really help the beginner. Something more specific is needed. I describe below the principal steps which I use in programming, in the hope they will be of some small assistance.

(i) Make a plan

This rather baffling piece of advice is often offered in identical words to the beginner in chess. Likewise the writer of a short story is advised to `think of a plot' or an inventor to `have an idea'. These things are not the kind that we try to make rules about. In this case however some assistance can be given, by describing the decisions that go to make up the plan.

a) If it is a genuine numerical computation that is involved (rather than e.g. the solution of a puzzle) one must decide what mathematical formulae are to be used. For example if one were calculating the Bessel function $J_0(x)$ one would have, amongst others, the alternatives of using the power series in $x$, various other power series with other origins, interpolation from a table, various definite integrals, integration of the differential equation by small arcs, and asymptotic formulae. It may be necessary to give some small consideration to a number of the alternative methods.

b) Some idea should be formed as to the supply and demand of the economic factors involved. A balance must always be struck between the following incompatible desires

• To carry the process through as fast as possible
• To use as little storage space as possible
• To finish the programming as quickly as possible
• To achieve the maximum possible accuracy

We may express this by saying that machine time, storage space, programmers' time and inaccuracy of results all cost something. The plan should take this into account to some extent, though a true optimum cannot be achieved except by chance, since programmers' time is involved, so that a determination of the optimum would defeat its own ends. The `state of the market' for these economic factors will vary greatly from problem to problem. For instance there will be an enormous proportion of problems (40% perhaps) where there is no question of using the whole storage capacity of the machine, so that space is almost free. With other types of problem one could easily use ten million digits of storage and still not be satisfied. The space shortage applies mainly to working space rather than to the space occupied by the routines. Since these usually have to be written down by someone this in itself has a limiting effect. [The statement that instructions are not likely to cause a space shortage is also somewhat at odds with current practice.] Speed will usually be a factor worth consideration, though there are many `fiddling' jobs where it is almost irrelevant. For instance the calculation of tabular values for functions which are to be stored in the machine and later used for interpolation, would usually be in this class. Programmers' time will usually be the main factor in special jobs, but is relatively unimportant in fundamental routines which are used in most jobs. Accuracy may compete with machine time e.g. over such questions as the number of terms to be taken in a series, and with space over the question as to whether 20 or 40 digits of a number should be stored.

c) The available storage space must be apportioned to various duties. This will apply both to magnetic and electronic storage. The magnetic storage will probably be mainly either working space or unused. It should be possible to estimate the space occupied by instructions to within say two tracks, for a large part will probably be previously constructed programmes, occupying a known number of tracks. The quantities to be held in the working space should if possible be arranged in packets which it is convenient to use all at once, and which can be packed into a track of a half-track or quarter-track. For instance when multiplying matrices it might be convenient to partition the matrices into four rowed or eight rowed square matrices and keep each either in a track or a quarter-track. The apportionment of the electronic store is partly ruled by the conventions we have introduced, but there is still a good deal of freedom, e.g. if eight [electronic] pages are available then pages 4, 5, 6 can be used for systematic working space and may be used for various different purposes that require systematic working space.

The beginner will do well to ask for advice concerning plans. Bad plans lead to programmes being thrown away, wasting valuable programmers' time.

d) If questions of time are at all critical the `plan' should include a little detailed programming, i.e. the writing down of a few instructions. It should be fairly evident which operations are likely to consume most of the time, and often these will consist of a small number of instructions repeated again and again. In these cases the few instructions in question should be written down so as to give an estimate of the time, and help decide whether the plans as a whole is satisfactory. Very often the `omission of counting method' [i.e., loop unrolling; see p. ] should be applied

e) If one cannot think of any way, good or bad, for doing a job, it is a good thing to try and think how one would do it oneself with pencil and paper. If one can think of such a method it can usually be translated into a method which could be applied to the machine.

(ii) Break the problem down

This in effect means to decide which parts of the problem should be made into definite subroutines. The purpose of this is partly to make the problem easier to think about, the remaining work consisting of a number of `limited objective' problems. Another reason for breaking down is to facilitate the solution of other problems by the provision of useful subroutines. For instance if the problem on hand were the calculation of Bessel functions and it had already been decided to use the differential equation, it might be wise to make and use a subroutine for the solution of linear second order differential equations. This subroutine would in general be useful in connection with other subroutines which calculate the coefficients of the equation.

(iii) Do the programming of the new subroutines

It is better to do the programming of the subroutines before that of the main routine, because there will be a number of details which will only be known after the subroutine has been made, e.g. scale factors applied to the results, number of pages occupied by the subroutine, etc. It also frequently happens in the making of the subroutine that some relatively small change in its proposed properties is desirable. Changes of these details may put the main routine seriously out if it were made first. There is a danger that this procedure may result in one's `not seeing the wood for the trees', but this should not happen if the original plan was well thought out. The programming of each subroutine can itself be divided into parts.

a) As with programming a whole problem a plan is needed for a subroutine. A convenient aid in this is the `block schematic diagram'. This consists of a number of operations described in English (or any private notation that the programmer prefers) and joined by arrows. Two arrows may leave a point where a test occurs, or more if a variable control transfer number is used. Notes may also be made showing what is tested, or how many times a loop is to be traversed (see p. ).

b) The operations appearing as blocks in a) may be replaced by actual instructions. It is usually not worth while at first to write down more than the last two characters of the (presumptive) instruction, i.e. the B line and function parts. These are quite enough to remind one of what was the purpose of the instruction.

c) One may then write the instructions into a page, deciding at the same time what are to be the addresses involved. Some of the finer points of this are described in the `hints' in the next section.

d) When the programme is complete, check sheets must be made. This process has already been described (p. ). It is often advisable to start making check sheets long before the program is complete; one should in fact begin them as soon as one feels that one has got into a muddle. It is often possible to work out most of the programme on the check sheets and afterwards transfer back onto the page or pages of instructions.

(iv) Programme the main routine

This follows principles similar to (iii).

Of course these remarks merely represent one possible way of doing programming. Individuals will no doubt vary as to the methods they prefer.