Kirill recently posted a blog about connected component labeling in C#.  He also asked for solutions in other languages, so of course I had to code it in F#.

You can read his blog for more info, but the gist is, given a black and white grid, do a "flood fill" of each section with a different random color.  Here's a sample before-and-after screenshot:

There are slider controls which let you control both the size of the initial black-and-white grid and the "white percentage".  So here's a bigger example that starts off mostly white:

When you move the sliders you get a new black-and-white grid, and then when you click the button, it colors it.  Get the idea?  Cool and fun.

Anyway, I shamelessly stole all Kirill's UI code, transliterated it to F#, and then implemented the Union-Find algorithm Kirill had mentioned, and it seems to be blazingly fast.  So I present for your enjoyment, without further commentary, the F# code:

When I need a quick-and-dirty fifteen-line script for a one-off task involving text files, I often use perl.  The problem is, I use perl infrequently enough that each time I decide to use it, I usually need to give myself a five-minute refresher on the syntax and common functions before I can get the job done.

On the other hand, I use F# every day.

Thus today's blog entry is just to call out how easy it is to write little handy scripts with F#. 

FSI

I haven't talked about FSI much.  You can use F# Interactive from the command-line (fsi.exe), or as a Visual Studio Add-in (inside VS, select "Tools\Add-in Manager..." and click the check box next to F# interactive).  I like the VS add-in because it makes it easy to use the VS text editor as a "scratch pad" with syntax highlighting and intellisense.  When you have code you want to execute, just select it and press Alt-Enter and the code will be sent to the FSI window and executed.

A sample script

Suppose I want to know what percentage of the sample .fs files in the F# distribution use the lightweight syntax option (#light).  I can quickly hack together:

Highlight this code, press alt-enter, and FSI says

Cool.  I wonder which files don't use #light?  I can just add a little code to the "else" branch:

and then highlight the last block of code (from "[for..." to the end of the file) and hit alt-enter again, and I see

in the FSI window.  Neat.

There might be shorter or more elegant ways to accomplish the same goal with F# (or perl, or what have you), but my focus today is on writability, demonstrating that it's easy to hack little scripts like this in less than five minutes.

Some F# details

The script above demos some F# bits that I don't think I've talked about before.  The "seq { ... }" code is an example of a sequence comprehension, another example of F#'s computation expression syntax.  Recall that "seq" (short for "sequence") just means "IEnumerable".  Inside a sequence comprehension, "yield" means the same thing as it does in a C# iterator block, and "yield!" means nearly the same thing, except that you pass it a sequence rather than a single item.  (In other words, "yield! s" is like "for i in s do yield i", where s is a seq<'a> and i is an 'a.)  So AllFiles returns a seq<string> that recursively enumerates all the file names under some directory.

The portion in square brackets is a list comprehension, which is pretty much just like a sequence comprehension, except the result is a list<'a> rather than a seq<'a>.  Thus we end up with a list of integers, with the value 100 for each file containing "#light", and 0 for the other files.  We average the values in the list, and we get the percentage of files that use #light.

That's all for today - just some quickie fun I wanted to share!

Last time I showed you how to use the F# Control library to easily parallelize a primes-computing program.  Today I'll show you how to use the same library in C# to achieve the same end.  I'll also talk more about one of the real strong suits of the library - making async programming more compositional - and this leads to all kinds of interesting discussions for C#, involving LINQ, as well as iterators and "yield".  Hold on tight - it's a wild ride!

Easy async from C#

As we saw last time, the F# solution involved calling library functions like Async.Parallel, but it also involved a tiny async workflow that looked like this:

That is, this part of the F# solution leveraged the F# computation expression syntax.  We don't have this syntax available in C#, so what are we to do?

As I hinted obliquely last time, C# has its own syntax sugar that will fit the bill: LINQ.  The key piece of the original C# code that we need to parallelize can be written this way:

That's the bit that takes more than 12 seconds to run on my box.  We can parallelize just as in F#, using the F# library + LINQ thusly:

I'll explain it in a minute, but the first thing to note is - we got the same big win as in F#.  If you look back at the original C# code from part one, you'll see it was about 10 lines of mess involving ThreadPool.QueueUserWorkItem, ManualResetEvent, and Interlocked.Decrement.  The code above is much simpler - we just create a sequence of all the computations we want to do, parallelize them, and run.

AsyncExtensions is a small wrapper class I authored that just wraps up the F# Control library in a thin facade that makes it more C#-friendly.  You'll get a chance to see the implementation shortly.  The Run() and Parallel() methods just forward calls to the corresponding Async calls in the F# Control library.

The interesting/unexpected part is the LINQ query.  Though you typically think of LINQ as just syntactic sugar for authoring queries over IEnumerables, the way LINQ is defined in the C# language specification is far more general, and enables the LINQ syntax (things like "from" and "select") to be used in an arbitrary monad.  (I demonstrated this a long while back, when I showed how to use LINQ in the definition of monadic parser combinators in C#.)  I'm continuing to defer the full discussion about monads (what they are, why they matter, what LINQ has to do with it) because at this point it would still be a needless distraction.  All you need to do right now is take it on faith that this C# code:

means the same thing as this F# code:

and that this C# inside a LINQ query:

means the same as this F# inside a computation expression:

and you're good to go.  Actually, you don't have to just take it on faith - you can try the code yourself.  Here's the full C# code.  Just throw it in a C# project, reference FSharp.Core.dll from your F# 1.9.4.15 installation, and try it out.  But then keep reading - there's more blog after this code:

So there's some fun C# code you can run with today.

Compositional async code

