Ayende @ Rahien

It's a girl

Designing Erlang#

I am currently reading another Erlang book, and I am one again impressed by the elegance of the language. Just to be clear, I don't have any intention to actually implement what I am talking about here, this is merely a way to organize my thoughts. And to avoid nitpickers, yes, I know of Retlang.

Processes

Erlang's processes are granular and light weight. There is no real equivalent for OS threads or processes or even to .Net's AppDomains. A quick, back of the envelope, design for this in .Net would lead to the following interface:

public class ErlangProcess
{
	public ErlangProcess(ICommand cmd);
        public static ProcessHandle Current { get; } 
	public MailBox MailBox { get; }
	public IDictionary Dictionary { get; }

	public Action Execution { get; set; }
        public Func<Message> ExecutionFilter { get; set; }
}

A couple of interesting aspects of the design, we always start a process with a command. But we allow waiting using a delegate + filter. This is quite intentional, the reason is the spawn() API call, which looks like this:

public ProcessHandle Spawn<TCommand>();

We do not allow to pass an instance, only the type. The reason for that is that passing instances between processes opens up a chance for threading bugs. For that matter, we don't give you back a reference to the process either, just a handle to it.

Messages

Message passing is an important concept for Erlang, and something that I consider to be more and more essential to the way I think about software. Sending a message is trivial, all you need to do is call:

public void Send(ProcessHandle process, object msg);

Receiving  a message is a lot more complex, because you may have multiple receivers or conditional receivers. C#'s lack of pattern match syntax is really annoying in this regard (Boo has that, though :-) ). But I was able to come up with the following API:

public void Recieve<TMsg>(
	Action<TMsg> process);

public void Recieve<TMsg>(
	Expression<Func<TMsg, bool>> condition, 
	Action<TMsg> process);

A simple example of using this API would be:

public class PMap : ICommand
{
	List<object> results = new List<object>();

	public void Execute()
	{
		this.Receive(delegate(MapMessage msg)
		{
			foreach(var item in msg.Items)
			{
				Spawn<ActionExec>().Send(new ActionExecMessage(Self(), msg.Action, item));
				this.Recieve(delegate(ProcessedItemMessage itemMsg)
				{
					results.Add(itemMsg.Item);
					if(results.Count == msg.Items.Length)
						msg.Parent.Send(new ResultsMessage( results.ToArray() ));
				});
			}
		});
	}
}

This demonstrate a couple of important ideas. Chief among them is how we actually communicate between processes. Another interesting issue is the actual execution of this. Note that we have no threading involved, we are just registering to be notified at some date. When we have no more receivers registered, the process dies.

Execution environment

The processes should executed by something. In this case, I think we can define a very simple set of rules for the scheduler:

  • A process is in runnable state if it is has a message to process.
  • A process is in stopped state if there are no messages matching the current receivers list.
  • A process with no receivers is done, and will be killed.
  • A process may only run on a single thread at any given point.
  • It is allowed to move processes between threads (no thread affinity).
  • Processes have no priorities, but there is a preference for LIFO scheduling.
  • A process unit of work is the processing of a single message (not sure about that, though).
  • Since the only thing that can wake a process is a message, the responsibility for moving a process from stopped to runnable is at the hands of the process MailBox implementation.

Okay, that is enough for now.

Comments?

Comments

Gilligan
09/22/2008 02:47 PM by
Gilligan

I love it! I always stood in awe at the simplicity of Erlang. I think showing the principles as C# code will allow many others to also see how cool the ideas behind Erlang really is.

Mike Brown
09/22/2008 03:07 PM by
Mike Brown

So basically a function call in Erlang is represented by an object rather than just passing data around on a stack. This sounds interesting to me. Is there a book I can pick up to get started learning this?

Ayende Rahien
09/22/2008 03:23 PM by
Ayende Rahien

No, that is not how it works.

I suggest getting Programming Erlang, it is a great book

Mike Brown
09/22/2008 03:30 PM by
Mike Brown

Sorry I had changed my message must have ctrl+z'd my change. I was comparing it to how starting a WF instance through an ExternalDataEvent works. You define the workflow and fire it off with a message.

Of course WF is a bit more heavy weight than your description of Erlang implies and there is the whole multi-threaded thing :P

Peter Ibbotson
09/22/2008 04:16 PM by
Peter Ibbotson

Well if you ever get it off the ground and want the IronErlang(.com|.net|.org) domains I'd be more than happy to pass them over. I've been way too busy to actually get started.

I kept on wondering about using fibres for processes but I couldn't convince myself it was worth the trouble.

Ayende Rahien
09/22/2008 04:23 PM by
Ayende Rahien

Peter,

You don't need fibers, you just need simple execution for the scheduler in user mode.

Matthew Podwysocki
09/22/2008 05:32 PM by
Matthew Podwysocki

I would more look at designing this around the DLR, as it has better ways of handling process separation around the script hosts. I did a heavier implementation on C# a while ago using AppDomains, because if any given process dies, I have another to watch, clean up and report the problems.

Matt

Ayende Rahien
09/22/2008 05:51 PM by
Ayende Rahien

Matthew,

The problem here is that it is expected to have hundreds of thousands to millions of processes. Most isolation strategies break down in the mere hundreds

Igor Tamaschuk
09/22/2008 10:31 PM by
Igor Tamaschuk

It's really inspiring to finally develop a fluent scheduler framework for long term execution code launched within requests service process (say asp.net)... especially as because I m working on this special solution in the one of my current projects...

Stephen
09/23/2008 01:29 AM by
Stephen

My naive impression was that instead of pattern matching against incoming messages, in a statically typed language you'd just type every message as a separate class and then do some sort of double dispatch against it.

e.g. handle(Message m) if m instanceof FirstMessageType this.handle((FirstMessage m), if m instanceof SecondMessageType this.handle((SecondMessage) m) else pass.

That being said, I've never worked with/studied in-language pattern matching before, so perhaps there is awesomeness that switching just on type would be missing out on.

Ayende Rahien
09/23/2008 04:37 PM by
Ayende Rahien

Will,

CCR is on my "to figure out" list for a while now.

Can you create a sample pmap using the CCR and share with us? I would be interesting to see how this works.

Frank Quednau
09/23/2008 07:10 PM by
Frank Quednau

No idea if that's of interest to you but linking costs nothing. Here's a ton and a half on writing a pattern matcher with Expression<...> in c# over here...

bartdesmet.net/.../default.aspx

Comments have been closed on this topic.