valerio.net

I’ve been interested in learning more about Inversion of Control (IoC) and Dependency Injection (DI) containers for awhile now, so I decided to take a look.

My interest was piqued by an article by Mark Seemann from his upcoming book “DI in .NET”. This was a good introduction, but not very in-depth – I’m certainly looking forward to his book now.

After digging in more, I discovered a few more good articles (also on .NET Slackers) that explain IoC and DI using the Castle Project – “Inversion of Control and Dependency Injection with Castle Windsor Container” – check them out:

• Part I
• Part II
• Part III
• Part IV

Very cool stuff.

I’ve received 3 inquiries in the last 2 weeks as to my “job availability status”, all surrounding my experience with F# on my resume. I’m no longer looking for a job (thankfully) and thought I had removed all references to my resume from my website, Dice, Monster, etc.  I suppose there are still a few floating around somewhere.

I don’t know a lot of details about the positions these recruiters are trying to fill, but I did find out that one is in Columbus, OH and one is in Redmond, WA. In an effort to help out the F# community I figured I’d post about these jobs.  There’s nothing in it for me.

If you are interested, shoot me an email and I’ll send you the contact information for the folks who called/emailed/talked to me.

Here’s my info:

let email = 
    [(5,"gmail"); (2,"."); (3,"valerio"); (6,"."); (1,"matt");
     (7,"com"); (4,"@")]
    |> List.sortBy fst
    |> List.map snd
    |> List.reduce (^)

Awhile back I wrote a post about tail-call optimizations that the F# compiler used to eliminate stack overflows. Brian McNamera commented about another optimization that I didn’t illustrate – the ‘tail’ opcode that appears when mutually-recursive and indirectly-recursive functions are encountered. Tail-call optimization is one of the really powerful features of F#, so I really wanted to see how this worked under the hood.

The first thing we need is a pair of mutually-recursive functions.  The easiest (laziest? ) way to do this is to write one function (e.g. f1) and duplicate its implementation as another name (e.g. f2):

// Hunting for tail calls

 

// 6.17.09

 

 

 

open

 

 

 

let

 

 

 

 

 

 

and

 

 

 

 

 

let

 

 

 

let

 

 

 

 

 

 

 

After compiling this, I popped open the resulting executable in Reflector. Of course I wasn’t going to find the ‘tail’ opcode by looking at the C# – I needed to disassemble the IL. I hunted and hunted for the ‘tail’ opcode, but couldn’t find it!  Every call to f1 from f2 (and f2 from f1) used the stack to pass around n and acc. Even stranger – this is the first F# program I’d written using Visual Studio 2010, and I could have sworn that I’d done the same thing with F# in Visual Studio 2008 a couple months ago.

After building the project again, I noticed the command-line arguments passed to fsc:

 

 

“—tailcalls-“? Somehow tailcalls are being turned off. Maybe there’s something in the project settings that are disabling the tailcalls? Ah-ha! The checkbox was unchecked

After poking around a bit more, I discovered that by default the “Generate tail calls” box is unchecked fo Debug mode, and checked by default for Release mode.  Hmmm, interesting.

After switching to Release mode, I rebuild the project and opened the .exe in Reflector.  Here we go! There’s the elusive ‘tail’ opcode:

.method

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

}

(The IL code for sum2 looks identical.) Interestingly enough, the C# code from Reflector looks exactly the same between Debug and Release modes (with and without tail calls) – C# doesn’t have the capability to make tail calls.

Well, there you have it! We finally found the elusive ‘tail’ opcode.

That being said, be sure to keep this in mind – the default settings of Visual Studio 2010 for F# development are drastically different between Debug and Release mode.  Bugs might crop up in Debug mode (e.g. StackOverflowExceptions) that don’t rear their heads in Release mode.

I think the motivation for this is that using tail calls severely limit the usefulness of the Visual Studio debugger since it relies on traversing the stack frame (that the tail opcode destroys) to display debugging information.

For example, without tailcall optimizations setting a breakpoint on sum1 looks like this:

The callstack shows some useful debugging information, specifically the values of n and the accumulator.

However, if we enable tailcall optimization, this breaks down after running through the breakpoint 10 times, each time it shows one line with different information:

… You get the idea.

Hope that sheds some light on tailcall optimization, as well as some of the new features of F# in Visual Studio 2010!

A helpful comment on a post over at HubFS by Brian McNamara really helped me wrap my mind around tail recursion and why it’s immensely important to understand in F#. Brian coined the phrase “tail recursion police”, hence the title

