Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/unix/volume3/trc/part4

Text File | 1986-11-30 | 42.6 KB | 1,532 lines

Newsgroups: mod.sources
Subject: TRC - expert system building tool (part 4 of 8)
Approved: [e-mail]

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