hexadecimal

Whenever I get my hands on a new piece of technology, I always try and experiment with it using real-world problems that I encounter. This not only helps me learn the technology, but also to evaluate it for my current and upcoming projects. And this weekend, I’ve been fiddling around with MGrammar, which is a part of Oslo.

Credit card validation is by no means a straightforward task, and I will demonstrate how MGrammar can help with that.

In fact, the typical credit card number is actually composed of lots of little flags, bits, indicators, checksums and what-not. Not to mention the identity of the card issuer, such as Visa or MasterCard.

The information on the magnetic stripe on the card which is read by card readers contains more information than just the account number. I won’t go into details about this, but if you are interested in how this works, I would suggest you have a look at ISO 7813.

Suffice to say, that the information read (usually a Track2), contains a specific format, which can be broken down into fields such as prefix, account number, expiry date, service code and so on.

Typically, high-traffic stores won’t actually contact the card authority for every card purchase. Instead, they queue them up and run them in batches over night. These are called “offline” transactions.

Not all cards allow this. Some cards are flagged as online-only. Others, are flagged so that they can only be used offline in their own country, and not in other countries.

This is further complicated by the fact that each card issuer, Visa, MasterCard, Diners, Amex and all the others, have their own completely unique set of rules, flags, bits, indicators and check-sum algorithms. This means that not all cards have a way of indicating if they can be used offline or not, and those that do, have different ways of doing it.

In most cases, a web-shop or store will simply not handle offline transactions, and will instead rely entirely on a third party, the payment processor, to perform all the required validations on the card. This is all good and well, unless you are that third party.

In the interest of not breaching any NDAs or disclosing any information that could aid any fraudulent people out there, I won’t go into any further details about how the card numbers work, or present any actual real-world rules in my examples. All the rules in the examples, although based on real-world rules, have been altered with fictional values.

Right! So you could implement all these unique and distinct validation rules in C# with a lot of if/else and switch/case statements and call it day. Which is fine, if you want a lot more work in the future, since these rules have a tendency to change over time, with new card issuers entering the market and the old ones inventing new cards with new and improved rules.

Another way, would be to create some sort of rule engine and let the suits or grease monkeys keep it up to date. You would have to create a syntax for the rule engine, table structures, parsing routines and of course a nice nifty UI in WPF with cool transitions, sparkles and animations (naturally!), so they can easily administrate these rules and leave you alone to engage in interesting coding experiments and tend to your blog.

Much of which you can do with MGrammar.

MGrammar is, as previously stated, a part of Oslo, which is yet another brainchild of Microsoft that will ship with .NET 4.0 and Visual Studio 2010. If you can’t wait that long to get your hands dirty, go get it from here.

Basically, you teach MGrammar the syntax of your own language using the modeling language M, stuff some data into it, and let it crunch out some structured XML-like output.

Consider the following imaginary rules for our imaginary credit card called BuyLess.

• * The card is issued by the company Northwind Credits Ltd.
• * The card number is always 16 digits long.
• * The card number must always have the value 2 in the 10th position of the card number.
• * If the card number has the value 0 in the 14th position, then offline transactions are allowed.
• * If the card number has the value 1 in the 14th position, then offline transactions are not allowed.
• * If the card number has the value 2 in the 13th position, and 0 in the 14th, then offline transactions are only allowed in Sweden and no other countries.
• * If the card number has the value 7 in the 13th position, then the card may only be used in ATMs, and not for purchases.

How would we like the user to express and maintain such rules?

We can’t very well tell them to go meddle with our code! Binary files? No way! Complex table structures and an accompanying UI?

How about plain text files (or blobs in the database) containing natural-language-like rules like this:

RuleSet BuyLess
    // Check length of card number
    Require that length of PAN is equal to 16
        or error "Invalid length of card number."

    // Make sure it's not an ATM card
    Require that PAN not have 7 at position 13
        or error "This is an ATM card!"

    // Value check at position 10
    Require that PAN has 2 at position 10
        or error "Expected 2 in position 10."

    // If this is an offline transaction ...
    If IsOffline is equal to 1 Then
        // Make sure that card may be used for
        // offline transactions
        Require that PAN has 0 at position 14
            or error "Card may not be used offline"

        // Domestic offlines only
        If PAN has 2 at position 13 Then
            Require that IsDomestic is equal to 1
                or error "This card can not be used
                for offline purchase in this country."
        End If
    End If
End RuleSet

