Just a Thought...

Disclaimer: I’m originally a Java guy, and I know all kinds of asynchronous patterns and approaches that work in the Java world. The .Net approach to multi-threading and asynchronous applications is quite a bit different. In some ways the way that Microsoft approached the problem is more problematic. I stumbled across someone’s code for a small C# ray tracer with a fixed scene. I figured that this would be the perfect place to start playing with asynchronous code. Microsoft likes to hide things from you. I find this a bit problematic while trying to find out what is going wrong. Case and point: my assumptions about the way lambdas and closures ought to work (from my Ruby background) turned out to be wrong. Consider this code snippet:

for (int y = 0; y < screenHeight; y++)
{
    for (int x = 0; x < screenWidth; x++)
    {
        RenderColorDelegate px = RenderColor;
        px.BeginInvoke(x, y, scene, ar =>
           {
                Color c = px.EndInvoke(ar);
                RenderPixelDelegate dl = RenderPixel;
                pictureBox.Invoke(dl,new Object[]{x,y,c});
            }, null);
    }
}

Before I go into the surprise, let me tel you what this code is doing. This code is launching the rays from the view port one pixel at a time to calculate the color for that pixel. The px.BeginInvoke call is done on a delegate I had to create to alias the method I wanted to make asynchronous. I needed to pass in the variable “x”, “y”, and the scene that was passed in to the Render method. The original code makes use of synchronous calls, and behaves exactly as you would expect. X is always between 0 and one less than screenWidth. Y is always between 0 and one less than screenHeight. Now here is the surprise: when calling the methods asynchronously X can become greater than screenWidth!

Let me state that again in other terms: the values you pass in to the asynchronous method are not the values that end up being used. It behaves as a reference to the integer you pass in, and any call to x++ will increment the value on any asynchronous calls that have not been executed yet. That should alarm you. This can be (and was in this case) the source of serious and difficult to trace errors. With Ruby and Java anonymous classes, the values for x and y are frozen at the moment the asynchronous block is created. However, with .Net it is not. In order to fix the problem we have to copy x and y to new integers strictly for the purpose of passing in to the asynchrnous call:

for (int y = 0; y < screenHeight; y++)
{
    for (int x = 0; x < screenWidth; x++)
    {
        // Necessary to work around bug
        int cx = x;
        int cy = y;

        RenderColorDelegate px = RenderColor;
        px.BeginInvoke(cx, cy, scene, ar =>
            {
                Color c = px.EndInvoke(ar);
                RenderPixelDelegate dl = RenderPixel;
                pictureBox.Invoke(dl,new Object[]{cx,cy,c});
            }, null);
    }
}

The “pictureBox.Invoke” method should be familiar to .Net and Java UI developers. Essentially screen drawing and refreshing has to be done within the GUI thread. The “Invoke” method makes that happen when you are in another thread. The style of asynchronous call that I used included the callback function. This makes the redraw happen after the calculation is done.

When it comes to more traditional Thread manipulation, Java’s bag of tricks is a bit more complete. That may have changed with .Net 4.0 but I need to stick with 3.5. For example, the Future construct is really what I need. A Future is basically the promise of a value for when you need it later. It allows you to start processing a complex algorithm before you need the result, and pause for the result only when you really need it. It works for lazy initialization, but it’s more effective when you have a number of complex calculations you need to merge together. Java also has some good thread pool support, tasks, and other features. The Fork/Join approach in Java7 is also a very effective way to divvy up work. .Net 4.0 may have something similar to that, but both of those are taboo for new work for the time being.

All in all, I only scratched the surface. The delegate BeginInvoke() approach was designed for asynchronous event processing. It wasn’t really designed for more serious multi-threading. In fact, the way I used it for the ray tracer was the wrong tool for the job.

The bottom line is that I have to change the way I think about multi-threaded application design in the .Net platform. Some of the principles I’ve picked up from other languages still convey—but there’s a new twist on them. It’s to be expected. However, do be cautious of the delegate problem I ran into. It’s not good to have your values change underneath of you.

