One of my pet-peeves is code written like this,

            if (0 != value) { ... }

This reads backwards to me. I hear echoes of Frank Oz in my head, "if zero the value is not". As cute as this dialect is coming from a pointy-eared muppet, it still takes a bit to translate back into the more common English phrasing, "if the value is not zero". It seems programmers who insist on writing in this style have forgotten that their source should be readable as well as executable. Don't force your readers to have to do grammar gymnastics as well as having to decipher your algorithmic gynmastics.

Once upon a time, this was considered good style in order to avoid accidentally writing something like,

            if (value = 0) { ... }

In C#, this is illegal. In most (all?) modern C and C++ compilers, this will generate a warning. (You do compile with warnings reported as errors right?) There ceases to be a good reason to write test expressions backwards. Let's let this style rest in peace.

Even if you think the above form has some redeeming value, let's all agree that any programmer that voluntarily writes something like,

            if (false == value) { ... }

should have an electric shock sent directly through their keyboard.

In my previous post I introduced a program I wrote to that uses the method described in First-Order Logic by Raymond M. Smullyan to prove an arbitrary propositional logic expression is a tautology. In this program I use some techniques that I want to describe. The first is the scanner. When writing scanners I have always hand written the scanner. There are two primary reasons for this, first I have never found scanners that difficult to write and, second, they are very time critical, often taking more than 20% of the overall parsing time, and auto-generated scanners are hard to optimize. Tableaux uses a hand-written scanner. The code for the scanner is in Scanner.cs in the zip file found here.

A scanner is a routine that takes text input and classifies it into a stream of tokens. Scanners typically give one token at a time. The scanner is the lowest level of the parsing process. Parsers are built on top of scanners and use the scanner results to determine the meaning of the source using some kind of grammar. The distinction between the parser and the scanner is somewhat arbitrary. You could just consider each character of the input as a token and build the parser up from there. Doing this is typically slower than a traditional scanner, however, so most parsers use a scanner. The line between the scanner and the parser is usually drawn at the lexical elements such as identifiers, reserved words, numeric and string constants, comments, etc. More formally, a lexical element is a string of characters that can be matched and classified by a regular expression. Scanner generators, such as Lex, use regular expressions to specify the scanner.

The trick to a fast scanner is to reduce the per-character cost of the scanner. One way to do this is to make sure you are executing the fewest number of instructions per-character-scanned as possible. A few of tricks I use to reduce the per-character cost include,

1. Use the switch statement
   • That included switch or case statement typically heavily optimize the result, often generating jump tables.
2. Pull fields into local variables and only write them at the before returning.
   • Local variables can be mapped to registers during code generation. Fields never will be. Stores to global memory (i.e. a field of a object allocated from the heap) are very hard for code generators to optimize. Local variable are much easier.
3. Make checking for boundaries (end of file or end of buffer) appear as a character.
   • This merges the end-of-file check with character classification.
   • In this case I use the character value 0 to indicate end of file. If I was willing to use unsafe code I would have taken advantage of the fact that the CLR ensures a 0 value at the end of every string.

One thing that looks slow that isn't is the GetChar() routine. Normally you would see that and think I am paying for a CALL/RET pair but his gets inlined in retail. I am paying for the end of buffer check every character but, as noted above, this can be removed if I wanted to use unsafe code, definitely overkill for a small program like tableaux.

I went a bit overboard, intentionally, with identifier. It handles C# style identifiers, handling Unicode letter and number classifications. To avoid calling the Unicode classification routines for every character I hard-coded the ASCII part and only call the Unicode classification routines when I encounter a non-ASCII potential identifier character. It is not that the classification routines are slow, it is that every cycle counts in the scanner and avoiding the CALL/RET and character table look is significant for file that contain mostly ASCII characters. Note also that I hard-code some non-identifier characters in the identifier internal loop. This avoids calling the Unicode classification routines for those character, which are the most common characters you might find after an identifier, which avoids calling the Unicode classification routines at all for most input.

When I was reading First-Order Logic by Raymond M. Smullyan I was fascinated by the second chapter in which he describes a method for proving a propositional logic expression is a tautology. This method is called the Tableau Method. The Tableau Method is a rather straight forward way to prove a statement is always going to be true by demonstrating that asserting it is false will result in a contradiction. The propositional logic expression language Dr. Smullyan uses is rather simple. I present a modified version of it here. My version contains a not operator (!), a conjunction operator (&), a disjunction operator (|) and an implication operator (→).¹ For example,

p & q

is true when both p and q are true;

p | q

is true when either p is true or q is true;

p → q

is true when p is false or p is true and q is also true; and finally,

!p

is true only when p is false. This should be very familiar to any programmer. A propositional logic expression is a tautology if it will always be true regardless of the value of its propositional variables. An example of a simple tautology is,

p | !p

which will be true if p is true or false. This statement is always true. This can be proven by simply demonstrating that asserting it is false results in a contradiction. For example, we assert a statement is false by prefixing it with a capital F or true with a capital T. For the above expression this would look like,

F p | !p

For this to be false both of the sub-expressions would also have to be false. This would then look like

F p
F !p

For !p to be false p would have to be true, which looks like,

T p

Now we have a contradiction, according to propositional logic, p cannot be both true and false so p | !p must always be true. Using the Tableau Method this would look like,

(1) F p | !p
(2) F p (1)
(3) F !p (1)
(4) T p (3)
X

where the X indicates that the tableau ends in a contradiction (i.e. is closed) and the numbers to the left label the expressions and the numbers to the right indicate which expression the assertion is derived from. To produce a tableau you first assert the expression is false then use the following table to add assertions,

When two expressions are asserted the table might branch. If the above table says "and" then both statement are asserted directly, but if it contains an "or" then both assertions must lead to a contradiction independently. For example, consider wanting to prove the transitive property of the implication operator, that is (p→q & q→r) → (p→r), this would start off with adding asserts until we are required to branch,

(1) F (p→q & q→r) → (p→r)
(2) T p→q & q→r (1)
(3) F p→r (1)
(4) T p→q (2)
(5) T q→r (2)
(6) T p (3)
(7) F r (3)

We now have to handle (4) and (5) with require us to branch the table. The first branch is the F p branch,

(8) F p (4)
X

This lead immediately to a contradiction because of (6) so this branch of the tableau is closed. We now need handle the T q branch,

(9) T q (4)

This doesn't lead to an immediate contradiction so we need to branch again for (5). The first branch for (5) looks like

(10) F q (5)
X

This again leads to an immediate contradiction, we already asserted that q must be true in (9). The second branch for (5) is the T r branch.

(11) T r (5)
X

This also lead to an immediate contradiction because of (7). Since all branches lead to a contradiction the original expression must always be true.

Putting this altogether we get,

This is a simple and elegant way to demonstrate proof by contradiction. Of course I just had to write a program to tell me whether an arbitrary propositional logic expression is a tautology and automatically generate the tableau.

You can find the source project that is works with the just released Visual Studio 2008 here. It requires VS 2008 because I am addicted to some of the new C# features, especially the var keyword.

¹ Dr. Sumullyan uses different characters for his operators but his characters are not as commonly included in browser fonts and are not as easy to type on a standard keyboard (using -> as a synonym of →) as the ones I use. << back

The mixin technique in my last post was a bit awkward to use with generic methods. It is much less awkward to use for classes, however. For example, if you want an expression evaluator much like I posted here, but you want to leave the result type open, you can use this technique to do it.

First, I declared a policy interface for the operators I wanted to abstract over,

            partial
            interface IOperatorPolicy<T> {
    T Add(T a, T b);
    T Subtract(T a, T b);
    T Multiply(T a, T b);
    T Divide(T a, T b);
}

Second, I created the operator policies for int and double. I could have created more, decimal, float, etc. but two is sufficient for demonstration.

            partial
            struct IntOperatorPolicy : IOperatorPolicy<int> {
    int IOperatorPolicy<int>.Add(int a, int b) { return a + b; }
    int IOperatorPolicy<int>.Subtract(int a, int b) { return a - b; }
    int IOperatorPolicy<int>.Multiply(int a, int b) { return a * b; }
    int IOperatorPolicy<int>.Divide(int a, int b) { return a / b; }
}

partial struct DoubleOperatorPolicy : IOperatorPolicy<double> {
    double IOperatorPolicy<double>.Add(double a, double b) { return a + b;
    double IOperatorPolicy<double>.Subtract(double a, double b) { return a - b; }
    double IOperatorPolicy<double>.Multiply(double a, double b) { return a * b; }
    double IOperatorPolicy<double>.Divide(double a, double b) { return a / b; }
}

Next are the expression nodes themselves. I wrap them in a generic class that takes the parameters. This mitigates some of the clutter caused by the policy.

            partial
            class Expression<T, OperatorPolicy>
    where OperatorPolicy : struct, IOperatorPolicy<T> {

    static OperatorPolicy _operatorPolicy = new OperatorPolicy();

    publicabstractpartialclass Expr {
        publicabstract T Evaluate();
    }

    publicpartialclass Literal : Expr {
        private T _literal;

        public Literal(T literal) { _literal = literal; }

        publicoverride T Evaluate() {
            return _literal;
        }

        publicoverridestring ToString() {
            return _literal.ToString();
        }
    }

    publicabstractpartialclass BinaryOp : Expr {
        private Expr _left;
        private Expr _right;

        protected BinaryOp(Expr left, Expr right) { _left = left; _right = right; }

        publicoverride T Evaluate() {
            return EvaluateOp(_left.Evaluate(), _right.Evaluate());
        }

        protectedabstract T EvaluateOp(T left, T right);
    }

    publicpartialclass Add : BinaryOp {
        public Add(Expr left, Expr right) : base(left, right) { }
        protectedoverride T EvaluateOp(T left, T right) {
            return _operatorPolicy.Add(left, right);
        }
    }
    
    publicpartialclass Add : BinaryOp {
        public Add(Expr left, Expr right) : base(left, right) { }
        protectedoverride T EvaluateOp(T left, T right) {
            return _operatorPolicy.Add(left, right);
        }
    }

    publicpartialclass Subtract : BinaryOp {
        public Subtract(Expr left, Expr right) : base(left, right) { }
        protectedoverride T EvaluateOp(T left, T right) {
            return _operatorPolicy.Subtract(left, right);
        }
    }

    publicpartialclass Multiply : BinaryOp {
        public Multiply(Expr left, Expr right) : base(left, right) { }
        protectedoverride T EvaluateOp(T left, T right) {
            return _operatorPolicy.Multiply(left, right);
        }
    }

    publicpartialclass Divide : BinaryOp {
        public Divide(Expr left, Expr right) : base(left, right) { }
        protectedoverride T EvaluateOp(T left, T right) {
            return _operatorPolicy.Divide(left, right);
        }
    }
}

Here the Expression class acts as a container of a family of classes. Once you have an instance of one of the Expr derived classes, calling Evaluate() is straight-forward. Unfortunately, constructing one is a bit of a challenge. To get a literal of the int expression you would need to do,

            var i1 = new Expression<int, IntOperatorPolicy>.Literal(1);

You can make this a little better by introducing a static method into Expression like,

            public
            static Expr L(T literal) {
    returnnew Literal(literal);
}

then the above becomes,

            var i1 = Expression<int, IntOperatorPolicy>.L(1);

This still a bit awkward especially when you want to construct a more complicated expression,

            var e = new Expression<int, IntOperatorPolicy>.Add(i1, i1);

This can be made significantly better by adding operator overloads to Expr as in,

            public
            abstract
            partial
            class Expr {
    publicabstract T Evaluate();
    publicstatic Expr operator +(Expr a, Expr b) {
        returnnew Add(a, b);
    }
    publicstatic Expr operator -(Expr a, Expr b) {
        returnnew Subtract(a, b);
    }
    publicstatic Expr operator *(Expr a, Expr b) {
        returnnew Multiply(a, b);
    }
    publicstatic Expr operator /(Expr a, Expr b) {
        returnnew Divide(a, b);
    }
}

now the e assignment can look like,

            var e = i1 + i1;

and finally, to make it look even better you can put the code to create the expression in a static method of a class that derives from Expression and closes the type parameters. Here are examples of one for int and a similar one for double.

            class TestInt : Expression<int, IntOperatorPolicy> {
    publicstaticvoid Run() {
        var iv = L(1) + L(2) * L(3);
        Console.WriteLine(iv.Evaluate());
    }
}

class TestDouble : Expression<double, DoubleOperatorPolicy> {
    publicstaticvoid Run() {
        var dv = L(1.2) + L(3.4) * L(5.6);
        Console.WriteLine(dv.Evaluate());
    }
}

This shows taking advantage of the C# compiler's operator overloading to produce an expression tree and the use of the L() method as a sort of cast to change a literal of T into a Literal<T>. The call to Evaluate() calculates the result of the expression as an int or double. The code generated, as discussed last time, is quite good when JIT'ing outside the debugger and using optimized retail bits.

This use of a policy struct is what I refer to as an adapter policy. The Expression class has an abstraction it supports, represented by IOperatorPolicy<T>, but this abstraction is not supported by any of the interesting types you would want to pass as Expression's T. This is solved by creating an adapter policy and passing that along with T. This allows a generic type to introduce an abstraction that is unknown to the types the generic wants to range over, allow us, as above, to pass int for Expression's T even though int doesn't implement IOperatorPolicy<T> itself.

Next time I will discuss another application of an adapter policy.

One thing that has always frustrated me about typical binary search routines found in libraries is they always assume you can easily produce a copy of the item you are searching for. What I mean is they typically follow this pattern,

            int BinarySearch<T>(IList<T> list, T item);

which takes a list of some type, left open here, and searches for it in the list. This is great if the very next thing you do next is insert item into the list. You already have item in hand so this signature is perfect. But if you don't have a ready item, and item is difficult to produce, you are stuck.

This happened to me just recently in my code. I had a sorted list of a data structure representing a span of source, similar to a TextPointer from WPF, called a TextRange. My version can quickly return the offset of the beginning of the span but, since TextRange tracks source changes, creating a new TextRange is expensive. When text in the editor is change, I receive the location of the change in an event. How do I figure out which one of my TextRanges was modified? Since the list is sorted, the obvious choice is to use a binary search which yields O(Log N) performance. Since my TextRanges are store in a List<TextRange>, obviously I should call List<T>.BinarySearch(). Unfortunately, TextRanges are expensive to produce; too expensive for a per-keystroke operation (I am glossing over some details for the sake of brevity; you need to trust me this is true). I have one of two choices, write my own BinarySearch() or create a fake TextRange that is a special TextRange that is less expensive to create and only used for searching. Neither choice is pleasant. Hand-rolled binary searches are not hard to right but, for some strange reason, I always get them wrong the first time.

What I needed is prebuilt and tested version of BinarySearch() that looks more like,

            int BinarySearch<T, K>(IList<T> list, K key, Converter<T, K> converter);

What this binary search routine does is find some key value in the list given a function that can convert any list item into the key. In my example, I would call it like,

            int location = BinarySearch(textRangeList, location, TextRangeToLocation);

where TextRangeToLocation looks something like,

            int TextRangeToLocation(TextRange range) { return range.Location; }

I don't need to produce a TextRange. I have the location I am looking for handy, I just need to know what, if any, TextRange contains the location. This method would do just that. You can even use a lambda function in C# 3.0 to get this all on one line,

            int location = BinarySearch(textRangeList, location, (n) => n.Location);

This is starting to look like a good idea. Let's code it up. Here is the method I ended up with,

            public
            static
            int BinarySearch<T, K>(IList<T> list, K value, 
    Converter<T, K> convert, Comparison<K> compare) {
    int i = 0;
    int j = list.Count - 1;
    while (i <= j) {
        int m = i + (j - i) / 2;
        int c = compare(convert(list[m]), value);
        if (c == 0)
            return m;
        if (c < 0)
            i = m + 1;
        else
            j = m - 1;
    }
    return ~i;
}

I added an extra parameter, compare. This is required because I didn't put any limits on what K can be and I need a way to compare one K with another. Many types, such as int, already know how to compare values of their own type. Typically types that are comparable, such as int, string, etc., implement IComparable<T>. We can accommodate such types by creating an overloaded version of BinarySearch() that looks like,