Recursion pops up quite a bit in functional programming so it’s a good idea to understand the risks/tradeoffs/benefits. A gross simplification of an analogy would be:

For loops : C# :: Recursion : F#

Sure, you can do for-loops and imperative-style coding in F#, but it doesn’t showcase the beauty of the functional style programming that F# offers.

Recursive functions (in both C# and F#) are just functions that call themselves.  They do so by pushing the current state of the function onto the stack, popping them off when calls start completing. Because the stack is a limited resource, it can be exhausted (StackOverflowException) if the function is called recursively too many times. 

These kinds of runtime exceptions can be difficult to find unless explicitly tested for, leading to hard-to-find bugs.  Oftentimes tests will only exercise simple cases of algorithms and then fail at runtime when large (real-world) inputs are used. After all, “everything works for small N”.

F#, however, has a very interesting feature where (under certain conditions), it can recognize recursive functions and perform a “tail call optimization”, turning the recursive function into a while-loop that uses no stack space whatsoever. This is called tail recursion.

The rule for tail-recursion is simple:

If the recursive call to the function is the very last thing that happens in the algorithm, then the function can be made tail-recursive.

In most cases a recursive algorithm can be expressed in both recursive and tail-recursive forms. Other times, it may not even be possible to implement a specific algorithm tail-recursively.

Let’s look at some examples.

Tail Recursive or Not?

One way to implement the “map” function that applies a specific function, f, to every element in a list would be:

While this implementation easily expresses the algorithm (splitting a list into its head and tail, applying the function f to the head, and consing it to the list obtained from applying the function to the tail), it is NOT tail recursive! The recursive call to “map” must happen, then f is applied to h, and then the results are cons’d (:: operator).  The recursive call to “map” is not last in this instance, so it’s not tail-recursive.

How can we make this map operation tail-recursive? Typically this involves 2 things — factoring out an inner loop that is recursive and threading an accumulator through that inner loop:

In the 2nd-to-last line, f2 is applied to the head, then cons’d with the accumulator, and that result (along with f2 and the tail) are passed to the recursive call to “loop”.  In this case, “loop” is the very last thing that happens, so the F# compiler can implement this tail-recursively.

Double-Check with Reflector

We can double-check that the F# compiler created a recursive function for the “map” case by using Reflector.  While F#-compiled-to-IL-decompiled-to-C# can be a bit verbose thanks to all of the generics and partial function application (FastFunc), it can still be seen that the map function recursively calls itself.

If the Tail Recursion Police were out, we’d be totally busted.

For the “mapTR” case, the implementation is a bit hidden behind some closures, but can be found with a little work.  The meat of the tail-recursive function is implemented with a while(true) loop! This is fantastic since it uses no stack space. The Tail Recursion Police would let us off clean on this one.

Sidenote: The List<T> type here is not the standard System.Collections.Generic.List<T>.  It is a singly-linked list that is part of the F# core libraries. In F# the Generic.List<T> is known as ResizeArray<T> since it more resembles a resizable array than a singly-linked list.

Sidenote 2: I’ve heard some things about the “.tail” IL opcode, but don’t see it popping up anywhere in this code. The while loop seems more efficient to me than a recursive call that drops the current stack frame, though. I’m not entirely sure what the relationship is between the .tail opcode is and tail recursion in F#.

Let’s walk through another example and dig into a little more detail.

Kaboom! StackOverflowException Strikes

When working on some code over the weekend, I ran into the need for a slightly different version of List.map. The “map” function has the signature “(‘a -> ‘b) -> ‘a list -> ‘b list” — that is, it takes a function that takes a ‘a and returns a ‘b as well as a ‘a list to operate on, producing a ‘b list. It simply applies the given function to each item in the list and returns a new list with the result of each function application.

What I needed, however, was a method that took a list of one type and returned a list of another type, but applied a function that accepted a list of values and produces a resulting value.  That is, I needed a function with a signature “(‘a list -> ‘b) -> ‘a list -> ‘b list”. When you think about this, I needed an algorithm that would operate on the initial list by calling a method by “snapping off” successive portions of the list, producing another list.  So, if we had a list [1;2;3;4], the mapping function would be called in succession with input lists [1;2;3;4], [2;3;4], [3;4], [4], and []. Since it’s still doing a mapping, though making the entire list (instead of just the head of the list) available to the mapping function, I decided to call it “mapl” for “map list”.

My first stab at an implementation was straightforward:

Good so far. However, it’s not tail-recursive, so let’s see if we can break it:

Kaboom! The Tail Recursion Police are already on the scene, cleaning up the remains of fsi.exe…

Tail-Recursion Tweaks and Performance

Ok, so let’s make this “mapl” function tail-recursive. I wanted to investigate 3 different approaches and compare the performance based on slight nuances between the implementations.

Here’s my code for mapl_tr1, mapl_tr2, and mapl_tr3:

You can see that we factored out an inner loop that is recursive, added an accumulator list, and made sure that the loop function call was the last operation before recursing.

• mapl_tr1: This function captures the function “f” (a closure) from within the inner loop.
• mapl_tr2: This function explicitly passes the function “f” to the inner loop to test if a closure slows things down
• mapl_tr3: This function creates tuples when passing values to the inner loop and recursing to test if tuples are faster than partial function applications

To test these functions out, I used a simple test harness:

This takes a list of the three methods (isn’t it great to pass around code as data in functional languages?), run a test by timing it and taking the average of 10 executions, then print out the results.

Wow, that’s really interesting. mapl_tr1 and mapl_tr2 are almost the same running time, but mapl_tr2 is slightly faster.  So we can conclude that the closure adds a very small amount of overhead, which isn’t surprising.  What caught me off guard is that mapl_tr3 takes more than 50% longer than mapl_tr2, owing to the constant creation of tuple objects under the hood. Looks like we have a winner, mapl_tr2!

For completeness, the implementations of time_iter and press_enter are given below:

(time_iter can be optimized so it doesn’t create a 0..n list and uses sequence expressions…)

Conclusions

F# makes it really easy to write recursive functions that succinctly express our algorithms, but care must be taken to address tail recursion so that StackOverflowExceptions aren’t encountered in production code. Also, tail-recursive functions can be further optimized by ensuring that tuple objects aren’t created at each iteration, and by explicitly passing functions to inner loops and not relying on closures.

Whenever you write “let rec”, don’t give the Tail Recursion Police reason to take you downtown…

Hope that helps someone and eliminates some of the smoke/mirrors surrounding tail recursion! 

Right on the heels of my last post about an AssemblyInfo.fs file for F# Libraries (DLLs), we can do the same thing for F# console applications with a slight modification.

The default F# console application contains a single Program.fs source file. By default, this puts everything in that file into a module named “Program”.

The entry point of an F# console application is typically the top-most code in the last .fs file of the project.  This leads to the standard F# programming pattern of the last file in the project (typically Program.fs) containing something along the lines of:

Now, to add all of the assembly metadata to the project, we need to attribute the “main ()” function call with all of the attributes.  We can’t use the “unit” operator “()” like we did in the F# Library case, since our console application actually does have an entry point that we care about.

We can accomplish this by moving the “main ()” line to the AssemblyInfo.fs file, requiring us to fully-qualify it to “Program.main ()” since it resides in the Program module.

If we add the AssemblyInfo.fs file from the previous post, it must go last, for example:

Now, in Program.fs we only have:

And at the end of AssemblyInfo.fs we have:

Just like in the library case, it would be nice if the default F# console application template included both Program.fs and AssemblyInfo.fs and included a definition for “main” to avoid any confusion as to the entry point of the application.

Hope that helps!

It’s standard practice for C# applications and assemblies to have metadata attached to the assembly specifying the version number, name, company, author, etc. Usually this information is specified in the Properties\AssemblyInfo.cs file.

However, F# libraries (by default) don’t have this assembly metadata, so you don’t know what version of a DLL you are looking at.  For example, without assembly information, MyLibrary looks like this in the Explorer window:

That’s not very helpful.

Thankfully, it’s very easy to add an AssemblyInfo.fs file to our F# library and achieve the same thing as a C# library.

Here’s the AssemblyInfo.fs file that you can copy/paste into your project.

To use it, make AssemblyInfo.fs the last file in your F# Library (DLL) project (remember – file order is important for F# projects).  If necessary, right click on the file and use the “Move Up” and “Move Down” commands.

After compiling the F# Library, it will then have all of the usual CLR metadata compiled into the assembly and show up in the Explorer window correctly:

It is very important to note that the last line of AssemblyInfo.fs is “()”.  The file won’t compile without this, since attributes (even though they are assembly-level attributes) must be applied to something.  In this case, we’re applying all of the attributes to the “nothing” placeholder in F#, called “unit”, or “()”.

It would be nice if the F# templates that ship with the F# CTP included this file by default. I guess I could always make my own template

Hope that helps!

This week at the F# for Scientists Book Club we got onto the topic of Project Euler, problem 11. 

To restate the problem:

In the 20×20 grid below, four numbers along a diagonal line have been bolded.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26x63x78x14 = 1788696.

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

We started down the path of how to extract all of the possible sequences of 4 numbers from the 20×20 grid using sequence expressions.  However, it occurred to me that pattern matching might be a good fit for this, so I decided to try out an alternative approach using pattern matching.

The first step is to create a pattern-matchable structure containing our 20×20 grid of numbers. I decided to use an “int list list” — a list of a list of integers.  This is easy enough to do if we split the text into lines, then split each line into number strings, and then convert each number string into an integer:

In F#-ese, we take the text, and “pipe” (using the |> operator) it into the String.split operation that splits the string on newlines.  This gives us a list of strings (string list) that we can then “pipe” into a List.map operation that applies the given function to each string in the list (each row).  This mapping function splits each row string on spaces and then converts each number string to an integer.  I’m using function composition here (the >> operator), since the string split happens, and then the integer conversion happens.

As we’re hunting through all of the possible 4-number combinations (left-right, up-down, diagonal-left, and diagonal-right), we need to store some information.  We need 1) the product of the 4 numbers and 2) the 4 numbers themselves.  This seems like a good place to use a tuple, where we can store two things — the product and the 4-number list.  We can write a function that takes 4 numbers and creates this tuple for us:

The signature of this method is “val makeTuple : int -> int -> int -> int -> int * int list”, which says that we take 4 integers and create an (int * int list), i.e. a 2-element tuple with an integer and an integer list.

Now we come to the pattern matching aspect of the problem.  We need to apply a 4×4 filter to the 20×20 cell array, look for 4 patterns, and then repeat the process for the remaining cells.

Pattern matching in F# can easily dissect a list into its head (first element) and its tail (whatever’s left). This is denoted as “head::tail”.  You can also match with more than one element out of the front of the list, using “h1::h2::h3::tail”. In addition, you can ignore things if you don’t want to explicitly give them a name by using the “I don’t care” symbol, _, e.g. “h1::h2::_”.  And, you can group elements together and give them a new name, for example “h1::(h2::h3::_ as tail)”.

So, here’s the code for our pattern finding algorithm:

The findPatterns function takes our cells (a list of list of integers) and performs a pattern match over them.  The syntax is a little odd at first, so I made a picture to show what is matched with what:

If the cells match the pattern (that is, a 4×4 square has been found), then the 4-length sequences are stored as a tuple, and the method is recursively called again, twice. 

The first recursive invocation is called with a new 2-d list containing the 4 tails from the previous match. In this loop, [t1; t2; t3; t4] keep getting their leftmost elements stripped out until there isn’t a 4×4 square left, in which case the pattern match fails, _ is matched, an empty “list list” ([[]]) is returned, and the recursion stops.  So basically we are walking left-to-right matching patterns and storing the results.

The second recursive invocation is called with the tail t5.  This is the input cells without the first row.  With this invocation we’re recursively walking the cells from top to bottom.

So, once we are able to find all of the patterns, then to solve the problem we just need to find the maximum value of the tuples returned:

Here we invoke findPatterns with the cells (returning a list list), concatenate that down to a list (of int * int list), and then find the maximum using the first value of the tuple (the product of the 4 numbers).

The result is:

> result;;
val it : int * int list = (70600674, [87; 97; 94; 89])

Cool!  It doesn’t take any time at all to execute on my machine — well below the “1 minute rule” for Project Euler.

I’m sure there are ways to improve this algorithm.  It uses the stack quite heavily, and the list concatenation (@ operator) is expensive. Also, storing all of the results for all combinations wastes memory — a fold would be more efficient, allowing you to compare as you move along.

Despite these potential problems, I really like this solution because it is so concise.

After the awesome F# for Scientists Book Club meeting the other night, I wanted to set up a code repository for everyone to share their code.

After some discussion on the Google Groups list, we decided to use Git instead of Subversion for the source control.  Sure, why not? Might as well try out something new.  We found GitHub.com which offers free hosting for public projects.

Installing the Git Client

I hunted around for a TortoiseSVN-esque Windows client for git, but there isn’t one (yet?).  Ah well, back to the command line with Cygwin.  I usually have Cygwin installed, but my installation on this machine is broken for whatever reason.  Thankfully I stumbled onto msysgit, an all-in-one installer.

I ran the installer, using all of the default options:

Git uses SSH under the covers to connect to the remote git repository, so we need to spend a second setting up our public/private key pairs.

Double-clicking on the “Git Bash” shortcut on my desktop brings me up to a MINGW32 command prompt.  I need to generate new SSH keys, so I did:

$ ssh-keygen.exe

