• F# August September CTP is out! Don Syme has the announcement, Jomo Fisher has the link roundup and details are on the brand-spanking-new MSDN F# Dev Center. Major congrats to the F# team. I've been running a pre-release version of these bits, and they are a huge step forward if you're an F# developer.
• I've got an article on IronPython in the latest issue of CoDe magazine. Also check out Brad Wilson'sIronRuby article, Ted Neward'sF# article and Neil Ford'sPolygot Programming article.
• Via Michael Foord I discovered that IronPython tester Dave Fugate is back on the blog. He starts with a couple of posts about measuring IronPython performance.
• Speaking of blogging teammates, I think the dynamic languages team has the highest percentage of bloggers in any group at MSFT. All four Program Managers (Dave (lead), John, Jimmy and me), four of five developers (Shri (lead), Dino, Curt and Oleg) and all three Testers (Jim, Dave and Srivatsn). The only non blogger right now is Tomas - who at least has a home page - and  the lead tester which is an open position right now. 11 bloggers out of 12 team members equals 91.67% team blogger coverage.
• I was really impressed with Newspeak when I saw it at Lang.NET so I'm very excited to see they have a new website. No public bits yet, but I like the part where they point out Newspeak "can be implemented independently of Squeak, Smalltalk or any particular VM or IDE". How about implementing a version on DLR guys?
• Maurice de Beijer shows off embedding IronPython inside a WF application. Kinda cool, but he's primarily showing off implementing a CLR interface in IPy. How about a WF activity that execute arbitrary IPy code. That would be cool. (via IronPython URLs)
• Ironclad has reached their 0.5 milestone, being able to import numpy from IronPython. BTW, guys - I'm not sure commenting out one line that appears to be unreferenced qualifies as a "monstrous caveat". Congrats guys! (via IronPython URLs)

OK, onto geek stuff:

• My new boss Dave Remy has moved to a new blog. If you're curious what he was up to for the 10 months he was away from Microsoft, he's happy to share.
• IPy and IRuby developer Curt Hagenlocher (aka Iron Curt) is blogging. Cue the Ozzy...I AM IRON CURT. Or don't. Anyway, he dives in the deep end of the pool - no "hello world" lollyblogging for Iron Curt - digging into the stack implications of rethrowing exceptions and debugging emitted IL.
• Srivatsn writes about static compilation of IPy scripts. Note, we're not talking about static typing - it's still the same good-old dynamically typed IronPython, just packaged up as an assembly, rather than as a bunch of .py files. Note, if you're interested in compiling IronPython, you should check out the PYC sample we published as part of Beta 4.
• Speaking of IPy Beta 4, Shri Borde posts about the COM dispatch support which is enabled by default as of Beta 4. If you're driving COM automation clients (like Office) from IPy, this is a huge improvement over the old mechanism.
• Jeff Hardy has released a new version of NWSGI, a managed version of Python's Web Service Server Gateway Interface. My understanding is that this would allow any Python web stack written against WSGI to run in IIS with IronPython (subject to IronPython's compatibility with CPython). Jeff's been documenting his efforts getting Django running with NWSGI on his blog. Awesome work Jeff! (Thanks for the correction Seo!)
• I never really bought into the "Attention Economy", but Chris Anderson's economic analysis of his DIY Drones site traffic was fascinating.
• Lutz announces "it is time to move on" from Reflector and there was a collective horrified scream in the .NET community. He's handing it over to Red Gate, who promised they "will continue to offer the tool for free to the community".
• I missed this when he posted it in June, but I really liked Nikhil Kothari use of the DLR in Silverlight to cut down on the XAML verbosity in his ViewModel action binding.
• Brian McNamara previews the new Add Reference and file ordering support in the upcoming F# CTP. I'm really looking forward to the project-to-project reference support. I can't tell you how many times I've gotten burned because my main project recompiled but my test project didn't. You just get used to hitting Rebuild All instead of Build. As for file ordering, it's a bit of a bummer that F# requires it, but the new experience is hella better than editing the project file by hand. I'm really looking forward to the new CTP.

I spent a year on the .NET Adoption Team with Robert back in 2002 & 2003 - basically my last year in the Microsoft field organization. NAT - as were were known - was a national team of developer and architecture evangelists, so while we were all teammates, we didn't see much of each other in person. However, Rob and I both lived in the Puget Sound area and called on many of the same customers - I was an architect evangelist and Robert was a developer evangelist - so we ended up working together often. We drove together to Olympia many times- he drove and I hacked code in a kind of strange pair programming effort.

Robert grew up in the Pacific NW and had spent almost his entire career as an enterprise technology sales engineer here, so he had friends everywhere. I often used the lame line from the Dragnet movie with Dan Aykroyd: "They ought to put you in Missing Persons. You know everybody." because it seemed like everywhere we went we'd run into someone he grew up with, had worked with or had sold to. If we hung around before or after a sales call - coffee shop in Olympia before a meeting, debriefing with the sales rep on the steps outside of Costco HQ in Issaquah, etc - chances are someone would recognize him.

