IanG on Tap

Cartesian Products Closing Thoughts

Sun, 08 Aug 2010 17:17:14 GMT

This is the final part of a series of six blogs:

Simple but Too Specialized
Moving Away from Anonymous Types
LINQ to LINQ
The Missing LINQ: IEnumerable<T> and Scalars
Other Languages
Closing Thoughts (this entry)

Part 6 – Closing Thoughts

Back at the start of this series, I started with a simple, specialized Cartesian product where I knew the number of sets in advance. Anonymous types made this easy, but I had to move away from those to get a more general-purpose solution. This seems to happen quite a lot with anonymous types—they’re handy for very well-contained scenarios, but I often find myself getting rid of them as my code grows more complicated.

I think this is an example of a broader issue. LINQ works really well in monolithic applications—if you can get everything you need in a single method, or better yet a single query, it does a great deal of very useful work for you. But as soon as you want to start splitting things up, life gets harder. You might want to reuse parts of a query, or perhaps you just want to decompose your code into smaller chunks to improve readability, testability, and maintainability. Either way, dismantling a LINQ query into its component parts is possible, but rarely straightforward. I saw a similar step up in complexity here—I started with something that was easy, using small, specialized LINQ queries, but generalizing it was a lot more work.

However, although the general solution was significantly less convenient than the specialized one, it was still reasonably compact. I had been expecting to see a bigger difference between the C# code and the examples from geekier languages such as Clojure, F# and Haskell. But the results are surprisingly similar, I think. The biggest difference I can see is that Haskell’s type system makes it easier to define functions capable of operating over any monadic type—the examples for all other languages only work on lists.

The next biggest difference is that the C# code has more explicit typing—I’ve had to say a lot about the argument and return types of the CartesianProduct method. You’re allowed to state this stuff explicitly in Haskell if you want, but you’re not required to. This brings me onto my final point: ceremony.

An Unfashionable Defence of Ceremony

It has recently become fashionable to attack some languages for requiring more “ceremony” than others. Apparently, “ceremony” is anything you have to write because it's formally required, but which doesn’t directly say anything about what your program does. The need for explicit type declarations in C# is one example. With Haskell I was able to write just the essence, whereas with C#, I had to say more about what I was doing before I could do it. (Haskell is very much a statically typed language, by the way. It’s just that you can leave its type inference system to do a lot of the work.)

I hold an unfashionable view: I’m not convinced that absence of ceremony is intrinsically a good thing—in this particular case I suspect it makes it easier for someone reading the code. I don’t want to have to perform complicated type inference in my head when reading source code—I’d rather the code was explicit about the types it’s using because a) that saves time when I’m reading it and b) removes doubt over whether the author wrote what he or she meant to write.

In what little Haskell I’ve done, I’ve found it much easier to write explicit type declarations even in cases where the compiler doesn’t need them. The ceremony’s not for the compiler—it’s for my benefit. Just to be clear: I don't think that ceremony is intrinsically good either. Pointless verbosity helps nobody. I’m just saying that sometimes, making things explicit can improve readability.

Other Languages

Thu, 05 Aug 2010 22:33:19 GMT

This is part five in a series of blogs:

Simple but Too Specialized
Moving Away from Anonymous Types
LINQ to LINQ
The Missing LINQ: IEnumerable<T> and Scalars
Other Languages (this entry)
Closing Thoughts

Part 5 – Other Languages

In the previous blogs in this series, I’ve shown how to generate Cartesian products in C#. I started with the simple, elegant, anonymous type solution that works when you know at compile time exactly what your inputs are. But because my original scenario involved varying inputs, I built a more generalized solution, and then honed it to the point where I was reasonably happy with its size and readability.

In this part, I thought it’d be interesting to show solutions in a handful of other languages. In language advocacy fist fights^H^H^H^H^H^H^H^H^H^H^H debates, it’s common to argue that a language’s power is inversely proportional to the amount of code required to express a particular concept. In other words less is more—the language that can solve a particular problem in the smallest space wins. (I don’t completely agree with that—I think readability matters, and terseness is sometimes the enemy of readability. But size has the benefit of being objective.)

Haskell offers the shortest solution I’ve seen to this problem:

sequence [['1', '2'], ['A', 'B']]

This produces:

["1A","1B","2A","2B"]

That initially struck me as a little wierd until I realised that a string in Haskell is just a list of characters. I think it makes slightly more sense to think of that output as this:

[['1','A'],['1','B'],['2', 'A'],['2','B']]

That makes it more obvious that sequence has just produced every possible concatenation. But Haskell prefers to print lists of characters using string literal syntax. In fact if you type in the second representation at a Haskell prompt, it'll print out the first one.

You might think that this is cheating because I appear to be using a built-in function to do the job. But that would be a bad argument on two counts. First, the expressiveness of the available library functions is a critically important aspect of the practical usefulness of any language. Second, this built-in sequence function is not just for Cartesian products—it’s more general-purpose. What you’re looking at in that example is a very general mechanism being applied in this particular case to produce an n-ary Cartesian product.

The sequence function works with any monadic type. For example, I can use Haskell’s Maybe monad, which is roughly analogous to the idea of a nullable type:

sequence [Just 1, Just 2, Just 3]

Here I’m passing a list of maybes where every item does in fact have a value, and it produces:

Just [1,2,3]

But if I include Nothing, which is (sort of) analogous to null, then the usual behaviour of the Maybe monad kicks in, which is to say I get Nothing out. So this:

sequence [Just 1, Just 2, Nothing, Just 3]

produces this:

Nothing

Haskell also uses monads to handle IO, so I could use sequence to execute a series of IO actions:

get2chars = sequence [getChar, getChar]

The getChar function returns an IO Char, so passing a list of these into sequence produces something of type IO [Char], i.e., it produces an IO monad which can feed a list of Char values into a subsequent step:

do { result <- ioseq; putStrLn result }

That reads two characters, and then prints them to the output. Not a particularly useful example perhaps, but it illustrates that the way in which the sequence function combines the elements is defined not by sequence itself, but by the monad you’re using.

If you’re not entirely familiar with monads, and want to understand this in terms more familiar to a C# developer, you could think of Haskell’s sequence function as being the generalized version of the CartesianProduct function I wrote earlier, but rather than being specific to IEnumerable<T>:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    IEnumerable<IEnumerable<T>> inputs)

