Reactive Programming: How to Invert an Enumerator

July 29th, 2009

“The opposite of a correct statement is a false statement. But the opposite of a profound truth may well be another profound truth.”

Niels Bohr

Enumerables and Enumerators, oh my!

Enumerables and Enumerators are great; big sacks of data we can iterate through using a well-established method. Just in case anyone isn’t up on their GOF, the pair looks a bit like this:

interface IEnumerable<T>

{

    IEnumerator<T> GetEnumerator();

}

interface IEnumerator<T> : IDisposable

{

    bool MoveNext();

    T Current { get; }

}

So we have our “sack”, our Enumerable of type T, where we can obtain a disposable reference to the Enumerator (also of type T), which we can use as a sort of pointer into the sack to move about and grab elements out. This is of course exactly what the compiler does when you use the foreach construct in C#:

foreach (var item in myEnumerable)

{

    Console.WriteLine(item);

}

// Is equivalent to:

using(var myEnumerator = myEnumerable.GetEnumerator())

{

    while(myEnumerator.MoveNext())

    {

        var item = myEnumerator.Current;

        Console.WriteLine(item);

    }

}

 

This bit of background is necessary in order to discuss the really interesting bit:

  What is the opposite of an Enumerable?

 


Part the second, where we talk about funky math

Long ago in days of yore, when computer scientists, philosophers and mathematicians all hung out at the same bars discussing grand ideas, people with names like Russell, Church, and Turing spoke of a new way of describing “stuff” that was governed entirely by the unyielding rules of math and logic. Finally, people the world over could talk about apples and oranges, and even state in precise terms how apples and oranges were both indeed fruit, even though an apple was not an orange, nor an orange an apple!

Ok, that may have been a bit much – rather than go into a deep discussion about type theory and lambda calculus, I shall refer you, humble reader, to the magic of the internets, where you shall find descriptions so as to make your brain melt into a goo. Alternatively, you could talk to this guy.

Instead, in the hopes of keeping at least some of your attention, we shall jump right in with trying to express the above Enumerable/Enumerator pair using a very simple “type language.” Looking first at the IEnumerable<T>, we see that it has one method (we’ll call it a “function”):

IEnumerator<T> GetEnumerator();

In our simple type language, we shall describe it thusly:

     () -> ( () -> T )

The above can be read as: “A function that returns a thing that contains a function that returns something of type T”. It can also be read as “A function that returns an enumerator that contains a function pair that can return something of type T”.

Of course, it’s quite a bit more complicated than this – since we are implicitly changing the state of the enumerator whenever we call MoveNext, we get into some funky stuff relating to that cringe-worthy word “Monad”, but we’re going to glaze over all that for now. Just think of it as described above.

Ok, now that is settled, we’re going to do something really funky; we’ll take this:

     () -> ( () -> T )

And turn around all the arrows, producing this (why this is a valid thing to do is related to mystical terms like covariance and contra-variance, which I won’t begin to try to describe here):

     () <- ( () <- T )

It’s a little easier to read left to right, so reordering:

     (T -> ()) -> ()

We can read this as: “A function ‘A’ that takes another function ‘B’ that takes a thing of type ‘T’ and returns nothing, with function ‘A’ also returning nothing”. Interesting…that looks a lot like the definition of a callback:

void Foo(Action<T> callback);

If we perform that same type of “type reversal” to all the members of IEnumerable and IEnumerator, we get definitions a bit like these:

interface IBackwardsEnumerable<T>

{

    void Subscribe(

        IBackwardsEnumerator<T> callbackLikeThing

    );

}

interface IBackwardsEnumerator<T>

{

    void OnDone(bool done);

    void OnValue(T value);

}

But wait, that’s not quite right…the earlier definition for the enumerator had IDisposable in there somewhere, plus there was the implicit possibility of an exception being thrown by Current.Get (in the case where we’ve MoveNext’ed past the end of the enumerable). We still need to account for all the inputs and outputs when we do our reversal (henceforth called the dual), so how do we account for these? Well, it doesn’t make a lot of sense to have our callback thingy be disposable; but we can make the registration of that callback disposable…

interface IBackwardsEnumerable<T>

{

   IDisposable Subscribe(IBackwardsEnumerator<T> callbackLikeThing);

}

interface IBackwardsEnumerator<T>

{

   void OnDone(bool done);

   void OnError(Exception error);

