Usenet 1994 January

home *** CD-ROM | disk | FTP | other *** search

/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume3 / trc / part5 < prev next >

Wrap

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

Newsgroups: mod.sources Subject: TRC - expert system building tool (part 5 of 8) Approved: jpn@panda.UUCP Mod.sources: Volume 3, Issue 113 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.3.doc. Dan Kary ihnp4!dicomed!ndsuvax!nckary -------------- cut here --------------- - 46 - that an object is 'in-use'. The MARK variable is not needed for it's original purpose when it is in the backtrack stack. OUTPUT: relink_A_struct(start) int start; { backtrack->mark_A++; token[A]--; } relink_B_struct(start) int start; { int i, j; struct B_struct *temp; for(i = start; i < B_max; i++) if(B_list[i]){ temp = B_list[0]; j = 0; while(temp != B_list[i]){ temp = temp->next; j++; } if(B_list[i]->prev == NULL) B_list[0] = B_list[i]->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; B_list[i]->MARK = j; B_list[i]->next = backtrack->mark_B; backtrack->mark_B = B_list[i]; B_list[i] = NULL; i = B_max; token[B]--; } } The backtracking action itself is initiated after the label 'End:' in the procedure 'loop'. If there is something on the backtrack stack, the index of the last rule that fired is copied out and the procedure 'backup', which undoes the actions of the last rule that fired, is called. Execu- tion continues with the rule that follows the last rule that fired. The procedure 'backup' first restores objects that were MARKed by the last rule and then removes objects that were ADDed. The MARKed objects are restored to their origi- nal positions in the list. OUTPUT: backup() - 47 - { int i; struct back_track_stack *temp; struct B_struct *B_temp, *B_temp2; if(backtrack == NULL) return; token[A] += backtrack->mark_A; token[A] -= backtrack->Add_A; while(backtrack->mark_B){ B_temp2 = backtrack->mark_B; backtrack->mark_B = backtrack->mark_B->next; B_temp2->prev = NULL; B_temp2->next = NULL; B_temp = B_list[0]; if(B_temp){ for(i = 0; i < B_temp2->MARK; i++) if(B_temp->next) B_temp = B_temp->next; else i = B_temp2->MARK + 1; } else i = -1; if(i == B_temp2->MARK){ B_temp2->next = B_temp; B_temp2->prev = B_temp->prev; if(B_temp->prev) B_temp->prev->next = B_temp2; else B_list[0] = B_temp2; B_temp->prev = B_temp2; } else{ if(B_temp){ B_temp->next = B_temp2; B_temp2->prev = B_temp; B_temp2->next = NULL; } else B_list[0] = B_temp2; } B_temp2->MARK = 0; token[B]++; } for(i = 0; i < backtrack->Add_B; i++){ B_list[1] = B_list[0]; free_B_struct(1); } temp = backtrack; backtrack = backtrack->next; free(temp); } The procedures generated by the BACKTRACKing option can - 48 - be called from embedded c-code to implement user controlled backtracking. A rule may undo itself with the following two statements: backup(); goto NEXT_RULE; The label 'NEXT_RULE' is replaced with the label of the rule that follows the current rule (this is done by the knowledge engineer, not TRC). To undo the current rule and the rule that fired previous to the current rule, use the following two statements: backup(); goto End; The label 'End' always refers to the point that follows the action part of the last rule. Appendix C contains a small expert system that implements backtracking with calls in embedded c-code. _1_3._5. _Z_E_R_O The ZERO option generates code that will free all dynamic structures allocated by TRC generated code. It is useful in systems where the loop procedure is entered more than once. It may be necessary to clean up the remains of a previous execution before beginning a new one. A single procedure, 'zero()', is written on the file 'zero.c'. The zero procedure will free all the elements and all the objects in STM and zero the arrays that hold the counts of objects in each list. If BACKTRACKing is enabled, zero will free all the objects and elements in the backtrack stack. If the TRACE option is enabled, zero will free all the entries in the trace list. If the PROFILE option is enabled, zero will set the value of all the integer array elements to zero. The actual code produced for the zero procedure is uninteresting and is not reproduced here. _1_3._6. _S_A_V_E The SAVE option writes a set of procedures on the file 'save.c' that simplify building expert systems capable of checkpointing their own execution. Procedures are generated for saving and reloading each type of dynamic structure that might be generated. In each case the procedures are passed a file pointer that points to an open file. The code pro- duced by the save procedures is uninteresting so only the names are listed here. The purpose of each procedure should be obvious from it's name: save_stm(fp) load_stm(fp) - 49 - save_backtrack(fp) load_backtrack(fp) save_profile(fp) load_profile(fp) save_trace(fp) load_trace(fp) Appendix C presents a small expert system that uses the SAVE option to generate code for checkpointing the execution of the system. The example includes an automatic restart capability. - 50 - APPENDIX A: TRC GRAMMAR The grammar for TRC which is presented throughout PART ONE of this document is presented in it's entirety here. identifier ::= letter { underscore | letter | digit} letter ::= upper-case-letter | lower-case-letter f-p ::= [ minus ] digits dot digits integer-literal ::= [ minus ] digits digits ::= digit { digit } string-literal ::= quote { [ character ] } quote comment ::= slash asterisk { [ character ] } asterisk slash c_code ::= left-bracket { [character] | [c_code] } right-bracket definition ::= identifier definition ::= identifier left-paren item-list right-paren item-list ::= { [ item ] } item ::= identifier colon type type ::= INT | FLOAT | STRING | POINTER stm ::= { [ entry ] } entry ::= [ integer-literal ] identifier entry ::= [ integer-literal ] identifier left-paren { [ init-item ] } right-paren init-item ::= identifier arrow value value ::= integer-literal value ::= floating-point-literal value ::= string-literal ltm ::= { [option] } { rule } option ::= ZERO | PROFILE | BACKTRACK | DUMP | RECURS | NORECURS | SAVE | TRACE | PREFIX identifier rule ::= label situation arrow action semicolon label ::= identifier colon | colon situation ::= { [ s-option ] } { [ match ] } s-option ::= EMPTY identifier identifier s-option ::= RECURS | NORECURS match ::= [ integer-literal ] identifier match ::= NOT identifier match ::= [ integer-literal ] left-paren name match-list right-paren match ::= c-code name ::= hat identifier identifier match-list ::= { match-item } match-item ::= identifier dot identifier relop literal match-item ::= identifier dot identifier relop identifier dot identifier relop ::= equality | not-equal | less-than relop ::= greater-than | greater-than-or-equal relop ::= less-than-or-equal action ::= statements c-code statements ::= { [statement] } statement ::= MARK mark-list statement ::= ADD add-list statement ::= OPTIMIZE identifier - 51 - mark-list ::= { [ mark-item ] } mark-item ::= [ integer-literal ] identifier add-list ::= { [ entry ] } - 52 - APPENDIX B: ERROR MESSAGES Error messages are listed and explained here in alpha- betical order. All messages that refer to the input file begin with the line number of the input file where the error was noticed. This line number is not necessarily the line where the error occurred, the actual error could be on an earlier line. The notations %s and %o mean that a string or an octal number, respectively, from the input file is included in the error message. %s is not an element of %s The named object does not include the named ele- ment. cannot translate %s in rule %s A c-code in rule %s contains an identifier %s that is preceded by a dollar character. The identifier is not known to TRC. This will occur if a dollar character occurs at some random point in the c- code. This error will also occur if an identifier is misspelled. can't have %s and NOT %s in the same rule NOT %s is a test that is true only when %s is an empty list. Obviously a list may not contain an object and be empty so the statement is meaning- less to TRC. can't MARK an EMPTY object An EMPTY object is an object that exists outside of STM. The scope of an EMPTY object is the rule in which it is declared. Since EMPTY objects are not in STM, attempting to MARK one is meaningless. can't mark more %s's than are found Unless STM is searched for an object and the object is found it is not possible to remove that object from STM. STM is searched only in the situation part, anything to be deleted in the action part must have been found in the situation part. - 53 - count on free variables undefined The purpose of a free variable is to assign a name to a specific object. Placing a count in front of a free variable definition is meaningless because the name can be assigned to only one object. degenerate case please rewrite A match in a rule compares an element to itself. The result of comparing an element to itself is known without performing any test. TRC refuses to generate the extra code that this useless test requires. duplicate declaration -> %s Object names must be unique, %s is the name of the object that is mentioned twice in the definition section. duplicate name in definition -> %s Each element in an object definition must have a unique name. free variable already defined -> %s The scope of a free variable is a single rule. Free variable names may be reused in every rule, but only once per rule. label repeats object declaration -> %s Rule labels and object names must be distinct from one another to prevent name conflicts in the out- put source code. negative count is undefined Be serious. How can a list contain less than zero items? newline embedded in string The scanner attempts to prevent errors caused by forgetting to terminate a string. For that reason - 54 - literal newlines are not permitted in strings. A newline and other control characters can be embed- ded in a string using the normal UNIX and C escapes. no code produced due to errors in source TRC will generate code only when there are no errors in the source. object field must be a string object field must be double object field must be integer TRC enforces strong type checking for the three data types, all assignments and relational tests must involve elements of the same type. objects in a complex test must match Here is an example of this type of error: (A.A1 == 2 B.B1 == 3) Because a single set of parens bracket this test it is presumed to be a test for a single object. A single object can not be in both list A (A.A1) and list B (B.B1). Either there is a typo in one of object names or some parens are missing. OUT OF MEMORY TRC IS EXITING This message is not generated by TRC, rather it is generated by the code that TRC produces. It will occur when the TRC generated inference engine attempts to dynamically allocate a data object. If the allocate fails, the TRC generated code prints this message and exits. redefined label -> %s Every rule must have a distinct label. semantic error: use a free variable This message suggests a solution to the perceived - 55 - problem. It is printed when the right hand side of a relational test mentions an object name that is different from the object name mentioned on the right hand side. This type of test can be accom- plished, but the item on the right hand side must be found first and must have a free variable name assigned to it. syntax error syntax error in ADD statement syntax error in MARK statement syntax error in OPTIMIZE statement syntax error in definitions syntax error in header syntax error in previous rule syntax error in short term memory syntax error in trailer A syntax error is generated by the parser when it can not reduce the input tokens with any of it's rules. The current input token will be discarded and the parser will attempt to reduce the new input. At least three input tokens must be parsed before the parser will assume it is in sync. Once the parser finds an error it will throw tokens out until it can sync. This is the reason why semi- colons are used as a rule terminator, they provide an absolute point where the parser can sync no matter how badly the input is botched. This behavior is common to YACC generated parsers. All syntax error messages indicate the line that was being scanned when the error was noticed and most inform the user of what section of the code was being parsed. types of element (%s) and value (%s) do not match Strong type checking is enforced by TRC. Literals must be of the same type as the element they are being assigned to. Floating point literals MUST contain a decimal point. There can be no cross assignment between integer and floating point ele- ments. types of %s.%s and %s.%s do not match Strong type checking is enforced by TRC. Only elements of identical types may be compared. unable to attach %s to the standard input - 56 - The scanner actually reads the standard input. The file named on the command line could not be opened for reading and attached to the standard input. unable to open %s Open failed on one of the output files. TRC aborts. unable to recover from earlier errors The parser completely wigged out, this usually happens when the input terminates before the parser can resync. undefined element -> %s.%s The object %s does not have an element %s. undefined flag (%c) A command line argument included a compiler flag that is not defined. Use 'man trc' to get a manual page. undefined free variable -> %s A reference was made to a free variable on the right hand side of a relational test. That free variable was not attached to an object in the current rule. Remember that the scope of a free variable is a single rule. undefined object -> %s The name %s was used as an object name but not defined as such in the definition section. undefined object field -> %s.%s The object %s was defined, but it did not contain an element %s. unexpected '!' unexpected '%' - 57 - unexpected '=' unexpected or undefined character: %o These messages are generated by the scanner. These characters, when not embedded in a comment, string or code section, are meaningful only as part of a compound symbol (e.g !=, ==, %%). A single character is not returned to the parser since it will only propagate errors. unterminated C code unterminated comment These elements of the input are handled completely by the scanner. These messages are printed if the end of the input file is reached before the ter- minating character is found. Each of these mes- sages indicate the line of the input where scan- ning began. usage: trc [options] filename Command line error. Use 'man trc' to get a manual page. zero count is undefined Nice try. If you really want to search STM for zero occurrences of something use the NOT state- ment described in Section 6.3.1 of this document. - 58 - APPENDIX C: STYLE NOTES TRC was designed to produce fast code, but it is not the least bit difficult to produce very slow code with TRC. The intent of this section is to suggest some things that can be done that will lead to fast code and to suggest some ways to avoid creating slow code. The central issue is reducing the amount of time spent searching STM. In the battle against long search times, TRC's first line of defense is the definition section. Think of STM as a data base. When a data base is designed two issues are central: first the data base must be capable of representing all the facts that are to be stored and retrieved and second the data base should be arranged in a manner that will facilitate searching the data base. In a relational data base, the data base manager will designate primary keys based, in part, on the way that users are likely to specify searches. Think of STM as a data base, the rules in LTM are the users that are searching the data base, design the data base (STM) for searching. Suppose an expert system for routing cargo on commer- cial air carriers is being built. The objects that this expert system will deal with include airplanes and cargo. It is certainly possible to define a single TRC object whose elements can describe either an airplane or a piece of cargo. When a rule searches for an airplane in this system, it has to wade thru cargo and airplanes to find the airplane it needs. Why not define two different objects, one that describes airplanes and one that describes cargo. Then a rule that is searching for an airplane can search only the airplane list without having to wade thru the cargo too. Carried to an extreme, this suggestion implies a dif- ferent object definition for every combination of attributes that can exist in STM. This extreme will often not be feas- able. There is a trade off to be made; by defining more objects, the length of each list should be reduced which should reduce execution time. The penalty is that for each object there is a code overhead for the procedures that manipulate those objects. Code size is being traded for execution speed. For object definitions that do not include any elements there is a very low code overhead. Object definitions that do not include elements are useful when the objects do not differ from one another and only a count of how many there are is needed. Since objects of this type do not differ, no list is maintained. If STM can be represented entirely with objects that contain no elements, all searching will be eliminated. This situation usually leads to the fastest executing systems. - 59 - The situation part of a rule is the second line of defense against slow expert systems. On each pass thru LTM, only one rule is selected for firing. This implies that most rules fail most of the time and that is is somewhat unusual for a rule to actually fire. Since rules generally fail far more often than they fire, wouldn't it be reason- able to design rules to be good at failing, i.e. fail quickly? The preconditions automatically placed on every rule by TRC are an initial attempt to cause a rule to fail without doing any searching. If a rule searches for an object in list A, one in list B and one in list C, the order that the list are searched may not be significant. The order will not be significan unless one of the searches refers to something that was pre- viously found. If the order is not significant, why not first search for the object that is least likely to exist? If the objects are equally likely, why not first search the list that is likely to be shortest? The search is carried out in the order that the objects are listed in the situa- tion part. Remember that rules usually fail and design your rules to fail quickly wherever possible. The optimizer is the third line of defense, use it. - 60 - A SAMPLE SYSTEM This sample expert system demonstrates some of the features of the TRC language. The expert system finds a path from one node to another node in a 'dungeon'. Some of the nodes are marked as 'dangerous', and no path may go through that node. The main procedure prints a map of the 'dungeon' and asks the user for start and end nodes. It then initializes STM and calls loop. On return from loop it prints out the path (if one was found) and the execution time and profile. The path is not necessarily the shortest path, only the first path found. Cycles are not permitted. This sample system uses backtracking that is initiated by embedded c-code. It also uses the SAVE option to sim- plify the checkpoint and reloading procedures. The pro- cedure 'checkpoint' saves the state of all dynamic struc- tures and 're_do' restores from a previous checkpoint. If the system is started with no command line arguments, it simply queries the user for start and end points. If it is started one or more command line arguments, it will restart from a previously saved snapshot. Since it is possible for a system to crash while the checkpoint files are being written, this system writes alternately on two sets of files. A flag file indicates which set of files is complete. INPUT: %% END (E1:STRING) NODE (N1:STRING N2:STRING N3:STRING) PATH (P1:STRING) START (S1:STRING) %% NODE ( N1 => "ANEMONIE" N2 => "DANGER" N3 => "QUAGGA") NODE ( N1 => "ANEMONIE" N2 => "DANGER" N3 => "YENTI") NODE ( N1 => "ANEMONIE" N2 => "SAFE" N3 => "MEADOW") NODE ( N1 => "ANEMONIE" N2 => "SAFE" N3 => "KESTREL") NODE ( N1 => "BANDIT" N2 => "SAFE" N3 => "JABBERWOCK") NODE ( N1 => "BANDIT" N2 => "SAFE" N3 => "PEGASUS") NODE ( N1 => "BANDIT" N2 => "SAFE" N3 => "LAPIS LASULI") NODE ( N1 => "CAVERN" N2 => "SAFE" N3 => "ICE ROOM") NODE ( N1 => "CAVERN" N2 => "SAFE" N3 => "TREASURE") NODE ( N1 => "CAVERN" N2 => "DANGER" N3 => "HOBGOBLIN") NODE ( N1 => "DUBLOON" N2 => "SAFE" N3 => "ICE ROOM") NODE ( N1 => "DUBLOON" N2 => "DANGER" N3 => "HOBGOBLIN") NODE ( N1 => "DUBLOON" N2 => "SAFE" N3 => "SPRING") NODE ( N1 => "ELVES" N2 => "SAFE" N3 => "NYMPH") NODE ( N1 => "ELVES" N2 => "SAFE" N3 => "URCHIN") NODE ( N1 => "FOUNTAIN" N2 => "SAFE" N3 => "RUBY") - 61 - NODE ( N1 => "FOUNTAIN" N2 => "SAFE" N3 => "NYMPH") NODE ( N1 => "FOUNTAIN" N2 => "DANGER" N3 => "XEROC") NODE ( N1 => "GROTTO" N2 => "DANGER" N3 => "WRAITH") NODE ( N1 => "GROTTO" N2 => "SAFE" N3 => "OGRE") NODE ( N1 => "GROTTO" N2 => "SAFE" N3 => "RUBY") NODE ( N1 => "HOBGOBLIN" N2 => "SAFE" N3 => "TREASURE") NODE ( N1 => "HOBGOBLIN" N2 => "SAFE" N3 => "CAVERN") NODE ( N1 => "HOBGOBLIN" N2 => "SAFE" N3 => "ICE ROOM") NODE ( N1 => "HOBGOBLIN" N2 => "SAFE" N3 => "DUBLOON") NODE ( N1 => "HOBGOBLIN" N2 => "SAFE" N3 => "MEADOW") NODE ( N1 => "ICE ROOM" N2 => "SAFE" N3 => "CAVERN") NODE ( N1 => "ICE ROOM" N2 => "DANGER" N3 => "HOBGOBLIN") NODE ( N1 => "ICE ROOM" N2 => "SAFE" N3 => "DUBLOON") NODE ( N1 => "JABBERWOCK" N2 => "SAFE" N3 => "MEADOW") NODE ( N1 => "JABBERWOCK" N2 => "SAFE" N3 => "VERMIN") NODE ( N1 => "JABBERWOCK" N2 => "SAFE" N3 => "LAPIS LASULI") NODE ( N1 => "JABBERWOCK" N2 => "DANGER" N3 => "BANDIT") NODE ( N1 => "JABBERWOCK" N2 => "SAFE" N3 => "PEGASUS") NODE ( N1 => "JABBERWOCK" N2 => "DANGER" N3 => "ZOMBIE") NODE ( N1 => "KESTREL" N2 => "DANGER" N3 => "YENTI") NODE ( N1 => "KESTREL" N2 => "SAFE" N3 => "ANEMONIE") NODE ( N1 => "KESTREL" N2 => "DANGER" N3 => "QUAGGA") NODE ( N1 => "LAPIS LASULI" N2 => "SAFE" N3 => "VERMIN") NODE ( N1 => "LAPIS LASULI" N2 => "SAFE" N3 => "JABBERWOCK") NODE ( N1 => "LAPIS LASULI" N2 => "DANGER" N3 => "BANDIT") NODE ( N1 => "MEADOW" N2 => "DANGER" N3 => "HOBGOBLIN") NODE ( N1 => "MEADOW" N2 => "SAFE" N3 => "ANEMONIE") NODE ( N1 => "MEADOW" N2 => "SAFE" N3 => "JABBERWOCK") NODE ( N1 => "MEADOW" N2 => "SAFE" N3 => "NYMPH") NODE ( N1 => "MEADOW" N2 => "DANGER" N3 => "WRAITH") NODE ( N1 => "NYMPH" N2 => "SAFE" N3 => "MEADOW") NODE ( N1 => "NYMPH" N2 => "SAFE" N3 => "ELVES") NODE ( N1 => "NYMPH" N2 => "SAFE" N3 => "URCHIN") NODE ( N1 => "NYMPH" N2 => "DANGER" N3 => "XEROC") NODE ( N1 => "NYMPH" N2 => "SAFE" N3 => "FOUNTAIN") NODE ( N1 => "NYMPH" N2 => "SAFE" N3 => "RUBY") NODE ( N1 => "NYMPH" N2 => "SAFE" N3 => "URCHIN") NODE ( N1 => "OGRE" N2 => "SAFE" N3 => "SPRING") NODE ( N1 => "OGRE" N2 => "DANGER" N3 => "WRAITH") NODE ( N1 => "OGRE" N2 => "SAFE" N3 => "GROTTO") NODE ( N1 => "PEGASUS" N2 => "DANGER" N3 => "BANDIT") NODE ( N1 => "PEGASUS" N2 => "SAFE" N3 => "JABBERWOCK") NODE ( N1 => "PEGASUS" N2 => "DANGER" N3 => "ZOMBIE") NODE ( N1 => "QUAGGA" N2 => "SAFE" N3 => "KESTREL") NODE ( N1 => "QUAGGA" N2 => "SAFE" N3 => "ANEMONIE") NODE ( N1 => "QUAGGA" N2 => "SAFE" N3 => "VERMIN") NODE ( N1 => "RUBY" N2 => "SAFE" N3 => "GROTTO") NODE ( N1 => "RUBY" N2 => "SAFE" N3 => "NYMPH") NODE ( N1 => "RUBY" N2 => "SAFE" N3 => "FOUNTAIN") NODE ( N1 => "SPRING" N2 => "SAFE" N3 => "DUBLOON") NODE ( N1 => "SPRING" N2 => "DANGER" N3 => "WRAITH") NODE ( N1 => "SPRING" N2 => "SAFE" N3 => "OGRE") NODE ( N1 => "TREASURE" N2 => "SAFE" N3 => "CAVERN") NODE ( N1 => "TREASURE" N2 => "DANGER" N3 => "HOBGOBLIN") - 62 - NODE ( N1 => "TREASURE" N2 => "DANGER" N3 => "YENTI") NODE ( N1 => "URCHIN" N2 => "SAFE" N3 => "ELVES") NODE ( N1 => "URCHIN" N2 => "SAFE" N3 => "NYMPH") NODE ( N1 => "URCHIN" N2 => "DANGER" N3 => "XEROC") NODE ( N1 => "VERMIN" N2 => "DANGER" N3 => "QUAGGA") NODE ( N1 => "VERMIN" N2 => "SAFE" N3 => "LAPIS LASULI") NODE ( N1 => "VERMIN" N2 => "SAFE" N3 => "JABBERWOCK") NODE ( N1 => "WRAITH" N2 => "SAFE" N3 => "MEADOW") NODE ( N1 => "WRAITH" N2 => "SAFE" N3 => "SPRING") NODE ( N1 => "WRAITH" N2 => "SAFE" N3 => "OGRE") NODE ( N1 => "WRAITH" N2 => "SAFE" N3 => "GROTTO") NODE ( N1 => "XEROC" N2 => "SAFE" N3 => "URCHIN") NODE ( N1 => "XEROC" N2 => "SAFE" N3 => "NYMPH") NODE ( N1 => "XEROC" N2 => "SAFE" N3 => "FOUNTAIN") NODE ( N1 => "YENTI" N2 => "SAFE" N3 => "KESTREL") NODE ( N1 => "YENTI" N2 => "SAFE" N3 => "ANEMONIE") NODE ( N1 => "YENTI" N2 => "SAFE" N3 => "TREASURE") NODE ( N1 => "ZOMBIE" N2 => "SAFE" N3 => "JABBERWOCK") NODE ( N1 => "ZOMBIE" N2 => "SAFE" N3 => "PEGASUS") %% BACKTRACK DUMP TRACE PROFILE SAVE ZERO R1: /* See if we are at the end */ (^START HERE) (END.E1 == HERE.S1) => { printf("Found a path"); remove_checkpoint(); return; } ; R2: /* See if the next node that would be selected is already in the path. If it is, remove it from consideration */ (^START HERE) (^NODE NEXT NODE.N2 != "DANGER" NODE.N1 == HERE.S1) (PATH.P1 == NEXT.N3) => MARK NODE { } ; R3: /* Select the first non-dangerous node as the next node */ - 63 - (^START HERE) (^NODE NEXT NODE.N2 != "DANGER" NODE.N1 == HERE.S1) => MARK START NODE ADD START(S1 => NEXT.N3) PATH (P1 => NEXT.N3) { } ; R4: /* A dead end has been reached. Undo the last path taken and mark it as dangerous in R5 */ => { /* undo this rule */ backup(); /* check if there was a previous rule */ while(backtrack){ if(backtrack->next_rule == 5) backtrack = backtrack->next; else{ backup(); /* undo it */ goto R5; /* and mark it as dangerous */ } } /* no solution */ goto R6; } ; R5: /* Grab the first available path and call it dangerous */ (^START HERE) (^NODE NEXT NODE.N2 != "DANGER" NODE.N1 == HERE.S1) => MARK NODE ADD NODE (N1 => NEXT.N1 N2 => "DANGER" N3 => NEXT.N3) { checkpoint(); } ; R6: /* No solution */ => { printf("No Solution"); remove_checkpoint(); return; - 64 - } ; %% MAIN.C #include <ctype.h> #include <sys/file.h> #include <sys/time.h> #include "X_loop.h" extern char *rule_names[]; char *node_names[26] = { "ANEMONIE", "BANDIT", "CAVERN", "DUBLOON", "ELVES", "FOUNTAIN", "GROTTO", "HOBGOBLIN", "ICE ROOM", "JABBERWOCK", "KESTREL", "LAPIS LASULI", "MEADOW", "NYMPH", "OGRE", "PEGASUS", "QUAGGA", "RUBY", "SPRING", "TREASURE", "URCHIN", "VERMIN", "WRAITH", "XEROC", "YENTI", "ZOMBIE" }; int danger[26] = { 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1 }; extern int X_fire_profile[], X_test_profile[]; char *start, *xit; main(argc, argv) int argc; char *argv[]; { int i, fire, test; char c[512]; double d1, d2, d3; struct timeval tp, old_tp; struct timezone tzp; setbuf(stdout, NULL); if(argc > 1){ if(re_do()){ X_dump_PATH_struct(); test = fire = 0; for(i = 0; i < 17; i++) test += X_test_profile[i]; for(i = 0; i < 7; i++) fire += X_fire_profile[i]; X_zero(); printf("%d rules tested",test); printf("%d rules fired",fire); } printf("Continue [y or n] "); - 65 - scanf("%s",c); if(isupper(c[0])) c[0] = tolower(c[0]); if(c[0] == 'n') exit(0); } while(1){ start = xit = NULL; print_map(); while(start == NULL){ printf("Input start node "); scanf("%s",c); if(isupper(c[0])) c[0]=tolower(c[0]); if(islower(c[0])) start = node_names[c[0]-'a']; } while(xit == NULL){ printf("Input exit node "); scanf("%s",c); if(isupper(c[0])) c[0]=tolower(c[0]); if(islower(c[0])) xit = node_names[c[0]-'a']; } printf("initializing"); X_init(); X_backtrack = (struct X_back_track_stack *) malloc(sizeof(struct X_back_track_stack)); X_add_END_struct(xit); X_add_START_struct(start); X_add_PATH_struct(start); free(X_backtrack); X_backtrack = NULL; gettimeofday(&old_tp, &tzp); X_loop(); gettimeofday(&tp, &tzp); X_dump_PATH_struct(); d1 = old_tp.tv_sec; d2 = old_tp.tv_usec; d1 += d2/1000000; d2 = tp.tv_sec; d3 = tp.tv_usec; d2 += d3/1000000; d3 = d2 - d1; test = fire = 0; for(i = 0; i < 17; i++) test += X_test_profile[i]; for(i = 0; i < 7; i++) fire += X_fire_profile[i]; X_zero(); d1 = test; d2 = fire; printf("Elapsed time = %f seconds", d3); - 66 - printf("%d rules tested (%f rules/sec)",test, d1/d3); printf("%d rules fired (%f rules/sec)",fire, d2/d3); printf("Continue [y or n] "); scanf("%s",c); if(isupper(c[0])) c[0] = tolower(c[0]); if(c[0] == 'n') exit(0); } } print_map() { printf(" NODE NAMES (* DANGEROUS NODES) C - I "); printf(" ------------------------------- / \\ / \\ "); printf(" ANEMONIE NYMPH T - H - D "); printf(" BANDIT* OGRE / | \\ "); printf(" CAVERN PEGASUS Y | S "); printf(" DUBLOON QUAGGA* / | | | \\ "); printf(" ELVES RUBY K - A --- M --- W - O "); printf(" FOUNTAIN SPRING \\ / / \\ \\ / "); printf(" GROTTO TREASURE Q / \\ G "); printf(" HOBGOBLIN* URCHIN | / \\ | "); printf(" ICE ROOM VERMIN V / \\ R "); printf(" JABBERWOCK WRAITH* / \\ / \\ / \\ "); printf(" KESTREL XEROC* L - J - Z E - N - F "); printf(" LAPIS LASULI YENTI* \\ / \\ / \\ / \\ / "); printf(" MEADOW ZOMBIE* B - P U - X "); } int state = 0; char *lock = "lock.0"; char *stm = "stm.0"; char *back = "back.0"; char *pro = "pro.0"; char *trace = "trace.0"; checkpoint() /* save a snapshot of stm, back_track_stack, etc. */ { FILE *fp; lock[5] = '0' + state; stm[4] = '0' + state; back[5] = '0' + state; pro[4] = '0' + state; trace[6] = '0' + state; if(state) state = 0; else state = 1; unlink(lock); fp = fopen(stm, "w"); X_save_stm(fp); - 67 - fclose(fp); fp = fopen(back, "w"); X_save_backtrack(fp); fclose(fp); fp = fopen(pro, "w"); X_save_profile(fp); fclose(fp); fp = fopen(trace, "w"); X_save_trace(fp); fclose(fp); fp = fopen(lock, "w"); fprintf(fp,"good"); fclose(fp); } remove_checkpoint() /* remove all old snapshots */ { unlink(lock); unlink(stm); unlink(back); unlink(pro); unlink(trace); lock[5] = '0' + state; stm[4] = '0' + state; back[5] = '0' + state; pro[4] = '0' + state; trace[6] = '0' + state; unlink(lock); unlink(stm); unlink(back); unlink(pro); unlink(trace); } re_do() /* restore from a snapshot and continue execution */ { char c[512]; FILE *fp; if((fp = fopen(lock, "r")) != NULL) fscanf(fp,"%s", c); if(strncmp(c, "good", 4)){ if(fp) fclose(fp); if(state) state = 0; else state = 1; lock[5] = '0' + state; stm[4] = '0' + state; back[5] = '0' + state; pro[4] = '0' + state; - 68 - trace[6] = '0' + state; if((fp = fopen(lock, "r")) != NULL) fscanf(fp,"%s", c); if(strncmp(c, "good", 4)){ remove_checkpoint(); printf("No checkpoint files"); return(0); } } fclose(fp); fp = fopen(stm, "r"); X_load_stm(fp); fclose(fp); fp = fopen(back, "r"); X_load_backtrack(fp); fclose(fp); fp = fopen(pro, "r"); X_load_profile(fp); fclose(fp); fp = fopen(trace, "r"); X_load_trace(fp); fclose(fp); X_loop(); return(1); }