MS BRE Backward Chaining – Part 3: The ‘Bound Variable’ pattern

In this third, and final, part, we will extend the code to tackle more complex backward-chaining requirements.   The ‘simple name’ goal pattern is fairly easy to understand, but is limited. It provides a coarse-grained mechanism for switching sets of rules ‘on’ and ‘off’ in a backward-chained fashion. When this model fits the problem, it can work well. However, many real-world problems requires a greater degree of expressivity.

 

To understand the limitations of the approach, we will extend the scenario used in Part 2. A ‘customer’ company is implementing an automated order placement application that handles stock re-ordering and sends purchase order requests to suppliers. In Part 2, the customer wanted to introduce a degree of delay in placing orders with a specific supplier.   They want to send fewer purchase orders, but increase the average total value of any given order.   By increasing the value of orders, they hope to attract a higher number of discounts from the supplier.

 

In a real-world scenario, these rules would probably be part of a more complex, approach to policy-driven stock purchasing.   The customer may reason over a wider range of data to determine the most cost-effective way of satisfying their stock requirements. They will probably use multiple suppliers.   Each supplier will offer different terms. Purchasing policy will need to reflect these differences, reason over them and allow on-going adjustment to cater for changed terms, special offers, new and retired stock sources, etc.

 

We cannot hope to reflect that degree of complexity here.   However, if we extend our scenario just a little bit, we can begin to see the limitations of the ‘simple name’ pattern. However, before we address those limitations, we need to revisit the whole motivation for using backward-chaining in the first place.

In our example scenario, the customer deals with many different suppliers, and realises that a number of them offer similar, though not identical, terms. The example rule set in Part 2 was really designed for a single supplier. This is why, for example, the discount threshold value of £1,000 is ‘hard-wired’ as a literal value in the second rule.

 

We can fix this problem very easily.   First, we add a DiscountThreshold attribute to our Supplier fact type and assert multiple supplier facts at run-time.   Unfortunately, in Part 2, we used a single CurrentStockRequirements fact to represent all our current stock requirements.   We could fix this by re-implementing the GetValue() method of CurrentStockRequirements to accept the supplier ID and only return a value for the sub-set of stock items that we source from this supplier.   Of course, this is a gross simplification.   In a real-world system we probably have the additional complication that specific stock items can be sourced from multiple suppliers.   For the sake of simplicity, we will assume this complication does not arise or is dealt with elsewhere.

Rules 2 and 3 may end up looking something like this (I will use the supplier name as a unique identifier):

 

    IF

      AND

        SubGoal.get_Name is equal to Next Order

        CurrentStockRequirements.GetValue( Supplier.get_Name)  is greater than or equal to Supplier_getDiscountThreshold

        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( Supplier.get_Name) is greater than 0

        NOT

          Supplier.get_LastOrderDate is after DateTime.AddDays( -3 )

    THEN

      assert CurrentStockRequirements.CreateOrder( Supplier )

 

We have a new problem. Let’s say the customer asserts 100 Supplier facts, but only 15 of them offer order value-related discounts.   The two rules above will indiscriminately match the single CurrentStockRequirements fact against all 100 suppliers.  We can easily fix this by adding more attributes and extra conditions.   Our rules might become:

 

    IF

        SubGoal.get_Name is equal to Next Order

        Supplier.get_OffersDiscounts

        CurrentStockRequirements.GetValue( Supplier.get_Name)  is greater than or equal to Supplier_getDiscountThreshold

        Supplier.get_LastOrderDate is after DateTime.AddDays( -3 )

     THEN

      assert CurrentStockRequirements.CreateOrder( Supplier )

 

    IF

        SubGoal.get_Name  is equal to Next Order

        Supplier.get_OffersDiscounts

        CurrentStockRequirements.GetValue( Supplier.get_Name)  is greater than 0

        NOT

          Supplier.get_LastOrderDate is after DateTime.AddDays( -3 )

    THEN

      assert CurrentStockRequirements.CreateOrder( Supplier )

That’s OK, but what is the value of backward-chaining in this scenario?   None! We are now using forward-reasoning to infer a set of Orders for suppliers that offer discounts.   Our goals are entirely redundant.  

 

For such a simple example, it is hardly surprising to reach this conclusion. It highlights the following:

 

