Two-Minutes Scala Rules Engine

Scala is really seductive. To drive my learning of this JVM programming language, I thought I should go beyond the obvious experiments and try to tackle a subject dear to my heart: building a general purpose rules engine.

Of course, the implementation I am going to talk about here is naive and inefficient but the rules engine is just a pretext here: this is about Scala and how it shines. And it is also a subset of what Scala is good at: I mainly scratch the surface by focusing on pattern matching and collections handling.

The fact representation I use is the same than the one used by RuleML: a fact is a named relationship between predicates. For example, in "blue is the color of the sky", color is the relationship between blue and sky. The rules engine matches these facts on predefined patterns and infers new facts out of these matches.

In Scala, I naturally opted for using a case class to define a fact, as the pattern matching feature it offers is all what is needed to build inference rules:

view plainprint?

1. case class Fact(rel: String, predicates: Any*) {  
2. override def toString: String = rel + "{" + predicates.mkString(",") + "}"  
3.   
4. override def hashCode : Int = {  
5.  var h = 31 + rel.hashCode  
6.  predicates.foreach(predicate => h = 31 * h + predicate.hashCode)  
7.  return h  
8. }  
9. }  

case class Fact(rel: String, predicates: Any*) {<br />override def toString: String = rel + "{" + predicates.mkString(",") + "}"<br /><br />override def hashCode : Int = {<br /> var h = 31 + rel.hashCode<br /> predicates.foreach(predicate => h = 31 * h + predicate.hashCode)<br /> return h<br />}<br />}<br />Normally you do not need to implement your own hashcode functions, as Scala's default ones are very smart about your objects' internals, but there is a known issue with case classes that forced me to do so.

For rules, I opted to have them created as objects constrained by a particular trait:

view plainprint?

1. trait Rule {  
2. def arity(): Int  
3. def run(facts: List[Fact]): Option[Fact]  
4. }  

trait Rule {<br />def arity(): Int<br />def run(facts: List[Fact]): Option[Fact]<br />}<br />The method of note in this trait is run which accepts a list of n facts and returns zero (None) or one (Some) new fact ; with n equals to the value of the arity function.

So how is the list of facts fed to the rule run method created? This is where the naive and inefficient part comes into play: each rule tells the engine the number of facts it needs to receive as arguments when called. The engine then feeds the rule with all the unique combinations of facts that match its arity.

This is an inefficient but working design. The really amazing part here is how Scala shines again by providing all what is required to build these combinations in a concise manner. This is achieved thanks to the for-comprehension mechanism as shown here:

view plainprint?

