How to Implement a Rule Engine

Guidelines for implementing a rule engine

See this post for argument for implementing your own:

Rules Engine - pros and cons

mainly the problem centers around the anemic data model anti-pattern. as described here:

http://martinfowler.com/bliki/AnemicDomainModel.html

How you should implement depends very much on the requirements but generally important points to consider when designing your own include.

• Make the ability to add rules dynamic. So you don't have to shut down the system to edit rules.
• Match the rules syntax to the appropriate user level, don't expect a secretary to be writing SQL.
• Take advantage of your domain knowledge to implement your domain models which you will run your rules against.
• Drools is a good bit of software, try to learn lessons from how that was implemented.
• Try to modularize your rules engine so it functions independent of any business process tools you might be using

How to implement a rule engine?

This snippet compiles the Rules into fast executable code (using Expression trees) and does not need any complicated switch statements:

(Edit : full working example with generic method)

public Func<User, bool> CompileRule(Rule r)
{
    var paramUser = Expression.Parameter(typeof(User));
    Expression expr = BuildExpr(r, paramUser);
    // build a lambda function User->bool and compile it
    return Expression.Lambda<Func<User, bool>>(expr, paramUser).Compile();
}

You can then write:

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

// compile the rules once
var compiledRules = rules.Select(r => CompileRule(r)).ToList();

public bool MatchesAllRules(User user)
{
    return compiledRules.All(rule => rule(user));
}

Here is the implementation of BuildExpr:

Expression BuildExpr(Rule r, ParameterExpression param)
{
    var left = MemberExpression.Property(param, r.MemberName);
    var tProp = typeof(User).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 == 21'
        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);
    }
}

Note that I used 'GreaterThan' instead of 'greater_than' etc. - this is because 'GreaterThan' is the .NET name for the operator, therefore we don't need any extra mapping.

If you need custom names you can build a very simple dictionary and just translate all operators before compiling the rules:

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

The code uses the type User for simplicity. You can replace User with a generic type T to have a generic Rule compiler for any types of objects. Also, the code should handle errors, like unknown operator name.

Note that generating code on the fly was possible even before the Expression trees API was introduced, using Reflection.Emit. The method LambdaExpression.Compile() uses Reflection.Emit under the covers (you can see this using ILSpy).

creating a simple rule engine in java

Implementing a simple rule-based evaluation system in Java isn't that hard to achieve. Probably the parser for the expression is the most complicated stuff. The example code below uses a couple of patterns to achieve your desired functionality.

A singleton pattern is used to store each available operation in a member map. The operation itself use a command pattern to provide flexible extensibility while the respective action for a valid expression does make use of the dispatching pattern. Last bust not least, a interpreter pattern is used for validating each rule.

An expression like presented in your example above consists of operations, variables and values. In reference to a wiki-example everything that can be declared is an Expression. The interface therefore looks like this:

import java.util.Map;

public interface Expression
{
    public boolean interpret(final Map<String, ?> bindings);
}

While the example on the wiki-page returns an int (they implement a calculator), we only need a boolean return value here to decide if a expression should trigger an action if the expression evaluates to true.

An expression can, as stated above, be either an operation like =, AND, NOT, ... or a Variable or its Value. The definition of a Variable is enlisted below:

import java.util.Map;

public class Variable implements Expression
{
    private String name;

    public Variable(String name)
    {
        this.name = name;
    }

    public String getName()
    {
        return this.name;
    }

    @Override
    public boolean interpret(Map<String, ?> bindings)
    {
        return true;
    }
}

Validating a variable name does not make that much sense, therefore true is returned by default. The same holds true for a value of a variable which is kept as generic as possible on defining a BaseType only:

import java.util.Map;

public class BaseType<T> implements Expression
{
    public T value;
    public Class<T> type;

    public BaseType(T value, Class<T> type)
    {
        this.value = value;
        this.type = type;
    }

    public T getValue()
    {
        return this.value;
    }

    public Class<T> getType()
    {
        return this.type;
    }

    @Override
    public boolean interpret(Map<String, ?> bindings)
    {
        return true;
    }

    public static BaseType<?> getBaseType(String string)
    {
        if (string == null)
            throw new IllegalArgumentException("The provided string must not be null");

        if ("true".equals(string) || "false".equals(string))
            return new BaseType<>(Boolean.getBoolean(string), Boolean.class);
        else if (string.startsWith("'"))
            return new BaseType<>(string, String.class);
        else if (string.contains("."))
            return new BaseType<>(Float.parseFloat(string), Float.class);
        else
            return new BaseType<>(Integer.parseInt(string), Integer.class);
    }
}

The BaseType class contains a factory method to generate concrete value types for a specific Java type.

