If you haven't already noticed, my blogs trends mostly towards the obscure for no reason other than I find it fun and interesting. Well, let's keep trending in that direction then.
A few weeks back while iterating over some set of data (a generic list if I recall), I paused for a moment and re-realized the enumerator I was using was a form of coroutine. If you're not familiar with the term, a coroutine is generalized subroutine that supports multiple entry points and can pause and resume execution at pre-determined points in its definition. Take for example:
foreach (var y in SuccessiveSubtract(10, 1))
{
Console.Write("{0} ", y);
}
Where SuccessiveSubtract is defined as:
static IEnumerable<int> SuccessiveSubtract(int x, int y)
{
int z = x - y;
while (z >= 0)
{
yield return z;
z -= y;
}
}
You can immediately appreciate the convenience of a coroutine. The signature of SuccessiveSubtract fools us into thinking of it as a run of the mill subroutine with one entry and one exit point. However, its body reveals its true intentions; to return integer data in an on demand fashion. What we don't see is the actual run-time implementation of the coroutine in the above example. The yield statement acts as a sugar for the actual guts of the coroutine which is implemented in the spirit of a finite state machine. Anyhow, a quick glance at the above code shows how the foreach construct works in tandem with the yield statement to call SuccessiveSubtract multiple times all while the coroutine maintains its state across yields. Nifty.
What I do not necessarily care to talk about at this time is how to implement the enumerator design pattern and I'm also not concerned with finite state machines. But it would be fun to talk about state machines at some time in the future, so let's add that item to the to-do list. What I do care to talk about at this time is how to implement SuccessiveSubtract as a coroutine without using the foreach/yield combo. Furthermore, I plan on using continuations as a means to define control flow in and out of the coroutine.
The first step in this process is to rewrite the SuccessiveSubtract function in continuation passing style. From an earlier blog post of mine, we know the steps to follow in order to convert a function into one written in CPS:
- Change the return type, T, to void.
- Add an additional parameter C; a void returning function which takes a single argument of type T. This is our continuation.
- Replace all return statements with invocations of C.
Applying those steps to the SuccessiveSubtract function, yields its CPS'd cousin:
static void SuccessiveSubtract(int x, int y, Action<int> next)
{
int z = x - y;
while (z >= 0)
{
next(z);
// there isn't anything explicitly getting us back
// here other than when the continuation returns
z -= y;
}
}
Easy enough. So what do we have to do to the call site to accommodate the new signature of this function? What you're about to see will validate the distaste I expressed in the comment above.
// this works, but to call the coroutine again, you have to return from the continuation. is that lame?
Action<int> print = y =>
{
Console.Write("{0} ", y);
return;
};
SuccessiveSubtract(10, 1, print);
By eliminating the foreach statement we've sacrificed explicit enumeration of our sequence. Imperatively, I feel this is a sacrifice, but a functional perspective makes me think I'm on the right track and that I can do a better job of explicitly defining control flow.
In order to explicitly define control flow out of this function, I'll need it to accept a continuation N for it to invoke. To define control flow back into this function I'll pass a continuation to N to act as a hook back into the coroutine. Also, I'll want some type of mechanism to alert any call site that the sequence is out of values. Here's how that looks:
static void SuccessiveSubtract(int x, int y, Action<int> onValue, Action<Action> onNext, Action onDone)
{
int z = x - y;
if (z >= 0)
{
onValue(z);
onNext(() => SSC3(z, y, onValue, onNext, onDone));
}
else
{
onDone();
}
}
When enumerating a sequence in C# using the foreach construct, there are three things it is aware of:
- When a value is present.
- When another value exists.
- When no other values exists.
You can see how I've taken those ideas and made each into its own continuation above. This way, we're explicitly defining control flow when a value is present, when another value exists, and when our sequence is out of values. Here is how we can call this function:
Action onDone = () => Console.WriteLine("I'm done");
Action<Action> onNext = a => a();
SuccessiveSubtract(10, 1, print, onNext, onDone);
What's interesting about this is how a void returning function is able to generate a sequence of values in the spirit of a C# enumerator. If this seems like voodoo, I would recommend running this through a debugger to appreciate how I've defined control flow.
Before you get pedantic, I am aware that because of my use of recursion above I can't really call this a coroutine since the internal state of the routine is actually being maintained with closures and recursive calls. With that said, this approach was better in my eyes than the alternative use of goto statements. Which would require me to piss off Dijkstra and would also require a discussion on finite state machines.
With all that said, I think feel this was a fun and interesting exercise. I've used continuations to define control flow in and out of our coroutine, and even leveraged them in a such a way where we can iterate over a sequence of values without using an iterative structure. Well, I think that's fun and interesting at least. We also managed to use recursion and closures along the way.
It looks this this post aligned itself nicely with the spirit of this blog; obscure, fun and interesting. Stop back soon since last time I promised a post on streams, and I promise to post it shortly.
You lied about the shortened time in between posts. How dare you.
Posted by: Accentool | April 09, 2010 at 03:52 PM