This generated a few files:
~/.ssh/id_rsa = Private key
~/.ssh/id_rsa.pub = Public key

You’ll need to cat the id_rsa.pub file and copy/paste that public key (starting with the “ssh-rsa” line) into your GitHub account next.

Creating a GitHub account

Just sign up for a free Github account (pretty self-explanatory).

You’ll need to provide the SSH public key (not the private key!) to github so that you’ll have permission to commit. You can enter the key on the first screen (it’s optional), or add one once you’ve created the account.

Using Git

I just followed the directions on the fsharpbooksamples project page.

$ cd /d/OpenSource/
$ mkdir fsharpbooksamples
$ cd fsharpbooksamples/
$ git init

Here I created and edited a README.txt file

$ git add README.txt
$ git config –global user.email matt.valerio@gmail.com
$ git commit -m ‘Initial commit’
$ git remote add origin git@github.com:mattvalerio/fsharpbooksamples.git
$ git push origin master

And, that’s about it.  Note that on the last push command, it will fail if you don’t have your SSH keys set up correctly. It will complain with an error message that says “Permission denied (publickey)”.  If you set up a passphrase while generating your SSH keys, you’ll need to enter that here.

Hope that helps!

This weekend I wanted to throw together a nice sample illustrating some ideas that I was playing around with this summer. While I was out at Microsoft Research, I got turned onto Microsoft Robotics Developer Studio and the incredibly cool Concurrency and Coordination Runtime (CCR) that gives it a solid foundation.

Interacting with remote services is difficult.  WCF has made the interaction easier using the “address-binding-contact” abstractions, but this doesn’t address things like concurrency , multithreading, asynchronicity, failures, and timeouts. Writing code that handles all of the possible scenarios can be messy very quickly. ThreadPools, BeginInvoke, EndInvoke, IAsyncResult, ManualResetEvent, and friends aren’t exactly the easiest thing to get right, but if you want a responsive UI and a robust application, you must worry about all of these things.

George Chrysanthakopoulos and the creators of the CCR recognized this and have provided an amazing abstraction on top of the current threading implementations on the .NET platform. I’ve blogged about the CCR before, but haven’t really posted any useful examples that truly illustrate its power. Get ready to be blown away — I’m going to show how easy it is to write a WinForms client that accesses a remote WCF service that:

• Correctly interacts with the UI on the correct thread
• Has full responsiveness of the UI
• Caches requests to the service if necessary
• Never blocks a thread while waiting for something, performing all operations asynchronously
• Never uses the “lock” keyword

I couldn’t believe how easy it was to get everything working.

The WCF Service

I’ve just made an extremely simple WCF Service for this demo.  It has a single operation, DoSomething that takes a request and generates a response. I like the way that the DoSomethingRequest and DoSomethingResponse allow for both multiple input and output properties on the respective types, making for a cleaner interface. Apparently I’m not the only one to think this, though the motivation is grounds for another complete post.

Our WCF service is contained within a WCF Service Library. This makes it easy to reference from other projects in the solution.

The request/response classes are very straightforward:

The implementation of the service is also very simple:

The service just takes in a request (an integer) and returns a response (a string) with more text.  However, if the input is 2, then an exception is thrown, so we’ll need to be ready on the client to handle this. (We’re ignoring fault contracts now for simplicity).

I should also point out that this service has InstanceContextMod=PerCall.  This means that WCF instantiates a new instance of the UsefulService class for every call that comes in. Also, we have ConcurrencyMode=Multiple, indicating that WCF also uses a new thread for every incoming call (with a preset maximum number that I can’t remember at the moment).  What this does is essentially blow the WCF service host wide open in terms of concurrency, allowing multiple threads to interact with their own instance of the class.  Since we’re not doing anything requiring synchronized access to shared state, these settings are largely unimportant.

Note that I’m not using the CCR on the service side — not yet.  I have some examples of how to do this, but that will unfortunately have to wait for future post Now onto the client…

The WCF Client

On the client side (a WinForms project), we add a reference to the service, making sure to go into the advanced option and turn on the generation of asynchronous operations.

This automatically generates a UsefulServiceClient class that not only has synchronous methods DoSomething, but also a method/event pair that can be used to invoke the operation asynchronously:

We’ll use the method/event pair for this example and won’t worry about using the Begin/End methods.

<Sidenote>

It’s also interesting to note that our generated IUsefulService interface on the client actually has 3 methods instead of 1 (with the attributes, cruft and unnecessary namespaces removed):

