This weekend I worked on the Factual language parser. I started with a brute-force recursive descent parser, but ended up with something more elegant. The final product expresses the intent better than the original code did. It is easier to maintain, and easier to extend. You can follow along with the changesets on Codeplex. Here’s how I did it.

Step 1: Make it work
The goal was to create a parser for a known language. It was not to create a framework for any language that you could throw at it. My constraints were well defined:

• Parse the Factual language
• Produce an Abstract Syntax Tree
• Work within an open source license

These constraints defined my solution. Since I am working on an open source project, I did not want to take a dependency upon a proprietary parser generator. And since I knew the language that I was parsing, I was able to choose parser patterns that fit that language.

It would be foolish to take on this project without knowing the theory of compiler design. I have seen too many ad-hoc parsers created by people who did not do their research. The mistakes that they made could have easily been avoided. “Make it work” does not mean throwing together the simplest thing that would work. It means think it through, but go straight at the problem. Persistence is no substitute for understanding.

Knowing the theory, I knew that my language as defined was LALR(4). It is unambiguous with a lookahead of only 4 tokens. I also knew that with a slight modification, I could transform it into an LALR(1) grammar. This kind of grammar is easily parsable using recursive descent.

I started with this unit test:

[TestMethod]
public void WhenNamespaceHasNoDot_NamepaceIsRecognized()
{
    Parser parser = new Parser(new StringReader("namespace GameModel;"));
    Namespace result = parser.Parse();
    Pred.Assert(result.Identifier, Is.EqualTo("GameModel"));
    Pred.Assert(result.LineNumber, Is.EqualTo(1));
}

I did not write this code, as some proponents of TDD would recommend:

public Namespace Parse()
{
    return new Namespace("GameModel", 1);
}

Instead, I wrote this:

public Namespace Parse()
{
    Consume();
    Namespace namespaceNode = MatchNamespace();
    return namespaceNode;
}

private Namespace MatchNamespace()
{
    Token namespaceToken = Expect(Symbol.Namespace, "Add a 'namespace' declaration.");

    if (Lookahead.Symbol != Symbol.Identifier)
        throw new FactualException("Provide a dotted identifier for the namespace.", Lookahead.LineNumber);
    string namespaceIdentifier = MatchDottedIdentifier();

    Expect(Symbol.Semicolon, "Terminate the namespace declaration with a semicolon.");

    return new Namespace(namespaceIdentifier, namespaceToken.LineNumber);
}

That first method would have made the test pass, but it represents none of the understanding of the problem space. I find it better to capture that understanding in code as soon as possible, rather than writing a foolish method that I will throw away later.

After getting it working, I had a suite of unit tests. Each subsequent step was performed while keeping that same test suite passing.

Step 2: Clean up the working code

It bothered me that MatchNamespace knew that MatchDottedIdentifier expected an Identifier. So I did a quick refactoring to move that knowledge closer to the right place.

private Namespace MatchNamespace()
{
    ...

    if (!StartOfDottedIdentifier())
        throw new FactualException("Provide a dotted identifier for the namespace.", Lookahead.LineNumber);
    string namespaceIdentifier = MatchDottedIdentifier();

    ...
}

private bool StartOfDottedIdentifier()
{
    return Lookahead.Symbol == Symbol.Identifier;
}

private string MatchDottedIdentifier()
{
    StringBuilder result = new StringBuilder();

    Token idenifier = Expect(Symbol.Identifier, "Begin with an identifier.");
    result.Append(idenifier.Value);

    ...
}

Step 3: Find the patterns

After cleaning the code in a similar way in several places, I noticed that there were Start and Match pairs for almost every rule. I compared this with my knowledge of parsers, and found that it is a valid generalization.

In an LALR(1) grammar, you can calculate the First and Follow sets of every production. The First set is the set of tokens that could appear at the beginning of the production. The Follow set is the set that could appear after the production has been reduced. I recognized that Start represented the First set. The Follow set is useful for generating the First set (First includes Follow if the production could be empty), but was not strictly required for my grammar.

Having discovered that pattern, I extracted a common interface (actually an abstract base class).

public abstract class Rule<T>
{
    public abstract bool Start(Symbol symbol);
    public abstract T Match(TokenStream tokenStream);
}

I implemented this interface with one derived class per production.

Step 4: Find the common intent

