...Removing All Doubt

"If you are using a loop, you're doing it wrong."

That is the advice one of my college professors told us when he was teaching us APL. APL was designed to perform vector and matrix operations. Programming in APL is an exercise in stringing operators together to perform strange and wonderful things. Using a loop is just wrong and slows things down.

It is similar with LINQ, if you are using a loop you are doing it wrong. I find myself doing a lot of prototyping lately and I am forcing myself to use LINQ; not because I don't like it, far from it, I really like LINQ, but using loops is so ingrained into my psyche that I have to stop myself and force myself to think in LINQ. Every time I am tempted to write a loop that involves a collection or an array I ask myself, could I use LINQ instead? Programmers with more of a database background seem to take to LINQ like a duck to water. They think in sets and vectors, I don't, but I am getting there.

For example sometimes I find myself needing to return an IEnumerable<T> when I have a List<T> but of a different T. This often happens when I want to keep internal implementation details private. My internal List<T> might have the actual class but I need to return an enumerable for some interface. Before I would simply write a loop using the C# 2.0's yield syntax,

List<Foo> foos = new List<Foo>();

...

public IEnumerable<IFoo> Foos {
    get {
        foreach (Foo f in foos)
            yield return f;
    }
}

This loop involves a collection, can I use LINQ? Sure! By using LINQ's Cast<T>() method this can be replaced with,

public IEnumerable<IFoo> Foos {
    get { return foos.Cast<IFoo>(); }
}

If you are trying to find if a list contains an object by some name, you could write a loop like,

public bool Contains(string value) {
    foreach (Foo foo in foos)
        if (foo.Name == value)
            return true;
    return false;
}

Using LINQ this might look like,

public bool Contains(string value) {
    return (from foo in foos where foo.Name == value select foo).Any();
}

A nice thing about LINQ is you can perform complicated queries in pieces. With deferred execution of enumerators, this is fairly efficient as well. This is really helpful in the debugger. In one chunk of code I was writing I needed to coalesce adjacent ranges that are marked with the same text value. Assume you have a structure called Range that looks like,

struct Range {
    public int Start;
    public int Length;
}

and another struct that labels the ranges with names,

struct NamedRange {
    public string Name;
    public Range Range;
}

Now lets have a routine that calculates the range information over some stream,

public IEnumerable<NamedRange> GetNamedRanges(Stream stream) {
    ...
}

Lets assume that name ranges are some things like "whtespace", "reserved", "identifier", "number" "string", etc. as you might expect to receive from a lexical scanner like found in this post.

What I want to do with these ranges is to convert the names into styles such as you might find referencing a CSS style sheet. So, in effect, I am mapping NameRange values to StyledRange values where StyleRange would look something like,

struct StyledRange {
    public Style Style;
    public Range Range;
}

Lets create a dictionary that maps range names to styles such as,

styleMap["number"] = new Style() { Name = "green" };
styleMap["reserved"] = new Style() { Name = "bold" };

I only wanted to highlight numbers and reserved words, for everything else I will use the default style,

defaultStyle = new Style { Name = "normal" };

We can translate our named ranges directly into styled ranges by using a LINQ query expression such as,

var ranges = GetNamedRanges(stream);
var styledRanges = from range in ranges
                   select new StyledRange() {
                       Style = styleMap.MapOrDefault(range.Name) ?? defaultStyle,
                       Range = range.Range
                   };

where MapOrDefault() is an extension method for IDictionary<TKey, TValue> that looks like,

public static TValue MapOrDefault(this IDictionary dictionary, TKey key) {
    TValue result;
    if (dictionary.TryGetValue(key, out result))
        return result;
    return default(TValue);
}

which is patterned after the existing LINQ methods for IEnumerable<T>, FirstOrDefault() and LastOrDefault().

Since many of the ranges that have different names will have the same style, it would be nice to coalesce adjacent styles together so no two adjacent ranges have the same style. In other words, we only want a new styled range when the style changes. The above query expression just produces a one-to-one mapping of named range to styled range. What we need is something that will merge adjacent ranges. Do do this I will introduce another extension method, Reduce<T>() for IEnumerable<T>,

