Ermakov I. E. “Industrial” loop structuring

In one of the discussions on the forum (http://forum.oberoncore.ru/viewtopic.php?p=42396#p42396) there was an example of «industrial loop» (from a compiler project), with the statement, that early exit from the loop «practically required, and it is difficult to build complex loop without it.»

The author converted this loop to equivalent regular WHILE loop.

Original loop:

LOOP
  next := calc_next(curr);

  IF (next = NIL) OR NOT p(next) OR NOT p2(first, next) THEN
    EXIT;  
  END;    

  next_transformed := transform (next);
            
  IF NOT p3(curr_transformed, next_transformed, init_transformed) THEN
    EXIT;
  END;

  IF p4() THEN
    IF f(next) # fff THEN
      EXIT;
    END;
    INC(fff);
  END;
  
  INC(zzz);
  curr := next;
  curr_transformed := next_transformed;

  mmm := bar (curr_transformed, init_transformed, zzz);
  IF p5(zzz, mmm) THEN
    selected := curr;
  END;
END;

Explanation: a subsequent satisfying to condition p() & p2() & p3() & p4() & f(next) = fff is distinguished in the sequence. The last element of this subsequence, that satisfy to p5() should be returned.

(This loop specification leads to suspicion of poor program organization on the upper level. However, even with this specification it is possible to create a strict and transparent loop.)

Additional clarification from the author: p4() is invariant to the loop parameters (i.e. just some external configuration).

It has found, that in case when p4() is invariant, there is no need to have a special counter fff. The explanation was received, that it already has some initial value before the entering the loop, i.e. = zzz + const. We will use fff as a constant inside the loop, by adding it to zzz.

http://forum.oberoncore.ru/viewtopic.php?p=42454#p42454

We see that the cycle is working on a couple of elements of the sequence (Without the knowing of the problem it is unclear, what the relations are here. So, we just follow the code). In order not to lose the thread of reasoning, we call them a and b instead of curr and next. INVAR(a, b): b = CalcNext(a). To avoid the complication, we don’t allocate variables to hold the transformation (it is the matter of the final optimization).

So, let’s write out all LOOP completion conditions:

(b = NIL) OR ~P(b) OR ~P2(first, b) OR ~P3(Transform(a), Transform(b)) OR P4() & (f(b) # count)

We can Invert this disjunction and find the condition to continue the loop. The loop works on the sequence until one of conditions become false (full pass through initial subsequence, which elements have conjunction of 4 conditions).

The benefit of the loop - remembering the last encountered element that satisfies condition p5().

So, the non-optimized version of the loop looks as follow:

b := CalcNext(a);
count := 0;
WHILE (b # NIL)
   & P(b) & P2(first, b)
   & P3(Transform(a), Transform(b), init_transformed)
   & (~P4() OR (f(b) = count + fff))
DO
   IF p5(count+1, Bar(Transform(a), init_transformed, count+1) THEN
      selected := a
   END;
   INC(count);
   a := b;
   b := CalcNext(b)
END;

Tranform() requires an argument, not equal to NIL. Note, that all calls of Tranform(b) inside the loop are protected by the first conjunct b # NIL (precondition a # NIL is ensured by task). A qualified programmer should be able to use an abbreviated semantics of logical operations cand and cor (which is mandatory in all modern languages).

To avoid recalculating of Transform, we optimize the code by introducing additional variables ta and tb (and don’t forget to protect Transform(b) calculation by IF b # NIL )

The most important principle (follows from «divide and rule»): first we create transparent base version, then we do code optimization. The base version is stored next to the optimized one as the primary code. Any changes are made in the base version first, and then in the optimized final one.

ta := Transform(a);
b := CalcNext(a);
IF b # NIL THEN tb := Transform(b) END;
count := 0;
WHILE (b # NIL)
   & P(b) & P2(first, b)
   & P3(ta, tb, init_transformed)
   & (~P4() OR (f(b) = count))
DO
   IF p5(count+1, Bar(ta, init_transformed, count+1) THEN
      selected := a
   END;
   INC(count);
   a := b; ta := tb;
   b := CalcNext(b);
   IF b # NIL THEN tb := Transform(b) END
END;

Sure, we demonstrated that coding the loop without early exit is as easy, as with it.

However, the opinion about the fact that the proposed version is better, is divided.

An argument in support of original loop version is that “it agrees with the linear thinking: read and gradually understand how it works.»

In this regard we can note the following. Firstly, the basic requirement is transparency of composed structure’s properties. And we have to understand work of the loop by use of tool of reasoning, rather than by following program instructions (the loop must be built by reasoning, rather than by a gradual selection of instructions). The main sense of the loop is its goal — the final state, to which the loop must bring (the postcondition to ensure). The state of some possible classes (for example, the search may have two or more results: not found, found A, found B, etc.). As for work performed inside the loop body — it is not the sense of loop, It is just the routine work performed to get from initial state to the target. The simpler are these internal actions, the better is result. And of course, they do not have to include the making decision about the goal achievement.

Secondly, this topic has provoked further discussion (http://forum.oberoncore.ru/viewtopic.php?t=2348), which led to understanding of the following problem: most of programmers doesn’t follow structural approach to the programing (here the word «structural» we use in term of common sense, rather than in connection with structured programming). They consider the program as the literary text, which programmer-“writer” have to write to describe the actions required to perform by computer. Moreover, there is even a kind of «artistic timidity” in this approach.

Conclusion: Most of programmers doesn’t consider the program as an engineering system composed of structures connected according to the certain rules. And it is a real problem for the evolution of IT as an engineering activity. The mandatory requirement for engineering activities is the presence of strict (usually mathematically formalized) methods to analyze and ensure properties of created objects, deriving them from the properties of used elements and components. How it may look for software, has been shown, for example, in the «Discipline of programming» by Dijkstra.

Library, Ermakov I.E., Khaliullin N., Education