Several of the rules had a common structure. They each called a sequence of other rules in turn. Each time, they would check the Start, and then call Match. This commonality was not accidental. Each of these rules intended to represent a sequence. They only differed in which sequence, and what was done with it. So I factored out that intent.

public class RuleSequence3<T1, T2, T3, T> : Rule<T>
{
    private Rule<T1> _rule1;
    private Rule<T2> _rule2;
    private string _error2;
    private Rule<T3> _rule3;
    private string _error3;
    private Func<T1, T2, T3, T> _reduce;

    public RuleSequence3(Rule<T1> rule1, Rule<T2> rule2, string error2, Rule<T3> rule3, string error3, Func<T1, T2, T3, T> reduce)
    {
        _rule1 = rule1;
        _rule2 = rule2;
        _error2 = error2;
        _rule3 = rule3;
        _error3 = error3;
        _reduce = reduce;
    }

    public override bool Start(Symbol symbol)
    {
        return _rule1.Start(symbol);
    }

    public override T Match(TokenStream tokenStream)
    {
        T1 value1 = _rule1.Match(tokenStream);

        if (!_rule2.Start(tokenStream.Lookahead.Symbol))
            throw new FactualException(_error2, tokenStream.Lookahead.LineNumber);
        T2 value2 = _rule2.Match(tokenStream);

        if (!_rule3.Start(tokenStream.Lookahead.Symbol))
            throw new FactualException(_error3, tokenStream.Lookahead.LineNumber);
        T3 value3 = _rule3.Match(tokenStream);

        return _reduce(value1, value2, value3);
    }
}

Step 5: Express the intent

Now that rules can be built from the outside rather than coded from within, I had the opportunity to create a fluent interface. The code that uses this interface expresses the grammar of the language, rather than the steps required to parse it. The resulting code reads like a specification rather than an implementation.

// dotted_identifier -> identifier ("." identifier)*
// namespace_declaration -> "namespace" dotted_identifier ";"
var dottedIdentifier = Separated(
    Terminal(Symbol.Identifier),
    Symbol.Dot,
    identifier => new StringBuilder().Append(identifier.Value),
    (stringBuilder, identifier) => stringBuilder.Append(".").Append(identifier.Value));
var namespaceRule = Sequence(
    Terminal(Symbol.Namespace),
    dottedIdentifier, "Provide a dotted identifier for the namespace.",
    Terminal(Symbol.Semicolon), "Terminate the namespace declaration with a semicolon.",
    (namespaceToken, identifier, ignored) => new Namespace(identifier.ToString(), namespaceToken.LineNumber));

I find that this code is much easier to maintain and extend. The engineering of getting the parser right has been done once. Additional productions can take advantage of that engineering, so that simple mistakes are avoided. The goal was no reuse, but in the end I had created a reusable parser generator.

I might have been able to go straight there, but only at the risk of over engineering the solution. By refactoring my way from a working system toward an expression of intent, I was able to bring in just the theory that this particular problem requires. I know the limitations of my parser, and I can live within them.

How do we collaborate through software?

• The CAP Theorem – Eric Brewer
• Eventual Consistency – Werner Vogels
• Event Sourcing – Greg Young and Udi Dahan
• Partial Order

Download the slides

It is official. I have been invited to speak at Ignite Dallas.

In my prior recording of the talk, I neglected to mention the names of some folks who have been influential in collaborative application design. This new recording remedies that oversight.

I also modified the second half of the talk to tell the partial ordering story a little better. It still needs the slides in order to really get it, but fortunately those are coming along.

Give it a listen. Hope to see you next Wednesday!

I am preparing for the upcoming Ignite Dallas event. 5 minutes, 20 slides that auto advance every 15 seconds. The final speaker list has not yet been determined, but I’m hopeful that I’ll have a chance to present.

I will be talking about the current thinking in collaborative applications.

• The CAP Theorem
• Eventual Consistency
• Event Sourcing
• Partial Ordering

The challenge is to condense all of this learning into 5 minutes, make it accessible, and make it entertaining. You can help.

Please take five minutes (actually 4:45) to listen to my rough draft. Leave comments on what I can improve, what I didn’t make clear, and anything I could leave out.

Then order your tickets to the event and see some really great performances. Or submit one of your own.

