Matthew Podwysocki's Blog

The “Anti-For” Campaign

podwysocki — Thu, 25 Jun 2009 21:38:00 PDT

Recently, there has been an effort launched called the “Anti-If Campaign” in which they deride the use of if statements and instead, focus on Object Oriented Principles in order to create more flexible designs. Now certainly, I have a sympathetic ear to this cause as I’ve seen code that literally walks off the side of the screen due to nesting of if statements. Pattern matching to me, especially at the top level of the function is actually quite beautiful in a way, such as the implementations in Haskell:

-- Haskell
lucas :: Int -> Integer
lucas 0 = 2
lucas 1 = 1
lucas n = lucas (n - 2) + lucas (n - 1)

And in Erlang, this also holds true:

% Erlang
-module(lucascalc).
-export([lucas/1]).

lucas(0) -> 2;
lucas(1) -> 1;
lucas(N) -> lucas (N - 2) + lucas (N - 1).

Simple, easy to understand and best of all, no if statements. But, instead of focus on this debate, I’d like to propose another which strikes closer to this functional programmers heart, the “Anti-For Campaign”. This is simply to say that we should create and use composable functions instead of explicit for loops. This is actually an old post I had written months ago and until now had been unfinished, but now with some inspiration, it’ll finally be done.

What and Why?

Before you throw all sorts of questions asking what and why, let me instead ask a question. When you’re writing a loop, ask yourself the question, “What am I accomplishing in this loop?” Chances are, it might be one of the following:

Query (Map, Filter, etc)
Aggregation (Sum, Count, etc)
Perform some side effect

If you’re doing more than one of those in a single loop, then well, you’re probably doing too much. In fact, Martin Fowler’s Refactoring site has a refactoring called “Split Loop” which would solve that issue. It is better for future refactorings and readability if we keep those loops pointed to do one thing, and one thing only. Better yet, we could rid ourselves of that loop altogether, and that’s what we’ll focus on here.

Looking at first two bullet points, you’ll notice most of LINQ is indeed built around those two to be able to query data as well as aggregate. The final bullet point, we perform some sort of side effect, perhaps writing to a file, printing to the console, or even perhaps sending messages.

So, what’s my problem with them? My problem is that it focuses more on the How instead of the What. Let’s look at a quick example down below of what I mean. First, we’ll attempt to find all prime numbers under 100 using C# as an example language. First in the How:

static bool IsPrime(int i) {
    var lim = Math.Sqrt(i);
    
    Func<int, bool> check = null;
    check = j =>
        j > lim || (i % j != 0 && check(j + 1);
        
    return check(2);
}

static void Main(string[] args) {
    var numbers = Enumerable.Range(1, 100);
    var output = new List<int>();

    foreach(var number in numbers)
        if(IsPrime(number)) output.Add(number);
}

The problem is that if we then want to compose another operation, well, it’s really hard to do inside of these for loops. We’re too focused on the how at this point. Instead, getting to know generics and lazy evaluation, in .NET 2.0 and beyond, we were able to write generic functions to take advantage of some functional constructs. This will give us a more declarative style that we can now focus on the what.

static IEnumerable<T> Filter<T>(
    this IEnumerable<T> items,
    Func<T, bool> predicate) {
    
    foreach(var item in items)
        if(predicate(item))
            yield return item;
}

static void Main(string[] args) {
    var numbers = Enumerable.Range(1, 100);
    
    var primes = items.Filter(x => IsPrime(x));
}

Of course we realize that LINQ already has such constructs built in, so we could rewrite the entire code above in just one statement.

var primes = Enumerable.Range(1, 100)
    .Where(x => IsPrime(x));

And what’s better is that it is composable that we could do other operations such as aggregations (sum, count, etc) without much additional code:

var primesCount = Enumerable.Range(1, 100)
    .Where(x => IsPrime(x))
    .Count();

And there you have it. We not only have a query, but also an aggregation. Try doing that with those non-composable loops! Justin Etheredge has a nice writeup as well recently on the subject.

Coping Strategies

Functional languages tend to deemphasize the use of such constructs. In fact, Haskell has neither a for loop nor a while loop, and languages such as F# and OCaml have limited support for such constructs in terms of no break and continue. We tend to look at those two in particular with suspicion due to the fact that it cannot return a value and instead it mutates state in some fashion. With that in mind, how do we cope with the fact that those aren’t available to us? Above I showed a basic concept of a filter instead of an explicit loop, but what about some other considerations?

Some things we might want to consider with some links to some of my previous posts on the subject:

Explicit Recursion
Transforming each item (Map/Select & SelectMany in LINQ)
Selecting items (Filter/Where in LINQ)
Aggregating Data (Folds/Aggregate in LINQ)

In fact, many times that people could consider using explicit recursion could instead use a fold to aggregate the data which then cuts out the issue of tail call optimization. By truly understanding the goals of LINQ as well as the concepts of functional programming, we can realize that most of the looping that we do can indeed be replaced by the above, outside of side effects of course.

Now What About Those Side Effects?

Is there a place where we draw the line and say that explicit loops are ok? Eric Lippert was recently asked about the reasoning of the lack of the ForEach extension method on IEnumerable<T>. His response was that he was philosophically opposed to such an endeavor as the whole approach is to cause a side effect. As IEnumerable<T> collections are immutable, he doesn’t believe it makes as much sense because you wouldn’t be side effecting the collection itself. Not only that, but introducing closures can complicate object lifetimes and all sorts of potential reference issues.

What about me? I understand his concerns, and in C#, I can certainly see where he is coming from. However, in F# we have such constructs readily available to us in the iter and iteri functions as shown below in F# Interactive:

> let flip f y x = f x y
- [1..10]
-   |> List.map((*) 2)
-   |> List.filter(flip (%) 3 >> (=) 0)
-   |> List.iter(printfn "%d");;
6
12
18
> [1..10]
-   |> List.map((*) 2)
-   |> List.filter(flip (%) 3 >> (=) 0)
-   |> List.iteri(printfn "%d\t%d");;
0       6
1       12
2       18

Outside of logging, writing to the console and such are rare in functional programming, so once again, I can certainly understand the concern.

Conclusion

I hope by going through some basic scenarios that we will indeed question our code the next time we see that we are writing that explicit loop with a for and a while. With a tool chest filled with such functions as transforming every item, to filtering content, to aggregating data and so on, we can realize that we can create composable solutions instead of creating mutable collections or mutable variables and aggregating to them which are not as much. So, come and join me in the “Anti-For Campaign”.

Providing Safe Alternatives

podwysocki — Wed, 24 Jun 2009 06:18:00 PDT

When I was reading through Real World Haskell, I was struck several times by the mention of providing safe function alternatives. The idea is to provide a function that in all cases returns a value as well as the one which is meant to accept valid input and throw exceptions should that contract be violated. There is a real performance consideration to be taken into account as a function which repeatedly throws exceptions as logic will tend to overwhelm a system and slow it down significantly. Imagine if you will an application which reads a large directory to check each file for an X509 certificate, whether it has one or not, and it throws an exception if one is not present. The problem of course is there is no way to determine whether a file was signed at the time using the .NET class without resorting to P/Invoke (my favorite).

Recently on Twitter, there was talk finally of the inclusion of Guid.TryParse in .NET 4.0, yet somehow, Enum.TryParse has not been addressed yet (gee, we’re consistent here). The idea is to provide a way of determining whether the string is a Guid format without throwing an exception, and instead returning a flag indicating success and an out parameter with the value which is set to the value if there is success, else the default value. Before we dig any further, let’s look at some terminology.

Partial Versus Total Functions

To get some terminology straight, let’s talk about partial functions versus total functions. Partial functions are those functions which only return values for a defined subset of valid inputs, as throwing an exception is not considered a return value. On the other hand, functions that return valid results over the entire input are considered to be total functions. Let’s look at a quick example of what that means in F# interactive, the first being a partial function and the latter being a total function.

> open System.Linq;;
> ([] : int list).First();;
System.InvalidOperationException: Sequence contains no elements
   at System.Linq.Enumerable.First[TSource](IEnumerable`1 source)
   at <StartupCode$FSI_0003>.$FSI_0003.main@()
stopped due to error
> ([] : int list).FirstOrDefault();;
val it : int = 0

We see by the above that the First() function is a partial function because it only has defined behavior for non-empty collections, whereas FirstOrDefault() has defined behavior for empty lists and returns the default value for the given generic type. When we’re writing our code, we better know which one we’re dealing with as default values can cause unintended consequences. Without proper tests around these calls, this can be hard to manage.

Mitigating these partial functions with calls to such things as the Count() extension method is not necessarily the answer either. When dealing with non-lazy lists such as an array or a List<T>, then such things as the number of items in our collection is well known and part of the state. In the case of the lazy sequence, this is not the case, so any call to Count() would cause an evaluation of all items in the list, which could lead to unintended consequences. So, if we’re chaining together 4 partial functions together, we could be doing something wrong. All in all, total functions should be preferred usage, but of course within reason.

Can We Do Better Than Try?

Going back to one of the original points, can we do better than the standard Try (Parse/GetValue/etc) pattern that is pervasive throughout .NET code? After all, it tries to do two things at once, and the success flag can be missed if one so chose. F# decided to take a slightly different angle to this problem by returning the success flag and the value as a pair tuple. Such an example would be like this memoize function below:

open System.Collections.Generic

let memoize f = 
  let t = new Dictionary<_,_>()
  fun n ->
    match t.TryGetValue(n) with
    | (true , value) -> value
    | (false, _    ) -> 
        let res = f n
        t.Add(n, res)
        res

What we’re doing above is calling the TryGetValue method which takes a key and returns a success flag as well as the out parameter for the value (set if there is success). F# automatically creates a pair tuple for us which we can then pattern match against to take appropriate action. Unfortunately, for this go around at least, C# does not treat tuples as first class data types, so a solution like this exclusive to F# at this time. Overall, a much cleaner design, but maybe there’s another option?

Maybe there’s an Option…

Instead of dealing with the clumsiness of the above code, I would much rather solve this in a clean way using the F# Option type. This allows us to definitively specify whether we have a value or not. Oh great you say, another version of null. Not quite, as sometimes null can be a value… More to the point, we can have a universal solution to having a value without having to resort to the Nullable<T> or reference type null-ness nonsense. Simply put, the Option type is no more than the following:

type Option<'a> =
  | Some of 'a
  | None

You’ll notice two constructors for the Option type, the Some which takes a value, and the None which takes no parameters. Now, using this to extend the Dictionary class much like the F# Map class, we can add a function which returns an Option type whether we have a value or not.

type System.Collections.Generic.Dictionary<'k,'v> with
  member this.Lookup(k:'k) =
    match this.TryGetValue(k) with
    | (true , value) -> Some value
    | (false, _    ) -> None

Then we can rewrite our memoize function to utilize this in a cleaner fashion using the Option type for pattern matching purposes to show our true intentions of whether we have a value or not.

let memoize f = 
  let t = new Dictionary<_,_>()
  fun n ->
    match t.Lookup(n) with
    | Some v -> v
    | None   -> 
        let res = f n
        t.Add(n, res)
        res

Much cleaner and shows better intent on our part.

Conclusion

How far do we take this? After all, making full functions everywhere sometimes isn’t feasible as we want to constrain our system. Adding both partial and full implementations might just clutter up our entire API. With this comes balance, but there are certainly places where this comes into play such as parsing values, querying values from collections and so on. Could Code Contracts in .NET 4.0 help us here in terms of statically verifying that we’re not failing on a chained partial function? We’re not quite finished here with this discussion as I’ve yet to cover the many values of null.

F# – Async Running with Continuation Scissors

podwysocki — Fri, 19 Jun 2009 23:09:00 PDT

As you may have noticed, I’ve been covering a bit about concurrency on this blog lately, and for good reason. Between Axum, Erlang, Scala and F#, there is a lot to explore with actor model concurrency, task based concurrency, data parallel applications and so on. In the next couple of months, I have some talks coming up on concurrency and in particular with F#. I’ve been covering a bit of that with F# and mailbox processing, but I wanted to step back a bit into the asynchronous workflows and hitting against a well known API.

In this case, let’s walk through a simple example of using the Twitter HTTP API to get a user timeline using F# asynchronous workflows. Best of all, I’ve done all of the above code without ever once opening up Visual Studio and instead using the power of a simple text editor and F# interactive, I’m able to be quite productive. It certainly makes me rethink my utter dependence on certain tools…

Give me some tweets… eventually, when you get around to it

In order to get started, we need some helpers when dealing with LINQ to XML. In a previous post, I talked about the need for such a thing due to the lack of implicit operator support in F#. We can use the same operator that we had before such as the following:

let inline implicit arg =
    (^a : (static member op_Implicit : ^b -> ^a) arg)

let (!!) : string -> XName = implicit

Alternatively, we could look at utilizing the XNamespace as well due to it also having an implicit operator to convert from a string. This is helpful as it has a defined the op_Addition which allows us to add an XNamespace to a string to create an XName. To take advantage we could add an additional operator to take care of this. Below is a simple session of F# interactive to show how it might work:

> let (!?) : string -> XNamespace = implicit;;
val ( !? ) : (string -> XNamespace)

> (+) !?"";;
val it : (string -> XName) = <fun:it@205>

> !?"" + "foo";;
val it : XName = foo {LocalName = "foo";
                      Namespace = ;
                      NamespaceName = "";}

If you’ll notice above, I curried the XNamespace implicit operator function and sure enough it recognizes it needs a string in order to produce an XName. Now that we’ve defined our helpers, let’s start looking at how to get a user’s timeline in Twitter. We’ll need to define a holder for our status data as well as the URL we will be using to post data.

type UserStatus = { UserName : string; ProfileImage : string; Status : string; StatusDate : DateTime }

let timelineUrl = "http://twitter.com/statuses/friends_timeline.xml"

We’re interested at this point just of the user name, their image file location, their status and the date of the tweet. Now let’s move onto retrieving and parsing the data.

let parseDocument xml =
  let document = XDocument.Parse(xml)
  document.Root.Descendants()
    |> Seq.choose(fun node -> 
         if node.Element(!! "user") <> null then
           let status = HttpUtility.HtmlDecode(node.Element(!! "text").Value)
           let image = node.Element(!! "user").Element(!! "profile_image_url").Value
           let userName = node.Element(!! "user").Element(!! "screen_name").Value
           let statusDate = DateTime.ParseExact(node.Element(!! "created_at").Value, 
                                                "ddd MMM dd HH:mm:ss +0000 yyyy", 
                                                CultureInfo.CurrentCulture)
           Some { UserName = userName; ProfileImage = image; Status = status; StatusDate = statusDate}
         else None)  

let getUserTimeline userName password =
  async { let request = WebRequest.Create timelineUrl :?> HttpWebRequest
          do request.Credentials <- new NetworkCredential(userName, password)
          
          use! response = request.AsyncGetResponse()
          use reader = new StreamReader(response.GetResponseStream())
          let! xml = reader.AsyncReadToEnd()
          
          return parseDocument xml
        }

In the above code, we create a WebRequest, setting the credentials through Basic Authentication. We’ll cover this approach for now with some attention to OAuth at some point in the relative near future. After setting the identity, we get the response stream and read it to the end. This gives us XML to parse and by using LINQ to XML, we’re able to iterate through each node, and if the user node is not null then we parse out each element for which we’re concerned.

Now that we have the ability to do some asynchronous behavior, what do we do about it? In previous posts, I’ve taken the road of running these operations in parallel, which then runs all instances and returns an answer. But, if we’re only executing one instance, how do we enlist in asynchronous behavior overall? To illustrate, I’ll create a simple Windows Forms application to display the tweets in a textbox and have a refresh button to call the above function to repopulate our textbox. First, let’s create the basic skeleton:

let form = new Form(Visible=true, TopMost = true, Width=500, Height=300)

let status = new TextBox(Multiline=true, ScrollBars=ScrollBars.Vertical)
form.Controls.Add status
status.Width <- 400
status.Height <- 300

let refresh = new Button(Text="Refresh")
form.Controls.Add refresh
refresh.Left <- 410
refresh.Top <- 10

Now that we have a basic skeleton, let’s add the behavior to the button to refresh our textbox. To do this, we simply add a handler to the button click event. In there, we will call Async.RunWithContinuations which gives us the ability to handle not only the successful case, but also should an exception be thrown or some form of cancelation occurs. Before we look at the implementing code, let’s look at the signature of RunWithContinuations:

> Async.RunWithContinuations;;
val it :
  ('a -> unit) * (exn -> unit) * (OperationCanceledException -> unit) *
  Async<'a> -> unit = <fun:clo@0-42>

What this tells us is that it takes a success continuation as the first argument, the exception continuation as the second argument, the cancelation continuation as the third, and then finally the asynchronous operation. This allows us to uniquely handle each type of event, should they occur. In this case, our success continuation should populate the textbox, whereas both the cancelation and the exceptional case should show a message box containing the exception.

refresh.Click.Add
   (fun args ->
      status.Text <- ""
      Async.RunWithContinuations(
        (fun res -> 
           res |> Seq.iter(fun item -> status.Text <- sprintf "User: %s - %s\r\n\r\n%s" item.UserName item.Status status.Text )),
        (fun exn -> MessageBox.Show(sprintf "An error occurred: %A" exn) |> ignore),
        (fun cxn -> MessageBox.Show(sprintf "A cancellation error ocurred: %A" cxn) |> ignore),
        (getUserTimeline "username" "password")))

As you can see, the behavior is rather straight forward to define handlers for our three cases. Lastly, we provide our credentials to the getUserTimeline function and then when the button is clicked, we’ll get results much like the following screenshot.

Then we can keep pressing the refresh button and then asynchronously, it will handle the behavior appropriately, either in success or in failure.

Conclusion

This is a pretty simply and naive application, but it can show how you can take advantage of asynchronous behavior using the Async Workflows in F#. By being able to have the F# libraries handle the exceptions and cancelation, a major source of errors is reduced by quite a bit. Giving us the power then to handle each one of these scenarios, either in success, failure or cancelation is a great concept. There is still more yet to be covered including Futures and the inclusion of the Task Parallel Library as well as other adventures into Twitter and Bing APIs.

Revisiting Memoization

podwysocki — Thu, 18 Jun 2009 08:05:00 PDT

After revisiting the Haskell Wiki recently, I wanted to look at memoization again for a brief second after talking about it a while ago. In particular, there were two competing ideas, one around using a generic dictionary/map for storing the memoized values, the other using a lazy list approach. I wanted to briefly look into those as possible solutions.

The Baseline Approach

Let’s take a baseline approach, and instead of using the trite Fibonacci sequence, let’s use the Lucas Sequence instead. It’s a slight variation on the theme, and enough to avoid that dreaded function. The baseline should produce the following sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123

It might be implemented something like this:

let rec lucas = function
  | n when n = 0I -> 2I
  | n when n = 1I -> 1I
  | n -> lucas (n - 1I) + lucas (n - 2I)

You’ll notice that F# cannot handle BigInt values as literals like you can for integers and other primitives, but can be easily worked around by using a when clause in the pattern. When we run the aforementioned function in F# interactive, we see that we get the expected results.

> lucas 2I;;
Real: 00:00:00.003, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : bigint = 3I

The problem with the above function is that when dealing with larger numbers, and calling this function repeatedly, you have to take a rather large performance hit each time. And worse yet, when dealing with those larger numbers say greater than 30, the function just may hang. We can solve this through a process called memoization, which I’ve talked about before. The main idea is to cache all values that we’ve seen before for quicker retrieval instead of calculating the value each and every time.

The LazyList Approach

There are two ways I’ll cover memoization here, one using a lazy list and the other using the dictionary approach. First, let’s look at how we might be able to use a list to store those values we’ve already calculated. Let’s first look at the Haskell implementation which is similar to the Haskell Wiki example.

memoized_lucas :: Int -> Integer
memoized_lucas =
  (map lucas [0 ..] !!)
  where lucas 0 = 0
        lucas 1 = 1
        lucas n = memoized_lucas (n-2) + memoized_lucas (n-1)

The approach here is to perform a map of the lucas from 0 to infinity and taking the nth value. Since this is partially applied, we need to wait on the last value to say which value we need. When we run this through GHCi, we can calculate the 1000th Lucas number rather easily with me omitting the result and only checking the time:

*Main> memoized_lucas 1000
(0.03 secs, 0 bytes)

Not only that, but the performance is rather good. Any subsequent calls to this function should now be memoized such as the following call:

*Main> memoized_lucas 1000
(0.00 secs, 0 bytes)

Now, how would we apply this to F#? Can we get the same results as a lazy language? If we switch over from using a list to a LazyList, the answer is yes, and the performance will be close. First, we need to define the nth function which returns the value at the index specified. Using pattern matching, we can then return the appropriate value, or recurse again. We could use Seq.nth, but this may be more efficient.

module LazyList =
  open Microsoft.FSharp.Collections.LazyList

  let rec nth list index = 
    match list with 
    | Cons(h, t) when index >= 0 -> 
        if index = 0 then h else nth t (index - 1)
    | _ -> invalidArg "index" "the index was outside the range of elements in the list"

Now that we’ve defined our nth function, it’s time to define our memoized Lucas function. The logic is the same as above, and I’ve introduced a new operator to get the nth value which could be used as an infix operator. The problem is that F# currently does not allow for the infix operator to be in the middle during partially applied functions, so instead I have to define it in the beginning.

open System
open Microsoft.FSharp.Math
let (<!>) s (n:bigint) = LazyList.nth s (int n)

let rec memoized_lucas : bigint -> bigint =
  let lucas = function
    | n when n = 0I -> 2I
    | n when n = 1I -> 1I
    | n -> memoized_lucas (n - 1I) + memoized_lucas (n - 2I)
  (<!>) (LazyList.map lucas (seq {0I..new BigInt(Int32.MaxValue)} |> LazyList.of_seq))

This is a rather clumsy approach in some ways as we’re downcasting our bigint value to an integer, so in reality, we’re only able to get values up to Int32.MaxValue, which in most cases, should be ok. Let’s look at the performance of this in the same way we did above:

> memoized_lucas 1000I;;
Real: 00:00:00.092, CPU: 00:00:00.093, GC gen0: 15, gen1: 0, gen2: 0

You’ll notice that we are taking a slight performance penalty in terms of our Generation 0 memory in the GC. Any subsequent calls are memoized given the following results:

> memoized_lucas 1000I;;
Real: 00:00:00.001, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0

Let’s kick it up a notch to see what kind of penalty we may pay should we calculate the 10,000th Lucas sequence number:

> memoized_lucas 10000I;;
Real: 00:00:07.922, CPU: 00:00:07.815, GC gen0: 1511, gen1: 356, gen2: 1

Ouch! But, there is another approach that we can use and that I’ve shown before using the generic dictionary to store our values.

The Dictionary Approach

The generic dictionary approach is another approach rather than using the lazy list approach. We simply create a dictionary outside of our inner function which stores these values from our inner Lucas sequence function.

open System.Collections.Generic
let rec memoized_lucas' : bigint -> bigint =
  let t = new Dictionary<_,_>()
  let rec lucas n =
    match t.TryGetValue(n) with
    | (true , res) -> res
    | (false, _  ) ->
      match n with
       | n when n = 0I -> 2I
       | n when n = 1I -> 1I
       | n ->
           let res = lucas (n - 1I) + lucas (n - 2I)
           t.Add(n, res)
           res
  fun n -> lucas n

The code itself is rather self explanatory. We have the outer dictionary to store our values, then we have the inner function to calculate the value at the nth index. We then determine whether it is in the dictionary and, if so return it, else calculate, add to the list and then return. You’ll notice that we return not the literal value of the calculation, but instead a function which allows us to specify the nth at a later time. This is important!

Looking at the performance, we’ll notice the following:

> memoized_lucas' 1000I;;
Real: 00:00:00.006, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
> memoized_lucas' 1000I;;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

You’ll notice that the first calls is less expensive than the lazy list approach and has less impact on Generation 0 of the GC. Any subsequent calls, as above will be nil. But once again, let’s ratchet up the number to 10,000 much as we did above:

> memoized_lucas' 10000I;;
Real: 00:00:00.047, CPU: 00:00:00.062, GC gen0: 1, gen1: 1, gen2: 1

You’ll notice a drastically less performance hit than the above solution.

Conclusion

If nothing else, it was an interesting exercise in seeing different ways of memoization in action and what kind of performance penalties you may pay along the way. Now back to your regular programming…

F# – Duck Typing and Structural Typing

podwysocki — Thu, 11 Jun 2009 09:57:00 PDT

As you may have noticed on this blog lately that I’ve been focusing on Asynchronous Workflows. In those adventures, I’ve been taking well known APIs such as Twitter, Bing, among others and seeing what I can do with them. In this instance, when using LINQ to XML, I’ve run into a slight syntax problem.

The Problem with LINQ to XML

The syntax problem I had revolves around the retrieval of an XElement from the given XContainer. The signature of this is as follows:

public abstract class XContainer : XNode {
    public XElement Element(XName name);
}

But, what you may not realize is that there is an implicit operator which allows us to implicitly convert a string to an XName with little effort such as this:

public sealed class XName : IEquatable<XName>, ISerializable {
...
    public static implicit operator XName(
        string expandedName);
}

This allows us to use a string instead of an XName when specifying which element name we want, including namespace if desired, rather easily.

var document = XDocument.Parse(xml);
var statuses = document.Root.Descendants()
    .Select(node => node.Element("text").Value);

Unfortunately for us, this behavior does not work in the current F# release.

> document.Root.Descendants() 
-   |> Seq.map(fun node -> node.Element("node").Value);;

stdin(5,65): error FS0001: This expression has type
        string
but is here used with type
        XName

It does not recognize this implicit operator. What options do we have around this? One simple answer might be just a simple function that does the conversion for us, such as this:

> let ( !! ) : string -> XName = XName.op_Implicit;;
val ( !! ) : string -> XName

> let xFoo = !!"foo";;
val xFoo : XName = foo

What we’re now able to do is convert at will using the !! operator, or what I call the “Convert Dammit” operator. But, there is another solution worth exploring that is a bit more generic through the use of duck typing.

Duck Typing to the Rescue?!?

For those unfamiliar with the term duck typing, it is a style of dynamic typing in which the object’s current set of methods, properties, etc, determines its validity instead of its inheritance chain. In F#, we have the ability to use this mechanism to use this to our advantage to create generic functions. For example, let’s take the implicit operator example from above and use duck typing instead of the direct call to the XName class.

// Longhand
let inline implicit< ^a,^b when ^a : (static member op_Implicit : ^b -> ^a)> arg =
  ( ^a : (static member op_Implicit : ^b -> ^a) arg)
  
// Shorthand - let the compiler do the work
let inline implicit arg =
  ( ^a : (static member op_Implicit : ^b -> ^a) arg)

The two above statements are syntactically the same, although in the latter version, I don’t have to clutter up my declarations as much and instead let the compiler type inference magic do its work. From here on out, I’ll use the shorthand unless the longhand doesn’t quite work out. What you’ll notice is that I have a requirement for my ^a generic to have a restriction that it must have the implicit operator declared. Then we can execute said operation by passing in our argument. I can rewrite the convert dammit operator then to look something like this:

open System.Xml.Linq
let (!!) : string -> XName = implicit

let xFoo = !!"foo" // Our new XName

Now you can see here that I didn’t explicitly have to call anything on XName as I let the implicit operator do the work for me. Best of all here is that it’s now statically typed to that any call to implicit must have that operator defined on it, else it will not compile.

But, let’s not stop there, you can continue on all sorts of tangents. What about functions which have more than one argument? Let’s take the addition operator. Could we use duck typing in our favor for this? Although it’s not recommended, the answer is yes.

> let inline add arg1 arg2 = 
-   ( ^a : (static member op_Addition : ^a * ^b -> ^a) (arg1, arg2))
val inline add :
   ^a ->  ^b ->  ^a when  ^a : (static member ( + ) :  ^a *  ^b ->  ^a)

> open System;;
> let addedTime = add DateTime.Now (TimeSpan.FromSeconds 5000.);;
val addedTime : DateTime = 6/11/2009 1:00:32 PM

The reason why it’s not recommended is that a lot of primitive types are implicitly augmented with this operator such as int, float, etc, so this would not work for those plus not work on string as well since dynamic invocation is not allowed on this particular instance.

This is useful though in other scenarios. Take for example extracting a Name property from a given class. Once again, using the methodologies from above, it’s rather simple:

let inline getName arg =
  ( ^a : (member Name : string) arg)
  
open System
open System.IO
let fName = getName (new FileInfo("fsi.exe"))
let dName = getName (new DirectoryInfo(Environment.CurrentDirectory))

What about multiple restrictions? That’s not too difficult either. Let’s do the canonical Duck example with a little twist. First, we will define the overall function which will extract the Flying and Walking state of a given class.

let inline flyAndWalk arg =
  let flying = ( ^a : (member Fly : unit -> string) arg)
  let walking = ( ^a : (member Walk : unit -> string) arg)
  (flying, walking)

And now we can define our classes which have the methods which have our interest such as the Fly and Walk methods. We execute each of these, obtain the result and finally return the results of each as a tuple. Now, let’s define two classes below of a Duck and an Eagle.

type Duck() =
  member this.Swim() = "paddling"
  member this.Fly() = "flapping"
  member this.Walk() = "waddling"
 
type Eagle() =
  member this.Fly() = "soaring"
  member this.Walk() = "creeping"
 
let (eFly, eWalk) = flyAndWalk (new Eagle())
let (dFly, dWalk) = flyAndWalk (new Duck())

Our final result will be rather predictable as you might imagine. Just as well if we put a Penguin class which contains no fly, well, then this class won’t compile as shown below in F# interactive:

> type Penguin() =
-   member this.Walk() = "waddle"
-   member this.Swim() = "swimming";;

type Penguin =
  class
    new : unit -> Penguin
    member Swim : unit -> string
    member Walk : unit -> string
  end

> let (pFly, pWalk) = flyAndWalk(new Penguin());;

  let (pFly, pWalk) = flyAndWalk(new Penguin());;
  -------------------------------^^^^^^^^^^^^^

stdin(84,32): error FS0001: The type 'Penguin' does not support any operators na
med 'Fly'

As you can see, it’s a rather powerful concept, when used in moderation, can help you solve some interesting problems such as implicit operators as well as other scenarios.

Structural Typing

There is a concept that is prevalent in languages such as OCaml, ML, and Scala for Structural Typing as opposed to Duck Typing. This is a concept in which compatibility and equivalence is based upon the type’s structure and not the explicit declarations as I’ve had above. Equivalence is then measured by the structural sameness between the two even though they may be nothing more than anonymous objects.

In F#, we can accomplish this in a sense through the use of the record type quite easily. For example, we can define a class that has two properties and then check for sameness between them.

> type Foo = { X : int; Y : int};;

type Foo =
  {X: int;
   Y: int;}

> {X=32;Y=45} = {X=32;Y=45};;
val it : bool = true

Normally, given that these are reference types and not standard structures, they shouldn’t ordinarily equate one to another automatically, but F# through the use of structural typing, does allow for this. The same also applies for Discriminated Unions as well such as the following:

> type DU = A of string | B of int;;

type DU =
  | A of string
  | B of int

> B 42 = B 42;;
val it : bool = true

Once again, since they are reference types, they shouldn’t equal each other, but with F#, they do, through the use of structural typing.

Conclusion

Through the use of structural typing and duck typing, we realize how flexible the F# language really is. This gives us the ability to be creative in how we solve our problems generically in specialized cases such as our LINQ to XML example from above. Now that F# is a full citizen in the .NET space with Visual Studio 2010, it’s even more exciting about what we can do with the language.

Axum – Ping Pong with Ordered Interaction Points

podwysocki — Wed, 03 Jun 2009 23:22:00 PDT

UPDATE: Removed code and explained that what I had was not intended behavior

After a slight diversion into F# mailbox processing, it’s time to come back to talk a little bit more about Axum. In our last Axum post, we discussed using dataflow networks to clean up our canonical Ping-Pong example. This time, we’ll try another approach using ordered interaction points.

A Little Housekeeping

Before we get started with our full demonstration, let’s take a brief look at some concepts that will come into play for this solution. In our previous example using data flow networks, we a shared-nothing approach between these two agents. This time, let’s introduce the concept of domains. A domain in Axum allows for a group of agents to safely share data while shielding this state from the outside world. Like normal classes, domains can have such things as fields and methods, but also, we can declare agents. We’ll discuss how this comes into play later on in the post.

domain A {
    private string fieldName;
    ...
}

Another key concept to understand is reader and writer agents. Typically, when dealing with shared state of some sort, we have a notion of a reader-writer lock. This synchronization technique allows access to the shared state as one to many readers or a single writer to ensure consistency of that shared resource. Agents in Axum also follow this notion where a reader agent is only allowed to read shared state and a writer agent can both read and write to domain state.

domain A {
    private string fieldName;
    
    public reader agent A1 { ... } // Can read fieldName
    
    public writer agent A2 { ... } // Can read/write fieldName
}

One more concept that needs to be covered before our solution is the idea of hosts. By using a host, we are able to associate an agent’s type with a particular instance in the domain. For example when we look at the following code, what we’re doing is when someone asks for our A1 domain with an address of myA1, we attach it to the current domain and then return the associated C channel endpoint.

Host<A1>("myA1");

We can connect to this host then through a mechanism such as the following:

var chan = new C("myA1");

Bringing this all together, let’s look at the Ping-Pong example through these eyes.

Getting to the Solution

In this solution, we’ll introduce the aspect of ordered interaction points. This is an interaction point that acts as both a source and a target and the keyword being ordered which means that the order of messages is preserved. To declare one, use the OrderedInteractionPoint<T> class such as the following:

var ip = new OrderedInteractionPoint<int>();

Now, let’s get to our solution. The main application is no different, but where we will find differences is the interaction between the Ping and Pong agents. As the code for that part hasn’t changed, let’s focus on the interaction between the ping and pong inside our domain. First, let’s define the domain and we’ll call it the PingPongDomain (imaginative, I know). In this domain, we need to set up the hosting for the Pong agent at the “Pong” address as well as the ordered interaction points for the ping and the pong.

public domain PingPongDomain
{
    public PingPongDomain()
    {
        Host<Pong>("Pong");
    }
    
    OrderedInteractionPoint<Signal> ping = new OrderedInteractionPoint<Signal>();
    OrderedInteractionPoint<Signal> pong = new OrderedInteractionPoint<Signal>();

Once we have this defined for our domain, our Ping and Pong agents inside this domain will have access to these points. Since the Ping agent will ultimately both read and write messages, but using the immutable data type as the message type, we need not define it as a writer, but instead as a reader. Let’s define that below.

    public reader agent Ping : channel PingPongStatus
    {
        public Ping()
        {
            PrimaryChannel::HowMany ==> Process;
        }
        
        private Signal Process(int iters)
        {
            // Create pong
            var chan = new PingPong("Pong");

           // Send pings and receive pongs
           for (int i = 0; i < iters; i++)
           {
               ping <-- Signal.Value;
               receive(pong);
               Console.WriteLine("ping received pong");
           }

            chan::Done <-- Signal.Value;
            return Signal.Value;
        }
    }

You’ll notice that our code doesn’t look too much different than our previous example, except for connecting to the PingPongChannel with the “Pong” address that we defined in our domain above. The other change is that we are sending a message on the ping ordered interaction point and receiving a message on the pong instance.

Moving along to our Pong agent, once again, the code does not deviate much. But, as we are reading and writing our domain state by sending messages that are immutable, we could declare ourselves as a reader agent. We will continuously receive messages either on the ping ordered interaction point or we will receive a message on the Done port on the primary channel. The code will look something like the following.

    public reader agent Pong : channel PingPong
    {
        public Pong()
        {
            while (true) receive
            {
                from PrimaryChannel::Done:
                    return;
                from ping:
                    Console.WriteLine("pong received ping");
                    pong <-- Signal.Value;
                    break;
            }
        }
    }

Now that we have a solution, but, unfortunately due to a bug, this doesn’t work because the compiler cannot distinguish whether the state is immutable or not. But, we can get it to run with an escape hatch.

Being Unsafe in a Safe Way

As I stated before, Axum does have a notion of an escape hatch when it comes to code that allows you to execute code that might modify shared state through the use of the unsafe keyword. Most times it’s better to be safe than sorry in this regard, but in this example, it fits quite well. You can think of this unsafe escape hatch much like the Haskell unsafePerformIO function. This function in Haskell is the back door into the IO monad which allows an IO computation to be performed at any time. And like our unsafe keyword, in order for this to be safe, we should be free of side effects and not dependent upon the environment.

With this in mind, let’s rewrite the example using the unsafe construct. First, let’s look at the Ping agent and how we might make that a little unsafe, but yet fully operational:

public agent Ping : channel PingPongStatus
{
    public Ping()
    {
        PrimaryChannel::HowMany ==> Process;
    }
    
    private Signal Process(int iters)
    {
        // Create pong
        var chan = DefaultCommunicationProvider.Connect<PingPong>("Pong");
        unsafe
        {
            // Send pings and receive pongs
            for (int i = 0; i < iters; i++)
            {
                ping <-- Signal.Value;
                receive(pong);
                Console.WriteLine("ping received pong");
            }
        }
        chan::Done <-- Signal.Value;
        return Signal.Value;
    }
}

By simply wrapping our for loop in the unsafe block, we are able to send messages to our ping ordered interaction point and receive from our pong ordered interaction point where we weren’t allowed to in the above example. The same applies for our Pong agent as well. We can wrap the while loop receiving messages in an unsafe block so that we can receive from the ping ordered interaction point and then send a signal to the pong ordered interaction point.

public agent Pong : channel PingPong
{
    public Pong()
    {
        unsafe 
        {
            while (true) receive
            {
                from PrimaryChannel::Done:
                    return;
                from ping:
                    Console.WriteLine("pong received ping");
                    pong <-- Signal.Value;
                    break;
            }
        }
    }
}

Running our sample, we get our expected results. You can find the complete source code to this example here.

Conclusion

Unlike Erlang and other shared-nothing messaging approaches, Axum allows for shared domain state through tightly controlled access. By doing so, we keep the safety aspect of messaging through such notions of a reader-writer lock. Of course, there is an escape hatch for those who truly understand their application and the ramifications of what they are doing. As you can see, Axum has a wide array of solving even the most simple and canonical examples of actor model concurrency. There is still more yet to cover including asynchronous behavior and an exploration of the Auction example that I gave in F#.

Download it today, use it in anger and give the team feedback as to help shape what actor model concurrency might look like on the .NET platform.

[ANN] DC ALT.NET – 6/10/2009 – Evan Light on BDD

podwysocki — Tue, 02 Jun 2009 20:55:00 PDT

The June installment of DC ALT.NET will be on June 10th, 2009 from 7-9PM. Stay tuned to our mailing list to stay up to date with the happenings of the group. We’ve moved up the schedule just a little bit to accommodate our presenter, who will be attending Ruby Nation later that week.

We in the DC ALT.NET group are continuing our back to essentials series with our previous sessions on TDD, Refactoring and Pair Programming. This month, we have Evan Light to facilitate a discussion on Behaviour (note the u) Driven Development (BDD). Evan recently gave a talk at Scotland on Rails on the subject and we’ll discuss even further on the following items:

The Whys of BDD
How to BDD
BDD Antipatterns

Not only will we discuss the terminology and theory behind it, but also some of the frameworks that are available. Note that Evan is a Rubyist at heart, so for many it’ll be a new and hopefully enlightening experience.

Below are the details:

Date/Time: 6/10/2009 – 7-9PM

Location:

The Motley Fool
2000 Duke Street
Alexandria, VA 22314

When Side Effects and Laziness Collide

podwysocki — Tue, 02 Jun 2009 09:34:00 PDT

While working on a side project recently, I came to rediscover some of the consequences of one of my earlier posts on “Side Effects and Functional Programming”. It’s important that we realize that when we are creating our programs to beware of lazy evaluation and side effects.

Adding a Wrinkle

Consider the following example. We need to be able to get the stream data from a given web request for a given URL. From there, we will take the stream of data and read each line and return it as a collection. Typically if we’re going to do this through F#, we’d use a sequence expression to lazily read through each line and return it as an IEnumerable<string>. But, let’s add an extra wrinkle to this. What if we want to do this in a non-thread blocking asynchronous scenario? This adds an extra wrinkle to this in terms of managing the lifetime of our objects. We might write the code such as the following:

open System.IO
open System.Net

let getStreamData (uri:string) =
  async { let request = WebRequest.Create uri 
          let! response = request.AsyncGetResponse()
          
          return seq { use stream = response.GetResponseStream()
                       use reader = new StreamReader(stream)
                       while not reader.EndOfStream do yield reader.ReadLine() } 
        }

What we’re doing is putting a sequence expression inside of an asynchronous expression. We must bind the response outside of the sequence expression due to the fact that we are doing this in an asynchronous fashion. Once inside a sequence expression, a bind has a different meaning. But, there’s a problem with this code. Can you spot it?

The problem lies in the fact that we’re not explicitly disposing the response, which implements IDisposable. My rule of thumb when flushing out my design is that if a class implements IDisposable and I ultimately control its lifetime, then I must wrap it in a using block. If you read the documentation, you’ll realize that it’s not totally necessary when dealing with an HttpWebRequest to call Dispose, but it is when you’re dealing with an FtpWebRequest. Because I don’t make any distinction in this code, calling Dispose is a must. We might be tempted then to change the code to the following:

open System.IO
open System.Net

let getStreamData (uri:string) =
  async { let request = WebRequest.Create uri 
          use! response = request.AsyncGetResponse()
          
          return seq { use stream = response.GetResponseStream()
                       use reader = new StreamReader(stream)
                       while not reader.EndOfStream do yield reader.ReadLine() } 
        }

Running through a quick example using F# interactive, we’d get the following result:

> Async.RunSynchronously (getStreamData "http://www.bing.com");;
val it : seq<string> =
  Error: Cannot access a disposed object.
Object name: 'System.Net.HttpWebResponse'.

The problem now becomes that our response binding now will be disposed by the time that I iterate the results of the sequence expression. Remember that our evaluation of the sequence expression is lazy, so by the time I’m ready to iterate, the response has already had its Dispose called. So, where does that leave us?

Well, there are several things that we could do here. First, we could copy the response inside of our sequence expression and bind that to a using block. This would ensure that by the time we’re finished, we would properly dispose the response. That code might look like the following:

open System.IO
open System.Net

let getStreamData (uri:string) =
  async { let request = WebRequest.Create uri 
          let! response = request.AsyncGetResponse()
          
          return seq { use response' = response
                       use stream = response'.GetResponseStream()
                       use reader = new StreamReader(stream)
                       while not reader.EndOfStream do yield reader.ReadLine() } 
        }

This approach will work, unlike the previous example. By copying in this reference, we can ensure that the response will be disposed by the time we’re finished with our sequence expression. Although this works, it has a certain code smell to me. This code smell revolves around copying these references and there is a certain danger in doing so in terms of managing the lifetime. Instead, could we try another approach, perhaps more eager?

From Lazy to Eager

Another approach we could take with this is to do away with the idea of lazy I/O in this solution altogether. Instead, how about something as simple as a list comprehension instead of a sequence expression? The code might then look like the following:

open System.IO
open System.Net

let getStreamData (uri:string) =
  async { let request = WebRequest.Create uri 
          use! response = request.AsyncGetResponse()
          
          return [ use stream = response.GetResponseStream()
                   use reader = new StreamReader(stream)
                   while not reader.EndOfStream do yield reader.ReadLine() ] 
        }

Now what we have is that we have the use binding on our response and stream. At the end of our function, we simply use a list comprehension instead of the sequence comprehension which in this case gives us the benefit of eager evaluation.

Conclusion

When dealing with asynchronous expressions mixed with sequence expressions can cause problems due to object lifetimes. As I’ve had in my earlier post, it’s best to avoid such scenarios if possible and instead, focus on an eager approach. The savings you get here is you have to worry less about the resource lifetimes which may or may not be in scope by the time you’re ready to execute the sequence expression. The approach using the list comprehension should be the preferred solution.

Actors in F# – The Bounded Buffer Problem

podwysocki — Wed, 27 May 2009 23:58:00 PDT

In the previous post, I covered an example of an auction simulation using asynchronous message passing and a shared nothing approach using the MailboxProcessor class in F#. The auction example was a great piece to demonstrate scalability by adding additional clients to create a sort of bidding war between them. Once again, with this approach, we’ve eliminated the need for locks and other concurrency primitives.

This time, let’s take another canonical example of a Bounded Buffer and look at some of the design patterns around this.

The Bounded Buffer

The goal of this post is to walk through an example of actor model concurrency of the canonical Bounded Buffer which is another example given in Scala. The intent of this demo is to store and retrieve items in a buffer (rather simple actually). Given this example, we’ll walk through how we might implement this using the constructs in F#. One important aspect of this solution is to not post messages asynchronously as before, but instead, to post a message and await the reply.

Without further ado, let’s get into the code. As before, we have a few utility functions that will be quite handy for this journey. Much like we defined the (<—) operator last time for posting messages, I’d like one for posting and waiting for a reply. In addition, I need a way to accomplish currying for reasons you will see later. One thing that has irked me on occasion is the confusion between partial application and currying, which I’ve covered earlier. Getting back to the issue at hand, let’s look at the code for that:

// Curry the arguments
let curry f x y = f (x, y)

// Asynchronous post
let (<--) (m:_ MailboxProcessor) msg = m.Post msg

// Post and reply operator
let (<->) (m:_ MailboxProcessor) msg = m.PostAndReply(fun replyChannel -> msg replyChannel)

As you’ll notice, I put the two operators, the asynchronous post and the post and reply operators, the former not being needed for this post. The PostAndReply method gives a way to post a message and wait for the reply. A temporary reply channel is created and that forms part of our message. This reply channel is an AsyncReplyChannel<T> which supports one function of Reply which we will use later. This message is then sent back to the caller as the result.

Next, we need to define the messages we will be processing as part of this bounded buffer. Each of these messages define operations that our buffer supports, namely put, get and stop. Let’s take a look at these in detail:

type 'a BufferMessage = Put of 'a * unit AsyncReplyChannel 
                      | Get of 'a AsyncReplyChannel 
                      | Stop of unit AsyncReplyChannel

As you will notice, each of these has an associated AsyncReplyChannel part to the defined message. This is to allow me to reply to each of the callers in turn. The Put and Stop both have reply channels that take no associated data, so we can create them as an AsyncReplyChannel<unit>. The Put message allows us to put a value into the buffer, the Get allows us to retrieve those values in turn, and the Stop allows us to stop the mailbox.

Let’s move on to the heart of the matter, the actual bounded buffer. This class takes in a buffer size and then we expose methods that allow us to put values in the buffer, get values from the buffer and stop the mailbox. Below is how the code might look:

type 'a BoundedBuffer(N:int) =
  
  let buffer =     
    MailboxProcessor.Start(fun inbox ->
      let buf:'a array = Array.zeroCreate N
      let rec loop in' out n =
        async { let! msg = inbox.Receive()
                match msg with
                | Put (x, replyChannel) when n < N ->
                    Array.set buf in' x
                    replyChannel.Reply ()
                    return! loop ((in' + 1) % N) out (n + 1)
                    
                | Get replyChannel when n > 0 ->
                    let r = Array.get buf out
                    replyChannel.Reply r
                    return! loop in' ((out + 1) % N) (n - 1)
                    
                | Stop replyChannel -> replyChannel.Reply(); return () }
      loop 0 0 0)
      
  member this.Put(x:'a) = buffer <-> curry Put x
  member this.Get() = buffer <-> Get
  member this.Stop() = buffer <-> Stop

Inside our BoundedBuffer class, we create the buffer which then creates an initialized array. Because array contents are mutable, there is no sense in putting this as part of our processing loop. Instead, we’ll focus on the input index, the output index and the number of items in the buffer as part of our processing loop. When we receive the Put message when the number of items in the buffer is less than the buffer size, we set the value at the specified input index, return a reply back to the caller, and then loop with an increment to our index with a modulo of the buffer size as well as the number of items in the buffer. In receiving a Get message when the number of items in the buffer is greater than zero, we get the item at the output index, send the reply back to the caller with the value, and then loop with an increment to the output index with a modulo as well as decrementing the number of items in our buffer. Finally, should we receive a Stop, we simply reply back to the caller and return.

We created three methods to wrap this functionality for outside consumption. The Put method takes in the item to post to the buffer, and then we simply do a PostAndReply with our Put message and our item to post. I used currying here because the Put message requires two parameters, the item to put as well as the reply channel. In this case, my operator already provides that reply channel, so I only need to supply the item to put. Both the Get and the Stop methods are fairly straight forward as they post their respective messages with their private reply channels.

How does this work? Let’s fire up F# interactive and take a look with an example of posting a few items to our buffer and then retrieving them.

> let buffer = new int BoundedBuffer 42;;

val buffer : int BoundedBuffer

> buffer.Put 12;;
val it : unit = ()
> buffer.Put 34;;
val it : unit = ()
> buffer.Put 56;;
val it : unit = ()
> buffer.Get();;
val it : int = 12
> buffer.Get();;
val it : int = 34
> buffer.Get();;
val it : int = 56
> buffer.Stop();;
val it : unit = ()

What I did was create a BoundedBuffer that handled integers with a buffer size of 42. Then I posted three values, 12, 34 and 56. After putting these values into our buffer, I then retrieved each in the order in which it was placed into our buffer. Finally, I stopped the buffer. The complete source code to this example can be found here.

Conclusion

Once again, we can create rather interesting solutions using this shared nothing asynchronous message passing approach in F#. This solution involving the bounded buffer is no exception. How might this solution look in Axum? In due time, we will approach this as well as our Auction example from the previous post. There are a lot of Axum items to cover especially in regards to asynchronous methods and ordered interaction points, so stay tuned.

[ANN] DC ALT.NET – 5/27/2009 – Introduction to Pair Programming

podwysocki — Tue, 19 May 2009 22:48:00 PDT

The DC ALT.NET group is continuing the back to basics approach with this month covering an introduction to pair programming. It’s part of our commitment to the community to encourage such practices as in our previous sessions on Test Driven Development and Refactoring. This month is no exception in pair programming and why two heads are better than one.

In this session, we are joined once again by Jonathan Cogley, CEO and founder of Thycotic, to not only facilitate a discussion on pair programming, but help lead a session in which we implement user stories in pairs. We will lead this in a fishbowl style and then alternate in and out the pairs just to get an idea of how it is done. Not only will we see how it’s done, but also the benefits that can be had.

Our efforts in this back to basics series will continue next month covering Behavior Driven Development with Evan Light, so stay tuned.

Below are the details:

Date/Time:
5/27/2009 – 7-9PM

Location:
The Motley Fool
2000 Duke Street
Alexandria, VA 22314

Hope to see you there!

F# Actors Revisited

podwysocki — Tue, 19 May 2009 22:25:00 PDT

UPDATE: Removed ref cells to use two recursive loops

In the previous post, I covered briefly about the actor model in F#. This style of concurrency, using asynchronous message passing and a shared-nothing approach through the use of mailboxes is a pretty powerful mechanism for achieving scalability. With a shared-nothing approach, we can remove the need for such concurrency primitives such as locks.

Taking cues from Erlang, F# has the capabilities as well through the use of the MailboxProcessor class. In this post, let’s walk through a canonical example and explain some of the design patterns around this.

Mailboxes, Etc

Before we begin, let’s make sure we have some of the basics down. As I stated above, the approach here is that inter-agent communication is accomplished through a shared-nothing asynchronous message passing system. Each of these agents have a mailbox, which is nothing more than a queue of messages sent by other processes. These messages are then retrieved via either a scan or receive approach, depending if you wish to continue receiving messages. To determine which message we received, we do basic pattern matching against our given message types and decide how we want to handle it. To continue processing, we then recurse the function again to keep sending and receiving. We can send any number of pieces of data as part of these messages. For our example, we’ll implement the Auction example that comes from Scala.

Going Once… Going Twice… Sold!

Our goal in this post is to walk through implementing the Auction example which is an example given in Scala. The intent of this demo is to show an online auction service using the shared-nothing asynchronous message passing. We’ll have two clients bidding against each other to see who wins the particular item. Given that Scala has library support for actors, this is an attempt to see how well F# can handle this as well. The first impressions of the Scala model is that it’s much more focused on classes and objects than the F# version will be.

Without further ado, let’s start digging through the code. First up, let’s get some utility functions out of the way to help us on our journey. Instead of using the dot operator on some objects to send messages, I prefer the <—operator, as shown also in the Expert F# book. Also, I need a way to deconstruct an option type so that I can deal with a bidder that may not exist yet.

let (<--) (m:_ MailboxProcessor) x = m.Post x
let unSome (Some x) = x

Both of these functions should be rather self explanatory. The unSome takes in an option type with Some value and returns the value. Let’s move on to the messages that we need to define. I have comments beside each as to define what each message signifies.

type AuctionMessage =
  | Offer of int * AuctionReply MailboxProcessor // Make a bid
  | Inquire of AuctionReply MailboxProcessor     // Check the status
and AuctionReply =
  | Status of int * DateTime // Asked sum and expiration
  | BestOffer                // Ours is the best offer
  | BeatenOffer of int       // Yours is beaten by another offer
  | AuctionConcluded of      // Auction concluded
      AuctionReply MailboxProcessor * AuctionReply MailboxProcessor
  | AuctionFailed            // Failed without any bids
  | AuctionOver              // Bidding is closed

I decided to use a recursive type definition as to allow my AuctionMessage discriminated union to appear before my AuctionReply discriminated union, because both messages in AuctionMessage references a MailboxProcessor that handles the AuctionReply messages. In F#, order does matter in which values are declared, so this is a quick way to get a readable output. Next, we need to define some constants such as time to shutdown and our allowed bid increments:

let timeToShutdown = 3000
let bidIncrement = 10

It’s now time to define our auction agent. This will handle the overall orchestration of how the auction is handled. This includes handling both the Offer and the Inquire messages as well as what happens when we fail to get a message within a certain time period. Let’s step through the code now and then explain down below:

let auctionAgent seller minBid closing =
  new AuctionMessage MailboxProcessor(fun inbox ->
    let rec loop maxBid maxBidder =
      async { let! msg = inbox.TryReceive((closing - DateTime.Now).Milliseconds)
              match msg with
                | Some ( Offer(bid, client) ) ->
                    if bid >= maxBid + bidIncrement then
                      if maxBid >= minBid then unSome maxBidder <-- BeatenOffer bid                  
                      client <-- BestOffer
                      return! loop bid (Some client)
                    else
                      client <-- BeatenOffer maxBid
                      return! loop maxBid maxBidder
                
                | Some ( Inquire client ) ->
                    client <-- Status(maxBid, closing)
                    return! loop maxBid maxBidder
                
                | None ->
                    if maxBid >= minBid then
                      let reply = AuctionConcluded(seller, unSome maxBidder)
                      unSome maxBidder <-- reply
                      seller <-- reply
                    else seller <-- AuctionFailed
                    
                    let! msg' = inbox.TryReceive timeToShutdown
                    match msg' with
                    | Some ( Offer (_, client) ) -> 
                        client <-- AuctionOver
                        return! loop maxBid maxBidder
                    | None -> return ()         
            }
    loop (minBid - bidIncrement) None)

It’s a bit of code to digest, but the gist of this is rather simple. When creating an instance of this auction agent, we need a seller, a minimum bid and a closing time for the auction. From this, we create our MailboxProcessor to handle AuctionMessage types. Since we are continuously in a cycle of receiving messages and sending results, we have a recursive loop which carries our state for us. This state, which we carry from recursive call to the next is our maximum bid and our maximum bidder at the time. When we begin our call to this loop function, we start with the max bid of the minimum bid minus the bid increment and no maximum bidder.

When we are receiving messages, it’s important to handle any potential timeouts. In this case, we use this timeout as a mechanism for determining when our auction is over. In order to do this, we must use the TryReceive function instead of the Receive. Let’s look at the differences below:

// Throws an exception if timeout is exceeded
member MailboxProcessor.Receive : ?timeout : int -> Async<'msg>

// Returns None if timeout is exceeded
member MailboxProcessor.TryReceive : ?timeout : int -> Async<'msg option>

Since we need to know how to handle timeouts, it’s best to use the TryReceive approach. If we receive an offer, we determine whether the bid is acceptable, meaning greater than our current maximum plus increment. If it is, then we check whether the maximum bid is greater than the minimum, and if so, then send a message to the current maximum bidder with the BeatenOffer message. If we receive an inquiry, we simply return a Status message back to the client with our current bid and how much time they have left. Finally, if we don’t receive a message in the given timeframe, it’s time to wind down our auction. If the maximum bid is greater than our minimum, our auction is a success and we let our maximum bidder and our seller know. If, however, we don’t receive any bids, then our auction is considered a failure. Finally, and additional offers received will be responded to with an AuctionOver message to indicate to the client that they are not the winner. If this operation times out, we simply exit. A bit of a mouthful, but fairly straight forward.

Let’s move on to the client aspect. First, let’s set up a few things necessary for our client, encapsulated in the Auction module. We’ll set such parameters as our minimum bid, our closing date, our seller and our auction itself.

module Auction =
  let random = new Random()
  
  let minBid = 100
  let closing = DateTime.Now.AddMilliseconds 10000.
  
  let seller = new AuctionReply MailboxProcessor(fun inbox ->
    let rec loop() =
      async { let! _ = inbox.Receive() 
              return! loop()}
    loop())
  let auction = auctionAgent seller minBid closing

In order to create a seller for our auction, we need to stub out basic features of this agent. In this case, we simply have a processing loop which receives a message, does nothing with it, and continues with the loop again. As I have stated above, we need both our seller agent, and our auction agent, but what about our clients? In our same module, we define them as the following:

  let client i increment top = 
    let name = sprintf "Client %i" i
    let log msg = Console.WriteLine("{0}: {1}", name, msg)
    
    new AuctionReply MailboxProcessor(fun inbox ->
    
      let rec startAuction() =
        async { log "started"
                auction <-- Inquire inbox
                let! curMsg = inbox.Receive()
                match curMsg with
                | Status(maxBid,_) ->
                    log <| sprintf "status(%d)" maxBid
                    return! loop 0 maxBid }
      and loop current max =
        async { if max >= top then log "too high for me"
                    
                let current' =
                  if current < max then
                    let current' = max + increment
                    Thread.Sleep (1 + random.Next 1000)
                    auction <-- Offer(current', inbox)
                    current'
                  else current
                
                let! msg = inbox.TryReceive timeToShutdown
                match msg with
                | Some BestOffer -> 
                    log <| sprintf "bestOffer(%d)" current'
                    return! loop current' max
                | Some (BeatenOffer maxBid) ->
                    log <| sprintf "beatenOffer(%d)" maxBid
                    return! loop current' maxBid
                | Some ( AuctionConcluded(seller, maxBidder) ) ->
                    log "auctionConcluded"; return ()
                | Some AuctionOver ->
                    log "auctionOver"; return ()
                | None -> return () }
      startAuction())

What we’re doing here is having two mutually recursive loops. The first loop, the startAuction loop will get the max bid for us and then go to the main loop where we do our main work. From there, we’ll receive a message sent from the auction to the inbox and determine whether we’re the highest bidder, we’re the maximum or it’s time to call it a day. Once again, fairly straight forward code.

Lastly, it’s time to bring it all together. Let’s set up the calling code and see the results:

open Auction

seller.Start()
auction.Start()
(client 1 20 200).Start()
(client 2 10 300).Start()
Console.ReadLine() |> ignore

Executing this code gives us the following for our results:

Client 2: started
Client 1: started
Client 2: status(90)
Client 1: status(90)
Client 2: bestOffer(100)
Client 1: bestOffer(110)
Client 2: beatenOffer(110)
Client 1: beatenOffer(120)
Client 2: bestOffer(120)
Client 2: auctionConcluded
Client 1: auctionOver

What this tells us is that client 2 starts first and bids first. Client 2 then bids 100, only to be outdone by client 1 and goes back and forth until client 2 comes in with the best and final offer. The auction is then concluded and client 1 is notified that the auction is over. We can add additional client agents to the list and have just as much fun as before. To give you an idea, if we add another agent with an increment of 30 and a max bid of 150, we get the following results:

Client 1: started
Client 2: started
Client 3: started
Client 1: status(90)
Client 2: status(90)
Client 3: status(90)
Client 1: bestOffer(110)
Client 1: beatenOffer(120)
Client 3: bestOffer(120)
Client 2: beatenOffer(120)
Client 3: auctionConcluded
Client 1: auctionOver
Client 2: bestOffer(130)
Client 2: auctionConcluded

Now what we have here is that client 2 wins with an offer of 130 and the rest are notified of their loss. You can find the complete code for this example here.

Conclusion

Solutions such as these using shared-nothing asynchronous message passing can create rather scalable architectures. Utilizing the MailboxProcessor class, we’re able to implement actor model concurrency to tackle some of these problems with coordination of concurrent processes. How might Axum handle this scenario? Good question and I hope to have that answered shortly.

Axum – Ping Pong with Dataflow Networks

podwysocki — Fri, 15 May 2009 05:48:00 PDT

In the previous post, I gave the canonical Ping-Pong example in Axum and how it compared with Axum. I want to revisit this post because there are some areas in which we can rework it in addition to the other solutions we’ll visit. Some parts were needlessly chatty and instead we’ll work in some other language features to help clean up our solution.

Actors in F#

But, before we begin, Nicklas Gustafsson, the architect behind Axum, was inspired by my post and made an F# version of the canonical Ping-Pong example. F# supports a concept of mailbox processing as a first class citizen, much like other languages such as Scala and Erlang, although not as central to the core as it is in Erlang.

To use these, simply use the MailboxProcessor class. Below is an implementation as given by Nicklas and we can compare with my previous post with the Erlang implementation. The Start function creates a new MailboxProcessor instance and starts it with the given inbox. Much like the Erlang solution, this relies upon recursion as a technique for keeping the mailboxes alive. In order for us to communicate from one mailbox to the other, we must as part of our message, include a reference to our mailbox of origin in order to communicate.

#light

type Message = Finished | Msg of int * Message MailboxProcessor

let ping iters (outbox : Message MailboxProcessor) =
    MailboxProcessor.Start(fun inbox -> 
        let rec loop n = async { 
            match n with
            | 0 -> outbox.Post Finished
                   printfn "ping finished"
                   return ()
            | _ -> outbox.Post <| Msg(n, inbox)
                   let! msg = inbox.Receive()
                   printfn "ping received pong"
                   return! loop(n-1)}
        loop iters)
            
let pong() =
    MailboxProcessor.Start(fun inbox -> 
        let rec loop () = async { 
            let! msg = inbox.Receive()
            match msg with
            | Finished -> 
                printfn "pong finished"
                return ()
            | Msg(n, outbox) -> 
                printfn "pong received ping"
                outbox.Post <| Msg(n, inbox)
                return! loop() }
                    
        loop())

ping 100 <| pong() |> ignore
System.Console.ReadLine() |> ignore

It’s a fairly straight forward and follows the mold of Erlang quite nicely. Scala as well also follows this mold in their Ping-Pong example. Using the actor package in Haskell, we can also simulate the Ping-Pong example.

Of the criticisms mentioned in the post, I have no real issues with these such as the issues with no clear endpoints and how to distinguish the actors from one another. The type safety of Axum does give us some advantages as to define an explicit contract between actors.

Getting back to the issue at hand, what could we do to clean up our example in Axum?

Cleaning Up with Dataflow Networks

In our previous example, where we had the two agents communicating with each other, the Ping and the Pong, we pretty much driven by the data received from other agents. Instead, we can turn our attention to using dataflow networks, which is to be driven only by the availability of data entering our network and the computations that are performed as we move through this network.

Using Axum, we have several operators that can help us. The Forward Operator ( ==> ) sends each message produced by the source to the target. We also have the Forward Once ( –> ) operator which forwards a message from the source to the target, then disconnects after the first message. Using these operators, we can build pretty rich pipelines for our data to flow, but just as well, we could use it to build an event-driven system where we respond to events.

Let’s take a look at the rewrite of the main agent in which we create the endpoints for Ping and then send the message on the HowMany port. After that, we then forward the received value of Done to the Done state. Much cleaner than before.

using System;
using System.Concurrency;
using Microsoft.Axum;
using System.Concurrency.Messaging;

public agent Program : channel Application
{
    public Program()
    {
        // Create instance of ping and send msg
        var chan = Ping.CreateInNewDomain();
        chan::HowMany <-- 10;
        chan::Done ==> Done;
    }
}

Next up, let’s take a look at the Ping agent. You’ll note no change in our PingPongStatus channel and the associated ports. The interesting part is in the Ping constructor in which we forward the message from the HowMany port to the Process method which takes the number of iterations to perform. In Process method, we create the Pong instance and communication channels, then we loop through our number of iterations to send the Signal to the Ping port, and receive the return Signal on the Pong port. After the loop, we send a message to the Done to close the interaction and then return a Signal to end our Ping. Below is the implementation of the code.

public channel PingPongStatus
{
    input int HowMany : Signal;
    output Signal Done;
    Start: { HowMany -> End; }
}

public agent Ping : channel PingPongStatus
{
    public Ping()
    {
        PrimaryChannel::HowMany ==> Process;
    }
   
    private Signal Process(int iters)
    {
        // Create pong
        var chan = Pong.CreateInNewDomain();      
        
        // Send pings and receive pongs
        for (int i = 0; i < iters; i++)
        {
            chan::Ping <-- Signal.Value;
            receive(chan::Pong);
            Console.WriteLine("ping received pong");
        }
        chan::Done <-- Signal.Value;
        return Signal.Value;
    }  
}

You’ll notice that we’re no longer interested in sending the number of iterations to the Pong. It shouldn’t be needed and instead, we can send the Signal message on the Done port when we’re complete. The Pong can listen in an infinite loop until it receives the message on the Done port.

Lastly, let’s take a look at the Pong agent. We’ll clean up the channel to rid ourselves of the HowMany port. Instead, all we need are Signals to communicate at this point inside the infinite loop that I mentioned above. Let’s take a look at the code required.

public channel PingPong
{
    input Signal Done;
    
    input Signal Ping;
    output Signal Pong;
}

public agent Pong : channel PingPong
{
    public Pong()
    {
        while (true) receive
        {
          from PrimaryChannel::Done:
            return;
          from PrimaryChannel::Ping: 
            Console.WriteLine("pong received ping");
            PrimaryChannel::Pong <-- Signal.Value;
            break;    
        }
    }
}

As you can see, inside the Pong constructor, we’re performing an infinite loop in which we call receive each time, then we can react to the messages coming on the specified ports, in this case, the Done and the Ping ports. If we receive a message on the Ping port, we then send a Signal back on the Pong port and then break. Else, if we receive a message on the Done port, then we exit the agent. This approach is a bit more cleaner than our previous attempt at the Ping-Pong example.

Conclusion

As I indicated before, are other angles I wish to tackle with this example, including using asynchronous methods, ordered interaction points and so on, which I will get into in subsequent posts. With this little cleanup, I hope this shows some of the power of the language that we can indeed create concise, yet safe concurrent apps using message passing. Download it, use it in anger, and give the team feedback on the MSDN forum. Once again, with your help we can help shape the future of an actor based concurrency model on .NET.

Axum – Introduction and Ping Pong Example

podwysocki — Mon, 11 May 2009 22:37:00 PDT

As it was announced last week, Axum, a .NET Domain Specific Language around safe, scalable parallel programming through the actor model and message passing was released to the world as a CTP. It was noted, that although this is an initial release, that this is still an incubation project which may or may not lead to a final product. This post will serve as a kind of introduction to the language and some basic concepts.

Just A Brief Introduction

Before we get started, I wanted to make sure that we had a basic introduction to the language. The question often comes up, why another .NET language? Many people feel that with such others as C#, VB.NET, now F#, IronPython and IronRuby, that maybe we have enough languages already to solve most of our programming needs. But there remains one important, yet untackled problem around making coordinated parallelization easy. Sure, we have such things as the Parallel Extensions for .NET being baked into .NET 4.0, which gives us the Task Parallel Library, Parallel LINQ and so on, but none of these really address the intricate nature of coordinated parallelization.

Typically, when we’re developing these parallel applications, we could partition the data as usual and then scatter them out as parallel tasks. Some jobs were meant for solutions such as this, but others might require a bit more coordination. The Axum language, built upon the Microsoft Concurrency and Coordination Runtime from the Microsoft Robotics Studio, allows for a pretty natural language around such concepts as messaging, side effect free programming, but just as well, free yourself of many concurrency related bugs. Because isolation is built-in as a default, one of the major sources of concurrency related bugs is taken away. Just as well, when we design our applications with messaging in mind, we are building a scalable solution where concurrency isn’t an afterthought.

So, the final word is, why a language? Built-in isolation, easy to understand syntax around messaging, easy asynchronous programming model and many other benefits we get by stepping outside of the C# bounds. The real question then becomes, so what? What can we do with it?

The Erlang Way

When learning language concepts, I find it easier to spend some time in the language which most strongly implements that concept. This way, I learn the concepts best when they are first-class citizens in the space. For learning functional programming, I don’t think it’s as wise to spend your time hacking on C# as to instead learn on a more functional language such as Haskell. Often when people ask how best to learn FP concepts, often Haskell comes into the equation and has obviously improved my F# code as well as some of my C# as well. The same applies to a language with actor model concurrency as a built-in concept, where I can learn from my time spent in Erlang as a good precursor to what I can do in Axum.

One of the really elementary things to do in Erlang is a simple ping-pong example. In this simple example, we create two processes, a pinger and a ponger, and send messages between them a number of times. Such code might look like the following:

-module(tut15).

-export([start/0, ping/2, pong/0]).

ping(0, Pong_PID) ->
    Pong_PID ! finished,
    io:format("ping finished~n", []);

ping(N, Pong_PID) ->
    Pong_PID ! {ping, self()},
    receive
        pong ->
            io:format("Ping received pong~n", [])
    end,
    ping(N - 1, Pong_PID).

pong() ->
    receive
        finished ->
            io:format("Pong finished~n", []);
        {ping, Ping_PID} ->
            io:format("Pong received ping~n", []),
            Ping_PID ! pong,
            pong()
    end.

start() ->
    Pong_PID = spawn(tut15, pong, []),
    spawn(tut15, ping, [3, Pong_PID]).

From this example, we have two functions, a ping and a pong. Our ping has an arity with two arguments, the iteration number and the Process ID (PID) of the pong. If we are at zero iterations left, then we sent the finished message back to the pong’s PID, else we send a ping to the pong, then receive our pong message and then recurse to decrement the iteration number. Pretty simple, elegant and straight forward example. Running this example, we might get the following:

Erlang R13B (erts-5.7.1) [smp:2:2] [rq:2] [async-threads:0]

Eshell V5.7.1  (abort with ^G)
1> c(tut15).
{ok,tut15}
2> tut15:start().
Pong received ping
<0.40.0>
Ping received pong
Pong received ping
Ping received pong
Pong received ping
Ping received pong
ping finished
Pong finished

The <0.40.0> value you see above is the return value from the start() function which is nothing more than the PID of the ping process. Now that we’ve seen this in action in Erlang, how could we do the same in Axum?

The Axum Solution

We have a couple of options when implementing this ping-pong example in Axum. First, we have approach using channels, and another using an ordered interaction point. Let’s walk through each of these solutions as a possible implementation. The Axum Programming Guide is a great reference just in case you want to dive deeper into some of these topics.

Before we get started here, let’s first take a look at a simple hello world example to get you familiar with the syntax. Below is a quick example of getting the command line arguments, and then setting the channel to say we are finished. Alternatively, we could set the error code

using Microsoft.Axum;

public agent Program : channel Application
{
    public Program()
    {
        // Wait for the command line arguments
        var cmdLine = PrimaryChannel::CommandLine;
        var cmdArgs = receive(cmdLine);  
        
        // Tell the application we're done
        PrimaryChannel::Done <-- Signal.Value;
    }
}

The first piece you will notice is the lack of the word class, and instead the keyword agent. The agent concept comes from the actor model of concurrency in which it is an autonomous entity that communicates with others via messages they receives from these other “actors” and can spawn off other “actors” as well. These agents aren’t like normal classes in which you have fields that other classes can modify, nor have any direct method calls you can make.

The second piece you’ll notice after the agent declaration is that our Program implements the Microsoft.Axum.Application Channel. When we implement a channel, we are attached at the implementing end of that channel and we become the server of messages on that channel. This channel has a public property called PrimaryChannel which gives access to the channel being implemented. The double-colon operator gives us access to the channel’s port.

Now to actually dive through the agent constructor, we wait for the command line arguments to be passed. This receive is a blocking call, so we will wait until we receive the data from the CommandLine port, which in this case will be a string array. We then tell the application we are done by sending a message through the <—operator to the Done port, which is done asynchronously, as opposed to the receive. Now that we looked at a basic example, let’s move on to a channel based approach.

The Channels Example

The first example we’re going to look at is using channels and protocols. In this example, we will use some of the above constructs with the addition of channel protocols. First, let’s look at the main code which starts the program:

using System;
using System.Concurrency;
using System.Collections.Generic;
using Microsoft.Axum;
using System.Concurrency.Messaging;

public agent Program : channel Application
{
    public Program()
    {
        // Wait for our command args
        var cmdArgs = receive(PrimaryChannel::CommandLine);
        
        // Set the iterations to be some number
        var iters = 3;
        
        // Create instance of ping and send msg
        var chan = Ping.CreateInNewDomain();
        chan::HowMany <-- iters;
        
        // Receive how many done
        receive(chan::Done);
        
        PrimaryChannel::Done <-- Signal.Value;
    }
}

This code first waits for our command arguments, then we set the iterations to 3 for now, but we could set it as high as we wish, maybe higher than 5000 if we care. Sure, that’s a high number, but our system should be good for it. We then call Ping.CreateInNewDomain() which instantiates two ends of the PingPongStatus channel, creates an instance of Ping that implements the channel, then returns the using end of the channel. After this, we send a message on the HowMany port with our number of iterations desired. Then, we’ll block until we’ve received our message on the Done port to indicate that we are finished. Finally, we wrap up with setting the overall Done on the PrimaryChannel to indicate our program completion. Let’s move onto the Ping implementation next.

public channel PingPongStatus
{
    input int HowMany;
    output int Done;
    
    Start: { HowMany, Done -> End; }
}

public agent Ping : channel PingPongStatus
{
    public Ping()
    {
        // How many are we supposed to do?
        var iters = receive(PrimaryChannel::HowMany);
        
        // Create pong and send how many to do
        var chan = Pong.CreateInNewDomain();      
        chan::HowMany <-- iters;
        
        // Send pings and receive pongs
        for (int i = 0; i < iters; i++)
        {
            chan::Ping <-- Signal.Value;
            receive(chan::Pong);
            Console.WriteLine("Ping received Pong");
        }
        
        // How many did Pong process?
        int pongIters = receive(chan::Done);

        PrimaryChannel::Done <-- 0;
    }  
}

First, we created a PingPongStatus channel to get an input of how many to process, and then we have an output message which says we’re complete. You’ll notice there’s something more to our channel which begins with Start:. This is an implementation of a protocol, which allows us to specify the order in which messages are sent to which ports. All cases start with the Start as we have above, and then we transition to the HowMany port, then from the Done, it signifies the end of our interaction on this channel.

Now to analyze the Ping agent. Quite simply, we receive the number of iterations message from our Program agent from above. From there, we call Pong.CreateInNewDomain() which instantiates two ends of the PingPong channel, creates an instance of Pong that implements the channel, then returns the using end of the channel. We send a message to the HowMany port to specify the number of iterations our ponger should do. Going through each iteration, we send a message on the Ping port of a Signal, receive the message back on the Pong port. Finally, we receive the number of iterations that our pong did and then set our Done flag to 0. Now, let’s move onto our Pong implementation.

public channel PingPong
{
    input int HowMany;
    output int Done;
    
    input Signal Ping;
    output Signal Pong;
}

public agent Pong : channel PingPong
{
    public Pong()
    {
        // Get how many we're supposed to do
        var iters = receive(PrimaryChannel::HowMany);

        int i = 0;

        // Receive our ping and send back our pong
        for (; i < iters; i++)
        {
            receive(PrimaryChannel::Ping);
            Console.WriteLine("Pong received Ping");
            PrimaryChannel::Pong <-- Signal.Value;    
        }
    
        PrimaryChannel::Done <-- i;
    }
}

Notice that we have defined our PingPong channel to have ports to indicate how many to do, an output of how many we did, plus an input of a ping and an output of a pong. Pretty straight forward and self explanatory. Our Pong agent receives the number of iterations we’re supposed to do. Then we loop through our iterations, receiving a ping and sending a pong. After we finish the loop, we send a message on the Done port to indicate the number of iterations done.

If we stick with our three iterations, the output from our application should look like the following:

Pong received Ping
Ping Received Pong
Pong received Ping
Ping Received Pong
Pong received Ping
Ping Received Pong

Pretty straight forward and easy example as we dip our toe into what we can do with Axum. You can find the complete source code here.

Conclusion

There are other angles I wish to tackle with this example, including using asynchronous methods, ordered interaction points and so on, which I will get into in subsequent posts. Until then, I hope this brief foray into some of the capabilities of Axum will inspire you to give Axum a look. Download it, use it in anger, and give the team feedback on the MSDN forum. With your help we can help shape the future of an actor based concurrency model on .NET.

Axum Hits CTP

podwysocki — Fri, 08 May 2009 11:06:00 PDT

As I relayed in an earlier post about the soon availability of Axum, well, today is the day. I noted before that Microsoft has still not decided whether to release this as a real project, and needs feedback from users like yourself. On the Axum site there is a great video on how to build your first Axum application. Over time, I hope to add a few to the picture myself as actor model concurrency to me is highly interesting for many problems in today’s environment. You can read more of the announcement at the Axum Team Blog.

Feedback Required

Josh Phillips, the PM of the Axum team has asked for pointed feedback for this release. These include:

Learning curve: How complex do you find it to do simple things in Axum? Do you think the value it provides is worth the investment in learning and understanding the language?
Form: Do you think that Axum is better off as a language or would you be just as happy with a library-based solution?
Interop: How hard was it to consume objects that were created in other .NET languages? Was it easy to place isolation guarantees on these objects? If not, how would you change the process?
Async pattern: What do you think of asynchronous methods? Do they make the APM pattern easier?
Legacy: What issues are there with porting legacy applications? Any blockers or things we could do to make it easier?
Platform fit: How does Axum fit in with the rest of .NET? For graphical applications, did you face any challenges with the UI?
Scalability: Were you able to easily write applications that scale from cores to the cluster to the cloud? Is the unified model all it's cracked up to be?
Tools: What kind of tools (compile-time, run-time, post-run) would make you a more productive Axum programmer?
Love/Hate: What's the one thing about Axum that frustrates you to no end? What's the thing you love most about it?

Download it, use it in anger, and give the team feedback!

Type Classes Are The Secret Sauce

podwysocki — Thu, 07 May 2009 23:35:00 PDT

I came across a recent post on adding Ruby and C# operators to F# that sparked a few thoughts in my head. The post was good, but yet there were operators that already existed for some of the operations mentioned such as the defaultArg and ( @ ). But what really got me was thinking about type classes again due to the fact that extension operators aren’t currently supported in the language whereas extension events, properties, methods and statics are. I covered this in the past in regards to implementing an approximate equality check for my Functional Programming Unit Testing series, but I want to dive further into that subject a little more in this post.

Just What Are Type Classes?

As you may note that I do cover a bit of Haskell on this blog, and I think for very good reason. It’s a great language for incubating a lot of interesting ideas. Some of these ideas have been distilled into other languages such as concepts as monads. Type classes is another great feature of the language that I have come to know and love.

When we talk about implementing functions, we have two main types of polymorphism, parametric and overloading. Talking about parametric polymorphism is the typical programming with generics in which a function allows arguments of arbitrary related types of an unlimited nature. One such example of this is the map function, or the Select method for those in the LINQ land which allows us to specify both the source and destination types which might be just about anything.

Prelude> :t map
map :: (a -> b) -> [ a ] -> [ b ]

On the other hand, we have ad-hoc polymorphism or overloading, which depending on its context, can assume more than one type. If the allowable types are limited and must be known ahead of time, this makes is ad-hoc. This polymorphism type is made possible in Haskell through the use of type classes. For example, if we want to check for equality between two given algebraic types, this type must either derive the Eq type class or we create and instance of our own. Let’s make this a little more clear by actually looking at one. Instead of taking a look at the Eq or Equality check, let’s look at the Ord which contains the comparison operators.

Prelude> :i Ord
class (Eq a) => Ord a where
  compare :: a -> a -> Ordering
  (<) :: a -> a -> Bool
  (>=) :: a -> a -> Bool
  (>) :: a -> a -> Bool
  (<=) :: a -> a -> Bool
  max :: a -> a -> a
  min :: a -> a -> a
      -- Defined in GHC.Classes

This type class lays out our basic comparison operators such as greater than, less than, min, max, etc. But, it also has a restriction which states that any implementation of this type class must also have an associated implementation of the Eq type class which checks for equality. You can think of this as generic restrictions. The command we ran above, the info command also not only gave us information about the type class, but also some implementations such as the following:

instance (Ord a) => Ord (Maybe a) -- Defined in Data.Maybe
instance (Ord a, Ord b) => Ord (Either a b)
  -- Defined in Data.Either
instance Ord Integer -- Defined in efined in GHC.Base
instance Ord Char -- Defined in GHC.Base
instance (Ord a) => Ord [a] -- Defined in GHC.Base
instance Ord Int -- Defined in GHC.Base

In order to provide that functionality such as ordering checking, we must create an instance of the Ord class and implement some members. We needn’t implement all, just the ones we need for our given scenario. To give you a sense of how this works, let’s take a look at the implementation of Ord for the Bool type.

instance Ord Bool where
    compare False True  = LT
    compare True  False = GT
    compare _     _     = EQ

Now we have the compare function available to use with the Bool type. Pretty nice and easy. Because of this, we can determine whether one is greater than the other such as the following:

Prelude> compare True False
GT

Besides the Eq and the Ord I’ve already mentioned, there are others such as:

Show – Converting values to strings
Read – Converting strings to other values (opposite of Show)
Num – Numeric operations such as addition, subtraction, multiplication, etc
Enum – Enumeration operations
Fractional - Division

And the list goes on. But what I 'like about this, is the opt-in nature of providing a given set of operations and implementing only what you need. Also, it allows everything to be open so that I can create new instances of a type class for a given type as I see fit, even outside of the module in which it was created. If you want to go deeper on the subject, Brent Yorgey has a great article called the Typeclassopedia in the Monad Reader Issue 13.

A Poor Man’s Type Class in F#

Ah, but alas we do not have type classes in F#. It would be great if we did, but I’m sure it might take some changes to the CLR to make this happen such as allowing for higher-kinded polymorphism, which I’ve covered in the past. As it is, creating generic functions such as the basic math ones can prove to be rather difficult even with the CLR generics. What it essentially does is checks to see if that given operator exists for your given class among other things. But, what if you don’t own that class, how could you possibly extend it this way, for example things like adding two Colors? That’s the power of type classes.

Although not supported natively, we can add that behavior to our classes. Take for example checking for approximate equality for floating point arithmetic. As we know, the precise nature of checking for equality of floating points isn’t the same as for integers, and instead must be checked if the difference is less than epsilon. Let’s define an interface for what that might look like:

open System
open System.Collections.Generic

// Define the type class and it's global associations table
type IApproxEq<'a> = 
    abstract member approxEqual    : 'a -> 'a -> bool
    abstract member approxNotEqual : 'a -> 'a -> bool

What we have here is the beginning of a type class as to define two functions, one for equality and one for inequality. Next, we need to have some sort of repository for our instances that we declare so that we can dynamically look them up and perform the given operation. That might look like the following:

[<AbstractClass>]
[<Sealed>]
type ApproxEqualAssociations private() = 
  static let associations = new Dictionary<Type, obj>()
  static member Add<'a>(approxEqual : IApproxEq<'a>) = associations.Add(typeof<'a>, approxEqual)
  static member Get<'a>() = 
    match associations.TryGetValue(typeof<'a>) with 
    | true, assoc -> assoc :?> IApproxEq<'a>
    | false, _    -> failwithf "Type %O does not have an implementation of IApproxEq" <| typeof<'a>

This solution gives us a global singleton in a way of dealing with these operators. As we shouldn’t be adding to them frequently, and instead reading, it shouldn’t be too much of an issue, but it is an issue nonetheless. Now that we have this repository of them, let’s declare ones for both single precision floating point and double precision floating points.

type SingleApproxEqual() =
    let epsilon = 0.001f
    interface IApproxEq<float32> with
        member this.approxEqual x x' = abs(x - x') < epsilon
        member this.approxNotEqual x x' = abs(x - x') >= epsilon  
type DoubleApproxEqual() =
    let epsilon = 0.001
    interface IApproxEq<float> with
        member this.approxEqual x x' = abs(x - x') < epsilon
        member this.approxNotEqual x x' = abs(x - x') >= epsilon      
ApproxEqualAssociations.Add(new SingleApproxEqual())       
ApproxEqualAssociations.Add(new DoubleApproxEqual())

Once we’ve created these two implementations and added them to our associations table, it’s time to put some syntactic sugar on top to make them a real infix operator.

let (=~) x x' = ApproxEqualAssociations.Get().approxEqual x x'
let (/~) x x' = ApproxEqualAssociations.Get().approxNotEqual x x'

Now we have an extensible operator that can be added to at any given time. Say if we wanted to say that some colors are considered approximately equal? It wouldn’t be hard to implement something like that and add it to the associations table. We can now test our behavior such as the following:

> 4.000001f =~ 4.0f;; // Testing with float32
val it : bool = true
> 5.1 /~ 5.01;; // Testing with float
val it : bool = true

The true power of this approach is that it opens up the function for future implementations that may want to enlist in our behavior. Take this in contrast to the typical way we create operators in F# which lock us in to one type, although it can be circumvented, but it’s not well known and not well documented.

> let (+*) x y = (x * y) + (x + y);;
val ( +* ) : int -> int -> int

As you can see, we’re locked into the integer implementation which isn’t extensible. I noted above there are ways around this and if you look through the F# implementation, you will find some pretty interesting code for how they implemented the standard operators.

What Are the Limitations?

So like everything, there are limitations. For example, there is no such thing as compile time safety, which doesn’t actually bother many people, especially those in the dynamically typed world. Another issue is of course the maintenance of this global association table per type class can also be a little much as it might grow over time. It’s not the ideal solution, but it’s a solution. Do I think that F# should incorporate this? Absolutely! I really do like this language feature of type classes in Haskell and there are other lessons other languages can take from it.