Prolog is a good language for building prototypes of interesting
software tools. In this assignment (suggested by R.G. Hamlet's work),
you will build prototypes for static and dynamic analysis tools.

Static error analysis techniques are designed to detect specific classes
of faults or anomalous constructs in a program without executing the program.
Most static analyzers are pessimistic programs, producing warning messages
if errors might occur on some possible execution path. lint detect bugs
in C programs, as well as pinpointing features that are nonportable or wasteful.

One of the bugs detected by lint is using uninitialized variables. However,
lint only checks that some assignment to the variable appears before its use,
regardless of the conditions required to execute the assignment. Thus
lint will not flag the following error:

main() {
int a,b;
scanf("%d",&a);/* 1 */
if (a < 0)/* 2 */
b = a;/* 3 */
printf("%d",b);/* 4 */
}

despite the existence of a path from statement 1 to 4 (e.g., [1,2,4])
that does not contain a definition of b. You are to write a Prolog
program def_clear defined as follows:

def_clear(Var,From,To,Result) - Result contains a list of stmts from From
to To, none of which contains an assignment to Var.

To make this assignment possible, assume the existence of a yacc program
that instruments programs to write a set of Prolog facts summarizing
the results of program execution. The facts will have one of the following
forms:

pstep(From,To). a possible step from stmt From to stmt To.
step(SeqNum,From,To). step SeqNum went from stmt From to stmt To.
assigned_in(Var,Stmt). variable Var is assigned a value in stmt Stmt.
used_in(Var,Stmt). the value of variable Var is read in stmt Stmt.

The yacc program analyzes programs and constructs a file containing a list
of static facts about the program.

pstep(1,2).
pstep(2,3).
pstep(2,4).
pstep(3,4).
assigned_in(a,1).
used_in(a,2).
assigned_in(b,3).
used_in(a,3).
used_in(b,4).

Your program should use these facts to produce answers to queries
of the following type.

| ?- def_clear(b,3,4,P).
no
| ?- def_clear(b,1,4,P).
P = [1,2,4]

Dynamic analysis tools analyze the results of program execution on test data.
Test coverage metrics judge the adequacy of test data. Usually, these
metrics are based on particular components of a program such as statements,
branches, or data flow definition-use (DU) paths. A DU path is any loop-free,
definition-clear path between the definition of a variable and its use. Users
must provide enough test data to justify the complexity of the program
structure (e.g., to demonstrate that a program with fewer statements, branches
or DU paths could not produce the same results). Once again, a yacc program
analyzes a source program and produces a set of facts about the possible steps
that could be taken during execution.

#include

void p(a) int a; { }

main(){
int a;
scanf("%d",&a);/* 1 */
while (a > 0) {/* 2 */
a = a - 1;/* 3 */
if (a % 2 != 0)/* 4 */
p(a);/* 5 */
} /* 6 */
} /* 7 */


pstep(1,2).
assigned_in(a,1).
used_in(a,2).
pstep(2,3).
used_in(a,3).
assigned_in(a,3).
pstep(3,4).
used_in(a,4).
pstep(4,5).
used_in(a,5).
pstep(5,6).
pstep(4,6).
pstep(6,2).
pstep(2,7).

In addition, the yacc program produces an instrumented version of the
original source program for testing.

#include

void p(a) int a; { }

main(){
int a;
int snum = 1, seqnum = 1;
FILE* facts;

facts = fopen("facts","w");

scanf("%d",&a);
fprintf(facts,"step(%d,%d,2).\n",seqnum++,snum);
snum = 2;
while (a > 0) {
fprintf(facts,"step(%d,%d,3).\n",seqnum++,snum);
snum = 3;
a = a - 1;
fprintf(facts,"step(%d,%d,4).\n",seqnum++,snum);
snum = 4;
if (a % 2 != 0)
{fprintf(facts,"step(%d,%d,5).\n",seqnum++,snum);
snum = 5;
p(a);
}
fprintf(facts,"step(%d,%d,6).\n",seqnum++,snum);
snum = 6;
fprintf(facts,"step(%d,%d,2).\n",seqnum++,snum);
snum = 2;
}
fprintf(facts,"step(%d,%d,7).\n",seqnum++,snum);
fclose(facts);
}

Executing this program with test data 1 produces the following facts file:

step(1,1,2).
step(2,2,3).
step(3,3,4).
step(4,4,6).
step(5,6,2).
step(6,2,7).

You are to write Prolog programs for branches_not_taken and du_paths_not_taken.
In branches_not_taken(S), S is a list of branches (each of which is
represented by a 2-element list) which could have been executed
(i.e., pstep facts exist), but were not (i.e., no corresponding step
fact exists). For du_paths_not_taken, you should compute two values:

pos_DU_path(Var,Beg,End,Result) - where Result is a sequence of
loop-free, definition-clear paths starting where Var is assigned(Beg)
and ending at End.

xpath - the sequence of paths executed.

du_paths_not_taken - the possible DU paths that were not returned by
x_path. Sample output for these commands appears below.

| ?- branches_not_taken(S).
S = [[4,5]] ? ;
no
| ?- du_paths_not_taken(T).
T = [3,4,5,6,2] ? ;
T = [3,4,5,6,2,3] ? ;
T = [3,4,6,2,3] ? ;
T = [3,4,5] ? ;
no