We've seen how the F# Control library can be used to parallelize computations in both F# and C#.  But parallelization is just one aspect of the F# Control library.  An even more enticing value proposition is the ability to write async code that composes easily.  Let's consider another example, from a networking domain, using WCF.

Suppose I have a web service that exposes an endpoint that can be used to compute squares of integers - for example, you pass 5 to the web service, and it does some extremely difficult computations and finally returns you the answer 25.  (As is often the case, my blog samples are very contrived, in order to stay simple.)  Given a particular object that represents the connection to this service, we might write come C# code like this:

as a sample of what we can do with a "client" connection to the web service.

Now, each of the operations on the client (Open(), Square(), and Close()) can potentially involve a call out over the network.  In the code above, all the code executes synchronously, which means this function holds a CLR thread for the duration of the whole call to SumSquares().  Sometimes this is fine, but often (especially when writing servers or middle-tier components) we need to be more frugal when it comes to resources like threads, and ensure that we are only holding threads when necessary - not while we are blocked, waiting for some network call to return.  To this end, the .NET framework provides the Begin/End pattern and IAsyncResult type.  So for example, in addition to methods like Open(), frameworks also provide the corresponding async versions via BeginOpen() and EndOpen().  This API pattern makes it possible to get the job done - you can make a "Begin" call with a callback object, release the current thread, and then when the operation eventually finishes, your callback gets invoked with the result so you can pick up where you left off (probably with code now running on a different thread). 

While the Begin/End pattern is somewhat workable for a single call, it fails miserably for composing a series of async calls.  Suppose we want to author BeginSumSquares() and EndSumSquares(), with the implementation making calls to the Begin/End versions of Open, Square, and Close.  This is a perfectly reasonable thing to want to do - in fact, if you work on framework code in this kind of domain, this may be something you need to do all the time.  Ideally it would be straightforward - SumSquares is a five-line method, and we just want to do the same thing, only async.  In practice, it's a nightmare.  I won't even attempt to write the code for Begin/End-SumSquares here, because I know I will get it wrong.  The Begin/End pattern forces you into a hideous mess of spaghetti code where each async call necessitates a new callback method and a new IAsyncResult object, and this simple SumSquares example will probably take on the order of 100 lines of code to implement async.  If you've never had to write this kind of code before, thank your lucky stars.

Again, the problem is that the Begin/End pattern does not compose.  If I have two synchronous methods I want to call in series, one after another, I just write "Method1(); Method2();".  But with two async methods, I have to write tons of code just to correctly string two calls together in series.  What we need is a pattern for writing async code that makes composing a series of async calls as easy as composing a series of sync calls.

In F# this is easy to do.  The F# synchronous code looks like this:

(The "box" and ":?>" bits are just how the cast to type IClientChannel is performed in F#.)  To make it async, rather than use the Begin/End pattern, we can use the F# Async pattern (which is easy to build on top of the Begin/End methods, using the Async.BuildPrimitive function in the library).  Then we can use F# async workflows like this:

The "do!" keyword in an F# async workflow lets us call an async method when we don't care about the result, and the "let!" keyword calls an async method and binds the result to a new variable name.  As a result, our original five-line synchronous method is still just five lines when we rewrite it to run asynchronously - the difference is that we write the code inside an async workflow.

It turns out that we can do the same thing for C#.  This sync C# code:

can be rewritten as this async code:

using the F# Control library from C#.  Again, I am using LINQ.  Once we enter the async monad (the first line with "StartWorkflow"), each subsequent "from" in C# is like a "let!" in F#.  There is no LINQ syntax that corresponds to "do!", so we have to use "from" and bind the meaningless results to dummy variable names (I chose "_0", "_1", and "_2" as the names for my "don't care" variables here).  The code looks a little weird, since we are "abusing" LINQ in order to achieve our goal.  But I am a pragmatic, and if I can save myself from having to write 100 lines of nightmare Begin/End/IAsyncResult/callback code in order to achieve composable async C# code, then I am willing to pay the price of having to use some awkward syntax (the "from", "select", and dummy variables).  The code looks a little weird, but it still feels like a big win.

Shortcomings of the LINQ approach to async in C#, and an alternative approach

The async C# code I just showed is pretty nifty, but there are more problems with the "LINQ approach to async" other than just the awkward syntax.  The example I chose (SumSquaresAsync) was very simple - a method with straight-line code that made five async method calls.  What if we want to start with some more complicated synchronous code, that involves if-then-else, while loops, try-catch blocks, or arbitrary other C# constructs?  These constructs do not have an obvious/straightforward mapping into LINQ when we try to create the corresponding async code.  As a result, the async version of code using such constructs will probably have to look different from (and be more complicated than) the corresponding sync code.  That's unfortunate, as it erodes the main benefit we were out to achieve in the first place (async code that's as simple as the original sync code).

There is an alternative to the LINQ approach.  Another of the C# language's "syntax sugars" fits the bill: "yield".  Iterator blocks that use the "yield" statement create a way to write C# code that will 'exit and return later where we left off', which is just the type of thing you need for writing async code.  As a result, it's possible to build an async library atop the iterator metaphor, rather than atop an async monad (utilizing LINQ).  This is the approach taken, for example, by CCR in Robotics Studio, which you can read a little about here.  I haven't yet studied this approach in depth, but it seems very interesting, as it doesn't suffer the LINQ drawbacks I just mentioned in the previous paragraph.  It's possible the two approaches might be complimentary (perhaps the same library can expose both the LINQ programming model and the "yield"/iterator programming model for composing async computations).

What's next?

There's potentially a lot more to talk about, but this is a good place to wrap things up for today. 

Source code

Below is the full source code for the WCF example - first in F#, then in C#. 

F# code

C# code