Searching for Exceptions in .NET

I recently came across a rather interesting question on StackOverflow that posed the problem of discovering all the exceptions that a given method might throw under every circumstance.

Of course, in the great majority of situations, XML  documentation for the BCL (and ideally any third-party libraries too) should provide information about any exception that might be thrown and any potential reason for it. Indeed, thisthis is generally all one needs to write largely error-safe code. However, not every exception is documented in any case, and for production-quality applications, it is often desirable to insure that there is no realistic chance of an unhandled exception ocurring. For this reason, it is sometimes desirable to do a rigorous check for all exceptions. Clearly, an application-level unhandled (fatal) exception handler would do the job to some extent, and although this is always a good fallback feature to have, it is the least elegant solution to coping with exceptions.

After some consideration, it became quite apparent that the task reduces to the halting problem. However, with a few simplifications, the problem does become relatively solvable. Most importantly, complex logic that determines whether an exception will be thrown must be ignored, and one must simply assume that any throw statement within a given method could possibly cause an exception under certain conditions.

Here is the complete code for the algorithm I wrote. The GetAllExceptions method is an extension method that returns a read-only collection of exceptions, which makes it very straightforward and efficient to use.

Notably, the code detects all of

• instantiated exceptions,
• exceptions return from method/property calls,
• exceptions stored in fields (though if the method return type or field type is non-specific, i.e. a parent class of the actual exception type thrown), this is used instead.

Exceptions are only counted when the appropiate throw instruction is encountered at some level. Also, the stack and local variables are handled correctly, as far as I can tell, so this method should work soundly in pretty much all cases. (It has been tested with some a few quite complex methods within the BCL, as well as simpler user-defined ones.)

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;
using System.Text;
using ClrTest.Reflection;

public static class ExceptionAnalyser
{
    public static ReadOnlyCollection<Type> GetAllExceptions(this MethodBase method)
    {
        var exceptionTypes = new HashSet<Type>();
        var visitedMethods = new HashSet<MethodBase>();
        var localVars = new Type[ushort.MaxValue];
        var stack = new Stack<Type>();
        GetAllExceptions(method, exceptionTypes, visitedMethods, localVars, stack, 0);

        return exceptionTypes.ToList().AsReadOnly();
    }

    public static void GetAllExceptions(MethodBase method, HashSet<Type> exceptionTypes,
        HashSet<MethodBase> visitedMethods, Type[] localVars, Stack<Type> stack, int depth)
    {
        var ilReader = new ILReader(method);
        var allInstructions = ilReader.ToArray();

        ILInstruction instruction;
        for (int i = 0; i < allInstructions.Length; i++)
        {
            instruction = allInstructions[i];

            if (instruction is InlineMethodInstruction)
            {
                var methodInstruction = (InlineMethodInstruction)instruction;

                if (!visitedMethods.Contains(methodInstruction.Method))
                {
                    visitedMethods.Add(methodInstruction.Method);
                    GetAllExceptions(methodInstruction.Method, exceptionTypes, visitedMethods,
                        localVars, stack, depth + 1);
                }

                var curMethod = methodInstruction.Method;
                if (curMethod is ConstructorInfo)
                    stack.Push(((ConstructorInfo)curMethod).DeclaringType);
                else if (method is MethodInfo)
                    stack.Push(((MethodInfo)curMethod).ReturnParameter.ParameterType);
            }
            else if (instruction is InlineFieldInstruction)
            {
                var fieldInstruction = (InlineFieldInstruction)instruction;
                stack.Push(fieldInstruction.Field.FieldType);
            }
            else if (instruction is ShortInlineBrTargetInstruction)
            {
            }
            else if (instruction is InlineBrTargetInstruction)
            {
            }
            else
            {
                switch (instruction.OpCode.Value)
                {
                    // ld*
                    case 0x06:
                        stack.Push(localVars[0]);
                        break;
                    case 0x07:
                        stack.Push(localVars[1]);
                        break;
                    case 0x08:
                        stack.Push(localVars[2]);
                        break;
                    case 0x09:
                        stack.Push(localVars[3]);
                        break;
                    case 0x11:
                        {
                            var index = (ushort)allInstructions[i + 1].OpCode.Value;
                            stack.Push(localVars[index]);
                            break;
                        }
                    // st*
                    case 0x0A:
                        localVars[0] = stack.Pop();
                        break;
                    case 0x0B:
                        localVars[1] = stack.Pop();
                        break;
                    case 0x0C:
                        localVars[2] = stack.Pop();
                        break;
                    case 0x0D:
                        localVars[3] = stack.Pop();
                        break;
                    case 0x13:
                        {
                            var index = (ushort)allInstructions[i + 1].OpCode.Value;
                            localVars[index] = stack.Pop();
                            break;
                        }
                    // throw
                    case 0x7A:
                        if (stack.Peek() == null)
                            break;

                        exceptionTypes.Add(stack.Pop());
                        break;
                    default:
                        switch (instruction.OpCode.StackBehaviourPop)
                        {
                            case StackBehaviour.Pop0:
                                break;
                            case StackBehaviour.Pop1:
                            case StackBehaviour.Popi:
                            case StackBehaviour.Popref:
                            case StackBehaviour.Varpop:
                                stack.Pop();
                                break;
                            case StackBehaviour.Pop1_pop1:
                            case StackBehaviour.Popi_pop1:
                            case StackBehaviour.Popi_popi:
                            case StackBehaviour.Popi_popi8:
                            case StackBehaviour.Popi_popr4:
                            case StackBehaviour.Popi_popr8:
                            case StackBehaviour.Popref_pop1:
                            case StackBehaviour.Popref_popi:
                                stack.Pop();
                                stack.Pop();
                                break;
                            case StackBehaviour.Popref_popi_pop1:
                            case StackBehaviour.Popref_popi_popi:
                            case StackBehaviour.Popref_popi_popi8:
                            case StackBehaviour.Popref_popi_popr4:
                            case StackBehaviour.Popref_popi_popr8:
                            case StackBehaviour.Popref_popi_popref:
                                stack.Pop();
                                stack.Pop();
                                stack.Pop();
                                break;
                        }

                        switch (instruction.OpCode.StackBehaviourPush)
                        {
                            case StackBehaviour.Push0:
                                break;
                            case StackBehaviour.Push1:
                            case StackBehaviour.Pushi:
                            case StackBehaviour.Pushi8:
                            case StackBehaviour.Pushr4:
                            case StackBehaviour.Pushr8:
                            case StackBehaviour.Pushref:
                            case StackBehaviour.Varpush:
                                stack.Push(null);
                                break;
                            case StackBehaviour.Push1_push1:
                                stack.Push(null);
                                stack.Push(null);
                                break;
                        }

                        break;
                }
            }
        }
    }
}