public static IEnumerable<T> Reduce<T>(this IEnumerable<T> e,
    Func<T, T, bool> match,
    Func<T, T, T> reduce) {
    var en = e.GetEnumerator();
    T last;
    if (en.MoveNext()) {
        last = en.Current;
        while (en.MoveNext()) {
            if (!match(last, en.Current)) {
                yield return last;
                last = en.Current;
            }
            else
                last = reduce(last, en.Current);
        }
        yield return last;
    }
}

What this method does is if two adjacent elements match (as defined by the match delegate returning true) they will be reduced into one element by calling the reduce delegate. For example, the Sum<T>()standard extension method could be implemented using Reduce<T>() as,

var sum = numbers.Reduce((a, b) => true, (a, b) => a + b).First();

Now that we have Reduce<T>(), lets reduce the list of styled ranges to coalesce the adjacent ranges with the same style. This can be done by,

styledRanges = styledRanges.Reduce(
    (r1, r2) => r1.Style == r2.Style,
    (r1, r2) => new StyledRange() {
        Style = r1.Style,
        Range = MergeRanges(r1.Range, r2.Range)});

MergeRanges() referenced above, is,

Range MergeRanges(Range r1, Range r2) {
    return new Range() { Start = r1.Start, Length = r2.Start - r1.Start + r2.Length };
}

In my example, this took 18 ranges for a typical line of C# source down to 7 ranges. Pretty good. But I noticed that some of those ranges were styling whitespace as "normal". This seems like a waste; why switch back from green to black text for writing whitespace? Why not combine those with adjacent ranges instead? A simple approach to this is to add the following code prior to mapping the styles,

ranges = ranges.Reduce(
    (r1, r2) => r1.Name == "whitespace" || r2.Name == "whitespace",
    (r1, r2) => new NamedRange() {
        Name = r1.Name == "whitespace" ? r2.Name : r1.Name,
        Range = MergeRanges(r1.Range, r2.Range)
    });

This says to merge whitespace ranges with adjacent non-whitespace ranges. This reduces the range count from 7 to 4. Not bad from the original 18 and that was just for one line of source. This savings adds up quickly over an entire file.

The complete example, made as a function, looks like,

IEnumerable<StyledRange> StyleRanges(IEnumerable<NamedRange> ranges) {

    // Merge whitespace ranges with adjacent non-whitespace ranges
    ranges = ranges.Reduce(
        (r1, r2) => r1.Name == "whitespace" || r2.Name == "whitespace",
        (r1, r2) => new NamedRange() {
            Name = r1.Name == "whitespace" ? r2.Name : r1.Name,
            Range = MergeRanges(r1.Range, r2.Range)});

    // Map named ranges to styles.
    var styledRanges = from range in ranges 
                       select new StyledRange() { 
                           Style = styleMap.MapOrDefault(range.Name) ?? defaultStyle,
                           Range = range.Range };

    // Merge adjacent ranges with the same style.
    styledRanges = styledRanges.Reduce(
        (r1, r2) => r1.Style == r2.Style,
        (r1, r2) => new StyledRange() {
            Style = r1.Style,
            Range = MergeRanges(r1.Range, r2.Range)});

    return styledRanges;
}

