JavaScript Generators

These work annoyingly well. Why annoying? Because they’re Mozilla specific. If only we could use them all the time. The other thing that’s annoying is how they are actually better than the C# equivalent.

There are two major advantages compared with C#’s yield return.

1. You can use yield inside an anonymous function.

2. You can make yield return a value. No, I don’t mean send a value out of the generator function to the caller. I mean the other way: the caller can send values into the generator function.

Okay, regarding point 2, in my previous ridiculous post I was doing exactly that in C#. But it was awkward:

int i = null;
yield return input => i = input;

I had to yield a lambda so the client could call it, passing me the input, which I then assign to a named variable. Ugh. But in JavaScript in Mozilla, you can do this:

document.body.innerHTML = yield ASYNC.ajax("message.txt");

Note the yield, hiding there in front of an expression. The ASYNC object is a little utility I’ve just written to learn how to use this stuff:

    var ASYNC = {

        ajax: function(url) {

            return function(receiver) {

                jQuery.ajax({ url: url, success: receiver });
            };
        },

        run: function(gen) {

           var quitRequested = false;
           var result = undefined;

           var manager = {

               quit: function() {

                   quitRequested = true;
               },

               step: function() {

                   var y = undefined;

                   try
                   {
                       y = gen.send(result);
                       result = undefined;
                   }
                   catch (e) { }

                   if (quitRequested || y === undefined) {

                       gen.close();

                       if (manager.finished)
                           manager.finished();

                       return;
                   }

                   if (y === null) {

                       window.setTimeout(manager.step, 0);
                       return;
                   }

                   y(function(newResult) {

                       result = newResult;

                       manager.step();
                   });
               }
           };

           gen = gen(manager);

           manager.step();
           return manager;
        }
    };

With this in place, we can do:

$(document).ready(function() {

        ASYNC.run(function() {

            for (var i = 0; i < 100; i++) {

                document.title = i;
                yield null;
            }

            document.body.innerHTML = yield ASYNC.ajax("message.txt");

            for (var i = 0; i < 100; i++) {

                document.title = i;
                yield null;
            }
        });
    });

This counts to 99 on the title bar, then grabs a text file from the server and displays it, then counts to 99 again.

By yielding null, we say “let the browser have a turn”, so the UI can update to reflect the changes we’re making. But we can also yield a function that, when called, returns another function that accepts a function to which an output value can be passed. (Read that a few dozen more times until it goes in.) The ASYNC.ajax function is a fine example. The output value is then stashed away so it can be sent back into the generator and get returned from the next call to yield.

Of course, the advantage of this is that you can write a mix of UI updating and AJAX requests in a linear fashion, instead of having to chain together a zillion callbacks.

I really wish this was in C#… also apparently you can give the generator an exception you’d like it to throw on the next yield, which is beautiful. That way if the AJAX request fails, the yield can throw an error. And that’s something else I’ve previously wished for in C#.

Presumably all this was in CLU’s original version of this idea, but I don’t know anything about that.

Linq To Stupid

This is perhaps the oddest idea I’ve had for a while.

In functional programming, we write functions that return values, and have no side effects. But often it is useful to consider a series of operations that work as a pipeline and “pass forward” their results to some object. Each operation therefore has no return value in the usual sense. It has to have a side-effect on something, or there would be no point in it executing.

We can represent such an operation in C# with the Action<T> delegate. For example:

Action<object> print = v => Console.WriteLine(v);

Now we can imagine a stream of values being passed to that delegate. But this is unsatisfactory, because there is no way to notify that the stream has ended. But we can solve that!

And the stupidest way I can think of (actually it’s quite fun, but almost certainly useless) is as follows. Instead of representing a destination for values by a mere Action<T>, we can use IEnumerable<Action<T>>. That is, we get a sequence of recipients. Bear in mind that to loop through such a thing, we have to get an IEnumerator from it, and when we’re done with it, we Dispose of it. So this properly communicates the fact that the sequence has a beginning and an end.

Now, this raises the question of how you might implement the receiver. The obvious (!) answer is to use yield return.

public static IEnumerable<Action<object>> Print()
{
    for (;;)
    {
        object item = null;
        yield return input => item = input;

        Console.WriteLine(item);
    }
}

This is quite a curious beast. It’s a function that reads a series of values from it’s own return value. You see what I mean by stupid. And how would you pass a sequence of values to such a beast?

