8 A Multitasking Application
Each process can achieve its goal through the following methods:
The application stores the goal patterns on a stack called the goal stack. Initially, the only item on the goal stack is the top-level goal. When a rule is selected whose conclusion matches the top goal in the goal stack, the goal is popped off of the goal stack, and the premises of the rule are pushed onto the goal stack. The backward chainer process repeatedly tries to achieve all of the goals in the goal stack. If it can do so, the original goal is achieved; that is, a fact is deduced that matches the original query pattern.
Each pattern can match more than one fact, rule, or both. To handle this situation, the reasoning chain splits into parallel branches for pursuing alternative derivations. All branches in the decision tree represent disjunctive, or alternative, reasoning paths. A new process is created when the stack is modified to avoid conflicts over the use of only one stack by alternative reasoning processes. This technique results in a one-to-one correspondence between the goals and the reasoning processes.
Each node has its own goal stack to represent the set of goals whose collective achievement would imply achievement of the top-level goal. When a process encounters a pointer to a rule as the top item on its goal stack, all of the premises of that rule have been satisfied, and the rule is applied. The conclusions of the rule are asserted into the database by using the variable bindings in effect at that node.
When a node is created with an empty goal stack, all necessary subgoals have been achieved; thus, some instance of the user's original query pattern has been inferred. The node sends a success message up the tree to its parent. This message allows the user to specify how many instances of the pattern to deduce. When that number of success messages are received, the tree is killed.
The root node in the tree is initialized with the top-level goal on its goal stack. Since the root is the only reasoning process at this point, the BC scheduler runs it. The BC scheduler allows each level in the tree to finish processing before the next level is activated.
Once a variable receives a binding in one premise or conclusion of a rule, the binding is propagated throughout the rule. Thus, each occurrence of the variable in the rule is effectively replaced with the symbol to which it is bound. For example, the following rules are not the same:
R1: (IF (THE BROTHER OF CLYDE IS ?BRO) (THE COLOR OF ?BRO IS ?COLOR) THEN (A SELECTED COLOR IS ?COLOR))If the fact
R2: (IF (THE BROTHER OF CLYDE IS ?BRO) (THE COLOR OF ?WHO IS ?COLOR) THEN (A SELECTED COLOR IS ?COLOR))
(THE BROTHER OF CLYDE IS JOE)is stored in the database, the rule
R1selects only the color of
R2does not select the color of anyone.
Generated with Harlequin WebMaker