That rule set is written in a completely brand-spanking new language called QCard. A language I just invented five minutes ago. It’s so simple and easy to understand that I can put it in the hands of the operation managers and feel fairly confident that they can take it from there.

To teach MGrammar about this new language, I define the language in M, the modeling language, like this:

//---------------------------------------------------
// QCard language for validation of credit cards
//---------------------------------------------------

module CardRules
{
  export QCard;

  language QCard
  {
    // Basic character tokens
    token Whitespace = (' ' | '\r' | '\n');
    token Digit = ('0'..'9');
    token Numeric = Digit+;
    token Identifier = ('A'..'Z' | 'a'..'z' | '.' | '_'
      | '-')+;
    token Linebreak = '\n' | '\r' | '\r\'n';

    // Keywords
    @{Classification["Keyword"]} token RuleSet = 'RuleSet';
    @{Classification["Keyword"]} token Require = 'Require';
    @{Classification["Keyword"]} token That = 'that';
    @{Classification["Keyword"]} token Length = 'length';
    @{Classification["Keyword"]} token Of = 'of';
    @{Classification["Keyword"]} token Is = 'is';
    @{Classification["Keyword"]} token Equal = 'equal';
    @{Classification["Keyword"]} token To = 'to';
    @{Classification["Keyword"]} token Starts = 'starts';
    @{Classification["Keyword"]} token Start = 'start';
    @{Classification["Keyword"]} token Greater = 'greater';
    @{Classification["Keyword"]} token Less = 'less';
    @{Classification["Keyword"]} token Than = 'than';
    @{Classification["Keyword"]} token With = 'with';
    @{Classification["Keyword"]} token Not = 'not';
    @{Classification["Keyword"]} token If = 'If';
    @{Classification["Keyword"]} token Then = 'Then';
    @{Classification["Keyword"]} token Ends = 'ends';
    @{Classification["Keyword"]} token End = 'End' | 'end';
    @{Classification["Keyword"]} token Within = 'within';
    @{Classification["Keyword"]} token Has = 'has';
    @{Classification["Keyword"]} token Have = 'have';
    @{Classification["Keyword"]} token At = 'at';
    @{Classification["Keyword"]} token Position = 'position';
    @{Classification["Keyword"]} token Error = 'error';
    @{Classification["Keyword"]} token Or = 'or';

    token Field = 'PAN' |'ExpiryDate' |
      'ServiceCode' | 'IsDomestic' | 'IsOffline';

    @{Classification["Comment"]}
      token CommentToken
      = CommentDelimited
      | CommentLine;
    token CommentDelimited = "/*" CommentDelimitedContent* "*/";
    token CommentDelimitedContent
      = ^('*')
      | '*'  ^('/');
    token CommentLine = "//" CommentLineContent*;
    token CommentLineContent
      = ^(
           '\u000A' // New Line
        |  '\u000D' // Carriage Return
        |  '\u0085' // Next Line
        |  '\u2028' // Line Separator
        |  '\u2029' // Paragraph Separator
        );

    token QuoteDelimited = '"' c:QuoteDelimitedContent* '"' => c;
    token QuoteDelimitedContent = ^('"');            

    interleave Skippable = Whitespace | Comment;
    interleave Comment = CommentToken;        

    syntax Main = RuleSet name:Identifier rules:Rule*
      End RuleSet => { Name = name, Rules = rules};            

    syntax Rule =
      r:RequireClause => r |
      l:LengthClause => l |
      i:IfClause => i;            

    syntax RequireClause = Require That condition:Condition
      e:WithError? => Require[condition, e];

    syntax LengthClause = Require That Length Of
      condition:Condition e:WithError?
      => Require[condition, e, IsLength[true]];

    syntax Condition = name:Field operator:Operator
      => Condition[name, operator];

    syntax IfClause = If name:Field operator:Operator Then
      rules:Rule* End If => If[name, operator, rules];

    syntax Operator =
      Is Equal To value:ValueListOr => EqualTo[value] |
      Is Not Equal To value:ValueListOr => NotEqualTo[value] |
      Starts With value:ValueListOr => StartWith[value] |
      Not Start With value:ValueListOr => NotStartWith[value] |
      Ends With value:ValueListOr => EndWith[value] |
      Not End With value:ValueListOr => NotEndWith[value] |
      Is Within value:ValueListComma => IsWithin[value] |
      Is Not Within value:ValueListComma => IsNotWithin[value] |
      Is Greater Than value:Numeric => GreaterThan[value] |
      Is Less Than value:Numeric => LessThan[value] |
      Has value:ValueListOr At Position pos:PositionClause
        => Has[value, pos] |
      Not Have value:ValueListOr At Position pos:PositionClause
        => NotHas[value, pos];

    syntax ValueListComma = "(" v:ValuePartComma+ ")" => v;
    syntax ValuePartComma = value:Numeric ", "? => value;

    syntax ValueListOr = v:ValuePartOr+ => v;
    syntax ValuePartOr = value:Numeric Or? => value;

    syntax PositionClause = value:Numeric => id("Position")[value];

    syntax WithError = Or Error message:QuoteDelimited
      => id("ErrorMessage")[message];
  }
}

