Cω stream flattening
10 Jun 2010This post was imported from blogspot.
The Microsoft research language Cω (C-omega), which predates C# 3.0 (and even 2.0?), extended C# with a number of interesting features, of which C# 3.0 includes several comparable features. To me the most interesting thing in Cω was streams, which are roughly just lists of things in IEnumerables. For instance, the stream "int*" basically means "IEnumerable<int>", but they allowed you to manipulate lists of things without using explicit loops:int* FromTo(int from, int to)
{
for (i = from; i <= to; i++) yield return i;
}
void Example()
{
Console.WriteLine(string.Join(", ",
ToArray(FromTo(1, 10)[it % 2 == 0].ToString())));
// Output: 2, 4, 6, 8, 10
}Luckily, LINQ provides similar features in C# 3.0, just with a different syntax:
IEnumerable<int> FromTo(int from, int to)
{
for (int i = from; i <= to; i++) yield return i;
}
void Ex()
{
Console.WriteLine(string.Join(", ",
(from i in FromTo(1, 10) where i % 2 == 0 select i).ToString()).ToArray()));
}There's one thing missing from C# 3 that I would really like, though: flattening. Quite simply, you can combine Cω streams easily with no performance hit. The Cω guys illustrated this in a paper with a silly, but illustrative, alternative to FromTo():
int* FromToB(int b, int e)
{
if (b>e) yield break;
yield return b;
yield return FromTo2(b+1,e);
}They explain tersely:
Without flattening we would be forced to copy the stream produced by the recursive invocation, leading to a quadratic instead of a linear number of yields:
int* FromToC(int b, int e)
{
if (b>e) yield break;
yield return b;
foreach (int i in FromTo3(b+1,e)) yield return i;
}
Basically, FromToC does the same thing as FromToB, except that it is extremely slow. The reason is that when you enumerate over FromToC, a new enumerator is created on every iteration, and because the enumerators are nested, each enumerator that exists must be called in sequence to enumerate a single value.
This is perhaps better illustrated by the following practical example, which gives you a list of all subfolders of a folder:
public IEnumerableSubFolders(string path) { yield return path; foreach (string dir in Directory.GetDirectories(path)) foreach (string subfolder in SubFolders(dir)) yield return subfolder; }
Suppose you write
var folders = SubFolders(@"C:\").GetEnumerator();
while (folders.MoveNext())
Console.WriteLine(folders.Current);Imagine that somewhere in the middle of this process, the enumerator returns "C:\Windows\System32\drivers". This does not happen directly. First the MoveNext() method of the enumerator for "C:\" is called. That enumerator calls MoveNext() on its child enumerator, "C:\Windows". The child enumerator then calls MoveNext() on its child, "C:\Windows\System", which advances to "C:\Windows\System32\drivers". Thus, for all subfolders that are 3 levels deep, the MoveNext() method is actually called 3 times. I hope you can see that the code will get slower as the directory structure gets deeper--not just because the strings are longer, but because the MoveNext() gets called one extra time for every level of nesting.
Stream flattening is a feature of Cω that removes all the intermediate calls to MoveNext(), so that MoveNext() and Current are only called once for every folder returned, while at the same time making the code simpler:
public IEnumerableSubFolders(string path) { yield return path; foreach (string dir in Directory.GetDirectories(path)) yield return SubFolders(dir); }
Stream flattening and the "*" syntax make it more convenient to write coroutines. Coroutines are useful for numerous purposes, but perhaps the most obvious is game programming. In games you need to program numerous "actors", each with its own behavior. Actors' behavior can be described in a linear way. For instance an enemy might have logic like this:
- Wander around until player is within 10 metres - Attack the player while my health > 25% - Retreat until distance from player exceeds 50 metres - Regenerate health at 1% per second - If at any time my health reaches 0%, - run death animation - wait 10 seconds - despawn the body
Logic like this could be expressed straightforwardly using streams... something like this:
class Enemy : AbstractEnemy
{
public override IAction* EnemyLogic()
{
// The game engine resumes this method every frame
foreach(var a in NormalBehavior()) {
yield return a;
if (Health <= 0)
break;
}
yield return DeathAndUnspawn();
}
IAction* NormalBehavior()
{
for(;;) {
while(Distance > 10) {
yield return Wander();
Health = Math.Min(Health + 0.01 * TimePerFrame, 1.0);
}
while(Health > 0.25)
yield return Attack();
while(Distance < 50)
yield return Retreat();
}
}
IAction Attack() { ... }
IAction Retreat() { ... }
IAction Wander() { ... }
IAction* DeathAndUnspawn()
{
yield return DeathAnimation();
yield return Wait(10.0);
yield return Despawn();
}
IAction* DeathAnimation() { ... }
...
}While you can certainly do this in regular C#, streams improve performance and make the syntax more convenient.
Of course, neither Cω streams nor C# generators were actually designed for coroutines; any function that contains code that can be "paused" must return some sort of IEnumerable, which can be inconvenient sometimes. For one thing, a pausable function cannot easily return a value to its immediate caller, only to its "highest-level" caller (such as the game engine).
But, since the .NET framework doesn't support genuine coroutines, this is the only option right now. Mono recently introduced continuations that it calls "tasklets", which can also be used to write coroutines (but only under Mono, not Microsoft .NET); Since they apparently duplicate and restore the entire call stack, though, I am concerned that Tasklets might have poor performance.
I don't actually know how the flattening is implemented; I'll be sure to update this entry if I figure it out.