Tony Finch – blog

Erlang is an excellent language for implementing distributed systems. One of the reasons for this is the semantics of its message-passing primitives. (Other reasons include the way it isolates processes and its distributed failure handling.)

Erlang’s send operation is non-blocking, and sends a message to a particular process. Its receive operation can block (with an optional timeout) and can selectively pick messages from the process’s mailbox out-of-order, which is useful for avoiding state explosion or tedious book-keeping.

Some languages, including occam and CML, have a send which can block until another process is ready to receive. This kind of rendezvous doesn’t make sense in a distributed setting when there is significant latency between the two processes: does the synchronization happen at the sender or the receiver? With asynchronous message passing you have to be explicit about it, typically by making the sender wait for an ack so synchronization happens at the receiver.

Instead of messages being sent to processes, many concurrent languages have a notion of a channel. The problem with channels in a distributed setting is dealing with message routing when channel endpoints can be passed from machine to machine. It’s unfeasibly tricky if (as with CML and Concurrent Haskell) multiple processes (potentially on multiple machines) can be waiting to receive from a channel.

It’s interesting to observe that, as well as scaling up gracefully, Erlang-style message passing also scales down to very simple forms of concurrency, i.e. coroutines, co-operative multi-tasking, or “fibres”. Communication between coroutines is usually synchronous (since you pass the flow of control as well as some values) and addressed by process (not by channel).

Although coroutines can be dead simple, there are some variations, chiefly between asymmetric/symmetric (distinguishing resume and yield or not), and kinds of hobbled coroutines that typically can’t yield from a nested function call. The paper about coroutines in Lua has a good survey, plus an example of how you can implement symmetric coroutines on top of asymmetric coroutines by adding a scheduler. (The dual implementation is similar.) You also need a scheduler if you are going to add features like message passing. Stackless Python is a good example of an elaborate coroutine implementation.

Erlang-style message passing between coroutines is dead simple. The send routine just appends the message to the end of a queue, and receive just pulls a message off the start of the queue and dispatches it to the destination process. For selective receive, each process can have a mailbox of pending messages which it checks for a match before dispatching on the main queue; when a process is resumed with a message that doesn’t match its current receive statement it adds the message to its mailbox and dispatches the next message from the main queue.

Thinking about this reminds me a lot of my larval stage hacking around with the Acorn Archimedes RISC OS WIMP, especially the UserMessage feature.