it works for any type that provides the LINQ SelectMany operator. (So a hypothetical C# equivalent of sequence would work against LINQ to XML or LINQ to Entities, and not just LINQ to Objects, which is what our current CartesianProduct implementation uses.) SelectMany is just LINQ’s name for one of the standard monadic operators. (It’s sometimes called “bind”, and Haskell denotes it with the >>= operator.) So you could imagine this sort of thing:

public static IEnumerable<IMonad<T>> Sequence<T>(IEnumerable<IMonad<T>> inputs)

That’s not real because there is no IMonad<T> in .NET—I’m just trying to illustrate the broad idea behind Haskell’s sequence function. So the reason we can use sequence to build an n-ary Cartesian product is the same reason we can build them with C# LINQ queries with multiple from clauses—both C# and Haskell represent lists as monadic types whose binding behaviour happens to be a Cartesian product. C# doesn’t explicitly call these things monads, but it’s the same idea in practice.

(Note that sequence has one limitation that my C# code doesn't: Haskell has no direct equivalent of System.Object. The C# method can combine any old mixture of types, whereas Haskell's a bit more picky. As it happens, I don't care for my original problem: I only needed to cope with the number of input sets being unknown at compile time. The set members all happened to be of the same type; the ability to cope with a mixture of types was an accidental bonus, and not even one I wanted to keep. As you will recall, I eventually moved from object to a type argument. But if you really wanted to handle a mixture of types not known until runtime, Haskell's actually at a disadvantage; or perhaps the idiomatic Haskell response would be to wave my hand in the manner of a Jedi and tell you that this is not the type system you're looking for. In practice, I suspect that if you're using Haskell, you'd probably be unlikely to find yourself in a position where you were trying to handle that unknown mixture of types anyway.)

So Haskell wins because it has a built-in function, sequence, which combines a list of monadic types. I had to write my own function to do that in C#. But if Haskell didn’t have sequence, I could build it in much the same way I did with C#. In C# I used the Aggregate operator, and in Haskell I could use the similar foldr method.

mySequence = foldr
  (\ input soFar ->
    soFar >>= (\prevProductItem ->
      input >>= (\item -> [item:prevProductItem])))
  [[]]

Although that works here, it’s a little too specialized—I’m constructing lists with the [] syntax here, and the original sequence function works with any monad. Fortunately, as mentioned earlier, Haskell requires monadic types to define an operation to construct an instance of the monad from a value. (The gap I filled in C# with my EnumerableFrom method in the previous part. And as I noted in a recent update to the previous article, Rx provides something similar through its EnumerableEx.return method.) This is provided by the return operation:

mySequence = foldr
  (\ input soFar ->
    soFar >>= (\prevProductItem ->
      input >>= (\item -> return (item:prevProductItem))))
  (return [])

It might not be obvious if you’re unfamiliar with Haskell, but the structure’s pretty similar to the C# version. The from clauses have turned into >>= operators, the call to Append has been replaced with the colon operator. And in fact that’s a prepend, rather than an append; everything’s turned inside out because foldr works from back to front… (I could have used foldl, but foldr seems to be the more common idiom in Haskell.)

Haskell offers a specialized syntax for chaining monads together: the do notation. The following example is equivalent to the preceding one, but it might be more idiomatically correct:

mySequence = foldr
  (\ input soFar ->
      do prevProductItem <- soFar
         item <- input
         return (item:prevProductItem))
  (return [])

Hopefully this makes the structural similarity between this Haskell example and the C# CartesianProduct slightly more obvious—compare the <- clauses in this do notation with the from clauses in the C#. (Compared to foldr, LINQ’s Aggregate happens to use the reverse order for its arguments, and also for the arguments for the lambda, but otherwise, this is pretty similar.)

This still relies on monadic operators, so just as C# from clauses work with any type that offers the relevant LINQ operators, all the Haskell examples shown so far will work with any monad. And when I feed in a list of lists, it’s the Haskell List monad that’s doing the actual work of producing the cross product here, just as the C# code ultimately relies on the LINQ to Objects code in the Enumerable class. If you prefer your code more explicit, here’s one that generates the products without relying on monads:

explicitCartes = foldr
  (\ input soFar ->
    concatMap (\prevProductItem ->
      concatMap (\item -> [item:prevProductItem]) input)
      soFar)
  [[]]

Here’s a completely different take on the same problem:

compCartes = foldr
  (\ input soFar ->
    [item:prevProductItem | prevProductItem <- soFar, item <- input])
  [[]]

That’s using a list comprehension. Here I’m essentially exploiting the fact that the language will generate a 2-set Cartesian product if I define a list in terms of two input sets, and once again I’m using foldr to generalise that to an n-ary cross product. (This last example only works with lists—unlike the built-in sequence, and the last two mySequence examples above, this won’t work with other monads.)

There are probably other viable approaches. These may not be particularly idiomatically good examples of Haskell by the way—not only do I not know much Haskell, I’ve also attempted to keep some kind of connection between my C# examples and the Haskell code through my choice of variable names, to make it easier to explore the similarities and differences.

Craig Andera helpfully supplied me with a Clojure version:

(defn cross-prod [& colls]
  (->> colls
       (reduce #(for [x %1 y %2] [x y]))
       (map flatten)))

I’m pretty sure that’s doing much the same thing—reduce is Lisp’s name for what Haskell calls foldr, and what LINQ calls Aggregate.

I also took a shot at an F# version. I don’t really know much F#, but F# MVP Richard Minerich (aka rickasaurus) generously looked at my example, and was kind enough to describe it as “quite good”. He also came up with something more clever, but it would actually have required more code, so I'm sticking with my original:

let cartes inputs =
  List.foldBack
    (fun input soFar -> seq { for y in soFar do for x in input do yield x::y })
    inputs
    (Seq.singleton List.Empty)

let result = cartes [[1..5];[42;50];[99;100]] |> Seq.toArray

The List.foldBack operation is similar to Haskell’s foldr, and again, the overall structure is much the same as the C# example. Don’t be thrown by the name seq—this is different from Haskell’s sequence function. In F#, the seq keyword is used to introduce a block of code that will produce a sequence of items as its output. The block that follows here is conceptually pretty similar to the C# example, but with a pair of for … in … do constructs in place of a pair of from clauses.

(Note that as with the Haskell version, this one’s also picky about types. But again it doesn’t matter to me, because in my original problem, the input sets all contained members of the same type. It was only the number of sets I didn't know at compile time.)

The final line of this F# example is just for test purposes, and the reason I’m feeding the result through the Seq.toArray function is that the debugger shows more useful information for arrays than it does for generic sequences. (I guess that’s because a sequence might be infinite, so attempting to display the whole thing might be undesirable. But in converting it to an array, I’ve already chosen to force the sequence to be fully evaluated, so the debugger can show it safely.) Here’s the output from evaluating that last line in the F# Interactive window:

val result : int list array =
  [|[1; 42; 99]; [2; 42; 99]; [3; 42; 99]; [4; 42; 99]; [5; 42; 99];
    [1; 50; 99]; [2; 50; 99]; [3; 50; 99]; [4; 50; 99]; [5; 50; 99];
    [1; 42; 100]; [2; 42; 100]; [3; 42; 100]; [4; 42; 100]; [5; 42; 100];
    [1; 50; 100]; [2; 50; 100]; [3; 50; 100]; [4; 50; 100]; [5; 50; 100]|]

So that seems to work.

Old School

I asked a friend who works mainly in Java for a Java version of this code. I’m not going to offer any commentary beyond observing that a) this is probably roughly what it would have look like in C# before C# 3.0 turned up and b) this is why I like C# 3.0 so much:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


public class Cartesian {
    public static void main(final String... args) {

         final Object[] letters = { 'A', 'B', 'C' };
         final Object[] numbers = { 1, 2, 3, 4 };
         final Object[] colours = { "Red", "Blue" };

         final List<List<Object>> params = new ArrayList<List<Object>>();
         params.add(Arrays.asList(letters));
         params.add(Arrays.asList(numbers));
         params.add(Arrays.asList(colours));

         for( final List<Object> item : cartesian(params)) {
             System.out.println(item);
        }
    }

     public static <T> List<List<T>> cartesian(final List<List<T>> params) {
         if( !(params.size() > 0) ) return new LinkedList<List<T>>();
         return cartesian(new LinkedList<List<T>>(params),
             new ArrayList<List<T>>());
     }

    private static <T> List<List<T>> cartesian(
      final LinkedList<List<T>> params, final List<List<T>> results) {
         if( !(params.size() > 0) ) return results;
         aggregate(params.removeLast(),results);
         return cartesian(params,results);
     }

    private static <T> void aggregate(final List<T> items,
                                      final List<List<T>> target) {
        if( target.size() == 0 ) {
            for(final T item : items) {
                final List<T> targetItems = new ArrayList<T>();
                targetItems.add(item);
                target.add(targetItems);
            }
        } else {
            final List<List<T>> oldTarget = new LinkedList<List<T>>(target);
            target.clear();
            for(final T item : items) {
                for(final List<T> oldTargetItems : oldTarget) {
                    final List<T> targetItems = new ArrayList<T>();
                    targetItems.add(item);
                    targetItems.addAll(oldTargetItems);
                    target.add(targetItems);
                }
            }
        }
    }
}

Next time, some final thoughts.

The Missing LINQ: IEnumerable and Scalars

Mon, 02 Aug 2010 14:33:25 GMT

This is part four in a series of blogs:

Simple but Too Specialized
Moving Away from Anonymous Types
LINQ to LINQ
The Missing LINQ: IEnumerable<T> and Scalars (this entry)
Other Languages
Closing Thoughts

Part 4 – The Missing LINQ: IEnumerable<T> and Scalars

Last time, I turned LINQ on itself: I used a LINQ query to build a LINQ query. This worked, but the result wasn’t quite as neat as it could have been. I can improve matters by adding a couple of helpers to the world of LINQ. I’ve often found it slightly odd that these don’t seem to be built into LINQ, but they’re easily added.

LINQ offers no built in clean way to take a single scalar item and convert it into a sequence with that single item in it. The usual approach is just to build a single-element array. This works, but it's rather clunky, and I often run into situations where this curious omission makes code more awkward than it needs to be. It has led to a rather ugly first argument to Aggregate:

        (IEnumerable<IEnumerable<T>>) new T[][] { new T[0] },

What I’m actually saying here is that I want to take an single element—an empty sequence of T (new T[0])—and turn it into a sequence that contains just that one element. (I’m building a sequence of sequences here, remember.) The Enumerable class does actually provide a helper for building an empty sequence, so I can make this code say what it does slightly better by writing this:

(IEnumerable<IEnumerable<T>>) new IEnumerable<T>[] { Enumerable.Empty<T>() },

I think it’s now slightly more obvious that an empty sequence is involved here. But I’ve ended up building an array to get my one-element sequence, and I think it’s ugly. What really I’d like to write is this:

Enumerable.From(Enumerable.Empty<T>()),

I’m imagining a From method here that returns a single-element sequence containing whatever element you pass as the argument. Sadly, this method doesn’t appear to exist. That seems weird to me—we have the Empty<T> method, so it would seem natural also to have a method that wraps a single item as an enumerable. (Moreover, LINQ draws heavily from the concepts behind monadic types such as those offered in Haskell. One of the fundamental operations of a monad is the ability to construct one from any underlying type. There are only two fundamental operations, so this is a particularly striking omission.) It’s easy enough to write our own though:

private static IEnumerable<T> EnumerableFrom<T>(T item)
{
    return new T[] { item };
}

Other implementations are possible of course—this might be a more expressive idiom:

private static IEnumerable<T> EnumerableFrom<T>(T item)
{
    yield return item;
}

That’s prettier, and appeals much more to my language geek tendencies, but it generates a lot more code under the covers. So I’ll stick with the first one.

A similar problem exists with concatenation. On this line here:

select prevProductItem.Concat(new T[] { item }));

I have an IEnumerable<T> (prevProductItem), and a single value of type T (item), and I want to append that to the original enumeration. The Concat operator is only able to combine two enumerations, so I’m obliged to turn that single item into a sequence by wrapping it in an array. This is essentially another instance of the previous problem, so I could just use my new EnumerableFrom method:

select prevProductItem.Concat(EnumerableFrom(item)));

But that feels a bit heavy handed. I’d love it if there were an overload of Concat that accepted singular values, in which case I could write:

select prevProductItem.Concat(item); // Won't compile

Although that might cause ambiguity, so perhaps it’d be better to have a distinct operator for appending just one item:

select prevProductItem.Append(item)); // Won't compile without help

As far as I can tell, that doesn’t exist. (Although it’s always possible that it does exist under a less obvious name, and I’ve simply missed it. Wouldn’t be the first time…) But I can write an extension method to provide it:

static class AppendExtension
{
    public static IEnumerable<T> Append<T>(this IEnumerable<T> that, T item)
    {
        IEnumerable<T> itemAsSequence = new T[] { item };
        return that.Concat(itemAsSequence);
    }
}

With this and my EnumerableFrom helper method in place, I can simplify our CartesianProduct method a little:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    IEnumerable<IEnumerable<T>> inputs)
{
    return inputs.Aggregate(
        EnumerableFrom(Enumerable.Empty<T>()),
        (soFar, input) =>
            from prevProductItem in soFar
            from item in input
            select prevProductItem.Append(item));
}