            public
            static
            int BinarySearch<T, K>(IList<T> list, K value, 
    Converter<T, K> convert) where K : IComparable<K> {
    return list.BinarySearch(value, convert, (n, m) => n.CompareTo(m));
}

which uses a lambda function to create a Comparison<T> for any type that supports IComparable<T>. Beware that this doesn't work well with reference types because it doesn't check for null. You can make it safer by putting struct in the where clause but that seemed overly restrictive to me.

Now that I have a BinarySearch() that meets my needs better than the built-in BinarySearch(), my next thought was I should evangelize the benefits my version of BinarySearch() to the team responsible for maintaining the CLR collections and, maybe, someday, I will have it as a native part of the CLR; maybe, someday. Then I remember extensions methods. In C# 3.0, with a slight modification to the above methods, they can appear as if they were already part of the CLR.

            public
            static
            class ListExtensionMethods {
    publicstaticint BinarySearch<T, K>(this IList<T> list, K value,
        Converter<T, K> convert, Comparison<K> compare) {
        int i = 0;
        int j = list.Count - 1;
        while (i <= j) {
            int m = i + (j - i) / 2;
            int c = compare(convert(list[m]), value);
            if (c == 0)
                return m;
            if (c < 0)
                i = m + 1;
            else
                j = m - 1;
        }
        return ~i;
    }

    publicstaticint BinarySearch<T, K>(this IList<T> list, K value, 
        Converter<T, K> convert) where K : IComparable<K> {
        return list.BinarySearch(value, convert, (n, m) => n.CompareTo(m));
    }
}

My version of BinarySearch() now appears as part of the methods of any type that implements IList<T>. This allows us to write,

            int location = textRangeList.BinarySearch(location, (n) => n.Location);

just like it was a native part of the CLR. No more hand-rolled BinarySearch()s!

Now that we have a ListExtensionMethods class, what other missing methods could we add? Here are a few that I thought would be useful,

            public
            static
            void Sort<T, K>(this List<T> list, 
    Converter<T, K> coverter, Comparison<K> compare) {
    list.Sort((n, m) => compare(convert(n), convert(m)));
}

publicstaticvoid Sort<T, K>(this List<T> list, 
    Converter<T, K>  converter) where K : IComparable<K> {
    list.Sort((n, m) => convert(n).CompareTo(convert(m)));
}

publicstaticvoid Swap<T>(this IList<T> list, int index1, 
    int index2) {
    var value = list[index1];
    list[index1] = list[index2];
    list[index2] = value;
}

publicstaticvoid Shuffle<T>(this IList<T> list) {
    int count = list.Count;
    Random r = new Random();
    for(int i = count - 1; i > 1; i--)
        list.Swap(i, r.Next(i - 1));
}

The Sort() methods above are allow you to extract a key for sorting using the same methods as above. These are not strictly necessary since constructing the lambda function I use is not that complicated but I believe they make the code more readable if you are consistent in how you extract keys from a list, so these are convenient wrappers that allow you to use the same methods to sort and search. Swap() and Shuffle() are throw-ins. They are really only useful for demo code or, in my case, test code. I used them to test the Sort() method which I used to test the BinarySearch() method.

Reading Pick a License, Any License by Jeff Atwood inspired me to pick one for the code I post on this blog. I picked Ms-PL. I certainly intended people to use the code I post, this make that intent more clear. I have modified the my copyright footer to reflect this selection.

The astute among you realized right away that PolyDictionary does not really avoid a cast, it just hides it. The TryGetValue() has a cast in it, highlighted below,

          public
          bool TryGetValue<K, V>(Key<K, V> key, out V value) {
            object objValue;
            if (_table.TryGetValue(key, out objValue)) {
                value = (V)objValue;
                returntrue;
            }
            value = default(V);
            returnfalse;
        }

So, can we get rid of the this cast? Yes, but the results are not very pleasant. One approach is to create one dictionary for each unique value type and then find that dictionary by that type and index into it using the key, instead of storing all the values in the same dictionary. This sounds similar to the original problem! All we need is a PolyDictionary that maps T to Dictionary<Key<T>, T>. We could code this but we couldn't run it because we would be defining PolyDictionary in terms of itself, consuming all of memory in the process. We need something like PolyDictionary but isn't a PolyDictionary.

OK, things will now get ugly. Have your barf bags on the stand-by! And, for the love of God, don't ever put this in a production application!

Now that is off my chest, here is one technique to avoid the cast. You can create a nested class SubDictionary that has a static instance variable which maps PolyDictionaries to Dictionary<Key<T>, T>. We can then parameterize SubDictionary by T which will create a unique dictionary for each T (I warned you it was ugly). This is because the CLR treats every instantiation of SubDictionary<T> as a unique type with unique static variables. Essentially we are tricking the CLR into producing a dictionary of T to Dictionary<PolyDictionary,Dictionary<Key<T>,T>>. Since the variable is static we need to find the version that is for the instance we are using, hence the key of PolyDictionary.

Here is the example,

    /* Never, Never use this code! */
    class PolyDictionary {
        
        class SubDictionaries<T> {
            internalstatic Dictionary<PolyDictionary, Dictionary<Key<T>, T>> Dictionaries = 
                new Dictionary<PolyDictionary,Dictionary<Key<T>,T>>();
        }

        public PolyDictionary() { }

        publicvoid Add<T>(Key<T> key, T value) {
            Dictionary<Key<T>, T> subDictionary = GetDictionary(key);
            subDictionary.Add(key, value);
        }

        public T Get<T>(Key<T> key) {
            Dictionary<Key<T>, T> subDictionary = FindDictionary(key);
            if (subDictionary != null)
                return subDictionary[key];
            thrownew KeyNotFoundException();
        }

        publicbool TryGetValue<T>(Key<T> key, out T value) {
            Dictionary<Key<T>, T> subDictionary = FindDictionary(key);
            if (subDictionary != null)
                return subDictionary.TryGetValue(key, out value);
            else {
                value = default(T);
                returnfalse;
            }
        }

        Dictionary<Key<T>, T> FindDictionary<T>(Key<T> key) {
            Dictionary<Key<T>, T> subDictionary;
            if (!SubDictionaries<T>.Dictionaries.TryGetValue(this, out subDictionary))
                returnnull;
            return subDictionary;
        }

        Dictionary<Key<T>, T> GetDictionary<T>(Key<T> key) {
            Dictionary<Key<T>, T> subDictionary;
            if (!SubDictionaries<T>.Dictionaries.TryGetValue(this, out subDictionary)) {
                subDictionary = new Dictionary<Key<T>, T>();
                SubDictionaries<T>.Dictionaries.Add(this, subDictionary);
            }
            return subDictionary;
        }
    }

This code has so many problems I don't know where to start. For one, it never frees memory, the dictionaries are in memory and will never be collected. I only include it to show that it can be done. As you can see, sometimes it is better to have a cast. There might be better techniques that eliminate some of the problems but my feeling is, why bother. The cast is not that bad.

In the last entry we defined a dictionary that can contain a value of any type and extra that value out of the dictionary without our code using a cast. The dictionary itself used a cast (which I show a "way" to remove it next time) but our code didn't. One problem it had, however, is it used declared keys instead of constructed keys. A declared key is a key can only be referenced by knowing the variable it is assigned to; a unique object. A constructed key, on the other hand, uses object equality instead of object identity for the key. String keys are constructed keys; you can read them from a file, calculate them or use a literal value. The dictionary will eventually compare the strings for equality. In other words, constructed keys can be constructed from data where declared keys cannot.

Can we modify PolyDictionary to use constructed keys? One way to do it is to create a new Key type that takes the constructed key type as a parameter. One such type is,

          struct Key<K, V> {
        public K Value;
        public Key(K value) {
            this.Value = value;
        }
        publicstaticimplicitoperator Key<K, V>(K value) {
            returnnew Key<K, V>(value);
        }
    }

This struct just wraps the key value. I use a struct instead of a class because structs will do a value comparison for equality by default, classes use reference equality.

The existing methods of PolyDictionary do not take this kind of key; but, we can add methods to PolyDictionary that do. For example, we can create an Add() method that looks like,

          public
          void Add<K, V>(Key<K, V> key, V value);

We can then create a Get() method that looks like,