public static void Read<TIn>(this IEnumerable<Action<TIn>> destination, IEnumerable<TIn> source)
{
    var e = destination.GetEnumerator();

    try
    {
        foreach (var item in source)
        {
            if (!e.MoveNext())
                break;

            e.Current(item);
        }
    }
    finally
    {
        e.Dispose();
    }
}

The above is a general helper for driving any receiver. For example, applying it to our Print receiver:

Print().Read(new object[] {1, 6, 23, 5, 7, 2});

Now, there’s some co- and contravariance misery here. My input array is of type object, because that is what Print expects (because Console.WriteLine can print anything). But we ought to be able to pass an array of int, because ints are objects. This will perhaps be solved by C# 4.0 (I would check, but this code is too silly to bother).

Now, the odd thing is that we can now write particular versions of the Linq operators such as Select, Where, and so on. For example, here’s the specialized version of Select:

public static IEnumerable<Action<TIn>> Select<TIn, TOut>(
    this IEnumerable<Action<TOut>> destination, Func<TIn, TOut> selector)
{
    foreach (var action in destination)
    {
        TIn item = default(TIn);
        yield return input => item = input;

        action(selector(item));
    }
}

Where is similar.One slight drawback is that you have to write your linq query backwards:

Action<int> printTotal = total => Console.WriteLine("Total of squares greater than 4 is: " + total);

printTotal.Aggregate((l, r) => l + r)
    .Where(square => square > 4)
    .Select((int n) => n*n)
    .Read(new[] {1, 6, 23, 5, 7, 2});

Each step is the recipient of whatever is produced by what comes after it. I do not call it Linq to Stupid lightly.

But there are some other things that we can do here that Linq cannot do!

For instance, we can multicast. That is, we can attach several receivers together to appear like a single receiver, and then push a stream of values into them:

public static IEnumerable<Action<TIn>> Multicast<TIn>(
    this IEnumerable<IEnumerable<Action<TIn>>> destinations)
{
    var enumerators = destinations.Select(d => d.GetEnumerator()).ToList();

    try
    {
        for (; ; )
        {
            TIn item = default(TIn);
            yield return input => item = input;

            foreach (var enumerator in enumerators)
            {
                if (!enumerator.MoveNext())
                    break;

                enumerator.Current(item);
            }
        }
    }
    finally
    {
        enumerators.Dispose();
    }
}

This has been a hot topic recently, with the arrival of Microsoft’s Rx framework, and before that community efforts like Push Linq. Those libraries are predicated on the assumption that there are certain things you can’t do with IEnumerable.

I think I’ve demonstrated that in fact you can do a forward-passing pipeline, if you’re prepared to use IEnumerable in the stupidest possible way.

WPF Performance

I’m doing some work on performance in WPF. One curious standout is dashed lines. A pen with the DashStyle set to DashStyles.Solid is very much faster than one with DashStyles.Dash. Obviously this will only make a difference if you’re drawing a lot of them, but if you have a hundred or so on a Canvas, you will notice a severe degredation in the smoothness of scrolling the Canvas.

Node#

The node.js project is a rapidly evolving effort to build a runtime for writing event-driven servers in JavaScript. It’s part of a general JS renaissance, growing from a widening appreciation of the positive aspects of JS compared with other well-established languages such as C/C++ and Java. These include closures and dynamic typing, though I’d argue the former is much more important than the latter.

Due to the fact that server-side JavaScript is still in its infancy, node.js has to specify everything from scratch. For example, there is currently no widely accepted standard for linking together multiple independent JavaScript source files into one program (though it may be on the way). Nor is there a standard library for accessing files or network resources.

But the node.js project regards this blank slate as a crisitunity to lay down the law. No operations will be allowed to block – instead they return an object called a promise, which is basically a bundle of standard events (such as “success” and “error”) that you can listen for.

Event-driven programming is certainly not going to come as a big shock to those who’ve written GUI applications on Windows or the Mac. But in server-side programming it’s perhaps less widely used. One key restriction of JavaScript right now is that there should only be one thread executing the script, so thread-based parallelism is effectively ruled out. But this is not necessarily a problem, because web servers spend most of their time waiting for an OS service to complete, whether it’s sending/receiving on a socket or reading from a file. Given this, a single-threaded state machine is likely to be more efficient and scalable than a system that uses a thread to manage each client. As long as the CPU work is fairly minimal, it may never be necessary to share it between multiple threads. So it’s just another crisitunity: no threading, but maybe that’s a good thing. (It certainly is in my opinion; I’ve long regarded shared-memory concurrency as a practical joke that has backfired with tragic consequences.)