To be quite honest, I’m not sure whether I’ll need to use this code myself at any point, but I’ve posted it regardless for the benefit of anyone who might require such rigorous exception checking. It was definitely an interesting challenge, at the least.

Any further comments or suggestions would be welcome, as always.

Playlist Synchronisation for Portable Devices

I have recently been attempting to properly set up synchronisation between Windows Media Player and my portable music player (which happens to be my phone). Though I found that the Windows Media Player synchronisation tool does the job pretty well, it does fail in one respect: it cannot copy over playlist (WPL) files. For me, this was a bit of a nuisance, since I rely very much on playlists to categorise my music collection.

The solution for me was to write my own tool that synchronises a given set of playlists with a portable device that is compatible with WMP (Windows Media Player) – as I believe many devices tend to be. The tool works simply by finding the appropiate place on the device to which to copy the playlist files (a known XML descriptor file on the device should specify this), and then copying over these files, with the locations of the media files updated to point to those on the device.

Naturally, my choice of technology with which to write the thing was .NET/C# – this does mean that it’s not a fully standalone application, though it does only consist of a single EXE. However, thanks to a few particularly convenient features of the language/framework (primarily LINQ to XML), the code was largely trivial to write, and the majority of the ~200 lines is in fact error handling.

You can download the program here. As mentioned, it requires the Microsoft .NET Framework 3.5 (SP1) to run, which is not installed on any current version of Windows by default, so it will need to be downloaded and installed firstly if you don’t yet have it. Also, if anyone is curious to see the code, I may be able to upload that at some point.

The tool should be run from the command line, and would seem to be very straightforward to use. (Run the program with no arguments to see the help information.) An example command line to syncrhonise the playlists in the standard location of your user profile with a portable device on drive F might be:

pps F “C:\Users\username\Music\Playlists”

That’s all it takes. The task should finish within a matter of seconds  and then report some general information about the playlists it found and what it managed to successfully synchronised; else return an error message.

NB: If you’re wondering how the synchroniser matches the media files on the device with those in the playlist, I have a small admission to make. Because the directory structure is not guaranteed to be the same on the device as at the location of the source media, the current version simply matches media items by file name. This works perfectly well for me, though there is clearly a caveat. I am looking for an improvement on this method, and while I have a few ideas, I haven’t finalised my decision yet. Any recommendations by someone more knowledgeable on the subject would be appreciated.

Now, this program was designed primarily for my own use, but I did consciously attempt to make it usable with any WMP-compatible portable device, so hopefully people shouldn’t have any major problems using it.

Finally, it would be nice to hear any feedback regarding this little tool of mine, so please feel free to drop me a message (even if it’s just to say you’re using it). If I hear any suggestion for a worthwhile feature to add (or of course a valid bug report), I will gladly update the program.

Code Golf: Evaluating Mathematical Expressions

Yesterday I happened to stumble across a code golf question and for no particular reason (except for perhaps boredom) decided to create my own problem and to post it on StackOverflow for the community to reply with their solutions. It actually turned out to be much more popular than I might have anticipated.

A quick definition of code golf for those who are unaware of this enormous (though really quite enjoyable) time sink:

The objective of code golf is simply to write a program/function that solves a given problem using the fewest possible number of characters. This usually involves clever tricks related to the problem and whatever language you use, followed by heavy obfuscation.

Here is the problem specification, copied from my StackOverflow post:

Write a function that takes a single argument that is a string representation of a simple mathematical expression and evaluates it as a floating point value. A “simple expression” may include any of the following: positive or negative decimal numbers, +, -, *, /, (, ). Expressions use (normal) infix notation. Operators should be evaluated in the order they appear, i.e. not as in BODMAS, though brackets should be correctly observed, of course. The function should return the correct result for any possible expression of this form. However, the function does not have to handle malformed expressions (i.e. ones with bad syntax).

Examples of expressions:

1 + 3 / -8                            = -0.5       (No BODMAS)
2*3*4*5+99                            = 219
4 * (9 - 4) / (2 * 6 - 2) + 8         = 10
1 + ((123 * 3 - 69) / 100)            = 4
2.45/8.5*9.27+(5*0.0023)              = 2.68...

Now, my own solution isn’t particularly astounding, but I did get it down to 403 characters, and have since cut off a few more (though haven’t bothered to re-obfuscate it). It is in fact my first proper attempt at code golf, so I don’t consider it too bad.

