creating a simple rule engine in java

Question

I am exploring different ways to create a simple business rule engine in Java. I need to present the client with a simple webapp that lets him configure a bunch of rules. A sample of rule base might look like this :

Here's example:

 IF (PATIENT_TYPE = "A" AND ADMISSION_TYPE="O")
 SEND TO OUTPATIENT
 ELSE IF PATIENT_TYPE = "B" 
 SEND TO INPATIENT

The rule engine is pretty simple, the final action could be just one of two actions, sending to inpatient or outpatient. The operators involved in an expression could be =,>,<,!= and logical operators between expressions are AND, OR and NOT.

I want to build a web application where user will write in a small script in a textarea, and I would evaluate the expression - this way, business rules are explained in simple English and business user has complete control on logic.

From the research I did so far, I came across, ANTLR and writing my own scripting language as possible options to solve this problem. I haven't explore options like Drools rules engine, because I have a feeling that it might be an overkill here. Have you had any experience in solving these kind of problems? If yes, how did you go about it?

Solution 1

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.

Solution 2

Basically... Don't do it

To understand why see:

1. http://thedailywtf.com/Articles/The_Customer-Friendly_System.aspx
2. http://thedailywtf.com/Articles/The-Mythical-Business-Layer.aspx
3. http://thedailywtf.com/Articles/Soft_Coding.aspx

I know it looks like a great idea from afar, but the business rules engine will invariably end up being harder to maintain, deploy and debug then the programming language it was written in - don't make up your own programming languages if you can help it.

I've personally been down that road in an ex firm and I've seen where it goes after a couple years (giant undebuggable scripts sitting in a database written in a language that came straight from a parallel dimension where God hates us that in the end never meet 100% of customer expectation because they're not as powerful as a proper programming language and at the same time they're far too convoluted and evil for devs to handle (never mind the client)).

I know there's a certain kind of client that's enamoured with the idea that they won't pay programmer hours for "business rule adaptations" and little understand that they'll be worse off in the end and to attract this kind of client you'll have to make something in this direction - but whatever you do don't invent something of your own.

There's a plethora of decent scripting languages that come with good tools (that don't require compilation, so can be uploaded dynamically etc) out there that can be slickly interfaced and called from Java code and take advantage of your implemented Java apis that you make available, see http://www.slideshare.net/jazzman1980/j-ruby-injavapublic#btnNext for example, Jython possibly too,

and when the client gives up writing these scripts you will be left with the happy duty of maintaining his failed legacy - make sure that that legacy is as painless as it can be.

Solution 3

I would suggest using something like Drools. Creating your own custom solution would be an overkill because you would have to debug it, and still provide functionality certainly less than the one provided by a rule engine like Drools. I understand that Drools has a learning curve, but I would not compare it with creating a custom language, or a custom solution...

In my opinion, in order for a user to write rules, he/she would have to learn something. While I suppose you could provide for a language simpler than the drools rule language, you would never capture all of his/her needs. Drools rule language would be simple enough for simple rules. Plus, you could provide him/her with a well formed documentation. If you plan to control the rules created by the end user and applied on the system, then perhaps it would be wiser to create a gui that would form the rules applied on drools.

Hope I helped!

Solution 4

You're setting yourself up for failure for two major reasons:

1. Parsing free text from the user is HARD.
2. Writing parsers in Java is somewhat cumbersome

Solving 1. is either going to push you into the fuzzy domain of NLP, for which you can use a tool like OpenNLP or something from that ecosystem. Because of the large amount of subtly different ways the user can write things down you will find your thinking skew towards a more formal grammar. Making this work will end you up in a DSL type solution, or you'll have to design your own programming language.

I've had reasonable results using Scala parser combinators to parse both natural language and more formalised grammars. The problems are the same, but the code you have to write to solve them is more readable.

Bottom line, even if you're thinking of a very simple rule language, you're going to find you underestimate the amount of scenario's you have to test for. NeilA is right to advice you to reduce the complexity by creating a proper UI for each type of rule. Don't try to be too generic, or it will blow up in your face.

Solution 5

If you're looking for something lighter than drools but with similar functionality you can check http://smartparam.org/ project. It allows storing parameters in properties files as well as in database.

View more solutions

Comments

[Admin]

stackoverflow.com/questions/4329858/… might help

