Edsger W. Dijkstra – A short introduction to the art of programming 

Link: E.W.Dijkstra Archive: A Short Introduction to the Art of Programming (EWD 316)

1. Preface 

For those readers who identify the programmer’s competence with a thorough knowledge of the idiosyncrasies of one or more of the baroque tools into which modern programming languages and systems have degenerated, the book will also be very incomplete, because I won’t describe any programming language —not even the one I use— to any degree of detail. I shall use some sort of programming language, as “a communication language” say, not for the communication of algorithms, but for the communication of ways of thinking, as a vehicle for programming style.

This is a sad experience and no amount of prior warning that this misunderstanding is bound to happen if they are not careful, has enabled me to avoid it!) To put it in another way: it is my purpose to transmit the importance of good taste and style in programming, the specific elements of style presented serve only to illustrate what benefits can be derived from “style” in general. In this respect I feel akin to the teacher of composition at a conservatory: he does not teach his pupils how to compose a particular symphony, he must help his pupils to find their own style and must explain to them what is implied by this. (It has been this analogy that made me talk about “The Art of Programming”.)

2. Some Fundamental Notions

It seems more fruitful to describe the programmer’s activity as “designing a class of computations”, rather than as “making a program”. In this connection it should be borne in mind that the more relevant assertions about programs —e.g. about the correctness of their resource demands— indeed pertain to the computations, rather than to the last thing that leaves the programmer’s hands, viz. the program text. It is for this reason that, when introducing fundamental notions, I will start at the side of the computations, with the “happenings in time”.

The first notion is that of an action. An action is a happening, taking place in a finite period of time and establishing a well-defined, intended net effect. In this description, we have included the requirement that the action’s should be “intended”, thereby stressing the purposefulness. If we are interested in action at all, it will be by virtue of its net effect.

An algorithm is the description of a pattern of behavior, expressed in terms of a well-understood, finite repertoire of named (so-called “primitive”) actions of which it is assumed a priori that they can be done (i.e. can be caused to happen).

In writing down an algorithm, we start by considering the happening to take place as a process, dissected into a sequence of sub actions to be done in succession. If such a subaction occurs in the well-understood, finite repertoire of named actions, the algorithm refers to it by its name. If such a subaction does not occur in the finite repertoire, the algorithm eventually refers to it by means of a sub algorithm in which the subaction, in its turn, is regarded as a process, etc. until at the end all has been reduced to actions from the well-understood, finite repertoire.

The notion of an algorithm, of an executable precept for the establishing of a certain net effect, is very well known from daily life: knitting patterns, directions for use, recipes and musical scores are all algorithms. And if one asks the way to the railway station in an unfamiliar town, one asks essentially for an algorithm, for the description of a pattern of behavior which, when followed, will lead to the desired goal.

The moral of this story is that it is an intrinsic part of the duty of everyone who professes to compose algorithms to supply a proof that his text indeed represents a proper algorithm.

Our next fundamental notion is a machine (or a “computer”). A machine is a mechanism capable of causing actions to take place following a pattern of behavior such as can be described by algorithms expressed in terms of a repertoire of primitive actions belonging to this machine.

Above we have given two algorithms for peeling potatoes, one for a natural number of potatoes and one only for even numbers of potatoes. Both algorithms have been expressed in the same repertoire of primitive actions. They were introduced in the realm of “observing happenings”; one could describe the pattern of behavior of my left-hand neighbor, the other the one of my right-hand neighbor. Suppose that my own wife

1) is also capable of performing those primitive actions

2)will accept from me algorithms expressed in these primitives and will follow such an algorithm obediently.

3. Programming Languages and their implementation

Because the programmer expressed his program in terms of the instruction repertoire of that particular machine, he was forced to tailor his program to that machine. He needed a thorough and ready knowledge of all the details of the instruction repertoire of that machine —which for the more intricate machines was no mean task— and worse: once his program was written, it could only be executed by that particular machine. Exchange of programs between institutes equipped with different machines was impossible; furthermore, whenever an institute replaced its old machine by a new and different one, all programs for the old machine became obsolete. From that point of view it was clear that tailoring one’s programs so closely to the idiosyncrasies of a specific piece of hardware was not a very wise investment of the intellectual energies of one’s programmers.