As of today (February 2010), the story of Java/WCF interoperability is fair. That wasn’t always the case. In the past, I’ve struggled to get Java and .NET to play nice. Today, I was able to make a .NET WCF client talk to a Java CXF web service with just a little coaxing. Here’s how I did it.

Contract first
The first step to successful interoperability is to define the contract. Somehow you need to generate the WSDL, and you need to tightly control what it looks like. Use tools to help you, but keep a close eye on what those tools do.

I started with a WCF service contract. This is a .NET interface that uses the [ServiceContract] and [OperationContract] attributes. Put this interface and all of the data types it uses into a class library project. Here’s an example:

[ServiceContract(Namespace = "http://correspondence.updatecontrols.com")]
public interface ISynchronizationService
{
    [OperationContract]
    FactTree Get(FactTree pivotTree, long pivotId, long timestamp);

    [OperationContract]
    void Post(FactTree messageBody);
}

The FactTree data type used by this interface is decorated with the [DataContract] and [DataMember] attributes.

[DataContract(Namespace = "http://correspondence.updatecontrols.com")]
public class FactTree
{
    [DataMember]
    public long DatabaseId { get; set; }

    [DataMember]
    public List<Fact> Facts { get; set; }

    [DataMember]
    public List<FactRole> Roles { get; set; }

    [DataMember]
    public List<FactType> Types { get; set; }
}

Create a WCF service

Even though we want to end up with a Java web service, an intermediate step is to implement this service in WCF.

1. Create a new project in Visual Studio using the template Visual C#: Web: WCF Service Application.
2. Add a reference to the class library that defines the interface.
3. Change the name of the generated service from Service1 to something meaningful.
4. Delete the generated IService1 interface.
5. Use your own interface instead.
6. Add a [ServiceBehavior] attribute to set the Namespace.

At this point, the service looks something like this:

// NOTE: If you change the class name "Service1" here, you must also update the reference to "Service1" in Web.config and in the associated .svc file.
[ServiceBehavior(Namespace = "http://correspondence.updatecontrols.com")]
public class SynchronizationService : ISynchronizationService
{
    public FactTree Get(FactTree pivotTree, long pivotId, long timestamp)
    {
        throw new NotImplementedException();
    }

    public void Post(FactTree messageBody)
    {
        throw new NotImplementedException();
    }
}

Like the comment says, we need to edit the svc file and the web.config. Right-click the svc file in the project tree and select “View Markup”. Change the Service attribute to the fully qualified name of the service class.

<%@ ServiceHost Language="C#" Debug="true"
  Service="UpdateControls.Correspondence.WebService.SynchronizationService"
  CodeBehind="SynchronizationService.svc.cs" %>

The web.config change is slightly more complicated. There’s a lot of junk in web.config that you don’t need to worry about. The section you want is all the way at the bottom. Look for the <service> tag. It has two attributes: name and behaviorConfiguration. Also look for the <endpoint> tag right below it. It has three attributes: address, binding, and contract.

1. Change the service name to the fully qualified name of your service class.
2. Change the endpoint binding from wsHttpBinding to basicHttpBinding.
3. Change the endpoint contract from IService1 to the fully qualified name of your interface.

Here’s a trick to getting the fully qualified names. Delete the text between the quotes of the attributes. Open the Class View by hitting Ctrl+Shift+C in Visual Studio. Expand the tree to find your service class and interface. Drag them onto the web.config file between the quotes.

You can also change the name of the service behavior, but that’s not necessary for this intermediate step.

Examine the WSDL

These steps ensure that we have nice clean WSDL to work from. Take a look at it by running your WCF service application. A directory listing will open in the browser. Click on the svc file. If you get a yellow screen, please double-check your steps.

Click on the link to see the WSDL you’ve created. Different browsers react differently to raw XML. IE and Firefox will show it to you, but Chrome will give you a blank screen. You’ll have to view source to see the WSDL in Chrome.

On this first page, you’ll see all of the input and output messages, and the operations, and the service itself. Double-check that the service uses binding="i0:BasicHttpBinding_...".

Hack the url to look at more detailed information. Change the query string to “?wsdl=wsdl0” to see the declaration for the binding. It uses “http://schemas.xmlsoap.org/soap/http” with the “document” style.

Hack the url again with “?xsd=xsd0” to see the data types. You should recognize these data types as the ones you wrote in C#. Notice that it turns all of your List<T>s into ArrayOfTs. When we import these into Java, they will become classes containing List<T>.

