In the last post, I built out a basic parser monad in C#. While the approach worked OK, the syntax is still a little foreign to your typical .NET programmer, what with it’s nested anonymous functions and all. Now, I’m going to translate that code to F# and take a look at the special monadic syntax F# supports that makes using monads as easy any sequential code.

First, let’s translate our Parser delegate, Bind, Result and Item functions over to F#. Just for kicks, let’s also port over the final version of TwoItems too.

type Parser<'input, 'result> = 'input-> ('result * 'input) option

// the Bind function, defined as a custom operator
let (>>=) p f : Parser<'i,'r> =  
    fun input ->
        match p input with
        | Some(value, input) -> (f value) input
        | None -> None

let Result v : Parser<'i,'r> = fun input -> Some(v, input)

let Item : Parser<string, char> =  
    fun input ->
        if string.IsNullOrEmpty(input)  
            then None
            else Some(input.[0], input.Substring(1))

let BestTwoItems =  
    Item >>= (fun v1 ->  
    Item >>= (fun v2 ->  
    Result (sprintf "%c%c" v1 v2)))

First, we start with the declaration of the Parser type. Unlike C#, F# has built in support for tuples, so I didn’t bother to define a Result type (just the Result function). A Parser is declared to be a function that takes in some generic input type and returns an optional tuple pairing the result with the remaining input to be parsed. As I’ve blogged before, F#’s option type is kinda like C#’s Nullable type, so a parser that returns None is considered to have failed to parse the input.

Next up is are the monad functions Bind and Result. The only significant change from the C# version is that I used the custom operator >>= for the Bind function. So instead of calling Item().Bind(some\_function), we can call Item \>\>= some\_function. F# functions aren’t attached to a type like C# extension methods are, so this is the only way to get the more readable infix notation. I’m using >>= as the bind operator because that’s the operator Haskell uses for their monad function. Other than the custom operator name, Bind and Result work identically to their C# counterparts. Note, I explicitly specified the return type of Bind, Result and Item, but I didn’t have to. F# can infer the types of all the parameters from usage just fine. I added the type specifications for the reader, in case you’re not familiar with F#’s syntax.

Likewise, Item is identical to the C# version including using strings as the parse input, except for than the F# syntax. Typically, in a real parsing app you would use an intrinsic list of chars instead of strings, since F#s list is a much more efficient data structure than strings for operations that strip characters off the head of the list (like parsers are wont to do). However, I wanted to make this code as similar to the previous code, so I stuck with strings.

Finally, we have BestTwoItems. Again, syntax aside, it’s exactly like it’s C# cousin though I did use the slightly more compact sprintf function instead of string.Format. Again, while BestTwoItems it works well, it uses the same nested anonymous function syntax from the C# version. Maybe I shouldn’t have called it “BestTwoItems”!

However, in F# it’s possible to define a custom syntax for your monad that let’s you write the function this way:

let VeryBestTwoItems =
    parse {
        let! v1 = Item
        let! v2 = Item
        return sprintf "%c%c" v1 v2 }

With this monadic syntax, we’ve now completely eliminated not only the Parser delegate and the input string, but also the nested anonymous functions needed by the Bind function, making the code appear completely sequential.

The secret to making this work is the parse monad object. It the code above, the word parse almost feels like a language keyword, but it’s not. It’s actually an instance of an parse monad object with a specific signature. F# knows how to take the syntax above and combine it with the parse monad object to produce the right code. Here’s the parse monad:

type ParseMonad() =
    member w.Delay(f) = fun input -> f () input  
    member w.Return(v) = Result v  
    member w.Bind(p, f) = p >>= f

let parse = ParseMonad()

As you can see, there’s an obvious direct correlation of Result and Bind functions we defined last time and the Return and Bind methods in the ParseMonad. The only thing we haven’t seen before is the Delay method. Monads are one of of F#’s many delayed expressions. F# wraps the entire monad in a call to Delay to ensure the monad isn’t executed prematurely.

As per the F# grammar spec, there are several other functions you can define on your monad if you so choose. My “real” parser monad also implements Zero and Combine. Zero returns a parser that unconditionally fails. By defining Zero on my monad object, I can write ifs without elses, the parser monad will implicitly inject Zero clause as your else statement. Combine combines results (I know, a shocker!). I use it as a prioritized choice. In other words, when you Combine two parsers, you only call the second parser if calling the first parsers fails. Prioritized Choice is used very often in PEGs, which is why I chose to define it this way.

F# monadic syntax also support For, Let, While, Using, TryFinally and TryWith. Frankly, I haven’t spent much time thinking about scenarios where you’d use these other syntax elements. The only one that’s obvious to me is Using for deterministic finalization, which you could see using anywhere you access IDispoasble objects. Here’s hoping the F# folks document in detail how to use this powerful syntax.

So that’s it for basic monads in F#. I’ve gotten some great comments (and one less than great comments) as I’ve written this series. In my last post on monads (in this series at least) I’ll repost some of those comments as well as provide some concluding thoughts.

