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.

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.