Business Rule Compiler Based on Expression Trees

Currently, notifications are a very important marketing tool that allows the businesses to both retain the user interest in the product and to maintain loyalty by showing relevant information about products and services, innovations, and more, to the user. In our project, however, such user notifications are a business product, a feature with which users can filter the necessary information based on the rules they create. In this article, I will tell you how we created the user notification feature and how we eventually built an expression-trees-based compiler that helped us successfully complete this task.

TL; DR

For those who prefer to read the code, here is a link to our GitHub repository.

Project and tasks

For our clients, we are developing an application that keeps the users informed about the global commodity markets, including metals, timber, agriculture, etc. Such markets are extremely volatile, so we had to create a feature for setting up user notifications that would allow to get the most relevant data in the shortest possible time.

For instance, let's assume a user is tracking aluminium price action and wants to get notified as soon as the price exceeds a specific value. With our application's feature, they can create a rule that will inform them about the appropriate event once it occurs.

Such a solution had to be as flexible as possible, relying only on the data scheme, and efficient, without overloading the servers with complex processing. This is why we decided to create a compiler that, based on the rule definition received as JSON, would create a function that takes the required arguments and returns the Boolean result (true: send a notification, false: do not send any notification). We created the compiler with C# and using expression trees.

Some more background info

Before we move further on, allow me to talk a little about the Expression Trees technology in .NET. Rather than copying and pasting the documentation text, however, I will give my personal view on this technology regarding this specific task.

Let's start with a simple Microsoft Excel workbook. This MS Office application is a dominating one in all business sectors, partly due to its rich features. Right now, let us focus on the User Defined Functions (UDFs). Using this feature, you can create calculations, link the results obtained at earlier stages, and based on them conduct other calculations or analysis. This will allow you to decompose complex calculations into a few simple ones, which provides a lot of room for creativity.

Here is a small example of what I am talking about. In the workbook below, I am trying to display a formatted ALERT message if the price changed by more than 20%.

We've got four columns: PREVIOUS (previous price), CURRENT (current price), % (change percentage), and Result, which tells us whether we should or should not send a notification (ALERT).

Now, here's how it works. Each Excel workbook is initially a set of unlinked cells; once there are any dependencies, however, they become linked. This allows us to create a directed acyclic graph, the nodes of which can be both constants and functions. As a result, each change in thenodes leads to a complete recalculation in all other graph parts that depend on thosenodes.

There is a programming pattern called dataflow programming that basically represents a program as a set of such graphs. Many development trends and technologies, such as TensorFlow, actor model, or reactive programming, are actually based on this pattern and related ideas.

Let's take a simple graph for example:

It has multiple nodes containing values, and some nodes containing operations. As a result, we have an expression represented as a tree. Now, getting back to the question of how I regard the expression trees in the context of this particular task, here is the answer:

Since our task consists in implementing a simple feature similar to User Defined Functions in Microsoft Excel, the expression trees technology is for me a directed acyclic graph with certain operations and values in its nodes; i.e., expression trees are a way to create such functions and manage them moving forward.

An additional advantage of using expression trees is the ability to compile this graph into a function, which will significantly reduce costs when using it. If this technology were missing in .NET, we would most likely solve this task by creating a simple graph that would be a user defined function.

Solution

I will create a set of simple rules to use as an example and, based on those rules, I will describe how the data gets processed.

The minimum ask price of aluminium on the London Metal Exchange (LME) exceeded a certain value.

price.Symbol == "LME-AL" && price.Ask > 20 

The average copper or gold price on the London Metal Exchange (LME) declined below a certain value.

(price.Symbol == "LME-CO" || price.Symbol == "LME-GO") && price.Mid < 14 

Prices for specific metals changed on the Chicago Mercantile Exchange.

price.Symbol == "CME-CO" || price.Symbol == "CME-ZN"
  || price.Symbol == "CME-AL"|| price.Symbol == "CME-NI" 

Please note: The symbol names are random and used for information purposes only.

Now, we can see how a simple expression we want to get as a result will look like:

// ... price.Symbol == "LME-AL" && price.Ask > 20 
System.Linq.Expressions.BinaryExpression binaryExpression 
     = System.Linq.Expressions.Expression.MakeBinary( 
         System.Linq.Expressions.ExpressionType.And, 
         System.Linq.Expressions.Expression.MakeBinary( 
             System.Linq.Expressions.ExpressionType.Equal, 
             System.Linq.Expressions.Expression.Constant({price.Symbol}), 
             System.Linq.Expressions.Expression.Constant("LME-AL")), 
         System.Linq.Expressions.Expression.MakeBinary( 
             System.Linq.Expressions.ExpressionType.GreaterThan, 
             System.Linq.Expressions.Expression.Constant({price.Ask}), 
             System.Linq.Expressions.Expression.Constant("20"))); 

Even in this static description, one may clearly see the tree structure; this should also be applicable to the structure of the data we get from the user. Here are the examples for the three rules above:

{ 
//... metadata 
      "condition" : { 
          "operator" : "And", 
          "conditions" : [ 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "LME-AL" 
             }, 
             { 
                 "fact" : "Ask", 
                 "operator" : "GT", 
                 "value" : "20" 
             } 
         ] 
     } 
} 

{ 
//... metadata 
      "condition" : { 
          "operator" : "And", 
          "conditions" : [ 
             { 
                  "operator" : "OR", 
                  "conditions" : [ 
                     { 
                          "fact" : "Symbol", 
                          "operator" : "EQ", 
                          "value" : "LME-CO" 
                     }, 
                     { 
                          "fact" : "Symbol", 
                          "operator" : "EQ", 
                          "value" : "LME-GO" 
                     } 
                  ] 
             }, 
             { 
                 "fact" : "Mid", 
                 "operator" : "LT", 
                 "value" : "14" 
             } 
         ] 
     } 
}

{ 
//... metadata 
      "condition" : { 
          "operator" : "OR", 
          "conditions" : [ 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-CO" 
             }, 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-ZN" 
             }, 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-AL" 
             }, 
             { 
                 "fact" : "Symbol", 
                 "operator" : "EQ", 
                 "value" : "CME-NI" 
             } 
         ] 
     } 
} 

The examples of documents above show we will be using various expression subtypes so as to code the rules. Thus, we create a specific class hierarchy, for which we also should define a common set of operations. In order to separate the operation layer from the data layer, such operations must be part of other classes; at the same time, however, we need to have a way to determine at run time which specific operation we need to perform for which specific type. This can be done with the double dispatch mechanism, i.e. a way to call a class virtual method based on both the heir type and the argument or input data type.

To separate the code in such a way, we will be using the Visitor pattern.

Let's start with a simple thing: defining the base class and subclasses for the rules (expressions) based on the standard Expression and ExpressionType classes from the System.Linq.Expressions namespace.

public abstract class Condition
{
  public ExpressionType Operator { get; set; }
  public abstract Expression Accept(IConditionExpressionVisitor visitor);
}

// ...
public sealed class BinaryCondition : Condition
{
	public string Fact { get; set; }
  public string Value { get; set; }
  public override Expression Accept(IConditionExpressionVisitor visitor)
  {
  	return visitor.Visit(this);
  }
} 
 
// ... 
public sealed class CompositeCondition : Condition
{
	public IEnumerable<Condition> Conditions { get; set; }
  public override Expression Accept(IConditionExpressionVisitor visitor)
  {
  	return visitor.Visit(this);
  }
} 

Now let us see how the compilation process looks like. I like to use code metaphors that have something to do with the reality. For example, in this case, I really like the idea of creating a compiler that is similar to a real compiler for an existing programming language. Of course, it is going to be simplified, this is what the metaphor is all about.

The compilation process, in our case, will get broken down into: 1. translation and 2. compilation.

As the first step in this simplified algorithm, the translation process gets implemented using the Visitor pattern:

public interface IConditionExpressionVisitor
{
  Expression Visit(CompositeCondition condition);
  Expression Visit(BinaryCondition condition);
}