a) The direction of ‘reasoning’ is a matter of choice.   Any logic problem can be solved either through forward-reasoning or backward-reasoning.

b) The Microsoft Business Rules Engine naturally lends itself to forward-chaining.   You should use forward-chaining unless there is a good reason to do otherwise.

 

So why use backward chaining at all?   Well, look at this example again and you begin to glimpse the possible benefits.   First, forward-chaining tends to take an expansive ‘scatter-gun’ approach to problem solving. The above example finds all possible orders for all suppliers who offer discounts on order values.  

 

What if we have a number of additional criteria. Our policy may state that we only delay orders for suppliers of lower-value items who have a 97%, or higher, history of timely delivery, who have supplied to us on a regular basis for at least three years and who are ranked at 80% or higher satisfaction level for support. Forward-chaining approaches tend to solve these issues by adding more and more criteria to existing rules to filter the available facts down to the required subset. That’s OK, but complex policies are hard to manage.   Backward-chaining can be a useful mechanism for partitioning and simplifying our logic.   We could have other rules, or even rule sets, that specialise in inferring the set of eligible suppliers for delayed ordering.   We could then use that sub-set of suppliers to drive order placement towards the goal of maximising discounts.

 

As rule sets get bigger and more complex, we need to work much harder at structuring them in a way that retains the benefits of rules processing.   We need to align them closely to the business perspective.   We need to model business policy in a clean and traceable fashion.   We need to write rules that are understandable and can easily be amended and changed over time.   Backward-chaining is a tool we can use, where appropriate, for this purpose. Used well, it can make our rule sets easier to understand and manage.   It can even make rule processing more efficient.

 

The limitation of the ‘simple name’ model is that it can only be used at the level of entire rules.   It allows us to switch rules ‘on’ and ‘off’, but offers no further expressivity. If we want to exploit the goal-driven approach effectively, we need our goals to communicate more than just a name.    To focus the pattern search we need to somehow associate attribute values with the goals themselves.  Instead of simply saying ‘fire the rules that match this named sub-goal’, we need to state ‘fire the rules that match this sub-goal on a specific supplier’.

 

In the rules processing community, we describe this in terms of bound variables on our goals. The bound variables can be used to implement much more focused goal-driven logic by matching fact attributes.   In our very simple scenario, we can infer orders effectively using forward-chaining only.   However, let’s see what things might look like if we used a more expressive form of backward chaining.

 

Goals have different semantics to other facts.   They signal the overall purpose of the rule processing and the result we are seeking to reach.   In particular, we must avoid asserting duplicate sub-goals.   In Part 1, we differentiated sub-goals by name alone.   However, if we extend our goals to carry an unbounded collection of additional attribute values, we have a problem. It becomes easier and easier to inadvertently assert multiple sub-goals which are indistinguishable.   At the very best, this will make rule processing inefficient.   At worst, it could compromise the logic of our backward-chaining rule sets.

 

The sample code implements bound variable capabilities by extending each sub-gaol with an instance-level dictionary of name-value pairs.   In fact, this functionality is pushed all the way down to the abstract GoalBase type. Hence goals supports variables, as well as sub-goals. The GoalBase class overrides the equality/inequality operators and Equals method, and also implements and IEqualityComparer class for use with HashSets.   If you look at the code, you will see that goals test their equality using a combination of their names and any variable values they contain.   The BoundVariables dictionary accepts attribute values as objects.   The GoalBase class therefore  implements a number of ‘cast’ methods for accessing attribute properties according to specific types.

Whenever we assert a sub-goal, we can add variables to its collection.   These variables should be treated as read-only, though this sample code is not sophisticated enough to implement guards against abuse.   The only sensible way to initialize a sub-goal within our rules is to use a constructor.   Hence, the ‘bound variable’ pattern depends on developers sub-classing the Goal and/or SubGoal classes to create specialised goals and sub-goals.   Remember that the Microsoft Business Rules Engine offers no explicit support for backward-chaining, and has no mechanism for allowing us to declare goals within the rule language.   We have to create specialised Goal types in our own code.   Contrast this with a number of commercial engines that have built-in support for declaring goals.

 

You need to follow a simple pattern when sub-classing the Goal or SubGoal types.   Create a public instance constructor that passes a goal name value to a base constructor.   The name is still supported.   You may want to set it at construction time or use some ‘built-in’ name.   Define constructor parameters for each bound variable.   In the body of the constructor, populate the Variables dictionary with name-value pairs for each bound variable.

 

