segunda-feira, 19 de maio de 2008

Lightweight Fiber/Coroutines implementation on C#

I was recently experimenting with exploiting the C# 2.0 iterators to simulate continuations, as suggested in Wesner Moise's blog and came up with what seems to be a general and reasonable way to implement fibers in .NET.

To implement a logical execution thread we basically need a stack to keep track of "subroutines" and a "program counter" to keep track of the current execution point. Basically we take on the IEnumerator interface as the basic type for program counters.

Simulating an execution is simply a matter of stepping through the current IEnumerator routine. Every time this enumerator yields a subroutine, the current routine is pushed onto the stack and the "program counter" switches to the new routine. Every time a routine terminates, the stack is tested for parent routines by popping().

Here's the lightweight fiber implementation and a small sample of how to use it:
public class Fiber
{
private readonly Stack<IEnumerator> stackFrame =
new Stack<IEnumerator>();
private IEnumerator currentRoutine;

public Fiber(IEnumerator entryPoint)
{
this.currentRoutine = entryPoint;
}

public bool Step()
{
if (currentRoutine.MoveNext())
{
var subRoutine = currentRoutine.Current
as IEnumerator;
if (subRoutine != null)
{
stackFrame.Push(currentRoutine);
currentRoutine = subRoutine;
}
}
else if (stackFrame.Count > 0)
{
currentRoutine = stackFrame.Pop();
}
else
{
OnFiberTerminated(
new
FiberTerminatedEventArgs(
currentRoutine.Current
)
);
return false;
}

return true;
}

public event EventHandler<FiberTerminatedEventArgs>
FiberTerminated;


private void OnFiberTerminated(
FiberTerminatedEventArgs
e)
{
var handler = FiberTerminated;
if (handler != null)
{
handler(this, e);
}
}
}

public class FiberTerminatedEventArgs
: EventArgs
{
private readonly object result;

public FiberTerminatedEventArgs(object result)
{
this.result = result;
}

public object Result
{
get { return this.result; }
}
}
Now to implement a small recursive test program:
class FiberTest
{
private static IEnumerator Recurse(int n)
{
Console.WriteLine(n);
yield return n;
if (n > 0)
{
yield return Recurse(n - 1);
}
}

static void Main(string[] args)
{
var fiber = new Fiber(Recurse(5));
while (fiber.Step()) ;
}
}
This will print all the numbers from 5 to 0 by using fiber recursion. By yielding an IEnumerator, the fiber recursive function pushes the current fiber execution down to the recursive call. Test it yourself on the debugger and step through the execution to understand the basic mechanism.

With such a fiber/coroutine methodology its possible to define logical execution threads controlled by your application in which all involved iterator routines can be arbitrarily interrupted and resumed while preserving context.

Cool stuff once it clicks on you. Nice going for C# 2.0 iterators.

sexta-feira, 9 de maio de 2008

Immutability and the good old 'const' keyword

With all the recent interest on C# functional programming and language integration of related concepts, one of the more interesting ideas is that of expressing immutability of an object.

An object is immutable if no methods beside the constructor can modify its internal state. Automatic verification of immutability is far from trivial, so many have been asking about how one could specify that an object is immutable at compile-time.

This would be interesting in multithreaded functional algorithm implementation, since we could potentially disregard parallelism concerns during function composing. All the shared data between functions was carefully protected simply by the fact that the data itself is immutable.

A couple of days ago I led myself to think: "Wait, isn't this what the const keyword in C++ was all about?". In fact, it's interesting how easily one could verify in C++ that an object was indeed immutable. Simply declare a const reference to an object and you only have access to const methods, which are methods guaranteed by the programmer that they won't change the object's internal state.

C# effectively abolished lots of extraneous keywords, in a quest to end unnecessary verbosity and functionality perhaps, but could it be that we're on the verge of witnessing a comeback of the so-called 'const programming'? No doubt it is an interesting way of solving the problem AND making sure that everything's verified at compile time. But it definitely increases the complexity in programming.

sexta-feira, 18 de abril de 2008

NSvn Handling of Repository Externals Property Text

This first post does not entirely relate to the .NET framework itself, but rather to a useful assembly implemented by the Ankh SVN project: NSvn.

NSvn is a managed assembly to programmatically call Subversion commands like Update, Commit and others. It's a rather straightforward, and usable, library. However, there are some strange behaviors regarding some of its innards which can lead to some rather obscure bugs.

One of the latest I encountered was the handling of the svn:externals property in code. Here's a small annotated snippet of the endeavour:

Client client = new Client();
client.Checkout(sourceSVN, projectName,
Revision.Head, NSvn.Common.Recurse.Full);

Basically I instantiated a NSvn.Client instance and performed a checkout of a repository located in sourceSVN into the directory projectName.

PropertyDictionary dictionary = client.PropGet("svn:externals", projectExternalsDir, Revision.Head, Recurse.None);
Property externalsProperty = dictionary[Path.Combine(sourceSVN, "Externals")];

One can then proceed to access the svn:externals property via the PropGet method. This returns a PropertyDictionary which one can access. The Externals property itself has to be retrieved from the dictionary by specifying the full repository path.

The problem began when we reached the point of actually modifying the value of the property, in particular, when adding a new external repository line:

string values = Encoding.UTF8.GetString(externalsProperty.Data);
values += newExternal +
'\n';
values += newExternal +
'\n';
byte[] vals = Encoding.UTF8.GetBytes(values);
client.PropSet(new
Property(externalsProperty.Name, vals), projectExternals, Recurse.None);

By doing this, NSvn threw a SvnClientException indicating that there was an error parsing the property text.

It turns out that each Externals line has to be separated by a '\n' (not a '\r\n'!), but it's absolutely vital that the last line does not have ANY separator whatsoever. Adding a TrimEnd call to the end of values does the trick:

byte[] vals = Encoding.UTF8.GetBytes(newValues.TrimEnd('\n'));

Strange thing...

quarta-feira, 9 de abril de 2008

FxCritic launches

"The word critic comes from the Greek κριτικός, kritikós - one who discerns, which itself arises from the Ancient Greek word κριτής, krités, meaning a person who offers reasoned judgment or analysis, value judgment, interpretation, or observation. The term can be used to describe an adherent of a position disagreeing with or opposing the object of criticism." - Wikipedia


FxCritic is a blog dedicated to giving reasonable criticism of Microsoft's .NET framework and associated libraries and utilities. Expect commentaries about new functionalities, framework inconsistencies, bugs, weird tweakings, workarounds, interesting ways to achieve desired effects, etc.