internal partial class ConditionTranslator : IConditionExpressionVisitor
{
	private readonly BinaryConditionTranslator _binaryTranslator;
  private readonly CompositeConditionTranslator _compositeTranslator;
  
  internal ConditionTranslator(Type modelType, ParameterExpression parameter)
  {
  	_binaryTranslator = new BinaryConditionTranslator(modelType, parameter);
    _compositeTranslator = new CompositeConditionTranslator(this);
  }
  
  internal Expression Translate(Condition condition)
  {
  	return condition.Accept(this);
  }
  
  Expression IConditionExpressionVisitor.Visit(CompositeCondition condition)
  	=> _compositeTranslator.Translate(condition);
  
  Expression IConditionExpressionVisitor.Visit(BinaryCondition condition)
  	=> _binaryTranslator.Translate(condition);
} 

internal partial class ConditionTranslator
{
  private class BinaryConditionTranslator
  {
    private readonly Type _modelType;
    private readonly ParameterExpression _parameter;
    
    internal BinaryConditionTranslator(Type modelType, ParameterExpression parameter)
    {
      _modelType = modelType;
      _parameter = parameter;
    }
    
    internal Expression Translate(BinaryCondition condition)
    {
      if (string.IsNullOrWhiteSpace(condition.Fact))
      {
        throw new ArgumentException($"'{nameof(BinaryCondition)}.{nameof(condition.Fact)}' can not be null or empty.");
      }
      
      if (condition.Value == null)
      {
        throw new ArgumentException($"'{nameof(BinaryCondition)}.{nameof(condition.Value)}' can not be null.");
      }
      
      if (!FactIsPresented())
      {
        throw new ArgumentException($"Fact '{condition.Fact}' is not available.");
      }
      
      return TranslateToBinary();
      
      bool FactIsPresented() => _modelType.GetProperty(condition.Fact) != null;
      
      Expression TranslateToBinary()
      {
        try
        {
          PropertyInfo property = _modelType.GetProperty(condition.Fact);
          MemberExpression left = Expression.Property(_parameter, condition.Fact);
          
          Expression right = property.PropertyType.GetGenericArguments().Any()
            ? (Expression)Expression.Convert(Expression.Constant(
            	Convert.ChangeType(
                condition.Value, 
                property.PropertyType.GetGenericArguments().First(),
                CultureInfo.InvariantCulture)), property.PropertyType)
            : Expression.Constant(
              Convert.ChangeType(
                condition.Value,
                property.PropertyType,
                CultureInfo.InvariantCulture));
          
          return Expression.MakeBinary(condition.Operator, left, right);
        }
        catch (Exception ex)
        {
          throw new InvalidOperationException("Rule compilation exception", ex);
        }
      }
    }
  }
}

internal partial class ConditionTranslator
{
  private class CompositeConditionTranslator
  {
    private readonly ConditionTranslator _parent;
    
    internal CompositeConditionTranslator(ConditionTranslator translator)
    {
      _parent = translator;
    }
    
    internal Expression Translate(CompositeCondition condition)
    {
      List<Exception> exceptions = new List<Exception>();
      Expression[] translated = condition.Conditions.Select(child => Translate(child)).ToArray();
      
      if (exceptions.Any())
      {
        throw new InvalidOperationException("Rule compilation exception", new AggregateException(exceptions));
      }
      
      return translated.Aggregate((left, right) => Expression.MakeBinary(condition.Operator, left, right));
      
      Expression Translate(Condition condition)
      {
        try
        {
          return _parent.Translate(condition);
        }
        catch (AggregateException ex)
        {
          foreach (Exception innerEx in ex.InnerExceptions)
          {
            exceptions.Add(innerEx);
          }
          
          return Expression.Empty();
        }
        catch (Exception ex)
        {
          exceptions.Add(ex);
          return Expression.Empty();
        }
      }
   	}
  }
} 

This will make the compiler interface much simpler.

public interface IConditionCompiler<TModel>
{
	Func<TModel, bool> Compile(Condition condition);
} 

