       EVOLUTION OF A DATA-STRUCTURED EXPERT SYSTEM
                        IN FORTH

               ME 715  Assignments 7.1, 8.1
                      Brad Rodriguez
                     17 October 1989

   I. INTRODUCTION

      The objective of this project is to demonstrate how,
      by successive refinement, and by creative use of the
      programming structures afforded by Forth, the
      iterative expert system of Assignment 5.1 can be
      transformed into a backward chaining, data structured
      expert system.

      This transformation arises from a series of simple
      and "obvious" improvements to the explicit-code rules
      evaluator.  There are four steps in this "evolution."
      We will describe each step in turn.

  II. FIRST PHASE - BACKWARD CHAINING

      The first improvement is to "encapsulate" each rule
      in a separate routine.  A rule is a Forth word
      (function) which returns a logical value.

      We could define each rule function so that it would
      store the result in a logical variable.  But in
      Forth, this isn't needed.  The rule can leave its
      data on the stack, just as a fetch from a variable
      would.  The effect of
           RULE-FUNCTION
      which returns a truth value, is identical to that of
           RULE-VARIABLE @
      which fetches a truth value.

      This means that each rule will be re-evaluated
      whenever it is referenced.  (We'll fix this later.)
      It also means that the subroutine tree of the program
      will exactly represent the "logic tree" of the expert
      system.  (Figure 1.)  And, the process of calling
      successively "deeper" subroutines, and then returning
      to the calling functions, evaluates rules in exactly
      the sequence of the "backward chaining" control
      structure!

      In effect, any modern structured language, which uses
      a stack to hold return addresses, implicitly embodies
      the backward chaining algorithm.  This same approach
      would work in Pascal or C.  Also, if the language
      supports recursive functions -- like Forth --
      recursion can be used in the rules, as well.

      A limitation is imposed by Forth.  Forth does not
      allow forward references; in order to use a word
      inside another word, the former must already have
      been defined.  So, to define a rule in terms of other
      rules, those other rules must be defined first.  This
      means that the rules can not be given in arbitrary
      order, but instead must follow the hierarchy of the
      logic tree.  The lowest level (the inputs) must be
      defined first, and so on.  The upshot of this is that
      the rules must be defined in their optimal order!
      Failure to do so will cause a Forth compilation
      error.  (We'll fix this later, too.)

      What about inputs?  An input is a Forth word which
      returns a logical value, which is not derived from a
      rule.  The beauty of this approach is that, since a
      input word is a function, it can "actively" obtain
      its value -- perhaps by reading some input signal,
      perhaps by querying the operator.  For now, we will
      just make inputs Forth words which return a value
      pre-stored by the programmer.

      Listing 1 (screens 15-20) is this version of the
      expert system.

      Figure 2, the test run for a tiger, shows how the
      "instrumentation of the code" illustrates the action
      of the expert system.  As each rule or input word is
      exited, its result is printed on a line.  The
      indentation of the line indicates how "deeply" the
      subroutines have nested.  Note that this does not
      illustrate the path "down" the tree -- the backward
      chain -- but just the return path "up" the tree.
      (This is because of how the instrumenting words were
      written.)  By reading upward in the printout, you can
      see the "subrules" which were evaluated to determine
      any particular rule's result.

      This is in some ways a "trial and error" approach.
      The program "assumes" a conclusion -- CHEETAH -- and
      then begins testing rules to see if it is supported
      by the evidence.  If not, the program assumes the
      next conclusion -- TIGER -- until a valid conclusion
      is found.

      Observe that there is some "wasted effort" in the
      evaluation of certain rules.  For example, once we
      know that the animal EATS-MEAT, we know it is a
      CARNIVORE.  There's no need to evaluate the rule T1.
      We will fix this soon, by allowing the expert system
      to "prune" unnecessary branches of the tree.

      Observe also that some rules are evaluated multiple
      times.  For example, MAMMAL and CARNIVORE are
      evaluated in the process of deciding both CHEETAH and
      TIGER.  This represents an inefficiency, since we are
      repeatedly "recalculating" a value which only need be
      calculated once.  We will fix this, too, as we evolve
      a "better" expert system.

      Figure 3 is the test run for a zebra.  Observe that
      the trial conclusions CHEETAH, TIGER, and GIRAFFE are
      tried and discarded before the true conclusion ZEBRA
      is found.

      Figure 4 is a test run with data delibrately
      contrived to produce no valid conclusion.  All of the
      possible conclusions are tried, causing all of the
      branches of the logic tree to be exhaustively
      traversed.  When no conclusion succeeds, the program
      prints the message "Cannot identify."  (The iterative
      program of assignment 5.1 would loop forever here,
      unless some arbitrary limit was imposed.)

 III. SECOND PHASE - PRUNING

      One way to improve this expert system is to "prune"
      the logic tree, i.e., to not evaluate branches from a
      particular node if they cannot change the outcome.
      We will redefine the AND and OR operations to
      evaluate only enough terms as required to establish
      the result.

      Two "metarules" define this technique:
      a) once any term of an OR is "true," the result is
         true; no other terms can affect this.
      b) once any term of an AND is "false," the result is
         false; no other terms can affect this.

      Two new Forth words implement this:
      a)  |  is the "or" operator; if the first term is
         true, it stops evaluating and returns true.
      b)  &  is the "and" operator; if the first term is
         false, it stops evaluating and returns false.
      Note that these are both "infix" operators, i.e.,
      expressions are written
           term | term
           term & term
      This is in contrast to "normal" Forth where both
      terms appear first, followed by the operator.

      (Incidentally, similar operators already exist in the
      C language: the "logical" operators || and &&.  One
      of the powerful features of Forth is the ability to
      add new operators to the language.)

      Ideally, if a five-term OR has only one true term,
      we'd like to evaluate it first, and skip evaluating
      the four false terms.  This is difficult to decide
      automatically.  Instead, we evaluate the terms in the
      order they appear, left to right, and count on the
      programmer to put the "easy" terms first.

      Listing 2 (screens 21-26) is this version "B" of the
      expert system.  The new operators | and & are defined
      on screen 21.  Their operation depends on the fact
      that the Forth sequence R> DROP causes a premature
      exit of the calling routine.  Screens 23 and 24 show
      the syntax of these new operators.

      Figure 5 is the test run for a tiger.  Compare this
      with Figure 2 and note the "pruning" of the logic
      tree.  For example, once HAIR is known to be true,
      the intermediate conclusion MAMMAL is returned
      immediately -- GIVES-MILK is never tested.  Likewise,
      given EATS-MEAT as true, the T1 rule and all of its
      inputs need not be evaluated to know that the animal
      is a CARNIVORE.  The conclusion "tiger" requires the
      evaluation of only 14 rules & inputs, contrasted with
      24 in Figure 2.

      Figures 6 and 7 are the test runs for "zebra" and "no
      animal," respectively.  These show the savings of
      pruning even more vividly, when compared with the
      corresponding Figures 3 and 4.  For example, it takes
      the evaluation of only one input in Figure 7 to
      disqualify ZEBRA, as opposed to 12 rules and inputs
      in Figure 4.

  IV. THIRD PHASE - RULES TABLE

      The next improvement which can be made to the expert
      system is to relax the requirement that rules be
      given in optimal order.  We would like to be able to
      write the rules in any, arbitrary sequence.

      Recall that this limitation is imposed by Forth's
      inability to handle a forward reference, that is, a
      reference to a subroutine not yet defined.  We can
      borrow a concept from the C language to deal with
      this.  We shall require that all rules be declared,
      so that the compiler knows of their existence, before
      any use.  We shall then allow the definition of the
      rule to occur at a later time.

      Again, to declare a rule is simply to identify that a
      rule function of some name exists.  To define the
      rule is to specify how it is to be evaluated, i.e.,
      to supply the subroutine code for the rule function.

      We do this in Forth by letting every rule contain a
      pointer to its function, and then providing a way to
      create that function and change that pointer at a
      later time.  All of these pointers are kept in a
      single large table, the "rules table."

      Listing 3 (screens 27-32) is this version "C" of the
      expert system.  All of the Forth words to declare and
      define rules are on screen 28.  The important words
      are:

         RULES  allocates space for the rules table.  This
                is something like a DIMENSION statement in
                Fortran.  The statement "n RULES" is only
                made once; in this case, "50 RULES" are
                allocated on screen 29.

         RULE   declares the existence of a rule.  This
                merely reserves a slot in the rules table,
                and creates a Forth word to execute
                whatever function is stored in that slot.
                "RULE HAIR" creates such a "deferred" Forth
                function, called HAIR.

         DEFINE defines the function of a rule.  This
                invokes the Forth compiler to compile a
                subroutine, and then changes the pointer in
                the rules table for the named rule to point
                to the new subroutine.  An example is:
                     DEFINE UNGULATE   T2 | T3 ;

      Screens 29 through 31 contain the declarations and
      definitions of all the rules.  Note that both the
      declarations and the definitions can appear in
      arbitrary order, but all of the declarations (RULE)
      appear before any of the definitions (DEFINE.)

      Note also the new way of handling inputs.  Inputs
      still look like any other rule; i.e., they are
      "deferred" Forth functions found in the rules table.
      So, to set an input to a truth value, we no longer
      store the truth value in the input word -- we store a
      pointer to a Forth function which returns that truth
      value.  (Forth has two functions for this, TRUE and
      FALSE.)

      Figures 8, 9, and 10 are the three examples of
      "tiger," "zebra," and "no animal."  Observe that the
      order of evaluating rules is identical to that of
      Figures 5, 6, and 7.  This new version of the system
      allows rules to be defined in any order, but it does
      not change the "internal" definition of each rule --
      and hence the order in which the rule subroutines are
      executed remains the same.  Rules are still evaluated
      in "optimal" order.

   V. FOURTH PHASE - RULES MEMORY

      There is still room for improvement in the expert
      system program.  Observe in Figure 10 that the
      function for MAMMAL is evaluated three times.  We
      would prefer to evaluate each rule function only
      once, and "remember" the result for subsequent uses.

      In essence, we require each rule to have a "memory"
      of whether it is "true," "false," or "not yet
      evaluated."  When the rule function is invoked, we
      should attempt to supply the result from this memory.
      Only if the rule is "not yet evaluated" should the
      defined rule function be executed, and then the
      result should be saved for future reference.

      This is implemented in screen 34 of Listing 4
      (screens 33-35).  We take advantage of the fact that
      all RULEs share a common piece of code -- the DOES>
      clause of the word RULE.  (RULE is an example of a
      Forth "defining word," which creates a "family" of
      words that execute a common subroutine with different
      data.  The DOES> clause is the common routine.)  The
      truth value is stored in the rules table along with
      the function pointer; if this value is "unknown," the
      function will be evaluated and its result stored.
      Compare this with the DOES> clause in screen 28 of
      Listing 3, which always evaluates the rule function
      and doesn't store the result.

      The rest of this version "D" program is unchanged
      from version "C."

      Figures 11, 12, and 13 are the test cases of "tiger,"
      "zebra," and "no animal" for this program.  The
      "instrumenting words" which produce the run-time
      listing have been changed to only print a line when a
      rule's function is evaluated; that is, a rule is not
      printed out if it is merely fetched from memory.  (If
      we printed out every reference to a rule, we would
      merely print the order of evaluation -- and we would
      find it to be identical to that of versions B and C.)

      Compare Figure 12, for a zebra, with Figure 9.  The
      rule functions HAIR and MAMMAL, which were evaluated
      three times, are now evaluated only once.  The logic
      values are still used three times, but the second and
      third use are obtained from the "memory" of the first
      evaluation.  The run-time listing of Figure 12 is
      thus shorter than that of Figure 9; this does not
      mean that the logic tree has been condensed, but that
      fewer logical calculations are required.  Since a
      memory fetch is "cheaper" than a calculation, this
      represents a savings.

      Observe also that each input is "evaluated," and
      appears in the printout, once.  This is because each
      input is defined as a function (the Forth words TRUE
      or FALSE), and when the program is started, the input
      functions have not yet been evaluated.  The practical
      impact of this is that each input function could be a
      Forth word to ask the operator a question.  With the
      combination of pruning and "rule memory," only the
      questions necessary to determine the results will be
      asked, and each question will be asked only once.

  VI. CONCLUSION - THE DATA STRUCTURED SYSTEM

      These four enhancements of the simple expert system
      have led us to what is essentially a data structured
      expert system.  This is perhaps more evident in
      Figure 14, which shows the data structures that have
      evolved.

      At the left side of the diagram are the Forth words
      which are the named rules of the system.  These are
      created by RULE.  Each rule contains its name (an
      ASCII string), and a pointer into the rules table.

      At the top of the diagram is the rules table.  This
      is created by "n RULES" and will be filled in as
      rules are defined and executed.  For each rule, the
      table holds its current logic value, and a pointer to
      its "evaluator function."

      At the right side of the diagram are the evaluator
      functions.  These are what define each rule, that is,
      specify their "logical content."  They are created by
      DEFINE.  Each of these is a Forth subroutine, which
      may consist of subroutine calls to other rules,
      illustrated by pointers in the diagram, or other
      Forth functions to print messages or obtain inputs.
      For example, the definition which is associated (via
      the rules table) with the rule CARNIVORE is an OR
      combination of two other rules, EATS-MEAT and T1.
      The definitions for the rule EATS-MEAT is shown here
      as a Forth subroutine which asks the operator a
      question, and obtains an answer.  (We presume the
      existence of Forth functions ASK and GET-INPUT.)

      This differs from the data driven system described in
      Chapter 8 in the following respects:

         * it's not one data structure, but three.

         * the "input" arcs are represented by the series
           of function calls that comprise a rule.

         * the "output" arcs are not stored.  There is no
           support for forward chaining.

         * the "node type" (input, AND, or OR) is
           represented "procedurally," that is, by the
           functions which make up the rule definition.

         * any input prompts or node messages are also
           given "procedurally," using Forth functions.

         * the ASCII description of the node is the name of
           the Forth word.  This is stored by Forth when
           the word is created.  (We've been using the
           Forth function ID. to print this out.)

      Memory is allocated by a mixture of techniques:

         * the rules table is a simple, fixed-size array,
           allocated by the program.

         * rule definitions are kept in the extensible
           Forth dictionary, and all of the problems of
           allocation are handled by the Forth compiler.

         * the backward chaining logic uses the Forth
           subroutine return stack to "remember" the path
           through the logic tree.

      We have seen how rules can be easily added and
      changed, input and output messages can be added, and
      a logic trace can be incorporated into this system.
      So, even though it does not exactly follow the
      example from Chapter 8, the expert system we have
      evolved here, by its use of the facilities offered by
      Forth, is, in essence, a data-structured system, with
      all of the concomitant advantages.

