All Manuals > KnowledgeWorks and Prolog User Guide > Appendix C: Implementation Notes

C.1 Forward Chainer

C.1.1 Forward Chaining Algorithm

The KnowledgeWorks forward chaining engine is based on the RETE algorithm (see Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem by Forgy in Artificial Intelligence 19, September 1982). A data flow network representing the conditions of the forward chaining rules (a RETE network) is maintained and this keeps lists of the instantiations and partial instantiations of rules. This structure is modified at run time as objects change. The RETE algorithm relies on the tacit assumption that during the forward chaining cycle relatively few objects change (hence there are relatively few changes to be made to the network each cycle), and in these cases gives a huge increase in performance speed.

C.1.2 CLOS and the Forward Chainer

CLOS objects acquire KnowledgeWorks functionality from the standard-kb-object mixin. Object creation and modification hooks defined on this mixin enable the RETE network to track the objects. Objects are indexed into the RETE network by class and modifications propagated only where any changes to the slots of the object are relevant.

One potential problem is that as KnowledgeWorks CLOS objects are designed for use in ordinary code, performance could deteriorate seriously as every time an object is changed the RETE network must be amended. For this reason changes to CLOS objects are merely remembered as they are made. The stored set of changes is flushed at the start of every forward chaining cycle, so the penalty for using KnowledgeWorks objects is really only paid when the forward chainer is running.

C.1.3 Forward Chaining and the Backward Chainer

For more uniform semantics throughout KnowledgeWorks, the right hand side of KnowledgeWorks forward chaining rules are executed directly by the backward chainer, as is the default meta-interpreter for a context which has no meta-interpreter specially defined. When compiled with debugging turned off, in many cases the backward chainer can be optimized out leaving raw Lisp code.

KnowledgeWorks and Prolog User Guide (Unix version) - 01 Dec 2021 19:35:52