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.