3.1 Forward chaining

3.1.1 Overview

Forward chaining rules consist of a condition part and an action part. The condition part contains conditions which are matched against the object base. If and only if all the conditions are matched, the rule may fire. If the rule is selected to fire, the actions it performs are given in the action part of the rule. The process of selecting and firing a rule is known as the Forward Chaining Cycle, and the forward chaining engine cycles repeatedly until it runs out of rules or a rule instructs it to stop. KnowledgeWorks forward chaining rules reside in a group of rules, or context, and may have a priority number associated with them for conflict resolution (choosing which of a set of eligible rules may fire).

3.1.2 Forward Chaining Syntax

Forward chaining rule bodies are defined by:

<body> ::=

          [:context <context-name>]

          [:priority <priority-number>]

          <forward-condition>* --> <expression>*)

where <context-name> is the name of a context which has already been defined (see Control Flow) defaulting to default-context, and <priority-number> is a number (see Control Flow ) defaulting to 10.

The syntax for forward-conditions is:

<forward-condition> ::=

     <object-condition>

     |  (test <lisp-expr>)

     |  (not <forward-condition>+)

     |  (logical <forward-condition>+)

<object-condition> ::=

     (<class-name> <variable> [<object-slot-condition>]*)

<object-slot-condition> ::=

     <slot-name> <term>

<object-condition> is an object-base match where the variables (introduced by "?") in <term> are bound (via destructuring) to the corresponding data in the slot named by <slot-name>. <variable> is a single variable bound to the object matched.

Note: "?" on its own denotes an anonymous variable which always matches.

(test <lisp-expr>) is a Lisp test where <lisp-expr> is any Lisp expression using the variables bound by other conditions, and which must succeed (return non-nil) for the condition to match. Computationally cheap Lisp tests can frequently be used to reduce the search space created by the object base conditions. Lisp tests, and any functions invoked by them, should not depend on any dynamic global data structures, as changing such structures (and hence the instantiations of the rule) will be invisible to the inference engine. Lisp tests can depend on the values of slots in objects matched by preceding object-base conditions only if the values are bound to variables in the rule using the <object-slot-condition> syntax. They cannot depend on values obtained by calling slot-value or a reader function.

(not <forward-condition>+) is simply a negated condition. A negated condition never binds any variables outside its scope. Variables not bound before the negation will remain unbound after it.

(logical <forward-condition>+) is used to indicate clauses that describe the logical dependencies amongst objects. See Logical Dependencies and Truth Maintenancefor more details.

Note that if a forward chaining rule contains any conditions at all then it must contain at least one object base reference of the form


(<class-name> <variable> ...)

The syntax for expressions is:

<expression> ::=

       <forward-condition>

         |(erase <variable>)

         |(assert (<class-name> <variable>

                   [<slot-name> <term>]*))

         |(context <context-list>)

         |(return)

         |(<lisp-expr> <term>*)

         |<goal>

<forward-condition> is a forward condition which must succeed for execution of the action part of the rule to continue.

(erase <variable>) removes the instance bound to <variable> from the knowledge base. It is an error if <variable> is bound to anything but a KnowledgeWorks instance.

(assert (<class-name> <variable> [<slot-name> <term>]*)) is an assertion which modifies the contents of the object base, where if <variable> is unbound a new object of the given class with the given slot-values is created, and if it is bound, the object to which it is bound has its slots modified to the given values.

(context <context-list>) adds the given list of contexts to the top of agenda (see Control Flow).

(return) passes control to the top context on the agenda and removes it from the agenda (see Control Flow).

(<lisp-expr> <term>*) binds the result or results of calling <lisp-expr> to the <term>s with execution of the rule terminating if any bindings fail (if no <term>s are given execution will always continue).

<goal> may be any backward chaining goal expression (see Backward Chaining).

Note that in the action part of a rule, only backward chaining goals and object base matches invoke the backward chainer.

3.1.2.1 Example

(defrule move-train :forward

          :context train

          (train ?train position ?train-pos)

          (signal ?signal position ?signal-pos

           color green)

          (test (= ?signal-pos (1+ ?train-pos)))

-->

  ((format t "~%Train moving to position ~s"

              ?signal-pos))

  (assert (signal ?signal color red))

  (assert (train ?train position ?signal-pos)))

specifies that if there is a train with a green signal directly in front then the train may move on and the signal changes to red.

3.1.3 Defining Forward Chaining Rules

Forward chaining rules may be defined and redefined incrementally. When redefined all the instantiations of the rule are recreated. This means that during execution of a rulebase the redefinition capability should be used with care as previously fired instantiations will reappear and may fire again.

When a rule is redefined it inherits its order (with respect to the order conflict resolution tactic) from its initial definition. If this is not required, the rule should be explicitly undefined before being redefined.