Here it is, in all its obfuscated ugliness:

float e(string x){float v=0;if(float.TryParse(x,out v))return v;x+=';';int t=0;char o,s='?',p='+';float n=0;int l=0;for(int i=0;i<x.Length;i++){o=s;if(
x[i]!=' '){s=x[i];if(char.IsDigit(x[i])|s=='.'|(s=='-'&o!='1'))s='1';if(s==')')
l--;if(s!=o&l==0){if(o=='1'|o==')'){n=e(x.Substring(t,i-t));if(p=='+')v+=n;
if(p=='-')v-=n;if(p=='*')v*=n;if(p=='/')v/=n;p=x[i];}t=i;if(s=='(')t++;}
if(s=='(')l++;}}return v;}

And in a rather more readable form (identical in behaviour):

float Eval(string expr)
{
    float val = 0;
    if (float.TryParse(expr, out val))
        return val;
    expr += ';';
    int tokenStart = 0;
    char oldState, state = '?', op = '+';
    float num = 0;
    int level = 0;
    for (int i = 0; i < expr.Length; i++)
    {
        oldState = state;
        if (expr[i] != ' ')
        {
            state = expr[i];
            if (char.IsDigit(expr[i]) || state == '.' ||
                (state == '-' && oldState != '1'))
                state = '1';
            if (state == ')')
                level--;
            if (state != oldState && level == 0)
            {
                if (oldState == '1' || oldState == ')')
                {
                    num = Eval(expr.Substring(tokenStart, i - tokenStart));
                    if (op == '+') val += num;
                    if (op == '-') val -= num;
                    if (op == '*') val *= num;
                    if (op == '/') val /= num;
                    op = expr[i];
                }
                tokenStart = i;
                if (state == '(')
                    tokenStart++;
            }
            if (state == '(')
                level++;
        }
    }
    return val;
}

The current leading solution in one written in Haskell (a mere 226 chars), with another in Python (237 chars) taking second place. This hardly surprises me – the functional and dynamic languages almost inevitably have more succinct syntax, besides generally being known to be more suitable for creating parsers. (If I hadn’t specified the absence of the BODMAS rules, I would have surely seen a solution containing little more than an “eval” statement!) Interestingly, the top two have both managed to avoid using regex altogether (though other solutions have with some success). In my opinion, it’s worth reading through the question to see how the various languages compare at performing the same task.

Please feel free to reply to the StackOverflow question or this post if you have a unique solution (in any language) that you’d like to share.

Update

I ended up spending just a bit longer on this task, since having seen some of the other solutions, it became pretty clear that I could get the char count down a good deal more. With the help of regex, my new solution stands at 294 characters. That in fact seems to be the winner amongst the set of solutions in C-style languages, so I’m quite pleased. (I have now promised myself not to entertain myself any long with this game, however.)

Here it is in a (relatively) clear form, in case anyone’s interested. (It assumes the System.Text.RegularExpressions namespace has been imported.)

float e(string x)
{
    while (x.Contains("("))
        x = Regex.Replace(x, @"\(([^\(]*?)\)", m => e(m.Groups[1].Value).ToString());

    float r = 0;
    foreach (Match m in Regex.Matches("+" + x, @"\D ?-?[\d.]+"))
    {
        var o = m.Value[0];
        var v = float.Parse(m.Value.Substring(1));
        r = o == '+' ? r + v : o == '-' ? r - v : o == '*' ? r * v : r / v;
    }
    return r;
}

http://stackoverflow.com/questions/928563/code-golf-evaluating-mathematical-expressions/944716#944716

Circular Buffer for .NET

This is a quick announcement that I’ve released my code for an implementation of a generic circular buffer for .NET (written in C# 3.0). The release also includes an implementation of a circular stream, which is a wrapper over a circular buffer of bytes. You can view the project and download the source code over at CodePlex, where I’ve licensed it under the MS-PL, which should hopefully be fairly unrestrictive.

If you’re wondering where this idea came from, I recently came across an interesting use for a circular buffer, and upon finding out that the .NET BCL contained nothing along the lines of a circular buffer (or stream), I decided to implement one myself. I’ve attempted to do everything properly of course (i.e. in the style of the BCL data structures), so hopefully it should be immediately useful to anyone familiar with the concept.

More about this to come later.

Numerical Analysis for .NET

During my ongoing work on a computational project for university, I recently discovered the need to perform some serious numerical analysis from my C# code.  Unfortunately, I must admit that the .NET world only now seems to be catching up in terms of the free and open source libraries it offers for various tasks, and initially I was disheartened to find that there seemed to be nothing available for doing calculations on large (sparse) matrices. After a fair deal of searching, only a couple of somewhat incomplete and no longer maintained matrix libraries turned up. Being an avid user of StackOverflow, however, I decided that if anyone was aware of some library that could do what I needed, I would most likely find them there.

The result was much better than for what I was even hoping. dnAnalytics is a general-purpose package for numerical analysis in .NET that does almost everything for which I might possibly ask – and from my first impressions, does it very well indeed. This wonderful find is a well-maintained, fully open-source, library with great API documentation (not a wholly unexpected thing, but surprisingly uncommon among so many open source projects). There are several features that stand out as particularly impressive. One undoubtedly is I/O classes for Matlab and delimited files (among other formats). What is more, the library seems to offer both a fully managed version and one that wraps the Intel® Math Kernel Library. I’m not sure how the performance compares between the two (I haven’t yet tried the latter), but it is surely nice to have the pair of options available, quite similarly to how you have alternatives of cryptographic algorithms in the .NET BCL, that is to say, a) a fully managed version, v) a version based on top of the Windows Crypto API, c) a version that uses the CNG (Next Generation) API introduced with Vista. Perhaps what appeals to me the greatest about this library is that the developers have clearly gone to an effort to make it user-friendly, not only with regards to the documentation, but also by adding an interface friendly to F# coders (likely to be a language of choice for future mathematical/scientific programming), and even visual debuggers for Visual Studio (possibly the only library to date I’ve seen include them).