          public V Get<K, V>(Key<K, V> key);

All these methods can be added directly to PolyDictionary because, through method overloading, they don't interfere with the original, declared key versions.

Using this dictionary looks like,

    Key<string, string> k1 = "k1";
    Key<string, int> k2 = "k2";
    Key<int, double> k3 = 3;

    PolyDictionary dictionary = new PolyDictionary();

    dictionary.Add(k1, "one");
    dictionary.Add(k2, 2);
    dictionary.Add(k3, 3.33);

    string v1 = dictionary.Get(k1);
    int v2 = dictionary.Get(k2);
    double v3 = dictionary.Get(k3);

    Console.WriteLine("v1 = {0}", v1);
    Console.WriteLine("v2 = {0}", v2);
    Console.WriteLine("v3 = {0}", v3);

The complete example of PolyDictionary follows,

          class PolyDictionary {
        private Dictionary<object, object> _table;

        public PolyDictionary() {
            _table = new Dictionary<object, object>();
        }

        publicvoid Add<K, V>(Key<K, V> key, V value) {
            _table.Add(key, value);
        }

        publicvoid Add<T>(Key<T> key, T value) {
            _table.Add(key, value);
        }

        publicbool Contains<K, V>(Key<K, V> key) {
            return _table.ContainsKey(key);
        }

        publicbool Contains<T>(Key<T> key) {
            return _table.ContainsKey(key);
        }

        publicvoid Remove<K, V>(Key<K, V> key) {
            _table.Remove(key);
        }

        publicvoid Remove<T>(Key<T> key) {
            _table.Remove(key);
        }

        publicbool TryGetValue<K, V>(Key<K, V> key, out V value) {
            object objValue;
            if (_table.TryGetValue(key, out objValue)) {
                value = (V)objValue;
                returntrue;
            }
            value = default(V);
            returnfalse;
        }

        publicbool TryGetValue<T>(Key<T> key, out T value) {
            object objValue;
            if (_table.TryGetValue(key, out objValue)) {
                value = (T)objValue;
                returntrue;
            }
            value = default(T);
            returnfalse;
        }

        public V Get<K, V>(Key<K, V> key) {
            return (V)_table[key];
        }

        public T Get<T>(Key<T> key) {
            return (T)_table[key];
        }

        publicvoid Set<K, V>(Key<K, V> key, V value) {
            _table[key] = value;
        }

        publicvoid Set<T>(Key<T> key, T value) {
            _table[key] = value;
        }
    }

Note: the implementation changed a bit from the previous example. The Get() methods now use the this property instead of calling TryGetValue(). This allows the Get() methods to be inlined at the cost of an additional cast or two in the code.

Rob's post Best Forum Practices recommends some guidelines for the WPF forum. My favorite is,

Recommended Steps for Answering [Questions]:

1) Answer the question

These are good guidelines for any question/answer style forum, not just WPF's.

I have to be honest; I didn’t expect the response I received from my Fatherly advice to new programmers article. There have been some very nice things written about it, not only in the comments but in other blogs. I don’t consider myself a very good writer and having my writing style praised was highly unexpected. I thank everyone for their kind words. Also, if you haven’t read the comments posted to the article yet, I highly recommend it. They offer interesting insights from a variety of perspectives.

I also recommend reading some of the blogs entries that have been written in response to it. I would like to point out one in particular from Jeff Atwood: Shipping Isn't Enough. I agree with him. You not only need to focus on shipping but make sure what you are working on is worth shipping. You need to focus on shipping programs people use and enjoy using.

Other bloggers have pointed out that you often don’t that much control over what you are working on, such as Mike-O-Matic’s Shipping Is Enough, Sometimes. And other point out that sometimes you don’t know if what you are working on will be used or not, as in Avonelle’s If a program falls in a forest....

These entries remind me of one more bit of advice: you are not your users. Just because you like something some particular way doesn’t mean that your users will, nor just because you would never use something doesn’t mean nobody needs it. You are not your users; you should get to know them.

I finally have a definitive answer to the question of why MyNode is needed. Consider the following, simplified, version of the LinkedList classes I posed,

          class C<X> { class N { } }
  class D: C<D.N> { }

This is really an obfuscated form of

          class N<X> { }
  class C<X> { }
  class D: C<N<?>> { }

where ? needs to be replaced by an infinite list if N<N<...>>. In other words, I am trying to define a type directly in terms of itself, a T where T=N<T>. This is not allowed. An additional type is required to break the cycle, such as M in,

          class M: N<M> { }

Then I can write,

          class D: C<M> { }

So, there we have it, MyNode is necessary to avoid defining a type directly in terms of itself. The unobfuscated version makes this much more clear. MyNode serves the same role as M does above.

Thanks again to Andrew for taking the time to beat this into my thick skull.

It looks like none of my children will become programmers. Instead of letting my fatherly advice to my new programmer son or daughter go to waste, I am going to inflict it on you. If you are newly embarking on the journey that is becoming a programmer, here is advice your father would tell you if he were a programmer. These are things I had to learn the hard way.

Keep Learning: Read. Go to conferences. Subscribe to journals. Take classes. Whatever it takes for you to keep learning, make it a priority. Learn about every language you can find. Take time to learn about any new frameworks, algorithms, techniques, models, paradigms, you can. Each gives you one more tool in your tool chest. Each will help you more easily tackle your next programming problem. Find a mentor, someone much better than you, and learn all they can teach you. Never stop learning.

Learn To Communicate: I often joke that the most important skill you can learn as a programmer is how to draw a rectangle on a white-board. Communication is critical to the job of a programmer. Communicating with customers, clients, users, co-workers, bosses, vice presidents, CEO's, board-members, VC capitalists, all will become important at some point in your career. Learn how to speak in public. Learn how to write in English. Learn to effectively communicate in person. Learn how to persuade without shouting, getting angry, or getting flustered. Learn how to speak without jargon. Help people understand what you are doing. Learn to break things into simple, understandable pieces. Learn to communicate by analogy and symbolism. Learn to communicate.

Be Predictable: Learn how fast you can comfortably program. Wait to predict how long it will take you to complete a task until you understand it. Allow for the unexpected. Plan for vacations and time-off. Live with your predictions. I don't believe I know a problem well enough to predict how long it will take to complete until I can break that task down into sub-tasks that each take no longer than 3 days (often less than one day). Live by this rule, under-promise, over-deliver. It is better to deliver in 10 days what you promised in 15 than to deliver in 10 days what you promised in 5. People depend, schedule, and plan around your predictions. Make them the best you can and make sure you can comfortably do them or you will be asked to live up to your uncomfortable predictions. You will not be good at it at first; to compensate, verify your predictions with someone more experienced. Learn to get better. Be predictable; other depend on you.

Own Up To Your Mistakes: You will make mistakes. How you handle your mistakes is how you will be judged. Learn how to say "I was wrong." If you underestimated how long it will take you to do something, tell people as soon as it is clear to you. If you broke the build, fix it. If you created a bug, fix it. Don't deny the mistake, don't make excuses for the mistake, don't figure out how to hide the mistake, don't blame others for the mistake, do something about it. Take ownership of your mistake or you will repeat it.

Never Let Bad Code Off Your Desk: Your job as a programmer is to write code that works, never let code off your desk you are not sure meets that criteria. Not only does it reflect badly on you, it is much more expensive, and much harder, to find a problem once it leaves your desk than before. Learn to love unit tests. Learn to love code coverage. Learn to test your code better than people who are paid to test it. Be embarrassed about bugs that are found after you have checked-in. Be especially embarrassed when a customer finds the bug. Don't rely on others to find your bugs for you, find them and fix them yourself. Don't hope it will work. Test it. Don't assume it will work. Test it. Don't whatever. Just test it. If you haven't tested it, it doesn't work; of this you can be sure. But, even if you are diligent with testing, bugs will get by you. You will make mistakes but try your best not to.