1. def combine[E](source : List[E], arity : Int) : List[List[E]] =  
2. rity match {  
3. case 0 => List(List())  
4.   
5. case _ =>  
6. for {  
7.   a <- combine(source.tail ::: List(source.head), arity-1)  
8.   b <- source  
9.   if (!a.contains(b))  
10. } yield a ::: List(b)  

def combine[E](source : List[E], arity : Int) : List[List[E]] =<br />arity match {<br /> case 0 => List(List())<br /><br /> case _ =><br /> for {<br /> a <- combine(source.tail ::: List(source.head), arity-1)<br /> b <- source<br /> if (!a.contains(b))<br /> } yield a ::: List(b)<br />}<br />Notice how this code is generic and knows nothing about the objects it combines. With this combination function in place, the engine itself is a mere three functions:

view plainprint?

1. def processUntilDone(factBase : Set[Fact], ruleBase : List[Rule]) : Set[Fact] =  
2. // call process until the fact base stabilizes  
3. processRules(factBase, ruleBase) match {  
4. case processedFactBase if (processedFactBase == factBase)  
5.   => factBase  
6.   
7. case processedFactBase  
8.   => processUntilDone(processedFactBase, ruleBase)  
9. }  
10.   
11. def processRules(factBase : Set[Fact], ruleBase : List[Rule]) : Set[Fact] =  
12. ruleBase match {  
13. case rule :: tail  
14.   => processOneRule(factBase, rule) ++ processRules(factBase, tail)  
15.   
16. case Nil  
17.   => factBase  
18. }  
19.   
20. def processOneRule(factBase : Set[Fact], rule : Rule) =  
21. Set() ++ combine(factBase.toList, rule.arity).flatMap(facts => rule.run(facts))  

def processUntilDone(factBase : Set[Fact], ruleBase : List[Rule]) : Set[Fact] =<br />// call process until the fact base stabilizes<br />processRules(factBase, ruleBase) match {<br />case processedFactBase if (processedFactBase == factBase)<br /> => factBase<br /><br />case processedFactBase<br /> => processUntilDone(processedFactBase, ruleBase)<br />}<br /><br />def processRules(factBase : Set[Fact], ruleBase : List[Rule]) : Set[Fact] =<br />ruleBase match {<br />case rule :: tail<br /> => processOneRule(factBase, rule) ++ processRules(factBase, tail)<br /><br />case Nil<br /> => factBase<br />}<br /><br />def processOneRule(factBase : Set[Fact], rule : Rule) =<br />Set() ++ combine(factBase.toList, rule.arity).flatMap(facts => rule.run(facts))<br /><br />With this in place, let us look at the facts and rules I created to solve the classic RuleML discount problem (I added an extra customer). Here is the initial facts definition:

view plainprint?

1. val factBase = Set[Fact](  
2.      Fact("Luxury", "Porsche"),  
3.      Fact("Regular", "Honda"),  
4.      Fact("Spending", "Peter Miller", 2007, 5500),  
5.      Fact("Spending", "John Doe", 2007, 4500))  

val factBase = Set[Fact](<br /> Fact("Luxury", "Porsche"),<br /> Fact("Regular", "Honda"),<br /> Fact("Spending", "Peter Miller", 2007, 5500),<br /> Fact("Spending", "John Doe", 2007, 4500))<br />And here are the two rules:

view plainprint?

1. object premiumCustomerRule extends Rule {  
2. def arity() = 1  
3.   
4. def run(facts: List[Fact]): Option[Fact] =  
5. facts match {  
6.  case List(Fact("Spending", customer: String, year: Int, amount: Int)) if (amount >= 5000)  
7.    => Some(Fact("Premium", customer))  
8.   
9.  case _  
10.    => None  
11. }  
12. }  
13.   
14. object luxuryDiscountRule extends Rule {  
15. def arity() = 2  
16.   
17. def run(facts: List[Fact]): Option[Fact] =  
18. facts match {  
19.  case List(Fact("Premium", customer: String), Fact("Luxury", item: String))  
20.    => Some(Fact("Discount", customer, item, "7.5%"))  
21.   
22.  case _  
23.    => None  
24. }  
25. }  
26.   
27. val ruleBase = premiumCustomerRule :: luxuryDiscountRule :: Nil  

object premiumCustomerRule extends Rule {<br />def arity() = 1<br /><br />def run(facts: List[Fact]): Option[Fact] =<br />facts match {<br /> case List(Fact("Spending", customer: String, year: Int, amount: Int)) if (amount >= 5000)<br /> => Some(Fact("Premium", customer))<br /><br /> case _<br /> => None<br />}<br />}<br /><br />object luxuryDiscountRule extends Rule {<br />def arity() = 2<br /><br />def run(facts: List[Fact]): Option[Fact] =<br />facts match {<br /> case List(Fact("Premium", customer: String), Fact("Luxury", item: String))<br /> => Some(Fact("Discount", customer, item, "7.5%"))<br /><br /> case _<br /> => None<br />}<br />}<br /><br />val ruleBase = premiumCustomerRule :: luxuryDiscountRule :: Nil<br />With this in place, calling:

view plainprint?

1. processUntilDone(factBase, ruleBase).foreach(fact => println(fact))  

processUntilDone(factBase, ruleBase).foreach(fact => println(fact))<br />produces this new fact base with the correct discount granted to good old Peter Miller but not to the infamously cheap John Doe:

view plainprint?

1. Spending{Peter Miller,2007,5500}  
2. Spending{John Doe,2007,4500}  
3. Regular{Honda}  
4. Luxury{Porsche}  
5. <span style="font-weight: bold;">Premium{Peter Miller}</span>  
6. <span style="font-weight: bold;">Discount{Peter Miller,Porsche,7.5%}</span>  

Spending{Peter Miller,2007,5500}<br />Spending{John Doe,2007,4500}<br />Regular{Honda}<br />Luxury{Porsche}<br /><span style="font-weight: bold;">Premium{Peter Miller}</span><br /><span style="font-weight: bold;">Discount{Peter Miller,Porsche,7.5%}</span><br />This is truly a two minutes rules engine: don't ship it to production! Thanks to the standard pattern matching and collection handling functions in Scala, this was truly a bliss to develop. On top of that, Scala's advanced type inference mechanism and very smart and explicit compiler take strong typing to another dimension, one that could seduce ducks addicts.

So why does Scala matter? I believe the JVM is still the best execution platform available as of today. It is stable, fast, optimized, cross-platform and manageable. An alternative byte-code compiled language like Scala opens the door to new approaches in software development on the JVM.

Closing note: an interesting next step will consist in parallelizing the engine by using Scala actors. But this is another story...