My particular usage of the library requires me to use the linear algebra (specifically, sparse matrix) classes. Although I must point out that the specific algorithm that I was intending to employ for the project was not available (see my later discussion), it did include a host of other ones, primarily focusing on direct and iterative matrix decomposition, which would appear to be quite handy in many circumstances. I haven’t yet had a chance to play with the other areas of the library, but I have noticed that it offers some statistical functions and methods as well as a number of modern pseudo-RNG algorithms such as the Mersenne Twister.

To conclude, I should come back to the point that the most important part of the analysis I require was not (at least direclty) contained by the library – finding the eigenvalues or eigendecomposition of large (1000s of rows/columns) matrices, which happens to be in relation to spectral theory, in case you’re curious. Even so, being such a complex field and one fraught with difficulties when it comes to implementation (numerical instability is a huge problem), I was not surprised to find that an implementation of the Arnoldi or Lanczos algorithm was not present. Fortunately, after a bit more searching around (by this point I knew specifically what I was looking for), I came across the ARPACK library, written in the archaic Fortran77 language. It did however seem to be exactly what I was looking for: a set of fast routines to find the eigenvalues of large (either dense or sparse) matrices of various types. After only a small amount of pain messing about with MinGW, I managed to get the code compiled nicely into a DLL. At this point, I am of course perfectly able just to use the P/Invoke capabilities of .NET and do some hackery to integrate the ARPACK stuff with my existing code and dnAnalytics. Yet, I am also inclined to do this whole task properly and basically write a managed wrapper for ARPACK that is tightly conforms with dnAnalytics. I could then perhaps submit these wrapper types (along with a few unit tests?) as a repository patch to the dnAnalytics team in the hope that they’ll take it and add it to the next release. As with most other projects at this time, I will have to see what time permits me, though I would certainly hope to contribute something substantial to what truly is a terrific project that I would love to see expand further.

LINQ to YAML

LINQ to XML is one of the many technologies introduced with the .NET Framework 3.5, and one that is certainly a step forward in terms of usability. It allows querying in both the functional style (using LINQ and lambda expressions) and the more traditional imperative one, meaning that it’s a great tool for concisely working with XML data in any sort of application, and undoubtedly a significant improvement over the old XML DOM that resides in the System.Xml namespace.

In the spirit of LINQ, and with the advent of YAML, I recntly decided it was about time that this new “markup language” were integrated with LINQ. Surprisingly, there does not already exist anything akin to LINQ to YAML out there (though there are a couple of fairly usable implementations of a YAML reader/writer for .NET). This seemed to me like a good chance to potentially create something that might be used by more than the odd .NET developer or two. My plans are to implement a LINQ to YAML provider either from scratch or on top of one of the existing YAML libraries. (Which option I choose will depend on the state of the existing projects, which I haven’t yet investigated properly. I am however suspecting that it might be worthwhile writing my own, since it would a) teach me all the intricacies of YAML, and b) allow me to support the latest version [1.2], which the existing libraries do not.)

Before I launch into an overview of my intended implementation, here is a little bit about YAML itself, for those who aren’t already familiar with it. Although technically YAML isn’t a markup language (after all, the recursive acronym stands for YAML Ain’t Markup Language) – it is rather a serialisation format – it does essentially fulfill the the role that XML  traditionally has, in a variety of common situations. I’m not going to try to sell the format to you right now, but it should suffice to say that you wouldn’t have reached this far in the post if you weren’t already at least intrigued! Without doubt, the format is actively gaining popularity because of it’s ultra-lightweight syntax and suitability for hand editing, perhaps the two points that summarise its advantages over XML.

Anyway, here’s a short example of a YAML document (taken straight from the Wikipedia page), so you can see precisely how pleasant it is to work with (at least for humans).

—

receipt:     Oz-Ware Purchase Invoice
date:        2007-08-06
customer:
    given:   Dorothy
    family:  Gale

items:
    - part_no:   A4786
      descrip:   Water Bucket (Filled)
      price:     1.47
      quantity:  4

    - part_no:   E1628
      descrip:   High Heeled "Ruby" Slippers
      price:     100.27
      quantity:  1

bill-to:  &id001
    street: |
            123 Tornado Alley
            Suite 16
    city:   East Westville
    state:  KS

ship-to:  *id001

specialDelivery:  >
    Follow the Yellow Brick
    Road to the Emerald City.
    Pay no attention to the
    man behind the curtain.
...

Of course, the great thing about YAML, which is demonstrated clearly by this example, is that you don’t have to have any real knowledge about YAML to understand exactly and immediately what the data represents, and as a bonus it doesn’t hurt your eyes to stare at for too long! Even the referencing syntax should be fairly self evident. (&id00 and *id001 would surely be nothing new to C programmers.)

The semantics as well as the syntax of YAML obviously differ to those of XML greatly, although there is almost always some sort of correspondence between the features and possibilities that the two formats offer. The only notable missing feature when contrasted to XML is attributes, yet their usefulness is questionable anyway.

