How to implement a rule engine in C#


Recently there was an interesting question on StackOverflow about creating a rule engine in C#.

Say we have a collection of Users (with Name, Age, ...) and rule definitions like this:

static List<Rule> rules = new List<Rule> {
     new Rule ("Age""GreaterThan""20"),
     new Rule ( "Name""Equal""John"),
   new Rule ( "Tags""Contains""C#" )
};

and we want to be able to evaluate the rules:

// Returns true if User satisfies given rule (e.g. 'user.Age > 20')
bool Matches(User user, Rule rule)
{
    // how to implement this?
}
 
One  obvious solution is to use reflection.
Here we will show a solution which uses Expression trees to
compile the rules into fast executable delegates. We can then evaluate the rules as if they were normal boolean functions.

public static Func<T, bool> CompileRule<T>(Rule r)
{
    var paramUser = Expression.Parameter(typeof(User));
    Expression expr = BuildExpr<T>(r, paramUser);
    // build a lambda function User->bool and compile it
    return Expression.Lambda<Func<T, bool>>(expr, paramUser).Compile();
}
 
static Expression BuildExpr<T>(Rule r, ParameterExpression param)
{
    var left = MemberExpression.Property(param, r.MemberName);
    var tProp = typeof(T).GetProperty(r.MemberName).PropertyType;
    ExpressionType tBinary;
    // is the operator a known .NET operator?
    if (ExpressionType.TryParse(r.Operator, out tBinary))    {
        var right = Expression.Constant(Convert.ChangeType(r.TargetValue, tProp));
        // use a binary operation, e.g. 'Equal' -> 'u.Age == 15'
        return Expression.MakeBinary(tBinary, left, right);
    } else {
        var method = tProp.GetMethod(r.Operator);
        var tParam = method.GetParameters()[0].ParameterType;
        var right = Expression.Constant(Convert.ChangeType(r.TargetValue, tParam));
        // use a method call, e.g. 'Contains' -> 'u.Tags.Contains(some_tag)'
        return Expression.Call(left, method, right);
    }
}
 
Now we can implement the rule validation by compling the rules and then simply invoking them:

var rule = new Rule ("Age""GreaterThan""20");
Func<Userbool> compiledRule = CompileRule<User>(rule);
 
// true if someUser.Age > 20
bool isMatch = compiledRule(someUser);

Of course we compile all the rules just once and then use the compiled delegates:

// Compile all the rules once.
var compiledRules = rules.Select(r => CompileRule<User>(r)).ToList();
 
// Returns true if user satisfies all rules.
public bool MatchesAllRules(User user)
{
    return compiledRules.All(rule => rule(user));
}
 
Note that the “compiler” is so simple because we are using 'GreaterThan' in the rule definition, and 'GreaterThan' is a known .NET name for the operator, so the string can be directly parsed. The same goes for 'Contains' – it is a method of List. If we need custom names we can build a very simple dictionary that just translates all operators before compiling the rules:

Dictionary<stringstring> nameMap = new Dictionary<stringstring> {
"greater_than""GreaterThan" },
"hasAtLeastOne""Contains" }
};

That’s it. As an improvement we could add error messages to the rule definitions and print the error messages for the unsatisfied rules.

If you found this useful, feel free to rate the answer on StackOverflow.

Posted by Martin Konicek on 1:10 PM 63 comments

Covariance and contravariance - simple explanation

This is a very concise tutorial on covariance and contravariance. In 10 minutes you should understand what these concepts are and how to use them. The examples are in Scala, but apply to Java or C# as well.

Covariance

Assuming Apple is a subclass of Fruit, covariance lets you treat say List[Apple] as List[Fruit].

val apples = List(new Apple(), new Apple())
processList(apples)

def processList(list:List[Fruit]) = {
  // read the list
}

This seems obvious - indeed, a list of apples is a list of fruit, right?

The surprise comes when we find out this does not work for arrays. Why is that so? Because you could do the following:

val a = Array(new Apple(), new Apple())
processArray(a)

def processArray(array:Array[Fruit]) = {
  array(1) = new Orange() // putting an Orange into array of Apples!
}

The main difference between List and Array here is that the List is immutable (you cannot change its contents) while the Array is mutable. As long as we are dealing with immutable types, everything is OK (as in the first example).

So how does the compiler know that List is immutable? Here is the declaration of List:

sealed abstract class List[+A]

