I’ve just finished uploading a new in-car video from the Hurricane region PCA Driver’s Ed event at Carolina Motorsports Park in South Carolina. View it embedded here, or click the link below the picture to go to Vimeo.

PCA DE CMP August 2010 from Eric Vincent on Vimeo.

Some notes about the video and data acquisition, for those interested in the gory, geeky details:

· Video was shot on a GoPro HD. Last year I tried a ContourHD, but the picture wasn’t quite as good and the sound was terrible – the GoPro does a better job dealing with the wind noise.

· The data (speedo, Tach, Throttle position) was collected using a PLX 2340 KIWI Wifi. This device interfaces with the OBD-II port of your car (also used by mechanics to read diagnostics), and transmits several different types of metrics in real time over Wi-Fi at with an observed sample rate of about 3 samples / second.

· The data was then recorded using Rev by DevToaster for iPhone. This app is compatible with the PLX, so it can collect data being transmitted by your car. It also adds accelerometer data. There’s GPS too, but the iPhone’s GPS is completely unusable for track purposes. The sampling frequency is too low, and it does some very funky interpolation which in the end renders the GPS data useless. For example, here’s a simple plot (graphed using F#) of one of the runs:

· The data is then exported from the phone as an emailed comma separated value file (.csv).

· A small program I wrote in F# reads the file and transforms the timestamps in to frame numbers (29.97 frames/second), and the data into either rotational data (for the analog gauges) or simple integers (for the digital gauges).

· That data can then be imported into Adobe After Effects. Images of the gauges (drawn from scratch in Adobe Illustrator) are animated into a video overlay using the PLX/Rev data.

· Adobe Premiere then takes the gauges and overlays them on top of the video from the track. There’s some fiddling involved to get the gauge data and video in sync. Premiere then renders the video (20 minutes took 6 hours… not sure if I’m doing that right).

· That rendered video is HD and is pretty big, so I used Microsoft Expression Encoder (Adobe has an encoder too) to re-encode the video into a smaller MP4 format that Vimeo wanted for uploading.

As C# has evolved it has acquired more and more of what some people refer to has functional programming features and constructs. One such concept is the idea that a function is a "first class” value. This is a fancy way of saying that functions are values that can be passed to and returned from other functions. A function that operates on other functions is called a high-order function.

Combinators are high order functions that compose, combine, or otherwise modify functions in useful and interesting ways. These types of operations are not typically seen in C#, but expanding your problem solving toolkit to include these concepts is not only fun and interesting, but can result in new, efficient, robust solutions.

The Timer

Imagine you’ve got a method that you want to put a stopwatch on. For example, in the following code, you need to see how long it’s taking each download to complete, for debugging information.

class Program {

    static string url;

    static void Main(string[] args) {

        url = "http://microsoft.com";
        RetrieveFromWeb();

        url = "http://amazon.com";
        RetrieveFromWeb();

        url = "http://dpreview.com";
        RetrieveFromWeb();

        Console.Write("Press any key...");
        Console.ReadKey(true);
    }

    static void RetrieveFromWeb() {
        System.Net.WebClient wc = new System.Net.WebClient();
        var s = wc.DownloadString(url);
        Console.WriteLine("URL: {0} - string length is {1}", url, s.Length);
    }
}

An ugly solution would be to do this.

static void Main(string[] args) {
    var sw = new System.Diagnostics.Stopwatch();

    sw.Start();
    url = "http://microsoft.com";
    RetrieveFromWeb();
    Console.WriteLine("{0:#,##0}ms", sw.ElapsedMilliseconds);

    sw.Restart();
    url = "http://amazon.com";
    RetrieveFromWeb();
    Console.WriteLine("{0:#,##0}ms", sw.ElapsedMilliseconds);

    sw.Restart();
    url = "http://dpreview.com";
    RetrieveFromWeb();
    Console.WriteLine("{0:#,##0}ms", sw.ElapsedMilliseconds);

    Console.Write("Press any key...");
    Console.ReadKey(true);
}

Try not to get physically ill. You and I both know there’s plenty of code running around in the wild that looks a lot like this. Red flags – you see repeated code – starting, stopping, printing the time. Should we go into the RetrieveFromWeb() method and modify it for timing? Let’s not. Lets try this instead. Step one, let’s define a variable for the method we’re calling. Leaving out the timing code for now, we make this change:

static void Main(string[] args) {

    // Create a delegate, set it to the method of interest

    Action retrieveFromWeb = RetrieveFromWeb;

    url = "http://microsoft.com";
    retrieveFromWeb();

    url = "http://amazon.com";
    retrieveFromWeb();

    url = "http://dpreview.com";
    retrieveFromWeb();

    Console.Write("Press any key...");
    Console.ReadKey(true);
}

I’ve added a local variable of type Action, and set it equal to the call to the method RetrieveFromWeb(), and now we’re calling that method indirectly. It has the same exact effect, the method gets called three times. Only we’ve added a layer of indirection. We do this all the time in OO programming; for example, you might have a Person object, but rather than coding directly to that object, you create an IPerson interface, and code to that, opening up the possibility of mocking the object, decorating it, etc. Similar thing here. Rather than “binding” the call sites directly to the method, we’re binding to a variable that points to the method.

We’re doing this because now we’ve got a value that can be altered or augmented to add additional functionality. This is where a combinator comes in. This is a simple timer combinator:

class Combinators {

    public static Action Time(Action a) {
        return () => {
            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            try {
                a();
            } finally {
                Console.WriteLine("{0:#,##0}ms", sw.ElapsedMilliseconds);
            }
        };
    }
}

This combinator takes an Action and returns a new action (aka a new function), that has timing included. At line 8 the parameter action is being called, the timing is what’s added. The only change we have to make to the main method is where the delegate is being defined:

Action retrieveFromWeb = Combinators.Time(RetrieveFromWeb);

The rest of the method stays the same, but now, there’s timing added. This is a super-simple, contrived example, but you should be starting to see what’s possible. Let’s take this a step further. Here’s an example simulating retrieval of information from the database:

static void Main(string[] args) {

    Func<string, Guid> lookupUser = LookupUser;

    var emails = new[] {
        "eric@work.com", "joel@office.com", "cole@school.com",
        "karin@job.com", "haley@home.com" };

    foreach (var em in emails) {
        var id = lookupUser(em);
        Console.WriteLine("user {0} id = {1}", em, id);
    }

    Console.Write("Press any key...");
    Console.ReadKey(true);
}

static Guid LookupUser(string email) {
    // Fake looking up a user in the database
    var rnd = new Random(System.DateTime.Now.Millisecond);
    Thread.Sleep(rnd.Next(250, 2500));
    return Guid.NewGuid();
}

Memoization is the idea that a function can remember the results for given parameters. It’s like caching, but the term is specific to caching function results based on input. Here’s a simple Memoization combinator for C#:

public static Func<A, B> Memoize<A, B>(Func<A, B> fn) {
    var dict = new Dictionary<A, B>();
    return a => {
        B b = default(B);
        if (!dict.TryGetValue(a, out b)) {
            b = fn(a);
            dict.Add(a, b);
        }
        return b;
    };
}

It’s simple, but it demonstrates some very useful and interesting functional programming concepts. First, it’s takes and returns Func<A,B>. This is a delegate with a parameter of type A that returns a type B. This will work for effectively any method with that signature. Next point of interest, a dictionary is created, then the lambda is created and returned. The lambda refers to the dictionary defined outside the lambda. It is said that the dictionary is captured in a closure. It’s not important that you remember the terms, but look over the code and see if the concept is clicking for you. This function will return (effectively) a function, the dictionary is captured by that function. Even when the call to Memoize() goes out of scope, the dict variable will still exist in the returned function. Enough talk. We modify the main program just slightly:

Func<string, Guid> lookupUser = Combinators.Memoize(LookupUser);

The Memoize function will create a new function, one that caches results of the LookupUser function automatically. Nothing else has to change in the program to take advantage of this. Want to be sure that it’s actually working? Time it! The non-memoized LookupUser() has a built in Thread.Sleep(2500), and so takes 2.5sec * number of lookups to run. The memoized version will run almost instantly, so we can prove the memoizer is working by timing. The time combinator we created earlier was for timing Actions. I’ve created a overload of the time combinator that has the signature we need – Func<A,B>:

public static Func<A, B> Time<A, B>(Func<A, B> fn) {
    return a => {
        var sw = new System.Diagnostics.Stopwatch();
        sw.Start();
        try {
            return fn(a);
        } finally {
            Console.WriteLine("{0:#,##0}ms", sw.ElapsedMilliseconds);
        }
    };
}

and added it to the definition of lookUpUser in the main function

Func<string, Guid> lookupUser =
    Combinators.Time(
        Combinators.Memoize<string,Guid>(LookupUser));

Again without modifying the main code, we’ve augmented the method. Throw in some duplicate email addresses to test it out. The real power of these techniques becomes more evident the more you use them. Functional programming developers have been using these are similar techniques for years, and now with the added ability and flexibility of C#, we can employ these patters as well.

I was in one of those curious moods the other day, and decided to check out the API for the service behind my RSS reader, FeedDemon. I like this reader because it keeps my subscriptions and read / unread data synchronized across machines and my iPhone via an app called NetNewsWire.

Well it ends up that Google has gobbled up the service and it’s now Google Reader. Fair enough. It means you can also read your RSS feeds on the web at the Google reader site. Whatevs. It also turns out that Google has not publicized the API for that service yet. Yuck. But there are a couple of people out there (like here and here) who have picked it apart using fiddler or some such thing.

Well to put this meandering story to an end, I was playing with the API and it seems that some of the methods only return JSON. Others return XML, and others still are switchable. Messy. No wonder it’s not public yet. So that brings me to the point of this post… Parsing Json using F#.

Why F#?

I’ve avoided posting about F# to date, even though I love “playing” with it; I feel that posts about C# are more relevant. People are using F#, but I’ve never had the chance to use it on the job, and I don’t know anyone personally who has either. But since it’s mainstream now, what the heck. Plus parsing is one of those tasks that’s right up F#’s alley. If you haven’t worked with a functional language since college (or ever), give it a whirl. It’s refreshingly different from pure, straight, intensely object oriented thinking.

Json, Briefly

Most everyone knows what Json is by now. It’s just a tad more horrifying in real life as the supernatural killer from the Friday the 13th movies with whom it homophonetically shares its name. It’s a text format for representing data that can be evaluated in that wonderfully fast and lose language of the web, JavaScript, resulting in actual JavaScript objects. Read about it from the experts here. Here’s an example of some awesome Json:

{
    "glossary": {
        "title": "example glossary",
        "GlossDiv": {
            "title": "S",
            "GlossList": {
                "GlossEntry": {
                    "ID": "SGML",
                    "SortAs": "SGML",
                    "GlossTerm": "Standard Generalized Markup Language",
                    "Acronym": "SGML",
                    "Abbrev": "ISO 8879:1986",
                    "GlossDef": {
                        "para": "A meta-markup language, used to create markup languages such as DocBook.",
                        "GlossSeeAlso": ["GML", "XML"]
                    },
                    "GlossSee": "markup"
                }
            }
        }
    }
}

The Tokenizer

I’m no parsing / compiler / language expert, but I do know that tokenizing is the first step. This is when we run through the string and create tokens; identifying the open and close braces, the name value pairs, etc.

First thing we want to look at is the Token type, which is a discriminated union. This type defines the logical things that are in the Json string. For example, an open quote, some characters, and a close quote is a string.

type Token =
  | OpenBracket | CloseBracket
  | OpenArray | CloseArray
  | Colon | Comma
  | String of string
  | Number of string

For this simple parser, the tokens are as above, open and close bracket and square bracket (aka array), colon, comma, numbers, and strings. This is a good reason to start with Json, it’s painfully simple. The tokenize function below turns the string into a list of tokens.

let tokenize source = 

  let rec parseString acc = function
    | '\\' :: '"' :: t -> // escaped quote
                          parseString (acc + "\"") t
    | '"' :: t -> // closing quote terminates
                  acc, t
    | c :: t -> // otherwise accumulate
                parseString (acc + (c.ToString())) t
    | _ -> failwith "Malformed string."

  let rec token acc = function
    | (')' :: _) as t -> acc, t // closing paren terminates
    | (':' :: _) as t -> acc, t // colon terminates
    | (',' :: _) as t -> acc, t // comma terminates
    | w :: t when Char.IsWhiteSpace(w) -> acc, t // whitespace terminates
    | [] -> acc, [] // end of list terminates
    | c :: t -> token (acc + (c.ToString())) t // otherwise accumulate chars 

  let rec tokenize' acc = function
    | w :: t when Char.IsWhiteSpace(w) -> tokenize' acc t   // skip whitespace
    | '{' :: t -> tokenize' (OpenBracket :: acc) t
    | '}' :: t -> tokenize' (CloseBracket :: acc) t
    | '[' :: t -> tokenize' (OpenArray :: acc) t
    | ']' :: t -> tokenize' (CloseArray :: acc) t
    | ':' :: t -> tokenize' (Colon :: acc) t
    | ',' :: t -> tokenize' (Comma :: acc) t
    | '"' :: t -> // start of string
      let s, t' = parseString "" t
      tokenize' (Token.String(s) :: acc) t'
    | '-' :: d :: t when Char.IsDigit(d) -> // start of negative number
        let n, t' = token ("-" + d.ToString()) t
        tokenize' (Token.Number(n) :: acc) t'
    | '+' :: d :: t | d :: t when Char.IsDigit(d) -> // start of positive number
        let n, t' = token (d.ToString()) t
        tokenize' (Token.Number(n) :: acc) t'
    | [] -> List.rev acc // end of list terminates
    | _ -> failwith "Tokinzation error"

  tokenize' [] source

We don’t have time for the full treatment of F#. If there’s any interest, I’ll post up some tutorials or at least links to some of the very many existing good tutorials out there already. For now, assume we have an understanding of the syntax, and the logic of tokenizing and parsing is what we’re after here.

One of the first things we see is that tokenize defines a few functions within the function. Great feature of F#, allowing definitions of inner functions; it allows the coder to partition logic without having function explosion.

The driving inner function is tokenize’, whose signature is (Token list –> char list –> Token list). This means it takes a Token list and a char list, and returns a Token list. The first token list (acc) is an accumulator. This list is built up as the procedure calls itself recursively. This is a common pattern in functional languages, to “thread” an accumulator through recursive calls. The second parameter is a char list, or a list of characters from the source string.

We don’t see the char list explicitly because of the use of the  function keyword at like 20, this keyword means that the last parameter (the char list) is implicitly used in a match statement, the cases of which follow after the function keyword. The syntax would be equivalent to:

  let rec tokenize' acc sourceChars =
    match sourceChars with
    | w :: t when Char.IsWhiteSpace(w) -> tokenize' acc t   // skip whitespace
    | '{' :: t -> tokenize' (OpenBracket :: acc) t
    | '}' :: t -> tokenize' (CloseBracket :: acc) t
...

The idea that the sourceChars variable being passed immediately to the match..with construct is so common in F# that the function keyword is used as a contraction, allowing the elimination of what is an unnecessary variable. In many cases, this construct allows for a one line function definition.

Most of the cases in the block matches a character which in turn maps to a token, which is appended to the accumulator (acc : Token list), and passed to a recursive call of tokenize’. This way the tokens are built up (in reverse order) as the string is traversed. This is seen in lines 22-27. Line 21 skips whitespace by calling tokenize’ without adding a token to the accumulator first.

Things are a bit more interesting at lines 28, 31, and 34. Line 28 detects the beginning of a string, and starts a new recursive thread with the parseString function, the signature of which is (string –> char list –> string * char list). So the accumulator is a string, the “work” is being done on a char list, to which is passed our source char list, and the return is a tuple of string * char list, which is our parsed string and the rest of the source char list. One (of I’m sure many) optimizations that could be made is to use a mutable StringBuilder as the accumulator in parseString.

The token function on line 12 does a similar job for non-string literals (numbers in this case, there are no bools in Json).

Lastly, line 37 handles the case where we run out of source characters. The Token list we’ve been accumulating is backwards; we’ve been “appending” to the front of the list all this time. This is a common pattern. At the end, we return the reverse of the list. When the Json at the top is put through the tokenizer, we get this:

> let tk = tokenize source;;

val tk : Token list =
  [OpenBracket; String "glossary"; Colon; OpenBracket; String "title"; Colon;
   String "example glossary"; Comma; String "GlossDiv"; Colon; OpenBracket;
   String "title"; Colon; String "S"; Comma; String "GlossList"; Colon;
   OpenBracket; String "GlossEntry"; Colon; OpenBracket; String "ID"; Colon;
   String "SGML"; Comma; String "SortAs"; Colon; String "SGML"; Comma;
   String "GlossTerm"; Colon; String "Standard Generalized Markup Language";
   Comma; String "Acronym"; Colon; String "SGML"; Comma; String "Abbrev";
   Colon; String "ISO 8879:1986"; Comma; String "GlossDef"; Colon; OpenBracket;
   String "para"; Colon;
   String
     "A meta-markup language, used to create markup languages such as DocBook.";
   Comma; String "GlossSeeAlso"; Colon; OpenArray; String "GML"; Comma;
   String "XML"; CloseArray; CloseBracket; Comma; String "GlossSee"; Colon;
   String "markup"; CloseBracket; CloseBracket; CloseBracket; CloseBracket;
   CloseBracket]

This list of tokens is an intermediate step. From here, we could go in several directions. For my purposes, I wanted to see it as XML. To get there, I created a parser that takes the token list and returns an XElement.

let parseToXml source =
  let map = function
    | Token.Number(n) -> n.ToString()
    | Token.String(x) -> x
    | v -> failwith "Syntax Error, unrecognized token in map()"

  let rec parseValue (acc:XElement) = function
    | OpenBracket :: t ->
      let newElement, t' = parseElement acc t
      newElement, t'
    | OpenArray :: t ->
      let name = acc.Name.LocalName
      if name.EndsWith("ies") && name.Length > 3 then
        let childName = name.Substring(0, name.Length - 3) + "y"
        let newListElement, t' = parseArray childName acc t
        newListElement, t'
      elif name.EndsWith("s") && name.Length > 1 then
        let childName = name.Substring(0, name.Length - 1)
        let newListElement, t' = parseArray childName acc t
        newListElement, t'
      else
        let childName = acc.Name.LocalName
        acc.Name <- XName.Get(childName + "s")
        let newListElement, t' = parseArray childName acc t
        newListElement, t'
    | h :: t ->
      acc.Value <- map(h)
      acc, t
    | _ -> failwith "bad value"

  and parseArray name acc = function
    | Comma :: t -> parseArray name acc t
    | CloseArray :: t ->  acc, t
    | t ->
      let newElement = XElement(XName.Get(name))
      let acc', t' = parseValue newElement t
      acc.Add(acc')
      parseArray name acc t'

  and parseElement (acc : XElement) = function
    | Comma :: t ->
      parseElement acc t
    | Token.String(n) :: Colon :: t ->
      let newElement = XElement(XName.Get(n))
      let v, t' = parseValue newElement t
      acc.Add(v)
      parseElement acc t'
    | CloseBracket :: t ->
      acc, t
    | _ -> failwith "Malformed JSON object"

  let root = XElement(XName.Get("root"))
  let tokens = tokenize source

  match tokens with
    | OpenBracket :: t ->
      let result, t' = parseElement root t
      result
    | _ -> failwith "Json did not begin with an object"

There is still syntax checking happening in the parse step. The tokenizer would have found illegal tokens, but the parse function will find illegal Json structure. It works in a similar way to the tokenizer, except instead of a raw stream of characters, we’ve got a stream of tokens, which is examined one by one and passed to a set of recursive functions which accumulates the XML, in this case as an XElement.

parseToXml defines inner functions map, parseValue, parseArray, and parseElement. It then gets to work by creating a root XElement, and getting the Token list. Json should start with an OpenBracket token. Anything else and we failwith an error (like C#’s throw). When we find that OpenBracket, the recursion begins with a call to parseElement. The root XElement serves as the accumulator, and the Token list is the “work” to be done.

You should be able to see what’s happening if you’re somewhat comfortable with F#. The parseValue function does some extra work to wrap arrays in nodes where the singularity / plurality of the node makes it read a bit better (in English, most of the time). The other point of interest is that the accumulator is a mutable object in parseToXml, unlike the Token list was in tokenize. At lines 37 and 46, the newly created elements are added to the accumulator using the Add(XElement) method, which mutates the accumulator and keeps using it. This is a departure from “purer” functional techniques, but that’s what’s cool about F#, you can make those departures where it makes sense. In this case, leveraging the XElement class of the .NET framework was worth it. Consuming this class from C# is that much easier and more intuitive.

After all is said and done, this is the XML that is emitted.

<root>
  <glossary>
    <title>example glossary</title>
    <GlossDiv>
      <title>S</title>
      <GlossList>
        <GlossEntry>
          <ID>SGML</ID>
          <SortAs>SGML</SortAs>
          <GlossTerm>Standard Generalized Markup Language</GlossTerm>
          <Acronym>SGML</Acronym>
          <Abbrev>ISO 8879:1986</Abbrev>
          <GlossDef>
            <para>A meta-markup language, used to create markup languages such as DocBook.</para>
            <GlossSeeAlsos>
              <GlossSeeAlso>GML</GlossSeeAlso>
              <GlossSeeAlso>XML</GlossSeeAlso>
            </GlossSeeAlsos>
          </GlossDef>
          <GlossSee>markup</GlossSee>
        </GlossEntry>
      </GlossList>
    </GlossDiv>
  </glossary>
</root>

It isn’t the most sophisticated, performant, or I’m sure accurate Json parser out there. But it does the trick for my immediate need, is a good starting point for more sophistication later if needed, and was an excellent exercise in parsing and F#. It was fun to write, and hopefully it stimulates some curiosities. Let me know if you’ve got any questions or comments.

My last couple of blog entries were ostensibly about lambda functions (last one, one before). With these ideas, or a general comfort level with lambdas and the Action<> and Func<> delegate types in the back of your mind, consider this.

I was working on a project where the development team was instructed to implement a retry logic into our data access layer. In other words, if we experience database connectivity problems, retry the operation as seems reasonable.

Here’s some code we’re going to use as a basis for the conversation:

class Program {
    static void Main(string[] args) {

        try {
            Retry01();
        } catch (Exception ex) {
            Console.WriteLine(ex.Message);
        }
        Console.Write("Press any key...");
        Console.ReadKey(true);
    }

    static void Retry01() {
        // Iterate through the directories on the C:\ drive
        foreach (var dir in Directory.EnumerateDirectories("C:\\")) {
            OccasionallyThrow(0.1d);
            Console.WriteLine("dir: {0}", dir);
        }
    }

    static Random _rnd = new Random(DateTime.Now.Millisecond);
    /// <summary>
    /// Occasionally throw an exception
    /// </summary>
    /// <param name="freq">Percentage (as a fraction) of the time to
    /// throw an exception. Uses a random number generator, so
    /// this is not an exact measure</param>
    static void OccasionallyThrow(double freq) {
        if (_rnd.NextDouble() <= freq)
            throw new InvalidOperationException("An occasional exception");
    }
}

We’ve got a method, OccasionallyThrow(freq) that, occasionally throws an exception (duh). We’ve got a method that iterates through directories on the C:\ drive and pretty much can’t get through it without throwing.

So first pass, let’s fix Retry01() so it actually retries.

static void Retry01() {
    // Iterate through the directories on the C:\ drive
    foreach (var dir in Directory.EnumerateDirectories("C:\\")) {

        int retryCount = 0;
        bool done = false;
        do {
            try {

                OccasionallyThrow(0.25d);
                Console.WriteLine("dir: {0}", dir);

                done = true;

            } catch (Exception ex) {
                if (ex is InvalidOperationException) {
                    if (retryCount++ < 3) {
                        // can try again. Under the limit
                        Console.WriteLine("Caught exception, retry #{0}", retryCount);
                        done = false;
                    } else {
                        // retried too many times already
                        Console.WriteLine("Exceeded retry count. Throwing.");
                        throw;
                    }
                }
            }
        } while (!done);
    }
}

Yikes. That’s a bunch of code. Assuming we want to make this construct generally available, some refactoring is in order. Worse, the boilerplate code that manages retries surrounds the code we want to apply it to, at lines 10 and 11 of a 30 line block of code. This is a similar problem to the one described in my last post, so you may see where this is going. Here’s one approach to solving the problem.

static void Retry(Action action, int maxRetries = 3) {
    int retryCount = 0;
    bool done = false;
    do {
        try {
            action();
            done = true;
        } catch (Exception ex) {
            if (ex is InvalidOperationException) {
                if (retryCount++ < maxRetries) {
                    // can try again. Under the limit
                    Console.WriteLine("Caught exception, retry #{0}", retryCount);
                    done = false;
                } else {
                    // retried too many times already
                    Console.WriteLine("Exceeded retry count. Throwing.");
                    throw;
                }
            }
        }
    } while (!done);
}

static void Retry02() {
    foreach (var dir in Directory.EnumerateDirectories("C:\\")) {
        Retry(() => {
            OccasionallyThrow(0.25d);
            Console.WriteLine("dir: {0}", dir);
        }, 3);
    }
}

This approach solves many of the problems we’ve identified. The retry logic is encapsulated in a function that’s trivial to reuse. One point of interest here… if you’re not familiar with the syntax and techniques, it may look a bit strange. But it also should look a little familiar; consider the “using” block:

byte someByte = 100;
using (var stream = File.Open("C:\\data.dat", FileMode.CreateNew)) {
    for (byte i = 0; i < someByte; i++)
        stream.WriteByte(i);
}

The C# using block has a similar pattern. There’s some construct (using), and then a block of code to which the construct applies. It has a similar feel to our Retry() solution. Hmmm… could we use the Retry() approach to write our own using?

static void Using<T>(T disposableVar, Action<T> usingBlock) where T : IDisposable {
    try {
        usingBlock(disposableVar);
    } finally {
        disposableVar.Dispose();
    }
}

static void UsingMyUsing() {
    byte someByte = 100;

    Using(File.Open("C:\\data.dat", FileMode.CreateNew), stream => {
        for (byte i = 0; i < someByte; i++)
            stream.WriteByte(i);
    });
}

See that’s why I like coding so much… that’s definitely cool. It’s not exactly character for character like the using statement, but it’s pretty darn close (actually, mine is a couple of characters shorter). And it’s equivalent (at least it is superficially, I haven’t checked thoroughly, it’s almost 1am after all). It had to get a little fancier with the generics, but we’ve recreated a C# language construct.

This article is long enough, and I’m sure you get the picture. To me, this is a great example of how functional thinking can lead to interesting, robust solutions to problems. Let me know if you’ve got any questions or comments. Until then, have fun!

The last article described the absolute (and I mean really absolute) basics of lambdas in C#. Assuming you’re continuing from there, where to next? Let’s use some lambdas. There are two approaches we can use. First is using lambdas in places you traditionally used other approaches. Second is using them in new and interesting ways. Hmmm. Which to choose.

New and Interesting Code Constructs using Lambdas

Yea that’ll do. Let’s take an example situation. You’re tasked with writing part of a data access layer. It’s a low level data access layer, we’re not using Entity Framework, no Linq to SQL. No NHibernate. Just you and the keyboard. Sweet.

The team decides they’re comfortable with the forward only read only data reader. Ok. So you start sketching out your code and end up with this:

public static IDataReader GetSomeData() {
    using (var con = new SqlConnection(conString))
    using (var cmd = new SqlCommand(cmdString, con)) {
        con.Open();
        IDataReader rdr = cmd.ExecuteReader();
        return rdr;
    }
}

Well, this won’t work. Trying to return the reader, but you’ve got a command and a connection both in using blocks. On returning, those blocks will terminate, disposing of the connection and command (which is good). What now? Briefly consider not using using blocks, not disposing of anything and just returning the reader. Nah – just can’t do that. Ok, so bail on data reader and go with a data set or some other statefull representation of the data I guess.

But WAIT! Don’t punch out just yet. What’s happening here is we’ve got a disposable resource we want to use in a spot that’s surrounded if you will by other important code. Let’s take a look at this:

public static void UsingReaderGetSomeData(Action<IDataReader> processor) {
    using (var con = new SqlConnection(conString))
    using (var cmd = new SqlCommand(cmdString, con)) {
        con.Open();
        using (IDataReader rdr = cmd.ExecuteReader()) {
            processor(rdr);
        }
    }
}

Now we’ve got a method that does all the right things with the data reader. The reader, its connection, and its command are all in using blocks so they’ll be properly disposed of. We ask the caller to supply an Action<IDataReader>, and we’ll apply that action to our well protected data reader.

This looks reasonable, but since it’s a data reader, won’t the caller always be doing the while(rdr.Read()) thing? Let’s take care of that for them.

public static void UsingReaderGetSomeData(Action<IDataRecord> processor) {
    using (var con = new SqlConnection(conString))
    using (var cmd = new SqlCommand(cmdString, con)) {
        con.Open();
        using (IDataReader rdr = cmd.ExecuteReader()) {
            while(rdr.Read()) {
                processor(rdr);
            }
        }
    }
}

Now instead of asking for an Action<IDataReader>, we’re asking for an Action<IDataRecord> that will be called once for each record. Our function can iterate the data reader and call the processor once for each result. Here’s a sample caller that builds an HTML ordered list and writes the results to the console:

static void Main(string[] args) {

    StringBuilder sb = new StringBuilder();
    sb.AppendLine("<ol>");
    Dal.UsingReaderGetSomeData(dr => {
        sb.Append(" <li>");
        sb.Append(dr[0]);
        sb.AppendLine("</li>");
    });
    sb.AppendLine("</ol>");
    Console.WriteLine(sb);

    Console.Write("Press any key...");
    Console.ReadKey(true);
}

A client uses our function like a loop. Everything it puts in the curly braces from line 5 – 9 is like the the body of the loop. With this approach, we’re getting the benefits of the data reader, it’s fast and forward only. The construct is similar to a loop, so the consumers (our team mates) should be able to understand how to use this. And finally, we’re taking proper care to dispose of the resources.

To summarize, this approach allows you define functions that accept functions as parameters, and build more complex behavior. This technique is called functional composition. It’s one of the core principal concepts of Functional Programming, but as we’ve seen here, it can be applied to solutions in imperative programming languages like C# to great effect. Using techniques like this help you break your code down in smaller and smaller chunks, with some functions doing little bits of work, and other functions serving as glue or framework code. All this makes your code easier to test and less prone to errors if done correctly.

Taking it Further, or, Something More like Real Production Code

Alright, that was interesting. And as far as blog posts go, that’s all I was really trying to get across. But if you’re curious about what production code might look like that uses an approach like this, here’s an example:

private static void UsingReader(
    string command,
    Action<SqlCommand> preAction = null,
    IEnumerable<Action<IDataRecord>> recordProcessors = null,
    Action<SqlCommand> postAction = null) {

    // Instantiate connection and command, open the connection
    using (var con = new SqlConnection(conString))
    using (var cmd = new SqlCommand(command, con)) {
        con.Open();

        // Execute a pre-action if specified
        if (preAction != null) preAction(cmd);

        // If the reader processing blocks are supplied
        if (recordProcessors != null) {

            // Get an enumerator for the processing blocks & move
            // to the first processor
            var processorEnumerator = recordProcessors.GetEnumerator();
            if (!processorEnumerator.MoveNext())
                throw new InvalidOperationException(
                    "Supply at least one record processor");

            // Open the reader
            using (var reader = cmd.ExecuteReader(CommandBehavior.CloseConnection)) {

                do {
                    // Get the current record processing block
                    var recordProcessor = processorEnumerator.Current;

                    // Iterate the records of the IDataReader using the current block
                    while (reader.Read())
                        recordProcessor(reader);

                    // The loop condition advances both IDataReader and enumerator
                    // in sync continuing as long as there's a next resultSet and a
                    // processor to process it
                } while (reader.NextResult() && processorEnumerator.MoveNext());
            }

        } else
            // If there are no actions to execute using data reader, just execute query
            cmd.ExecuteNonQuery();

        // Do any clean up that might be needed
        if (postAction != null)
            postAction(cmd);
    }
}

Here we pass optional pre- and post- actions that allow the caller to optionally manipulate the command before and after it’s executed. We also accept a set of actions we’re calling record processors, to handle the case when a stored procedure or command is returning multiple result sets. In the case of multiple result sets, we’d expect the caller to send a different record processor for each result set it expects.

So this seems like a lot of code. Why bother? The way I approached it was that this code is a private method of the data access layer, and the public methods would leverage this method to avoid repeating the gory details of working with data readers. Leveraging the above method, our original GetSomeData() now looks like:

public static void UsingReaderGetSomeData(Action<IDataRecord> recordProcessor) {
    UsingReader(cmdString, null, new Action<IDataRecord>[] { recordProcessor });
}

And if we had a data access method that took a couple of parameters, it would look like this:

public static void UsingReaderGetSearch(string criteria, Action<IDataRecord> resultProcessor) {
    UsingReader(cmdString,
        cmd => cmd.Parameters.Add(new SqlParameter("@searchCriteria", criteria)),
        new Action<IDataRecord>[] { resultProcessor });
}

I hope this has proved helpful. I’ll keep throwing more of these posts out there, let me know if there’s something you’d like to see.

You don’t need to use Lambdas to make a living writing code in .NET. You can probably get away with not even knowing what Linq is. You can also still find work coding in .NET 2.0. But that’s painfully BORING. So to avoid the stinging monotony of working in a 5 year reverse time-shift, let’s take a look at lambdas.

The (arguably) simplest lambda.

string message = "Hello World";
Action simpleLambda = () => Console.WriteLine(message);

Console.WriteLine(“Get ready for a message!”);
simpleLambda();
Console.WriteLine(“That was the message!”);

The the type “Action” is a delegate, which can be thought of as a function pointer. The variable “simpleLambda” is now a function. The same way that “message” is a string. In reality, there are delegates and pointers involved, but for the day to day, just think of “simpleLambda” as a function. It can be called just like you would any function, which is what we’ve done here.

There are two different Types that are generally used for these functions. They are “Action” and “Func”. Action, which we just saw, is a function that doesn’t return anything. It’s a void function. When we want to define a function that returns something, we use the “Func” type. Remember back to your early days of Visual Basic, Pascal, etc., when there were different keywords that you’d use to specify if there was a return value or not? Same kinda thing here. Func returns, Action doesn’t. So here’s a Func example.

// Define a func that returns something

Func<string> minutesAndSeconds = () => string.Format("{0:mm:ss.ffff}", DateTime.Now);

Console.Write("Current Minutes and seconds are: ");
Console.WriteLine(minutesAndSeconds());

Here’s a function that returns a string. It’s type is Func<string>, which you can read as a function that returns a string. Let’s break down the syntax of the lambda itself. It centers around the lambda operator “=>”, which some people read as “goes to”. In both our examples, simpleLambda and minutesAndSeconds are functions that take no parameters. So on the left of the lambda operator are empty parenthesis. Means no parameters to the function. Easy. On the right is the body of the function.

There are two ways of expressing the body of the function. If the body is a single statement, you can just put that statement. This is called an Expression Lambda. If you need more than one statement on the right of the Lambda operator, you end up with something like this:

Func<string, string> hasher =
    s => {
        var sha = new System.Security.Cryptography.SHA1CryptoServiceProvider();
        return Convert.ToBase64String(sha.ComputeHash(ASCIIEncoding.UTF8.GetBytes(s)));
    };

Console.WriteLine("The base64 encoded SHA1 hash of \"Hello World\" is {0}", hasher("Hello World"));

A couple of differences here… first there’s some added whitespace to make stuff more readable. Don’t let it throw you. Whitespace == good. Second, the type is now Func<string, string>. The key to reading the Func type is that the last generic type specification is the return type. So it reads “a function that takes a string and returns a string”. Since this lambda takes a string as a parameter, to the left of the lambda operator goes the parameter. You can name this parameter anything you want, just like when you’re defining a regular function. This parameter is bound to the input to the function.

The next thing that’s different is there are open and close curly brackets, just like a function definition, after the lambda operator. This is the body, it’s just like a function body. You declare local variables in here, and when you’re done, you return something. Or if this is an Action instead of a Func, you don’t need to return anything (remember, Action is like a void function). This is the same function except as a statically defined method on a class:

public static string Hasher(string s) {
    var sha = new System.Security.Cryptography.SHA1CryptoServiceProvider();
    return Convert.ToBase64String(sha.ComputeHash(ASCIIEncoding.UTF8.GetBytes(s)));
}

Thaaaaatts pretty much it. There’re plenty of implementation details under the covers, and there’s a whole world of design patterns and techniques to explore with regards to using lambdas. But as far as what they are, you’re looking at it. I’ll push it a little further in the next blog post. If you’ve got any questions or want to dive deeper into this or any other subject I write about, let me know in the comments. In the mean time, have fun!

The thing with spending time on functional programming is that the typical .NET programmer will not likely be able to write production code in F#, and almost certainly not in Haskell. But what you are able to do is apply a new set of problem solving approaches to your every day work.

So here’s a simple problem that we see all the time; you’re writing a console application to test a component. Here’s the pseudo code:

/// While still processing
///     Get a string from the user
///     Process the string
/// End While

Super duper simple. So here’s a straight forward way to code it:

static void Main(string[] args) {
    NonReusableLoop();
}

static void NonReusableLoop() {
    string input = string.Empty;
    bool done = false;
    do {
        Console.Write("Enter a web site to process. Press enter to end: ");
        input = Console.ReadLine();
        if (string.IsNullOrEmpty(input)) {
            done = true;
        } else {
            ProcessWebSite(input, true);    // don't really care about second parameter
        }
    } while (!done);
}

static void ProcessWebSite(string webSite, bool someOtherParameter) {
    // Do some fake work
    if (!webSite.StartsWith("http://", StringComparison.OrdinalIgnoreCase)) {
        throw new InvalidOperationException("Poorly formed web site name");
    }
    Console.WriteLine("Processing web site {0}", webSite);
    var rnd = new Random(DateTime.Now.Millisecond);
    Console.WriteLine("Web site has {0:#,##0} pages!", rnd.Next(1, 1000));
}

So lets say we want to extract something reusable out of this. Lets say we regularly churn up little console apps and we’re tired of writing this over and over again.

There are a couple of approaches that seem obvious you if you’ve got your functional thinking cap on. For example, this first pass looks like a function that does the interesting work (calls ProcessWebSite()) in the middle of a bunch of other stuff (getting user input, looping, checking for the quit condition). Let’s go with that observation:

static void Main(string[] args) {
    ProcessUserInput("Enter a web site url", input => ProcessWebSite(input, true));
}

static void ProcessUserInput(string prompt, Action<string> fn) {
    if (fn == null) return;
    string input = string.Empty;
    bool done = false;
    do {
        Console.Write("{0}. Press enter to end: ", prompt);
        input = Console.ReadLine();
        if (string.IsNullOrEmpty(input)) {
            done = true;
        } else {
            try {
                fn(input);
            } catch (Exception ex) {
                Console.WriteLine("Exception thrown: {0}", ex.Message);
                Console.Write("Show exception stack? (y/N):");
                var exInput = Console.ReadLine();
                if (exInput.Equals("y", StringComparison.OrdinalIgnoreCase)) {
                    Console.WriteLine(ex.ToString());
                }
            }
        }
    } while (!done);
}

Now we’ve got a function that does the collection of the user strings, checking for the quit condition, and even adds some simple error handling to catch any exceptions that the “work” might throw. The parameter is an “Action<string>”. This is the .NET way of describing a function that returns void and has a single string parameter. This is a functional way of looking at the problem, because in functional programming passing functions around and working on functions is a fundamental technique. Getting used to doing this is a powerful tool.

But there’s a better way of looking at it. What if we think of the strings the user is entering as a set of strings. We end up with something like this:

static void Main(string[] args) {
    ProcessStrings(
        SetOfUserInput("Enter a web site url"),
        str => ProcessWebSite(str, true));
}

static void ProcessStrings(IEnumerable<string> setOfStrings, Action<string> fn) {
    foreach (var item in setOfStrings) fn(item);
}

static IEnumerable<string> SetOfUserInput(string prompt) {
    string input = string.Empty;
    bool done = false;
    do {
        Console.Write("{0}. Press enter to end: ", prompt);
        input = Console.ReadLine();
        if (string.IsNullOrEmpty(input)) {
            done = true;
        } else {
            yield return input;
        }
    } while (!done);
}

Now we’ve got a function that returns a set of strings (IEnumerable<string> is the .NET way of saying a set of strings), and a function that takes a set of strings and applies a function to each member. The yield keyword makes the SetOfUserInput() method into a set. Each time the yield return keyword is hit, the value is passed out to the caller. When the caller attempts to retrieve the next value from the set, control is passed to the line after the yield return. This construct is called a continuation, and it’s a powerful concept.

These two simple concepts, that functions can be passed around and worked on, and that you can generate sets of data using continuations, are simple and fundamental to functional programming. But as these examples show you can use these techniques to your advantage in C#, solving real, every day problems.

Two years ago I took up the OCaml programming language, purely out of intellectual curiosity. For me, OCaml was a gateway drug to functional programming in general. I’ve since spent a good bit of time with F# and Haskell. With the consulting work I do I don’t have the opportunity to use these languages in production, but I have found that using these languages has unlocked a new worlds of problem solving techniques.

This series lays down a groundwork of C# understanding upon which we can build a library of modern problem solving techniques, where we take the most useful functional approaches, and see how to apply them to C# programming in .NET. Even if you’ve not any interest in functional programming, this series can be of service helping you understand some of the less obvious aspects of C# programming.

Delegates

C++ has pointers to functions. C# has delegates. A delegate is a .NET type that can be thought of as a type safe function pointer. A function pointer is a variable that instead of pointing to or containing data, points to a function. This variable can be used to invoke, or call, the function it is pointing at.

Type safe refers to the fact that a delegate variable cannot point to just any function, it can only point to a function that matches the delegate’s signature. Signature refers to the parameters and return value of the function. Together, the parameters and return type form a fingerprint for a function which must match that the delegate.

In this example, a delegate is created at line 5 called GetStatsDelegate where the signature specifies a single string parameter and an integer return value. Judging from the name, the delegate should point to a function that gets some stats about a string.

class Program
{
    // define a delegate type for a function that takes a
    // string and returns an int
    delegate int GetStatsDelegate(string str);

    public static void main() {

        // Define a variable of our new delegate type, and
        // assign it a value. Any method with the same signature
        // can be assigned to this variable.
        GetStatsDelegate myFunc = GetLengthWithoutSpaces;

        // Both these print 0
        Console.WriteLine(myFunc("Hello"));
        Console.WriteLine(GetLengthWithoutSpaces("Hello"));
    }

    // This is a function that we can point to, because it has
    // the right signature for our delegate
    public static int GetLengthWithoutSpaces(string s) {
        return 0;
    }
}

At line 12 the delegate we created (which is a type) is used to define a variable, myFunc. We then set myFunc’s value equal to GetLengthWithoutSpaces, which is a function. Lines 15 and 16 call the function, once using the delegate, and once the traditional way.

Here’s where it starts to get interesting. This is a snip from Reflector, looking at how GetStatsDelegate is defined.  We defined it as a delegate, but the compiler has built what looks like a standard class which inherits from the MulticastDelegate framework class.

This is good to know. C# treats delegates in a special way. They’ve been granted their own keyword and a special unique way of declaration. The declaration declares a subclass for us, saving us the trouble of building out a subclass ourselves. If we use Reflector to dig into the base class (System.Delegate), we see these properties and fields:

// *** From Delegate ***

// Properties
public MethodInfo Method { get; }
public object Target { get; }

// Fields
internal MethodBase _methodBase;
internal IntPtr _methodPtr;
internal IntPtr _methodPtrAux;
internal object _target;

// *** From MulticastDelegate ***

// Fields
private IntPtr _invocationCount;
private object _invocationList;

These fields tell us a few things. An instance of a delegate has reflection information about the method it points to, this is what the MethodInfo public property. The pointer to the function itself is of type IntPtr, which we can think about as a pointer to memory.

The _target field is important too. In the case of a delegate that points to an instance method (ie a non-static method on a non-null object), the _target field points to the object with the method. This is important because it is not obvious from looking at code that a delegate holds a reference to the object with the method. It’s possible for this to be the source of memory leaks, where objects cannot be garbage collected because a delegate is holding a reference. You see this most often in events. Being delegates, events hold references that need to be unregistered in order to release these references.

Also we have something called _invocationList, which if we dig through the disassembly we come to find is an array of Delegates implemented as a linked list using pointers (IntPtr) directly for performance reasons. This means that MulticastDelegates are delegates that have a chain of additional delegates. This is used heavily in .NET’s event mechanism, where an event can have multiple handlers. The handlers are simply functions wrapped in delegates added to the linked list of a the event MulticastDelegate.

Next post we’ll look at using delegates, not as events (which anyone who has ever dropped a button on a form knows about), but as function pointers and objects, and start looking at some novel approaches to solving common problems.

As always if you’ve got questions or topics you’d like me to follow up on, please leave a not in the comments!

About a week ago Joa Ebert posted Flirting with Silverlight, in which he discussed his experiences with a cool little Lorenz attractor application. The strange attractor app (which you can check at his blog) was his way of playing around with the newly released Silverlight 3 (Props to Joa for some very cool work BTW). It calculates a shape in 3D defined by some 300,000 particles, and animates the spinning and rotating of this shape as the user moves the mouse across the display surface.

His point was to relate his first Silverlight experience, and how the non-optimized Silverlight application compared very favorably with the significantly optimized AS3 version. The HTML5 Javascript version was a non-starter, barely able to achieve a few frames per second compared to 30 for AS3 and SL3.

Joa made his code available. After looking at the SL3 source code I thought it would be trivial to add some basic concurrency that would significantly increase performance. Here’s a comparison of different implementations:

• Flash AS3 Version, Optimized
• Original Silverlight Version, naive implementation
• Silverlight Version, optimized to leverage Concurrency
• HTML 5 Version

A point of interest, as far as I know there is no way to do concurrency in Action Script 3. In Joa’s application, the bulk of the hard work is done in a loop that executes every frame:

void OnStoryboardCompleted(object sender, EventArgs eventArgs)
{
    targetX += (mouseX - targetX) * 0.1;
    targetY += (mouseY - targetY) * 0.1;

    var index = MaxScreen;
    var maxIndex = MaxScreen;

    while (--index > -1)
        bitmap.Pixels[index] = 0x000000;

    var particle = particles;
    var matrix = Matrix4x4.RotationY(targetX * 0.05) * Matrix4x4.RotationX(targetY * 0.05) * translationMatrix;

    var cx = 275.0;
    var cy = 200.0;

    var w = 0.0;
    var xi = 0;
    var yi = 0;
    var x = 0.0;
    var y = 0.0;
    var z = 0.0;
    var pz = 0.0;

    while (null != particle)
    {
        x = particle.X;
        y = particle.Y;
        z = particle.Z;

        pz = focalLength + x * matrix.I02 + y * matrix.I12 + z * matrix.I22 + matrix.I32;

        if (0.0 < pz)
        {
            xi = (int)( ( w = focalLength / pz ) * ( x * matrix.I00 + y * matrix.I10 + z * matrix.I20 ) + cx );
            yi = (int)( w * ( x * matrix.I01 + y * matrix.I11 + z * matrix.I21 ) + cy );

            index = xi + yi * ScreenWidth;

            if (index > -1 && index < maxIndex)
            {
                var color = bitmap.Pixels[index] + 0x202020;
                bitmap.Pixels[index] = color > 0xffffff ? 0xffffff : color;
           }
        }

        particle = particle.Next;
    }

    bitmap.Invalidate();

    storyboard.Begin();
}
    }

What he’s doing here is writing pixels into a bitmap. At line 9, he sets all the pixels to zero (black), erasing the previous frame. At line 23 he starts a loop that will calculate each pixel that should be turned on for the upcoming frame. In both these cases he’s dealing with a one dimensional array of pixels. This is the perfect case for data parallelism. The work of setting pixels can be divided between processors.

In general, concurrency is not a simple technique to implement correctly. The number and type of problems that one can run into are way beyond the scope of anything short of a very thick book. But this perhaps the simplest case; simple static composition data parallelism. It’s static because you can pre-assign the amount of work each thread will do. It’s data parallelism because each thread will be doing the same kind of work (calculating and flipping pixels), as opposed to a solution where one thread does one thing (like talk on the network) while another thread does something else (like shred xml files).

We get this done by building a function that behaves like a For() loop, but executes the body in parallel between several threads. If you’ve played with the recently released Visual Studio 2010 beta that has the .NET 4.0 framework, you’ll recognize this function which is in the next version of the framework (but in a far more sophisticated and powerful form).

void ParallelFor(int lo, int hi, Action<int> body, int p)
{
    int chunk = (hi - lo) / p;      // Iterations per thread

    AutoResetEvent[] latch = new AutoResetEvent[p];
    for (int i = 0; i < p; i++) latch[i] = new AutoResetEvent(false);

    // Schedule the events to run in parallel
    for (int i = 0; i < p; i++)
    {
        ThreadPool.QueueUserWorkItem((ob) =>
        {
            int pid = (int)ob;
            int start = lo + pid * chunk;
            int end = pid == p - 1 ? hi : start + chunk;
            for (int j = start; j < end; j++)
            {
                body(j);
            }
            latch[pid].Set();
        }, i);
    }
    WaitHandle.WaitAll(latch);
}

ParallelFor() takes lo and hi values, an Action<int>, and the degree of desired parallelism. The Action<int> is a delegate, which is like a pointer to a function. In this case, it’s a pointer to a function that has a single int parameter, and returns void. This function is the work that happens every iteration. Silverlight, .NET, and C# make it possible (I think it’s easy, but I’ve been doing this a while) to use anonymous methods and what amount to functional techniques to make Joa’s code multithreaded.  It may be best to illustrate by example.

while (--index > -1)
    bitmap.Pixels[index] = 0x000000;

Joa’s code above, which initializes the pixels in the bitmap, becomes:

ParallelFor(0, buffer.Pixels.Length, (i) => buffer.Pixels[i] = 0x0, numComputationThreads);

The parameters of ParallelFor are zero for where to start the for loop, Pixels.Length for where to end the loop, the lambda function (i) => buffer.Pixels[i] = 0x0, and the number of threads to use to do the work. The lambda function is anonymous (i.e. we don’t have to create a function with a name). The type of “i” is inferred from context to be an int. The body of the lambda (the part after the “=>”), is the work that is done each time through the loop.

This makes the clearing of last frame’s bitmap concurrent. To make the rendering of the next frame concurrent is a bit more invasive, but still not bad. Here’s the concurrent version.

ParallelFor(0, particles.Length, (i) =>
{
    Particle part = particles[i];
    var x = part.X;
    var y = part.Y;
    var z = part.Z;

    var w = 0.0;
    var xi = 0;
    var yi = 0;

    var pz = focalLength + x * matrix.I02 + y * matrix.I12 + z * matrix.I22 + matrix.I32;

    if (0.0 < pz)
    {
        xi = (int)((w = focalLength / pz) * (x * matrix.I00 + y * matrix.I10 + z * matrix.I20) + cx);
        yi = (int)(w * (x * matrix.I01 + y * matrix.I11 + z * matrix.I21) + cy);

        var index = xi + yi * ScreenWidth;

        if (index > -1 && index < maxIndex)
        {
            var color = buffer.Pixels[index] + 0x202020;
            buffer.Pixels[index] = color > 0xffffff ? 0xffffff : color;
        }
    }

}, numComputationThreads);

buffer.Invalidate();
lastRender = elapsed;

}

There are a few changes that I made to make the optimization a bit easier. Joa used a linked list of particles, I captured an array, just because it was a bit easier to make concurrent. But the significant difference is the body of Joa’s loop is now in an anonymous function. Values that will change in the body of the loop are now defined in the loop (x,y,z, etc). This is because if the loop used the variables defined outside the lambda, then the different threads would try to use the same variables as one another, which is obviously a problem. Other than that, the code is pretty much the same.

So how much of an improvement is there? Yea, a lot. I put a frame counter on Joa’s original code and on my MBP dual Core Duo 2.4Ghz 4Gig ram running Windows 7 release, it was getting about 30 frames per second. On OS X it was about the same. With the concurrency, and set to use 4 threads, it got up to 45 fps. On my quad core Dell M6400 Core 2 Exreme Q9300 at 2.54 Ghz with 8gig ram, it went up to 65 fps. If found it was best to use more threads then you have cores. So 4 threads was good on the dual core, 8 on the quad core.

Of course, this means the app will absolutely peg the processor, which is good if you want max speed. But you can also throttle the frame rate back, say hold it at 30, and use less processor to get the same fps as the original.

Silverlight 3 has caused a bit of a splash in the RIA community if the Twitter chatter is any indication. There is some venomous talk out there; you know the such and such tech sucks, such and such tech rules, and of course Microsoft is evil. I choose to stay out of that fray, perhaps it’s hitting 40 that did it. I don’t care to argue with Fanbois. I will say that the the community will discover that the .NET framework and C# (even VB.NET) make for a serious development platform that will benefit the community at large. It’s a very good time to be a developer!

Here’s a link to a zip file containing my version of the project: Strange Attractor Project

Would you like to see the concepts in this post expanded? Want to know more about concurrency, functional patterns, generics? Leave me a note in the comments or send me a Twitter reply at @efvincent. Oh, and thanks for reading!