Right, so now I ought to explain a bit about how I actually plan to design this library. The basic framework will be virtually equivalent to that of LINQ to XML. In other words, the hierarchy will be largely based around an abstract YamlObject (YObject?) class, and will look very much like the one contained within System.Xml.Linq.

LINQ to XML class hierarchy

Though LINQ to YAML must of course accomodate for the unique nature of the format, I would initially aim for minimal difference and only significantly adjust the hierarchy when it is found to be necessary. Classes such as XCData and XDocumentType would not apply at all to YAML, yet there would need to be a place for a YReference or such somewhere in the hierarchy. The referencing aspect of YAML will likely prove to be one of the more interesting challenges; while YAML’s lists, maps (dictionaries), and combinations thereof would seem relatively straightforward with regards to emulation of the LINQ to XML design, references would introduce a substantially novel concept. Some sort of implementation of lazy evaluation followed by concrete referencing should be able to solve the problem, but there’s no way to predict how well this might work in practice at this moment.

What I realised only after deciding to create a LINQ to YAML library is that among LINQ providers, LINQ to XML is somewhat special in that the LINQ aspect of it is built on top of LINQ to Objects (i.e. LINQ using IEnumerable<T> objects), with only a relatively small number of extension methods specific to LINQ to XML. Indeed, most LINQ providers (LINQ to Objects and LINQ to SQL among others) require you to implement the IQueryable and IQueryProvider interfaces to provide complex logic for interpreting and returning the results of expressions, as well as evaluating complex expression trees.  All this means that I can pretty much just design a DOM  to a certain style (i.e. one suited to functional code, like LINQ to XML), and let LINQ to Objects to everything else for me.

As I can’t think of anything more worth mentioning about my project at this time, I shall leave any more specific and complex details to a future post. Still, do by all means feel free to query me about my plans – I would be glad to answer any questions, and even gladder to receive some suggestions as how you think I might design LINQ to YAML, or simply a nod that you might find this useful at some point. I don’t anticipate this project to be a very long one, though I must say that both my work and free-time schedule are likely to be fairly messed up for the next month or two, therefore I’m not going to promise when I’ll get around to my initial release. Whenever it so happens, I will duly post the link to the project page on Launchpad (or wherever I decide to host it).

Strongly-Typed CSV Reader in C#

As part of a project on which I’ve recently started working, I found it necessary to write a class that reads entries from CSV files. Such a simple format, you might think, so why would I bother sharing such trivial code? Indeed, it is a relatively short class, but I thought I’d post it here nonetheless, primarily because I believe its usage promotes a design practice of which I am particularly fond, and I suspect (hope) other people may appreciate as well. There are also a few bits of code that might be considered interesting (and unusual) from a language/design perspective.

When I decided to formalise the logic for reading from CSV files, I firstly thought it would be nice to write something in the spirit of .NET 3.5 – in this case, easily compatible with LINQ, fully generic (strongly-typed), and attribute-oriented (as seems to be the trend in APIs nowadays). Before I launch into any further discussion, here’s the code for the class in full.

using System;
using System.ComponentModel;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;

namespace NetworkAnalyser
{
    public class CsvReader<TEntry> : IDisposable where TEntry : struct
    {
        private StreamReader streamReader;
        private FieldTypeInfo[] fieldTypeInfos;

        private bool isDisposed = false;

        public CsvReader(string path)
        {
            streamReader = new StreamReader(path);
            Initialize();
        }

        public CsvReader(Stream stream)
        {
            streamReader = new StreamReader(stream);
            Initialize();
        }

        ~CsvReader()
        {
            Dispose(false);
        }

        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        protected virtual void Dispose(bool disposing)
        {
            if (!isDisposed)
            {
                if (disposing)
                {
                    if (streamReader != null)
                        streamReader.Dispose();
                }
            }

            isDisposed = true;
        }

        public IEnumerable<TEntry> ReadAllEntries()
        {
            TEntry? entry;
            while ((entry = ReadEntry()).HasValue)
                yield return entry.Value;
        }

        public TEntry? ReadEntry()
        {
            var line = streamReader.ReadLine();
            if (line == null)
                return null;

            var entry = new TEntry();
            var fields = line.Split(new char[] { ',' }, StringSplitOptions.None);
            FieldTypeInfo fieldTypeInfo;
            object fieldValue;

            for (int i = 0; i < fields.Length; i++)
            {
                fieldTypeInfo = fieldTypeInfos[i];
                fieldValue = fieldTypeInfo.TypeConverter.ConvertFromString(fields[i].Trim());
                fieldTypeInfo.FieldInfo.SetValueDirect(__makeref(entry), fieldValue);
            }

            return entry;
        }

        private void Initialize()
        {
            var entryType = typeof(TEntry);
            fieldTypeInfos = (from fieldInfo in entryType.GetFields(BindingFlags.Instance |
                                  BindingFlags.Public)
                              let fieldTypeConverterAttrib = fieldInfo.GetCustomAttributes(
                                  typeof(TypeConverterAttribute), true).SingleOrDefault()
                                  as TypeConverterAttribute
                              let fieldTypeConverter = (fieldTypeConverterAttrib == null) ? null :
                                  Activator.CreateInstance(Type.GetType(
                                      fieldTypeConverterAttrib.ConverterTypeName))
                                  as TypeConverter
                              select new FieldTypeInfo()
                              {
                                  FieldInfo = fieldInfo,
                                  TypeConverter = fieldTypeConverter ??
                                      TypeDescriptor.GetConverter(fieldInfo.FieldType)
                              }).ToArray();
        }

        private struct FieldTypeInfo
        {
            public FieldInfo FieldInfo;
            public TypeConverter TypeConverter;
        }
    }
}

