The Three Trinity of Programming
or
The Third Needn't, and The Second Is Not Right

Ochkov Valery, Russia, Moscow

This article starts with the classic of the program.

' Program 1 (QBasic). The method of half division - God loves Trinity

DECLARE FUNCTION F! (Arg!)

INPUT "A, B, Error"; A, B, Eps

Yleft = F(A) ' Calculation of Y on the left end of the interval

DO WHILE B - A > Eps ' Start of the while loop

X = (A + B) / 2 ' Divide the interval into half

IF Yleft * F(X) > 0 THEN ' Alternative

A = X ' Left shoulder of the alternative

ELSE B = X ' Right shoulder of the alternative

END IF ' End of the alternative

LOOP ' End of the while loop

PRINT "Y="; F(X); " at X="; X

END

FUNCTION F (A)

F = A ^ 2 - 3

END FUNCTION

Listing 1. The derivation of the square roots of the algebraic equation by the method of dichotomy use three articles - three basic algorithmic constructions: movement (statements), repetition (DO WHILE ... LOOP) and choice (IF...THEN...ELSE...END IF)

In the headline of the first program, instead of "God", we can write "E. Dijkstra" i.e. to say his three algorithmic constructions mention in the basic theorem. And the problem here is not only in the triads but in this, that, hopes have been set on this theorem for more than 30 years, people have believed in this theorem, just like they believe in God.

Lets remember it.

"Algorithm of any kind of difficulty may be achieved by the usage of three constructions: movement (operators), repetition (cycle) and choice (alternative)".

But of course more than three algorithmic constructions have been thought of. To these constructions changes can be made: i) alternatives can be added, ii) procedures can called (especially recursive subroutine), iii) branching can be done, iv) work can be done with the functions that the programmer has called v) and in the end transition to the label. But all these constructions are helpful in increasing the speed (first point of the E Dijkstra theorem), and the coding of algorithms becomes easier, but anyway, it is quite manageable without these constructions(just like the author of this article has done). Moreover, from the variety of these cycles (cycle with the verification done before, cycle with the verification done later, cycle with parameters, etc.), the while loop has been used as the basic qualitative cycle in programming (DO WHILE...LOOP), while the rest are again only helpful constructions. This, for example has had an effect in the lang. FRED which is located in the structure of the integral packet Framework, where there only is the while loop – @while(Boolean expression, cycle body) - and there isn't a until loop or a loop with parameters.

10 REM Program 2 (GW-BASIC). Quadratic equation

20 INPUT "A, B, C"; A, B, C

30 D = B ^ 2 - 4 * A * C

40 IF D >= 0 THEN PRINT "X1="; (-B + SQR(D)) / 2 / A; " X2="; (-B - SQR(D)) / 2 / A ELSE PRINT "No roots"

50 END

Listing 2. The derivation of roots of a quadratic equation- this is a classic example of a full alternative (IF ... THEN ... ELSE ...), which is used a lot in different books of programming.

' Program 3 (QBasic). Quadratic equation

INPUT "A, B, C"; A, B, C

D = B ^ 2 - 4 * A * C

Flag = -1

DO WHILE D >= 0 AND Flag

PRINT "X1="; (-B + SQR(D)) / 2 / A; " X2="; (-B - SQR(D)) / 2 / A

Flag = 0

LOOP

DO WHILE Flag

PRINT "no roots"

Flag = 0

LOOP

END

Listing 3. Algorithm for the derivation of roots of a quadratic equation using only the while loop

Program 2 and 3 prove that (depending on the programmer) it is quite manageable if we don't use alternatives: in GW-BASIC-the second program is there but in its QBasic analogue, the third program isn't there.In the third program the while loop and the variable Flag are enough to find the statements of the (real in form and boolean in content), body in the given cycles and these cycles can be used either once or not at all.

An alternative may be substituted into two while loops, literally of two accounts. First Account: let's change the perfect alternative (IF...THEN...ELSE...) into two non-perfect alternatives (IF...THEN...). This kind of substitution has been recommended for a very long time so that a few lines can be excluded in the fortran-programes. Second: change the alternatives from the two non-perfect alternatives into the while loop (DO WHILE...LOOP), whose structure can be used either once or not at all.

The third alternative - superfluous. Now the 4-7 programmes explain what is meant by "The Second Is Not Right" as in the name of the text.

10 REM Program 4 (GW-BASIC). Method of golden dissection

20 DEF FNY (X) = X ^ 2 - 3

30 INPUT "A, B, Error"; A, B, Eps: GOSUB 100: GOSUB 110

40 : IF ABS(B - A) <= Eps GOTO 80: REM problem solved

50 IF Y1 < Y2 THEN B = X2: X2 = X1: Y2 = Y1: GOSUB 100: GOTO 70

60 A = X1: X1 = X2: Y1 = Y2: GOSUB 110

70 : GOTO 40: REM New value of minimum

80 : PRINT "Y minimal="; FNY(X1); " when X="; X1

90 STOP: REM end of the basic program

100 : X1 = .618 * A + .382 * B: Y1 = FNY(X1): RETURN

110 : X2 = .382 * A + .618 * B: Y2 = FNY(X2): RETURN

120 END

Listing 4. Ask a friend of yours to divide the interval into two not-even parts. You can be sure that he will do it by the rule of the golden relation. In this case the computer divides the interval of the not known A-B, in such a way that when we are close to the minimal value it chooses only one value of the function that we are analyzing.

' Program 5 (QBasic). Method of golden dissection

DEF FNY (X) = X ^ 2 - 3

INPUT "A, B, Error"; A, B, Eps

GOSUB Right ' "Right" subroutine

GOSUB Left ' "Left" subroutine

DO WHILE ABS(B - A) > Eps ' Start of the while loop

DO ' Alternative

IF Y1 < Y2 THEN B = X2: X2 = X1: Y2 = Y1: GOSUB Right: EXIT DO

A = X1: X1 = X2: Y1 = Y2: GOSUB Left: EXIT DO

LOOP ' End of the alternative

LOOP ' End of the while loop

PRINT "Y minimal="; FNY(X1); " when X="; X1

STOP

Right: ' "Right" subroutine

X1 = .618 * A + .382 * B: Y1 = FNY(X1)

RETURN

Left: ' "Left" subroutine

X2 = .382 * A + .618 * B: Y2 = FNY(X2)

RETURN

END

Listing 5. Two program line (variables, functions and procedures) "sound" name (Left, Right), you will never forget that division is done in corresponding subroutines, where the left (A-X1) value or the right (X2-B) value in the interval where the function cannot be found decreases

An alternative may be excluded by another method i.e. we don't use the while loop but a cycle with an exit from the middle of the program. This is illustrated in the pair of programmes (4 - GW-BASIC and 5 - QBasic) derivation of a minimum and at the same time the derivation of a one-module function by the method of golden dissection.

The 3rd program can almost be written in Pascal without any changes. The 5th prog., where the perfect alternative also has been excluded, but not by two while loop but by one with two exits from the program but it should be remembered that this program is not easy to rewrite in Pascal But it should be remembered that in the basics of this language lies the basic structure of this theorem - in Pascal we need to remember that the perfect alternative has three cycles: the main while loop and the other two auxiliaries (the until loop and the loop with parameters). A cycle with several exits allows the exclusion of the perfect alternative (prog. 5) without the additional variable Flag (prog. 3). This way the while loop takes second place in the basic structural theorem(illegally, though), and the third alternative like we have already shown is not needed at all.

The value of a cycle with a subroutine (exit) is, that it can have several sub-programs and is not in the exclusion of the perfect alternative without calling new variables. Even though we can have several exits this cannot be avoided when the meaning of the logical expression changes outside the cycle nd there is a fear that at the necessary moment the change may be left out. This can only happen if in the program the additional elements of parallel programming, for example the logical expressions lean against the built-in time devices of the computer or on the state of the surroundings (is the printer on, is the paper in, is there a disk in the disk drive, is the disk formatted etc).

The cycle with exits in the program makes it easier to remove the counters from the program without using the next classical triads of programming - three methods of structural algorithm dubbing, to introduce signs and runningstart - programs 6 - 9.

10 REM Program 6 (GW-BASIC). Game "Guess the No."

20 RANDOMIZE TIMER - 32767

30 PRINT "Guess a No. from 1 to 1000 in the minimum No. of attempts."

40 A = 1 + INT(1000 * RND(1))

50 I = 0: REM Counter of attempts

60 : I = I + 1

70 PRINT I; "-th attempts";

80 INPUT B

90 IF B > A THEN PRINT "High": GOTO 60

100 IF B < A THEN PRINT "Low": GOTO 60

110 PRINT "Guessed"

120 END

Listing 6.

' Program 7 (QBasic). Game "Guess the No."

RANDOMIZE TIMER - 32767

PRINT "Guess a no from 1 to 1000"

A = 1 + INT(1000 * RND(1))

I = 0 ' Counter of attempts

B = A + 1: DO UNTIL A = B ' while loop

I = I + 1

PRINT I; "-th attempts";

INPUT B

IF B > A THEN PRINT "High" ' IF A = B THEN EXIT DO

IF B < A THEN PRINT "Low" ' IF B > A THEN PRINT "High" ELSE PRINT "Low"

LOOP ' LOOP

PRINT "Guessed"

END

Listing 7.

Programmes 6 and 7 give us a chance to the play the game "Guess a No." with the IBM, where the machine actually thinks of a No. in the range of 1 to 1000 (look at line No. 40 of prog. 6) which in the end the person playing the game must guess the No. in minimum number. of attempts. These games often illustrate the principle of double derivation. Sticking to the optimum strategy, a person must be able to divide the interval of uncertainty into two and the average No. which is found in ths interval tells the machine the quality of the taken guess(look at line 80 of prog. 6). By the answers given by IBM "High" or "Low" the person playing the game decreases his guess by two. In GW-BASIC-program 6 based on the natural string of actions: if the guess of the person is more than or less than the actual No. which has been thought of by the computer, then the computer us about it and immediately the statement GOTO goes back to the line of inquiry i.e. it asks for our new guess. The 6th program can be structured, wen we double some actions and therefore reconstruction into QBasic program 7. Here the statement GOTO the non-conditional statement has been removed, but here we get the while loop which is extra when we first look at the functions. If the value of B is not bigger than the A, and the value of B is not less than the value of A then there is no need to additionally check the equality of these numbers. But these duplicate operations have structured the program and with their help the algorithm of the game can be made out by the while loop, whose body holds the last two non-perfect alternatives (with one shoulder). In the 7th program it is more appropriate to use the until loop than the while loop. The until loop is of course thought of as a helpful construction to work with but is only used when boolean expressions, which operates with the cycle, gains the definition but only after the first fulfillment of its body, just like in the in the 7th program. Substitution of the while loop with the until loop takes place if it is necessary, like it happens while programing in the environment of the integral packet Framework: B = A + 1, for example whit program 7. This is similar to the situation in football when a player of the attacking team runs ahead of the defenceman and is the only one standing near the goal (offside).

The commentary of the 7th program shows that the substitution of the while loop with the cycle with an exit from the framework of the program makes it easier and simplifies the structure of the algorithm.

The second method of structuring illustrates a program, which solves the famous question of the known English physicist Paul Dirac (1902-1984).

"Three fishermen went to bed, do no deviate fishes. At night the first fisherman decided to leave with him fishes. But the number of fishes didn't reduce. Then he threw one and take him part of fishes. The second and the third fishermen also did the same. Is asked what is the lowest No. of fishes according to the conditions of the problem.

Paul Dirac was a master at adding different substantive prefixes "anti"-antipart, for example. And as we see it he fishes and the fish in the problem didn't change their habit so as this problem was originally solved the answer is: minus two fishes.Let's throw one "anti"-fish we'll get instead of -2,-3, we'll take one back we'll get -2 and so on and so forth.But as it always happens a mistake came up in the calculations which of course can be explained by the fact that Dirac didn't have a computer.

10 REM Program 8 (GW-BASIC). Fisherman and the fish

20 INPUT "No. of fishermen "; Fishers

30 INPUT "Change in the No. of fishes "; DeltaFish

40 INPUT "The initial No. of fishes"; StartFish

50 : P = StartFish: REM 1st fisherman counted the initial no of fishes

60 FOR I = 1 TO Fishers: REM recount of all the fishermen

70 P = P + DeltaFish: REM every fisherman either threw the fishes or caught the change in the no, of fishes

80 P = P - P / Fishers: REM and took his part

90 IF P > INT(P) THEN StartFish = StartFish - 1: GOTO 50

100 NEXT I: REM The second fisherman woke up

110 PRINT "The answer- "; StartFish; " fishes "

120 END

Listing 8.

' Program 9 (QBasic). Fishermen and the fishes

INPUT "No. of fisherman "; Fishers

INPUT "The change in the No. of fishes "; DeltaFish

INPUT "Initial No. of fishes "; StartFish = StartFish + 1 ' Nothing

DO

StartFish = StartFish - 1 ' Nothing

Flag = -1 ' Nothing

P = StartFish

FOR I = 1 TO Fishers

P = P + DeltaFish

P = P - P / Fishers

IF P > INT(P) THEN Flag = 0 ' IF P > INT(P) THEN EXIT FOR

NEXT

' IF P = INT(P) THEN EXIT DO

' StartFish = StartFish - 1

LOOP UNTIL Flag ' LOOP

PRINT "The answer - "; StartFish; " fishes "

END

Listing 9. The calculations done in the 8th and the 9th prog. give us not only one but a full line of solved p[problems (..., -110, -83, -56, -29, -2, 25, 52, ...). I think that no one will argue with me when I say that -29 and as a matter of fact -110 is less than -2. Yes, it is sad that Paul Dirac didn't have a computer.

The programmes 8 and 9 solve the problem about the fishes and the fish by the method of recombination, when the starting No. of the fishes (StartFish Ä look at line 40 of program 8) is checked and then does it satisfy the conditions of the division (cycle with parameter line 60-100) If the recombination is satisfied then the answer is ready.(look at line 110), if not then the starting No. of fishes is reduced by one(line 90), and the calculations is repeated. Now does the machine find the answer early or late. This way (just like Paul Dirac did) we are not going to confuse the fact that the No. of fishes was a negative one. For a normal person this kind of nuance would of course be confusing but a normal would not have thought of these anti-parts:this of course is an abnormal talent.

But let's now to return to our problem with the fishes and the fish. In GW-BASIC-in the 8th program the earlier interruption of the cycle with the parameters spoils the structure of the prog. She of course can be saved, if the in the prog. the comparand word is changed (Flag Ä see prog. 9). Before we enter into the cycle comparand word equals minus one (the basic truth- "presumption"). If by any chance the remainder from the division of fishes is a decimal No., then the comparant word loses its non-zero value. This would be a signal directed towards the loss of the account with the reduction of the fishes by one. The algorithm of the mechanical solution of the problem Dirac was the architect in the until loop we have another cycle with parameters with the unfulfilled alternative.

In the 9th program the line with the second the third method of structuring has been used - running start: the first No. of the fishes at first increased by one (StartFish = StartFish + 1), and then immediately it decreases in the cycle by the same No.(StartFish = StartFish - 1). This kind of movement in the prog. as lake motion a jumper at the time of the running start - takes a step back and then starts. This also pursues the goal of structuring the prog. But the removal or substitution of a few statements in the 9th prog. which are written in the commentary-just like it was used in the 7th prog. where the prog. was constructed without using the three classical methods.

In Pascal the cycle which has exits from the middle of the prog. (see. programmes 5, 7 and 9) are not very grievous. At the time of necessity the cycle can be realized by two methods. The first one is to check the cycles in any p[lace possible with the help of the lines and the statements of conditional transition (If ... Goto ...). The same way the lines act on in a prog. just like the reaction a red cloth has on a bull, make as: the cycle is written by procedures with the impregnation If... Then Exit, i.e. with the commands "If..., then the first action is to fulfill the procedures and return to the main program or to compare the procedures with a higher procedure behind the name of the procedure. A lot of programist in Pascal-reflect the calling of procedures to the basic structures of programming. In QBasic it is possible to interrupt a cycle at zany place and not only one (EXIT DO or EXIT FOR). Without a big ceremony QBasic permits deal with procedures (EXIT SUB), and with functions (EXIT FUNCTION). Language C displays even more flexibility: in C a cycle can interrupted given the control of the program even if it is at the end of the program (If...Then Break), whether at the beginning (If...Then Continue). This shows that you can be more catholic, than the roman father and there can be a better structural lang. than Pascal".

If the reader so far has not been fully confused here is something understandable, in the problem of the minimal numbers and its algorithm (meaning of the main structure theorem of Dijkstra) gives the book "Programming Languages: Ada C and Pascal. Comparison and Marks". In the book on the 72nd and 73rd pages its written: "To be up to the genealogy of control structures <...> cycles with the usage of statements (with Break ) and statements of continuation Continue are related to the class DREC1. (This kind of abbreviation could not have been thought of by a European - by B.Ž.). Theorems proven by R.Kosarau (surely not a European - Japanese), shops that the working structures are related to the class DREC1, and that they can't be formulated with the help of structures which are related to the class D (name of this class is taken from the first letter from the surname of E. Dijksrta Ä author of the basic structural theorem), which are compiled from some numbers of the conditional statement If, statements of the while loop and their combinations. Over all the operating structures, are related to the class DRECi (which has in it's composition the statement Exit(i) (or Break), which ensure the exit in the first level and the statement Cycle(i) (or Continue), which ensure the cycle is done in the first level of the enclosure, as for example in the lang Bliss), is more powerful than the operating structures which are related to the class DRECi-1. <...> Sometimes programmes which hold cycles with the usage statements Exit and Cycle, seem to be much more harder to understand. An analysis shows that the necessity of using statement Exit rarely shows up. It still has not been proven if the necessity of availability of the operating constructions is of a much higher level than the constructions of the D class." It was started for the peace of the main structural theorem but unfortunately it ended on a sad note. This last phrase of this text made the author pick up the pen.

There were battles connected to the structural prog. with the structures almost forgotten and the programist sick with a new disease Object-orientated programming (OOP) where the same triad has been crystallized (storage of info in the object, and the structure of the object and the methods of operation)   diada succession (the possibility of the outcome of the new object with the succession of structures and methods) and polymorphism (applicability of the functions with the same name for the realization of different methods so that the objects can be managed). Is all this correct and logical? And it could be that in basic of (OOP) there isn't a triad but a diode (tetrada, pentada). but this is a different dialogue.

P.S.

The magic figure 3 (used by the author) which in the article has been used in a prog. (three into three (3*3)) reminds of six (2*3) languages used in programming (BASIC, Pascal, C, fortran, FRED and the magical Bliss), and the exits there were exactly three (1*3) points:

1. During 30 years the basic structural theorem was given to us in a wrong formulation. The correct reduction is such a "An algorithm of any level of difficulty can be realized by using only two constructions: movement and repetition".

2. Alternatives are related to the auxiliary structures of operating constructions which may substituted by cycles which have two exits from the prog. - by a conditional and the non-conditional statement.

3. Pascal is based on the undone collection of structurable operating constructions.