We could also use the {Begin/End}DoSomething pair here (also exposed on the UsefulServiceClient) since WCF can handle the APM (Asynchronous Programming Model pattern of the framework) invocation under the covers.  I’ll dig into this in a future post when we get to using the CCR on the server side. If you’re interested, Dan Rigsby has an excellent series of posts about asynchronous WCF service implementation. I’ll talk about this more in a future post.

</Sidenote>

CCR-Compatible WCF Client Wrapper

I’m not going to go into much detail here (check out this post to get started) about the architecture of the CCR. Suffice it to say that we have our very own thread pool, the DispatcherQueue, not related in any way to the .NET ThreadPool.  We create any number of “ports” which are just strongly-typed queues that can have messages “posted” to them.  Then, we can hook up handlers that get called whenever a message gets posted to the port.  The sender and receiver are completely decoupled, and the thread which executes the handler is managed by the dispatcher.

The key thing to take away from this is that ports (aptly named) are the “interfaces” between the producer and the consumer.  So, if we want to communicate with a service, we ask it for a port with which to post incoming requests for it to operate on.  On a similar token, we can also request a reference to a port with which we can hook up a handler to be called whenever the service obtains a response.

So, we can create a wrapper class around the auto-generated WCF client class that exposes two ports — an input (request) and an output (response) port.

Well, that’s the idea anyway.  Unfortunately we’ve subtly overlooked our failure scenarios.  Another possible outcome of a call to the service is that an exception is thrown.  The CCR allows us to create a conglomerate of ports called a PortSet which allows us to specify that either of two message types can be posted there.  We need this for the output port since the outcome of our operation could either be a response or an exception. This is a great approach since the failure information is explicit — we don’t have to wonder if an exception will just “bubble up” later.

Another point that needs to be made is that the CCR operates under a message-passing paradigm which emphasizes statelessness. Every message is self-contained.  So, we could post message requests into a port and wait for message responses on another port, but because of the asynchronous nature of things, we can’t assume that the response order will match the request order.  If we need to know which request generated which response (as is the case here), we need to be more explicit. The solution isn’t difficult — we just bundle a request with its response and call it a DoSomethingContext:

This brings us to the first glimpse of our UsefulServiceWrapper class:

We notice that our wrapper inherits from CcrServiceBase, a lightweight base class that just provides a TaskQueue property that exposes a DispatcherQueue which is set in the constructor, as well as a few other convenience methods.  We need to have access to the application’s DispatcherQueue to be able to send and receive messages through the ports.

There are three ports (or Ports/PortSets to be particular) here.  The first port is the input to the DoSomething operation which takes a DoSomethingContext (in this case the Request property will have a non-null DoSomethingRequest and the Response property will be null). The second port is a PortSet of a DoSomethingContext and an Exception, indicating that there are 2 possible outcomes of the operation.  The third port is a convenience port which allows the internal workings of the wrapper class to be observed (if desired) by allowing log messages to be posted to it.

Wrapper Logic

While implementing the wrapper logic, we have one rule — NEVER block a thread while we’re waiting for WCF to do something.  If we’re not doing something constructive with the thread (a scarce resource), then let the CCR execute other code with it.

Consequently, the standard WCF client convention is completely out:

This ties up a single thread during the entire execution of the operation.  If there’s a lot of network delay, I wouldn’t be surprised if 99% of the time the thread is sitting there idle, waiting for a response. This really limits our scalability in a big way. This isn’t going to work work — we need to use the asynchronous equivalent for everything — {Begin/End}Open, DoSomethingAsync/DoSomethingCompleted, and {Begin/End}Close.

Let’s take a look at just the constructor operation.  We’re going to use an awesome feature of the CCR – CCR Iterators — that uses C# 2.0 iterators to write synchronous-looking code that executes asynchronously.  The trick is to implement a method that returns IEnumerator<ITask>.  ITask is just a “unit of work” for the CCR, and we return an enumeration.  We get to use the yield keyword inside of iterator methods.

When you think about it, iterators are methods that execute different code each time that you call them.  That is exactly why they are well-suited for doing asynchronous programming — the individual sections of the method can be executed by different threads in an asynchronous manner as they are needed. The compiler works its magic behind the scenes, actually implementing iterators as a state machine. Pretty cool stuff.

Here’s the first part of the implementation showing how we can execute the constructor and catch any exceptions:

First we create a SuccessFailurePort, just a fancy name for PortSet<SuccessResult,Exception>. Then we try to call the constructor inside of a try/catch block. If the constructor completes successfully, then we post a success result to the success/failure port.  If an exception occurs, then we post the exception to the port.  The next line is where the magic of the CCR comes in — we “yield return Arbiter.Choice(successFailurePort…)”.  Translated into english, this means: “Return this thread back to the CCR and don’t come back until EITHER a success result OR an exception gets posted to the successFailurePort. Then, when we’ve ‘joined’ up with either result, execute either of these next two anonymous methods depending on which one was posted.”  Whoa.  That’s an amazing amount of power right there, after you get used to the unfamiliar syntax.

So, If there is a successful result, a message is posted to the log and the method continues down.  If there is an exception, we post a message to the log and also post the exception to the DoSomethingOutputPort, and set the failed flag to true.  If that flag is set, then we “yield break”, indicating to the CCR that we are completely finished with this method and never expect to re-enter the iterator. When we yield break, we’re completely done.

(Bear with me — even though this looks like a lot of code, it’s boilerplate. I’ve written a T4 template for generating it.  Also, there are less verbose ways of calling things (thanks to some extension methods in the latest version) but they can be difficult to grasp without first seeing things like this. We’ll see soon that interacting with this code via the ports is a breeze, so it’s worth it to write it once and forget about it.)

Now, assuming that the constructor didn’t throw an exception, we can now open the client (asynchronously of course):

This pattern should look familiar — it is the standard method of interacting with APM code.  The trick is that the EndXXX method can always throw an exception if the operation failed, so we need to handle that in the same way as before with the successFailurePort. Notice that if we have two possible paths (e.g. success or failure) then both paths must be capable of posting something to the port to be able to continue past the Choice.

Now we can interact with the DoSomethingAsync operation.  First we subscribe to the even handler, call the method, and then wait for either success or failure:

Once again, if there was a failure then the exception is posted to the output port and we “yield break” indicating that the iterator method has completed (completely).

As the last step, we then call {Begin,End}Close:

If we make it this far in the iterator method, then we are finished and a successful result has been stored in the DoSomethingContext.  We can then post the completed context (containing both the request and the response of the DoSomething method) to the output port:

And…we’re done. Almost.

The only thing missing is how we specify that DoSomethingIterator contains all of the code to run when something is posted to the DoSomethingInputPort.  To do this, we need to “activate” a “receiver” on the input port — that is, wire up the input port so that it runs the iterator. In this case, it’s as easy as putting this in the constructor:

The TaskQueue property refers to the DispatcherQueue given to the wrapper class’s constructor.

Now that we have the verbose part out of the way, let’s take a look at how we can use our CCR-compatible wrapper class by interfacing through its ports.

The WinForms Client

Ok, now we get to the fun part. So far we have implemented a service, auto-generated a WCF proxy to the service, and created a wrapper class around the WCF proxy.  Now all we need to do is create a form to illustrate how to use our CCR WCF wrapper class.

The form is simple: 1 input text box, 1 button, and a scrolling output text box.

When I press the Send button, I want to fire off N simultaneous requests to the WCF service with the request payload counting from 1 to N. When a request comes back, I want to log some information in the bottom text box.  I also want to handle all service exceptions, and I want to be able to move the window around while the service calls are being executed without having redraw problems.

Ok, so we’re faced with an interesting scenario here: to be CCR-compatible, we need to use the CCR  DispatcherQueue (essentially a thread pool), but how can we do that when WinForms has very specific threading requirements to handle the underlying Win32 API interop (message pump, etc)?

The trick is that the CCR comes with a number of WinForms adapters that make this impedance mismatch easier to handle.  Unfortunately I didn’t find everything that I needed in the Microsoft.Ccr.Adapters.WinForms namespace, so I needed to write a little more interface code.  The result is a programming API that directly mimics a typical WinForms program.  Normally the Program.cs file contains:

However, I’ve written a CcrApplication.Run static method so that we can do this instead:

That’s not so bad.  The only trick here is that instead of passing in a Form argument to Application.Run is that we’re passing in a Func<DispatcherQueue,CcrForm> delegate.  This is just a method that takes a DispatcherQueue and returns a CcrForm.  What is this CcrForm, you ask?

It’s just an abstract base class that accepts a DispatcherQueue in the constructor and uses that queue to set everything up. The key here is that the CcrForm has a property called FormServicePort of type WinFormsServicePort that lets us interact with the form (create a new one, invoke delegates on the UI thread, and close down the form).

I modified the code from this post so that it correctly handles form shutdown. The CcrApplication.Run method just creates a DispatcherQueue and then initializes a ManualResetEvent that we can wait on to keep the main thread from exiting (otherwise our window wouldn’t even show). We also hook up to the FormClosed event on the form so that we can cleanly shut down.