There are a few nice things about this function. First, it builds up an IEnumerable<T> but this enumerable doesn't execute until one of its enumerators is enumerated. This is due to the deferred execution of enumerators. Second, even though deferred execution makes single step debugging challenging, you can get a picture of what the function will do by using ToArray() in the watch windows on the intermediate results. This allows you to inspect the intermediate result to see if the mapping or reducing is what you expected. Third, this routine has no loops. It operates on each enumerable as a set. Now some of you will rightly say there is a loop buried in the Reduce<T>() method. True; Reduce<T>() is just like many other LINQ extension methods, they contain loops implied by the returned enumerator. But LINQ allows me to write code that communicates what I am trying to do without it being obscured by the details of how it is done. I think of LINQ not so much as a set of features in C# but a way of programming. A way of programming that, if you are using loops, you are doing it wrong.

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();

    public abstract partial class Expr {
        public abstract T Evaluate();
    }

    public partial class Literal : Expr {
        private T _literal;

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

        public override T Evaluate() {
            return _literal;
        }

        public override string ToString() {
            return _literal.ToString();
        }
    }

    public abstract partial class BinaryOp : Expr {
        private Expr _left;
        private Expr _right;

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

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

        protected abstract T EvaluateOp(T left, T right);
    }

    public partial class Add : BinaryOp {
        public Add(Expr left, Expr right) : base(left, right) { }
        protected override T EvaluateOp(T left, T right) {
            return _operatorPolicy.Add(left, right);
        }
    }
    
    public partial class Add : BinaryOp {
        public Add(Expr left, Expr right) : base(left, right) { }
        protected override T EvaluateOp(T left, T right) {
            return _operatorPolicy.Add(left, right);
        }
    }

    public partial class Subtract : BinaryOp {
        public Subtract(Expr left, Expr right) : base(left, right) { }
        protected override T EvaluateOp(T left, T right) {
            return _operatorPolicy.Subtract(left, right);
        }
    }

    public partial class Multiply : BinaryOp {
        public Multiply(Expr left, Expr right) : base(left, right) { }
        protected override T EvaluateOp(T left, T right) {
            return _operatorPolicy.Multiply(left, right);
        }
    }

    public partial class Divide : BinaryOp {
        public Divide(Expr left, Expr right) : base(left, right) { }
        protected override 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) {
    return new 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 {
    public abstract T Evaluate();
    public static Expr operator +(Expr a, Expr b) {
        return new Add(a, b);
    }
    public static Expr operator -(Expr a, Expr b) {
        return new Subtract(a, b);
    }
    public static Expr operator *(Expr a, Expr b) {
        return new Multiply(a, b);
    }
    public static Expr operator /(Expr a, Expr b) {
        return new 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> {
    public static void Run() {
        var iv = L(1) + L(2) * L(3);
        Console.WriteLine(iv.Evaluate());
    }
}

class TestDouble : Expression<double, DoubleOperatorPolicy> {
    public static void 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 of the limitations of C# generics is you cannot abstract over operators. That is not completely true, you can if the base class used in where clause has operators; but, since operators are more useful, and more common, on value types, that is only marginally helpful. Also, this abstraction is provided by the base class not by using generics. What I would like to do is declare that my type  parameter requires the type to implement a particular operator. For example, to create a generic Add() method I would like to specify that the type parameter must implement the + operator and then be able to use the + operator in my code such as,

// Invalid C#
static T Add<T>(T a, T b) where T: T operator +(T, T) {
    return a + b;
}

C# doesn't support this but you can get somewhat close by supplying a policy struct like I described in this post. The policy interface and the int policy struct would look like,

interface IAddPolicy<T> {
    T Add(T a, T b);
}

struct IntAddPolicy : IAddPolicy<int> {
    public int Add(int a, int b) { return a + b; }
}

This allows you to write the following,

static T Add<T, P>(T a, T b) where P: struct, IAddPolicy<T> {
    return new P().Add(a, b);
}

Unfortunately the policy struct cannot be inferred from the parameters so you have to supply the type parameter explicitly,

var i = Add<int, IntAddPolicy>(3, 4);

which doesn't look pretty and generates less than efficient code for the Add() method on an i386 architecture,

00000000  sub         esp,8 
00000003  xor         eax,eax 
00000005  mov         dword ptr [esp],eax 
00000008  mov         dword ptr [esp+4],eax 
0000000c  mov         byte ptr [esp],0 
00000010  movsx       eax,byte ptr [esp] 
00000014  mov         byte ptr [esp+4],al 
00000018  add         ecx,edx 
0000001a  mov         eax,ecx 
0000001c  add         esp,8 
0000001f  ret              

This generates code to initialize the policy structure we don't actually use. We can get rid of that by recasting this a bit to save the dummy struct allocation by putting the Add() method in a wrapping class that takes the type parameters. The type would allocate the struct instead of the method. This looks like,

class Adder<T, P>
    where P: struct, IAddPolicy<T>
{
    static P AddPolicy = new P();
    static public T Add(T a, T b) { return AddPolicy.Add(a, b); }
}

which generates the following code for Add(),

00000000  add         ecx,edx 
00000002  mov         eax,ecx 
00000004  ret              

This can be called like,

var i2 = Adder<int, IntAddPolicy>.Add(3, 4);

Note that the code in IntAddPolicy gets inlined into the Add() method. Even though this doesn't get inlined into the caller of Add(), it will still be pretty quick with the branch prediction and register aliasing of modern processors. This means that you are not paying much (and in many cases nothing) in code quality for using an AddPolicy over writing out the Add() method explicitly.

To use the Add() method above with another type, such as double, you need to create another add policy struct. This would look like,

struct DoubleAddPolicy : IAddPolicy<double> {
    public double Add(double a, double b) { return a + b; }
}

Using this struct to call Add() will produce the following code for the Add() method,

00000000  fld         qword ptr [esp+0Ch] 
00000004  fadd        qword ptr [esp+4] 
00000008  ret         10h  

This is not quite as good as the code generated for int because it uses the stack to pass the parameters but it is still pretty fast.

We now have a method that can add two values of any type T for which an AddPolicy can be created. This is pretty close to, and more general than, what I originally wanted. Unfortunately, even though the code generated is good, calling this code is very awkward; we have to call a static method of a parameterized class and the policy struct prevents the compiler from being able to use type inferencing to supply the parameters for us. Next time I will describe a more practical application of this technique where the awkwardness is not as noticiable.

I recently needed to create a set of classes that was the combinatorial expansion of several implementation flavors of two independent sets of methods. Why I needed combinatorial expansion is not that interesting but the solution is. What I came up with is a way of supporting a form of mixin's in C#.

Lets take the methods,

void Lock();
bool Unlock();
bool Locked { get; }

If you call Lock(), Locked returns true, until you call Unlock(). Also Unlock() returns true if the object is now unlocked. There are several implementations I can think of for these methods, one uses a Boolean value and doesn't support nested calls to Lock():

void Lock() {
  _locked = true;
}

bool Unlock() {
  _locked = false;
  return true;
}

bool Locked {
  get { return _locked; }
}

Another uses an integer value to count the number of nested calls to Lock() and it remains locked until a matching number of Unlock() calls are made.

void Lock() {
  _count++;
}

void Unlock() {
  _count--;
  return _count == 0;
}

void Locked() {
  return _count > 0;
}

This isn't thread safe so we could provide a relatively thread-safe version in,

void Lock() {
    System.Threading.Interlocked.Increment(ref _count);
}

bool Unlock() {
    return System.Threading.Interlocked.Decrement(ref _count) == 0;
}

bool Locked {
    get { return _count > 0; }
}

I am sure you have already thought of at least one more. Now I have four possible implementations (including yours), which is the correct one? Unfortunately, that depends on how the locking is going to be used. If I know I will never need nested locks, only taking space for a Boolean makes sense. If I know I will need to support nested locks then the int seems like a good choice. If it is going to be used in a multi-threaded application I should probably use the thread-safe version. I now have two choices, pick one implementation or pass it the implementation as a parameter. Picking one implementation is easy, just copy of of the above implementation into the class; but how do you efficiently pass an implementation as a parameter?

From now on I will refer to each implementation as a locking policy. What I want is an efficient way to pass the locking policy to a set of classes. Most obvious way is to write a class for each policy and pass the policy as a parameter to each instance. This might look something like,

abstract class LockingPolicy {
  public abstract void Lock();
  public abstract bool Unlock();
  public abstract bool Locked { get; }
}

class LockableObject {
    private LockingPolicy _lockingPolicy;
  
    public LockableObject(LockingPolicy lockingPolicy) {
        _lockingPolicy = lockingPolicy;
    }
  
    public void Lock() {
        _lockingPolicy.Lock();
    }

    public bool Unlock() {
        return _lockingPolicy.Unlock();
    }

    public bool Locked {
        get { return _lockingPolicy.Locked; }
    }
}

Unfortunately, this has, on average, 36 bytes of overhead per instance on a 32 bit machine (more on 64).  This seems a bit much for such a policy and picking just one implementation, even one too general for the average application, starts looking like a better alternative. We must be able to do better than this.

Since passing the implementation as a parameter to the instances is expensive, why not try to pass the implementation to the class instead? In order to do that we need use a type parameter. What we want is something like,

class LockableObject<LockingPolicy> {
    private LockingPolicy _lockingPolicy = new LockingPolicy();

    public void Lock() {
        _lockingPolicy.Lock();
    }

    public bool Unlock() {
        return _lockingPolicy.Unlock();
    }

    public bool Locked {
        get { return _lockingPolicy.Locked; }
    }
}

In other words, we need to passing a class and delegate the implementation to that class. This does not look significantly better than the previous implementation, however, because we are new'ing up an instance and assigning it to an instance variable which, as before, consumes a minimum of 36 bytes per instance. But if LockingPolicy is a struct instead of a class then it will only add the size of the struct to the LockableObject instance size. In other words, we would only be taking space for either a bool or an int. The size overhead looks good, now how about the delegation? In order to call methods on LockingPolicy the LockingPolicy struct must implement an interface. It cannot be an abstract class because all structs are sealed and cannot be inherited from. The interface for the locking policy is fairly straight forward and looks like,

interface ILockingPolicy {
    void Lock();
    bool Unlock();
    bool Locked { get; }
}

An implementation of the Boolean locking policy looks like,

struct SimpleLockPolicy : ILockingPolicy {
    bool _locked;

    void ILockingPolicy.Lock() {
        _locked = true;
    }
    bool ILockingPolicy.Unlock() {
        _locked = false;
        return false;
    }
    bool ILockingPolicy.Locked {
        get { return _locked; }
    }
}

The counted locking policy looks like,

struct CountedLockPolicy : ILockingPolicy {
    private int _count;
    void ILockingPolicy.Lock() {
        _count++;
    }
    bool ILockingPolicy.Unlock() {
        _count--;
        return _count == 0;
    }
    bool ILockingPolicy.Locked {
        get { return _count > 0; }
    }
}

We now need to add a where clause to the LockableObject class so we can call the methods provided by the struct's methods. The modified LockableObject class looks like,

class LockableObject<LockingPolicy>
    where LockingPolicy : struct, ILockingPolicy 
{
    private LockingPolicy _lockingPolicy = new LockingPolicy();

    public void Lock() {
        _lockingPolicy.Lock();
    }

    public bool Unlock() {
        return _lockingPolicy.Unlock();
    }

    public bool Locked {
        get { return _lockingPolicy.Locked; }
    }
}

The LockableObject can now be instantiated like,

var lockableObject = new LockableObject<SimpleLockPolicy>();

for a lockable object that uses the Boolean implementation. To use the counted locking policy you would construct the object like,

var lockableObject = new LockableObject<CountedLockPolicy>();

The space consumption looks good but the delegation looks expensive it call through an interface which is a virtual. But since we are using structs, which are sealed, the call through the interface can be made static and then be a candidate for inlining. In fact, this is what happens in retail builds when not debugging. This is not entirely free however since there the runtime doesn't inline twice. Implementing Lock() directly instead of through delegation means the Lock() method can be inlined, removing the call entirely, the delegated version inlines the delegation but it still generates a call.

This mechanism for C# mixins is not as convenient as languages that support multiple inheritance, because we have to manually delegate to the policy, but it is just as efficient as we will see demonstrated more clearly in some of the next entries.

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 {
    public static int 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;
    }

    public static int 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)));
}

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

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

public static void 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.