Create the Java contract project

Create a Java project in your favorite IDE (mine is Eclipse). Open a command prompt and go to the source directory of that project (probably ends in “src”). Download Apache CXF and unzip it to your hard drive (mine is in “c:\apache-cxf-2.2.6”).

Go back to the first WSDL page, the one with the “?wsdl” query string. This is the URL that we are going to generate Java files from. Copy this URL and use it at the command line:

\apache-cxf-2.2.6\bin\wsdl2java.bat http://localhost:3642/SynchronizationService.svc?wsdl

CXF will generate a bunch of class files. Most will be in a package derived from your namespace. One will be in “com.microsoft.schemas._2003._10.serialization”. If you find one in org.tempuri package, you forgot a Namespace setting in one of your attributes. These class files are decorated with enough annotations to make them compatible with the WCF service.

Create the Java service project

Although you could put your service implementation and contract in the same project, I prefer to keep them separate. You can use the contract project to write a different service implementation, or even to write a client.

Create a new Dynamic Web Project. Add to the new project a reference to the contact project. You will also need to add this reference to the Java EE Module Dependencies in the project properties. Otherwise it won’t copy the contract jar file to the service lib directory, resulting in a NoClassDefFoundError at runtime. Then add a class that implements the service contract. Copy the @WebService annotation from the interface to the class. The service looks something like this:

@WebService(targetNamespace = "http://correspondence.updatecontrols.com", name = "ISynchronizationService")
public class SynchronizationService implements ISynchronizationService {

    @Override
    public FactTree get(FactTree pivotTree, Long pivotId, Long timestamp) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public void post(FactTree messageBody) {
        // TODO Auto-generated method stub

    }

}

The service project needs the CXF jar files. Copy them from the CXF install folder (C:\apache-cxf-2.2.6\lib) into the project’s library folder (WebContent\WEB-INF\lib). This is the minimal set that you will need:

• jaxb-api-2.1.jar
• jaxb-impl-2.1.12.jar
• wsdl4j-1.6.2.jar
• XmlSchema-1.4.5.jar
• cxf-2.2.6.jar

Now we need to publish this web service as a servlet. The quickest way to do that is to derive a class from CXFNonSpringServlet. Right-click the project and select "New: Servlet”. Change the servlet base class to “org.apache.cxf.transport.servlet.CXFNonSpringServlet”. Uncheck the boxes to implement doGet and doPost. The base class handles those for you. Once the class is created, override the loadBus method.

package com.updatecontrols.correspondence.service;

import javax.servlet.ServletConfig;
import javax.servlet.ServletException;
import javax.xml.ws.Endpoint;

import org.apache.cxf.transport.servlet.CXFNonSpringServlet;

public class SynchronizationServlet extends CXFNonSpringServlet {
    @Override
    public void loadBus(ServletConfig servletConfig) throws ServletException {
        super.loadBus(servletConfig);        

        Endpoint.publish("/SynchronizationService", new SynchronizationService());
    }
}

