records) and the properties of the operators over such data structures. In fact, the central concept in all software is that of a program, and a generally satisfactory definition of program is still needed. The most frequently used definition — that a program is a sequence of instructions — forces one to ignore the role of data in the program. A better definition is that a program is a set of transformations and other relationships over sets of data and container structures. At least this definition guides the designer to break up a program design problem into the problems of establishing the various data and container structures required, and defining the operators over them. The definition requires that attention be paid to the properties of the data regardless of the containers (records, words, sectors, etc.), the properties of the containers themselves, and the properties of the data when combined with containers. It also forces the designer to consider how the operators relate to these structures.«
Dijkstra’s paper: Complexity controlled by hierarchical ordering of function and variability gave rise to several remarks.
Van der Poel: I agree with the systematics behind the ideas of Dijkstra and his layered structure. In fact when you develop a program systematically in his fashion you have given the proof of its correctness and can dispense with testing altogether. There are, however, a few points to make.
Dijkstra requires that you should be able to verify the correctness of that proof. However, if you insist on having seen every piece of programming yourself, of course you can never step up to a high level of programming. At some stage you will have to believe the correctness of a piece of software which has not been seen or proved by yourself, but by some other party.
Another point is that I think the picture a bit unrealistic on the kind of errors. Errors cut right across the layers, because these are just abstractions. The machine does not know anything about sub-routines, and an error can cut across all these layers in such a way that very illogical results can ensue.
My next point is that I miss an important point in Dijkstra’s deductions, and that is he doesn’t include the solution of the problem. When he constructs a program then in fact the solution of the problem has been made already. I would like to ask how do we solve the problem. At least I do not know it. When you can visualize a flow diagram or a program in an abstract way, somehow you have solved the problem first; and there is some missing link, some invention, some intuition, some creation process involved which is not easily or not at all symbolised or mechanised. When it’s mechanised it is no problem anymore, it’s just a mechanical solution of the problem.
Then about errors and error propagation and testing: a program is a piece of information only when it is executed. Before it’s really executed as a program in the machine it is handled, carried to the machine in the form of a stack of punch cards, or it is transcribed, whatever is the case, and in all these stages, it is handled not as a program but just as a bunch of data. What happens to errors which occur at that stage, and how can you prove the correctness of all these transmission steps?
Then, as a last question I would like to put the following. The specifications of a problem, when they are formulated precisely enough, are in fact equivalent to the solution of the problem. So when a problem is specified in all detail the formulation can be mapped into the solution; but most problems are incompletely specified. Where do you get the additional information to arrive at the solution which includes more than there was in the first specification of the problem?
Dijkstra: I see in the remarks you made three main elements, one of them the error propagation at a rather mechanical, clerical level. The problem of clerical errors is very serious if it is neglected in practice. On the other hand there are very effective and cheap methods to deal with it by using suitable redundancy.
Next you said that you missed in my description something which you described as, how does one solve a problem. Well, as you, I am engaged in the education business. If I look for someone with a position analogous to the way in which I experience my own position, I can think of the teacher of composition at a school of music. When you have got a class of 30 pupils at a school of music, you cannot turn the crank and produce 30 gifted composers after one year. The best thing you can do is to make them, well, say, sensitive to the pleasing aspects of harmony. What I can do as a teacher is to try to make them sensitive to, well, say, useful aspects of structure as a thinking aid, and the rest they have to do themselves.