Programming is Fun But Shipping is Your Job: Programming is fun. It is the joy of discovery. It is the joy of creation. It is the joy of accomplishment. It is the joy of learning. It is fun to see your handiwork displaying on the screen. It is fun to have your co-workers marvel at your code. It is fun to have people use your work. It is fun have your product lauded in public, used by neighbors, and discussed in the press. Programming should be fun and if it isn't, figure out what is making it not fun and fix it. However, shipping isn't fun. I often have said that shipping a product feels good, like when someone stops hitting you. Your job is completing the product, fixing the bugs, and shipping. If bugs need fixing, fix them. If documentation needs writing, write it. If code needs testing, test it. All of this is part of shipping. You don't get paid to program, you get paid to ship. Be good at your job.

Remember these simple statements,

• Never stop learning.
• Communication is critical.
• Under promise, over deliver.
• "I was wrong."
• If it is not tested it doesn't work.
• Programming isn't your job, shipping is.

I honestly thought I was done with this topic but as it turns out I missed something. I stated firmly that "currently, in C#, we are stuck with the cast" but I was wrong. One of the great things about working at Microsoft is the people you can interact with. In back burner researching a definitive answer to Hallvard's question to my post of why linked list LinkedList<T> cannot be written,

          class LinkedList<T>: LinkedList<T, LinkedList<T>.Node> { }

I asked Andrew Kennedy to look at my page. I like talking to Andrew; I learn at least one new thing every time we talk. This was certainly no exception. He quickly pointed out something that was staring me squarely in the face but I missed entirely, folding my implementation of DoubleLinkedList<T> with DoubleLinkedList<T, N> and closing the node type directly will remove the cast. In other words, DoubleLinkedList<T> can be written without casts as,

          class DoubleLinkedList<T>: LinkedList<T, DoubleLinkedList<T>.DoubleNode>,
        IDoubleLinkedList<T> {

        publicclass DoubleNode: Node {
            DoubleNode _previous;

            publicoverride DoubleNode Next {
                get {
                    returnbase.Next;
                }
                set {
                    base.Next = value;
                    value._previous = this;
                }
            }

            public DoubleNode Previous { get { return _previous; } }
        }

        public IEnumerable<T> Backwards {
            get {
                if (Last != null) {
                    DoubleNode current = Last;
                    do {
                        yieldreturn current.Data;
                        current = current.Previous;
                    } while (current != Last);
                }
            }
        }
    }

which closes the node parameter instead of leaving it open. This is one of those head-slapping, "how stupid of me" moments like when someone points out that "you know, if you would have pushed the other pawn instead, you would have had checkmate in three moves." You can see that this is a straight forward application of the requires clause version (declaring it to be DoubleNode instead of requiring it). In my zest to introduce the concepts of the "this type" from LOOM and the requires clause from Scala, I missed what should have been obvious. Silly me.

This solution has the limitation that you cannot derive something like TripleLinkedList<T> from DoubleLinkedList<T> so my example still holds some water (TripleLinkedList<T, N> can be derived from DoubleLinkedList<T, N>) but it is not nearly so compelling. I still think that one of the two features would be very useful but I need a much better motivating example.

While I still don't have a definitive answer to Hallvard's question, I picked up this gem along the way. Not bad so far.

A straight forward implementation of a double-linked list that implements the interface,

          interface IDoubleLinkedList<T>: ILinkedList<T> {
        IEnumerable<T> Backwards { get; }
    }

can be implemented as,

          class DoubleLinkedList<T>: IDoubleLinkedList<T>, IEnumerable<T> {

        privateclass Node {
            public T Data;
            public Node Next;
            public Node Previous;
        }

        private Node _last;

        public DoubleLinkedList() { }

        publicvoid Add(T value) {
            Node newNode = new Node();
            newNode.Data = value;
            if (_last == null) {
                newNode.Next = newNode;
                newNode.Previous = newNode;
                _last = newNode;
            }
            else {
                newNode.Next = _last.Next;
                _last.Next.Previous = newNode;
                _last.Next = newNode;
                newNode.Previous = _last;
                _last = newNode;
            }
        }

        publicvoid Clear() {
            _last = null;
        }

        public IEnumerator<T> GetEnumerator() {
            if (_last != null) {
                Node current = _last;
                do {
                    current = current.Next;
                    yield return current.Data;
                } while (current != _last);
            }
        }

        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }

        public IEnumerable<T> Backwards {
            get {
                if (_last != null) {
                    Node current = _last;
                    do {
                        yield return current.Data;
                        current = current.Previous;
                    } while (current != _last);
                }
            }
        }
    }

With a casual comparison of this implementation to the implementation of LinkList<T> you will see that most of the methods are the same. Clear() and GetEnumator() are identical. Add() is nearly identical; in fact, it would be identical if we changed the Node implementation to

          private
          class Node {
            public T Data;
            private Node _next;
            public Node Previous;

            public Node Next {
                get {
                    return _next;
                }
                set {
                    _next = value;
                    value.Previous = this;
                }
            }
        }

With this change to the Node class, the only difference between LinkedList<T> and DoubleLinked<T> is the Node class and the Backwards property. It seems obvious we should use inheritance to share code. DoubleLinked<T> should derive from LinkedList<T>. To allow code sharing we need to make some changes to LinkedList<T>. First we need to change Node implementation to allow DoubleLink<T> to override the behavior of Next,

          protected
          class Node {
            public T Data;
            private Node _next;
            publicvirtual Node Next { get { return _next; } set { _next = value; } }
        }

Then we need to add,

          protected Node Last { get { return _last; } }

to allow DoubleLinked<T> to access to _last but not modify it. DoubleLink<T> need Last to implement Backwards. Additionally we need to introduce

          protected
          virtual Node CreateNode() { returnnew Node(); }

and change the first statement in the Add() method to,

            Node newNode = CreateNode();

to allow DoubleLinked<T> to override which class to create for the nodes in the list. This allows DoubleLink<T> to create DoubleNode instead of Node. With these changes we can now change the implementation of DoubleLink<T> implementation to,

          class DoubleLinkedList<T>: LinkedList<T>, IDoubleLinkedList<T> {

        protectedclass DoubleNode: Node {
            public DoubleNode Previous;

            publicoverride Node Next {
                get {
                    returnbase.Next;
                }
                set {
                    base.Next = value;
                    ((DoubleNode)value).Previous = this;
                }
            }
        }

        public IEnumerable<T> Backwards {
            get {
                if (Last != null) {
                    DoubleNode current = (DoubleNode)Last;
                    do {
                        yield return current.Data;
                        current = current.Previous;
                    } while (current != Last);
                }
            }
        }

        protectedoverride LinkedList<T>.Node CreateNode() { returnnew DoubleNode();  }
    }

There we have it. We used inheritance to share code. Unfortunately, we had to use casts to get this to work. The casts show we are now running into some limitations in the expressiveness of the C# type system. We know that all the items of the list will be of type DoubleNode but we need to convince the compiler (and the CLR) with a cast in the set part of the Next method and the Backwards property. It would be nice to write this without casts. Next time we look at a way to rid ourselves of one the cast in the Backwards property and the virtual CreateNode() method. We will also look at some possible ways to increase the expressiveness of C#'s type system to allow us to get rid of the final cast.

Last time I investigated several ways to implement an expression evaluator using a procedural style and several object oriented styles. I used this to demonstrate a data structure that doesn't lend itself well to being representing in an object oriented style. Another problematic structure is a linked list. It is not so much the linked list itself but writing it is such a way that is both type safe and also supports code sharing with, say, a doubly-linked list. What I want to implement is a class that implements the following interface.

          interface ILinkedList<T>: IEnumerable<T> {
        void Add(T value);
        void Clear();
    }

And then a subclass of that class that implements,

          interface IDoubleLinkedList<T>: ILinkedList<T> {
        IEnumerable<T> Backwards { get; }
    }

which inherits the implementation of Add() and Clear() and efficiently implements Backwards. For now, I will ignore the generic parameter and just implement a simple linked list. First, lets create a Node that will form the nodes of the linked list.

          class Node {
        publicobject Data;
        public Node Next;
    }

A linked list consists of a list of these nodes.

          class LinkedList: IEnumerable {
        Node _last;
    }

