All Manuals > KnowledgeWorks and Prolog User Guide > 6 Advanced Topics

NextPrevUpTopContentsIndex

6.2 Optimization

6.2.1 Forward Chaining

6.2.1.1 KnowledgeWorks Structures

A CLOS class may be replaced by a structure for increased speed when all the power of CLOS is not needed. Within the rule interpreter the structure behaves like a CLOS class which:

A KnowledgeWorks structure is defined by the macro

(def-kb-struct <class-spec> <slot-spec>*)

where the arguments are the same as for defstruct except that in <class-spec> only the options :include and :print-function are allowed. A structure may only be included in a KnowledgeWorks structure if it too is a KnowledgeWorks structure defined by def-kb-struct. All the functions normally provided by defstruct (accessors, a predicate etc.) are generated. An instance of the structure class may be created by the generic function

(make-instance <class-name> 
             {<slot-specifier> <value>}*)

where <slot-specifier> is the keyword version of the slot name, as with any structures, and <value> is the value the slot is to take, otherwise defaulting to the value specified in the def-kb-struct form. If created from Lisp by any means other than make-instance (for example, by the automatically defined make-<structure-name> constructor), the inference engine will not know about the structure.

Once created, structures must not be modified directly from Lisp as this will corrupt the state of the forward chaining inference engine. For example:

(def-kb-struct train position speed)
(def-kb-struct signal position color)
(make-instance 'train :position 0 :speed 80)
(make-instance 'signal :position 10 :color 'red)

defines KnowledgeWorks structures for trains and signals and makes an instance of each. Note that they are not fully-fledged CLOS objects but are analogous to working memory elements in OPS5.

6.2.1.2 Efficient Forward Chaining Rule Preconditions

Forward chaining rules are more efficient if the more restrictive preconditions (that is, the ones which will have fewer matches) are written first. Computationally cheap Lisp tests should be used wherever possible as they reduce the search space of the rule interpreter. The Lisp tests should where possible be broken into sufficiently small pieces that they can be applied as early on as possible.

For example, the precondition fragment

(train ?t position ?p1)
(test (> ?p1 5))
(signal ?s position ?p2)
(test (> ?p2 6))

is better than

(train ?t position ?p1)
(signal ?s position ?p2)
(test (and (> ?p1 5) (> ?p2 5)))

because in the first example the Lisp tests can be applied directly to the trains and signals respectively before looking at combinations of trains and signals, whereas in the second case all the combinations must be produced before the Lisp test can be applied. Simply separating the tests is enough for the rule compiler to apply them to the right object base matches -- the precise order of the tests is unimportant.

6.2.2 Conflict Resolution

6.2.2.1 Use of Contexts

The single most significant way to improve conflict resolution time is to divide the rulebase up into contexts. The time taken by conflict resolution is dependent on the total number of instantiations of all the rules in the context so the fewer rules in each context, the more efficient conflict resolution will be.

6.2.2.2 Optimization of the Strategy

A conflict resolution strategy may be optimized by combining the constituent tactics in a more effective manner. There are three different types of conflict resolution tactic:

KnowledgeWorks is best able to optimize rule-defined tactics and least able to optimize dynamic tactics. The optimizations for a particular type of tactic can only be applied if it is preceded only by tactics which can be optimized to the same degree (or better). For example, in the strategy (recency priority), the tactic priority would only be optimized as a static tactic. In the strategy (priority mea recency), priority can be optimized as a rule-defined tactic but recency will be treated as a dynamic tactic.

Some final points to bear in mind:

6.2.3 Backward Chaining

6.2.3.1 Pattern Matching

The KnowledgeWorks Backward Chainer indexes clauses for a backward rule based on the first argument. If the first arguments to backward rule clauses are distinct non-variables, the backward chainer can pre-select possible matching clauses for a call.

For example, in the following rule:

(defrule age-of :backward
                ((age-of charlie 30) <--)
                ((age-of william 25) <--)
                ((age-of james 28) <--))

The call: (age-of james ?x) would jump directly to the third clause and bind ?x to 28 without trying the other two.

The call: (age-of tom ?x) would fail immediately without doing any pattern matching.

Clauses are distinguished first by the types and then the values of their first arguments.

6.2.3.2 Tail Recursion

The KnowledgeWorks Backward Chainer supports the transformation of "tail-recursive" calls into jumps. Thus, stack overflow can be avoided without resorting to "repeat, fail" loops in most cases. For example, given the definition:

(defrule run-forever :backward
                    ((run-forever)
                    <--
                     (run-forever)))

the call: (run-forever) will run forever without generating a stack overflow. Note that this optimization is not limited to recursive calls to the same rule. The last call of any rule will be compiled as a jump, drastically reducing stack usage.

6.2.3.3 Cut

The use of "cut" is a well known performance enhancement for Prolog-style rules. In KnowledgeWorks it does more than reduce the time spent in search. When a "cut" is invoked, all the stack space between the initial call to the containing rule and the current stack location is reclaimed immediately, and can have a significant impact on the total space requirements of a program.


KnowledgeWorks and Prolog User Guide (Unix version) - 26 Feb 2015

NextPrevUpTopContentsIndex