Download Implementation of a Transformation Algorithm

Kiran Lakhotia
MSc Individual Project Report September 2005
Case 2
The second case requires a slightly more complicated implementation of the algorithm. In the
branch of a predicate containing the positive assignment to a flag, fitness gets assigned the
value of counter. The branch avoiding the assignment needs to do two things.
One, it needs to check the state of the flag, i.e. if it has already been set to true during an
iteration. This is done with if(counter==fitness). If this evaluates to true, the fitness is
incremented by 1, so when exiting the loop, the statement counter==fitness is true too.
Two, in case a test input avoided setting the flag to true, the fitness is incremented by a local
fitness function to provide ubiquitous guidance for the genetic algorithm.
...
counterFLAG ++;
if ((i == 2))
{
flag = 1;
fitnessFLAG = counterFLAG;
}
else
{
if ((counterFLAG == fitnessFLAG))
{
fitnessFLAG += 1;
}
else
{
fitnessFLAG += local1(i, 2);
}
}
...
Figure 17: Illustrating how a positive assignment to a flag is transformed. If setting the
flag to true is avoided by an iteration, the program needs to check if the flag has been
set to true by a previous iteration of the loop.
Case 3
A flag can have multiple assignments of different type, e.g. true to false or false to true. These
assignments can all be inside one loop, or spread over different loops. One assumption this
paper makes is that all flags are loop assigned. In case a flag is both, loop assigned as well
as assigned outside any body of a loop, the outside assignment is ignored by the algorithm. If
assignments to a flag are spread over different loops, the same rules as for Case 1 and 2 are
applied for each assignment.
The next case to consider is where a predicate contains an if{}elseif{}else{}
statement, with two branches leading to an assignment to a flag and the third case avoiding
an assignment. This is depicted in an AST as a simple if{}else{if{}else{}} statement,
with the else part containing another predicate.
if(i==3)
flag = 0;
else
{
if(i==2)
flag = 1;
else
i = 1;
}
Figure 18: Source code representation of how elseif statements are ordered in the
AST
To transform an if{}elseif{}else{} statement, a slight adaptation is necessary. The
‘true’ branch of the predicate follows Case 2, and the ‘false’ part Case 1. However, the
18