That’s looking a lot calmer to me.

I fear it may be write-only code—I’m not convinced that if I were to come across that finished product 6 months after writing it that I’d be able to work out how it works without first referring back to this blog series… However, because I know what an n-ary Cartesian product is, I’ll find it pretty easy to read code that uses this method.

Next time we’ll look at some solutions to this problem in other programming languages, to see how C# compares.

[Update, 5th August 2010: A few people have emailed me to mention that the Reactive Extensions for .NET (Rx) offer the missing features I add. So if these ever make it out of the labs into the full .NET Framework, I'll get my wish. The monad influence is clear - they've given their version of what I called EnumerableFrom the name return (yes, that's a blank web page - there doesn't seem to be much online documentation, and that's the only reference I could find - you'll need to download Rx to see the actual docs). Haskell also calls it return.]

LINQ to LINQ

Sun, 01 Aug 2010 18:27:13 GMT

This is part three in a series of blogs.

Simple but Too Specialized
Moving Away from Anonymous Types
LINQ to LINQ (this entry)
The Missing LINQ: IEnumerable<T> and Scalars
Other Languages
Closing Thoughts

Part 3 – LINQ to LINQ

Last time, I wrote a generalized method that built an n-ary Cartesian Product. It did this by building up a LINQ query—it chained as many SelectMany calls together as were needed. But it turns out that I am reinventing the wheel here—this is an example of a slightly more general process. Our n-ary Cartesian product method works by taking a starting value (a sequence containing the empty set), and repeatedly applying a function (SelectMany) once for each item in an input sequence (the sequence of input sets we’re combining), feeding the output of each step back in as the input to the next.

If the LINQ team had employed Apple’s marketing agency, this might be a good time to say: there’s an operator for that!

This concept of building up something by repeatedly applying the output of a function as the input to the same function is quite a common one. The process of calculating the sum of a list of numbers has exactly the same structure: your initial value is zero, and then for each number in the input list, you apply the ‘+’ (addition) function to the running total and the current number. It’s the same process, but using numbers and addition instead of sequences and SelectMany.

Most list processing systems have some general-purpose implementation of this process, and it goes by various names, including fold and reduce. And in LINQ it’s called Aggregate. Here’s a modified version of the method, using the LINQ Aggregate operator:

public static IEnumerable<object[]> CartesianProduct(params object[][] inputs)
{
    return inputs.Aggregate(
        (IEnumerable<object[]>) new object[][] { new object[0] },
        (soFar, input) => soFar.SelectMany(prevProductItem =>
            from item in input
            select prevProductItem.Concat(new object[] { item }).ToArray()));
}

Earlier, I turned my LINQ query expression into explicit calls to SelectMany, but that was just an illustrative device to make it more clear what’s going on. Having got to this stage, I think it looks slightly neater to go back to the query expression syntax. It’s no less powerful in this example:

public static IEnumerable<object[]> CartesianProduct(params object[][] inputs)
{
    return inputs.Aggregate(
        (IEnumerable<object[]>) new object[][] { new object[0] },
        (soFar, input) =>
            from prevProductItem in soFar
            from item in input
            select prevProductItem.Concat(new object[] { item }).ToArray());
}

