Monadic Parsing

August 13, 2014

I’ve spent a nontrivial part of my time at SEP working on projects that needed to do low level communication with some sort of remote device.  Thankfully, the trend for remote device communication is going in the direction of Bluetooth and USB, so we can leverage existing libraries and OS facilities to handle low level communication protocols.  In addition to the typical benefits of using modern and standardized communication protocols, there are also some very nice developmental benefits:

  1. These protocols are designed with general purpose in mind, so it is unlikely that your developers will run into a situation that your product requires, but which the protocol itself cannot handle.
  2. Preexisting libraries means that you save a bunch of development time for writing the protocol itself (it’s already written).
  3. Preexisting libraries also implies someone else is handling verification and maintenance for the protocol implementation.  This may or may not be a good thing actually.  For example, perhaps you do not trust the organization that owns the library.  However, if the protocol you are using is mainstream enough, then it may exist as an operating system facility.  In this case the library owner very well could be a multinational corporation with an army of developers overseeing production, testing, and maintenance.

However, real life is not always so convenient.  Sometimes you need support for your legacy devices.  Sometimes the requirements prevent you from being able to utilize modern communication hardware.  Sometimes the device is not directly under your control, but you still have to interoperate with it.  The point is that sometimes you can’t use existing solutions or you need to interface with a custom communication protocol; the question is how can this be accomplished with a minimal cognitive overhead for your developers so that implementation, verification, and maintenance costs are all kept low.  This is a question that I’ve been asking myself for years, and I’ve finally found a very promising solution.

Recently, the Haskell programming language has begun to popularize monadic parsing.  There are two well-known monadic parsing libraries for Haskell:  Parsec [1], which is a general parsing library, and attoparsec [2], which is a parsing library that is optimized for handling network protocols and binary file formats.  This is a good place to take a quick detour to discuss monads.

There’s been quite a lot of hubbub concerning monads [3] and their place in software development in the past several years.  There is no shortage of blog posts trying to describe some real world metaphor for monads, which in the end do little more than muddy the waters.  Additionally, their origin in abstract mathematics can be rather intimidating.  I’m not personally convinced that monads needs to be the next thing in software development, but I am convinced that one of their applications, monadic parsing, has rather a lot to contribute to certain areas of software development.

Now let’s take a quick look at a simple monadic parser in Haskell.

metaFieldParser =   do    getSpecificByte 0xFF     metaFieldLength <- getByte     metaField <- getFixedLength metaFieldLength     return metaField completeParser = addCrcCheck metaFieldParser

Clearly this example is hiding a lot of the behind-the-scene details, however this really is how you would define a parser using a monadic parsing library.  The code is incredibly declarative and describes the frame in exactly the same way that documentation would.  This makes it easy to implement the parser initially because you can almost just copy the protocol specification into the source code.  Verification through code reviews become much easier as well because the reviewer can focus more on what action the code is accomplishing instead of having to focus on how the code is accomplishing some action and if that action is correct.  And finally, this makes any modification due to changing specifications easy to accomplish.

Let’s take a look at some of the parsing functionality that we get by using this technique.

  1. The first line of the do-block is checking to see if the first byte to be parsed is equal to a specific value.  Arbitrary checks can be encoded into these parsers and previously bound fields in the byte stream can be used in these checks.
  2. The second line of the do-block is getting the next byte in the frame and binding it to the “metaFieldLength” variable.  This means that any field we parse out of the byte steam can be used to help us to continue to parse the remainder of the byte stream.  In this instance we’re deciding how many bytes to parse by looking at a length field.
  3. The third line of the do-block is parsing a fixed length of bytes based off of the previously parsed length field.
  4. The final line of the do-block is returning the “metaField” from the parser; a successful parse is complete.  This line can actually be arbitrarily complex and include multiple previously bound fields from the parsing.
  5. Finally, outside of the do-block we are creating the complete parser by modifying the meta field parser we already built.  This is an important part of the example because it means if we encounter common patterns in our parser we can abstract them.  This makes it much easier to build a complete parser out of common sub-parsers.  In this example, we found we needed to do a CRC check for many different frames and we wrote a CRC checker that we can use to modify any other existing parser.

Now of course not every project is going to be able to use a programming language like Haskell.  Not only is there the question of developer availability, but also whether or not your infrastructure can conveniently accommodate Haskell.  So can a more enterprise friendly language (say C#) also be used to leverage monadic parsing?  Fortunately, the answer is yes.

public static Parser MetaFieldParser = AddCrcCheck(     Parsing.Bind( Parsing.GetSpecificByte( 0xFF ),     Parsing.Bind( Parsing.GetByte, metaFieldLength =>     Parsing.Bind( Parsing.GetFixedLength( metaFieldLength ), metaFieldBytes =>     Parsing.Return( new MetaField( metaFieldBytes ) ) ) ) ) );

The monadic parser we wrote in Haskell is surprisingly portable across languages.  The C# example looks very similar.  All of the calls to the “Parsing.Bind” function are a little annoying, but they mostly stay out of the way.  Additionally, F# [4], another Microsoft supported programming language, has support to clean up monadic code [5] in a very similar way to how Haskell handles it.  Perhaps someday more enterprise languages will provide support for clean usage of monadic parsing, but for now we still have a very useful tool for dealing with low level communication protocols that we can start using today.

[1] –

[2] –

[3] –

[4] –

[5] –