An Operation is now a special expression like AND, NOT, =, ... The abstract base class Operation does define a left and right operand as the operand can refer to more than one expression. F.e. NOT probably only refers to its right-hand expression and negates its validation-result, so true turn into false and vice versa. But AND on the other handside combines a left and right expression logically, forcing both expression to be true on validation.

import java.util.Stack;

public abstract class Operation implements Expression
{
    protected String symbol;

    protected Expression leftOperand = null;
    protected Expression rightOperand = null;

    public Operation(String symbol)
    {
        this.symbol = symbol;
    }

    public abstract Operation copy();

    public String getSymbol()
    {
        return this.symbol;
    }

    public abstract int parse(final String[] tokens, final int pos, final Stack<Expression> stack);

    protected Integer findNextExpression(String[] tokens, int pos, Stack<Expression> stack)
    {
        Operations operations = Operations.INSTANCE;

        for (int i = pos; i < tokens.length; i++)
        {
            Operation op = operations.getOperation(tokens[i]);
            if (op != null)
            {
                op = op.copy();
                // we found an operation
                i = op.parse(tokens, i, stack);

                return i;
            }
        }
        return null;
     }
}

Two operations probably jump into the eye. int parse(String[], int, Stack<Expression>); refactors the logic of parsing the concrete operation to the respective operation-class as it probably knows best what it needs to instantiate a valid operation. Integer findNextExpression(String[], int, stack); is used to find the right hand side of the operation while parsing the string into an expression. It might sound strange to return an int here instead of an expression but the expression is pushed onto the stack and the return value here just returns the position of the last token used by the created expression. So the int value is used to skip already processed tokens.

The AND operation does look like this:

import java.util.Map;
import java.util.Stack;

public class And extends Operation
{    
    public And()
    {
        super("AND");
    }

    public And copy()
    {
        return new And();
    }

    @Override
    public int parse(String[] tokens, int pos, Stack<Expression> stack)
    {
        Expression left = stack.pop();
        int i = findNextExpression(tokens, pos+1, stack);
        Expression right = stack.pop();

        this.leftOperand = left;
        this.rightOperand = right;

        stack.push(this);

        return i;
    }

    @Override
    public boolean interpret(Map<String, ?> bindings)
    {
        return leftOperand.interpret(bindings) && rightOperand.interpret(bindings);
    }
}

In parse you probably see that the already generated expression from the left side is taken from the stack, then the right hand side is parsed and again taken from the stack to finally push the new AND operation containing both, the left and right hand expression, back onto the stack.

NOT is similar in that case but only sets the right hand side as described previously:

import java.util.Map;
import java.util.Stack;

public class Not extends Operation
{    
    public Not()
    {
        super("NOT");
    }

    public Not copy()
    {
        return new Not();
    }

    @Override
    public int parse(String[] tokens, int pos, Stack<Expression> stack)
    {
        int i = findNextExpression(tokens, pos+1, stack);
        Expression right = stack.pop();

        this.rightOperand = right;
        stack.push(this);

        return i;
    }

    @Override
    public boolean interpret(final Map<String, ?> bindings)
    {
        return !this.rightOperand.interpret(bindings);
    }    
}

The = operator is used to check the value of a variable if it actually equals a specific value in the bindings map provided as argument in the interpret method.

import java.util.Map;
import java.util.Stack;

public class Equals extends Operation
{      
    public Equals()
    {
        super("=");
    }

    @Override
    public Equals copy()
    {
        return new Equals();
    }

    @Override
    public int parse(final String[] tokens, int pos, Stack<Expression> stack)
    {
        if (pos-1 >= 0 && tokens.length >= pos+1)
        {
            String var = tokens[pos-1];

            this.leftOperand = new Variable(var);
            this.rightOperand = BaseType.getBaseType(tokens[pos+1]);
            stack.push(this);

            return pos+1;
        }
        throw new IllegalArgumentException("Cannot assign value to variable");
    }

    @Override
    public boolean interpret(Map<String, ?> bindings)
    {
        Variable v = (Variable)this.leftOperand;
        Object obj = bindings.get(v.getName());
        if (obj == null)
            return false;

        BaseType<?> type = (BaseType<?>)this.rightOperand;
        if (type.getType().equals(obj.getClass()))
        {
            if (type.getValue().equals(obj))
                return true;
        }
        return false;
    }
}

As can be seen from the parse method a value is assigned to a variable with the variable being on the left side of the = symbol and the value on the right side.

Moreover the interpretation checks for the availability of the variable name in the variable bindings. If it is not available we know that this term can not evaluate to true so we can skip the evaluation process. If it is present, we extract the information from the right hand side (=Value part) and first check if the class type is equal and if so if the actual variable value matches the binding.