   void OnValue(T value);

}

Wait a second…this is starting to look a lot like an Asynchronous method call:

void AsyncMethod(T initialParameter,

   Action<T> callback,

   Action<Exception> fault,

   Action cancel);

The “callback” is what gets invoked when we have done some work (OnValue(T) above), the fault handler is invoked if we have a problem (OnError(Exception) above), and we have a way of stopping or cancelling the call in mid-process (OnDone(bool=true) above).

The similarities are not unusual – we’ve gone from a blocking-read type of operation (pulling values from an Enumerable collection) to a non-blocking write type of operation (asynchronously pushing values into a sort of stream).

Cool. So what the heck does all of that mean?

Observations on Observation

The Observer pattern (read your GOF!) is defined as:

“A software pattern in which an object, called the subject, maintains a list of its dependents, called observers, and notifies them automatically of any state changes, usually by calling one of their methods”

Looking back at the dual of the Enumerable pattern above, we can see that what we have derived is nothing more than the Observer pattern, in a slightly altered form. And so, we’ll call it as such:

interface IObservable<T>

{

    IDisposable Subscribe(IObserver<T> observer);

}

interface IObserver<T>

{

    void OnDone();

    void OnError(Exception error);

    void OnNext(T value);

}

The only change (other than renaming some things) is to remove the redundant Boolean value passed into OnDone – this is because the only time “OnDone” really matters is when that Boolean value is true. It doesn’t make a whole lot of sense to keep telling someone watching you work “I’m not done yet, I’m not done yet” when you can simply say “I’m done now”.

If this looks strangely like the way one would attach an event handler to a control – say, a button click – that’s because it’s basically the same thing, since a multi-cast delegate is pretty much an observer pattern condensed into a neat little package.

So we’ve proved, albeit in a rushed fashion, that the Observer pattern is the dual of the Enumerator pattern. We’ve also shown that it’s virtually identical to an asynchronous method call. We can also infer that it’s very similar to the way we would normally attach event handlers.

Whoop-de-do… What is the point?

Ever hear of LINQ?

Coda: QNIL

So LINQ does all its work with Enumerables. Using that same reasoning we went through above, a couple of very clever folks over at Microsoft created what is essentially “a dual of LINQ” – I rather like the idea of calling it QNIL (pronounced “Kyu-nil”), but as they are much smarter than I, I’ll use their terms and call it Rx – short for “Reactive framework”, but don’t ask me where they got the “x” from.

Introducing Rx LINQ to Events

Why is this cool? Observe, and I shall dazzle you:

Doing drag-and-drop is a pain. Every single time you implement it, you need to catch the initial mouse down event, set some internal flag to know it’s in a “dragging state”, attach some MouseMove handler to be able to determine where it’s being drug to, and then waiting for the next MouseUp event to come along so you can unhook your move handler, reset your internal state, and finally you’re done.

And you have to re-implement the same damned logic each time.

Let’s think about what we’re really trying to do. If Visual Studio understood English (Visual Studio 2014, perhaps?), I would say to it:

“If a user clicks on my control, listen for any mouse move events until the next mouse up event, and give those events to me so I can move my control where the user has moved the mouse.”

With Rx, it might be something like:

IObservable<Event<MouseEventArgs>> draggingEvent =

    from mouseLeftDownEvent in

        ctl.GetMouseLeftDown()

    from mouseMoveEvent in

        ctl.GetMouseMove()

        .Until(ctl.GetMouseLeftUp())

    select mouseMoveEvent;

draggingEvent.Subscribe(

(moveEvent) =>

{ ctl.MoveTo(moveEvent.X, moveEvent.Y);})

And that, dear reader, is just plain cool.

2 Responses to “Reactive Programming: How to Invert an Enumerator”

  1. FeepingCreature Says:

    I’ve tried to do something similar in D (which has no LINQ); this is the closest I’ve come up with:

    http://paste.dprogramming.com/dparyim7

    Also, here’s the complete code, including the stuff that would normally go in a library:

    http://paste.dprogramming.com/dpghtd5v

    How’s it stack up?

  2. Jeremy Kimball Says:

    This is actually the first time I’ve looked at D code, but it does make me want to learn the language…

    The key things to replicate would be (in my opinion): the ability to specify sequences of events, and the ability to asynchronously subscribe to events as they occur (the “push” part of the inverted enumerator).

    Good luck!