A forward chaining rule may be undefined by entering


(undefrule <rule-name>)

A warning will be given if the rule does not exist.

3.1.3.1 Example


(undefrule move-train)

3.1.4 The Forward Chaining Interpreter

The forward chaining rule interpreter may be invoked by the Lisp function


(infer [:contexts <context-list>])

where <context-list> is a list of contexts where control is passed immediately to the first in the list, and the rest are placed at the top of the agenda. The object base may or may not be empty when the forward chainer is started. The infer function returns the final cycle number. When not specified, <context-list> defaults to (default-context).

3.1.5 Control Flow

3.1.5.1 The Agenda

The agenda is essentially a stack of rule groups (called contexts) which are still awaiting execution. The initial invocation of the forward chainer and any subsequent rule can cause contexts to be added to the top of the agenda. During normal execution the forward chainer simply proceeds down the agenda context by context. When the agenda is empty, passing control on will terminate the execution of the rule interpreter. This is a proper way to exit the forward chainer.

3.1.5.2 Contexts

Contexts are the groups into which rules are partitioned. The context default-context always exists. Contexts are defined by:

<context> ::=

          (defcontext <context-name>

                      [:strategy <CRS>]

                      [:auto-return t | nil]

                      [:meta <meta-actions>])

                      [:documentation <doc-string>])

where <context-name> is a symbol, <CRS> is a conflict resolution strategy defaulting to (priority recency order) (see below). If :auto-return is set to t (the default) then when the context has no more rules to fire, control passes to the next context on the agenda, but if it is nil an error occurs (a rule in the context should have issued a (return) instruction explicitly). The :meta option is necessary only if the default behavior of the context is to be modified and is explained in Meta Rule Protocol. If :documentation is given, then doc-string should be a string and the value can be retrieved by calling the function documentation with doc-type context.

3.1.5.3 Conflict Resolution

Every context has its own conflict resolution strategy, specified in the defcontext form. A conflict resolution strategy is an ordered list of conflict resolution tactics. A conflict resolution tactic may be any of the following:

priority -- instantiations of rules with the highest priority are preferred
-priority -- instantiations of rules with the lowest priority are preferred
recency -- the most recently created instantiations are preferred
-recency -- the least recently created instantiations are preferred
order -- instantiations of rules defined/loaded earliest are preferred. This favors the topmost rules in a file.
-order -- instantiations of rules defined/loaded latest are preferred
specificity -- the most specific rules are preferred (specificity is a score where a point is awarded for every occurrence of a variable after the first, every Lisp test, and every destructuring expression; the highest score wins)
-specificity -- the least specific rules are preferred
mea -- (stands for Means End Analysis) instantiations are preferred where the object corresponding to the topmost object-matching condition is more recently modified
-mea -- instantiations are preferred where the object corresponding to the topmost object-matching condition is less recently modified
lex -- (stands for LEXicographic) each instantiation is represented by the (in descending order) sorted list of the most recently modified cycle numbers of the objects in the instantiation; these lists are compared place by place with an instantiation being preferred if it first has a larger number in a particular position, or if it runs out first (hence the analogy with lexicographic ordering)
-lex -- the converse of the above.

The tactics are applied successively starting with the left-most until only one instantiation is left or until all tactics have been applied when it is unspecified which of the resulting set is chosen. For example, using the strategy (priority recency) first all the instantiations which are not of the highest priority rule or rules (as given by the rule's priority number) are discarded and then all instantiations which were not created in the same forward chaining cycle as the most recently created instantiation will be discarded. If more than one instantiation is left it is unspecified which will be selected to fire.

Note that the strategy (lex specificity) is equivalent to the OPS5 strategy LEX and (mea lex specificity) is equivalent to the OPS5 strategy MEA, hence the borrowing of these terms. For further information on LEX and MEA in OPS5 the reader is referred to Programming Expert Systems in OPS5 , by Brownston, Farrell, Kant and Martin (published by Addison-Wesley). However, KnowledgeWorks is not heavily optimized to use the tactics mea, -mea, lex or -lex.

3.1.6 Examples

(defcontext trains

            :strategy (priority recency order)

            :auto-return t)

(defcontext trains)

These two definitions are in fact equivalent.

3.1.6.1 Defining Contexts

A context may be defined and redefined. Redefining a context will clear all the rules in the context.

A context may be undefined and removed by entering


(undefcontext <context-name>)

3.1.7 Forward Chaining Debugging

Forward chaining debugging may be turned on by typing


(all-debug)

and off by typing


(no-debug)

When KnowledgeWorks is started, debugging is on. Debugging allows the actions of forward chaining rules to be single-stepped like backward chaining rules (see Backward Chaining Debugging), and also records information on which objects are modified by which rules. For information on how to use the debugging tools, refer to The Programming Environment.