As the actual parsing of the expressions is refactored into the operations, the actual parser is rather slim:

import java.util.Stack;

public class ExpressionParser
{
    private static final Operations operations = Operations.INSTANCE;

    public static Expression fromString(String expr)
    {
        Stack<Expression> stack = new Stack<>();

        String[] tokens = expr.split("\\s");
        for (int i=0; i < tokens.length-1; i++)
        {
            Operation op = operations.getOperation(tokens[i]);
            if ( op != null )
            {
                // create a new instance
                op = op.copy();
                i = op.parse(tokens, i, stack);
            }
        }

        return stack.pop();
    }
}

Here the copy method is probably the most interesting thing. As the parsing is rather generic, we do not know in advance which operation is currently processed. On returning a found operation among the registered ones results in a modification of this object. If we only have one operation of that kind in our expression this does not matter - if we however have multiple operations (f.e. two or more equals-operations) the operation is reused and therefore updated with the new value. As this also changes previously created operations of that kind we need to create a new instance of the operation - copy() achieves this.

Operations is a container which holds previously registered operations and maps the operation to a specified symbol:

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public enum Operations
{
    /** Application of the Singleton pattern using enum **/
    INSTANCE;

    private final Map<String, Operation> operations = new HashMap<>();

    public void registerOperation(Operation op, String symbol)
    {
        if (!operations.containsKey(symbol))
            operations.put(symbol, op);
    }

    public void registerOperation(Operation op)
    {
        if (!operations.containsKey(op.getSymbol()))
            operations.put(op.getSymbol(), op);
    }

    public Operation getOperation(String symbol)
    {
        return this.operations.get(symbol);
    }

    public Set<String> getDefinedSymbols()
    {
        return this.operations.keySet();
    }
}

Beside the enum singleton pattern nothing really fancy here.

A Rule now contains one or more expressions which on evaluation may trigger a certain action. The rule therefore needs to hold the previously parsed expressions and the action which should be triggered in success case.

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class Rule
{
    private List<Expression> expressions;
    private ActionDispatcher dispatcher;

    public static class Builder
    {
        private List<Expression> expressions = new ArrayList<>();
        private ActionDispatcher dispatcher = new NullActionDispatcher();

        public Builder withExpression(Expression expr)
        {
            expressions.add(expr);
            return this;
        }

        public Builder withDispatcher(ActionDispatcher dispatcher)
        {
            this.dispatcher = dispatcher;
            return this;
        }

        public Rule build()
        {
            return new Rule(expressions, dispatcher);
        }
    }

    private Rule(List<Expression> expressions, ActionDispatcher dispatcher)
    {
        this.expressions = expressions;
        this.dispatcher = dispatcher;
    }

    public boolean eval(Map<String, ?> bindings)
    {
        boolean eval = false;
        for (Expression expression : expressions)
        {
            eval = expression.interpret(bindings);
            if (eval)
                dispatcher.fire();
        }
        return eval;
    }
}

Here a building pattern is used just to be able to add multiple expression if desired for the same action. Furthermore, the Rule defines a NullActionDispatcher by default. If an expression is evaluated successfully, the dispatcher will trigger a fire() method, which will process the action which should be executed on successful validation. The null pattern is used here to avoid dealing with null values in case no action execution is required as only a true or false validation should be performed. The interface therefore is simple too:

public interface ActionDispatcher
{
    public void fire();
}

As I do not really know what your INPATIENT or OUTPATIENT actions should be, the fire() method only triggers a System.out.println(...); method invocation:

public class InPatientDispatcher implements ActionDispatcher
{
    @Override
    public void fire()
    {
        // send patient to in_patient
        System.out.println("Send patient to IN");
    }
}

Last but not least, a simple main method to test the behavior of the code:

import java.util.HashMap;
import java.util.Map;

