C.2 Backward Chainer

C.2.1 Backward Chaining Algorithm

The KnowledgeWorks backward chaining system is an extended Prolog written entirely in Lisp and based loosely on the Warren Abstract Machine (WAM). (see An Abstract Prolog Instruction Set by David H.D. Warren, Technical Note 309 SRI International October 1983). High performance is achieved by compiling each Prolog clause into a Lisp function and handling the Prolog control flow with continuation passing. This approach removes the need for interpretation and provides easy integration with CLOS.

C.2.2 Term Structure

In order to provide compatibility with Edinburgh Prolog, the KnowledgeWorks backward chaining system treats Prolog structured terms differently from lists. Structured terms whose functors are not `.' are stored as simple vectors with the functor as element 0 (for example, the term: foo(bar) is equivalent to #(foo bar)).

C.2.3 The Binding Trail

The variable binding trail for the backward chainer is stored in a simple vector but may overflow into list structure if the trail grows larger than the size of the vector: (30000). The system will continue to function normally when this happens but may slow down slightly and do more consing. (Note: We have never written a program that causes this to happen other than deliberately produced testing programs).