I’ll admit it, I’m a Ruby fan. There are certain aspects of programming with that language that are really fun. While I don’t have the privilege of working with it every day, I’m working with it enough. With yesterday’s look at the world of LINQ, I decided to play a bit more with delegates and extension methods. For the other Ruby fans out there, it is true that C# is both a statically typed language and those types are locked in at compile time. However, there are ways to make C# behave more like Ruby. Sure you can use the var keyword which just means that the type isn’t decided until the first assignment. But I’m going to look at imitating the way Ruby does looping in C#.

Our example Ruby code that we want to imitate:

list = ["one", "two", "three"]

list.each {|item| puts item}

# Alternately:

list.each do |item|
  puts item
end

Perusing the .Net APIs, your IEnumerable<T> or List<T> objects don’t have an Each() method. Although it’s not difficult to add it after the fact. The process is not hard. The first step is to create an extension method. Extension methods are much like Ruby mixins, and are implemented very similarly. As long as our mixin class in in scope, so is our extension method. Let’s look at how it would look in C#:

string[] list = {"one", "two", "three"};

list.Each( item => Console.WriteLine(item) );

// Alternately:

list.Each(
    delegate(string item)
    {
        Console.WriteLine(item);
    });

The code to implement this really is not difficult to do, but it requires some understanding of the underlying mechanisms that make it possible:

public static class IEnumerableExtensions
{
    public static void Each<T>(this IEnumerable<T> list,
            Action<T> callback)
    {
        foreach(T item in list)
        {
             callback(item);
        }
    }
}

To better understand what’s going on here, I’m going to have to call out a few things. First, the mixin class IEnumerableExtensions must be static. Without the static keyword in front of the class the CLR will not be able to look inside for extension methods. That keyword also tells the compiler that all members of this class will also be static. The class cannot be instantiated in any way. Functionally, it behaves a lot like a Ruby module, which is why I’m calling it a mixin class. Note: the name of the class really doesn’t matter, but convention adds the word “Extensions” to the class or interface we are adding functionality to.

Next, the first argument of an extension method includes the keyword “this” and the type we are extending as the first parameter. Without the keyword “this” we would have just another random static method. Also note, this is a feature that is not possible in Java without bytecode manipulation or dynamic proxy chicanery. Perhaps that will change in the future. For those that used to know how C++ objects worked, the structure here makes a lot of sense. It’s similar to the idiom popular among C programmers to pass the struct being modified as the first parameter. I chose the IEnumberable interface because the same method will work on anything that implements that interface: which is exactly how Ruby attacks the problem. Essentially Ruby has an Enumerable module (mixin) that defines all the extra methods the collection classes can use.

We used generics here to provide the same idioms and levels of type checking that come with the .Net platform. Even when you are mixing in concepts derived from other languages, you should never completely throw away the principles in the language you are using. The generics allow us to use the method preserving all the type safety built into the language without requiring us to write a number of overloads. This helps using the method feel a little more Ruby-like without ignoring C# principles.

Lastly, I want to point out the type Action. It is a delegate defined by the .Net framework, along with its companion “Func”. The only difference between the two is that Action does not return anything and Func does. Instead of creating my own delegates, I simply used what was already available. With the pair of delegates supplied, we can have a lot of fun. For example, let’s say we wanted to derive a list of answers from executing the same function across all the members of a set of values. One example would be to derive the Root Mean Square (RMS) value on a set of numbers. Our extension method would look like this:

public static List<TResult> Collect<T,TResult>(
        this IEnumerable<T> list, Func<T,TResult> callback)
{
    List<TResult> answers = new List<TResult>();

    foreach (T item in list)
    {
        answers.Add(callback(item));
    }

    return answers;
}

The way you would use the “Derive” method we just defined to calculate the RMS would look something like this:

double[] values = {1.0, 4.0, 3.0};

double rms = Math.Sqrt(
    values.Collect(x => x * x).Sum() / values.Count());

Console.WriteLine("RMS is: {0}", rms);

The “Derive” method as it is written will also allow you to do a mass conversion of all the elements in one IEnumerable object into a new list. For example, if you had an array of numbers and you wanted a set of strings it can be done with just one line:

double[] values = {1.0, 4.0, 3.0};

List<string> conversion = values.Derive( item => item.ToString() );