Open the web.xml file. You will notice that a servlet mapping was created for you. This mapping is set up to handle URLs that directly address the servlet, but the CXF servlet adds the service name to the URL. Add a “/*” to the end of the URL pattern to direct all such addresses to the servlet.

<?xml version="1.0" encoding="UTF-8"?>
<web-app id="WebApp_ID" version="2.4" xmlns="http://java.sun.com/xml/ns/j2ee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd">
    <display-name>correspondence_sync_service</display-name>
    <servlet>
        <description>
        </description>
        <display-name>SynchronizationServlet</display-name>
        <servlet-name>SynchronizationServlet</servlet-name>
        <servlet-class>
        com.updatecontrols.correspondence.service.SynchronizationServlet</servlet-class>
    </servlet>
    <servlet-mapping>
        <servlet-name>SynchronizationServlet</servlet-name>
        <url-pattern>/SynchronizationServlet/*</url-pattern>
    </servlet-mapping>
</web-app>

Run the project in Tomcat to make sure the servlet is published correctly. Point a browser at the servlet (in my case http://localhost:8080/correspondence_sync_service/SynchronizationServlet) and you should see a listing of available SOAP services. Append the service name to the URL (http://localhost:8080/correspondence_sync_service/SynchronizationServlet/SynchronizationService) and you will get a 500 error. If you get a 404, you haven’t modified the web.xml file correctly.

Create a WCF client

The last step is the easiest. Since we started by creating a WCF service contract, we can ask WCF to create a client proxy. I documented this technique in .NET to .NET web services without WSDL. It turns out that this trick works equally well for .NET to Java web services.

Add an endpoint to the app.config of your client. The URL should be the servlet name followed by the service name. For example:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
  <system.serviceModel>
    <bindings>
      <basicHttpBinding>
        <binding name="SynchronizationServiceSoapBinding" closeTimeout="00:01:00"
            openTimeout="00:01:00" receiveTimeout="00:10:00" sendTimeout="00:01:00"
            allowCookies="false" bypassProxyOnLocal="false" hostNameComparisonMode="StrongWildcard"
            maxBufferSize="65536" maxBufferPoolSize="524288" maxReceivedMessageSize="65536"
            messageEncoding="Text" textEncoding="utf-8" transferMode="Buffered"
            useDefaultWebProxy="true">
          <readerQuotas maxDepth="32" maxStringContentLength="8192" maxArrayLength="16384"
              maxBytesPerRead="4096" maxNameTableCharCount="16384" />
          <security mode="None">
            <transport clientCredentialType="None" proxyCredentialType="None" realm=""/>
            <message clientCredentialType="UserName" algorithmSuite="Default" />
          </security>
        </binding>
      </basicHttpBinding>
    </bindings>
    <client>
      <endpoint address="http://localhost:8080/correspondence_sync_service/SynchronizationServlet/SynchronizationService"
          binding="basicHttpBinding" bindingConfiguration="SynchronizationServiceSoapBinding"
          contract="UpdateControls.Correspondence.WebService.Contract.ISynchronizationService" name="SynchronizationService" />
    </client>
  </system.serviceModel>
</configuration>

And with that you have a .NET WCF client communicating with a Java CXF server. I expect that similar strategies could be used to go the other direction, although I haven’t tried yet.

Correspondence is a library for creating collaborative smart client applications in .NET. When you express a model in Correspondence, it provides three things:

• Storage
• UI updates
• Synchronization

This open source library includes a demo application to illustrate its collaborative capabilities. Correspondence Reversi is a WPF rendition of a popular two player game. Download the client to play against a friend, or to randomly join in a game with a stranger. Download the source code to learn how Correspondence makes collaboration easy.

Storage
Applications typically store their data in a relational database. But they act upon that data by loading objects into memory. To bride the gap, application designers can choose from several object-relational mappers (ORMs).

The problem with the ORM approach is that it requires the application designer to express their model three times:

• Database schema
• Objects
• Mapping configuration

Keeping these three in synch becomes a maintenance task each time the model changes. And deploying a new version requires that the data be migrated to the new schema.

Correspondence is not an ORM. The application model is not reflected in a relational database schema. When the model changes, only the objects are changed. The schema remains consistent. This allows for new versions to be deployed without changing the database or migrating data. And it eliminates the need for mapping configuration, as the library stores all models the same way.

UI updates
Correspondence is built on top of Update Controls, a library for keeping UI controls up-to-date. While most UI update libraries require you to manage your own dependencies, Update Controls discovers them for you and manages them on your behalf. The only thing that Update Controls requires is that your model alert it when a property is accessed or modified.

Correspondence takes on the responsibility of notifying Update Controls. A Correspondence model can be bound to a Winforms or WPF user interface – even through an intermediate View Model – to provide automatic dependency discovery and change notification. A Correspondence application developer will never see INotifyPropertyChanged or ObservableCollection.

Synchronization
By far the most compelling feature of Correspondence is that it automatically synchronizes a data model among clients. Two or more people collaborating on the same data on different machines will automatically see each other’s changes. The automatic UI updates provided by Update Controls ensure that changes made on one machine automatically appear on the screen of another.

Most smart client applications switch from off-line mode to on-line mode based on the availability of the network. While on-line, smart clients communicate changes that the user makes with a server. It runs queries on the server to bring back information that the user wants to see. While off-line, they switch into a mode where data storage and queries are performed locally. Typically, smart client synchronization occurs during the switch between modes.

Correspondence works differently. It offers a consistent programming model whether the network is available or not. Objects created in Correspondence are stored locally, regardless of network availability. A background thread constantly synchronizes the local storage with a server when available, and silently waits when it is not. By eliminating the switch between modes, Correspondence simplifies the task of smart-client development, and improves the end-user experience.

Correspondence Reversi synchronizes with a cloud service running in Windows Azure. This service collects data from each client, and redistributes that data to other clients who need it. Two people playing a game together will see each other’s moves. But they will not see any of the traffic from other games. This is not a special feature of the Reversi game model. This is a feature of Correspondence. A different model will be synchronized just as intelligently, and will work with the same synchronization service. There is nothing application-specific about the cloud service.

Please download the client and play against your friends. Then explore the source code and see what you can do with Correspondence.

The sum of an empty set is zero. This is a well-known mathematical truth that the .NET Framework understands.

int sum = Enumerable.Empty<int>().Sum();
Assert.AreEqual(0, sum);

Entity Framework 1.0, however, doesn’t work like that. If you try to sum an empty set, it will throw an exception.

OrderEntities entities = new OrderEntities();
int totalQuantity = entities.OrderLine
    .Where(orderLine => false)
    .Sum(orderLine => orderLine.Quantity);
Assert.AreEqual(0, totalQuantity);

System.InvalidOperationException: The cast to value type 'Int32' failed because the materialized value is null. Either the result type's generic parameter or the query must use a nullable type.

Here’s my solution

Let Sum return a nullable integer. Then, if it is null, coerce it back to zero.

OrderEntities entities = new OrderEntities();
int totalQuantity = entities.OrderLine
    .Where(orderLine => false)
    .Sum(orderLine => (int?)orderLine.Quantity) ?? 0;
Assert.AreEqual(0, totalQuantity);

You know that Quantity cannot be null. I know that Quantity cannot be null. But we have to trick Entity Framework into thinking that it could be null. By casting the integer to int?, you select the Sum overload that allows for a null. Since Entity Framework doesn’t do the right thing with that null, then we’ll do it ourselves.

The “We Are Microsoft” charity coding weekend is an opportunity for developers to donate their time to local charities. It is organized primarily by Toi Wright. Matt Lagrotte of Verio has graciously provided web hosting for all of the charities. Without their support, and the support of Microsoft and other sponsors, 20 charities would go without the IT support that they need.

Our charity is Second Wind Dallas. They find sponsors for local families in need. Schools identify those families, and a committee determines which sponsor will adopt which family. Several volunteers coordinate the communications among schools, families, and sponsors. Right now, the system is run completely by phone, email, and Excel. They need help.

We are building an online database to coordinate this information. Volunteer assignments, family referrals, and sponsor adoptions all change year after year. As a result, we are developing this as a historic model.

The primary function of the site is data entry. An administrator will set up the volunteer, school, family, and sponsor records. They will manage the assignments of volunteers to schools, the school referrals of families, and the adoption of families by sponsors.

The secondary function of the site is notification. A volunteer will be reminded to contact sponsors for donations. They will pick up those donations at the school and deliver them to the families. They will be reminded to send a thank you to each sponsor for those donations.

We are building this system using ASP .NET Web Forms, SQL Server 2005, and Entity Framework. We will have it done within the next 48 hours. And when we are done, Second Wind will have a much more manageable process.

Download the source code and follow along.

This post is part of a series:

1. The customer is not you.
2. If-then is backwards.
3. Condition and outcome templates.
4. Condition composition.
5. The rule model.

We’ve defined interfaces for the various types of rules in our point-of-sale system.

public interface IFreeItemsRule
{
    IEnumerable<Item> GetFreeItems(Check check);
} 

public interface IDiscountRule
{
    IEnumerable<Discount> GetDiscounts(Check check);
} 

public interface ICouponRule
{
    IEnumerable<Coupon> GetCoupons(Check check);
}

These interfaces assume that we can execute rules based entirely on the check. While this is true for the majority of our example rules, this is not true for the frequent diner discount.

• m dollars for every n prior visits of minimum dollars or more that have not already been rewarded.

This rule needs access to the history of visits. So instead of providing a simple Check, we’ll provide a richer object. Inspired by the Model-View-ViewModel pattern, I’ve decided to call this rich object a Rule Model.

The RuleModel class

The Rule Model has access not only to the Check that the user is currently editing, but also to a repository. It can query the repository for any historical information that a rule may require.

public class RuleModel
{
    private Check _check;
    private IRepository _repository; 

    public RuleModel(Check check, IRepository repository)
    {
        _check = check;
        _repository = repository;
    } 

    public Check Check
    {
        get { return _check; }
    }
}

For example, our frequent diner rule needs access to the history of visits.

public int GetPriorVisitCount(
    FrequentDiner frequentDiner,
    decimal minimumAmountPerVisit)
{
    int totalPriorVisitCount = _repository
        .GetChecks(check => check.FrequentDiner == frequentDiner &&
            check.TotalBeforeDiscounts > minimumAmountPerVisit)
        .Count();
    int discountedPriorVisitCount = _repository
        .GetChecks(check => check.FrequentDiner == frequentDiner)
        .SelectMany(check => check.Discounts)
        .OfType<PriorVisitDiscount>()
        .Sum(discount => discount.VisitsCounted);
    return totalPriorVisitCount - discountedPriorVisitCount;
}

The RuleModel can satisfy the demands of the frequent diner discount rule. It can count the number of prior visits by this frequent diner, and it can count the number of prior visits that have already been rewarded. The difference is needed to determine whether the frequent diner has earned a new discount.

Let history decide

When the frequent diner earns a discount, we record that reward on the new check. We use a derivative of the Discount class that captures the number of visits counted.

public class PriorVisitDiscount : Discount
{
    private int _visitsCounted; 

    public PriorVisitDiscount(
        string description,
        decimal amount,
        int visitsCounted)
        : base(description, amount)
    {
        _visitsCounted = visitsCounted;
    } 

    public int VisitsCounted
    {
        get { return _visitsCounted; }
    }
}

By capturing this information in the discount itself, we ensure that our action is atomic. The very act of awarding the discount deducts the visits required to earn it. Refer back to the GetPriorVisitCount method to see how this historical information is used.

By capturing data historically rather than keeping a separate tally, we can greatly reduce the likelihood of a defect. And if there ever is a question about discounts awarded (or not awarded), the entire history is there to be audited.

Rules are independent

Download the source code and examine the tests. You’ll find that each of the example rules that we originally promised the customer are working as expected. You will also find that they are working independently of one another. As we discussed at the beginning of this series, independence is important for understanding the behavior of the rule engine. If the rules depend upon one another, it becomes difficult to explain why they behave the way that they do.

An example of independence can be found if we combine a free item rule with a coupon rule.

• Buy 5 burgers, get 2 ice creams free.
• Buy an ice cream and get a coupon for half off your next visit.

Take a look at the IndependentRulesTest to see how we express these rules:

[TestInitialize]
public void Initialize()
{
    InitializeService(
        new List<IDiscountRule>(),
        new List<IFreeItemsRule>() {
            new BuyOneGetOneRule(5, BurgerId, 2, IceCreamId) },
        new List<ICouponRule>() {
            new TriggerItemCouponRule(1, IceCreamId, "Half off") }
    );
}

You might worry that the customer would be awarded free coupons for the two free ice creams. But fear not:

[TestMethod]
public void DontAwardACouponForFreeIceCream()
{
    // Buy five burgers.
    Check check = new Check();
    check.AddItem(BurgerId).Quantity = 5;
    Check outputCheck = _service.ExecuteRules(check); 

    // No coupons awarded.
    Pred.Assert(outputCheck.Coupons, Is.Empty<Coupon>());
}

As you can see, no coupons are awarded when the customer buys 5 burgers. This is because the rules are independent of one another. Each rule is evaluated against the original check. Rules are never permitted to modify the check. No rule depends upon the results of another.

Conclusion

The next time your customer asks for customizable business logic, consider what we’ve gone over here. You could use a general purpose off the shelf rules engine, but that is probably asking too much of your customer. They would be forced to think like a programmer. Instead, you can provide specific goal-directed rules that they can parameterize. Use set unions to compose rules, and be sure that each rule runs independently of the others. The result will be a simple, powerful, and extensible custom rules engine that will empower, rather than confuse, your customer.

Download the source code and follow along.

This post is part of a series:

1. The customer is not you.
2. If-then is backwards.
3. Condition and outcome templates.
4. Condition composition.
5. The rule model.

So far, we have defined rules by using concrete examples. We turned them around to express them in terms of the goal. And we coded one interface per outcome, one class per condition.

With this code, we could easily write a system that applies one rule.

public class PointOfSaleService
{
    private IDiscountRule _discountRule;

    public PointOfSaleService(IDiscountRule discountRule)
    {
        _discountRule = discountRule;
    }

    public CheckWithDiscounts AddDiscounts(Check check)
    {
        return CheckWithDiscounts.Create(check, _discountRule.GetDiscounts(check));
    }
}

Notice that the rule does not modify the original check. If it did, we could not safely execute the rule again. Instead, it returns a new object: a check with discounts. The check is independent. The check with discounts is dependent – upon the check and upon the rules.

Sorry, make that rule (singular). We inject the rule into the service. There is probably some code elsewhere that loads the rule from the database, so that the user can modify it.

But the user probably wants to write several different rules. They don’t want just one combo; they want a whole menu of them. Furthermore, they also want discounts for prior visits. We need to apply all of these discounts.

Union of collections

The IDiscountRule is coded to return a collection of Discount objects. We did this because one rule could apply multiple discounts. We can take advantage of that fact to compose these rules. All we need to do is take the union of their outcomes.

public class PointOfSaleService
{
    private List<IDiscountRule> _discountRules;

    public PointOfSaleService(List<IDiscountRule> discountRules)
    {
        _discountRules = discountRules;
    }

    public CheckWithDiscounts AddDiscounts(Check check)
    {
        return CheckWithDiscounts.Create(
            check,
            _discountRules.SelectMany(
                rule => rule.GetDiscounts(check)));
    }
}

The SelectMany extension method takes the union of several different sets. Each set is generated by one element of the source collection. You can think of it as flattening a tree. In this case, the parent of the tree is the rule, and the child is the list of discounts that the rule generates.

Isolation

We’ve taken care to remove cycles from our rules before we started. Remember the Big Spender rule? Give a 5% discount on checks totaling more than $500. To eliminate cycles, we need to consider the total of the original check, not the total after discounts have been applied.

Consider another way that we could have written the method:

public class PointOfSaleService
{
    private List<IDiscountRule> _discountRules;

    public PointOfSaleService(List<IDiscountRule> discountRules)
    {
        _discountRules = discountRules;
    }

    public void AddDiscounts(Check check)
    {
        // WARNING!!
        // This is the wrong way to apply multiple rules.
        foreach (IDiscountRule rule in _discountRules)
            check.AddDiscounts(rule.GetDiscounts(check));
    }
}

In this version, we are modifying the original check after each rule. The next rule sees the modifications. So what would happen if our Big Spender purchased a combo? If the combo brought the total of the check down below $500, he would no longer get his 5% discount. That is, unless we moved the Big Spender discount to the front of the list.

This is the mistake that so many rules engines have made. Each rule has the opportunity to change the state of the system. Each rule can see the effects of the rules that came before. Now, all of a sudden, order matters. The user has to prioritize rules. The rules engine has to run complex solutions like the Rete algorithm in order to iterate to a solution. We can no longer develop rules in isolation without running the risk of affecting the other rules.

Preserve original state

A point-of-sale system is interactive. The user can add items to a check and see what discounts are applied. They can then add or subtract other items and see how the discount is affected.

Imagine how we would accomplish that interactivity if we modified the check to apply discounts. Add a combo, and the rules engine adds a discount. Then remove one of the items. The rules engine would have to recognize what just happened and remove the discount in response. Can you imagine the code it would take to make this work? Can you imagine all of the corner cases? Can you imagine how much testing you would need to do to be sure it was right?

It is much easier to instead preserve the original state of the system. Our correct rules engine (second listing) does just that. Our incorrect rules engine (third listing) destroys the original check. It is nearly impossible to get back to the original.

In the correct rules engine, any changes that the user makes are applied to the original Check. The object that appears on the user’s screen, however, is the resulting CheckWithDiscounts. It is a very simple matter of re-running the rules after every change to update the discounts. If the user removes a trigger item, the rule will no longer fire, and the discount will be “removed”.

The only way to safely apply multiple rules is to allow each rule to see only the original data. Rules should not modify data. Instead, the engine should gather their outcomes and build a new state from that union. Even then, that new state does not replace the original state. When the original state changes, you can simply re-run the rules to evaluate their new effect.

To finish it all off, we provide all of the context that the rules need in the Rule Model.