Forward and Backward Chaining, Part 3

By Charles Forgy, PhD

This column looks in detail at the topic we discussed in general in the last column: How primarily forward-chaining production systems can provide support for backward chaining.  We are going to look at two real systems: JESS and OPSJ. It is interesting to compare these systems because they provide essentially the same functionality, but they do so using rather different designs.

Here is the problem we are going to consider: Suppose we are implementing an on-line order processing system, and that we are writing the rules to determine how much of a discount, if any, to give each customer based on these business rules:

R1. If the total price is >= $100.00 and < $1000.00, give a discount based on the following schedule:

Gold customers:         5%.

Silver customers:       3%.

All other customers:    0%.

 

R2. If the total price is >= $1000.00, give a discount based on the following schedule:

Gold customers:         7%.

Silver customers:       5%.

Bronze customers:       3%.

All other customers:    0%.

 

Suppose we will not know whether the customer is Gold, Silver, etc. unless we execute a time-consuming database access.

In a pure forward chaining system, we have two choices about how to implement these rules:

  1. We can always determine the customer’s class before deciding how big a discount to give.
  2. We can check the total price first, and only determine the customer’s class if the total price is at least $100.00.

Neither of these options is too attractive. The first will cause the system to perform unnecessary database accesses on many orders. The second will avoid the unnecessary database accesses, but it will complicate the rules and make the mapping between the business rules and the implementation rules less clear than it might be.

As will be illustrated below, backward chaining will enable the system to avoid the unnecessary database accesses while keeping a natural mapping between the business rules and the implementation rules.

Representing Attributes of Objects

Before describing how the systems implement backward chaining, we need to spend a few minutes on the more basic topic of how attributes of objects are represented in rule based systems. Two basic methods are used: The first is to use objects like those that would be used in Java or any other object-oriented programming language.  For example, a Customer might be represented as an instance of a class like this:

public class Customer

{

    public int mIdNumber;

    public String mName;

    public String mClass;

    . . .

}

 

The other basic method for representing attributes is to put each attribute and value into a separate fact object.  For instance, if the customer with IdNumber 1009 was named “John Smith” and had class “Bronze” the facts representing the customer might be

(isa  1009  Customer)

(name  1009  “John Smith”)

(class  1009  “Bronze”)

. . .

 

It should be noted that it is possible to combine these two representations—to put some information into a class like Customer, and other information into separate fact objects.

Backward Chaining in Jess

In JESS, backward chaining is performed on facts representing individual attributes, so rule R2 from above might be implemented as:[i]

(defrule R2JESS

;; If the current task is to compute the discount

;; for order number ?ord and customer ?cust

(Task (name ComputeDiscount)

      (order ?ord)

      (customer ?cust))

;; And order ?ord is for at least $1000.00

(Order (number ?ord)

       (amount ?amt & :(>= ?amt 1000.0)))

;; And the class of the customer is known

;; (Backward chain if necessary)

(class ?cust ?cls)

=>

;; Then apply the appropriate discount . . .

)

 

When JESS processes the above rule, if the class of the customer is known, the rule is executed as a standard forward chaining rule. However, if JESS determines that there is no object in working memory that matches the class condition it will automatically generate a goal to determine the class. The goal object looks like the object that this condition would match except that “class” is replaced with “need-class.” If this is customer 1009, the created goal is

(need-class  1009  nil)

 

Of course JESS does not backward chain on every condition that fails. So, how did it know that it was supposed to backward chain on the “class” condition? The answer is that a declaration has to be made before the rule is entered. The definition in this case is

(do-backward-chaining  class)

 

This says that all class conditions are to be considered by default subject to backward chaining. It may happen that in some rules backward chaining is inappropriate. In those rules backward chaining can be turned off by using the keyword explicit.  That is, the condition

(explicit (class ?cust ?cls))

 

will not result in backward chaining, while the condition in R2JESS will.

Backward Chaining in OPSJ

In OPSJ, backward chaining is performed on specific attributes of regular objects. So, instead of using a separate fact like

(class  1009  “Bronze”)

 

in an OPSJ program the class value would be held in a member field of the Customer object. Rule R2 could be written in OPSJ like this:

rule R2OPSJ

if {

// The current task is to compute a discount

t: Task (t.mName == “ComputeDiscount”);

// And the order is for at least $1000.00

ord: Order (ord.mNumber == t.mOrder,

            ord.mAmount >= 1000.0);

// And the class of the customer is known

// (Backward chain if necessary)

c: Customer(c.mIdNumber == t.mCustomer);

   need (c.mClass != null);

} do {

// Apply the appropriate discount . . .

}

 

In OPSJ, conditions where backward chaining may be needed are marked with the keyword “need.” The above rule says to use backward chaining on the mClass member of Customer c if its value is not currently known (or more specifically, if it has not been changed from its default value of null). So, when this rule is processed, if mClass is known, the rule behaves as a standard forward chaining rule. If mClass is not known, OPSJ causes a goal to be created to determine mClass.

Discussion

Both JESS and OPSJ allow us to do what we needed to do: To implement the business rules directly and yet insure that the database accesses are not performed unnecessarily. However, there are some interesting differences between the two languages:

  • JESS performs backward chaining on attributes represented as separate facts. OPSJ performs backward chaining on member attributes of standard objects.
  • In JESS a particular attribute can be declared to be backward chained, and the system will always backward chain on that attribute unless the keyword “explicit” is used to locally disable backward chaining. In OPSJ there are no global backward chaining declarations, and the system performs backward chaining only when the keyword “need” is used to locally enable backward chaining.


[i] The JESS and OPSJ rules use the actual syntax of the languages, but extensive comments are used, so it should not be necessary to be familiar with the languages to read the examples.