Tag Archives : F#

Monadic Philosophy Part 3 – The Parser Monad in C#

(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),  

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), 

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), 

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.

Monadic Philosophy Part 2 – The LINQ Monad

If you don’t come from a math or philosophy background (and I don’t) “monad” sounds like a made-up word. Of course, understanding OO’s use of terms like “class” and “object” can be hard to grok at first too. But at least those terms have some grounding in real-world concepts that non-math geeks come across. Because I couldn’t draw an analogy of monads to anything at first, it made grasping the concept of monads very hard for me.

It’s such a unfamiliar word that the F# team doesn’t like it either:

“[W]hen the designers of F# talked with the designers of Haskell about this, they agreed that the word monad is a bit obscure and sounds a little daunting and that using other names might be wise.”
[F# Workflows and Haskell Monads, Expert F#, p232]

The F# team thought about calling them workflows, but settled on computation expression. Frankly, I don’t like these names much better. Workflow is too easily confused with WF and if the term computation expression is way to generic. Isn’t everything in programming a computation expression? I think I’ll just stick with monad.

Of course, if there was a short, pithy way of describing a monad, I’m sure that’s what we’d call them. It’s a kinda complicated idea, so there’s no simple two or three word phrase that accurately describes it. “Sequential computation with context flow” is the best I could come up with. It’s a crappy description, but here’s an elegant example that most .NET programmers are probably already familiar with.

var Orders = new List<Order>()

//code to populate orders omitted

var q = Orders
    .Where(x => x.OrderDate < DateTime.Now)
    .OrderBy(x => x.OrderDate)
    .Select(x => new {ID = x.OrderID, Date = x.OrderDate})

Yes it’s true: LINQ is a monad. The two basic concepts about a monad from my description above is that it’s a) a sequence of operations and b) there’s a context that flows from operation to operation. We see both here in this simple LINQ query. I realize I’m using what looks like a LINQ to SQL query here, but for the sake of argument let’s assume that this is all happening in memory.

The query is a sequence of three operations: Where, OrderBy and Select. LINQ has a set of standard query operators that you can mix and match in whatever order you need to. Part of the monad’s job is to enforce the sequence of actions. For C#, that’s not really a big deal, since it has explicit sequencing already. However, other languages like Haskell use lazy evaluation, meaning there is no explicit order of execution. Many lazy evaluation languages use monads in areas, such as I/O, where order of execution matters.

While C# doesn’t need any help to enforce execution order, monads are very useful in the way they flow context between the operations. In the case of LINQ, all the standard query operators take an IEnumerable<T> as their first parameter and return an IEnumerable<T>. Since they have the same inputs and outputs, they can be plugged together in whatever order is required. Yet, you don’t see any reference to GetEnumerator or the enumerator objects they return in the LINQ code above. All that code is hidden inside the LINQ query operators so the LINQ developer doesn’t have to look at it.

If you squint hard enough, IEnumerable kinda looks like a functional construct. It exposes a single method (GetEnumerator) and can be passed around much the same way functional languages like F# pass around first-order functions. Furthermore, the result of calling GetEnumerator is an IEnumerator object that likewise exposes one main function (MoveNext). In other words, you can think of IEnumerable sort of like a function that returns a function that you call to iterate the collection.

So to sum up, a monad is a sequence of operations in a specific order that automatically flows context from one operation to the next. In the LINQ example, C# has built-in constructs – IEnumerable<T>, foreach and yield return – that makes the monad seem less foreign (which is why I used it as my first example!) However, as we’ll see, the concepts of sequence and context flow in a monad still hold even if we’re not using built in features of C# to implement them.

Monadic Philosophy

(Since I accidentally published part one of this series a few minutes ago, I figured I might as well start publishing the series.)

If you start learning functional programming, eventually you’ll come across the idea of a monad. Coming from the object/imperative world of languages like C#, I’ve had a hard time wrapping my head around this concept. There’s no shortage of monad tutorials out there, but most use Haskell’s IO as the prototypical example of a monad. Given that I don’t know Haskell very well, I found it hard to separate the Haskell stuff from monad stuff. So I set monads on the back burner and decided not to worry about them.

However, all that changed when Stephan Tolksdorf alerted me to his very cool monadic parser combinator library FParsec. I found the FParsec parsers much easier to read my F# parser efforts, so I became very interested in monadic parser combinators. As you might guess, a “monadic parser combinator library” makes heavy use of monads. Time to switch burners.

The problem with learning monads with FParsec is that it’s really designed for production use. I needed to break monads down to first principles, so I rolled my own monadic parser library. Make no mistake, if I were looking to build a production parser in F# right now, I’d use with FParsec. My monadic parser library might “get there” eventually, but right now it’s a toy.

Over a series of posts, I’m going to describe what I know about monads. I didn’t set out to write a tutorial on monads – as I said, there are plenty of them out there. However, I found most of the the many monad tutorials I read lacking because the did a good job explaining the “how”, but not such a good job on the “why”. Coming from an imperative world, I wanted to understand the philosophy better. That being said, there’s a lot of tutorial in and around the philosophy. Hopefully, you’ll find both useful.