So there’s the function that uses LINQ to build a LINQ query. Specifically, it uses the LINQ Aggregate operator to combine a series of LINQ SelectMany queries into one big query.

I can now write this sort of code:

object[] letters = { 'A', 'B', 'C' };
object[] numbers = { 1, 2, 3, 4 };
object[] colours = { "Red", "Blue" };

var cartesianProduct = CartesianProduct(letters, numbers, colours);
foreach (var item in cartesianProduct)
{
    Console.WriteLine(string.Join(",", item));
}

This code produces exactly the same output as the previous output shown, i.e., it is the Cartesian product of the three sets being fed into the method.

Comparing this with the original example in part one of this series, everything’s now an object[], so I’ve lost some compile time type checking, and I’ve lost meaningful names for our items, but the benefit is increased generality—I can pass as many sets as I like into the CartesianProduct method. I can decide on the number of sets at runtime, which was my original requirement.

Here’s a different way to use this CartesianProduct method. This next example generates digits for all numbers in a particular base of a particular length. The digitValues array contains all available digits in the selected base (e.g. {0, 1} for base 2), and then I use the Enumerable.Repeat method to generate a sequence containing that set of digits over and over again for the specified number of digits.

public static IEnumerable<object[]> Numbers(int radix, int digits)
{
    object[] digitValues = Enumerable.Range(0, radix).Cast<object>().ToArray();
    return CartesianProduct(Enumerable.Repeat(digitValues, digits).ToArray());
}

Those calls to Cast and ToArray are bugging me though.

Cleaning it Up

Earlier, I made a rather suspect decision—you may well have raised an eyebrow when I said I was going to represent each tuple as an array of objects. Arrays? Really? In the midst of all this LINQ, I decided to use arrays? Well actually, originally I didn’t—before I wrote this series of blogs, I started out by using enumerations for the tuples as well as for the input sets. The reason I introduced object[] was to make the example slightly easier to follow—as I was working through it, I kept forgetting whether the enumeration I was looking at was the one containing the input sets, or was one of the input sets themselves, or was perhaps one of my output values…

The object[] type had the useful benefit of being visually very distinct from all the other IEnumerable<T> types, making it very easy to know when I was looking at something representing a tuple in the output set. However, now that I’ve got it working, I want to get rid of it, because arrays are an unnecessarily restrictive choice here. Here’s a modified version that uses enumerables:

public static IEnumerable<IEnumerable<object>> CartesianProduct(
    IEnumerable<IEnumerable<object>> inputs)
{
    return inputs.Aggregate(
        (IEnumerable<IEnumerable<object>>) new object[][] { new object[0] },
        (soFar, input) =>
            from prevProductItem in soFar
            from item in input
            select prevProductItem.Concat(new object[] { item }));
}

This allows a slightly neater version of Numbers:

public static IEnumerable<IEnumerable<object>> Numbers(int radix, int digits)
{
    var digitValues = Enumerable.Range(0, radix).Cast<object>();
    return CartesianProduct(Enumerable.Repeat(digitValues, digits));
}

But there’s still that call to Cast<object>(). That’s only in there because CartesianProduct is using object as its representation for items in the input sets. For my first few examples, where the input sets were all of different types (char, int, and string), that made sense, but in this case, all three sets contain members of the same type: int. (And as it happens, in the program I was working on that originally motivated this blog post, all the input sets contained members of type Action.) I’d like to improve this. I can parameterise CartesianProduct by the type it uses to represent elements in input sets:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    IEnumerable<IEnumerable<T>> inputs)
{
    return inputs.Aggregate(
        (IEnumerable<IEnumerable<T>>) new T[][] { new T[0] },
        (soFar, input) =>
            from prevProductItem in soFar
            from item in input
            select prevProductItem.Concat(new T[] { item }));
}

// Enable variable argument list.
public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    params IEnumerable<T>[] inputs)
{
    IEnumerable<IEnumerable<T>> e = inputs;
    return CartesianProduct(e);
}

I can now modify our Numbers method to return a more specifically typed enumeration, and I can remove that ugly call to Cast as well:

public static IEnumerable<IEnumerable<int>> Numbers(int radix, int digits)
{
    var digitValues = Enumerable.Range(0, radix);
    return CartesianProduct(Enumerable.Repeat(digitValues, digits));
}

That Repeat method reminds me of a minor omission from LINQ that has caused our CartesianProduct to be slightly messier than necessary. I’ll clean things up further by adding some helpers in the next blog in this series.

Moving Away from Anonymous Types

Thu, 29 Jul 2010 21:05:19 GMT

This is part two in a series of blogs:

Simple but Too Specialized
Moving Away from Anonymous Types (this entry)
LINQ to LINQ
The Missing LINQ: IEnumerable<T> and Scalars
Other Languages
Closing Thoughts

Part 2 – Moving Away from Anonymous Types

In the previous article, I showed how you can combine multiple LINQ SelectMany calls to produce a multi-way Cartesian product. So far, I’ve used anonymous types to manage each increase in complexity—I just added a new property for each new input set. This is really handy when you know exactly what sets you’re working with, but if you want to deal with arbitrary numbers of sets, you need a slightly more general purpose representation.

What exactly do we need? Well remember, the Cartesian product of two sets produces a set containing pairs of items. (E.g., (A, 1) or (B, 3).) With three sets involved, rather than pairs we get what you might call “triples” such as (A, 2, Red), and with four input sets you get a set of “quadruples” and so on. The general name for a pair, triple, quadruple, quintuple, etc. is a Tuple, or n-Tuple, so you might think that the Tuple class (introduced in .NET 4.0) would be just the thing. But in fact, that’s designed for when you know how many items you want in your tuple at compile time, just like anonymous types. (The main advantage of Tuple over an anonymous type is that you can use Tuple in method and property signatures; anonymous types are effectively confined to the scope in which they are constructed.) A tuple is the right concept but the Tuple class is the wrong representation here.

A tuple is just an ordered set of items. So I could just use an array. For example, if you produce the Cartesian product of three sets, I can represent each item in the results using something like new object[] { 'A', 3, "Red" }. I can rewrite the last two queries from the previous blog in this series to use this representation:

var lettersAndNumbersCartesianProduct = letters.SelectMany(
    letter => numbers.Select(number => new object[] { letter, number }));

var cartesianProduct = lettersAndNumbersCartesianProduct.SelectMany(
    (letterAndNumber) => colours.Select(colour =>
        new object [] { letterAndNumber[0], letterAndNumber[1], colour }));

foreach (var item in cartesianProduct)
{
    Console.WriteLine(string.Join(",", item));
}

Now, lettersAndNumbersCartesianProduct and cartesianProduct are both IEnumerable<object[]>, i.e., they are sequences where each item in the sequence is an array. I’ve modified the foreach loop to expect a sequence of arrays, so the output now looks like this:

A,1,Red
A,1,Blue
A,2,Red
A,2,Blue
A,3,Red
A,3,Blue
A,4,Red
A,4,Blue
B,1,Red
B,1,Blue
B,2,Red
B,2,Blue
B,3,Red
B,3,Blue
B,4,Red
B,4,Blue
C,1,Red
C,1,Blue
C,2,Red
C,2,Blue
C,3,Red
C,3,Blue
C,4,Red
C,4,Blue

This is less convenient—the items produced by this code are just arrays, rather than statically-typed anonymous types with conveniently-named members like number and colour. However, I’m now in a position to generalise—I’ve got one type, IEnumerable<object[]>, capable of representing the Cartesian product any number of sets. For an n-ary product, each array in the sequence will be of length n. If I want to add in another set, the output can still be represented as an IEnumerable<object[]>, with each array being of length n+1. This lets me write a method that produces the Cartesian product of multiple sets iteratively:

