__On Understanding Programs.__

On a number of occasions I have stated the requirement that if we ever want to be able to compose really large programs reliably, we need a discipline such that the intellectual effort *E* (measured in some loose sense) needed to understand a program does not grow more rapidly than proportional to the program length *L* (measured in an equally loose sense) and that if the best we can attain is a growth of *E* proportional to, say *L*^{2}, we had better admit defeat. As an aside I used to express my fear that many programs were written in such a fashion that the functional dependence was more like an exponential growth!

I now offer, for the reader's consideration, an example showing how the same program can be understood in two different ways: in the one way, *E* grows proportional to *L*, in the other way it grows (even worse than) exponentially.

I express *E* in the number of "steps of reasoning" needed, a number which is determined as follows.

Let us consider a "stretched" program of the form

" S_{1};S_{2}; ...;S"_{N}(1)

i.e. the corresponding computations are a time-succession of the executions of *S*_{1} through *S _{N}* in that order. When the nett effect of the execution of each individual statement

In the case of a program of the form

" ifBthenS_{1}elseS_{2}"(2)

where, again, the nett effect of the execution of the statements *S*_{1} and *S*_{2} has been given, my measuring convention states that it takes 2 steps to understand program (2), viz. one step for the case *B* and another for the case __non__ *B*.

Consider now a program of the form

" ifB_{1}thenS_{11}elseS_{12};

ifB_{2}thenS_{21}elseS_{22};

.

.

.

ifB_{N}thenS_{N }_{1}elseS_{N }_{2}"(3)

According to the measuring convention it takes 2 steps per alternative statement to understand it, i.e. to establish that the nett effect of

" ifB_{i}thenS_{ i }_{1}elseS_{ i }_{2}"

is equivalent to that of the execution of an abstract statement *S _{ i }*. Having

If we had not introduced the abstract statements *S _{ i }*, but had tried to understand program (3) directly in terms of executions of the statements

If by now the reader protests that the second way to try to understand program (3) is utterly foolish, then I have him exactly in the position where I want him to be, for then we could not agree more fully. The point is, that any effort to improve upon the second method yields a method more similar to the first one: one will find oneself introducing the abstract statements *S _{ i}* (or combinations of them)!

The whole demonstration is an urgent plea to use our powers of abstraction as consciously as possible (and to restrict ourselves in programming to those program structures in which these powers can be exploited at greatest advantage!) The reader who has followed me thus far may wonder whether he has been confronted with something deep or something trivial. So did I, when I discovered this example; I have, however, decided to submit it for publication when I felt that it was probably both.

Edsger W.Dijkstra

Technological University

EINDHOVEN

The Netherlands

transcribed by Tristram Brelstaff

revised