This is the first of a three-part series, as follows:
Karl posted on forward and backward chaining at http://karlreinsch.com/2010/01/07/on-chaining/. I emailed him privately and talked a bit about how backward chaining can be implemented on Microsoft’s Business Rule Engine (I even sent him a little example). A couple of days later he published a second post at http://karlreinsch.com/2010/01/11/have-you-implemented-backward-chaining-on-a-microsoft-rule-engine/. So, I shall rise to the challenge and explain how backward chaining can be done in the BRE. However, I’ll leave that for parts 2 and 3. In this first part, I want to go over some of the history regarding the relevant features of the BRE and why they are there.
Back in the 1990s, IBM Research investigated the fascinating subject of ‘intelligent software agents’ (see http://www.research.ibm.com/iagents/). One of the outcomes of this research was the development of a technology called CommonRules and a rule language called ‘Business Rule Mark-up Language’ (BRML). IBM Research worked on CommonRules in the closing years of the 1990s, and Microsoft wrote their rule engine circa 2001-2003 (I was told that the rule engine started life in MS Research, but don’t know the details). CommonRules is not a rule engine, although it does come with an example forward chaining (non-Rete) engine. It is a Java-based technology for rule interchange with roots in the world of intelligent agents. BRML embodies some of the core concepts implemented in CommonRules. BRML is an important stepping stone in the history of rule standard specifications. Benjamin Grosof, who put together the specification, went on to become one of the co-founders of the RuleML initiative. RuleML represents, in part, an evolution of BRML. RuleML had a major influence on the development of the W3C RIF (Rule Interchange Format) standard. As well as RuleML, BRML also influenced Microsoft’s Business Rule Language (BRL).
Benjamin Grosof is an advocate for something called ‘Courteous Logic’ (CL). The idea of CL arose from research into how to support business rules in e-commerce and automated supply chain applications (how to ‘webize’ rules). It is based on the observation that business people sometimes specify contradictory business rules. The text-book example is:
Rule [1]: If the customer is loyal, give them a 10% discount.
Rule [2]: If the customer is a late-payer, don’t give them any discount.
What happens if you have a customer who is loyal, but never pays on time? Do they get a discount or not?
Courteous logic is based on ‘well-founded’ semantics (an important notion in logic programming) and adds a couple of constructs for handling contradiction. The first is a statement of priority between two rules called an ‘override’. When a match is found for two contradictory rules, the override determines which rule wins. In the above example, we might use an override to specify that Rule [1] trumps Rule [2]. The second construct is called a ‘mutex’. A mutex specifies mutual exclusivity rules when assessing facts. For example, in the above example, we could use a mutex to specify that a customer can’t be a late payer and be eligible for a discount. Mutexes and overrides provide a way of specifying additional constraints and partial orderings alongside rules which may be partial and contradictory. The idea is that this provides a more natural way to express the logic of business rules.
There is no support for courteous logic in the Microsoft rule engine. Grafting CL onto a rule engine based on the Rete Algorithm is not a trivial exercise. The only example I know of is SweetJess (part of SweetRules) which Benjamin Grosof and others worked on during the first few years of this millenium. The reason I mention BRML and CommonRules is that they embodied other ideas which provide real insight into the nature of Microsoft’s BRE. BRML (and, less explicitly, RuleML and W3C RIF) contains a real gem which comes straight from the world of ‘intelligent software agents’. This is the concept of ‘situatedness’.
A ‘situated’ system is one that is connected to the external world through ‘sensors’ and ‘effectors’. Sensors detect the current state of the external ‘situation’. Effectors change its state. The clever bit is that sensors and effectors can both report back to the situated system so that it can keep its internal representation of the external situation up to date.
We are in the mere foothills of intelligent software agents here. The vast rolling uplands of this fascinating subject lie before us. Nevertheless, situatedness is a simple but powerful concept, especially when applied to reasoning systems. Imagine a software agent or engine that can take, as input, a model of a set of rules. The model is abstract and high-level, but captures the essence of how to reason over some real-world situation. We need to hook up the model to that external situation. We can do this by binding discrete bits of the model to external sensors and effectors. Do we need to find out information about the state of the external world? No problem. We invoke a sensor. Do we need to change the state of the real world? We can invoke an effector bound directly to some representation of an ‘action’ in our rule set model.
That gets us a long way, but we need to go further. What if we need to sense something that doesn’t resolve into a simple Boolean truth value? Our sensors may need to notify our model-driven engine about more complex state. They may need to describe some aspect of the external world by asserting a number of facts about it. However, a sensor can’t just synchronously inject a whole lot of new facts straight into the innards of the engine. That might interfere with the engine’s current reasoning cycle. We need a way to raise ‘directive events’ which the engine will sink. Directives are requests that the engine will assert new facts, update existing facts, or retract facts when it is next safe to do so. The engine enqueues these directives and processes them asynchronously at the proper time.
It’s much the same with effectors. If the world were a simple place, an effector would only need to change some state value of the external situation according to the ‘pure belief’ of the reasoning engine. In reality, our effector might find that the engine’s ‘pure belief’ isn’t quite accurate. Perhaps it can’t make the state change as directed. It may discover new facts as a result of changing state. Effectors may also need to issue directives to the engine to ask it to update its internal representation of the world.
Sensors and effectors are explicitly represented in BRML. Sensors are associated with predicates used in rule conditions. Effectors are associated with rule actions. BRML captures the binding information which binds predicates and functions to external code. One small issue I have with this is that the notions of ‘sensor’ and ‘effector’ are really just semantics that we apply to our custom code. Rule developers may find that the language of ‘sensors’ and ‘effectors’ doesn’t always make sense in the real-world scenarios they are addressing. For example, if we write rules to process the XML content of business message, it may seem a little unnatural to think in terms of ‘sensing’ the XML.
Microsoft’s BRL is clearly influenced by BRML and CommonRules. Amongst other things, it borrows BRML’s terminology of ‘predicates’ and ‘functions’ and supports a similar model for binding these items to external code. It avoids using the terminology of ‘sensors’ and ‘effectors’, but betrays its allegiance to the concept of ‘situatedness’ by implementing a straight-forward mechanism that allows external code to issue ‘directive events’. The Microsoft Business Rule Engine is designed from the ground up to be ‘situated’.
BRL is a rule modelling language. The BRML influence means there is a (perhaps not immediately obvious) family resemblance to its cousin, the W3C RIF. By good fortune, it is also a lot like the OMG’s PRR (Production Rule Representation) which is a MOF-compliant rule modelling language. Like CommonRules and the W3C RIF, it defines libraries of ‘built-in’ predicates and functions. It doesn’t specify any implementation of these. Instead, the implementation is bound to the model within the engine using ‘engine operation’ binding definitions. BRL also defines three types of ‘user’ binding for XML data, database data and object-orientated classes. Class bindings bind directly to .NET types (value types and delegates, as well as classes). The XML and database bindings get special treatment in the engine which converts these to bindings onto specialised fact ‘wrapper’ classes (TypesXmlDocument, TypedDataTable and TypedDataRow). The engine also implements specialised Rete nodes which handle DataConnection facts and convert rule conditions into SQL SELECT statements. This allows the rule engine to reason directly over external databases (how’s that for ‘situatedness’!).
For ‘directive events’ BRL defines a built-in function called ‘executor’. If you pass this function as an argument to an IRuleSetExecutor parameter on a method in a custom .NET type, the Rete executor will pass itself out to your custom code. IRuleSetExecutor defines a number of engine operations including ‘assert’, ‘update’, ‘retract’, ‘clear’ and ‘halt’. Your custom code can raise a directive event by simply calling back on one of these methods. The engine processes the directive notification by en-queuing an engine operation which it then processes at the next safe point in its match-resolve-act cycle.
BRL’s support for bindings and directive events is both simple and powerful. The notion of ‘situatedness’ gives a whole new insight into the nature of Microsoft’s rule engine. The ability to raise directive events allows us to implement a vast array of different patterns and to integrate our rule set models and reasoning engine directly into the ‘real world’. We take our rule engine to the world and situate it there, rather than adapting the world to the rule engine.
Just after Christmas, I met up with fellow Londoner, Mark Proctor, who heads up the JBoss Rules (Drools) team. We had an enjoyably geeky afternoon discussing our favourite subject over coffee. Mark was explaining to me how Drools allows expressions within the rules to directly query the working memory. This is a powerful feature of Drools which it uses to perform various types of quantification and aggregation. This post arises in part from that conversation. I was saying how much I wished we had a similar feature in Microsoft’s BRE. I also tried (badly) to explain to him that if BRE were ever extended to support this, you would query the working memory from external code. I hope this post goes some way to explaining why that would be the case. I do wish MS BRE could query working memory like JBoss Rules. How about a LINQ provider over asserted facts. How cool would that be! Another feature that would improve things would be the ability to obtain the executor up-front before rule processing commences. I suggest that the RuleEngine class should expose it.
In parts 2 and 3, I shall directly address the issue of backward-chaining in MS BRE and show how it can be done through directive events and custom coding. The insight here is that backward-chaining can be implemented as a special case of ‘situatedness’. We can build an external goal management environment and then ‘situate’ our engine within it. This gives us an effective mechanism for extending the engine and performing backward-chaining.
