This is the second of a three-part series, as follows:
In part one of this three-part series, I explained some of the historical influences that led Microsoft to design their Business Rules Engine as a ‘situated reasoning engine’. This aspect of the engine is centred on the following features:
- The abstract definition of rules in a high-level rule modelling language (BRL)
- The definition of predicates and functions within the BRL model
- A mechanism to bind predicates and functions to built-in and external code. We can consider that the code represents ‘sensors’ and ‘effectors’
- A mechanism that allows external code to raise ‘directive events’ with the engine. These events direct the engine to undertake asserts, updates, retracts, etc.
In this second part, I want to look at a pattern that exploits these features. Microsoft’s engine is often described as a ‘forward-chaining’ rule engine. However, like several other similar engines, it is entirely capable of undertaking ‘backward-chaining’ as well. It has no explicit, built-in support for the semantics of backward-chaining, which is a pity. However, the ‘situated’ capabilities of the engine are sufficient to implement the backward-chaining approach.
The terms ‘forward-chaining’ and ‘backward-chaining’ are not always clearly understood by rule developers. Let’s explore their definition by considering the following simple business rule:
Orders placed by customers with a total value greater than £1,000 attract an automatic discount of 10%
A supplier implements this rule within their order processing system. They create an executable rule that looks something like this:
IF
the value of the order is greater than £1,000
THEN
discount the order by 10%
This is familiar territory to any BizTalk developer who has used the BRE. However, let’s think about this from the customer’s perspective. The customer regularly places orders with the supplier to replenish stock. They discover the business rule by reading terms and conditions on the supplier’s web site and realise that they can take advantage of it. If they introduce a delay in placing orders and wait for their stock requirements to increase, they should be able to place a smaller number of orders with the supplier and ensure these orders generally have a higher value. By introducing some delay, within suitable limits, they can exploit the supplier’s business rule and lower the overall cost of acquisition.
The customer implements an automated order placement system integrated with their stock control. They want to express the business rule something like:
IF
the goal is to get a 10% Discount
THEN
place an order whose value is greater than or equal to £1,000
The customer’s rule represents exactly the same business rule the supplier’s rule, but looks at it from a different perspective. Logicians say that the supplier’s rule uses ‘forward reasoning’ and that the customer’s rule uses ‘backward reasoning’. The chief difference is that backward reasoning uses the concept of goals whereas forward reasoning simply evaluates known facts to infer data. In this case, the supplier uses forward reasoning to infer the need to apply a discount. The customer uses backward reasoning to work out what facts they needed to determine a stated goal. In the given example, the customer needs an order with a large enough value.
This is a very simple example of reasoning. In more complex scenarios, we often need to reason by chaining our rules. Consider the following forward-reasoning example:
(Priority 10)
IF
AND
the value of the order is greater than £1,000
the order has not been assessed for discounts
THEN
discount the order by 10%
update order
IF
AND
the value of the order is greater than £1,000
THEN
waive shipping charges
We had to add a flag to the first rule to ensure that it does not enter a never-ending cycle of re-assessment. You often need to do this when chaining. We also had to prioritise the first rule to make sure it always fires before the second rule. We want the second rule to take discounts into consideration when deciding to waive shipping charges.
The rule set uses ‘forward-reasoning’. However, the reasoning emerges from the mechanics of the chaining or rules in the recursive cycle implemented by the rule engine. That is why we call this an example of ‘forward-chaining’.
Rule developers often mistakenly believe that the term ‘forward-chaining’ is synonymous with the recursive mechanism used by the rule engine. We call this mechanism the ‘match-resolve-act’ cycle (some people call it the ‘recognise-act’ cycle). Say we assert an order with a baseline value of £1,000. During the first match-resolve-act, the engine matches this order to both rules. The first rule fires due to its priority. The value is reduced to £900 and the ‘discounts assessed’ flag is set. The rule calls ‘update’ to tell the engine that the order has been changed. At this point, the engine recurses and enters a second match-resolve-act cycle. It re-evaluates the rules and determines that neither rule now matches. The shipping charges are not waived.
You may not think much of the moral integrity of our fictional company in insisting that waiver decisions are based on discounted values. A real-world example would probably be a lot more complex than this, so please don’t trip up over this unpleasant bit of mock-commercialism. The point is that our engine has reasoned using multiple rules and forward chaining.
Let’s consider an attempt to express backward-reasoning:
IF
goal is to get 10% Discount
THEN
place an order
IF
AND
time since the last order was placed is less than 3 days
value of outstanding stock requirements is greater than or equal to £1,000
THEN
assert a new order for outstanding stock requirements
IF
time since the last order was placed is greater than or equal to 3 days
THEN
assert a new order for outstanding stock requirements
This time, I’ve not concerned myself with flags and priorities. The rules are just high-level statements of intent. The rules convey backward-reasoning using a goal. The goal is to get a 10% discount, if possible. The first rule states that to satisfy the goal we have to place an order. The next two rules are designed to provide orders.
To perform backward reasoning, we need some way to ask our rule set to try to satisfy the goal. The first rule can’t initially fire because there are no asserted orders. It needs somehow to ‘switch on’ the second two rules and use them to evaluate the time interval since the last order was placed made and the total value of outstanding order requirements. The second or third rule may then assert an order. If an order is asserted, the first rule can now fire and place it with the supplier. If the time interval since the last order was placed with the supplier is too long, the third rule may result in orders that do not attract a 10% discount. The rule set encodes the idea of delaying order placement for a limited period to try to obtain as many discounts as possible.
Somehow, we need to chain our rules, but in a different way to the forward-chaining example. We need the first rule to trigger, or at least enqueue, recursion while in the ‘match’ phase, rather than the ‘act’ phase. This requirement lies at the heart of ‘backward-chaining’. The rules are processed using the same match-resolve-act cycle used for forward-chaining, but when handling goals, they communicate the need to trigger recursion at a different stage. Forward-chaining is not a synonym for the match-resolve-act cycle.
If you read Part 1, you will hopefully be starting to glimpse how to do backward chaining. The ‘directive events’ feature provides us with the core mechanism for implementing this approach. It gives us a way of en-queuing engine operations during the match phase. We can write custom predicates to enqueue fact assertions in order to cause recursion, and call the code from rule conditions rather than rule actions. However, this code needs to do a bit more than just issue directive events. It needs to manage goals. Our code needs to exhibit the following characteristics:
- It must represent the notion of goals during rule-set execution. We could use a ‘Goal’ class and assert instances of the class as facts.
- It must distinguish between goals and sub-goals. A goal is a top-level statement of what we want to achieve. Sub-goals have distinct semantics, and represent steps along the way.
- It must associate sub-goals with goals. A goal maintains a collection of sub-goals. The code must provide functionality for maintenance of sub-goal collections.
- It must prevent duplicate sub-goals from being asserted. The set-based and recursive nature of the engine means that there is plenty of scope for asserting multiple identical sub-goal facts. These would redundantly represent the same sub-goal. This is highly undesirable and must be prevented.
These characteristics will provide enough functionality to implement our example rule set. However, as we will see, they miss one additional feature that we need to implement a general-purpose approach to backward-chaining. This will be the subject of Part 3.
To meet the above requirements, we could create a class to represent goals and sub goals.
The Goal class represent a top-level goal which you would normally assert to the engine to kick things off (you can use rules to assert top-level goals if you want). Each Goal maintains a set of sub goals. Although the set is a flat structure, the sub-goals are organised as a tree. Each sub-goal can assert further sub-goals as required, and each sub-goal keeps a record of its parent.
The code maintains separate sets of sub-goals keyed on each instance of IRuleSetExecutor. Every instance of a Rete node network has its own set of sub goals. This allows developers to assert the same top-level goal to multiple instances of the rule engine. That is probably not to be recommended, but it should work OK. The code can be conditionally compiled for the old Dictionary<K, V> or the new ConcurrentDictionary<K, V> class introduced in .NET 4.0. When using Dictionary<K, V>, the code introduces some additional thread synchronisation.
The example code exhibits more complexity than we require for this first example. However, if you use the Goal and SubGoal classes directly, you will employ a ‘simple name’ goal pattern. This is sufficient for our first example. In this pattern, we identify each goal and sub-goal by a simple name only. The code ensures that only one sub goal of any given name can be asserted to the engine at any one time. You won’t get duplicates. In many cases, you wouldn’t get duplicates anyway because of the way the Rete Network optimises things. Even if multiple rules assert the same sub-goal, Rete will normally ensure that only one call is made to the AssertSubGoal() method. However, there are ways to invoke this method multiple times for the same named sub-goal, and we need to avoid asserting multiple instance of the SubGoal class for the same name.
The ‘simple name’ pattern allows us to represent the example rule set above as follows:
IF
AND
Goal.get_Name is equal to Get Maximum Discount
Goal.AssertSubGoal( executor , new SubGoal( Next Order ) )
THEN
Order.PlaceOrder
retract Order
IF
AND
SubGoal.get_Name is equal to Next Order
CurrentStockRequirements.GetValue is greater than or equal to 1000
Supplier.get_LastOrderDate is after DateTime.AddDays( -3 )
THEN
assert CurrentStockRequirements.CreateOrder( Supplier )
IF
AND
SubGoal.get_Name is equal to Next Order
CurrentStockRequirements.GetValue is greater than 0
NOT
Supplier.get_LastOrderDate is after DateTime.AddDays( -3 )
THEN
assert CurrentStockRequirements.CreateOrder( Supplier )
(Priority -100)
IF
Goal.IsAsserted
THEN
Goal.Retract( executor)
Look at the call to AddSubGoal() in the first rule. If the named sub goal has not already been added to the sub-goal collection, this method adds a new sub goal to the collection and issues a directive event to the engine requesting that the sub-goal is asserted. the method always returns ‘true’ so that it can be used as a predicate in the rule conditions.
We now have a genuine, if rather simplistic, example of backward chaining. You probably need to study the code a bit to get comfortable with the model. Don’t trip up over additional features of the code. We will come on that in Part 3. Note that the first rule is a good example of one that contains an ‘implicit’ condition. In the rule actions, we call the PlaceOrder method on an Order fact and then retract the Order. This means the rule has to match an Order fact in the first place. There is no explicit condition for this, but in effect, an additional condition is inferred at run-time from the action list. You can consider this implicit condition to be equivalent to: Order is not equal to <null>
At run-time, the engine will try to match all the conditions of the first rule. It won’t have an Order fact, but we will have asserted a main Goal fact named ‘Get Maximum Discount’ together with CurrentStockRequirments, Supplier facts and a DateTime value. The engine will do as much conditional evaluation as possible, and hence will call AddSubGoal(). This will assert a sub-goal named ‘Next Order’ that will be matched by the second and third rules. If either of these rules fire, they will assert a new Order. This will then allow the engine to find a complete match for the first rule. The first rule will fire and place the order. A fourth low-priority ‘clean-up’ rule is included to retract the main goal when all other processing is completed. The Goal class implements a Retract() method that recursively retracts all its sub-goals.
‘Backward-chaining’ experts will not be too impressed with the ‘simple name’ pattern. Also, this simplistic example hardly communicates the motivation for doing backward chaining in the first place. In the third part we are going to see that the ‘simple name’ approach suffers from limitations, and that we need to implement additional functionality to create a convincing general-purpose library to support backward chaining. We will also discuss scenarios where backward chaining may be a useful technique.