This segment on last night’s Daily Show was fantastic.

At the rate McCain’s going, Jon Stewart is going to have to change this segment to “McCain’s Dick Move of the Day”. I don’t know which is more embarrassing, McCain’s campaign or the mainstream media coverage of the campaign.

(If you disregarded my advice and read the previous version of this post, please note I rewrote this post significantly so you’ll probably want to read it again.)

In the last post, we looked at how LINQ is a monad and how IEnumerable is a pseudo-functional construct. However, C#’s intrinsic collection support – aka foreach and yield return – really obscure how you might go about building your own monad. So for this post, we’re going to take a look at a parsing monad instead. Just as LINQ broke the big problem of queries into a collection of standard query operators that were composable, we want to take the same approach for parsers.

Note, I’m going to stick with C# for now, and get into F# monads in my next post. Quick shout out to Luke Hoban and Brian McNamara, from whom I stole obtained some of the code below.

Quick refresher: I’ve described a monad as a sequence of computations with a context flow. Since C# has explicit sequencing, we want to focus on the context flow. For LINQ, the context was IEnumerable. For parsers, we could define an similar IParser interface like this:

class Tuple<T1, T2>
{
    public readonly T1 Item1;
    public readonly T2 Item2;
    public Tuple(T1 val1, T2 val2) { Item1 = val1; Item2 = val2; }
}

class Result<T> : Tuple<T, string>
{
    public Result(T val, string rest) : base(val, rest) { }
}

interface IParser<T>
{
    Result<T> Parse(string input);
}

The Parse function takes a string to be parsed as input and returns the parsing result which pairs the semantic value with with the remaining string input to be parsed. I’ve built out a simple generic tuple class because I know I’ll use it again later. I’ve long wished C# would support intrinsic tuples like F# does. For convenience, I’ve also created a strongly typed subclass of Tuple to represent parse results where the second item is a string, to save some typing. Since Result is a class, it can be null which means the the Parser failed to parse the input.

The problem with this approach is that unlike IEnumerable, the C# compiler has no built-in knowledge of this interface. That means there are no easy-to-use keywords like foreach and yield return that can do our heavy lifting of consuming or creating these IParser types for us. Instead, we would have to explicitly declare classes to implement the interface. As we add more and more parsers, that additional overhead of creating types would become more and more unwieldy. Instead, let’s redefine Parser as a delegate.

delegate Result<T> Parser<T>(string input);

The benefit of this approach is that you can create Parser delegates inside functions, using C#’s anonymous delegate syntax, without the overhead of creating a type. For example, here’s a function to create a simple primitive parser that strips the first character off the parse string and returns it as the parse result:

static Parser<char> Item()
{
    return input =>
        {
            return string.IsNullOrEmpty(input)
                ? null
                : new Result<char>(input[0], input.Substring(1));
        };
}

That’s a lot more convenient than building a type just to implement a single method.

Now that we have our Parser type, we need to think about how to compose Parsers so that we can flow context between them. Much as LINQ provides a collection of primitive query operators (Select, Where, OrderBy, etc), you would expect a monadic parser library to provide a collection of primitive parsers (Item, Satisfy, AnyOf, ItemEqual, etc), that you could combine into higher-order parsers along with some language specific lower-order parsers. Here’s an example from the the PEG grammar:

Primary \<- Identifier !LEFTARROW / OPEN Expression CLOSE / Literal / Class / DOT

The Primary parser depends on some high-order language specific parsers (Identifier, Expression, Literal and Class) as well as some language specific low-order tokenizer style parsers (LEFTARROW, OPEN, CLOSE and DOT) and finally some language-independent primitive parsers (the failure predicate ! and the prioritized choice operator /).

So how should we compose these various Parsers? LINQ query operators were fairly easy to compose because they all take in and return the same type (IEnumerable) so you can simply chain them together. Parsers are a little trickier because the inputs and outputs are asymmetric – i.e. they take a string, but return a Result – so simple chaining won’t work.

We could combine the parsers sequentially, taking the parse string returned from first parser and feed it into the second. Then we could combine the two parse values in a Tuple to return them (you see why I created a generic Tuple class?) resulting in a function that looks like this:

static Parser<Tuple<T1,T2>> Join<T1,T2>(this Parser<T1> p1, Parser<T2> p2)  
{  
    return input =>  
        {  
            var ret1 = p1(input);  
            if (ret1 == null)  
                return null;  

            var ret2 = p2(ret1.Item2);  
            if (ret2 == null)  
                return null;  

            return new Result<Tuple<T1,T2>>(  
                new Tuple<T1, T2>(ret1.Item1, ret2.Item1),  
                ret2.Item2);  
        };  
}

Note this is an extension method so we can call Parser1.Join(Parser2) rather than the less fluent Join(Parser1, Parser2). I was going to call this function Combine, but there’s already a static Combine method on the Delegate type that caused a conflict, so I used Join instead.