You can now implement the ‘bound variable’ pattern of backward-chaining.   In some ways, this is easier than the ‘simple name’ pattern. We now use specific classes for each goal and sub-goal type.   Hence, we don’t need to test for the name, though it is still there if you want to use it.   Better than that, we can compare sub-goal variable values in a natural fashion with other facts and implement properties to read variable values.   The sub-goals feel a lot less intrusive and integrate naturally into the expression of our rule conditions without obscuring the logic.

 

Here is the rule set for the ‘bound variable’ example in the downloaded code.

 

    IF

        MaxDiscountGoal.AssertOrderSubGoal( executor )

    THEN

      Order.PlaceOrder

      retract Order

 

    IF

        CurrentStockRequirements.GetValue( Supplier.get_Name )  is greater than or equal to Supplier_getDiscountThreshold

        Supplier.get_LastOrderDate is after DateTime.AddDays( -3 )

     THEN

      assert CurrentStockRequirements.CreateOrder( Supplier )

 

    IF

        CurrentStockRequirements.GetValue( Supplier.get_Name ) is greater than 0

        NOT

          Supplier.get_LastOrderDate is after DateTime.AddDays( -3 )

    THEN

      assert CurrentStockRequirements.CreateOrder( Supplier )

 

    (Priority -100)

    IF

      MaxDiscountGoal.IsAsserted

    THEN

      MaxDiscountGoal.Retract( executor )

 

Look at the AssertOrderSubGoal method of the MaxDiscountGoal class.   We use this is Rule 1 to assert a sub-goal.   Before we assert the MaxDiscountGoal to the engine (this is done in external code at the point we invoke the rule engine), we populate it with a SupplierName variable value for a given supplier.   We can assert multiple MaxDiscountGoals to the engine at one time.   The AssertOrderSubGoal communicates the SupplierName variable to a new instance of the OrderSubGoal class which is then asserted as a sub-goal.   In Rule 2 and Rule 3, we use the SupplierName variable on the sub-goal to match on a specific supplier.

 

Be very careful when implementing custom methods to assert or retract goals.   Notice how I use the inherited AssertSubGoal() method internally, rather than call Assert on the IRuleSetExecutor directly.   This is vital in order to exploit the built-in goal management features.   The cost of having no explicit support for goals in the BRE is that you must write external code and implement it correctly.   If you create custom constructors to manage variable initialisation and use the inherited assert and retract methods internally, your custom Goal and SubGoal classes should function correctly.

 

We can now assert a set of top-level Goals to the engine for a discrete group of ‘eligible’ suppliers.   This implies that we have done work elsewhere to determine which suppliers are of interest.   This helps us to partition our rules more effectively and make them more manageable. The rule fully exploits the backward-reasoning approach and is driven by the goals and sub-goals. Although we have introduced additional overhead due to testing equality using bound variable values, this will often be more than compensated for by a reduction in the overall amount of work the engine undertakes internally.

 

I have included an additional version of the rule set for Test 2 which uses vocabularies to represent the rule set as follows.   Some readers may find this easier to understand:

 

    IF

        the name of the supplier for maximised discounts  is equal to  the name of the order’s supplier

    THEN

      place the order

      retract the order

 

        the total value of current stock requirements for  the name of the supplier  is greater than or equal to the discount threshold offered by the supplier

        the date of the last order sent to the supplier is after now, -3 days

    THEN

      assert a new order to meet current stock requirements from Supplier

 

    IF

        the total value of current stock requirements for  the name of the supplier is greater than 0

        NOT

          the date of the last order sent to the supplier  is after  now, -3 days

    THEN

      assert a new order to meet current stock requirements from Supplier

 

    (Priority -100)

      the goal is to get the maximum discount from a supplier

    THEN

      retract the maximum discount goal from executor

 