public class Main 
{
    public static void main( String[] args )
    {
        // create a singleton container for operations
        Operations operations = Operations.INSTANCE;

        // register new operations with the previously created container
        operations.registerOperation(new And());
        operations.registerOperation(new Equals());
        operations.registerOperation(new Not());

        // defines the triggers when a rule should fire
        Expression ex3 = ExpressionParser.fromString("PATIENT_TYPE = 'A' AND NOT ADMISSION_TYPE = 'O'");
        Expression ex1 = ExpressionParser.fromString("PATIENT_TYPE = 'A' AND ADMISSION_TYPE = 'O'");
        Expression ex2 = ExpressionParser.fromString("PATIENT_TYPE = 'B'");

        // define the possible actions for rules that fire
        ActionDispatcher inPatient = new InPatientDispatcher();
        ActionDispatcher outPatient = new OutPatientDispatcher();

        // create the rules and link them to the accoridng expression and action
        Rule rule1 = new Rule.Builder()
                            .withExpression(ex1)
                            .withDispatcher(outPatient)
                            .build();

        Rule rule2 = new Rule.Builder()
                            .withExpression(ex2)
                            .withExpression(ex3)
                            .withDispatcher(inPatient)
                            .build();

        // add all rules to a single container
        Rules rules = new Rules();
        rules.addRule(rule1);
        rules.addRule(rule2);

        // for test purpose define a variable binding ...
        Map<String, String> bindings = new HashMap<>();
        bindings.put("PATIENT_TYPE", "'A'");
        bindings.put("ADMISSION_TYPE", "'O'");
        // ... and evaluate the defined rules with the specified bindings
        boolean triggered = rules.eval(bindings);
        System.out.println("Action triggered: "+triggered);
    }
}

Rules here is just a simple container class for rules and propagates the eval(bindings); invocation to each defined rule.

I do not include other operations as the post here is already way to long, but it should not be too hard to implement them on your own if you desire so. I furthermore did not include my package structure as you probably will use your own one. Furhtermore, I didn't include any exception handling, I leave that to everyone who is going to copy & paste the code :)

One might argue that the parsing should obviously happen in the parser instead of the concrete classes. I'm aware of that, but on the other hand on adding new operations you have to modify the parser as well as the new operation instead of only having to touch one single class.

Instead of using a rule based system a petri net or even a BPMN in combination with the open source Activiti Engine would be possible to achieve this task. Here the operations are already defined within the language, you only need to define the concrete statements as tasks which can be executed automatically - and depending on the outcome of a task (i.e. the single statement) it will proceed its way through the "graph". The modeling therefore is usually done in a graphical editor or frontend to avoid dealing with the XML nature of the BPMN language.

Method or pattern to implement a Business Rules Engine in a solution?

So, this is a bit of a rant, but I have yet to see a business rules engine work very well in a production environment. The only time I've seen them work well is when they are treated exactly like the code repository that they are replacing.

They need to follow a SDLC, going through requirements gathering, development (with engineers), QA, and finally promotion to production.

Rules engines are usually sold to business people as ways to bypass the cost of development, testing, and source-code-management. These systems usually fall apart in pretty short order. The rules are programming logic, the fact that they are loaded from a database somewhere instead of being loaded from a file system changes nothing. As programming logic, the people most suited to develop them are... programmers.

When business people try and write these things, they tend to get frustrated fairly quickly when the system doesn't keep them from making logic holes that the flow falls into. Things that programmers are used to thinking about.

It's really just a matter of fidelity. You are trading a high-fidelity programming language (java, c, python), for a low-fidelity language. You are not magically making the number of decision points smaller. You are just trying express them in a language that is necessarily more constrained. As you try and express your more complex problem in a low-fidelity language, you will end up creating a monster. With hundreds or thousands of rules daisy-chained together. With only one or two people able to make sense of it, it soon becomes a huge liability to the organization.

Maybe your company is different, but I've seen this happen a few times, and usually the only way out is to scrap and rebuild. I've seen business workflow engines that work fairly well. Things that just coordinate the lower level logic pieces in a fairly high-level way. But leaves all the real decision making to the lower level machinery. These too though, need to be kept in their place, and have viable promotion, qa etc.

Implementing a rules engine in Python

Do not invent yet another rules language.

Either use Python or use some other existing, already debugged and working language like BPEL.

Just write your rules in Python, import them and execute them. Life is simpler, far easier to debug, and you've actually solved the actual log-reading problem without creating another problem.

Imagine this scenario. Your program breaks. It's now either the rule parsing, the rule execution, or the rule itself. You must debug all three. If you wrote the rule in Python, it would be the rule, and that would be that.

"I think it would be difficult to filter the Python down to the point where the user couldn't inadvertently do some crazy stuff with the rules that was not intended."

This is largely the "I want to write a compiler" argument.

1) You're the primary user. You'll write, debug and maintain the rules. Are there really armies of crazy programmers who will be doing crazy things? Really? If there is any potential crazy user, talk to them. Teach Them. Don't fight against them by inventing a new language (which you will then have to maintain and debug forever.)

2) It's just log processing. There's no real cost to the craziness. No one is going to subvert the world economic system with faulty log handling. Don't make a small task with a few dozen lines of Python onto a 1000 line interpreter to interpret a few dozen lines of some rule language. Just write the few dozen lines of Python.

Just write it in Python as quickly and clearly as you can and move on to the next project.

---

Related Topics