A new method for the GOTOs' elimination
DR. D.E ZEGOUR
B. ABBASSI
National Computing High School, Algiers
B.P 68
Oued Smar, Algiers
Abstract : - We suggest in this paper a new method of algorithm's structuration. We will first show how to move from any B-algorithm (algorithm with GOTO) to an automate expressed by its transition matrix. Then, we will show how to associate a D-algorithm ( algorithm without GOTO ) to this transition matrix. The proposed method leads to very readable algorithms and shows explicitly the semantic of the original B-algorithm compared to the existing methods.
Key-words : Algorithm, Automate, Algorithm transformation.
1
1
* Work supported by the Ministry of the research of Algiers under the research project entitled "CONCORDE".
1
1 Introduction
Earlier in programming, GOTO statement was mostly used since the only control structures were the jump statement and the conditional jump. For the designers of the first programming languages, these control structures still remained and were the basis for constructing programs. In spite of the appearance of programming languages, the use of GOTOs remains incontournable.
Authors are still divided in using the GOTO statement. Some of them believe that the use of GOTO is a powerful tool for constructing programs while others have criticised it. This controversy is summarized in the two following papers :
Dijkstra [4] affirmed that the use of GOTO has disastrous effect and proposed to remove it from all programming languages.
Knuth [5] showed a manner for structuring programs with the GOTO statement and argued that it could be a powerful tool if it is well used.
The structuration of algorithms traces its origin to the famous theorem of Bohm and Jacopinni in 1966 who conceived, for the first time, a method which transforms any flow chart to a D-algorithm ( structured algorithm with only the control structures due to Dijkstra ). The suggested transformation is completely made on the flow chart and it is not recommended since the obtained program is much less readable.
Later on, Arsac [1] proposed an other approach for eliminating GOTOs. If the transformation of Bohm and Jaccopini is not evident to implement, the one of Arsac is easily programmable since the method is based on the resolution of equations' system. however, this method is also not used because it gives a none readable program .
More information on the transformation of Bohm and Jaccopini can be found in [6].
In 1985, Williams and Chen [3] proceeded by identification in order to eliminate GOTOs in any Pascal program. Three schemes have been proposed. The inconvenient of this method is that the result is not guaranteed since the above transformation is not achieved when a scheme is not present.
In the study of the different coalesced loops, Ramshaw[7] proposed solutions for resolving all the conflicts except the "head-head conflict". Thus, he developed a method for translating programs with GOTO to ones with multilevel exits.
We propose in this work a new procedure which transforms any B-algorithm to a D-algorithm. This method is completely different from the existing ones in the literature. Firstly, we construct, with a very simple manner, an automate which is expressed with its transition matrix from any B-algorithm. Secondly, we associate to this transition matrix the corresponding D-algorithm.
The paper is organized in nine sections. The next section describes the source and target languages. Then, the general algorithm and the method through an example are presented. In the section which follows, we present some common considerations for writing the proposed algorithms. Then, we give the rewriting algorithm. We find next the principle construction of the transition matrix and the algorithm which generates the D-algorithm from the transition matrix. Refinements of the proposed algorithms are finally discussed and a conclusion is given.
2 Source and target languages
In order to present this new method which consists of eliminating GOTO statements, we define two languages namely B-language and D-language. In the former, the only control structures are jump and conditional jump. In the latter, the only control structures are the "While statement" and the "if else statement".
Any language with GOTO statement can be easily transformed to a B-language and any language with no GOTO statement can be trivially transformed to a D-language. This way, the considered languages are representatives of the two classes of languages.
We give below the syntax of the B-language and the D-language in extended Backus-Naur-Form. Curly braces denote indefinite repetition (zero or more times) and square brackets denote optionality (zero or one times).
We notice that the considered languages are not interpreted. Hence, the atomic actions are symbols of no interpreted actions drawn for the set { a, b, ...}. Similarly, the tests are symbols from the set { t1, t2, ...}
B-language
<B-algo>==<St> { ; <St> }*
<St> ==> <SimpleSt>| Label: <SimpleSt>
<SimpleSt>==> <Jump>| <CondJump> |a|b| c| d......
<Jump>==> GOTO Label
<CondJump>==> IF <Exp> GOTO Label
<Exp>==> t1|t2|t3|.....
The only control structures are conditional and unconditional jumps.
a statement may be :
- an atomic action
- an conditional jump (IF GOTO)
- a jump (GOTO)
D-language
<D-algo>==<St> {; <St>}*
<St> ==<While> |<Ifelse> | a|b|c|d|.....
<While>==>WHILE <Exp> : <St> {; <St>}*
ENDWHILE
<Ifelse> ==>IF <exp>: <St> {; <St>}*
[ELSE]<St> {; St>}* ENDIF
<Exp>==>t1|t2|t3|.....
The only control structures are the alternative and the loop.
A statement may be :
- an atomic action
- an alternative (IF THEN ELSE)
- a loop (WHILE)
3 The method
Main algorithm
For any B-algorithm we associate an automate and give its corresponding D-algorithm. Each label in the B-algorithm represents a state in the automate. Some new labels are necessary. Therefore, they are added to the B-algorithm in order to achieve the transformation.
The main algorithm is the following:
Step 1.
Label the first statement. Label also any conditional jump statement contained in the B-algorithm. If several atomic actions follow each other and they are not labelled, then gather all of them in one sequence. In addition, for each state (label), associate the corresponding condition by constructing the partnership table COND between the states and the conditions.
Step 2.
Build the transition matrix from the B-algorithm.
Step 3.
Give the corresponding D-algorithm.
Example
In order to explain the method, we suppose that each statement holds in one line. This way, we can remove semicolons. However, the algorithms presented later on are general and are written according to the grammar of the language.
Let be the following B-algorithm:
a
b
E1c
d
IF t1 GOTO E2
x
E3IF t2 GOTO E4
z
GOTO E1
E2 r
s
u
GOTO E3
u
v
E4x
y
z
Step 1 : Rewriting
After rewriting, we obtain the following algorithm :
$0[a, b]
E1[c, d]
$1IF t1 GOTO E2
[x]
E3IF t2 GOTO E4
[z]
GOTO E1
E2[r, s, u]
GOTO E3
[u, v]
E4[x, y, z]
and the following partnership table between the states and the conditions :
Step 2 : Transition matrix
The application of the step 2 gives the following transition matrix :
For each state S, if the associated condition (in the partnership table COND) is true MAT(S, True) is considered else MAT(S, False) is considered. To consider means that the action before the symbol '->' is carried out, then go to the state after '->'.
For example, if the condition associated to $1, ie T1, is false, the following statements are carried out :
x ; State := E3
Notice also that the sequence [u, v] is removed, as it is not accessible.
Step 3 : D-algorithm
This step consists of moving from transition matrix build above to the following D-algorithm :
State is a variable. F designates the final state.
{ Initialisation }
State := $0
WHILE ( State # F ) :
IF State = $0 :
a; b; State := E1
ELSE
IF State = E1 :
c; d; State := $1
ELSE
IF State = $1 :
IF t1 :
State := E2
ELSE
x; State := E3
ENDIF
ELSE
IF State = E2 :
r; s, u; State := E3
ELSE
IF State = E3 :
IF t2 :
State := E4
ELSE
z; State := E1
ENDIF
ELSE
IF State = E4 :
x; y; z; State:=F
ENDIF
ENDIF
ENDIF
ENDIF
ENDIF
ENDIF
ENDWHILE
In this algorithm, we use the control structure "IF THEN ELSE" in succession. Each "if statement" corresponds to a row of the matrix. If a state have a value always true in the table COND, give simply the corresponding actions(if they exist)followed by the modification of the current state. If a state has some condition t, give a choice between the two columns of the matrix according the logical value of t.
For example, to row E3 of the matrix we associate the following alternative :
If Cond(E3) : State := E4 Else z ; State := E1 Endif
4 Common considerations
Below, we define a statement as a couple (Label, Action). An action may be an atomic action, a "GOTO statement" or an "IF statement".
In the algorithms that follow, we shall use the following functions :
Get(St) : return the next statement in St.
Label(St) : return the label of the statement St, & if the statement does not have a label. & designates the null string.
Action(St) : return the action of the statement St.
In addition, if the action is an "IF statement",
Test(St) : return the test contained in the "IF statement" St.
We also use the function
Ref(St) : which gives the label referenced by the GOTO in the statement St.
Each element of the transition matrix is of the form a --> b. a denotes a sequence of actions and b a label of the next statement. We will need also the following functions:
MATa(State, Value) : denotes the action to undertake at the state State for the value Value
MATb(State, Value) : designates the label of the next action to undertake.
Cond(State) : condition corresponding to the state State in the partnership table COND.
5 Rewriting Algorithm
The main idea consists of rewriting the algorithm by labelling :
- the first statement (if not labelled)
- any "if statement"
- the last group of statement ( if not labelled)
This algorithm also constructs the partnership table which associates to each label the condition if the statement is a conditional jump, and the value True otherwise.
For this propose, we use :
Atomic(St) : Predicate equal to True if St is an atomic action which is not labelled.
Add(Label, t) : add the condition t to the label Label in the partnership table COND.
Output(Label, a): append the statement ( Label, a) to the algorithm being newly build.
The algorithm is the following :
i := -1
Get(St) { first statement}
IF Label(St) = & :
Inc(i) ; Label := $i
ELSE
Label := Label(St)
ENIF
Add(Label, True)
E := {St}; Get(St)
WHILE Atomic(S) :
E := E U {St}
Get(St)
ENDWHILE
Output(Label, E )
WHILE( St # & ) :
IF St is an "If statement" :
IF Label(St) = & :
Inc(i) ; Label := $i
ELSE
Label := Label(St)
ENDIF
Add(Label, Test(St))
Output(Label, Action (St) )
ELSE
IF St is a " GOTO ":
Output( Label(St), Action(St) )
ELSE
E := {St}; Get(St)
WHILE Atomic(S) :
E := E U {St}
Get(St)
ENDWHILE
Output(Label, E )
ENDIF
Get(St) { the next statement ENDWHILE }
6 Construction principle of the automate
The algorithm that follows constructs an automate expressed by its transition matrix, from the rewritten B-algorithm and the partnership table obtained in step 1. The rows of the matrix are the states( labels) and the columns are the two logical values "True" and "False".
Now, each St represents either a sequence of actions or an "if statement" or a "GOTO statement".
We use also the function Skip which ignores all the next sequences not labelled.
Get( St) { first sequence }
WHILE St # & :
IF St is an "If Statement" :
MATb ( Label(St), True) := Ref(St)
Get(St')
IF not Label(St'):
IF St' is not a "GOTO":
MATa(Label(St), False) := Action(St')
Get(St')
IF not Label(St')
IF it is a "GOTO" :
MATb(Label(St), False) := Ref(St')
Skip
ENDIF
ELSE
MATb( Label(St), False) := Label(St')
St := St'
ENDIF
ELSE
MATb( Label(St), False) := Ref(St')
Skip
ENDIF
ELSE
MATb( Label(St), False) := Label(St')
St := St'
ENDIF
ELSE
IF St is a "GOTO statement" :
MATb(LastLabel, True) := Ref(St)
Skip
ELSE
MATa(Label(St), True) := Action(St)
IF Label(St*) # & :
MATb(Label(St), True) := Label(St*)
ENDIF
Get(St)
ENDIF
ENDIF
ENDWHILE
St*, being the next statement.
Discussion :
A statement may be an " if statement", a "GOTO statement" or a group of statements.
Case of an "if statement" :
We may have the following cases :
a) "IF statement" followed by a labelled statement.
E:IF t GOTO G
X:....
In this case, we put in MATb[E, True] the Value G and in MATb[E, False] the value X.
b) "IF statement" followed by a " GOTO statement.
E:IF t GOTO G
GOTO Y
In this case, we put in MATb[E, True] the Value G and in MATb[E, False] the value Y.
c) "IF statement" followed by a group of statements, then a labelled statement.
E:IF t GOTO G
Group
X:....
In this case, we put in MATb[E, True] the Value G, in MATa[E, False] the group of statements and in MATb[E, False] the value X.
d) "IF statement" followed by a group of statements, then a "GOTO statement".
E:IF t GOTO G
Group of statements
GOTO Y
In this case, we put in MATb[E, True] the Value G, in MATa[E, False] the group of statements and in MATb[E, False] the value Y.
Case of a group of statements
a) Group of statements followed by a labelled statement.
X:Group of statements
Y:
In this case, we put in MATa[E, True] the group of statements and in MATb[E, True] the value Y.
b) Group of statements followed by a non labelled statement.
X:Group of statements
...
In this case, we put only in MATa[E, True] the group of statements.
Case of "GOTO statement"
a) a "GOTO statement" not labelled and preceded by a group of statements.
X:Group of statements
GOTO G
In this case, we put in MATb [X, True] the label G. X being the last label encountered.
b) GOTO is a labelled statement
X:GOTO G
In this case, we put in MATb [X, True] the label G.
Note :
This algorithm detects all the inaccessible sequences and ignores them.
7 Passage from the automate to the D-algorithm
Finally, we give the algorithm which builds the D-algorithm from the transition matrix obtained in step 2 and the table COND obtained in step one. In this algorithm, we use the procedure
Generate : which products a string of characters in output.
Let State be a variable containing the current state. F designates the final state.
Generate "State := $0"
Generate " WHILE State # F"
n := 1
FOR each Label in COND :
Generate "IF State = " followed by Label :
IF Cond(Label) # TRUE :
Generate "IF " +COND(St) + ":"
Generate MATa(Label, True)+";"
Generate "State:=" followed by MATb(Label,True)
Generate "ELSE"
Generate MATa(Label, False)
Generate "State:=" followed by MATb(Label, False)
Generate "ENDIF"
ELSE
Generate MATa(Label, True)
IF Label is the last state in COND
Generate "State := F"
ELSE
Generate"State:=" followed by MATb(Label,True)
ENDIF
ENDIF
IF Label is not the last state in COND
Generate "ELSE"
ENDIF
Inc(n)
ENDFOR
Generate n "ENDIF"
Generate "ENDWHILE"
8 Refinements
We may represent in table COND only the conditions, i.e. we remove all the conditions with the value true.
We may also write an even algorithm more readable. First we define the following function:
Action (State, Condition) : unrolling the action corresponding to State, then modify the State.
We have thus the simple following general algorithm :
State := initial state
WHILE State is not the final state :
Action( State, COND(State))
ENDWHILE
9 Conclusion
This work constitutes a part of project CONCORD [8] in which we made a synthesis on procedural languages.
By this work, we think we have contributed to the theory of program transformation. As we have shown, the transformation is very simple compared to ones developed until now. In addition, the resulting algorithm reflects the semantic of the original B-algorithm and it is more readable compared to algorithms obtained by the other methods. On the other hand, the method developed here is not direct due to the fact that we pass first by a conversion to an automate, then we give the corresponding D-algorithm. An implementation of the method is made in Belgacem[2]. We have exploited this work for developing a powerful tool which is the reasoning by automate for writing structured algorithms[9]. We will show that they are much more powerful than the other formalisms known for writing algorithms. First, automates are most general than flow-charts. Second, The major interest of this representation, contrary to flow-charts, is that we can move automatically to structured algorithms, i.e. ones without coalesced loops!
Acknowledgments
A major expression of thanks must go to my colleague K. Benatchba for her advice and helpful comments and suggestions.
References
1 J. ARSAC. "La construction des programmes structurés". DUNOD 1977.
2. F. BELGACEM & N. BERKANI. " Elimination des GOTOs". Mémoire d'ingénieurs d'état en Informatique. INI, Alger.
3. M.H WILLIAMS & G. CHEN. " Restructuring programs Pascal containing GOTO statement", Vol 28, n°2 1985 Page 134
4. E.W DIJKSTRA. " GOTO statement considered harmful". Comm. ACM. Vol 11 Num 3. Mars 1968 Pages 147-148
5. D.E KNUTH. " Structured programming with GOTO statement".
6. C. LIVERCY. "Théorie des programmes : schémas, preuves, sémantiques". DUNOD 1978.
7. L. RAMSHAW. " Eliminating GOTO's while preserving program structure". Com ACM. Vol 35 Num 4. Octobre 1988.
8. D.E ZEGOUR. " CONCORD : an environment of CONstruction, CORrection anD transformation algorithms". IST ( Information Software Technology), Elseiver. 1997
9. D.E ZEGOUR & B. ABBASSI. "Automates : a powerful tool for writing structured algorithms." To be submitted.
1