The +A type parameter says "List is covariant in A". That means the compiler checks that there is no way to change contents of the List, which eliminates the problem we had with arrays.

Simply put, a covariant class is a class from which you can read stuff out, but you can't put stuff in.


Contravariance

Now when you already understand covariance, contravariance will be easier - it is exactly the opposite in every sense.

You can put stuff in a contravariant class, but you can never get it out (imagine a Logger[-A] - you put stuff in to be logged). That doesn't sound too useful, but there is one particularly useful application: functions. Say you've got a function taking Fruit:

// isGoodFruit is a func of type Fruit=>Boolean
def isGoodFruit(f:Fruit) = f.ageDays < 3

and filter a list of Apples using this function:

val list:List[Apple] = List(new Apple(), new Apple())
list.filter(isGoodFruit) // filter takes a func Apple=>Boolean

So a function on Fruits is a function on Apples - the filter will throw Apples in and isGoodFruit will know how to handle them.

The type of isGoodFruit is actually Function[Fruit, Boolean] - yes, in Scala even functions are traits, declared as:

trait Function[-A,+B]

So functions are contravariant in their parameter types and covariant in their return types.

OK, that's it; this is the minimal explanation I wanted to cover.

Posted by Martin Konicek on 11:39 PM 8 comments

Software engineering radio - best episodes

Software engineering radio is an excellent podcast full of in-depth information for developers; contains high quality content different from what you usually find online.

General

NoSQL and MongoDB with Dwight Merriman
Top 10 Architecture Mistakes with Eoin Woods
Being a consultant - honest, informal and funny
Software Craftsmanship with Bob Martin - concentrated motivation
Stefan Tilkov on REST - quite practical
Singularity research OS - microkernels, safety, static code analysis

Scala

Martin Odersky on Scala - great interview with the author of Scala
Scala Update with Martin Odersky - second half provides insights into possible future of programming

OmegaTau


Btw, Markus Völter (the guy behind se-radio) also does a podcast on technology and science. Software engineer talking to a Nuclear fusion expert - what could we want more? ;) I really enjoyed the following episodes:

Astrobiology at the NASA Astrobiology Institute
Quantum computing - kudos for mentioning the "next technical revolution"
Nuclear Fusion at MPI für Plasmaphysik



Please help me find great episodes - if you know about an episode that you really enjoyed, post it into comments. Thanks!

Posted by Martin Konicek on 2:00 PM 7 comments

TFS addin for Outlook TaskConnect released!

TaskConnect connects Outlook with issue tracking systems in a very cool way. So far there is support for TFS (2008, 2010) and Redmine.

This is how TaskConect looks inside Outlook:



It has many useful concepts making you deal with your tasks in no time. Be sure to check out the entirely new website.

Posted by Martin Konicek on 12:08 AM 0 comments

Scripting in Scala

Imagine we have a long text file, for example:

'CHINESE' : 'zh',
'DUTCH': 'nl',  
'ENGLISH' : 'en',
'SPANISH' : 'es',

And we want to turn it into this:

'zh' : 'Chinese',
'nl' : 'Dutch',  
'en' : 'English',
'es' : 'Spanish',

What we want to do is very simple: "Swap the two parts on every line!", and I believe it should be this simple also in code. Let's see how it looks in Scala:

import scala.io.Source

val lineRegex = "\\s+'(.+)'.*'(.+)'.*".r

for(line <- Source.stdin.getLines) {
   val lineRegex(name, code) = line
   println("'%s': '%s'," format (code, name.toLowerCase.capitalize))
}

That's 5 lines including the import, and the code is readable. Now we can run:

cat languages.txt | scala ourScript.scala > output.txt

That's it.

Btw, let's look at at the options we had for solving the problem:
  1. We don't want to be writing code in Java, C++ or C# and actually compiling an executable. Also you can imagine that the code in any of these languages would be overly complicated.
  2. OK, so we definitely should use a scripting language. What options do we have?
    • sed, awk, perl - Learn a (cryptic) language just for the purposes of scripting? No thanks.
    • Python, F#, Scala - All these languages have an amazing property that while you are already building your applications in them, you can use them for writing quick scripts. Scala is just elegant and more innovative than F# or Python. For a deeper look how the magic with lineRegex works, see this. If unfamiliar with Scala, here is a quick overview.

Posted by Martin Konicek on 4:02 PM 2 comments