This paper was first published in 1983 in the Polish journal "Projektowanie i Systemy" (Design and Systems), volume 5, pp. 75-83 (ISBN 83-04-01435-1). The paper was written in Russian but translated into Polish by Wojciech Gasparski. The English version below is a refinement of the original Russian article.

On Algorithmization of the Creative Process of Computer Program Design

Y. B. Karasik,
Thoughts Guiding Systems Corp.,
Ottawa, Canada.
e-mail:karasik@sympatico.ca

1. Program design as the process of contradictions overcoming.

Program design, or programming, is the process of decomposition of complex operations upon complex data into simple operations upon simple data, which are permissible by a programming language. The main problem of programming technologies is how to perform this decomposition so that the resulting program would indeed perform what is required. From experience it is known that when one tries to decompose complex operations and data into elementary ones right away, such decomposition most likely turns out to be erroneous. That is why the so-called "advanced methods of programming" suggest step-by-step program design, which involves gradual refinement and shaping of decomposition. Each subsequent step refines decomposition attained at the previous one. However, this approach makes only sense when we are guaranteed that at every step decomposition is performed correctly and that no errors would transpire at the subsequent steps. The "advanced methods of programming" do not guarantee that. Moreover, the erroneousness of decisions made at the initial steps of decomposition is very often not seen until decomposition is completed. The paradox of the known technologies of programming is that seemingly correct decisions at ALL steps of decomposition MAY nevertheless result in incorrect program. Here is an example.

There is seemingly nothing wrong in assuming that this program should look as follows:

completed := false;
i := 0;
while(not completed){
    record := readFile();
    if(it_is_last(record)){
       record := modification_of(record);
       completed := true;
    }
    A[i] := record;
    i++;
}

Here routine it_is_last(record) determines whether the record is last or not. In order to do that it has to try and read the next record to check to see if it encounters EOF (end of file). Hence one may assume that this routine should look as follows:

boolean it_is_last(record){
    readFile();
    if(EOF encountered) return true;
    else return false;
}

But it is easily seen that such a program would store only every second record in the array and would not work properly at all. Hence, we face a contradiction: routine it_is_last(record) has to read next record so that to determine whether the previous record was last or not, and has to not read it so that every record is stored in the array and not just every other record. Step-by-step refinement of a program's structure always gives rise to contradictions despite seemingly correct decisions made at every step of decomposition of a program's function into subfunctions, of these sub-functions into sub-sub-functions etc. Thus, the main roadblock on the way to algorithmization of program design with the help of the existing programming technologies is contradictions, which inevitably arise when these technologies are employed, and which they lack the means to resolve. This paper aims to bridge this gap by proposing the ways of contradictions resolution in the course of program design.

Methods of contradictions resolution in the course of program design

Not any contradiction can be directly resolved. Sometimes it has to be transformed into another one in order to make it resolvable. For example, contradiction "routine it_is_last(record) has to read next record and has to not read it" is not specific enough. One has to ask which specific portion of its code has to read and not to read. It is the line where readFile() is called. Hence, the above contradiction has to be specified as follows: routine readFile() has to read next record and has to not read it. This contradiction can be resolved as follows: readFile() has to read next record from file when it is called from it_is_last(record) routine; and does not have to read when called elsewhere.

Specifically, it does not have to read next record on line 4 of the main program. It may return record read by the call to it from it_is_last(record) routine. In order to do it it has to behave as follows: on the first call read and return record; on the second call also read and return record; on the third call do not read but return record read on the second call; on the fourth call read and return record; on the fifth call do not call and return record read on the fourth call, etc. The complete code looks as follows:

static Record readFile(){
   static call_number;
   static Record rec;
   if(call_number == 0 || call_number == 1 || call_number is odd) {
      rec = reallyReadFile();
   }
   call_number++;
   return rec;
}

Contradictions in program design are caused by introducing either conflicting or contradictory operations.

Contradictions caused by conflicting operations are resolved as follows:

Contradictory operation can be eliminated as follows:

Towards the technology of programming that avoids contradictions

Although developing means of contradictions resolution is important, developing means of contradictions avoidance is more important. Contradictions in programming arise due to erroneous decisions during programs design. It would be useful to create a databse of such errors and arrange them into patterns to be avoided.