[Joshua Taylor]

It seems overkill to spend time reimplementing something that already exists (even if you're not going to reuse all of what's available).

[Jay]

@JoshuaTaylor I am concerned about configuration effort here. Not every opensource framework would meet my requirement and there would be a bit of customization involved. At times, the time spent in customizing something could exceed building a simpler alternative.

[Jay]

to the gentleman who bothered to negative vote a simple question - could you please explain your intentions behind this noble act to this mediocre world!?

[torbinsky]

@Jay Counter to what a lot of others are saying, I think that if you decide that your DSL will be fairly simple and static, implementing it yourself might be better than using a heavy-weight framework. There are downsides to re-inventing the wheel, but there are also downsides to including heavy-weight frameworks. If you aren't familiar with them, they have ways of making you pay later. I am constantly reminded of this when I use various ORM's (cough Hibernate cough), for example. If what you provided is the entire DSL, you could parse the rules using an FSM.

[torbinsky]

@Jay Off top of my head, you could: Model this with an FSM. Transition between states for each token in your rules. If you encounter a token without a transition from your current state, then you can provide a human-friendly error message. As a start, you could follow a lot of online examples for building something like a postfix calculator. Basically, you would tokenize the text and then translate to the Java operator equivalents. You would ensure the logical structure is correct by assembling an expression tree. For more info, Google some keywords like "java expression evaluation postfix".

[bbozo]

@Jay, you probably got the downvote due to inner platform / softcoding antipatterns thedailywtf.com/Articles/Soft_Coding.aspx - it's best summed up in the sentence "Hm, I have a hammer, now I can build a tool to hammer some nails in" and a lot of advice you received here is rightfully to use your programming language to model your business logic thedailywtf.com/Articles/The-Mythical-Business-Layer.aspx

[bbozo]

I expanded my last comment into a full answer to better elaborate what I mean, stackoverflow.com/questions/20763189/…

[Jay]

thanks for your example, but I don't think it addresses my problem. My focus is to give the business user an easy way to specify rules. If else, and or not, and mathematical operators - this is just the domain.

[Jay]

I read Drools documentation. I am still not sure how to go about asking the user to write a Drools rule - that's not something a business user would understand. How do I make it simple for the end user?

[Candyfloss]

"How do I make it simple for the end user" - We faced a similar issue - we created a template spreadsheet (Decision table) that a user filled in with their rule criteria, this was then converted up into formal drools rules. Please see docs.jboss.org/drools/release/5.2.0.Final/drools-expert-docs‌​/… for more details and an example.

[torbinsky]

I completely agree that using a free-form text box is going to be error prone and would really complicate the error handling. Using components as @NeilA mentioned would be a good idea. You could still have a text area or something like that to output the final expression if you want to display it to the user in a textual form. Probably best not to have them edit that, though.

[torbinsky]

Drools looks impressive. However, I would caution @Jay to research it thoroughly and take the time to understand it before committing. I have seen many examples of devs "painting themselves into corners" with frameworks like this. It starts out great, you get your simple use case working. A few months down the line, you have your customer wanting something out yesterday, but you are stuck in a labyrinth of a framework. That being said, I am also a big fan of not re-inventing the wheel. The question is: is Drools a wheel, or is it a jet engine and OP really just needs a rubber wheel?

[Andrey Chaschev]

@Jay JIC you find it useful, an example of Groovy DSL: Log4j DSL. Martin Fowler is an advocate of the DSL and fluent interfaces, he even had written a book on them.

[flup]

I LOLed at the description of the scripts. +1

[Jay]

although, I found other answers to be just as useful as yours, and this probably is not the route I am going to take to fix my problem, I am awarding it to your answer mainly because it is elaborate and it shows that you have spent a lot of time and energy in putting it together. Thank you!

[jpmc26]

"I know there's a certain kind of client that's enamoured with the idea that they won't pay programmer hours for 'business rule adaptations' " I'm a dev. My job is to make good technical recommendations. Here's how I would phrase your recommendation in this answer: "That solution has historically proven to be less reliable and more error prone. It's not likely to save effort (and therefore money) in the long run. It will take longer and result in more bugs." That last sentence translates to, "more time (and money for that time) and more support dollars."

[mohdajami]

This is probably the most thorough answer I saw on SO. Good job.