(Please excuse the utter lack of comments in the code. Most of it is self-explanatory, but admittedly some parts are probably not. I put it together pretty quickly, but I may get around to commenting it some time soon. Some basic error handling might also be nice.)

At this point it may seem rather excessive just to read data from a CSV file, but I hope you’ll agree that it’s worthwhile once you see an example of typical usage.

The first step is to define a structure (struct) that holds each entry in memory. Here we’re going to define one that holds some basic information about a programming language.

public struct LanguageEntry
{
    public string Name;
    public string[] Paradigms;
    public string LatestVersion;
    [TypeConverter(typeof(CustomDateTimeConverter))]
    public DateTime InitialRelease;
    [TypeConverter(typeof(CustomDateTimeConverter))]
    public DateTime LatestRelease;
    public float Popularity;
}

The TypeConverter attributes are completely optional, and are only required when you’re reading some fields that have unusual formats and whose values you would like to convert to something simpler/more accessible (e.g. a string “Jun2002″ to a DateTime object in this case). For any field of a type recognisable by the default type converter, you don’t need to bother, as is shown for the double type. (This actually applies to a very large range of types within the BCL, including System.Drawing.Color, which can be specified in any format that you might use in the propeprty editor of Visual Studio, such as “DarkRed”.)

Finally, here’s a snippet to show how you might actually use the CsvReader<TEntry> class to read from a CSV file. This example reads all entries from the languages.csv file and prints out to the console the names of all functional languages.

using (var languagesReader = new CsvReader<LanguageEntry>("language.csv"))
{
    var languages = from lang in languagesReader.ReadAllEntries()
                    where lang.Paradigms.Contains("Functional")
                    select lang;
    foreach (var lang in languages)
        Console.WriteLine(lang.Name);
}

Hopefully that’s now convinced you that this is the right way to go about reading data entries from files. What this class provides is completely strongly-typed I/O (reading in this case, though it wouldn’t be very hard to create a similar CsvWriter class), and a declarative manner to defining entry types (or records, to use database termninology).

I’m not going to delve too deeply into the implementation of the class, but I think it’s worth highlighting a few specifics. Going back to the code for the class, the first thing to notice is the Initialize method – this is where much of the interesting stuff is happening. To summarise: it loops over all the public fields of the type specified by TEntry, gets the default type converter for the type of each field (or the one given by TypeConverterAttribute, if it exists), and then stores the FieldInfo along with the TypeConverter in a simple struct. The only other noteworthy point is the call to SetValueDirect in the ReadEntry method. This uses a keyword that’s almost wholly unknown (and undocumented!) to C# developers by the name of __makeref (there are other related ones by the names of __reftype and __refvalue) – I was certainly unaware of it before today. The problem that I initially encountered was one of using the SetValue method, which works perfectly well on classes, but presents a unique problem with structs: namely, because they are value-types, and the obj parameter is of type object, the argument must be boxed (wrapped into a reference type) and placed on the heap rather than the stack, meaning that the heap-based copy gets altered, and not the one you passed to the method (which is on the stack)! What the __makeref keyword does is create a TypeReference that directly references the stack-based object and thus allows SetValueDirect to set the field accordingly.

That’s enough explanation, I think. If you still aren’t sure about how it works precisely, then feel free to comment on this post. I’d also be quite happy to hear what anyone thinks of the general design and implementation, too.

Stratego Computer World Championships

The Computer Stratego World Championships is something of which I’ve been aware for a while now (since before its second event in 2008 in fact), but this year I’ve made my mind up to actually compete. Contrary to what its name suggests, it is a rather small competition (though indeed international and the only one of it sort), with only 5 individuals taking part last year. (Now I slightly regret not entering then while I at least had a statistically better chance, despite the lack of time and even experience.) This year there may be as many as twice as that number, and it appears as if there is even some academic interest from various places as well. Also, it seems that I will be submitting the first bot (computer player) written in .NET, thanks to a web service interface provided by Sven, one of the current and last year’s participants. (The standard interfaces provided with the SDK are only for Java and C++, requiring some form of IPC to get the client working with other languages.) Given that I have almost a full year to write, test, and improve upon my submission, I very much hope to submit a competitive bot by the time of the competition in December.

One of the great things about this tournament is the opportunity to test the bot you have coded at any time within a sizable online Stratego community at Metaforge (the host of the actual event), whose admin was nice enough to provide all participants with free testing accounts. If I’m lucky I may be able to get some useful feedback from some of the experts. The main method of testing and learning (perhaps automated learning if I’m feeling adventerous) will be offline, running marginally different versions of the bot against each other.

To me this competition is especially attractive because it deals with a largely unstudied area of game AI (hence the recent attraction of academic interest). Although it could be in vain, I’m hoping that my lack of formal education in this area may not serve as too big a disadvantage to me. It also means I can experiment with some really interesting theories without feeling I’m wasting time or reinventing the wheel. Until now, the most complex of the very few AI-related projects that I’ve worked on are a basic (though surprisingly skillful!) four-in-a-row player and an automatic solver for the Herbert challenge (part of Microsoft Imagine Cup in previous years – see my Herbert.NET project for more information). In fact, the AI that I ended up coding for a four-in-a-row game was quite overkill, since I implemented it primarily based on descriptions out of articles for advanced chess AI – now I hope to actually put it to good use.