When an item is added to the list we will create a new node to hold it and create circular list where the _last instance variable will always point to the last node. This way we can quickly find both the last node and the first node of the list because, since the list is circular, the last node's Next field points to the first node. The reason I chose this particular way of implementing a linked list will be obvious if you have watched this video.

          public
          void Add(object value) {
            Node newNode = new Node();
            newNode.Data = value;
            if (_last == null) {
                newNode.Next = newNode;
                _last = newNode;
            }
            else {
                newNode.Next = _last.Next;
                _last.Next = newNode;
                _last = newNode;
            }
        }

Clearing the list is simple, just forget all the nodes.

          public
          void Clear() {
            _last = null;
        }

I implemented IEnumerable interface by using the new yield feature of C# 2.0. I start at the last node of the list, walk forward (to the first node) and yield an element, each successive loop will yield another element until we have yielded the last element (which is pointed to by _last).

          public IEnumerator GetEnumerator() {
            if (_last != null) {
                Node current = _last;
                do {
                    current = current.Next;
                    yieldreturn current.Data;
                } while (current != _last);
            }
        }

Now I have a reasonable implementation of a linked list. Next time we will take several different approaches to implement the interfaces defined above.

Returning to the Party example we where using, lets say you want to author a document that has 10 kazoos when the version 2 assembly is present but replaces them with 4 extra balloons if we only have the version 1 assembly. This can be written using a markup compatibility AlternateContent block. This might look like,

    <Party mc:Ignorable="v2"
      xmln="...assembly-v1-uri..."
      xmlns:v2="...assembly-v2-uri..."
      xmlns:mc="http://schemas.micrsoft.com/winfx/2006/markup-compatibility">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
        <mc:AlternateContent>
            <mc:Choice Requires="v2">
                <Balloon Color="Green" Shape="Dog" />
                <v2:Favor Kind="Kazoo" Quantity="10" />
            </mc:Choice>
            <mc:Fallback>
                <Balloon Color="Green" />
                <Balloon Color="Violet" />
                <Balloon Color="Orange" />
                <Balloon Color="Yellow" />
            </mc:Fallback>
        </mc:AlternateContent>
    </Party>

When the version 1 assembly is present this is interpreted as,

    <Party xmln="...assembly-v1-uri...">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
        <Balloon Color="Green" />
        <Balloon Color="Violet" />
        <Balloon Color="Orange" />
        <Balloon Color="Yellow" />
    </Party>

but in version 2 it is interpreted as,

    <Party xmlns="...assembly-v2-uri...">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
        <Balloon Color="Green" Shape="Dog" />
        <Favor Kind="Kazoo" Quantity="10" />
    </Party>

The content of the Choice element is used when the v2 namespace is available because it is mentioned in the Requires attribute. This corresponds to when the version 2 assembly is in use. If v2 is not available, the content of the Fallback element is used. AlternateContent supports an arbitrary list of Choice elements and the Requires can be an arbitrary list of prefix names.

Of course exchanging balloons for kazoos is not a very compelling example. For a more practical example, let's assume we have following classes in version 1 of an assembly,

    [ContentProperty("Content")]
    class Paragraph {
        private List<Inline> _content = new List<Inline>();
        public List<Inline> Content { get { return _content; } }
    }
    
    abstractclass Inline { }
    
    [ContentProperty("Text")]
    class Run : Inline {
        string _text;
        publicstring Text { get { return _text; } set { _text = value; } }
    }
    
    class Image : Inline {
        private Uri _source;
        public Uri Source { get { return _source; } set { _source = value; } }
    }

Now in the version 2 assembly we add a new class that looks like,

          class Graph : Inline {
        private List<Point> _points = new List<Point>();
        public List<Point> Points { get { return _points; } }
    }

Now we want to write a paragraph that uses the new Graph class when version 2 of the assembly is present, because, for example, it scales better, but in version 1 we will just use a bitmap image of the graph. This might look like,

    <Paragraph mc:Ignorable="v2"
      xmln="...assembly-v1-uri..."
      xmlns:v2="...assembly-v2-uri..."
      xmlns:mc="http://schemas.micrsoft.com/winfx/2006/markup-compatibility">
        <Run>The sales projects for the next quarter are</Run>
        <AlternateContent>
            <mc:Choice Requires="v2">
                <v2:Graph Data="1,2 2,3 3,5" />
            </mc:Choice>
            <mc:Fallback>
                 <Image Source="SalesData.jpg" />
            </mc:Fallback>
        </mc:AlternateContent>
    </Paragraph>

When the version 2 assembly is present, this is interpreted as,

    <Paragraph xmlns="...assembly-v2-uri...">
        <Run>The sales projects for the next quarter are</Run>
        <Graph Data="1,2 2,3 3,5" />
    </Paragraph>

but, when only version 1 available, it is interpreted as,

    <Paragraph xmln="...assembly-v1-uri...">
        <Run>The sales projects for the next quarter are</Run>
        <Image Source="SalesData.jpg" />
    </Paragraph>

using the bitmap instead of of the Graph class. This allows a document author to produce a file that takes advantage of a new feature, such as Graph with its better scaling properties, but still allows older versions to see a the graph at a lower fidelity.

These classes make a better example for another feature of markup compatibility, the ProcessContent attribute. Let's add another class in the version 2 assembly,

    [ContentProperty("Content")]
    class Glow : Inline {
        private List<Inline> _content = new List<Inline>();
        public List<Inline> Content { get { return _content; } }
    }

This class allows us to make the content to appear to glow when drawn. This allows us to write a document that looks like,

    <Paragraph mc:Ignorable="v2"
      xmln="...assembly-v1-uri..."
      xmlns:v2="...assembly-v2-uri..."
      xmlns:mc="http://schemas.micrsoft.com/winfx/2006/markup-compatibility">
        <Run>The word</Run> 
        <v2:Glow><Run>glow</Run></v2:Glow> 
        <Run>will appear to glow when it viewed with version 2.</Run>
    </Paragraph>

Unfortunately, with version 1, this is interpreted as,

    <Paragraph xmln="...assembly-v1-uri...">
        <Run>The word</Run> 
        <Run>will appear to glow when it viewed with version 2.</Run>
    </Paragraph>

The word "glow" disappeared because, by default, when an element is ignored its content is ignored as well. This default can be modified by using the ProcessContent attribute. If the original document is modified to be,

    <Paragraph 
      mc:Ignorable="v2" 
      mc:ProcessContent="v2:Glow"
      xmln="...assembly-v1-uri..."
      xmlns:v2="...assembly-v2-uri..."
      xmlns:mc="http://schemas.micrsoft.com/winfx/2006/markup-compatibility">
        <Run>The word</Run> 
        <v2:Glow><Run>glow</Run></v2:Glow> 
        <Run>will appear to glow when it viewed with version 2.</Run>
    </Paragraph>

This will tell the reader to just ignore the tags for Glow if it doesn't understand it but leave the content intact. This is then interpreted as,

    <Paragraph xmln="...assembly-v1-uri...">
        <Run>The word</Run> 
        <Run>glow</Run>
        <Run>will appear to glow when it viewed with version 2.</Run>
    </Paragraph>

for version 1, and will be interpreted as,

    <Paragraph xmlns:v2="...assembly-v2-uri...">
        <Run>The word</Run> 
        <Glow><Run>glow</Run></Glow> 
        <Run>will appear to glow when it viewed with version 2.</Run>
    </Paragraph>

when version 2 is present which is exactly what we wanted.

In general, forward compatibility allows previous versions of a document reader to read a document intended for later versions and render the content at a lower fidelity. This helps immensely when deploying a newer version of an assembly. During initial deployment it might not be that wide spread. You can have your users start taking advantage of the new features immediately because older versions will still be able to read newer documents, at a lower fidelity, even when they don't have the new assembly.

As we saw last time, XAML supports backwards compatibility. XAML also supports forward compatibility. Forward compatibility is easiest to understand from through a set of examples. Take the balloon example before. Say we want to write a XAML document that says, when you have the version 2 assembly, I want a dog shaped balloon. If, however, you only have the version 1 assembly, a default shaped balloon is fine. In other words, I want a document that contains some version 2 specific references in it but it is OK to just ignore them when you have a version 1 assembly. In our example, we want to mark the Shape property some way that the version 1 reader will know it can ignore the property. In XAML you can use the markup compatibility namespace to accomplish this. You can write,

    <Balloon Color="Red" v2:Shape="Dog" 
      xmlns="...assembly-v1-uri..."
      xmlns:v2="...assembly-v2-uri..."
      xmlns:mc="http://schemas.micrsoft.com/winfx/2006/markup-compatibility"
      mc:Ignorable="v2" />