Now, here comes the compiler.

public class ConditionCompiler<TModel> : IConditionCompiler<TModel>
{
	private readonly Type _modelType;
  private readonly ParameterExpression _parameter;
  private readonly ConditionTranslator _translator;
  
  public ConditionCompiler()
  {
  	_modelType = typeof(TModel);
    _parameter = Expression.Parameter(_modelType);
    _translator = new ConditionTranslator(_modelType, _parameter);
  }
  
  public Func<TModel, bool> Compile(Condition condition)
  	=> Expression.Lambda<Func<TModel, bool>>(
        _translator.Translate(condition),
        _parameter)
      .Compile();
}

What is actually happening here? Long story short, we create a compiler which can be parameterized with the model type we are using. Next, we get an expression and iterate over each block recursively, checking whether we can compile it. We also check the type and fields of the model for matches.

Here is a small example of how this code can be tested:

var condition = new CompositeCondition
{
	Operator = ExpressionType.And,
  Conditions = new Condition[]
  {
  	new BinaryCondition
    {
    	Operator = ExpressionType.Equal,
      Fact = "Symbol",
      Value = "LME-AL"
    },
    new BinaryCondition
    {
    	Operator = ExpressionType.GreaterThan,
      Fact = "Ask",
      Value = "20"
    },
  }
};

Func<PriceModel, bool> rule = _priceRuleCompiler.Compile(condition); 

var incomingPriceUpdate = new PriceModel { Symbol = "LME-AL", Ask = 42 };
var shouldNotify = rule(incomingPriceUpdate);
if (shouldNotify)
{
  Console.WriteLine("PASSED. Notification is sent");
}

incomingPriceUpdate = new PriceModel { Symbol = "CME-AL", Ask = 42 };
var shouldNotNotify = rule(incomingPriceUpdate) is false;
if (shouldNotNotify)
{
  Console.WriteLine("PASSED. Notification has not been sent");
} 

For those interested, here are some figures and stats.

The compilation and execution time of a single rule is given in milliseconds for Intel i7-8550U, 16GB RAM.

Let's now talk a bit more about code extensibility.

Apart simple Boolean operations, you can add class method calls and compiler validation based on system reflection; for instance, you can forbid compiling some Boolean  operations for certain types of fields, or, to be more realistic, prevent compiling calls to some functions. All extensions can be added to the class constructor as dependencies or to the model, as metadata.

Tech stack and use in production

As we are active Azure users, our compiler is integrated into the service and deployed in a Service Fabric cluster. In order to store custom configurations of business rules, we use Cosmos DB, while the notification sending feature is implemented through a queue in the Service Bus.

The simplified workflow is as follows: there are two queues to which the service is connected, and a collection where the rules are stored. We use the first queue to receive updates from data sources, while the second is for sending notifications. We separated the compilation and execution phases in order to somewhat boost the performance. When started, the service requests all the rules from the storage, compiles them, and saves them to the internal cache. As soon as the user changes the existing rule or adds a new one, we get updates through the Cosmos DB Change Feed and change the cache value. This allows us to always have the cache updated and guarantee that a notification is sent to the user. Each time we receive a notification from the queue, we look through the cache, applying each rule; depending on the result, we either send a notification to the notification queue, or move further as per the workflow.

Our app is not highly loaded, as we have up to 100,000 active users, which is why simple caching of the compiled rules is more than enough for us. I am pretty sure, however, that this would be fine even in case of a high load app. For instance, one may use sharding by adding more nodes to the service and save only a part of the common rules in each node. With the Azure ServiceBus topics, one can also route updates from the sources to a specific node. Finally, one may use vertical scaling by increasing the number of threads in order to get a performance boost both while executing the rules and while compiling them.

Conclusion

This approach isolates the logic of creating rules from their direct use. The model objects are known only at the stage of compiling the rules, while no specific types matter when it comes to the compiler itself. This yields undeniable advantages: for example, these two processes can be placed into different services and used independently, which is exactly what we did in our particular case.

This actually concludes my article. Thank you!