Of course, programming a decent Stratego player is going to require quite unique algorithms and tactics. I will try and summarise a few of my theories here in brief, but don’t expect me to give too much away. (Admittedly, my ideas are currently little more developed than what I write here.) My plan is essentially to use something based on the alpha-beta search algorithm for traversing the tree of all possible future moves, almost identically to chess AIs. A transposition table and a few other traditional methods should come in handy, but that’s about where it ends and the statistical nature of the game requires its own approach. Clearly, considering an unknown opponent piece to be anything would allow the tree to branch far too quickly for any useful results, and would in many situations be near-pointless anyway. Very basically, my proposed solution is to use Bayesian probability and inference to calculate the likelihood of certain outcomes and thus assess the risk of different moves and strategies. Maintaining a list of probabilities of each opponent piece being of a certain type (for all nodes within the tree) is therefore a fundamental requirement, though with all liklihood not enough. In addition, it is perhaps equally important to keep track of what the opponent might guess its own pieces to be.  Now, simply choosing the move with the statistically best expected outcome would however produce a very poor player, since a good (human or computer) player does not base their moves purely on probabilitic calculations. For this reason, the program must have some understanding of the concept of bluffing among other things; it is generally not wise to attack an unknown piece with the potential of a large loss despite it being relatively likely that that it will defeat it anyway. In summary, I expect the design of the cost function for the search algorithm will be crucial in that it needs to account for movement behaviour of pieces as well as macro-decisions made by the opponent, apart from the usual point counts and piece positions. I cannot yet tell whether it will be more effective to simulate the human decision-making process when playing Stratego or that of existing AIs for board games (or quite possibly a hybrid of the two).

So that concludes the first of my posts on the subject. Look out for a follow-up post as I begin serious work on the bot and get some interesting results to show. For the meanwhile there is a rather long list of post ideas to keep me going.

Update

Imer Satz, the creator of Probe (the reigning AI of the Stratego Computer World Championships),  has kindly pointed out that there does in fact exist a host of files (roughly 75,000) of recorded classic Stratego games. The are available for download  from the gravon.de website. Imer has stated that he might be willing to put up an archive of all these games; I will update the post again if there is any success in this respect.

RoboChamps World Finals

About a month ago now I happened to receive a rather surprising email from Microsoft. Having read that I was invited to the Microsoft RoboChamps World Finals in Barcelona, I quite nearly dismissed it as spam until I read a bit further. It soon became obvious that it was in fact a real event for four “world finalists” to compete by programming robots to fight in a “Sumo ring” (essentially a physical version of the online Sumo challenge from the same competition). My disbelief was mainly due to the fact that RoboChamps wasn’t something I had devoted a huge amount of time to before then. I had watched some videos on MSDN Channel 9 and played around with a couple of the challenges downloaded from the website, but that was about it. Not before long I had encountered various bugs and issues in the SDK/challenges, quickly making me lose interest and move on to something completely new, as is often my tendency. (I might have anticipated the problems given that it was Microsoft beta software). Admittedly, the idea of programming robots in a simulated environment using the .NET framework sounded pretty cool, but I was busy enough at the time to (temporarily) forget about it. Back to my point: I soon found out that I had gained a wildcard place by my (comparatively) active participation in the forums, which at least clarified matters. So it came down to a free week-long holiday in the middle of the university term, simply to play around with robots (and win a guaranteed prize!) – how could I not accept such an opportunity?

