A DSL rule engine

In this 2 part series we will discuss the evolution of Discount compute engines across 3 software stacks. In the first part of the story I would like to share experiences from my days where I tried to build an all powerful DSL (Domain specific language) parser to power a configurable discount computation engine.

In the second part we will see the current implementation of the same engine with more advanced capabilities.

Brief introduction to DSL

DSL rule engines have been around for a long time in the technology industry. They can be found in gaming engines, salary calculators, insurance calculators, embedded devices etc. They are useful in
- Modelling complex domains
- Dynamically modifying behavior of systems without taking the performance hit by adopting interpreted languages.
- Abstracting the implementation of rules (in terms of underlying runtime language) from domain experts who define the rules in DSL.

In the context of redBus, we needed a way to encapsulate a set of frequently user parameters for computing applicable discount for a user transaction and give them to business operations team to define rules using them. This would give freedom to business team and at the same time remove dependency on developers to implement rules in code.

What was before DSL

At redBus we have discount coupons which need to be validated at the time of checkout. As the rules of computation change very frequently we needed a way to configure arbitrarily complex rules with out the need for compilation and deployment.

The transaction management system at redBus where all the orders are created was written in Java. Naturally the best option to implement coupon code functionality was to write them in Groovy. This approach while gave a lot of flexibility in defining coupon logic, it had a few drawbacks like
- It needed programming experience to create a coupon code
- It was slow often taking 500 ms to execute simple mathematical calculations
- And somethings I can’t remember after 10 years

So as it happens in many startups, instead of trying to optimize the existing system I decided to rewrite it (common I was 10 years younger and all night coding was still fun).

A great new idea

With the blessings of my manager I set out to write an all powerful yet easy to use rule engine which can be configured even by business operations team. At this time all thoughts were pointing to coming up with a DSL specification in which business people can define rules and those will be cross-compiled to C#. The decision to go with C# was taken as the we had plans to take the responsibility of offer configuration and calculation out of transaction management system and put it into API layer which was in .NET.

What started as an experiment in T4 text templates few weeks of later pivoted to become a parser combinator for DSL. After a few days of googling I found this little gem of a library called sparche (https://github.com/sprache/Sprache) which can be used for writing writing parser combinators in C#.

In their own words

“Sprache is a simple, lightweight library for constructing parsers directly in C# code. It doesn’t compete with “industrial strength” language workbenches — it fits somewhere in between regular expressions and a full-featured toolset like ANTLR.”

Sprache can be used like

Parser<string> identifier =
    from leading in Parse.WhiteSpace.Many()
    from first in Parse.Letter.Once().Text()
    from rest in Parse.LetterOrDigit.Many().Text()
    from trailing in Parse.WhiteSpace.Many()
    select first + rest;
var id = identifier.Parse(" abc123  ");
Assert.AreEqual("abc123", id);

So I set out to achieve the following

1. Come up with a minimalist DSL
2. Create a cross-compiler to C#
3. Create a GUI editor for rule
4. Create a library to integrate rules into API codebase

Main components of the system interacted in the following way

A brief explanation of the above diagram;

1. Rule-xyz: This is the rule definition written in DSL
2. Parser: The parser validates the DSL rule and creates an in-memory AST (Abstract syntax tree)
3. AST walker: The AST generated above is passed on to a AST walker which emits the equivalent C# code.
4. C# compiler: C# code generated by AST walker is complied to a .NET assembly and added to the cache
5. API: API layer hosts the cache. When a specific discount code is requested corresponding .NET assembly is loaded and rule instance is created.
6. Apply function: This is the entry point for the logic. Before calling this API layer adds the variables such as UserID, Channel, journey details to the rule context and passes it to the Apply method. Rule output is returned in a dictionary which is also passed a input to Apply method.

A typical rule written in DSL looked like this

INIT
    $rtcarr = {2020,3030,4040,8065,7115,3953,10283};
    $UDF_1 = "2016001";
ENDINIT
IF( Stringify($salesChannel) != "MOBILEAPP") THEN
    BEGIN
    SetOffer("", "OfferDenied", "Sorry! offer applicable for mobile transactions only.", 0);
    END
ELSEIF($rtcarr.Contains(ConvertToNumber($OperatorId)) == true) THEN
    BEGIN
    SetOffer("", "OfferDenied", "This offer is not applicable to Govt. RTCs.", 0);
    END
ELSEIF( GetCountOfPromtionsUsed($mobileNo, $emailId, $UDF_0, $OfferCode, $UDF_1) > 1) THEN
    BEGIN
    SetOffer("", "OfferDenied", "This offer has been already used once for this user.", 0);
    END
ELSEIF( GetAppTktsCountForOfferByDeviceId($deviceId,$OfferCode) > 1) THEN
    BEGIN
    SetOffer("", "OfferDenied", "This offer has been already used once by the user.", 0);
    END
ELSE THEN
    BEGIN
    SetOffer("RBCD100", "OfferApproved", "Offer successfully applied.", 100);
    END
ENDIF

DSL scope definition

Few restrictions were applied to make language simpler and parser easier to develop;
- All variable declarations to go in INIT block
- No support for FUNCTION definition, but input context can have both variables and functions added to it
- BEGIN and END signify a block of statements
- No type checking
- Only IF-ELSE, IF-ELSE IF constructs are supported
- .(dot) operator to be directly in-lined to output code to allow dynamic dispatching for native .NET types.

With a little bit of extra effort I was able to add support to do nesting of blocks and FOREACH loop construct.

The whole DSL parser was constructed using the parsers for these basic types

1. Statements: These represent the part of the logic which either modify the state of the context or modify the flow of the program. Examples of statements include Assignments and IF construct.
2. Expressions: These represent the set of commands which do not have any side effect but generate a value which can be used for assignments and comparison or just be thrown away. Examples of expressions include Arithmetic operations, Boolean conditions, Literal values and Function calls.
3. Statement blocks: The program at it highest level is a linked list of statement blocks and program at execution time walks from one block to another in a sequential manner. Each block’s logic is represented by a linked list of statements (which can be statement blocks themselves) which are written between the BEGIN and END markers.
4. IF-ELSE, IF-ELSEIF, FOREACH blocks: These are special case of statement blocks whose entry is guarded by BOOLEAN expressions
5. Rval and Lval: It was important to distinguish between the types of values which can be assigned to and which can not be assigned to. Examples of non assignable values include function call expressions and literals.
6. The PROGRAM: This is the top level parser which calls other parsers depending on the definition of the rule.

And for the brave and the patient who have been with me so far, this is the class hierarchy

Conclusion

DSL implementation of the discount calculation brought down the computation time from 500 ms to 2 ms. Also the IDE helped business people to build very expressive rules. A few lessons were also learnt (the hard way) on how to balance expressiveness with easier learning curve so as to not create overly complicated and inefficient rules.

DSL are a great way to build complex business rules from simple components. In addition to expressiveness and dynamic definition aspects, DSL also give an abstraction from implementation which enables optimizations and maintainability.

Particularly in the case of redBus the API layer can be rewritten in any other language and all the existing business rules can be ported by plugging in a different compiler to the output of the AST walker.

As time passed many more enhancements were demanded from the Discounting engine which lead to next iteration which we will covered in the next part of the story.