The CcrForm class is also fairly straightforward, just storing the DispatcherQueue so that we can use it from the form.

The Activate method is just for convenience so we don’t need to keep typing this.TaskQueue.  The FormInvoke method also makes calling it easier (as we’ll see in a sec).

Client Logic

Ok, we’re almost there! We need to “wire up” the logic in the form:

• Whenever a message is posted to the log port, display the information in the bottom text box
• Whenever a message is posted to the service output port (successfully), display the result in the bottom text box
• Whenever a message is posted to the service output port (exception), display the exception message in the bottom text box
• Whenever the Send button is pressed, post messages to the service input port.

The first 3 are receivers, and then last 1 is a post.  We can set up the first three persistent receivers in the constructor like this:

The Log method is just a helper method that appends a line of text to the lower textbox by wrapping the code up into a delegate and posted it to the WinFormsServicePort so that it may be executed on the UI thread.

The only thing we have left is the button handler which posts new messages to the service input port:

There’s an arbitrary limit of 50 messages in there, just so you can’t go completely nuts (100,000 requests might be a bit much).

Testing

After all of that work, we can finally try things out! I set my solution so that both my WinForms project and my WCF service get started when I hit F5.

The WCF test client starts up, indicating our service is live:

Now we dial in 10 as the number of threads to start and click the Send button.  Not just once.  20 times.  I just totally wail on the Send button and watch what happens:

After about 20 seconds, all of the queued requests finally finish and all log lines get printed to the text box.  Amazingly, I was able to constantly move the window around my screen without any hiccups as all of that was going on! And, to think that all of that happened without writing a single line of lock synchronization code…

Conclusion

I hope you enjoyed this in-depth exploration into the amazing world of the CCR.  I know I sure did. I’m quickly becoming a fan of the CCR’s model of event-driven asynchronous programming, where you can define your interfaces between components and then just “wire them up” with receiver code.  It certainly makes for a clean model.

To recap, we were able to write clean code that correctly interacted with the UI thread, giving us a fully-responsive UI, were able to cache the service requests by posting them into the wrapper’s input port, and we NEVER blocked a thread while waiting for asynchronous I/O. In addition, all failure conditions were handled cleanly. The code might seem pretty complicated at first (lots of anonymous methods everywhere) but after you get used to the way things work, it’s very powerful.  The ability to write synchronous-looking code that executes asynchronously is (to put it simply) pure genius on George’s part.

One thing that I didn’t cover is the CCR’s ability to coordinate lock-style code (e.g. to access shared state).  I’ll take an in-depth look into coordination/synchronization, as well as how to use the CCR to implement asynchronous WCF services in a future post.

I’ll put up the code soon for everyone to download.

Hope that helps!

I just ran across this article by Jeff Gould explaining that Microsoft has joined the Advanced Message Queuing Protocol (AMQP) working group. This is really exciting because AMQP is an open standard with a sizable number of cross-platform implementations. Jeff makes the analogy that:

“…AMQP is to high-value, reliable business messaging what SMTP is to e-mail.”

This certainly has the potential to really change the landscape for the better (and away from the proprietary messaging systems like IBM’s MQ or Tibco’s Rendezvous). The current 0.9 specification makes mention of different scales of deployment:

• “Developer/casual use: 1 server, 1 user, 10 message queues, 1 message per second
• Production application: 2 servers, 10-100 users, 10-50 message queues, 10 messages per second (36K messages/hour)
• Departmental mission critical application: 4 servers, 100-500 users, 50-100 message queues, 100 messages per second (360K/hour)
• Regional mission critical application: 16 servers, 500-2,000 users, 100-500 message queues and topics, 1000 messages per second (3.6M/hour)
• Global mission critical application: 64 servers, 2K-10K users, 500-1000 message queues and topics, 10,000 messages per second (36M/hour)
• Market data (trading): 200 servers, 5K users, 10K topics, 100K messages per second (360M/hour)”

Wow. That’s a lot of messages, with a lot of critical applications riding on top. They are also targeting a number of different system architectures:

• “Store-and-forward with many writers and one reader
• Transaction distribution with many writers and many readers
• Publish/subscribe with many writers and many readers
• Content-based routing with many writers and many readers
• Queued file transfer with many writers and many readers
• Point-to-point connection between two peers
• Market data distribution with many sources and many readers.”

There is a C#/.NET implementation called RabbitMQ that looks extremely interesting. There is even a version compiled explicitly for .NET 3.0 with WCF bindings.  There is even a good bit of documentation. Sweet.  I really need to try this out and see how easy it is to set up a publish/subscribe system with reliable messaging.