Don’t panic if the M definition seems complex and daunting, it actually took less than ten minutes to write after I had figured out the basics of M, merely by reading the samples and quickly skimming through the documentation.

Basically, you define the syntax; what a comment is, how to parse an If / End If clause, conditions and so on using the token and syntax  keywords.

At its core, it’s much like Regular Expressions on massive steroids, and when I say massive, I really do mean massive. You can tell that it uses some of the same syntax, with Kleene operators, ranges and so on. People familiar with Regular Expressions will be able to pick up this new toy and start spitting out new languages in minutes.

The above language is complete with conditional clauses, and is capable of testing against parts of the card number with operators like has X at position Y, contains X anywhere, and the SQL-like in operator.

The basic syntax is:

RuleSet 
  Require that   (or error )
  If   Then
    …
  End If
End RuleSet

The “or error” part is optional and can be omitted. Field works like an Enum.

The following is a list of valid expressions for and is used both by the If clause and the Require clause (by reference, so it’s only defined once).

is equal to
is not equal to
contains (or (or (…))
starts with (or (…))
not start with (or (…))
ends with (or (…))
is within ( (, (, (…))))
is not within ( (, (…)))
is greater than
is less than
has at position not have at position

Now, if I pass the language definition into one end of MGrammar and the plain text into another end, I’ll get a structured output that looks like this:

{
  Name{
    "BuyLess"
  },
  Rules{
    [
      Require[
        Condition[
          "PAN",
          EqualTo[
            [
              "16"
            ]
          ]
        ],
        ErrorMessage[
          "Invalid length of card number."
        ],
        IsLength[
          "true"
        ]
      ],
      Require[
        Condition[
          "PAN",
          NotHas[
            [
              "7"
            ],
            Position[
              "13"
            ]
          ]
        ],
        ErrorMessage[
          "This is an ATM card!"
        ]
      ],
      Require[
        Condition[
          "PAN",
          Has[
            [
              "2"
            ],
            Position[
              "10"
            ]
          ]
        ],
        ErrorMessage[
          "Expected 2 in position 10."
        ]
      ],
      If[
        "IsOffline",
        EqualTo[
          [
            "1"
          ]
        ],
        [
          Require[
            Condition[
              "PAN",
              Has[
                [
                  "0"
                ],
                Position[
                  "14"
                ]
              ]
            ],
            ErrorMessage[
              "Card may not be used offline"
            ]
          ],
          If[
            "PAN",
            Has[
              [
                "2"
              ],
              Position[
                "13"
              ]
            ],
            [
              Require[
                Condition[
                  "IsDomestic",
                  EqualTo[
                    [
                      "1"
                    ]
                  ]
                ],
                ErrorMessage[
                  "This card can not be used for offline
                   purchase in this country."
                ]
              ]
            ]
          ]
        ]
      ]
    ]
  }
}

You can write your language and see the result in real-time using Intellipad.

(Click the image for a larger view)

By embedding the language in my application, I can process input files in runtime and get a structured result that I can iterate much like I would XML.

You can do one of two things, you can embed the language in text format and compile it in runtime, which would enable you to read the language file from a database or a file on the disk, or you can pre-compile it using the command mg.exe which comes with the Oslo SDK. If you pre-compile it, you get a .mgx file, a MGrammar image file. The file has the infamous “PK” header, meaning it’s a .ZIP archive. I haven’t picked the contents apart yet, but there it is.

In my example, I have placed the .mg file, the Q-Card language definition in clear text in my project and use “Custom Tool” to compile it in the post-build event. This will hopefully be better integrated once Oslo hits RTM.

Then I use the following code to load and parse the language and execute it against the input file.

class Program
{
    static void Main(string[] args)
    {
        // Load the Q-Card language file
        DynamicParser language =
            DynamicParser.LoadFromMgx("QCard.mgx",
            "CardRules.QCard");

        // Parse the ruleset file
        object rootNode =
            language.Parse