conversion.Each( item => Console.WriteLine(item) );

Your creativity is bounded only by your imagination.

Finite state machines are useful design constructs for a number of situations, although they seem to be fewer and farther between these days. Currently, the only place I tend to use them is when I have to write a parser by hand. Sure there are BNF parser generators around, but not all parsing requirements fit those restrictions. I have to parse legacy message formats which predate BNF parser theory (i.e. from the 1950s), so this is a useful tool to ensure that the message is properly formatted and all the information is pulled out properly.

According to Design Patterns by the GoF, the way to do an object oriented finite state machine is to use objects to represent each state, each with a common interface. My first introduction was a C++ program that was written with the old C mindset. That meant that the states were represented by an enum and all actions were taken with large switch or if/else hierarchies. I can see how using objects can clean things up, because the conditional logic would be decided by the state object. Of course, the state pattern in the GoF book required keeping the state in an external object and neglected to dictate how to change the state properly.

The Problem We are Solving

For my purposes, I have to populate a message object with all the information from a text message. That includes things like security markings, addresses, tags, captions, etc. The message format is distinct enough so that each line means something. Of course, there is a proper order of processing, but I can parse one line at a time. That simplifies things a whole bunch. I can have the parser work with an interface that looks like this:

public interface Partial {
    public State parse(Message message, String line)
        throws ParseException;
}

In Java 7 we will likely be able to use partials for this approach, which will clean up a lot of the code clutter. In that case the interface would look like this:

{Message, String => State throws ParseException}

Either approach you take will allow you to write the enumeration delegating the actual processing to anonymous classes. I’m sure you’re thinking, “My God! This guy’s off his rocker! I thought he liked elegant code!” Trust me, you’ll see the elegance in a minute. You aren’t going to do this all the time, but when the situation calls for it, you’ll appreciate it. The real benefit comes from testing.

Enums and Finite State Machines

Java enums are objects which is really useful. I’ve used this fact to associate sort order SQL snippets with an enum for the different sorting algorithms supported in a system, along with other uses. I decided to do an experiment with rewriting a parser we have. The parser works for the most part, but it leaves out some important information we want to support, and more importantly it is difficult to change. It needs some major rework beyond the scope of a bunch of refactorings. That is why I chose to rewrite it.

We have to start writing the State instances, and it really helps to have a starting point. For this blog, I’ll only split a message into header and body sections. There’s a whole lot more going on, but I just want to show how things work. The marker that splits the message header from the body will be a line that has “BODY” on it with nothing else. First, let’s look at our State enum. The important thing here is that we are not

public enum State implements Partial {
    HEADER(null),
    BODY(null);

    private final Partial partial;

    private State(Partial parser) {
        partial = parser;
    }

    public State parse(Message message, String line)
            throws ParseException {
        return partial.parse(message, line);
    }
}

The implementations of HEADER and BODY are null right now because we will get into it a bit later. First, you’ll notice a couple things about the enum. We are passing something that does work into the constructor, which also means that our enums can do work. For consistency sake we used the same interface for the enum as we did for the interface we pass into the constructors. If we were to use the closures spec, we wouldn’t have an interface to implement, so the method we provided would be how we access the blocks passed into the constructor. The spirit of the design is the same, it’s just that there is less extra code to type. Just so you can see what it looks like (assuming I have a better understanding of the spec), here you go:

public enum State {
    HEADER(null),
    BODY(null);

    private final {Message,String=>State throws ParseException}
           partial;

    private State(
            {Message,String=>State throws ParseException} parser) {
        partial = parser;
    }

    public State parse(Message message, String line)
            throws ParseException {
        return partial.invoke(message, line);
    }
}

In either case, the base design is identical. The only way to have the functionality of enum values change based on the value is to use the delegate approach. In short, we are passing in an object that does the work that is specific to that state in the constructor and calling it later when we call the parse method. It’s also important to note that enums are singletons by definition. There is one and only one State.HEADER enum value in the system, as there is one and only one State.BODY enum value in the system. That means the implementation has to be re-entrant. As long as you don’t attempt to keep any state in the objects you should be fine.