This takes advantage of the Ignorable attribute of from the markup compatibility namespace. mc:Ignorable="v2" says that any attribute or element from the namespace associated with the "v2" prefix can be ignored and you would still have a document that would have an acceptable meaning. If a XAML reader only has the version 1 assembly, it would interpreted the above document as,

    <Balloon Color="Red" xmlns="...assembly-v1-uri..."  />

If the reader has the version 2 assembly, it would interpret it as,

    <Balloon Color="Red" Shape="Dog" xmlns="...assembly-v2-uri..." />

mc:Ignorable can also applies to elements. To see example of this lets define a class, Party, that is define as,

    [ContentProperty("Balloons")]
    publicclass Party {
        List<Balloon> _balloons = new List<Balloon>();
        public List<Balloon> Balloons { get { return _balloons; } 
    }

This allows us to define a Party instance that contains balloons. For this example, let's assume that Party was defined in the Version 1 assembly and is unmodified in the Version 2 assembly. We can then write a XAML document that looks like,

    <Party xmln="...assembly-v1-uri...">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
    </Party>

We can now also write a document that will include a third dog shaped balloon but only if we are using the version 2 assembly, and not include if we are still using version 1. It looks like,

    <Party mc:Ignorable="v2"
      xmln="...assembly-v1-uri..."
      xmlns:v2="...assembly-v2-uri..."
      xmlns:mc="http://schemas.micrsoft.com/winfx/2006/markup-compatibility">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
        <v2:Balloon Color="Green" Shape="Dog" />
    </Party>

This will be interpreted exactly as the prior document when reading it with version 1. With version 2, however, it would be interpreted as if it was,

    <Party xmlns="...assembly-v2-uri...">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
        <Balloon Color="Green" Shape="Dog" />
    </Party>

We can also add a new a new class, such as Favor, that can be used in a document such as,

    <Party mc:Ignorable="v2"
      xmln="...assembly-v1-uri..."
      xmlns:v2="...assembly-v2-uri..."
      xmlns:mc="http://schemas.micrsoft.com/winfx/2006/markup-compatibility">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
        <v2:Balloon Color="Green" Shape="Dog" />
        <v2:Favor Kind="Kazoo" Quantity="10" />
    </Party>

This doesn't affect the version 1 interpretation of the document, but adds 10 kazoos to the version 2 interpretation. If the author determines that the kazoos are really necessary to the interpretation of either the reference to v1 can be removed and the document rewritten to,

    <Party xmlns="...assembly-v2-uri...">
        <Balloon Color="Red" />
        <Balloon Color="Blue" />
        <Balloon Color="Green" Shape="Dog" />
        <Favor Kind="Kazoo" Quantity="10" />
    </Party>

or the the ignorable attribute can just be removed which amounts to an equivalent document given subsumption described in the previous entry.

Last time we took a procedural approach to solve the expression problem. This time I will demonstrate an object-oriented approach. As a reminder, we want to model the following forms of expressions,

number	Literal
expr + expr	Add
expr - expr	Subtract
expr * expr	Multiply
expr / expr	Divide

The most natural thing to do in an object-oriented language is to make each of the above expression forms its own class. First, I will introduce a base class to provide an expression abstraction.

          abstract
          class Expr {
    }

Now I will now create a sub-class for each expression.

          class Literal: Expr {
        protecteddouble Value;

        public Literal(double value) {
            Value = value;
        }
    }
    
    abstractclass BinaryExpr: Expr {
        protected Expr Left;
        protected Expr Right;

        public BinaryExpr(Expr left, Expr right) {
            Left = left;
            Right = right;
        }
    }
    
    class Add: BinaryExpr {
        public Add(Expr left, Expr right) : base(left, right) { }
    }
    
    class Subtract: BinaryExpr {
        public Subtract(Expr left, Expr right) : base(left, right) { }
    }
    
    class Multiply: BinaryExpr {
        public Multiply(Expr left, Expr right) : base(left, right) { }
    }
    
    class Divide: BinaryExpr {
        public Divide(Expr left, Expr right) : base(left, right) { }
    }

I created a base class for the binary expressions which I will take advantage of below.

To evaluate the expression I will add an abstract virtual method, Evaluate(), to Expr.

          abstract
          class Expr {
        publicabstractdouble Evaluate();
    }

Then I will override the Evaluate() method for each of the above classes. Evaluating a literal is simply returning the value of the literal so I modified the Literal class to,

          class Literal: Expr {
        protecteddouble Value;

        public Literal(double value) {
            Value = value;
        }

        publicoverridedouble Evaluate() {
            return Value;
        }
    }

All binary expressions need to evaluate their left-hand expression and right-hand expression and then perform their operation on the results. To represent this, I overrode Evaluate() to evaluate both Left and Right and then call a newly introduced EvaluateOp() method. I sealed the Evaluate() method because I want descendants to override EvaluateOp() not Evaluate().

          abstract
          class BinaryExpr: Expr {
        protected Expr Left;
        protected Expr Right;

        public BinaryExpr(Expr left, Expr right) {
            Left = left;
            Right = right;
        }

        publicsealedoverridedouble Evaluate() {
            return EvaluateOp(Left.Evaluate(), Right.Evaluate());
        }

        protectedabstractdouble EvaluateOp(double left, double right);
    }

Now I can implemented the concrete descendents of BinaryExpr.

          class Add: BinaryExpr {
        public Add(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left + right;
        }
    }

    class Subtract: BinaryExpr {
        public Subtract(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left - right;
        }
    }

    class Multiply: BinaryExpr {
        public Multiply(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left * right;
        }
    }

    class Divide: BinaryExpr {
        public Divide(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left / right;
        }
    }

The advantages an object-oriented approach are,

1. New data types can be added without affecting any of the other data types.
2. Each data type is encapsulated, only the data type needs to have access the instance variables.
3. All the operations affecting the instance variables are in one place, the methods of instance variable's class.
4. New operations can be added as abstract methods. The compiler will then generate an error if an operation is not implemented for one of the leaf classes.
5. Efficient storage is natural. Adding field to one of the expression types do not affect the others.

To demonstrate how easy it is to add a new data type I will again add support for Power.

expr ^ expr

Power

To do this I will add a class to represent the Power expression form. This looks like,

          class Power: BinaryExpr {
        public Power(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return Math.Pow(left, right);
        }
    }

Note that the Power data type can be added without modifying the other classes.

The disadvantages to an object-oriented approach are,

1. It is difficult to add new operations because adding an operation requires modifying all the classes.
2. The logic for each operation is spread over multiple classes and often multiple files. This makes it cumbersome to get a complete picture what the operation does.
3. It is very difficult to dynamically add operations and can't be done without careful planning.

To demonstrate some of the difficulties of adding a new operation, I will add the Print operation. First I will modify the base Expr class to add an abstract Print() method.

          abstract
          class Expr {
        publicabstractdouble Evaluate();
        publicabstractvoid Print();
    }

Now I will override this method in each class similar to the way I did for the Evaluate() method.

          class Literal: Expr {
        protecteddouble Value;

        public Literal(double value) {
            Value = value;
        }

        publicoverridedouble Evaluate() {
            return Value;
        }

        publicoverridevoid Print() {
            Console.Write(Value);
        }
    }

    abstractclass BinaryExpr: Expr {
        protected Expr Left;
        protected Expr Right;

        public BinaryExpr(Expr left, Expr right) {
            Left = left;
            Right = right;
        }

        publicsealedoverridedouble Evaluate() {
            return EvaluateOp(Left.Evaluate(), Right.Evaluate());
        }

        protectedabstractdouble EvaluateOp(double left, double right);

        publicsealedoverridevoid Print() {
            Left.Print();
            PrintOp();
            Right.Print();
        }

        protectedabstractvoid PrintOp();
    }

    class Add: BinaryExpr {
        public Add(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left + right;
        }

        protectedoverridevoid PrintOp() {
            Console.Write(" + ");
        }
    }

    class Subtract: BinaryExpr {
        public Subtract(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left - right;
        }

        protectedoverridevoid PrintOp() {
            Console.Write(" - ");
        }
    }

    class Multiply: BinaryExpr {
        public Multiply(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left * right;
        }

        protectedoverridevoid PrintOp() {
            Console.Write(" * ");
        }
    }

    class Divide: BinaryExpr {
        public Divide(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return left / right;
        }

        protectedoverridevoid PrintOp() {
            Console.Write(" / ");
        }
    }
    
    class Power: BinaryExpr {
        public Power(Expr left, Expr right) : base(left, right) { }

        protectedoverridedouble EvaluateOp(double left, double right) {
            return Math.Pow(left, right);
        }

        protectedoverridevoid PrintOp() {
            Console.Write(" ^ ");
        }
    }

As you can see, each of the classes needed to be modified to implement Print(). You can also note that the compiler complained until each of the classes implemented the Print() operation. This is because we used an abstract method in the Expr class.

If you compare the procedural approach vs. the object-oriented approach you will notice that they are pretty much opposites. It is easy to add operations in the procedural approach but difficult using an object-oriented approach. Adding data types is difficult using in a procedural approach, but easy in an object-oriented approach. Data needs to be public in procedural, but can be private in object oriented. When deciding which approach to use you need to try an predict what will occur more often, adding new data types or adding new operations. What I will present next are some compromise solutions that balance the advantages and disadvantages.

Mike Harsh and Mark Boulter demo'ed Cider for MSDN. Check it out...

Mark Boulter and Brian Pepin make an appearance on Channel 9 to explain and demo Cider. Check it out...

Brian Pepin has started to blog about Cider's architecture. Check it out...

If you missed the PDC and Eric Rudder's keynote address where Cider was demonstrated you can watch it here. Mark Boulter demonstrates it with Joe Marini demonstrating Sparkle. Their part begins around 37 minutes into the keynote.

XAML provides two ways to set a property, either through a Property Attribute or through a Property Element. We covered Property Attributes last time, this time we will focus on the Property Element.

A Property Element is an element that, instead of creating an object instance, set the value of a property. The following is equivalent to the example given in Part I but uses Property Elements instead of Property Attributes.

  <Button xmlns="http://schemas.microsoft.com/winfx/avalon/2005">
    <Button.Content>
      Hello, World!
    </Button.Content>
  </Button>

The loader distinguishes a Object Element from a Property Element by the presents of the '.' in the name. The first part of the name is a reference to a type and the second part, after the dot, refers to the property name (we will discuss exactly why this is when we discuss Attached Properties). Here we use Button in both Property Elements. Property Elements are necessary when the value of the property cannot be expressed as a string. For example, you can use a Property Element to set the content of a Button to be another Button (not sure why you would want that, but suspend disbelieve for a second) as in,

  <Button xmlns="http://schemas.microsoft.com/winfx/avalon/2005">
    <Button.Content>
      <Button Content="Hello, World!" />
    </Button.Content>
  </Button>

This can be written more explicitly as,

  <Button xmlns="http://schemas.microsoft.com/winfx/avalon/2005">
    <Button.Content>
      <Button>
        <Button.Content>
          Hello, World!
        </Button.Content>
      </Button>
    </Button.Content>
  </Button>

As you can see, using Property Elements can become a bit repetitive. To mitigate this, one of the properties of a class can be designated as the Content Property which tells the load to assign direct content of the element to that property. In the case of Button (and all ContentControls) the Content Property is, oddly enough, set to the property named Content. This allows us to write something like,

  <Button xmlns="http://schemas.microsoft.com/winfx/avalon/2005">
    Hello, World!
  </Button>

for the first example above, and,

  <Button xmlns="http://schemas.microsoft.com/winfx/avalon/2005">
    <Button>Hello, World!</Button>
  </Button>

for the second. Most Avalon classes have a Content Property defined. For Panel's, such as DockPanel, Grid, and Canvas, their Content Property is set to their Children collection. Any direct content of a Panel is assumed to be content intended for the Children property. This means the following,

  <StackPanel xmlns="http://schemas.microsoft.com/winfx/avalon/2005">
    <Button>OK</Button>
    <Button>Cancel</Button>
  </StackPanel>

is an abbreviated version of,

  <StackPanel xmlns="http://schemas.microsoft.com/winfx/avalon/2005">
    <StackPanel.Children>
      <Button>
        <Button.Content>
          OK
        </Button.Content>
      </Button>
      <Button>
        <Button.Content>
          Cancel
        </Button.Content>
      </Button>
    </StackPanel.Children>
  </StackPanel>

Now, with Property Elements and Content Property Attributes and Object Element and Property Attribute from Part I, we have covered the fundamentals of XAML.

Cider is now announced! In case you missed it at the PDC, Cider is the code name for the Visual Studio Designer for WPF (pronounced Avalon according to Chris) that will be delivered in Orcas. We also announced the Expression product line that includes a different designer called Sparkle. Other than the obvious difference between Sparkle and Cider, Cider is in VS, Sparkle is a stand-alone product, Cider will be a designer for developers, Sparkle will be a designer targeted at professional designers.

For those that were asking about what I was working on, I wasn't trying to be coy, I just didn't want to spill the beans early.

I will be more forthcoming in the months ahead and try to keep you up-to-date with our progress.

If I missed you at the PDC, I am sorry about that. Feel free to ask your questions here or via e-mail (chuckj directed through microsoft.com).

I am off to PDC. This will be my first PDC as an "insider" instead of a regular attendee, I am looking forward to it. We are announcing some very exciting things! I am not going to be presenting but I will be available to chat. I plan to spend most of my time in the "Big Room". If you don't know what that is now, you will once you get there. I should be easy to spot, I will be the guy in a blue Microsoft shirt and tan pants... ;-).

When I run across a particularly fast elegant algorithm I often find myself asking, “Why it is fast?” How can I make my algorithms fast like the author of this one did? I have found that the answer usually is found in how the algorithm manages data. How does the algorithm preserve work and prevent recalculating information? To step back a bit, there are only three ways to make some code go faster, find a way to make what it is doing faster, find a way to do less, find some other time to do it. The most elegant algorithms do the second well; they do less. For a few entries I want to look at various algorithms to see what makes them fast (or not so fast).

The first set of algorithms I want to investigate are some of the most fundamental, sorting. The simplest sort to write is the selection sort. In C# it looks like,

          static void SelectionSort(int[] a) {
         for (int i = 0; i < a.Length - 1; i++)
             for (int j = i + 1; j < a.Length; j++)
                 if (a[i] > a[j])
                     Swap(a, i, j);
  }

where Swap looks like,

          static
          void Swap<T>(T[] a, int i, int j) {
      T v = a[i];
      a[i] = a[j];
      a[j] = v;
  }

This sort finds the smallest item in the list and puts it first, and then it finds the second smallest and puts it second, etc. Even though it is very easy to write and relatively easy to verify, it isn’t very fast. We could improve this by in-lining the Swap() method. Additionally, we can limit the number of swaps to a.Length by only swapping the value we know is the smallest. A version that includes both optimizations is,

          static
          void ImprovedSelectionSort(int[] a) {
      for (int i = 0; i < a.Length - 1; i++) {
          int min = i;
          for (int j = i + 1; j < a.Length; j++)
              if (a[min] > a[j])
                  min = j;
          if (i == min) continue;
          int v = a[i];
          a[i] = a[min];
          a[min] = v;
      }
  }

These optimizations are examples of making what we are doing faster. Unfortunately, we still with do on the order of O(N²) comparisons even though we reduced the number of moves to O(N) and removed any overhead of doing a call in the middle of the loop. What we really want to do is less. To do less we need to come up with information we are not using or information we are throwing away.

Since we are trying to optimize the number of comparisons (since we got the moves down to O(N)) we should examine them closely. We need to come up with a way to make each comparison do more. One thing we should notice is the above algorithm totally ignores the transitive nature of a compare. That is if A > B and B > C then A > C. If we know that a[10] > a[11] and a[11] > a[12] we don’t need to physically do the comparison between a[10] and a[12] to know at a[10] > a[12], but how do we take advantage of that? In my next "sorting" post I will investigate an algorithm that takes advantage of this.