public static IEnumerable<object[]> CartesianProduct(params object[][] inputs)
{
    IEnumerable<object[]> soFar = new object[][] { new object[0] };
    foreach (var input in inputs)
    {
        var currentInput = input;
        soFar = soFar.SelectMany(prevProductItem =>
            from item in currentInput
            select prevProductItem.Concat(new object[] { item }).ToArray());
    }
    return soFar;
}

The soFar variable is used to build up the result, one input set at a time, so its initial value represents the Cartesian product of zero sets. I’ve chosen to represent this as a sequence containing a single zero-length array. You could argue that the result for no input sets should be an empty sequence, so it may look odd to return a sequence with a single item when there are no input sets. But you can also argue that there’s exactly one possible outcome when you have no input sets—the empty set—and so the result should be a sequence containing that one outcome. (I.e., the result is a sequence containing the empty set.) That second choice happens to work better as a starting point for chaining multiple product queries together, so I’ve gone with that. And the loop just goes round chaining a SelectMany query onto the previous query for each of the input sets.

This does the job, but I’m doing work LINQ could be doing for me, as we’ll see next time.

LINQ and N-ary Cartesian Products

Wed, 28 Jul 2010 19:21:32 GMT

I recently found myself needing to solve a problem that involved producing an n-ary Cartesian product. I ended up with a fun solution in which I used LINQ to generate a LINQ query. I thought I’d share it. Being me, I spent quite a while writing a blog about this, tinkering with the details, and leaving it for a few days so I could re-read the text with a fresher point of view. And then I got distracted. And then it got so large that I split it up.

The problem with sitting on a draft of a blog post for that long is that there’s a good chance that Eric Lippert will write a post on exactly the same topic in between me starting to write the post and actually publishing it.

Ah well. I ended up with a slightly different solution from Eric. Also, the main reason I was delaying this was that I wanted to get a couple of examples from other languages together. So I hope this will be interesting even to people who have already read Eric’s post.

This ended up being rather longer than I had anticipated, so I’m breaking it up into a series.

Simple but Too Specialized (this entry)
Moving Away from Anonymous Types
LINQ to LINQ
The Missing LINQ: IEnumerable<T> and Scalars
Other Languages
Closing Thoughts

Part 1 – Simple but Too Specialized

Before getting to the general n-ary case, let’s start with a simple case: the Cartesian product of two sets, or a cross join, as it’s known in databases. If you’re not familiar with this operation, it just produces every possible pairing between the items from two sets. This is easy in C# thanks to LINQ:

char[] letters = { 'A', 'B', 'C' };
int[] numbers = { 1, 2, 3, 4 };

var cartesianProduct = from letter in letters
                       from number in numbers
                       select new { letter, number };

foreach (var item in cartesianProduct)
{
    Console.WriteLine(item);
}

I start with two lists—the letters A, B, and C, and the numbers 1-4—and the output shows all the possible pairs:

{ letter = A, number = 1 }
{ letter = A, number = 2 }
{ letter = A, number = 3 }
{ letter = A, number = 4 }
{ letter = B, number = 1 }
{ letter = B, number = 2 }
{ letter = B, number = 3 }
{ letter = B, number = 4 }
{ letter = C, number = 1 }
{ letter = C, number = 2 }
{ letter = C, number = 3 }
{ letter = C, number = 4 }

That’s fine as far as it goes, but I needed to deal with more than two lists. LINQ can handle this too—you can have as many from clauses as you like:

char[] letters = { 'A', 'B', 'C' };
int[] numbers = { 1, 2, 3, 4 };
string[] colours = { "Red", "Blue" };

var cartesianProduct = from letter in letters
                       from number in numbers
                       from colour in colours
                       select new { letter, number, colour };

This produces the following output:

{ letter = A, number = 1, colour = Red }
{ letter = A, number = 1, colour = Blue }
{ letter = A, number = 2, colour = Red }
{ letter = A, number = 2, colour = Blue }
{ letter = A, number = 3, colour = Red }
{ letter = A, number = 3, colour = Blue }
{ letter = A, number = 4, colour = Red }
{ letter = A, number = 4, colour = Blue }
{ letter = B, number = 1, colour = Red }
{ letter = B, number = 1, colour = Blue }
{ letter = B, number = 2, colour = Red }
{ letter = B, number = 2, colour = Blue }
{ letter = B, number = 3, colour = Red }
{ letter = B, number = 3, colour = Blue }
{ letter = B, number = 4, colour = Red }
{ letter = B, number = 4, colour = Blue }
{ letter = C, number = 1, colour = Red }
{ letter = C, number = 1, colour = Blue }
{ letter = C, number = 2, colour = Red }
{ letter = C, number = 2, colour = Blue }
{ letter = C, number = 3, colour = Red }
{ letter = C, number = 3, colour = Blue }
{ letter = C, number = 4, colour = Red }
{ letter = C, number = 4, colour = Blue }

That’s a 3-way Cartesian product. You can keep adding as many from clauses as you like, because LINQ supports n-ary Cartesian products. Problem solved? Not quite. This approach is perfect if you know how many sets you’re combining at compile time—in these examples, I knew what the ‘n’ in n-ary was when writing the code. (2, and 3, respectively.)

But in the problem I’m trying to solve, I didn’t have that information at compile time. I need to produce the n-ary Cartesian product across a bunch of sets where I don’t know how many sets there would be until runtime.

But this doesn’t stop me from using LINQ. A LINQ query is just an object built up by a series of method calls—the query expression syntax I used in the last couple of examples disguises this, but explicit method calls offer a bit more power. LINQ queries with multiple from clauses use the SelectMany operator beneath the covers, so that last query is equivalent to this:

var lettersAndNumbersCartesianProduct = letters.SelectMany(
    letter => numbers.Select(number => new { letter, number }));

var cartesianProduct = lettersAndNumbersCartesianProduct.SelectMany(
    (letterAndNumber) => colours.Select(colour =>
        new { letterAndNumber.letter, letterAndNumber.number, colour }));