For the rest of the article, I’ll be focusing on the anonymous class approach (i.e. the first version). I’m assuming you can do the translation into closures later. Besides, I’m not sure if it would be legal to use the control invocation syntax for the constructor or not. This is a question for Neal Grafter, would this be legal syntax for the constructor of an object (it would be better if that’s the case)?:

HEADER(Message message, String line:) {
    HEADER
}

The State Implementations

The implementation of the state is very simple. We are providing an anonymous class (or closure declaration). The header is going to add the line of text to the header provided until we hit the “BODY” line. We aren’t going to copy that line at all. The important thing is that we can easily test these conditions in isolation from any other state. Let’s write some tests to make sure our implementation does what it is supposed to do (we are skipping the boiler plate JUnit code):

public void testCopiesLineToMessageHeader_and_ReturnsHEADERstate()
        throws ParseException {
    String line = "test line";
    Message message = new Message();

    State state = State.HEADER.parse(message, line);

    assertEquals( State.HEADER, state );
    assertEquals( line, message.getHeader() );
}

Currently our implementation compiles but only throws NullPointerExceptions because we haven’t given it anything to do yet. Let’s at least get this to pass. We have to rewrite the HEADER constructor in the enum:

HEADER(new Partial() {
    public State parse(Message message, String line)
            throws ParseException {

        message.addLineToHeader( line );
        return HEADER;
    }
});

That’s all well and good, but we need to make sure that we switch to the BODY state eventually. So let’s add a new test:

public testBodyLineReturnsBodyState_and_DoesNotWriteToMessage()
        throws ParseException {
    String line = "BODY" 
    Message message = new Message();

    State state = State.HEADER.parse(message, line);

    assertEquals( State.BODY, state );
    assertEmpty( message.getHeader() );
}

Now, all we have to do is make this pass in the HEADER enum:

HEADER(new Partial() {
    public State parse(Message message, String line)
            throws ParseException {
        if ( line.equals("BODY") ) return BODY;

        message.addLineToHeader( line );

        return HEADER;
    }
});

Now, if you are using Java closures, you simply cannot have multiple exit points. It’s easy enough to alter the logic. Some people don’t like what I did as a matter of principle. That’s OK. We know it works and its tested. We can refactor it later to our heart’s content. For the purpose of brevity, it’s up to you to do the same thing with the State.BODY implementation.

Using our Finite State Machine

Using the Finite State Machine we just created (granted it has only two states) is really easy. We know that we need a message object, and we need to iterate over the lines to a message. We’ll assume that you got it from some Reader. Here is a method that does the hard work for you:

public Message parseMessage(Reader in)
        throws ParseException, IOException
{
    Message message = new Message();
    State state = State.HEADER;
    BufferedReader reader = new BufferedReader(in);

    String line = null;

    while((line = reader.readLine()) != null) {
        state = state.parse(message, line);
    }

    reader.close();

    return message;
}

I left all the error handling code as an exercise for you, dear reader. If you want to provide accurate line numbers for your ParseException objects, you can surround the thing in a try/catch and use the following construct:

catch(ParseException pe) {
    // Rewrite the line number where the problem occurred.
    ParseException npe =
        new ParseException(pe.getMessage(), lineNumber);
    npe.setStackTrace(pe.getStackTrace());
    throw npe;
}

You have to keep track of the line number yourself. The lineNumber variable was incremented in the while loop in my code. I also wrapped the IOException in a ParseException keeping track of the line number so the signature was simplified. Of course, you’ll want close the reader in a finally clause.

In Conclusion

You aren’t going to write a finite state machine every day, but when you do you’ll want to keep things as simple as possible. The approach I outlined is very handy in the sense that you can completely test each state in isolation from the others. Because it is its own object, you don’t have to worry about testing the whole of the application to ensure your states are doing what they were designed to do. I typically have each State instance tested in its own TestCase object. This makes it particularly clear what each state is supposed to do, and how/when transitions take place.

I find that FSM are much easier to understand when you think about one state at at time. Trying to keep the whole “if this, then that, or is it the other thing” reasoning can be avoided that way. Doing it the old procedural approach is really not very useful these days. Don’t query data and keep control. Ask your objects to do work for you. Delegate.