When I was leaving the NAT, Robert and I went to Phoenix so I could hand off my customers there to him. I joked that at least I could be sure we wouldn't run into anyone he knew in Arizona. Yet, it turned out he used to work with the woman who was sitting in front of him on the flight home. She and her husband owned car dealerships in Phoenix and Tacoma. I was astonished - what are the frakking odds? - but Rob just shrugged his shoulders. It happened to him all the time so I guess he was used to it.

I only saw him off and on since I left the team, though as fate would have it I did see him last week on the day he died. I was heading into building 18 for a meeting as he was pulling into the parking lot - I hadn't realized he was working on campus. We exchanged the usual pleasantries and promised that we'd get together soon. He was blocking traffic, so it was a short conversation. 24 hours later, he was dead.

Rob wasn't your prototypical blue monster, but he sure touched a lot of people and he made the world a better place by just being himself. You will be missed, Rob.

A commenter named atp warned me not to "fall into the newbie trap of thinking that monads are about sequencing operations. They aren't. A large number of monads (for example, Reader) are commutative and do not enforce any sort of statement ordering." Fair enough. For example, you switch the order of some LINQ operators and still end up with the same result. If you switch Where and Select, you should end up with the same output (assuming the where clause isn't invalidated by the select projection). But from a C#/F# perspective, I don't really care about monads for enforcing order anyway - the language has that natively. I care much more about the context flow aspect of monads, which it sounds like atp thinks we should be focused on anyway. Works for me.

Finally, Yuri K. pointed out that we aren't really stuck with the nested lambda expression syntax in C#. In Luke Hoban's Monadic Parser Combinators using C# 3.0 post, he implements a Where, Select and SelectMany extension method for his Parser delegate type, which allows him to plug into C#'s query comprehension syntax. He's 100% correct and I considered including this fact in my post. However, the mapping between query comprehension and the Bind and Result functions is a little murky, so I skipped it.

For C# query comprehensions, basically SelectMany does double duty, not only binding the parser and the parser generating function (which Luke called 'selector'), but also taking the two parse values and calling to a projector function and returning the projection return value in a Result. By implementing SelectMany, you can rewrite the TwoValues parser like this:

which looks pretty much identical to the F# monadic syntax version. Luke also implements Where, which I have in my F# parser library as Satisfy. Where takes a parser and only returns the parser result if the provided boolean predicate returns true. Select is a projection, similar to SelectMany but only used with a single parser. I have a couple of specific projectors in my F# library (Ignore which tosses the parse result and Listify which turns a single result into a single item list) but I haven't had any need for a generic projector like Select. I'm assuming Luke only implemented Select to make the query comprehension work when you don't have multiple from statements.

So it kinda surprised me that the response to calling McCain a dick and his campaign an embarrassment was so tepid. No outrage. No promises to unsubscribe nor predictions that others would do likewise. Dale sounds like he agrees that McCain's campaign is an embarrassment, even though he clearly supports McCain. RandyG doesn't have anything to say about McCain one way or the other, but he thinks Obama is a "pompous dick". Only BigJ provides any defense of McCain at all, but it's an extremely weak defense. He described McCain as "not afraid to tick off a powerful, influential, big money contributor", which I would expect is hard to say out loud with a straight face. Given that McCain has raked in millions in contributions from the oil industry after flip-flopping on offshore drilling, describing the Hilton's $4,600 contribution as "powerful, influential, big money" is laughable. Hell, McCain is returning ten times that amount in "unusual" (read: possibly illegal) contributions because they "just didn’t sound right".

I figure there are two main possible reasons for the lack of outrage:

• All my readers who are willing to unsubscribe because I don't agree with their political view have already left, leaving only those who agree with or simply ignore my political posts.
• The number of people willing to stand up and defend McCain, even anonymously in my small corner of the Internet, is very small.

Personally, I probably a little of both, but I'm guessing it's more the latter than the former.

Fans of Python use the phrase "batteries included" to describe the standard library, which covers everything from asynchronous processing to zip files.
About Python

I'm very happy to announce that as of IronPython Beta 4, we are including the Python standard library in an IronPython release. In addition to the usual binary and source zip archives, we're shipping an MSI installer that gives you the option to include the library files. I mentioned a couple of weeks ago that I've been spending a lot of time with lawyers, and this is the first step towards making the IronPython project as open as possible. Note the use of the word "first" in that previous statement. In other words, I've got more lawyers to talk to.

We've added a new standard library component category to the IronPython Issue Tracker. So if you find any issues or incompatibilities with using the standard library with IronPython, please files bugs on them. We haven't figured out what set of libraries we're going to ship, but we don't want to include ones that we know wont work. For example, Kevin Chu reported on the mailing list that importing the sqlite3 module fails. This is because we don't have a managed version of the _sqlite3 C-based module. So that's one we'll probably remove outright.

Also, this is the first release we've distributed as an MSI file, and it looks some folks on the mailing list have had some troubles with it. If you have issues, please file setup bugs as well.

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.

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:

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:

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.

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.

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:

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.

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:

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:

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:

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

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

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:

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:

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.

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.