Feb 24, 2012

Asynchronous Function Looping in C#

It is often the case in code that you have to do several things in a sequence since each computation is dependent on the one(s) before it:
// ...
// stuff 1
// ...
// stuff 2
// ...
// stuff 3
// ... etc.
Good software techniques will tell you that you should break some of these up into methods:

stuff1();
stuff2();
stuff3();
If it gets big, you can even put it all in a collection and iterate (we're starting to get into weird coding now, I don't think anybody would actually do this):
var collection = new List<Action>() { stuff1, stuff2, stuff3 };
foreach (var func in collection){
func();
}
Now the part where this would actually be useful. What if some of these functions could potentially be asynchronous? That is, they depend on some value that may not be readily available - maybe user input, maybe some data from a network, etc. Blocking is not usually a great option - a modal dialog demands that the user pays attention to it even if there is something more important somewhere else. It would be better if this computation could "pause" and then resume later on when we get what we need. In some languages including Scheme and Ruby, you can accomplish this using a construct called callcc:
var collection = new List<Action<Action>>() { stuff1, stuff2,
stuff3 };
foreach (var func in collection){
// pseudo-code warning
call_cc(func);
}
Here, call_cc() will call func and pass in a function which will start executing right after the call_cc() call: it is a continuation of the loop. When func is done (or when it receives the response it wants), it can call this function to nicely continue executing the loop.

Unfortunately, C# 4.0 and lower do not support anything like callcc. C# 5.0 will support the await and async keywords which will accomplish exactly what we want, but for the time being we'll have to make do with what we have. How can we do that without callcc?

Let's give it a shot using a recursive function:
void AsyncForeach(IEnumerator<Action<Action>> iter){
if (iter.MoveNext()){
iter.Current( () => {
AsyncForeach(iter);
});
}
}
void OtherFunc(){
// ...
var collection = new List<Action<Action>>() { stuff1, stuff2,
stuff3 };

AsyncForeach(collection.GetEnumerator());
}
This would require every function in collection adhere to the Action<Action> delegate and when it is done, it will need to call the continuation manually in order to resume the computation. This is a bit annoying, and it's why all the BeginConnect, BeginSend, etc. in System.Net require an AsyncCallback to call when they are done. The new async and await keywords will be extremely useful to accomplish our task since everything is called automatically:
var collection = new List<Action>() { stuff1, stuff2, stuff3 };
foreach (var func in collection){
// func doesn't even need to call anything to
// keep this thing going!
await func();
}
It is useful to learn this from approach though. Say we want to halt the loop prematurely from within one of the functions. In that case, the function could simply not call the continuation. That would end our recursion, causing us to break out of our loop - the equivalent of the break keyword. In order to do that with the await keyword we'd have to have some sort of exception handling system, or return type, etc.

We could go even further and implement something similar to Python's for...else construct where if break is called somewhere in the computation it will run the else block:
for i in range(10):
if i == 5:
break
else:
# this is executed
print "should run"

for i in range(10):
if i == 12:
break
else:
# this is not executed
print "should not run"
We can do this by adding failure "continuations" to our functions:
void AsyncForeach(IEnumerator<Action<Action, Action>> iter,
Action failure){
if (iter.MoveNext()){
iter.Current( () => {
AsyncForeach(iter, failure);
}, failure);
}
}
void OtherFunc(){
// ...
var collection =
new List<Action<Action, Action>>() { stuff1, stuff2, stuff3 };

AsyncForeach(collection.GetEnumerator(), () => {
// handle failure
});
}
In this case the functions stuff1, stuff2, etc. will call the first function if they should continue looping, or call the second one in case of failure.

There's one final tweak to all of this. At the moment there are two problems with AsyncForeach: it depends on the type of the list we're iterating over (IEnumerator<Action<Action, Action>>), and it does not close over any variables that we may need for the loop. Can we do this using a closure?

In fact, we can:
var collection =
new List<Action<Action, Action>>() { stuff1, stuff2, stuff3 };

// declare looper early so that it closes over itself
Action looper = null;
var iter = collection.GetEnumerator();
looper = () => {
if (iter.MoveNext()){
iter.Current(looper, () => {
// handle failure
});
}
};
// don't forget to start the loop
looper();
Since this isn't so DRY, we can top it all off with a function that returns a function:
Action GetAsyncForeach<T>(IEnumerable<T> collection,
Action<T> body){
var iter = collection.GetEnumerator();
return () => {
if (iter.MoveNext()){
body(iter.Current);
}
};
}

void OtherFunc(){
// ...
var collection =
new List<Action<Action, Action>>() { stuff1, stuff2, stuff3 };

Action checker = null;
checker = GetAsyncForeach(collection, (current) => {
current(checker, () => {
// handle failure
});
});
checker(); // start the loop
}
We now have a DRY, re-usable component for implementing an asynchronous foreach loop in our code. It's not the most elegant approach, but it works really well and we don't need that much extra boiler plate to get this done (if C# supported a let rec keyword, we could make it even shorter!).

This is a useful method of looping through some asynchronous tasks that you may have to do. I found myself needing this sort of thing when calling ShowDialog would lock the entire GUI while the system waited for the user to input something, however sometimes the user would have to attend to something else before responding to the dialog. Since later actions in the loop depended on the result of the dialog box, a more asynchronous method was necessary.

Ultimately, this is why I believe that all programmers should have some experience with functional programming; this is a technique that would be obvious to a programmer in Lisp or OCaml but might be a bit trickier to someone who just has OO experience. Having functional programming know-how in your toolbelt will make you a better C# programmer.

No comments: