3.2 Backward Chaining

3.2.1 Overview

Backward chaining involves trying to prove a given goal by using rules to generate sub-goals and recursively trying to satisfy those. The KnowledgeWorks backward chaining engine is an extension of the LispWorks Common Prolog system which can match directly over KnowledgeWorks CLOS objects (the object base). All the standard Common Prolog facilities and built in predicates are available. For more detailed information the reader is referred to the Common Prolog. Note that all the different ways of proving a particular goal are defined together in the same form.

3.2.2 Backward Chaining Syntax

Backward chaining rule bodies are defined as:

<body> ::= <clause>+

<clause> ::= (<goal> <-- <expression>*)

<goal> ::= (<rule-name> <term>*)

In each sub-clause of the rule, the goal must have the same arity (number of arguments). Within each <term> destructuring is allowed and variables are introduced by ? (and ? on its own denotes the anonymous variable which always matches). <expression> is as defined in Forward Chaining Syntax.

3.2.2.1 Example

(defrule link-exists :backward

  ((link-exists ?town1 ?town2)

<--

  (or (link ?link town1 ?town1 town2 ?town2)

      (link ?link town2 ?town1 town1 ?town2))

  (cut))((link-exists ?town1 ?town2)

<--

 (route-exists ?town1 ?town2)))

which says that a link exists between two towns either if there is a link object between them in the object base or if there is a route between the towns. The route-exists predicate would be defined by another backward chaining rule, or might be in the Prolog database.

3.2.3 Objects

Backward chaining rules may refer to the object base using the standard (<class-name> <variable> [<slot-name> <term>]*) syntax, and these expressions are instantiated directly without creating any sub-goals. The <class-name> of any CLOS class or KnowledgeWorks structure may not coincide with any backward chaining <rule-name>. The Common Prolog database may be used to record factual information but it is distinct from the object base in that it may contain variables, and anything in it is inaccessible to the forward chaining rule preconditions.

3.2.5 The Backward Chaining Interpreter

The backward chaining interpreter can be invoked from Lisp by the following functions


(any <expr-to-instantiate> <expr-to-prove>)

which finds any solution to <expr-to-prove> and instantiates <expr-to-instantiate>, and


(findall <expr-to-instantiate> <expr-to-prove>)

finds all the solutions to <expr-to-prove>, instantiates <expr-to-instantiate> for each and returns these in a list.

For other interface functions to be called from Lisp the reader is referred to Common Prolog.

From the action part of a forward chaining rule the backward chainer is called implicitly when a CLOS match or goal expression is used. The action part of forward chaining rules and the antecedents of backward chaining rules are syntactically and semantically identical.

3.2.5.1 Examples


(any '(?x is in (1 2 3)) '(member ?x (1 2 3)))

returns


(1 is in (1 2 3))

The following expression:


(findall '(?x is in (1 2 3)) '(member ?x (1 2 3)))

returns


((1 is in (1 2 3))(2 is in (1 2 3))(3 is in (1 2 3)))

3.2.7 Backward Chaining Debugging

Backward chaining debugging follows the Prolog four port model. Backward chaining rules may be "spied" (this is a Prolog term which corresponds to tracing and single-stepping) which puts a break-point on them and means they can be single-stepped when they are invoked. When forward chaining debugging is on, the action part of forward chaining rules can be spied and single-stepped in the same way when they are fired. The Programming Environment, explains this in detail. The leashing of the ports can be adjusted, details are to be found in Debugging.