Backward-Chaining can be a useful addition to the rule developer’s armoury.   It is a pity that the Microsoft Business Rule Engine does not provide built-in support.   However, the ability to implement effective models of backward-chaining over the engine without requiring any internal changes to the engine itself is eloquent testimony to the power and effectiveness of the ‘situated reasoning engine’ design of the BRE and its ability to handle directive events. I deliberately named all IRuleSetExecutor parameters in the sample code as ‘thisExecutor’ to indicate why the model is so powerful. In BRE we can endlessly extend the language through bindings to objects, methods, properties and literals.   However, the built-in ‘executor’ method allows us to attach custom code procedures directly to the engine itself. The pattern of passing a ‘this’ reference as the first parameter to a method is one of the most commonly used design patterns in our industry, even if the first parameter is typically ‘hidden’ or expressed as an object reference in front of the method call. It is no different, in essence, from the design of ‘extension’ methods in C# and has much the same expressive capabilities. We can bind to the abstract rule model to extend the rule language infinitely.   We can further bind to the executor to extend the rule engine infinitely.   It is a simple, but powerful model.

 

Of course, not everything is perfect and rosy. There are limits to the implementation of backward-chaining and some subtle issues of which you should be aware. You should take great care to tidy up after yourself.   Sub-goals are asserted within the rule set, and the Policy class won’t automatically clear them when processing is done because it doesn’t know about them.   the Policy class, of course, maintains a cache of rule engine instances, and un-cleared facts are cached with each instance.   This is great for ‘long-term’ facts but not for goals.   Always tidy up after yourself.   The Retract method implemented in the Goal class (and inherited by SubGoal) will retract the goal and all its sub-goals.   The RetractAllSubGoals method retracts only the sub-goals.    Sub-goals can be nested to any depth.

 

The recursive retraction mechanism implemented in the sample code is really the beginnings of the notion of ‘truth maintenance’.   When you retract a goal, you retract all the sub-goals associated with it.  If the goal is no longer active, neither are the sub goals.   Microsoft’s rule engine has no built-in notion of truth maintenance.  You can begin to see that it is possible to construct forms of truth maintenance using the ‘situated’ features.   However, a declarative approach would be nicer.   Be careful not to compromise the ‘immutability’ of the bound variables.  The Variables property is protected and should only be used in sub-classes to write variable values in the constructor.   Once initialised, never change the value of a bound variable.  They represent ‘functional’, not ‘procedural’ variables.   Mutable variables could lead to horrible logical issues and even (due to a long-standing bug in the engine) memory leaks.   Also, beware of changes to facts whose attribute values you bind onto a goal.   If those facts change, the changes are not reflected through the goal hierarchy.   Make sure your goal-based logic is watertight.

 

The code is not tested and comes with all the normal health warnings.  It is sample code only.   As well as the immutability issue I suspect a lot more could be done to optimise the equality checks and searches through sub-goal collections.    I hope, however, it will prove of interest to developers who need to tackle more complex problems in MS BRE, and a starting point for implementing backward chaining.

 

One last point.   Given some of the discussions and blog postings in the rules community over recent months, and the ‘rediscovery’ of Paul Haley’s 20 year old paper on data-driven backward chaining, this article is in danger of attracting some negative feedback regarding a lack of any support for what has been called ‘full opportunistic backward chaining’ (FOBC).   I’d like to get in there first and address this. Backward-chaining involves the instrumentation of rules in order to assert and match sub-goals.   Extensive manual instrumentation of large rule sets can quickly become onerous.   FOBC is an approach where instrumentation of rules sets is automated and the system exploits backward chaining wherever possible.   The instrumentation may be hidden from the rule developer.   This is based on the idea that it is possible to instrument rules for backward-chaining without changing its fundamental underlying logic.   A better logician than I (who am I kidding, I’m no logician at all) might be able to comment on the limits of this approach given the ‘impure’ nature of a Rete engine as a vehicle for implementing logic programs.   However, Paul’s approach is highly commendable. As he points out, one major benefit is that automated instrumentation introduces a general optimisation mechanism that typically reduces the work done by the engine.   All good stuff.

 

Technically, I believe it should be possible to implement FOBC for the Microsoft Business Rule Engine.   You could do this at the BRL level or you could do this at the level of programmatic rule sets which are represented as a ‘Rule Object Model’ object graph.   However, it would not be a trivial undertaking. Instrumenting rules at the object model level makes much more sense than at the BRL level because Microsoft’s translator performs rule set normalisation (application of DNF, De Morgan’s laws, etc.).   You would want to instrument the rule set in a specialised IRuleSetTranslator after normalisation and before Rete translation. I suspect there would still be a lot of edge cases to think about.   Anyway, this is something I have not attempted and have no plans to attempt.