The Join approach works, but it’s a bit unwieldy to return the parsing values in a tuple. Every set of joined parsers will result in another level of tuple nesting in the Result that’s returned. That gets pretty ugly pretty fast. For example, lets say we want to create a parser that combines two instances of Item. It looks like this:

static Parser<Tuple<char, char>> TwoItems()
{
    return Item().Plus(Item());
}

That’s not so bad. But now look what happens if we combine the TwoItems parser with another instance of Item:

static Parser<Tuple<Tuple<char, char>, char>> ThreeItems()
{
    return TwoItems().Plus(Item());
}

The result is a nested tuple. Yuck. We need a better way. Enter the monadic bind. The code looks like this:

static Parser<U> Bind<T, U>(this Parser<T> p1, Func<T, Parser<U>> fun)
{
    return input =>
        {
            var ret1 = p1(input);
            if (ret1 == null)
                return null;

            var p2 = fun(ret1.Item1);
            if (p2 == null)
                return null;

            return p2(ret1.Item2);
        };
}

Like the Join function above, Bind starts by calling the first parser function, returning null if the parse fails. However, instead of calling to the second parser directly, it calls to the provided function that generates the second parser. This function acts as a closure, packaging up the parse value from the first parser for later processing. Finally, Bind calls to the generated second parser, feeding in the remaining text from the first parser result.

This approach allows you to inject code that combines the parsing values however we like rather than always pairing them up in a tuple. Here’s a version of TwoItems that binds a call to Item with a custom function that calls Item again and returns the two characters as a string rather than a tuple:

static Parser<string> BetterTwoItems()
{
    return Item().Bind<char, string>(
        val =>  
        {
            return input =>
            {
                var result = Item()(input);
                return new Result<string>(
                    string.Format("{0}{1}", val, result.Item1),
                    result.Item2);
            };
        });
}

It’s kinda strange to see a lambda expression that returns a lambda expression in C#, but that’s what this code does. The first lambda expression (val =>) defines the custom function, the second lambda expression (input =>) defines the Parser delegate. Val is the parse value from calling Item() the first time – ret1.Item1 in the Bind function above. Input is the remainder of the parse string – ret1.Item2 from the Bind function.

Unfortunately, while this approach avoids nested tuples for parse values, we’ve had to give up quite a bit of simplicity. The original TwoItems method was a single line of code. BetterTwoItems is significantly more complex. Furthermore, the double lambda expression syntax confuses C#’s type inference, forcing you to explicitly specify the generic types on the Bind method. Luckily there’s a better way to write this. However, let’s start by rewriting the function like this:

static Parser<string> SlightlyBetterTwoItems()
{
    return Item().Bind(
        v1 => Item().Bind<char, string>(
            v2 =>
            {
                return input =>
                {
                    return new Result<string>(
                        string.Format("{0}{1}", v1, v2),
                        input);
                };
            }));
}

SlightlyBetterTwoItems pulls the second call to Item out into a second Bind operation. The point of this refactoring is to make it clear that we can view this function as a call to Item, bound to a second call to Item, bound to custom function to return a Parser that returns the two parse value chars formatted as a string. You’ll notice that by eliminating the the double lambda expression on the first call to Bind, we were able to drop out the explicit generic type specification.

This version is a little clearer, but we can make it clearer yet. It turns out that wrapping up a parse value in a Parser that unconditionally returns the parse value and the parse text input in a Result is a very common operation. So let’s create a primitive function Result to wrap up a parse value in a Parser delegate and build our final version of TwoItems that uses it.

static Parser<T> Result<T>(T val)  
{  
    return input => new Result<T>(val, input);  
}  

static Parser<string> BestTwoItems()
{
    return Item().Bind(
        v1 => Item().Bind(
        v2 => Result(string.Format("{0}{1}", v1, v2))));
}

Now it’s very clear that we have a call to Item, bound to a second call to item, which is in turn bound to a call to Result. We’ve now dropped all use of double lambdas, which means C# can infer the types to each of our Bind calls implicitly. But more importantly, do you see any reference to Parser<T> delegates or input strings in this code? Only in the return type specification. Just as LINQ hides the specifics of flowing IEnumerable or enumerator objects between standard query operators, the parser monad hides the specifics of flowing Parser delegates or input strings between parse operations.

The Parser delegate plus the Bind and Result methods are all there are to our basic parser monad. Seriously, all that worry that monad “is a bit obscure and sounds a little daunting” and it’s really just two functions and a delegate type.

While this code is fairly straight forward, the whole nested lambdas expressions is fairly atypical syntax that some developers might have a hard time understanding. Unfortunately, if we’re writing our parsers in C#, we’re kinda stuck with this syntax. However, F# has a special syntax that lets you write what looks like normal sequential code, while still flowing the Parser context between parse operations exactly like the code above does. We’ll take a look at that syntax in the next post.