But even without the problem of transferring programs from one hardware machine to another, this way of programming, expressing programs as a monotonous stream of machine instructions, showed great drawbacks. One serious drawback was that this close contact between programmer and physical machine did not only enable the programmer to lard his program with all sorts of coding tricks, it actually invited him to do so. For many a programmer this temptation became irresistible; there even has been a time when it was generally believed that one of the most vital assets of a virtuoso programmer was that he be “puzzle-minded”, and it was only slowly recognized that a clear and systematic mind was more essential! When “tricky programming” was en vogue, programming was not only very expensive —it took too much time— it also turned out to be too difficult to get a program correct. Looking back, the period of tricky programming now strikes us as a generation of programmers walking on a tight-rope, in full confidence because they were unaware of the abysmal depth beneath it! The modern competent programmer is more humble and avoids clever tricks like the plague

The above shortcomings led to the design of so-called “(higher level) programming languages”. A programming language can be regarded as the machine code for a fictitious, idealized machine. Whereas the old machine codes were tailored to the needs of the hardware —i.e. the equipment electronic engineers could make— programming languages are more tailored to the intellectual needs and conceptual difficulties of the programmer who has to design the computations.

The problem now is that on the one hand we have the hardware machine A, that can be built but for which we don’t like to program because it is too cumbersome, and on the other hand we have “dreamed up” the fictitious machine B, for which we would love to program but which the engineers cannot build. How do we bridge that gap?

The gap is bridged by “software”: given machine A, we can make, once and for all, a program (in the machine code for machine A) which prescribes to machine A the pattern of behavior it should follow if it is to simulate machine B. Such a program is called “software for machine A”. Given hardware machine A, loaded with software, we have a mechanism —partly “hard”, partly “soft”— that is able to execute programs written for the fictitious machine B.

Usually this combination of hard- and software processes such programs in two stages. In the first stage (the “translation stage”) the program written in programming language B is subjected to a translation process. In this process a storage layout is decided, the necessary bookkeeping is carried out and an equivalent program —but now expressed in machine code A— is produced. In the second stage (the “execution stage”) the output of the first one is interpreted by machine A as a program and the intended computation is evoked.

The standard software that goes with the machine shields the user from the idiosyncrasies of the specific machine; apart from that it invokes —behind the user’s back, so to say— the standard ways of dealing with the tougher properties of the hardware, such as the possible parallelism (i.e. concurrence in time) of the computation proper and information transfers from and to peripheral devices and multilevel stores. Up till now we have described the hardware as if all storage cells were equally well accessible for the arithmetic unit. In practice this is seldom the case, two storage levels being quite common: primary store (usually ferrite cores) and secondary store (usually magnetic drums). The cells in primary store are the only ones that are directly and immediately accessible for the arithmetic unit; the information in secondary store (which in capacity is an order of magnitude larger than primary store) is not directly accessible for the arithmetic unit, but the possibility of bulk transfers from primary source and secondary storage is available instead. In such machines, the software may move the information around between the two stores, all the time keeping track of where everything is to be found at any moment and trying to keep in the primary store all “currently relevant” information. (This is called “the implementation of a virtual store”.)

We have mentioned the concept of the virtual store because it is related to an efficiency aspect over which the programmer has some control and in regard to which the programmer therefore has some responsibility. This is called “vagrancy”. A program has a small degree of vagrancy whenever for larger periods of time access are confined to a small, dense subset of the total amount of information; in that case the hope is justified that during that period of time this dense subset will be kept in primary store and that therefore the computation can go on at full speed. In computations with high vagrancy, the probability of information needed in secondary stores is much larger and the transport facilities between the storage levels then tend to become the bottle-neck. Therefore, if possible, high vagrancy should be avoided