There appears to be some active debate on the node.js mail list about whether promises are the right way to go (they certainly don’t make composition particularly smooth). But nevertheless node.js can already make some working examples appear to be delightfully clear and simple.

Right now if you want to play with node.js on a Windows system, the easiest approach is to start it up in a VM. The reason is that they are not really ready with a Windows port. The non-JS parts of the source are written to the POSIX API which is (of course) different in almost every detail from Win32.

But this is not a problem, because maybe the spirit of node.js can still be valuable even if the specific implementation is not the same. On Windows there is a well-established language, C#, that has closures just like JS.

JS:

var counter = 0;
var increase = function(amount) { counter += amount; };
increase(3);
increase(4);
// counter now has value 7

C#:

var counter = 0;
Action<int> increase = amount => counter += amount;
increase(3);
increase(4);
// counter now has value 7

(Note that we have to specify the type of the increase variable – C# has pretty good type inference, but it’s deliberately simple in some ways to keep error messages from becoming incomprehensible).

In fact it goes one better because it also has a built-in concept of events (lists of closures that can be executed with a single call so they all get the same arguments). This raises the possibility of supporting the creation of event-driven servers in C# in which the code will have the same pattern as node.js servers. The .NET platform certainly has all the asynchronous and thread-pool APIs we need.

So mostly for fun I’ve written a small library which is inevitably called Node#.

Here’s a very simple web server – actually it’s barely a web server at all, but it’s close enough to fool a browser:

Process.Run(p =>
    p.Listen(8726).Connect += client =>
    {
        client.ReadLine().Success += line =>
        {
            string body = "Zoidberg says: \"Screw you!\"\r\n" +
                          "(responding to " + line + ")";

            client.Write(
                "HTTP/1.0 200 OK\n" +
                "Content-Type: text/plain\n" +
                "Content-Length: " + body.Length + "\n" +
                "\n" +
                body);
        };
    });

You can download all the code here.

Build it and start NodeSharpCmd.exe, and then hit this URL in your browser:

http://localhost:8726/wiggles

Your browser will display:

Zoidberg says: "Screw you!"
(responding to GET /wiggles HTTP/1.1)

The first important concept from node.js is that our application code is single-threaded, so we never need to implement locks to control access to shared data. And yet in the background the library is using background threads like crazy. The solution to this contradiction is that there is one thread running an event loop, which reads arbitrary units of work from a queue and executes them. When any background thread wants to raise an event, it must post it into the queue so that it will be extracted and executed in the event loop thread.

To allow this, the guts of the library must have a channel for cross-thread communication:

public class Channel<T>
{
    private readonly Queue<T> _queue = new Queue<T>();

    public void Enqueue(T item)
    {
        lock (_queue)
        {
            _queue.Enqueue(item);
            if (_queue.Count == 1)
                Monitor.PulseAll(_queue);
        }
    }

    public T Dequeue()
    {
        lock (_queue)
        {
            while (_queue.Count == 0)
                Monitor.Wait(_queue);

            return _queue.Dequeue();
        }
    }
}

This could be used to pass any kind of value between threads, but in our case we want to pass units of work. In C# an arbitrary unit of work is an Action delegate:

var channel = new Channel<Action>();

An event loop is then extremely simple:

for (;;)
    Channel.Dequeue()();

That is, we repeatedly pull an action from the queue and then execute it, which is why we have another pair of parentheses on the end. The Dequeue method blocks while the channel is empty, so when another thread posts an action to the channel, the event loop will immediately wake up and execute it.

So from a background thread, we can easily “move” an operation into the event loop thread:

channel.Enqueue(() => Console.WriteLine("Hi!));

Another useful idea is the promise, which is the typical return value of a non-blocking operation. An operation either succeeds, in which case it produces zero or more useful results, or it fails, in which case it produces an Exception object. As C# is a statically typed language (and doesn’t yet have an automatic syntax for declaring variadic generics) we need a few versions of a Promise class with different numbers of arguments for the Success event. For example, here’s a simplified version of the two-arg promise:

public class Promise<TArg1, TArg2> : PromiseBase
{
    public event Action<TArg1, TArg2> Success = delegate { };

    public void EmitSuccess(TArg1 arg1, TArg2 arg2)
    {
        Success(arg1, arg2);
    }
}

So, armed with promises and an event loop, we can define the IO system. For simplicity I’ve gone for a more homogeneous approach than node.js, in that I use the same interface for files and sockets:

public interface IFileDescriptor
{
    Promise<byte[]> Read(int length);
    Promise Write(byte[] data);
    Promise Close();

    Process Process { get; }
}

(Note that the Process object is available via a property; we need to pass it around so that we can post to the event loop.)

Another difference with node.js is that we defer the question of text encoding and just use the native byte array type for the data in streams. We then have extension methods for convenience:

public static Promise Write(this IFileDescriptor fd, string text, Encoding encoding)
{
    return fd.Write(encoding.GetBytes(text));
}

public static Promise Write(this IFileDescriptor fd, string text)
{
    return fd.Write(text, Encoding.UTF8);
}

Extension methods augment an interface, making it appear to have additional methods. So now we can write a string to any file descriptor and it will by default become UTF-8:

fd.Write("Hello, world");

Of course, we still need to provide an implementation for each low-level method, but this is a fairly simple pattern of wrapping a call to an asynchronous method on a .NET stream object:

public Promise<byte[]> Read(int length)
{
    var buffer = new byte[length];
    var promise = new Promise<byte[]>(_process);

    _fileStream.BeginRead(
        buffer,
        0,
        length,
        a =>
        {
            try
            {
                _process.Channel.Enqueue(() =>
                     promise.EmitSuccess(buffer.Trim(_fileStream.EndRead(a))));
            }
            catch (IOException x)
            {
                _process.Channel.Enqueue(() =>
                    promise.EmitError(x));
            }
        }, null);

    return promise;
}

The asynchronous methods in .NET always start with a BeginXXXX method, to which a callback is passed. But the callback executes in some random thread, which is not what we want. So we supply a “middleman” callback that just posts the real callback (the raising of the Success event) to the event loop. We also catch any IO-related exception and use it to raise the Error event.

That is the basic pattern that is always followed to wrap an asynchronous operation in a promise. But note that a promise is suppose to only be used once. When you have a callback that should be called many times, define a different class with specific events. For example, the Process class has a Listen method that returns a Server object, which in turn has a Connect event that fires whenever a TCP/IP client connects to the listening socket managed by the Server object.

The only other thing used in the simplified web server example is ReadLine, another extension method. It’s an example of a composition on top of other promises, and I’ve given it a really inefficient (but working) implementation, reading one character at a time until I’ve built up a whole line:

public static Promise<string> ReadLine(this IFileDescriptor fd, Encoding encoding)
{
    var promise = new Promise<string>(fd.Process);
    var bytes = new List<byte>();
    Action readChar = null;

    readChar = () =>
    {
        var read = fd.Read(1);
        read.Error += x => promise.EmitError(x);
        read.Success +=
            data =>
            {
                if (data.Length != 0)
                {
                    if (data[0] != '\n')
                    {
                        bytes.Add(data[0]);
                        readChar();
                        return;
                    }
                }

                fd.Process.Channel.Enqueue(() =>
                    promise.EmitSuccess(
                    encoding.GetString(bytes.ToArray()).TrimEnd('\r', '\n')));
            };
    };

    readChar();
    return promise;
}

To do composition, you have to forward on the events to the outer promise. In my simplified implementation there are only two, so it doesn’t seem so bad. I define a local function readChar that repeatedly calls itself until it hits a newline.

And that’s all there is to it. Probably not directly useful in production code, but maybe it has pedagogical value, translating the concepts of event driven IO programming into yet another language.

More on delegates vs interfaces

A commenter on yesterday’s post asked about the lack of Dispose. Here’s a way of doing it:

public static IEnumerable<T> AsEnumerable<T>(
    this Tuple<Func<Tuple<bool, T>>, Action> source)
{
    try
    {
        for (var i = source.Item1(); i.Item1; i = source.Item1())
            yield return i.Item2;
    }
    finally { source.Item2(); }
}

public static Tuple<Func<Tuple<bool, T>>, Action> AsTuple<T>(
    this IEnumerator<T> source)
{
    return Tuple.Create<Func<Tuple<bool, T>>, Action>(
        () => source.MoveNext() ? Tuple.Create(true, source.Current)
                                : Tuple.Create(false, default(T)),
        source.Dispose);
}

public static Tuple<Func<Tuple<bool, T>>, Action> AsShared<T>(
    this Tuple<Func<Tuple<bool, T>>, Action> source, int clients)
{
    var padlock = new object();
    return Tuple.Create<Func<Tuple<bool, T>>, Action>(
        () => { lock (padlock) { return source.Item1(); }},
        () => { lock (padlock) { if (--clients == 0) source.Item2(); } }
        );
}

So then we can make something that can be shared between threads.

var mySequence = SomeFancyIteratorMethod();

var shared = mySequence.GetEnumerator().AsTuple().AsShared(4);

// in four other threads...
foreach (var n in shared.AsEnumerable())
{
    // can use 'break' in here
}

But is this necessarily a “good” way to do it?

It’s important to remember that we’re trying to solve two problems at once. Firstly, we need a single method for stepping through the items to be able to lock around it. Secondly, it’s usually more succinct and expressive to be able to write an inline lambda instead of a whole separate named class to implement an interface.

But when your interface of necessity has two operations in it, as this one does, then you’re going to be dealing with nested tuples of delegates, and C#’s type infererence just isn’t powerful enough to make that look pretty. The thing we’re using to represent a disposable iteration is Tuple<Func<Tuple>, Action>, or in other words: a tuple containing two things: a delegate that returns a tuple containing a bool and T, and an delegate that returns nothing. There are no helpful meaningful names on these things, so it starts to get pretty obscure.

This is what custom types (class, struct) are all about. Although tuples are great in short examples, I suspect in most real C# programs, we will continue to prefer custom-declared types so we can give meaningful names to things.

The above code would therefore probably be improved by writing a small class to use instead of Tuple, specifically for holding a GetNext delegate and a Dispose delegate. Apart from that, I think it has an edge over writing out traditional interfaces and classes that implement them, because lambdas and closures are just so much more succinct. A lot of noise in the code disappears because we don’t have to write constructors and fields explicitly.

There are lots of things of value that we can learn from functional programming languages, but I think un-named tuples are probably not the greatest thing.

By the way, there’s not actually anything strictly functional about this whole topic; in a pure functional language, a function never returns a different value the second time you call it with the same arguments.

If you remove that constraint, then a functional language would be nothing special! People talk about how in functional languages, there are higher order functions, which are functions that accept a function and return another function, and functions can be bound to data (closures). Well, in widely-used OO languages, an object is essentially a dictionary of functions (indeed, in JavaScript, that’s exactly what an object is). So string.Trim is a function that takes a dictionary of functions and returns another dictionary of functions. Big deal!

Threadsafe Interfaces, Delegates vs Interfaces, Stuff Like That

The mighty Skeet posted the other day about the idea of using a single instance of IEnumerable as a shared input for multiple threads (not that I realised at first, but I got there eventually).

Clearly the interface is no good for that purpose, because two operations (“check for existence of next item” and “read next item”) are exposed as separate methods/properties, so it can’t be made atomic. Jared Parsons has blogged a lot of times very readably about this.

This got me thinking, because I’ve noticed that I can often shrink an interface declaration down so it only has one method. And then it doesn’t need to be an interface; it can just be a delegate. That way you can implement it on the fly with a lambda expression. If you express it without any out/ref parameters, you don’t even have to declare a new delegate type. And if you have a Tuple class (as in .NET 4.0), you don’t need to declare any new types – just higher order methods.

Suppose you have a method that takes no parameters and returns something, i.e. any Func. This might be a useful general facility:

public static IEnumerable<T> Repeat<T>(this Func<T> read)
{
    for (; ; ) yield return read();
}

So now with any such method you can turn it into an IEnumerable:

Func<string> readLine = Console.ReadLine;
var lines = readLine.Repeat();

If you are in the habit of handing out such functions to multiple threads, and you want them to synchronize their calls to it, this would presumably be useful:

public static Func<TResult> ToAtomic<TResult>(this Func<TResult> func)
{
    var padlock = new object();
    return () => { lock (padlock) { return func(); } };
}

So for any function, you can now make another function that takes out a lock before calling the original function. (At first glance this may appear pointless, as the padlock object looks like a local variable, but it’s not – it’s captured by the new function we’re returning, and so will be shared across any callers who have a reference to that returned function.) So for example:

var threadSafeReadLine = readLine.ToAtomic();

(Not a great example if readLine is Console.ReadLine, as I think that’s probably already atomic).

As atomic interfaces often involve single methods (because otherwise they are impossible to make atomic in a simple way), this might be a very general useful facility, and you could create overloads of ToAtomic for 1, 2 … 8 arguments.

IEnumerator doesn’t fit that pattern, but we can fix it very easily with another extension method:

public static Func<Tuple<bool, T>> ToFuncT>(this IEnumerator<T> source)
{
    return () => source.MoveNext() ? Tuple.Create(true, source.Current)
                                   : Tuple.Create(false, default(T));
}

This makes us a new delegate that returns a Tuple, in which the bool will be false when we reach the end of the list. By converting to a Func in this way, we can now apply our ToAtomic extension to it. That makes it safe to hand out to multiple threads. Then for each thread seperately, we can turn it back into an IEnumerable by applying our Repeat extension to it.

Although for real convenience, a worker thread doesn’t really want an infinite sequence of tuples! They’d surely prefer a sequence of simple values, which terminates when there are no more values. That’s easy enough to enable:

public static IEnumerable<T> ToEnumerable<T>(
                  this Func<Tuple<bool, T>> read)
{
    return read.Repeat().TakeWhile(item => item.Item1)
                        .Select(item => item.Item2);
}

So now we can write a simple test:

var results = new HashSet<int>();

var atomicResultsAdd = new Func<int, bool>(results.Add).ToAtomic();

const int count = 10000000;
var numbers = Enumerable.Range(0, count);

var atomicNumbers = numbers.GetEnumerator().ToFunc().ToAtomic();

Util.Multithread(4, () =>
    {
        foreach (var number in atomicNumbers.ToEnumerable())
        {
            if (!atomicResultsAdd(number))
                Console.WriteLine("Clash: " + number);
        }
    });

for (int n = 0; n < count; n++)
{
    if (!results.Contains(n))
        Console.WriteLine("Skipped: " + n);
}

The definition of Util.Multithread is left as an exercise for the reader. Of course all it does is run the action passed to it on the requested number of threads, and waits for them all to finish.

We use a HashSet to check that each number in the range is consumed exactly once by a thread. (Another job for ToAtomic to do – this time, it’s the overload that takes one argument, which wraps the HashSet.Add method.)

You can see the difference if you change the expression for atomicNumbers (apologies for the chemistry pun):

var atomicNumbers = numbers.GetEnumerator().ToFunc() /*.ToAtomic()*/ ;

By commenting out that ToAtomic at the end, we cause a random number of messages about clashes and skips. Even so, they can be surprisingly rare, which is why threading bugs are so horrible. Here I’m testing with a range of ten million, and I still only get a handful of clashes or skips. This would presumably depend a little on the hardware.

I should say that the only problem with all this is that IEnumerable is not actually something that can generally be collapsed into a single method, because of its pesky (but very important) Dispose method that it inherits from IDisposable. If a consumer abandons an iteration without calling Dispose, then if the iteration is defined by an iterator method (containing yield return statements) it will not execute any outstanding finally blocks. So you can only use this approach safely for enumerators that don’t require clean up when they are abandoned.

Zip and Tuple Neatness

In BCL 4.0, there’s still no Unfold method (boooo), but at least there’s a Zip extension method to keep us warm as winter draws on.

I played with it thusly:

    var list1 = new[] { 1, 2, 3 };
    var list2 = new[] { "a", "b", "c" };
    var both = list1.Zip(list2, (first, second) => new { first, second });
    foreach (var item in both)
        Console.WriteLine(item);

Then I thought, what about these new fangled tuples? Shouldn’t there be an overload of Zip that only takes two lists and is smart enough to return a binary tuple?

Then I realised there’s not really much need, because you can ask for that to happen very succinctly already:

var both = list1.Zip(list2, Tuple.Create);

This is not technically that astounding, because it’s just an example of a pre-defined function happening to fit the delegate required by some method. No big deal.

But in another way, it is a big deal, because of the generality of it. Suppose you have a generic method that accepts a delegate as one of its parameters, and that delegate must accept some fixed number of parameters of specific types, but can return any type. Sometimes you just want to be able to say “Oh, whatever they are, just stick them together and I’ll figure out what to do with them later”. Well, now that wish has a name, and it’s name is Tuple.Create. And this is applicable for any method that takes a delegate that takes up to 8 parameters and can return a value of unconstrained type.

Sometimes I just want to cry at the beauty of functions-as-first-class-objects.

(Just occasionally.)

Scary Error

I’ve had error messages before where there was no text, just OK or Yes/No buttons, which looks amusing because you’ve no idea what you’re agreeing to. But if the button has no text either, the whole thing looks oddly sinister.

How var fixes a type hole in C#

Assuming we have:

public class Base {}
public class Derived : Base {}
public class Unrelated {}

We can make a list of Base:

List baseList = new List();

And we can loop through the list:

foreach (Base item in baseList)

What other types can we use for the loop variable? We would expect to be able to use a type from which the collection’s item type is derived. In this case, that’s object:

foreach (object item in baseList)

And that’s fine, it makes perfect sense, because everything on our list is surely an object. If we had a list of Derived it would also make sense to let us use Base as the type of the loop variable. All good.

It wouldn’t make sense to let us use Unrelated:

foreach (Unrelated item in baseList)

It’s a certainty that the objects on our list are not of that type, so it has no hope of working. So we get a compiler error – good call!

But what about:

foreach (Derived item in baseList)

Now, the items on our list could be of that type – it’s certainly possible. But they could be of other types derived from Base. This is called a downcast, and if you need to do that, it’s often (but not always) a sign that there’s a kludge in your design.

What may be surprising is that the compiler allows this to compile. In other words, it silently inserts a downcast. This is unfortunate, because it’s probably a mistake. Most situations where you required a downcast, you would do this instead:

foreach (Derived item in baseList.OfType())

That way, anything that couldn’t be cast to the required type would be safely skipped over.

Fortunately, the var keyword comes to the rescue. Always use var to declare the loop variable and you won’t fall into this hole.

foreach (var item in baseList)

The compiler uses the static type argument of the IEnumerable interface.

Note that var with a non-generic collection will be equivalent to object. But you can use the OfType trick again:

ArrayList whatever = new ArrayList();

foreach (var x in whatever.OfType())

The foreach keyword predates generic collections, which is why it has the ability to silently cast; before generic collections, any code that looped through the contents of a collection would require a downcast, so it made a kind of sense to build it into the foreach keyword. Now we have generic collections, it makes almost no sense; but it’s not so bad because we have var to plug the hole, so we can’t fall into it.

Square Roots are slow?

Fun question on Stack Overflow just now. Someone wants to know how to fill a circle by setting pixels. In the interests of trying the simplest thing first, I suggested:

    Bitmap bmp = new Bitmap(200, 200);

    int r = 50; // radius
    int ox = 100, oy = 100; // origin

    for (int x = -r; x < r ; x++)
    {
        int height = (int)Math.Sqrt(r * r - x * x);

        for (int y = -height; y < height; y++)
            bmp.SetPixel(x + ox, y + oy, Color.Red);
    }

    bmp.Save(@"c:\users\dearwicker\Desktop\circle.bmp");

As the questioner was already using the Bresenham algorithm to minimise the use of square-root calculation, my answer naturally attracted comments, because I’d completely ignored this issue.

To be honest, I probably would have leapt to the same conclusion. After all – Math.Sqrt looks like some kind of hefty call to a method in the BCL. Who knows how many thousands of instructions we’re going to be wasting on it?

Actually, we can find out by looking in the disassembly window. So what exactly does Math.Sqrt turn into when you run the program?

for (int n = 0; n < reps; n++)
00000098 mov dword ptr [rsp+2Ch],0
000000a0 jmp 00000000000000DD
c += (int) Math.Sqrt(n);
000000a2 mov rcx,7FF001D1FF8h
000000ac mov ecx,dword ptr [rcx]
000000ae cvtsi2sd xmm0,dword ptr [rsp+2Ch]
000000b4 sqrtsd xmm0,xmm0
000000b8 movsd mmword ptr [rsp+60h],xmm0
000000be cvttsd2si eax,mmword ptr [rsp+60h]
000000c4 add ecx,eax
000000c6 mov rax,7FF001D1FF8h
000000d0 mov dword ptr [rax],ecx

That’s right – it gets inlined into what is effectively a single x86 assembler instruction!

The above disassembly comes from a test program I wrote to compare the time taken to sum the results of lots of Math.Sqrt calls, with the time taken to do simple addition. There is no difference – or at least, the difference is so small that it is lost in the noise.

So, no – square roots are not slow!