THE ART OF PROGRAMMING

Programm i n g is a very difficult task. In order to improve our und e r standing we should try to st ru ctur e programs in some nice mann er. This paper indicates an approach to this probl em and discu sses i ts implications on writing a program a ri s ing from some given problem . Rapporteurs: Mr. P. Henderson Mr. R. Snowdon I In ty()du Ct l on 'The efforts of in st rucLion a r e seld om of muc h efficacy , except in those ha ppy disposi t i on s wherP. t hey ar e a lmo st s uperfl uous '. Gibho n : 'Dec line and Fall of Roman Empi re '. 'T,a plu s ue.!l e r u se du Diable est de fl OU S p ers uad e I' qu ' i1 n I C'xi:-;te pas I • Baud elai re. Before embarking on this subj ect it is useful to make a short ]"~t of misunderstanding s . Such misunderstandings are fo st e red by adv e rtisements, by programming courses and by instruction manual s . • Pr ogramming i s easy if a programm er know s how to get hi s underlinings and semi -colon s i n t h e right pl ace or how to write fluently in capital lette r s . 2. All a programmer n eeds to know is how to u se a f low charting stencil prop erly . . All a programmer needs to kn ow is how to writ e format statement s and job co ntro l card s. 4. Programming i s easy if your machin e is big enough. . A "pr ogramm er need on ly l earn not to make mi stak es . The las t two mi sund e rstanding s are mor e s ubtl e th a n th e fir s t thr ee . Contrary to these misund e rstanding s , programming i s pot ential ly ve ry, very difficu lt . Analysing th e task of pr ogramming l eads to t he co nc lu s ion t hat programming is a gigantic i ntellectual chall enge without any pr ecedent i n th e hi story of mankind. 4. How do we teach how to build nicely structur· ed programs? 1. On our inability to do much For practical reasons demonstration programs must be many times smaller than 'life-size programs'. In practice we are faced with large (1,000 page) programs and it would b e pleasant if the structuring which we may demonstrate in small programs carried over directly to these larger programs. This is not the case. One of t h e major sources of difficulty in programming is that a factor of one thousand is so large that if anything is a thousand times as large, as fast, or as difficult as something else, then this difference is so tremendous that the result strikes us as something entirely different. The only way to overcome this is to draw attention to the effects of size explicitly, to point out to the student s that 'a thousand times' i s a few orders of magnitude beyond their imagination. They do not believe this to begin with and the only recourse is to demonstrate it with metaphors. In a small village, to scan a few columns of a telephone directly in order to find that name correspond ing to a particular number is not difficult, but to do the same in a l arge city would be a major data processing task. The misunderstanding that pro gramming is easy provided you make no mistakes, suggests that programs are sometimes wrong . . Of course, it is not difficult to write a program of the size of a smal l booklet as long as it does not need to work. The requirement that it should. work is what makes programming such a great intellectual challenge. On the reliability of mechanisms If we have a program constructed from N components each with a probability of correctness p t hen the probability that the program is correct is P, where As N will probably be very large, p should be very, very close to 1 if we desi r e P to differ significantly from zero. The s heer size of programs, t h erefore, focuses attention on the correctness problem and thus requires a mu ch larger confidenc e level in the individual components. basis then can we increase this confidence level? 6 On what .. I r I As an exampl e of how not to do it let us consider a multiplier for two 21-bit integers . Since machines are so fast let us perform all possible multiplications. This, howeve r, involves 227 x ze7 different multiplications, and even assuming our machine is capable of 214 multiplications per second this will take longer than 30 ,000 years to complete. Although the total number of multiplications whic h will ever b e performed during the lifetime of the computer will be a negligible fraction of those of which it is capable, we still require it to p erform these correctly. The moral of this story is t hat if you consider a mechanism as a black box then the only way of convincing oneself of the correctness of this mechanism is by exhau stive testi ng, and this is out of the question for practical reasons. It is unsatisfactory from a theoretical point of view also, because we cannot be convinced that the mechanism has been put through all its internal states . We mu st, therefore, find other ways of convincing ourselves that a program work s . As a corollary we see that program testing can b e u sed to show the presence of bug s , but never to show their absence. We conclude that it is nec essary to take the structure of the mechanism into account. Rather than trying to find proof techniques to establish the correctness of arbitrary programs let us try to find those elementary structures for programs such that the intellectual effort needed to prove the correctness does not explode. On our mental aids What patterns of reasoning we do have at our disposal, how do we apply them and what are the consequences? our disposal are: 1. Enumerative reasoning. Mathematical induction. 3. Abstraction. 4. Intuitive stroke of genius. Only the first three will be considered here. Enumeration Among the mental aids at which requires two st eps of reasoning. Mathematical induc tion We u se this tool to tackle the problem of programs which include loops. An alternative to the direct application of mathematical induction to programs is to appeal to one of the following two theorems, which are stated without proof. Linear Search Th eo r em: These two theorems themselves are provided by mathemat i ca l induction and onc e proved we can appeal to these theorems without furth e r direct a ppli cat ion of mathematical induct ion . Abstract ion Th e ma in purpo se of abstraction i s to reduce the a ppea l we have to make to enumerative reasoning. For exampl e, a variabl e is an abstraction 8 from its value. In addition we may appeal to either operational or representational abstraction. In addition we require a further N steps to understand this. This gives a total of 3N steps which is linear in N (a measure of program length). Alternatively, if we do not introduce the abstract statements S then we must consider 2N possible paths through the program, each path con~aining N statements. The object is to find, as quickly as possible, a description applicable to a conditional clause in which the fact that it was controlled by a conditional clause has disappeared. A similar consideration applies to a piece of program controlled by a while clause. lowing example. All these tools are applied in the folExample 1. In order to apply t h e i nvariance theorem we need to set up an assertion P which remains invariant (and to prove termination). One of the e lements of P will be that y remains intege r valued and not l e ss than zero: integ e r y ;;, ° This is certainly true to start with and the statement qualifi ed by the while clause is executed only if y f 0, and so y will be positive. The abstract effect of: if odd(y) ~ begin y: = y-1j z: = z*x en