Category : Forth Source Code
Archive   : MEKS.ZIP
Filename : MEKS.DOC
Preliminary working documentation for version 3.2 as at 29/8/91
Uses four state logic (true,false,unknown and unavailable). Handles Boolean and fuzzy facts, handles 13 bit numeric values. Has special initialization pass to initialize values. Uses a multipass forward inference engine to fire as many rules as possible from known and deducible facts and values.
Backtracks to determine specific questions about facts it needs to know until all conclusions that can be established on the data available directly or via questions have been fired. Can focus using sub-sets of rules. Handles multiple sets of facts, corresponding to the situation at different times in the past. Seeks answers to questions that it cannot answer internally from fellow MEXSs via coms.
Strings.
All facts and variables are referred to by name, using the same conditions as normal Forth words, in particular no embedded blanks. Names of Forth words may be reused if desired as names of fact or variables without any fear of the two becoming confused. All strings are stored in string space (not in the normal vocabularies) as normal counted strings. The address of the count byte of this stored string is used to identify the string and is referred to as the Fact Identifier or FI in this software. The space allocated to string storage (called string space) is defined as constant at the start of the software and may be adjusted as required. This is true for the other spaces which are used to hold rules (rule space) facts and variables (fact space) and initialization instructions (init space). No check is made to detect overflow of any of these spaces.
Rule structure.
Basic structure: token, fact address, token, fact address, etc. Token bits have meanings. If any of bits 8 to 10 all set the token is a terminal clause, if they are all clear the token is a conditional clause.
b0 NOTb1 1=CONDITIONAL CLAUSE b2 1=CONSEQUENTIAL CLAUSEb3 0 1 0 1b4 IF = THEN THEN-RUNb5 AND > CONLUDEb6 OR < ELSE-RUNb7 UNLESS <> UNKNOWN-RUN
b8 +b9 -b10 | WHICH |b11 | FACT |b12 | SET |b13 THIS CLAUSE HAS BEEN RUN FLAG (^)b14 ALREADY CONSIDERED IN BACKTRACK PROCESS FLAG ($)b15 EVALUATED BUT NO CONCLUSION REACHED FLAG (*)
IF-NOT would thus have a token value of 0000000000010011=13hex. THEN-RUN would have a token value of 0000000000010100=24hex, which after unsuccessful evaluation would become 8024hex. P2 variable > would have the token 0000100000101010=82Chex.
Facts structure.
All facts occupy 4 bytes, the first is the status/type, the second the value of trueness or falseness, the third and fourth the fact-identifier [the adr of this phrase in string space]. The first and second bytes are collectively referred to as SV in this software.
<- FACTS -> <- VALUES ->
b15 0 = fact 1 = value
b14 <- report any change in status ->
b13 <- fact or value unavailable if set ->
b12 fact unknown if set | |
b11 fact true if set | 13 |
b10 fact false if set | |
b9 fact type boolean if set | |
b8 fact type fuzzy if set | bit |
b7 | 8 bit | | |
b6 | truth | | |
b5 | confidence | | unsigned |
b4 | value | | |
b3 | (fuzzy | | |
b2 | facts | | number |
b1 | only) | | |
b0
Initialization
A list of facts or values and their initialization routines is run. The routines must either return a full status value word, except for the `to be reported' bit (bit14) or value unavailable (A000). No check is made to see if the returned value is meaningful.
A value initialization routine must return 1rxx hex where xx is the 14 bit value and r is set if this value is to be reported or 1100 if unavailable. A fact initialization routine will return 28FF if Boolean and true 24FF if Boolean and false, 18xx if fuzzy and xx true, 14xx if fuzzy and xx false, 1100 if unavailable.
And operation definition
Performs a logical and between two S-V on the stack.Anything anded with unavailable gives unavailable answer.Anything but unavailable anded with unknown gives unknown.True false flags follows normal rules.Value is minimum of two inputs if both inputs true.Value is maximum of two inputs if both input false.Result is the false input if one input is true and one false.
OR operation definition.
Perform a logical OR between two S-V on stack.Anything ORed with unavailable gives itself as the answer.Anything ORed with unknown gives itself as the answer.True/false flag follows normal rules.Value is higher of two input values if both inputs true.Value is lower of two input values if both inputs false.Result is the true input if one input is true and one false.
UNLESS operation definition.
Perform a logical unless between two SV on stack.The top SV on the stack is check and then discarded. If it is true (only) the SV that is now on the top of the stack is forced to be false. This provides an inhibitory mechanism.
Specifying Rules
A rule set consists of both initialization instructions and the rules themselves. These may be in any order and intermixed if desired. A minimum rule consists of one IF conditional clause followed by one consequential clause. Any number of additional clauses may be added as long as the structure shown below is observed.
A. The rules are specified by lines of ASCII with the following structure. Rules must be preceded by the word RULES and terminated by the word END
| THEN fact name TRUE or |
TRUE | AND TRUE | | CONCLUDE " FALSE |
IF ForV or | OR ForV or | | THEN-RUN Forth word |
FALSE | UNLESS FALSE | | ELSE-RUN " |
| UNKNOWN-RUN " |
------------------------------------------------------- --------------------------------------------------------------------
Repeat as often as required Repeat as often as required
where ForV is either the name of a fact or the names of two values joined by one of the four relational operators =, >, <, or <>, or the sum or difference of two values followed by a relational operator and then another value.
A rule will consist of one IF clause followed by an indefinite number of AND, OR and UNLESS clauses. These are the conditional clauses. They are followed by at least one consequent clause. These clauses have two forms. One form sets the state of a fact or conclusion. The other conditionally runs any Forth word.
Any fact or value name may be optionally preceded by Pn where n is one of the numbers 0 through 7 and refers to which fact set to use. If no Pn precedes the fact or variable name, then P0 is assumed.
ForV is
{Pn} fact name
or
{Pn} value name = or > or < or <> {Pn} value name
or
{Pn} value name + or - {Pn} value name = or > or < or <> {Pn} value name
where { } indicates optional.
B. Initialization is specified by lines of ASCII with the following structure. Only facts or values in fact set P0 can be initialized.
INIT fact or value name Forth word to do initialization.
Specifying Facts and Values
Facts are specified by lines of ASCII with the following structure. Facts must be preceded by the word FACTS and terminated by the word END. Only facts or values in fact set P0 can be directly specified.
Fact type Name State Value, a number from 0 - 255
BOOLEAN fact name TRUE or FALSE not allowed
FUZZY fact name TRUE or FALSE always required
VALUE value name always required
REPORT fact name
Printing information.
To print a rule set, type .rules preceded if required by Rn where n is the number of the rule set required. The full rule set, rules and initialized will be printed.
To print a fact set, type .FACTs preceded if required by Fn where n is the number of the fact set required.
Module organisation.
Module one is always required. It provides for inputting basic rules, facts and initialization, in each case referring to the current set only. It performs initialization and then a forward evaluation of the rules only. It contains a number of deferred words, most of which are links to later modules. All such words have names that start with < and end with >. As long as no other module is to be loaded, all these words may be deleted and any occurrence if the source replaced by the default word as listed on the first page. If the default action is noop, all reference to the word may be omitted. The main word THINK is the one most affected, although deferred words are referred to in other words too. Once module one is loaded any combination of the remaining modules may be loaded, almost in any order. The exception to this is module five which has a small section at the end dealing with reporting facts, which must be loaded after module three (if module three is not to be loaded, this facility is not meaningful and the code - which is clearly marked at the very end of the file - commented out).
Module two is only required if one wished to inspect the current state of rules, facts or initialization lists. It contains code to support all the options added in modules 3, 4 and 5 but does not require these modules to be loaded.
Module three adds multiple sets of facts, mainly so that a history of the situation can be kept. new words are added to the rule structure so that rules can refer to previous states of facts or values. Once this module is loaded, module two will allow printing of any set. Words are provided to keep a virgin set of facts as loaded off disk or by keyboard so that at any time the shell can return to the original start up condition. A word is provided to ripple the facts down automatically. The current set becomes the one previous set, the old one previous becomes the new two previous and so on.
Module four adds multiple rule sets so that concentration can be focussed. If, as a result of some perceived situation it is deemed that it is worth special study that would not normally be done, a new subsidiary set of rules can be run. This subsidiary set can have its own initialization and run just as the main set does. When the set has been as fully evaluated as possible, and the current fact set updated to contain the information thereby deduced, control is automatically returned to the main set of rules which are then carried on from where they were left off. The action of focussing and then de-focussing may be nested if desired and even made recursive (if such a thing was found to be of any practical use). Focussing is invoked by a THEN-RUN, ELSE-RUN or UNKNOWN-RUN followed by >Rn, where n is the number of the rule set that is to be run.
Module five adds backward evaluation of the rule set currently being considered and reportable facts. backward evaluation is an extra pass after all possible forward evaluation has been carried out and a pass made through all the rules without establishing any new information. The a CONCLUDE clause that has not been proved is sought in the current rule set. If one is found the rule leading to that conclusion clause is inspected in order to find a fact that is unknown and preventing the rule from being evaluated. Once one is found, the rule set is inspected to find a rule that could establish this sought after fact. If one is found, that rule is in turn inspected to see what is stopping it from being evaluated. This process continues until a fact is found which could not be established by any of the currently unevaluated rules. A message is then sent to other MEKS seeking information on the state of this fact. The request may be repeated if needed until either a answer with the required information is received, or time is up and the fact is known to be unavailable. In either event the fact list is updated and an attempt made at forward evaluation, followed by backward searching as described above. After all facts have been asked for and are either known or unavailable a message may be sent consisting of any facts tat have been specified as reportable. The form of this message is REPORT fact-name fact-state, REPORT fact-name fact-state ... Periodically a watch is kept on the input buffer for any requests of us for information. If one is received, and the information sought is known, a reply is sent. The actually time keeping and message sending and receiving routines are machine dependent and are in a clearly identified block in this module. Version 3.21 assumes message structures that suit a separate communications package that runs in a time sliced multi tasking regime and does significant message packaging of its own. This is derived from the STAP/AGED1 project. The modified version that integrates all message sending and receiving into a co-operative multi-task loop and uses the input buffer IBUFF as the TIB has not yet been ported to F-PC.
ÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜ R w c s
o ¿
k Ó g Ø b à ^ æ Y ·
U Ç
Q o M u H d d e d d d d d e d e d u K w ] s > o x k f Ú b Ë ^ Z _ V a R ~ N ! J d e d d d d d d d d e d ! # w : s V o W k \ f b ^ Y U U 3 Q ~ N ! J d e d d e e d e e d e d
Ô ÿÿÖ ÿÿ ÿÿ ÿÿ ÿÿG ÿÿÜ ÿÿÞ ÿÿè x ê ÿÿ <
ê P ÿÿR ÿÿc x e ÿÿ8 ÿÿ: ÿÿæ o ´ o ¶ ÿÿ <