I arrived in Spain late on Sunday after far too many hours travelling by aeroplane/train (and then getting lost and having to rely on my paltry knowledge of Spanish for directions to the hotel in the dark). Still, I did manage to arrive at the conference centre on time for the keynote (opening) speech of the yearly EMEA TechEd developer conference, which was acting as host to the RoboChamps finals. Unfortunately I wasn’t able to attend any of the other talks given at the conference during the week. (The ones on the new F# language [see this post] and the future of C# looked reasonably interesting, but as contestants we were coding and testing literally from sunrise to sunset some days!) The keynote itself was all about the next version of Visual Studio (VS 2010), including a few live demos, which overall looked very promising. I haven’t actually downloaded the CTP for it yet, so I won’t go into the details here. I may however wait for the next release, given that the IDE crashed within about 30 seconds after startup on the first demo – quite unsurprising really, but still rather amusing in what was essentially a big promotional talk.

The competition proper started that afternoon, when I met the three other contestants as well as the guy from Microsoft who was organising everything for us. They were Jackson, a professor of robotics from Brazil, David, and Doug, both two American engineers with many years of experience… I thought it would be difficult simply not to embarrass myself, but contrary to expectations the contest turned out to be surprisingly close (possibly due to the severe time constraints). We were firstly given our individual robots, two shared practice rings on which to test, a reference book for Microsoft Robotics Studio, and a brief explanation of how the event would be run before we then set to work. The robots were in fact just iRobot Create models (very similar to do the Roomba vacuum cleaner) with an embedded box running Windows CE and a webcam attached. In addition, since I was without a laptop, I was kindly given one to use throughout the course of the event, with nothing less than a pre-released version of Windows 7 installed. This ought to be the topic of another (short) post, but suffice to say now that I was quite impressed with some of the updates from Vista. I even hear that a slimmed-down version is being developed, which means people may have rather more luck running it on EEE PCs and other less powerful machines.

There were initially (that is the whole of the first two days) some horrible issues trying to run even the sample program on the robots. To start I had the bad fortune of being unable to deploy my program to the embedded box (which took rather long to realise and resolve with Visual Studio displaying a “Deploy Successful” message, despite my wondering why my program was still behaving like the sample one). Still, it seemed that everyone had their fair share of problems over the week, both hardware and software related. The fact that half of the robots were originally broken in some way (and some never fixed), together with the low charge on all the battery packs meant that I spent the first two days doing all too little. I should however mention that we did have plenty of assistance in trying to fix everything as soon as possible. (Microsoft did want a good contest after all, especially since the fight on Thursday was being publicised to any conference-goer who walked near.)

Eventually when I did get my program running, things turned out to be a lot of fun and it the challenge became one of strategy rather than debugging. I started by tweaking the code for the sample program and improving upon the vision processing, with a limited degree of success. My hopes to use the SIFT algorithm (its virtues preached to me by David [my aforementioned friend, not opponent]) for feature detection and estimating the location of the robot’s self/opponent immediately vanished once I had run a few speed tests on the embedded device, showing about a 100x slowdown compared to my moderately fast desktop. Noticing that my opponents were using relatively straightforward algorithms for machine vision was however a big relief. (SIFT was largely magic to me anyway, having tried to learn it only the previous week from Wikipedia and some of David’s old lecture notes.) I ended up taking the general structure and motor-control code from the sample program (as I believe the others did too) and using my own code for handling the sensor data, in particular the camera frames. The essence of my vision processing algorithm was some fine-tuned colour segmentation (using a flood fill function I ported from a previous project). I also updated the motor control code to use proportional feedback. Most else was quite trivial.

We finally came to the afternoon of the competition, with barely a day and a half of serious development behind me (and little more, if any, for the others). Despite the evidently enormous amount of work everyone put into the competition, it was great to be with such casual, open, and friendly competitors, and we were sharing ideas even until the last few hours. The format of the rounds was very simple: the winners of the two semi-finals progressed to the finals, and the losers played for 3rd place, where each round was the best of three 60 second bouts. The first semi-final between Jackson and Doug began at 1:00pm (see the video recording of it here) and I was beginning to panic slightly, realising that the recent versions of my program were strangely intent on running the robot out of the ring by itself and not easily resolvable. (I had recently done some 3 or 4 hours coding without any testing, which would explain…) A bit foolishly, I also had no sort of version control on my code (unless you count the poor man’s version control of copying/pasting the source directory every so often). When it came to my semi-final round against David, his robot needed only to watch mine drive full speed out of the ring after about 15 seconds. Fail, indeed. Crucially I had a couple of hours before the 3rd place play-off, which meant I could at least revert to a backed-up version (of unknown behaviour in the ring) and do some tweaking/testing. This somehow won me the round against Doug (though my robot only succeeded in avoiding being pushed off) to finish 3rd overall. I did get the feeling that perhaps I would have faired rather much better on first round had I only been less intent on using my latest version, but I was nonetheless happy to settle for 3rd given the overall situation.

We had all agreed earlier in week that we would let the winner choose first whichever prize he wishes, followed by the others in rank order. (This was mainly due to the lack of fondness for the RoboDog, which was originally going to be the 1st place prize.) When it came to decision time Jackson was very generous in deferring his choice to the rest of us, which means I was lucky enough to receive one of the two laptops. I still am not aware of its precise specs, but hearing that it was a high-end Alienware gaming laptop was enough to sell me. The Corobot ended up going to Jackson and the RoboDog to Doug, but everyone seemed reasonably pleased (the robots were . In the end I don’t think I could have hoped for a better experience (minus the hardware issues perhaps). Now that it’s apparent this was both the first and last RoboChamps competition (it has already been merged with the Imagine Cup), I feel particularly fortunate to have been invited. (The Imagine Cup, inspite of being for students, seems to attract far too many Eastern European hackers to give many people a chance.)

On a final note to this absurdly long post, Microsoft Robotics Developer Studio 2008 has just been released. You can download the Express version here for free, but there’s now also a commercial Standard version. I suppose the focus on hobbyists had to come to an end at some point, although the free version still looks quite capable. Also, I should point out that the release of the Mars Rover challenge (an especially interesting one) is now imminent in case anyone fancies giving RoboChamps a go – there will most likely be some pretty nice prizes for the winner/runners-up too, as with the previous challenges.

Windows SSH Server

This is a notice to anyone who might be interested in my open-source Windows SSH Server project. Windows SSH Server is a project I started earlier this year as an attempt to fully implement an SSH2 server using the .NET 3.5 framework (primarily C# with a bit of C++ for interfacing with Windows Console). The project is currently hosted on Launchpad. I have maintained a Bazaar repository of the entire source code.

It has grown to become just about usable now, providing a shell interface to any Windows Console application (e.g. cmd, PowerShell), though not yet programs such as edit. The protocol library SSH.NET has been written from scratch and is probably about 90% complete (minus extra features such as TCP port forwarding) and all the necessary cryptographic algorithms have been implemented/integrated in full. The main task in order to make it fully usable is finishing the Windows Console scanner (also very nearly usable) and then create a proper user-interface for authentication, which is currently hard-coded.  Of course, there are other aspects to the project such as the Windows Service (which is already working) and the admin interface, though they are not so important for the first release. I am also considering splitting the development into two seperate projects, one of them being the SSH server and the other an xterm shell for Windows Console applications (which would be utilised by the server). The main purpose of this is so that the xterm shell can be completed (or at least made stable) much sooner than the SSH server and can serve as a useful program by itself.

Unfortunately, although the project has come along very well I likely won’t be able to find the time to work much on such a large project in the near future. (A one-man team was never going to finish the job!) I am nonetheless keen to maintain the project and see it become mature with the help of other experienced coders. If you’re interested in contributing to Windows SSH Server (or the Windows Console xterm shell) in any way, please contact me via Launchpad and I’ll be glad to answer any questions and possibly set you up as a developer.