EWD249 - 31

Excluding side-effects of the boolean inspections and assuming the value "B2" constant (i.e. unaffected by the execution of either "S1" or "S2"), we can establish the equivalence of the following two programs:

        "if B2 then
         begin while B1 do S1 end
               else
         begin while B1 do S2 end"            (1)

and

        "while B1 do
         begin if B2 then S1 else S2 end"     (2)

The first construction is primarily one in which sequencing is controlled by a selective clause, the second construction is primarily one in which sequencing is controlled by a repetitive clause. I can establish the equivalence of the output of the computations, but I cannot regard them as equivalent in any other useful sense. I had to force myself to the conclusion that (1) and (2) are "hard to compare". Originally this conclusion annoyed my very much. In the meantime I have grown to regard this incomparability as one of the facts of life and, therefore, as one of the major reasons why I regard the choice between (1) and (2) as a relevant design decision, that should not be taken without careful consideration. It is precisely its apparent triviality that has made me sensitive to the considerations that should influence such a choice. They fall outside the scope of the present section but I hope to return to them later.

Let me give a second example of incomparability that is slightly more subtle.

Given two arrays X[1:N] and Y[1:N] and a boolean variable "equal", make a program that assigns to the boolean variable "equal" the value: "the two arrays are equal element-wise". Empty arrays (i.e. N = 0) are regarded as being equal.

Introducing a variable j and giving to "equal" the meaning "among the first j pairs no difference has been detected", we can write the following two programs.

        "j:= 0; equal:= true;
         while j ≠ N do
             begin j:= j + 1; equal:= equal and (X[j] = Y[j]) end"    (3)