Morning Coffee 171

  • Big news for IronRuby out of OSCON. John and Jim have the details. Congrats to the IronRuby folks on reaching these milestones and paving the way for others (i.e. IPy) to follow some of the same paths.
  • One of those OSCON announcements, is a project my teammate Jimmy Schementi has been working on: Silverline, which “let’s you write Rails code that can run on the client“.
  • Shri Borde – the dev manager for IPy, IRuby and F# – tackles a tricky subject of static compilation of dynamic Python code. This came up on the mailing list recently as one of the outstanding requests for IPy to do is support custom attributes, which requires static compilation. Shri lays out some of the big issues with this approach. However, the community has been fairly clear on this, so it’s obviously something we need to look at.
  • I met someone from MS Research at the MS Product Fair who pointed me to the Institute for Personal Robots in Education, a joint effort between Georgia Tech and Bryn Mawr College and sponsored by Microsoft Research. Their Myro software (myro == my robot) is written in CPython, but there’s an effort underway (aka Miro 3.0) to build a .NET version that uses IronPython. Must investigate.
  • Seshadri shows how easy it is to extend C# types in IronPython. It’s also shows how simple it is to host DLR code in your app – it’s like 6 lines of code!
  • Early reviews of IronPython in Action are good.  
  • If you want to run an IronPython IDE in your browser with Silverlight, check out SilverShell from Dan Eloff.
  • The XNA team has announced their business plans for community games. Basically, you set a price point between 200 and 800 points (aka between $2.50 and $10) and receive a “baseline” of 70% of the revenue the game generates. More details are available in the FAQ. This is pretty excited. I’d like to build some co-op kids games.
  • Speaking of XNA, Caligari is now offering TrueSpace 7.6 for free . David Weller and Glenn Wilson provide an XNA viewpoint on the announcement, Chris Pendleton shows how to upload your models to VirtualEarth.
  • Congrats to the CodePlex team on their latest drop, which features that a cool new feature – Mailing Lists! IronPython has had a Mailman mailing list for years, so I’m not sure we’ll use this feature on IPy, but I’ll investigate it
  • Two PDC notes: First, Rick Rashid – VP of MS Research – will be delivering a PDC keynote. Second, the PDC team has put up a video podcast on Producing a Ginormous Conference in 10 Minutes or Less! It’s the “inaugural episode” so watch for more Countdown to PDC video podcast episodes in the future.
  • I recently discovered Chris Smith’s F# blog. He’s got recent posts on Mastering F# Lists and Guidelines for Readable F# code. For the F# novice, check out his F# in 20 Minutes posts (part one, part two)
  • Pat Helland is moving to the SQL team. Good luck Pat!
  • I like Nick Malik’s formal definition of use cases, but I can’t help be reminded of Charlie Alfred’s Value-Driven Architecture article in Architecture Journal 5 where he said use cases were “easy to teach and explain” but that “if simplicity were the only goal that counted, we’d all still be walking or riding horses to get from one place to another.”

Five Minutes Past Noon Coffee 170

  • Ben Hall announcesIronEditor, a simple dev tool for IronPython and IronRuby. Pretty nice, though fairly simplistic (as Ben readily admits). For example, it doesn’t have an interactive mode, only the ability to execute scripts and direct the output to IronEditor’s output window. However, it is a good start and I’m sure it’ll just get better. One thing he’s apparently considering is a Silverlight version. (via Michael Foord)
  • Speaking of “Iron” tools, Sapphire Steel have had an IronRuby version (in alpha) of their Ruby in Steel product for several months now. I wonder if John’s had a chance to play with it.
  • Speaking of John, the ASP.NET MVC / IronRuby prototype he talked about @ TechEd is now available on ASP.NET MVC Preview 4 via Phil Haack.
  • Ted Neward has an article exploring the IronPython VS Integration sample that ships in the VS SDK. As I mentioned the other day, we’re starting working on a production quality implementation of VS Integration for IPy.
  • Ophir Kra-Oz (aka Evil Fish) blogs Python for Executives. I like his “Risk, Recruiting, Performance and Maturity” model – four boxes, perfect for keeping an executive’s attention! :) Plus Ophir has some nice things to say about IronPython. (via Michael Foord)
  • Ronnie Maor blogs an extension method for PythonEngine to make Eval simpler. I especially like how he uses string format syntax so you can dynamically generate the code to eval. I wonder what this would look like in IPy 2.0 with DLR Hosting API. (via IronPython URLs)
  • Speaking of DLR Hosting, Seshadri has another great DLR hosting post, this time hosting IPy inside of VS08 so you can script VS08 events (document saved, window created, etc) with Python.
  • Justin Etheredge has a bunch of IronRuby posts – Getting IronRuby Up and Running, Running Applications in IronRuby, Learning Ruby via IronRuby and C# Part 1. (via Sam Gentile)
  • Don Syme links to several F# related posts by Ray Vernagus, though he’s apparently also experimenting with IronRuby. I’m really interested in his Purely Functional Data Structures port to F#.
  • Speaking of F#, Brian has a teaser screenshot of F# upcoming CTP. However, he chooses the New Item dialog to tease, which looks pretty much like the current new item dialog (the new one does have fewer F# templates). However, if you look in the Solution Explorer, you’ll notice a real “References” node. No more #I/#R! Yeah!
  • The interactive graphic in Kevin Kelly’s One Machine article is fascinating. It really highlights that the vast vast vast majority of power, storage, CPU cycles and RAM come from personal computers on the edge. Even in bandwidth, where PC’s still have the highest share but it looks to be around 1/3rd, the aggregate of all edge devices (PCs, mobile phones, PDAs, etc.) still dominates the data centers.