More generally, if you have N from clauses you will have N-1 calls to SelectMany. (You’ll notice that I’ve now got two anonymous types—the one used to contain the pairs produced by the first SelectMany is fed into the second SelectMany that produces the (letter, number, colour) ‘triples’ that make up my final output. One of the advantages of using the C# query expression syntax is that the C# compiler hides all of this sort of stuff for you. If you inspect the code C# produces for the query expression version, using ILDASM or Reflector, you’ll see it’s doing something similar under the covers.)

I split the last example into two statements to highlight a useful fact: if I need a 3-way Cartesian product, I can start with a 2-way Cartesian product, and then just bolt an extra SelectMany on the end. This technique of taking an existing LINQ query and invoking an extra operator on it to form a more complex query is sometimes called chaining.

I can take this a step further and build a general purpose method that takes any number ‘n’ of sets and produces the n-ary Cartesian product of those sets by repeatedly chaining SelectMany calls. However, I’d need to come up with a slightly more adaptable representation. As it stands, with each set I add to the product, the resulting set’s members grow more complex. The Cartesian product of numbers and letters produced a set where each member had both a number and a letter, e.g. { letter = 'A', number = 2 } or { letter = 'C', number = 1 }. The Cartesian product of numbers letters, and colours produced a set where each member had three items, looking like { letter = A, number = 3, colour = "Red" } or { letter = B, number = 2, colour = "Blue" }.

I’ll have to abandon anonymous types to generalize this—anonymous types are great when you know at compile time exactly what you’ll be dealing with. But they cannot adapt at runtime. So in the next blog in this series, I’ll use a different representation, so that I can write a generalized method for producing an n-ary Cartesian product.

Silverlight 3 at PDC

Sat, 05 Sep 2009 15:42:01 GMT

I’m absurdly excited about PDC this year because for the first time, I’ll be speaking there! Rich Griffin and I will be talking about Silverlight 3. This is one of the day-long workshops that run the day before the full conference starts.

I’m pleased to be talking with someone who I’ve worked with as a fellow developer—Rich and I have collaborated on some of the many WPF and Silverlight projects we’ve worked on over the last few years. We both have a lot of experience solving real problems, and we’re looking forward to bringing that to the workshop—we will be talking about building real software.

PDC is just over a couple of months away, so we haven’t quite set our talks in stone yet. We’d both love to hear from you if you’re contemplating coming to our session and have ideas on what you’d like to see. That said, we obviously need to give people a fair idea of what to expect so they can plan now. So here’s what we’re currently thinking.

We see the day breaking down into four pieces, taking roughly a quarter of the day each: The Ideas of Silverlight; Connecting; Software Design; Working with Designers.

The Ideas of Silverlight

I want to start by saying what this will NOT be. We absolutely don’t want to do a laundry list of Silverlight features, or a straight forward walk through of the developer and the design tools. We believe that a sound understanding of a critical set of ideas at the heart of Silverlight is the secret to true proficiency.

So we plan to talk about some features that make Silverlight very different from most other UI technologies, and how they combine in ways you might not expect. In particular, we plan to describe the roles played by templates, and styles, the structure of controls, the surprising importance of data binding, and why something called MVVM is so important. We also want to talk about some of the practical issues around deployment, testing, and tools.

Connecting

Silverlight is for the internet, so our second section will be all about how to connect with the rest of the world. We plan to look at WCF, REST, and POX in some depth. We’ll discuss the tension between security and flexibility, and some practical resolutions. We’ll talk about RIA services too, although since that’s a topic that could easily fill a day on its own, we don’t intend to cover it in depth—our current thinking is that we want to make it clear what it’s for and when you would or wouldn’t use it, illustrating just enough of it that you’ll see its overall approach. (Although if you think we should dedicate a large chunk of the day to RIA services, we’d like to hear from you, and we’d like to know what you think we should drop to make space for it.)

Software Design

It’s all very well to look at the core ideas, features and technologies of Silverlight, both on the inside, and where your code meets the rest of the world, but how do you tie it all together in practice? We’ll look at strategies for structuring your application’s design. (That’s software design, as opposed to interaction design or visual design, by the way.) We expect to go into more detail on MVVM here. We’d also like to talk about where technologies such as MEF and Prism can fit in.

Working with Designers

Yes, PDC is for developers. So is this session. Building Silverlight applications that look great takes more than throwing a finished application over the wall to where the visual designers work and asking them to slap a layer of sparkle on at the last minute. Integrating good visual design into your application requires planning. Developers need to understand the process and get involved. The way to get the best results is for developers and designers to work together closely. We’ll talk about the steps you need to take as developers to make this possible. We’ll also show how Blend fits into the world of the developer, and we’ll offer tips for how it can make your life easier when creating Silverlight applications.

So that’s the current plan. I’ll be posting more as we refine our ideas, and most likely tweeting too—we might do a couple of polls to gauge the level of interest in the various topics, so now is the perfect time for feedback. We look forward to your suggestions!

(If you’re wondering about why I only just mentioned this, when it was all announced a few weeks ago, I came on board to speak just as I went off on an extended holiday, and now that I’m back, I’m feverishly trying to catch up with everything.)

Designing a WPF Timeline Control Part 1: Structure

Thu, 04 Jun 2009 02:38:22 GMT

For a change, I’m involved in an endeavour I can blog about. I’m working with Brian Randell, Matthew Adams, and Felix Corke on a project that involves building a kind of timeline control. This blog describes the thinking behind the control’s structure—WPF controls tend to end up looking very different from their equivalents in anything based on classic Win32 UI underpinnings such as Windows Forms, and I thought it might be interesting to explain how and why the differences come about.

We’re not quite ready to show the code for this yet, as it’s still a work in progress, but we’ll make the source available before too long.

Requirements

The requirements were a little nebulous, because we set out to build a control for fun, rather than for any particular application or customers. So one of the most important requirements was that it be interesting to build. Nonetheless, we had some ideas about what sorts of things we wanted to be able to do. For example we wanted a way to show files found via Windows Search (or, as I find it hard to stop calling it, Windows Desktop Search). Positioning and grouping files by dates along a timeline seemed like it might be an interesting way to visualize search results.

Here’s an early prototype we built to get a rough idea of how it might work with some real data. I’m jumping ahead here a little, but a picture makes it easier to understand what we had in mind:

The user can drag the whole timeline left or right to move around, and zoom in and out with the mouse. The items are all expanded in that example above. It doesn’t have to be that way though—here’s how it might look when the user has zoomed out a bit and only has one item expanded:

Clearly we have a bit of a problem with the captions on the timeline here, but you can see how this gives an impression of which bits of the timeline have a lot of content, and which bits are empty. Notice that in this example we also experimented with vertically stacked bars to indicate how much stuff was inside each group, to give a better idea of information density over time.

Now obviously this example looks horrible. Our goal at this stage was to try out some ideas to see if they would work before building something properly. As you’ll see in future blogs, it started looking a lot better once Felix got his hands on it.

Another feature we wanted was the ability to support multiple levels of detail—we envisaged the initial view as being a bunch of blobs on the timeline indicating files placed by date, which could be expanded to reveal details, possibly multiple levels of detail. So the examples above aggregate a bunch of files that appear in quick succession as a single blob, showing a list of all the files if you click on that blob, but we might want to go further, with some sort of details fly-out available on each of the items in that list.

We also wanted to avoid assuming much about the nature of the data source. We had discussed various ideas for what we might want to display along a timeline—I forget the complete list, but TV schedule information, appointment booking, gaming, and project management came up as possible application areas.

So our ‘spec’ was pretty vague (although I’ve had worse). We decided to start with the file system/search example, and see where it took us—more a voyage of exploration than a software project. Perhaps not the most efficient approach to software development, but if you’re building a UI component of a kind you’ve not attempted before, it’s not a bad idea to be at least a little chaotic—your first design is unlikely to be your best, so some space to experiment is useful.

But where to start? If you want a custom control to get the best out of WPF, it’s a good idea to try and align yourself with WPF’s philosophy. But what is that, exactly?

Composition is King

I’ve long thought that WPF’s single biggest benefit is its composition-based approach. Examine most of the built-in controls, and you’ll find that they do less work than you might think, deferring to other WPF components to get the job done. And these subordinate components are almost invariably multi-purpose—they show up in other WPF controls, and can be used where appropriate in your own custom controls.

Take the ListBox. Amongst the things it doesn’t know how to do are: size and position the list items; render list items; provide selection highlighting; provide its own appearance. For these tasks it defers to its items panel, its item template, its item containers, and its control template respectively, and you can plug in your own objects for any of these, to customize the control. Of these, only the item container type (ListBoxItem) is specific to the ListBox, and even that shares a lot in common with other list controls’ items containers.

A single monolithic black box of a control might be in keeping with long-standing traditions of the Windows 3rd party control market, but it’s not the WPF way.

Areas of Responsibility

The WPF way is for each area of responsibility to be owned by a separate type. This is not a new idea, of course, but it’s one that seems to be less well represented in the UI layer than elsewhere.

When developing new UI element types, we design them to be combined in the ways we need them to work, and with luck, it will be possible to combine them usefully in ways we did not first anticipate. In fact that second part often requires more than luck—types are rarely reusable in practice until you’ve tried to use them in multiple scenarios and have fixed the problems that made them less useful than you had hoped. We haven’t done that yet for these controls, so this is probably not yet the definitive design.

So, what are the areas of responsibility we think exist for our timeline UI? Here’s a breakdown, along with a suggestion of what kind of object might fit the bill:

Generation of UI elements from a data source (ItemsControl?)
Visual representation of the ‘line’ in the timeline control (ControlTemplate?)
Control to provide panning/scrolling (ScrollViewer?)
Positioning of UI elements along a line (Panel?)
Generated element type to be positioned on the line (some sort of ContentControl or Expander?)
Visual representation of an item on the line (ControlTemplate?)
Expanded view of content of generated element (DataTemplate?)

You’ll notice that we have borrowed shamelessly from the pattern established by WPF’s various items controls. We can produce a very similar-looking list for ListBox:

Derives from ItemsControl, enabling it to generate items from a data source
Being a control it has a ControlTemplate to define its appearance
Relies on ScrollViewer to provide a scrollable area
Uses a VirtualizingStackPanel to position its elements vertically
Generates a ListBoxItem (which is a ContentControl) for each item in the list
ListBoxItem is a control, so it also has a template
ItemTemplate or implicit data template used to render items in the list

If WPF already has a pattern that meets your needs, it’s usually a good idea to follow suit. Anyone already familiar with WPF will find your code easier to follow, and it also means you’re on a path likely to lead somewhere useful. But the degree of similarity here raises an obvious question: could we get away without creating any custom elements at all?

No Custom Elements?

It’s surprisingly common for WPF applications to be able to cobble together various WPF elements to achieve effects that would have required a custom control in Windows Forms. Could we do that here?

As an early experiment we built an application that queried Windows Search for all the bitmaps on a system, used LINQ to group them by month, and dumped the results into an ItemsControl to produce a timeline. To keep it simple we just used a StackPanel to get the items in order, but not yet positioned precisely according to date. The ItemTemplate contained a list of the files, using an Image element to render the actual image file. This list was initially collapsed, but could be expanded by clicking a button.

It rapidly became obvious that this wasn’t going to fly from a performance perspective. Even with the image lists initially collapsed, mere invisibility wasn’t enough to prevent the Image elements from being created. This meant that when the application started, it would attempt to load every single bitmap found by Windows Search. We let it run for a while to enjoy the spectacle of a single process consuming over 4GB of memory—it’s entertaining to pretend you have a justification for owning a 64-bit system—before giving up and killing it off.

The naive approach clearly wasn’t going to work, but we could make a small change to reduce the memory footprint: we decided to take the image loading out of WPF’s Image element’s hands. Instead of binding the Image element’s Source directly to the bitmap path, we wrote some code to load the image. This gave us the option to specify a size for the loaded image—since we were only showing thumbnails, we told WPF to decode the image to a much smaller size, just 40x30 pixels. This way it was at least conceivable that all the images we were trying to load might fit in memory. This ‘improved’ matters in the sense that the application progressed from not working at all to working unusably slowly.

It was starting to look like some form of virtualization might be necessary.

(This is of course all utterly predictable. Less subtle minds than your own might even conclude that we were idiots for bothering to try this naive approach. But I’ve learned that it’s wise to start your performance investigations with the parts you can predict. That way you get to find out which of your predictions were wrong. Plus, you might get to observe things going wrong in a slightly different fashion from the one you expected, which can offer useful insights. Indeed, besides the rather obvious expected memory consumption problems, we observed some CPU-bound performance issues in the image handling in some places that surprised us, and which uncovered an opportunity to significantly speed up our eventual load time performance which might have been harder to spot at a later stage. I’ll cover this in a later blog.)

A couple of options stood out for improving the bitmap handling. We could get slightly cleverer with the expansion of the per-group list: rather than merely collapsing the list until the user expanded it, we could arrange not to create the list at all until needed—that should avoid the premature (and rather expensive) loading of every bitmap on the system. Or we could use a virtualizing panel for the main timeline items control, so that the groups’ UIs didn’t get instantiated at all until they appeared on screen. We tried both.

Either of these on their own produced a profound improvement—the application went from “Fail slowly” to “Sub-second load” performance. However, using just one or the other wasn’t enough to get that “sub-second” quite “sub-” enough—we were seeing a half second UI freeze between the Windows Search results coming back and the results being displayed. Only with both techniques applied was the performance satisfactory.

So we need at least one custom element: our panel needs to virtualize, and the only built-in virtualizing panel is the VirtualizingStackPanel. That doesn’t give us the positioning we want: we need to be able to select a position based on some date. Only Canvas and Grid make that sort of control possible, and neither of those can virtualize. So we need our own panel. We provisionally chose to call this a VirtualizingOffsetPanel, for want of a better name.

We also decided to build a custom control to perform the expansion. It is technically possible to get the deferred list realization needed with an Expander: the trick is to use a ContentTemplate rather than just making our image list the child of the Expander. However, we’d be relying on a side effect of an undocumented Expander behaviour. I’ve gone down a similar path before with tree view item expansion, and didn’t enjoy it. So we decided to make our own expander (which is a pretty simple thing to construct) in order to give us control over what actions occur and in which order when an item is expanded. And since this control was going to be instantiated for each item on the timeline, we decided to designate this as the item container for our timeline control. And since a custom item container requires a custom items control, we have a reason for a third custom element, the TimelineControl itself.

So it’s now looking like we’re going to write three custom elements: a TimelineControl, a TimelineGroupItem, and a VirtualizingOffsetPanel. Yes, for that second one, the name TimelineControlItem might have looked more consistent, but TimelineGroupItem felt like a more accurate description of what it represented. So far, it still feels that way, so we’re still calling it that.

Aside: To Group or Not to Group

If you’re familiar with the capabilities of WPF data binding, you might be thinking: hold on, why aren’t you using CollectionView.GroupDescriptions and a GroupStyle? Well we tried that, but it seems that grouping in ItemsControls has the side-effect of disabling virtualization. And since we need virtualization to get acceptable load performance, that’s a non-starter.

In any case, this didn’t seem like a great loss. After a fiddling around with Windows Search for a while, LINQ started to look like an easier and more flexible way to manage grouping.

Prototyping Matters

Trying to build a working example with no custom elements at all was an important exercise. We had outlined a rough design of what we thought we probably wanted before we started. This up-front design was by no means ‘big’, but we got something wrong nonetheless. We originally thought we’d want not just the timeline and group item controls, but also an individual timeline item control. But in working through the prototype, no clear need for such a control emerged—it seems that having established a need for the TimelineControl, TimelineGroupItem, and VirtualizingOffsetPanel items, a combination of content controls and data templates was enough to finish off the job.

In future blog entries I’ll talk about how we went about building each of these custom elements.

Oslo WPF and Silverlight Demos

Thu, 30 Apr 2009 15:49:57 GMT

This week I've been in Oslo, teaching a combined Silverlight and WPF course. For those of you who attended, here are the demos for download. And for those of you who didn't attend, well, you can download the demos too if you like.

Silverlight and WriteableBitmap

Fri, 07 Nov 2008 12:19:55 GMT

I’ve just released a library to CodePlex that implements a feature missing from Silverlight: the ability to generate bitmaps from pixels in code at runtime. WPF provides this through its WritableBitmap class, but Silverlight 2 doesn’t have that. My SlDynamicBitmap project offers a solution.

I was inspired to create this by the recent reports of the Silverlight port of Quake. From what the author says, it’s clear that they must have devised some sort of mechanism for pushing raw pixels onto the screen, something Silverlight really doesn’t help you with. I’ve been toying for a while with an idea about how you might solve this, but hadn’t tried it before. Quakelight shows that it’s definitely possible, which encouraged me to try out my idea.

Incidentally, I have no idea how Quakelight solves this problem. It may well have a much more elegant solution than the ghastly hack I’m perpetrating here.

Why Would I Want This?

Before I show how it works, it’s worth reviewing why you would even want a Silverlight equivalent of WPF’s WriteableBitmap – what’s it for? It’s useful for when you want to generate pixels at runtime based on some kind of algorithm. Ray tracing is one classic example – the computer constructs an image one pixel at a time, and in order to display the results, you need some way of controlling every single pixel on a region of the screen, rather than using higher level primitives.

To illustrate this I’ve chosen another classic example: a Mandelbrot set fractal renderer.

In case you’re not familiar with the Mandelbrot set, it’s a fractal generated with a deceptively simple process. It’s a striking demonstration of how incredibly basic non-linear systems can exhibit behaviour that is very complex, and which shows some very surprising geometric scaling features.

But for my present purpose, the interesting thing about the Mandelbrot set is that you end up with a program that generates a lot of pixels and needs some way to get them on the screen. In WPF, this is the kind of scenario that WriteableBitmap is for. To enable this in Silverlight, I’ve written a new class called PngGenerator.

It’s Called What?

I’ve chosen to call the main type in this library PngGenerator, and not WriteableBitmap. This may seem like an odd choice, but there are two good reasons for it. First, I regard this code as a workaround for a missing feature, not a proper solution, so I’m hoping that Silverlight will eventually get a WriteableBitmap of its own. So it would have been unhelpful of me to use the same name. Second, the usage model has ended up being pretty different – it’s not really possible to write a custom class in Silverlight that’s a drop-in replacement for WPF’s WriteableBitmap. Only Microsoft can provide us with that – it would require support from the Silverlight plug-in itself to build an exact replica.

So that’s why it’s not called WriteableBitmap. Why PngGenerator? That’s because of the ghastly hack I used to make this work.

The Ghastly Hack

The PngGenerator works by converting an array of pixel colour values into a Stream of bytes that represent the image as a PNG file. (I chose PNG rather than JPEG because JPEG files typically use lossy compression, so you don’t get precisely the pixels you asked for. It has since been pointed out to me that JPEG does now support lossless images too, so I guess you could use either format. BMP would have been a whole lot easier as it’s a simpler format than either, but Silverlight only supports PNG and JPEG.)

If Silverlight had an equivalent of WPF’s PngBitmapEncoder class, this would have been pretty straightforward to write. Unfortunately Silverlight doesn’t contain any code to generate PNGs from pixels. So most of the code in this library is a PNG builder.

By the way, I would not recommend using this code to generate PNG files for general use. It does a couple of rather crufty things. It only generates the bare minimum contents required to be just enough of a legal PNG file for Silverlight to render it. And it also doesn’t compress the data. The ‘deflate’ compression format mandated by PNG lets you put in so-called ‘non-compressible’ blocks. You’re supposed to use this for any data that gets bigger when you ‘deflate’ it. Some data is just hard to compress, and the idea is that you mitigate this problem by storing that data verbatim. But I’m storing all the pixel data this way to provide the simplest possible path from pixel to screen.

So it’s a little too specialized to be a useful general-purpose PNG generator.

I’ve seen nastier ways of solving this by the way. I’ve seen people generate Silverlight content made up of hundreds of tiny rectangles in an attempt to render their own pixel data! This doesn’t work all that brilliantly – you get anti-aliasing artefacts, and it’s mind-bogglingly slow. Unpleasant though the technique I’m using is, it does at least produce good quality results, and is tolerably quick, although not as good as a native WriteableBitmap built into Silverlight could be.

Using the PngGenerator

To use the PngGenerator, you do this sort of thing:

PngGenerator pngGen = new PngGenerator(640, 480);
Color[] m_pixelData = GenerateMyPixels();
pngGen.SetPixelColorData(m_pixelData);
BitmapImage imgSource = new BitmapImage();
imgSource.SetSource(pngGen.CreateStream());
myImageElement.Source = imgSource;

That may seem slightly less direct than necessary. I’m contemplating adding a CreateSource() method that builds the BitmapImage for you, to make the code a couple of lines shorter. But the verbose approach required by the current version does have the benefit of showing the process relatively clearly.

Walking through it, we build a new PngGenerator, telling it the image dimensions we require – 640x480 in this case. Then we build an array of Color values indicating the pixel colours we want. (So GenerateMyPixels() here stands for whatever code you’ve got that generates pixel values.) We pass these pixels to the PngGenerator’s SetPixelColorData method. Then we construct an instance of Silverlight’s BitmapImage type, and call its SetSource method. (BTW, BitmapImage.SetSource is the Silverlight feature that makes this possible. It accepts any System.IO.Stream object, and expects it to contain either a PNG or a JPEG.) The PngGenerator’s CreateStream method returns a Stream that contains a PNG representing the pixels passed in to SetPixelColorData. Finally, we use the BitmapImage as the Source property of a Silverlight Image element, and the image appears.

If you want to change the image, you just call SetPixelColorData again, and then repeat the steps to build a Stream and a BitmapImage. Silverlight’s BitmapImage only loads the PNG once – it doesn’t expect it to change – so we need to build a new one each time round. However, you’re free to pass the same array into SetPixelColorData every time around, and internally, the PngGenerator reuses all the same buffers for building the stream, so the costs of building a new frame aren’t as bad as they might be.

(My first prototype did build everything from scratch each time round. It was about three times slower than the current implementation! Memory allocation and copying start to look expensive when you’re trying to push millions of pixels around several times a second.)

Silverlight and Multicore

Incidentally, the example also happens to be a clear demonstration of Silverlight’s ability to exploit multiple CPU cores on the client side. In fact the time I first ran into the absence of WriteableBitmap in Silverlight was when I sat down to write exactly this Mandelbrot example as an illustration of how to use Silverlight’s multi-threading capabilities. At the time I had to abandon the idea due to the lack of writeable bitmap support. But finally, 6 months down the line, I can use the demo!

The code that performs the calculations to generate the fractal image uses the thread pool to parallelize the work. Crude, but effective. On my quad core desktop, it’s really quick, despite the lack of any clever optimizations that some fractal generators use. And since I first started writing Mandelbrot rendering code on 8-bit micros with 2MHz processors back in the mid 1980s, which used to take about 3 hours to produce a puny 256x256 image, I can hardly believe how fast this runs on new hardware.

Missing Features

The code up on CodePlex is designated version 0.1 because it’s incomplete. It doesn’t support an alpha channel, i.e. no semi-transparent bitmaps. There’s no fundamental reason for this, it’s just that I’ve only had time to spend a couple of evenings on this so far. I plan to add this. I also want to add a mechanism for using raw byte arrays for pixel data instead of having to use Color – there are some performance issues that this will solve. And there are a couple of places where the code is not as efficient as it could be. Right now on my machine, if I generate 1024x768 bitmaps as fast as possible it only manages about 15-20 frames per second, and I believe I can improve on that. (Although the tests I’ve performed suggests this is never going to do better than 30fps for 1024x768 on current hardware unless Silverlight evolves to provide native support for this feature.)

Getting Started

The code is up on the SlDynamicBitmap project on CodePlex. You can download a ZIP containing both binary and source, or you can browse the source online. Enjoy!

[Update, 2008-11-07: Pete Brown pointed out to me that this has already been done... Joe Stegman has some code that enables similar stuff. However, as far as I can tell my library is faster. Modifying Joe's code to do a 1024x768 image, it doesn't seem to be able to do more than about 5 frames per second. That's the same speed I got with my code before I started reducing the amount of copying and memory allocation. So while my contribution isn't original, its a few times faster than the existing work. So I hope it's still useful.]