Path: seismo!harvard!talcott!panda!sources-request From: sources-request@panda.UUCP Newsgroups: mod.sources Subject: TRC - expert system building tool (part 4 of 8) Message-ID: <1388@panda.UUCP> Date: 8 Feb 86 12:23:49 GMT Sender: jpn@panda.UUCP Lines: 1521 Approved: jpn@panda.UUCP 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