TRC - expert system building tool (part 4 of 8)
sources-request at panda.UUCP
sources-request at panda.UUCP
Sat Feb 8 22:23:49 AEST 1986
Mod.sources: Volume 3, Issue 112
Submitted by: ihnp4!dicomed!ndsuvax!nckary (Daniel D. Kary)
This is NOT a shell archive. Simply delete everything up to and including
the cut mark and save the result as reference.2.doc.
Dan Kary
ihnp4!dicomed!ndsuvax!nckary
-------------- cut here ---------------
- 23 -
PART TWO - OUTPUT
_8. _O_V_E_R_V_I_E_W
The output of TRC consists of several procedures writ-
ten on several different files. The files contain the
definitions and declarations of the data objects to be mani-
pulated by the TRC generated inference engine, procedures to
manipulate those data objects and a procedure which embodies
the rules.
The output of TRC is written on several files in the
current directory. The file names generated are; add.c,
dump.c, free.c, loop.c, misc.c, search.c relink.c,
backtrack.c, profile.c, zero.c and save.c. In addition to
these files, the user must provide at least a main procedure
which will invoke the inference engine, e.g.:
main()
{
/* 'loop' is the name of the
procedure that embodies
the rules and controls
testing the rules */
loop();
}
A sample Makefile is given here, the file main.c is
user supplied code.
# Makefile for expert systems generated by TRC
PROG = loop
OBJS = add.o backtrack.o dump.o free.o loop.o \
misc.o profile.o relink.o save.o \
search.o zero.o main.o
INCS = loop.h
CC = cc
all: $(PROG)
$(CC) -c -O $<
$(OBJS): $(INCS)
$(PROG): $(OBJS)
$(CC) -o $@ $(OBJS) $(LIBS)
_9. _C_O_M_M_O_N _P_R_O_C_E_D_U_R_E_S
There are several utility procedures that are generated
for each input file which are not dependent on the input.
- 24 -
These procedures, written on the file 'misc.c' perform rela-
tional testing.
test_int (a,b)
int a, b;
{
if(a < b) return(4);
if(a == b) return(2);
return(1);
}
test_double (a,b)
double a, b;
{
if(a < b) return(4);
if(a == b) return(2);
return(1);
}
test_string(a,b)
char *a, *b;
{
int i;
i = strcmp(a, b);
if(i < 0) return(4);
if(i == 0) return(2);
return(1);
}
The relational operators are bit encoded in an integer;
'less-than' occupies bit two, 'equality' occupies bit one
and 'greater-than' occupies bit zero. Each of these 'test'
procedures returns an integer which indicates the relation
between the operands. Examples of calls to these procedures
are included in section X.X.X. There are eight possible
values for a bit encoded relational operator; the generated
code:
< = >
0 0 0 /* never match */
0 0 1 /* greater-than */
0 1 0 /* equal */
0 1 1 /* greater-than-or-equal */
1 0 0 /* less-than */
1 0 1 /* not-equal */
1 1 0 /* less-than-or-equal */
1 1 1 /* don't care */
In addition to the testing procedures, a procedure for
dynamically allocating memory is written on the file
'misc.c'. This procedure checks for the out of memory
- 25 -
condition. Using this procedure to allocate memory obviates
the need to check for the out of memory condition elsewhere
in the code.
char *myalloc(n)
int n;
{
char *r;
r = (char *) malloc(n);
if(r == NULL){
fprintf(stderr,"OUT OF MEMORY");
fprintf(stderr,"TRC IS EXITING");
exit(0);
}
return(r);
}
_1_0. _D_A_T_A _O_B_J_E_C_T_S
At several points in PART ONE, it was mentioned that a
list is maintained for each object that has at least one
element. Objects that do not contain elements can not be
distinguished from one another, so no list is maintained,
only a count of how many there are is needed. The struc-
tures those lists are built from are defined in the file
'loop.h'. The example below gives a sample TRC definition
part and the output that might be generated with that input:
Input:
%%
A
B (B1 : INT
B2 : FLOAT
B3 : STRING
B4 : POINTER)
%%
Output:
#define A 0
#define A_max 2
#define B 1
#define B_max 2
struct B_struct {
int B1;
double B2;
char *B3;
struct B_struct *B4;
int MARK;
struct B_struct *prev;
struct B_struct *next;
} *B_list[B_max], B_empty[2], *B_temp[B_max];
- 26 -
There are two '#define' statements for each object.
The first defines the object name to be an integer. This
name is used for indexing arrays. The intention is to make
code more readable by using the name of the object that is
being referred to rather than a literal index number. At
the points in the output code where these names are used,
their meaning will be explained. The second '#define' asso-
ciated with each object is used for specifying the number of
pointers that are needed for each object. Since each rule
is completely independent of each other rule, the same
pointers may be reused in each rule. The maximum number of
pointers needed is the maximum used by any single rule.
Each object with at least one element has an associated
structure. In this example the object A has no elements and
therefore no structure. The object B contains four ele-
ments, one of each type. The structure is named 'B_struct',
each structure will be similarly named by appending
'_struct' to the object name. A data object will be
included in the structure for each element that was defined
for the object. The element names defined in the input are
used in the output, again to keep the output code readable
and meaningful. The correspondence of input data types to
output data types is straight forward; INT translates to
int, FLOAT to double, STRING to char *, and POINTER to a
pointer to a structure of the type that contains the
POINTER. The POINTER type is included for users who wish to
extend STM with user supplied code. There is no support for
testing or searching POINTERs or anything they may point to.
The 'B_list' and 'B_temp' pointers are used as free
variables and place holders in the inference engine. The
'B_list[0]' pointer points to the list of B objects. STM
consists of the various '*_list[0]' pointers, the lists they
point to and the count of how many objects of each type
exist at any given moment.
_1_1. _M_A_N_I_P_U_L_A_T_I_N_G _T_H_E _D_A_T_A
There are three basic manipulations that can be per-
formed on the data in STM, an object can be added to STM, an
object can be deleted from STM and STM can be searched for
the existence of an object with given elements. Since each
of the object types is defined by a separate structure,
separate add, delete and search procedures must be created
for each object type. The following sections give an exam-
ple and an explanation of how each procedure is generated.
_1_1._1. _A_D_D _P_R_O_C_E_D_U_R_E_S
For each object that is defined, a procedure is gen-
erated for inserting structures into the list associated
with the object. These procedures are written on the file
'add.c'. The parameters that are passed to this procedure
- 27 -
are the values that are to be assigned to the elements of
the object. The parameters are listed in the order that the
elements were declared, e.g.:
INPUT:
A
B (B1 : INT
B2 : FLOAT
B3 : STRING
B4 : POINTER)
OUTPUT:
add_A_struct()
{
token[A]++;
}
add_B_struct(B1, B2, B3)
int B1;
double B2;
char *B3;
{
struct B_struct *temp;
temp = (struct B_struct *)
myalloc(sizeof(struct B_struct));
temp->B1 = B1;
temp->B2 = B2;
temp->B3 = (char *) myalloc((strlen(B3)) + 1);
strcpy(temp->B3, B3);
temp->MARK = 0;
temp->next = B_list[0];
temp->prev = NULL;
if(B_list[0])
B_list[0]->prev = temp;
B_list[0] = temp;
token[B]++;
}
Since the A object contains no elements, adding an A
object is trivial; the count is simply incremented. The
variable 'token' is an integer array sized to have one
integer for each object type. If there are N object types
token is an array of N integers, indexed 0 through N-1. In
'add_A_struct' the array 'token' is indexed by A. Recall
that A, the name of a type of object, was defined to be an
integer, in this case 0. The integer 'token[0]' or
'token[A]' is the count of how many objects of type A exist.
The procedure 'add_B_struct' is typical of add pro-
cedures for objects with elements. The parameters passed in
are the values that are to be assigned to the elements of
the new object. Even though B_struct includes a POINTER
- 28 -
object, no value is assigned to that pointer. As has been
mentioned earler, there is no support for the pointer type
in TRC generated code. The code is very straight forward;
allocate a structure, initialize it's elements (note that
space is allocated for strings in the add procedure), insert
it at the head of the doubly linked list and increment the
count (token[B]++).
The file also contains the procedure 'init()'. This
procedure is based on the contents of the STM section of
code. For each statement in STM, a statement appears in
init. The statements are simply calls to the various add
procedures. The calls are made in an order opposite the
order the STM statements are listed. Since all additions to
lists are made as insertions at the head of the list,
inverting the order causes the final list to contain the
objects in the order they were actually listed, e.g:
INPUT:
%%
A
B
5A
B (B1 => 7
B2 => 6.6
B3 => "THIS")
5 B (B1 = 2)
%%
OUTPUT:
init()
{
int i;
for(i = 0; i < 5; i++)
add_A_struct(2, 0.0, "");
add_B_struct(7, 6.6, "THIS");
for(i = 0; i < 5; i++)
add_A_struct();
add_B_struct(0, 0.0, "");
add_A_struct();
}
As you can see, this facility is pretty crude, each
element that is listed in STM becomes a literal value in the
code. These literal values are then copied into dynamically
allocated memory, so there are actually two copies of all
the data in memory. The intention is that the STM section
and the init procedure will be used primarily during
development and testing and will be replaced by a user
developed front end that will collect the data and create
the dynamic structures for the TRC code. It is possible
that there is some small amount of data that must always be
- 29 -
loaded into STM for a given set of problems, it may be con-
venient to have the init procedure load this data into STM.
_1_1._2. _M_A_R_K _P_R_O_C_E_D_U_R_E_S
For each object that is defined, a procedure is gen-
erated for deleting structures from the list associated with
the object. These procedures are written on the file
'free.c'. The parameter passed to this procedure indicates
which object is to be deleted from the list, e.g.:
INPUT:
A
B (B1 : INT
B2 : FLOAT
B3 : STRING
B4 : POINTER)
OUTPUT
free_A_struct()
{
token[A]--;
}
free_B_struct(start)
int start;
{
int i;
for(i = start; i < B_max; i++)
if(B_list[i]){
if(B_list[i]->prev == NULL)
B_list[0] = B_list[0]->next;
else
B_list[i]->prev->next = B_list[i]->next;
if(B_list[i]->next)
B_list[i]->next->prev = B_list[i]->prev;
free(B_list[i]->B3);
free(B_list[i]);
B_list[i] = NULL;
i = B_max;
token[B]--;
}
}
As in the add procedures, the procedure to delete an
object with no elements is trivial; decrement the count of
objects of that type. The procedure 'free_B_struct' is typ-
ical of procedures for deleting an object from a list.
Recall that 'B_list[0]' points to the list of B objects
in STM and that the other 'B_list' pointers are used as free
variables. Each match statement in the situation part
- 30 -
causes STM to be searched for an object. If an object that
matches the test exists in STM, a pointer to that object is
returned and assigned to one of the pointers in the 'B_list'
array. Recall that only objects that were found in the
situation part can be MARKed in the action part and that
objects may be MARKed by name or the order in which they are
found.
There are two cases, the case where a named object is
to be MARKed and the case where the first object found is to
be MARKed. In the case where a named object is to be
MARKed, the name of the object is translated to the index
number of the pointer that points to that object. This
index number is passed to the free procedure. In cases
where the object is being MARKed based on the order it was
found, the index 1 (the first free variable used) is passed.
Examples of calls to 'free_B_struct' are given in section
X.X.X.
The array of pointers to objects of the given type
(B_list in this case) is searched for the first one that
points to an object. This object is unlinked from the list,
any space allocated for strings in the object being deleted
is freed and finally the space occupied by the structure
itself is freed. The count of objects in the list is decre-
mented and the 'for' loop counting variable is set to the
exit condition.
_1_1._3. _S_E_A_R_C_H _P_R_O_C_E_D_U_R_E_S
For each object that is defined, a procedure is gen-
erated for searching list associated with the object. The
procedure simply performs a linear search on the list in
question. The RECURSIVE search strategy is implemented as
multiple calls to the LINEAR search procedure. These pro-
cedures are written on the file 'search.c'. The parameter
passed to this procedure indicates where in the list to
begin searching, e.g.: INPUT:
A
B (B1 : INT
B2 : FLOAT
B3 : STRING
B4 : POINTER)
OUTPUT:
struct B_list *search_B_list(index,
B1, B1_relop,
B2, B2_relop,
B3, B3_relop)
int index, B1_relop, B2_relop, B3_relop;
int B1;
double B2;
char *B3;
- 31 -
{
int flag
struct B_struct *temp;
temp = B_temp[index];
while(temp){
if(temp->MARK == 0){
flag = 7;
if(flag & test_int(temp->B1, B1) & B1_relop);
else flag = 0;
if(flag & test_double(temp->B2, B2) & B2_relop);
else flag = 0;
if(flag & test_string(temp->B3, B3) & B3_relop);
else flag = 0;
if(flag){
temp->MARK = 1;
return(temp);
}
}
temp = temp->next;
}
return(NULL);
}
Since the object A has no elements, there is no list
and no search procedure for A objects. In the procedure to
search the B list the first parameter, 'index', is the index
of the pointer that points to the point in the list where
the search is to begin. The remaining parameters are the
value that each element is to be compared against and the
bit encoded relational operator for the comparison.
The first test (temp->MARK==0) checks to see if the
object is already 'in use'. Each object mentioned in the
situation part must match a unique object, the same object
can not match two situation part statements. An object is
marked as 'in use' by setting MARK to non-zero. If the
object is not 'in use', it's elements are tested, one at a
time, against the required values with the required rela-
tional operator. The procedures test_int, test_float and
test_string return the bit encoded relation of the two
values. This relation is bitwise ANDed with the bit encoded
relational operator that was passed in. If the result of
the bitwise AND is non-zero, the relation is true for those
two values. The 'flag' variable ensures that if one test
fails, all subsequent tests will fail.
If an object is found where all elements match the
desired values, it's MARK integer is set to one to indicate
that it is 'in use' and a pointer to that object is returned
to the calling procedure. If one or more elements of an
object fail a test, the next object in the list is tested.
If all objects are tested and none match, a NULL pointer is
- 32 -
returned.
This search procedure will work only for searches where
the value that is being searched for is known before the
call. In cases where an element is being compared to some
other element of the same object, a slightly different ver-
sion of the search procedure is generated, e.g.:
INPUT:
%%
B (B1:INT
B2:INT
B3:INT)
%%
%%
R1:
(B.B1 == B.B2)
(B.B3 < B.B1
B.B1 > B.B2)
(B.B3 < B.B2)
=>
MARK B B B
;
%%
OUTPUT:
struct B_struct *search_B_struct(index,
B1, B1_relop, B1_case,
B2, B2_relop,
B3, B3_relop, B3_case)
int index, B1_relop, B2_relop, B3_relop;
int B1;
int B2;
int B3;
{
int flag;
struct B_struct *temp;
temp = B_temp[index];
while(temp){
if(temp->MARK == 0){
flag = 7;
switch(B1_case){
case 0:
if(flag & test_int(temp->B1, B1)
& B1_relop);
else flag = 0;
break;
case 1:
if(flag & test_int(temp->B1, temp->B2)
& B1_relop);
else flag = 0;
break;
default: flag = 0;
- 33 -
}
if(flag & test_int(temp->B2, B2)
& B2_relop);
else flag = 0;
switch(B3_case){
case 0:
if(flag & test_int(temp->B3, B3)
& B3_relop);
else flag = 0;
break;
case 1:
if(flag & test_int(temp->B3, temp->B1)
& B3_relop);
else flag = 0;
break;
case 2:
if(flag & test_int(temp->B3, temp->B2)
& B3_relop);
else flag = 0;
break;
default: flag = 0;
}
if(flag){
temp->MARK = 1;
return(temp);
}
}
temp = temp->next;
}
return(NULL);
}
As can be seen in the example, the procedure is quite
similar. A 'case' variable has been added to the parameter
list for each element which might be compared to another
element of the same object. Case 0 is the situation where
an element is being compared to a value, all other cases are
comparisons of an element to another element of the same
object. Only the cases that are actually used are gen-
erated, not all possible cases.
There is an obvious code overhead for comparing ele-
ments within an object, but this overhead occurs only once
for each type of comparison. Subsequent rules could include
similar element to element comparisons without adding any
additional code overhead.
_1_2. _T_R_A_N_S_L_A_T_I_N_G _R_U_L_E_S
The LTM section is translated to a single procedure
named 'loop' which is written on the file 'loop.c'. An
inference engine is executed by calling the procedure
'init', which is written on the file 'add.c' followed by a
- 34 -
call to 'loop'. The loop procedure will test rules in the
order they were listed until no rule's situation part is
true or until the user code executes a return or exit. A
simple two rule system will be used to illustrate the trans-
lation:
INPUT:
%%
B (B1:INT
B2:INT
B3:INT)
%%
%%
R1:
EMPTY B NAMED
(B.B1 == B.B2)
{
$NAMED.B1 = some_procedure();
if(some_other_procedure($NAMED.B1))
$FAIL.
}
(B.B1 != NAMED.B1)
=>
MARK B B
{
printf("Rule R1 fired0);
}
;
R2:
RECURS
(B.B1 != 7)
(^B FIRST
B.B1 == 7)
(B.B2 <= FIRST.B3)
=>
MARK FIRST
ADD B (B1 => 0
B2 => FIRST.B3
B3 => FIRST.B2)
;
%%
OUTPUT:
loop()
{
int i;
Start:
R1:
if((token[B] >= 2) &&
1){
B_temp[1] = B_list[0];
if((B_list[1] = search_B_struct
(1, 0, 2, 1, 0, 7, 0, 7)) == NULL){
restore();
- 35 -
goto R2;
}
B_empty[0].B1 = some_procedure();
if(some_other_procedure(B_empty[0].B1))
{
restore();
goto R2;
}
B_temp[2] = B_list[0];
if((B_list[2] = search_B_struct
(2, B_empty[0].B1, 5, 0, 0, 7, 0, 7)) == NULL){
restore();
goto R2;
}
for(i = 0; i < 2; i++)
free_B_struct(1);
restore();
printf("Rule R1 fired0);
goto Start;
}
R2:
if((token[B] >= 3) &&
1){
B_temp[1] = B_list[0];
R2_B_1:
if(B_list[1])
B_list[1]->MARK = 0;
if((B_list[1] = search_B_struct
(1, 7, 5, 0, 0, 7, 0, 7)) == NULL){
restore();
goto End;
}
B_temp[1] = B_list[1]->next;
B_temp[2] = B_list[0];
R2_B_2:
if(B_list[2])
B_list[2]->MARK = 0;
if((B_list[2] = search_B_struct
(2, 7, 2, 0, 0, 7, 0, 7)) == NULL){
goto R2_B_1;
}
B_temp[2] = B_list[2]->next;
B_temp[3] = B_list[0];
R2_B_3:
if(B_list[3])
B_list[3]->MARK = 0;
if((B_list[3] = search_B_struct
(3, 0, 7, 0, B_list[2]->B3, 6, 0, 7)) == NULL){
goto R2_B_2;
}
B_temp[3] = B_list[3]->next;
add_B_struct(0, B_list[2]->B3, B_list[2]->B2);
free_B_struct(2);
restore();
- 36 -
goto Start;
}
End:
return(1);
}
A rule is translated to an extended 'if' statement.
Basically, "if situation then action". Each rule begins
with a label that repeats the rule label from the input.
The label 'Start' marks the beginning of the rules and the
label are included as a convenient way to exit (goto End;)
or restart (goto Start;).
The code for rule 'R1' begins at the label 'R1' and
ends at the label 'R2'. The first statement, "if((token[B]
>= 2))", is a pre-test. The array 'token[]' contains a
count of how many objects are in each list. Token[B] is the
count of how many objects are in the B list. Since rule
'R1' specifys two objects of type B in it's situation part,
it is pointless to search the B list if it contains fewer
than 2 objects. A statement similar to this is the first in
every rule. STM is never searched unless there are enough
objects that it is possible for the rule to fire. If this
initial test fails, testing will continue at label 'R2'.
The next statement, 'B_temp[1] = B_list[0];' initial-
izes a pointer to point to the beginning of the B list. The
index of this pointer is passed to the search procedure.
This use of indirection is not necessary in LINEAR rules but
it is convenient in RECURSIVE rules, the same calling tech-
nique is used by both search strategies to simplify the code
generation.
The call to the search procedure is embedded in an 'if'
statement along with an assignment to the free variable
pointer that will point to the object if it exists in STM.
The parameter list in this call consists first of '1', the
index of the temp pointer that indicates the start of the
search. The next value '0', is the value that the first
declared element, 'B1', is to be compared against. The next
parameter, '2', is the bit encoded relational operator,
equality. The next parameter, '1', is the 'case' of this
test. Since it is not zero, 'B1' is not being compared to
the value but rather is being compared in this case to the
element 'B2' of the same object. Values for elements 'B2'
and 'B3' were not specified, so those parameters are filled
in with the default value of '0' and relational operator '7'
which is the bit encoded 'don't care' operator. If 'NULL'
is returned, the object does not exist in STM and the rule
fails. A linear rule is made to fail by clearing all free
variables (restore();) and continuing with the next rule
(goto R2;).
- 37 -
If the first test does not fail, execution continues
with the next statement, which is the translated version of
the embedded c-code from rule 'R1'. The string '$NAMED' is
translated to 'B_empty[1]' which is the name of the struc-
ture that was named by the EMPTY statement. The string
'$FAIL.' is translated to the statements "restore(); goto
R2;", which cause the rule to fail in the standard manner.
The next 'if' statement is identical in form to the
previous one, only the values of the elements are different.
In this case element 'B1' is being compared to 'NAMED.B1'
which, again, is translated to B_empty[0].B1. If this test
fails, the pointers will be cleared and execution will con-
tinue at 'R2'. If it does not fail, the action part is exe-
cuted.
The action part of rule 'R1' consists of a MARK state-
ment and c-code which contains a 'printf' call. The MARK
statement is translated to a 'for' loop which deletes the
first object that was found in each of it's calls to
'free_B_struct'. The 'restore();' statement follows all ADD
and MARK statements in the action part to clear any active
free variables. The c-code 'printf' comes next followed by
'goto Start;' which causes the rule list to be searched
again for the first rule whose situation part is true.
The form of the second rule is quite similar to the
first rule. Since rule 'R2' is RECURSIVE, some minor
differences are evident. The first difference is that the
start of each test for the existence of an object is
labelled. This is to permit backing up to the previous
test. The second difference is that only the first test
contains the 'restore' and 'goto' statements. All other
tests simply back up one position if they fail. The
'B_temp' variables now store the location where the search
is to be restarted if some test fails.
In the action part of rule 'R2', the call to
'free_B_struct' passes the value '2', indicating that the
second object that was found is the one to delete. This was
specified with the statement 'MARK FIRST', where the object
named 'FIRST' was the second object of type B specified in
the situation part.
_1_3. _O_P_T_I_O_N_S
Options may cause additional procedures to be generated
and sometimes cause standard procedures to be modified.
This section will detail the effects each option has on the
output.
- 38 -
_1_3._1. _P_R_O_F_I_L_E
The intention of the profile option is to provide a
summary of the execution of the inference engine. The pro-
file option causes the procedure 'loop' to be modified and
an additional procedure is written on the file 'profile.c',
e.g.:
INPUT:
%%
B (B1:INT
B2:INT
B3:INT)
%%
%%
PROFILE
R1:
(B.B1 == B.B2)
(B.B1 != B.B2)
=>
MARK B B
;
R2:
(B.B1 != 7)
(^B FIRST
B.B1 == 7)
(B.B2 <= FIRST.B3)
=>
MARK FIRST
;
%%
OUTPUT:
loop()
{
int i;
Start:
test_profile[0]++;
R1:
test_profile[1]++;
if((token[B] >= 2) &&
1){
B_temp[1] = B_list[0];
R1_B_1:
test_profile[2]++;
if((B_list[1] = search_B_struct
(1, B_list[1]->B2, 2, 0, 7, 0, 7)) == NULL){
restore();
goto R2;
}
B_temp[2] = B_list[0];
R1_B_2:
test_profile[3]++;
if((B_list[2] = search_B_struct
- 39 -
(2, B_list[1]->B2, 5, 0, 7, 0, 7)) == NULL){
restore();
goto R2;
}
fire_profile[1]++;
for(i = 0; i < 2; i++)
free_B_struct(1);
restore();
goto Start;
}
R2:
test_profile[4]++;
if((token[B] >= 3) &&
1){
B_temp[1] = B_list[0];
R2_B_1:
test_profile[5]++;
if((B_list[1] = search_B_struct
(1, 7, 5, 0, 7, 0, 7)) == NULL){
restore();
goto End;
}
B_temp[2] = B_list[0];
R2_B_2:
test_profile[6]++;
if((B_list[2] = search_B_struct
(2, 7, 2, 0, 7, 0, 7)) == NULL){
restore();
goto End;
}
B_temp[3] = B_list[0];
R2_B_3:
test_profile[7]++;
if((B_list[3] = search_B_struct
(3, 0, 7, B_list[2]->B3, 6, 0, 7)) == NULL){
restore();
goto End;
}
fire_profile[2]++;
free_B_struct(2);
restore();
goto Start;
}
End:
test_profile[8]++;
return(1);
}
}
The 'loop' procedure that is generated with the PROFILE
option turned on is differs from the standard procedure in
several ways. Each test in each rule is labeled whether it
is RECURSIVE or not. Each label is followed by a statement
- 40 -
of form 'test_profile[N]++', causing the array test_profile
to maintain a count of how many times the following code was
executed. The action part of each rule begins with a state-
ment of form 'fire_profile[N]++', causing the array
fire_profile to maintain a count of how many times each rule
fired.
The PROFILE option causes the arrays test_profile and
fire_profile to be defined and properly sized. It also
defines two character arrays, label_names[] and rules[] to
be defined. These character arrays contain the names of
each label and each rule respectively. The procedure
print_profile is also generated. This procedure will print
the names of each label and it's associated count on the
standard output, e.g.:
OUTPUT:
print_profile()
{
int i, t;
t = 0;
printf("0ules Tested0);
for(i = 0; i < 9; i++){
printf("%d%s0,test_profile[i], label_names[i]);
t += test_profile[i];
}
printf("%d0, t);
t = 0;
printf("0ules Fired0);
for(i = 1; i < 3; i++){
printf("%d%s0,fire_profile[i], rules[i]);
t += fire_profile[i];
}
printf("%d0, t);
}
_1_3._2. _T_R_A_C_E
The TRACE option causes the 'loop' procedure to be
modified and an additional procedure is written on the file
'misc.c'. The modification to 'loop' is simply the inclu-
sion of a procedure call of form 'append_trace(N);' (where N
is an integer literal) in the action part of the rule. The
parameter is the index of the name of the rule in the char-
acter array 'rules' that is generated by the PROFILE option.
The PROFILE option only keeps a count of the number of times
a rule fires, the TRACE option records the ORDER that the
rules were fired.
struct trace {
int rule;
struct trace *next;
} *trace_front, *trace_back;
- 41 -
append_trace(i)
int i;
{
struct trace *temp;
temp = (struct trace *) myalloc (sizeof(struct trace));
temp->rule = i;
temp->next = NULL;
if(trace_front){
trace_back->next = temp;
trace_back = trace_back->next;
}
else trace_front = trace_back = temp;
}
_1_3._3. _D_U_M_P
The DUMP option generates a set of procedures written
on the file 'dump.c'. A procedure of form
'dump_NAME_struct()' (where NAME is the name of the object)
is generated for each object declared in the definition sec-
tion. There is also a procedure 'dump_stm()' which simply
calls the other dump procedures in the order that the
objects were defined. Each procedure prints the number of
objects in that list and the current values of the elements
of each object in tabular form on the standard output.
INPUT:
%%
A
B (B1:INT
B2:INT
B3:INT)
%%
OUTPUT:
dump_stm()
{
dump_A_struct();
dump_B_struct();
}
dump_A_struct()
{
printf("0umping A list (%d)0,token[A]);
}
dump_B_struct()
{
int i;
struct B_struct *temp;
i = 1;
- 42 -
printf("0umping B list (%d)0,token[B]);
temp = B_list[0];
while(temp){
printf("%d.%d%d%d0, i
, temp->B1
, temp->B2
, temp->B3);
temp = temp->next;
i++;
}
}
_1_3._4. _B_A_C_K_T_R_A_C_K
The BACKTRACKing option is easily the most complex.
While other options usually have a minor effect on the out-
put, BACKTRACKing will often double the size of the code
generated by TRC. BACKTRACK modifies the add and loop pro-
cedures and generates two new procedures, insert_backtrack
and backup, on the file 'backtrack.c'.
The intent of backtracking is to make it possible to
undo the action part of a rule and continue as if the rule
had never fired. This facility is useful in systems where
the first possible path through the problem space may not
lead to a solution or may not lead to the preferred solu-
tion. In the code produced by TRC, backtracking will occur
whenever no rule's situation part is true and there is a
rule which can be undone.
A rule is undone by restoring STM to the state it was
in before the rule fired and continuing testing at the rule
following the rule being undone. There are two obvious ways
to restore STM. The first is to save all of STM each time a
rule fires. To undo a rule, simply replace STM with the
previously saved version. This strategy can be expensive in
time and space if STM is large and/or many rules fire. The
second strategy is to save only the modifications to STM, to
restore STM simply reverse the modifications. The second
strategy is employed by TRC.
The backtracking strategy is implemented by building a
stack in memory which contains all known modifications made
to STM by a rule which fires. The only modifications that
the backtracking code is aware of are those modifications
made by ADD and MARK statements in the action part or by
calls to add and relink (discussed below) procedures in
embedded c-code in the action part. Modifications made by
embedded c-code that do not use the add or relink procedures
will not be known to the TRC code. It is the responsibility
of the knowledge engineer to insure that any modifications
that must be undone are known to TRC.
- 43 -
The backtracking stack is built in the following
manner; whenever a rule fires a new structure is placed on
the backtrack stack. This structure contains a count of how
many of each object are added by this rule. Since all adds
are insertions to the front of the list, the specific
objects that were added are implicitly known. MARKed
objects are unlinked from their STM lists and relinked into
the backtrack structure along with an indication of where
they were in the STM list. STM can now be restored by
relinking the MARKed objects into their previous position
and deleting objects that were added to the front of the STM
lists. An example follows:
INPUT:
%%
A
B (B1:INT
B2:INT
B3:INT)
%%
%%
BACKTRACK
R1:
(B.B1 == B.B2)
(B.B1 != B.B2)
=>
MARK B B
;
R2:
(B.B1 != 7)
(^B FIRST
B.B1 == 7)
(B.B2 <= FIRST.B3)
=>
MARK FIRST
;
%%
OUTPUT:
struct back_track_stack {
int Add_A;
int mark_A;
int Add_B;
struct B_struct *mark_B;
int next_rule;
struct back_track_stack *next;
} *backtrack;
insert_backtrack(rule)
int rule;
{
struct back_track_stack *temp;
temp = (struct back_track_stack *)
- 44 -
myalloc(sizeof(struct back_track_stack));
temp->next_rule = rule;
temp->Add_A = 0;
temp->mark_A = 0;
temp->Add_B = 0;
temp->mark_B = NULL;
temp->next = backtrack;
backtrack = temp;
}
The struct back_track_stack, pointed to by 'backtrack',
is where the backtracking data is maintained. The struct
back_track_stack contains two variables for each object that
is defined. The variables are of form 'Add_NAME' and
'mark_NAME', where 'NAME' is the name of the object. The
variable of form 'Add_name' is always an integer, it indi-
cates how many objects of the named type were added to STM
by this rule. The variable of form 'mark_NAME' is an
integer for objects that do not contain elements (and there-
fore have no associated list) and a pointer for objects that
do contain elements. The procedure 'insert_backtrack' allo-
cates a structure, places it at the head of the list pointed
to by 'backtrack' and initializes it's variables.
loop()
{
int i;
Start:
R1:
if((token[B] >= 2) &&
1){
B_temp[1] = B_list[0];
if((B_list[1] = search_B_struct
(1, B_list[1]->B2, 2, 0, 7, 0, 7)) == NULL){
restore();
goto R2;
}
B_temp[2] = B_list[0];
if((B_list[2] = search_B_struct
(2, B_list[1]->B2, 5, 0, 7, 0, 7)) == NULL){
restore();
goto R2;
}
insert_backtrack(1);
for(i = 0; i < 2; i++)
relink_B_struct(1);
restore();
goto Start;
}
R2:
if((token[B] >= 3) &&
1){
B_temp[1] = B_list[0];
- 45 -
if((B_list[1] = search_B_struct
(1, 7, 5, 0, 7, 0, 7)) == NULL){
restore();
goto End;
}
B_temp[2] = B_list[0];
if((B_list[2] = search_B_struct
(2, 7, 2, 0, 7, 0, 7)) == NULL){
restore();
goto End;
}
B_temp[3] = B_list[0];
if((B_list[3] = search_B_struct
(3, 0, 7, B_list[2]->B3, 6, 0, 7)) == NULL){
restore();
goto End;
}
insert_backtrack(2);
relink_B_struct(2);
restore();
goto Start;
}
End:
if(backtrack){
i = backtrack->next_rule;
backup();
switch(i){
case 1:
goto R2;
case 2:
goto End;
default:
goto End;
}
}
return(1);
}
Minor changes are made in the action part of each rule.
The action part begins with a call to 'insert_backtrack',
which places a structure on top of the backtrack stack. The
integer literal that is passed by this procedure indicates
which rule is firing. This information is used to determine
which rule to test next when this rule is undone.
Objects that are to be deleted are deleted with calls
to procedures of form 'relink_NAME_struct' where 'NAME' is
the name of the affected object. The relink procedures are
similar to the free procedures, except they link the object
to the backtrack stack instead of freeing it. The relink
procedures store a value in the object's variable MARK to
indicate the former position of the object in it's list.
Recall that the MARK variable is usually used to indicate
More information about the Mod.sources
mailing list