TRC - expert system building tool (part 5 of 8)
sources-request at panda.UUCP
sources-request at panda.UUCP
Sun Feb 9 14:32:19 AEST 1986
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);
}
More information about the Mod.sources
mailing list