Join-calculus

A general trend in programming languages is to evolve towards higher levels of abstractions. For example the goto statement has been replaced by structured loop constructs. One of the main benefits of doing so is a massive improvement in readability. The standard concurrency constructs have not followed the same evolution; most of them are still low-level and haven’t changed much in the last thirty or forty years. Semaphores (1968) and monitors (1974) still form the concurrency basis for many “modern” languages such as Java and C#. These low-level constructs neither compose well, nor do they promote a modular approach; too often they result in programs which are difficult to understand and debug. So just like modular and structured programming facilitates abstraction and composition, we need to find similar models for concurrent programming.

Join-calculus is an elegant and simple yet powerful synchronization model. It is based on the pattern matching of messages and the execution of a block of code on matches. It was developed at INRIA in the 90’s and first implemented in JoCaml. Several implementations exist, either as libraries (e.g. Boost Join, Joins Concurrency Library) or as a language feature (Funnel, Join-Java, Cw/Polyphonic C#, MC#, VB, VODKA).

I have written my own library implementation of join-calculus which I will be using here to introduce you to join-calculus.

Join-calculus is based on messages; these can be either synchronous or asynchronous. Synchronous messages are blocking, can have arguments and return data. Asynchronous messages never block, can have arguments but cannot return any data. The following snippet defines a simple example in pseudo C#:

    public class AsyncBuffer {
        public async Put(T value);
        public sync Get();
        chord Get() & Put(T value) {
            return value;
        }
    }

This class defines two messages Put and Get: Put is asynchronous and takes one parameter, Get is synchronous and returns a value. Next we define a chord, which is essential a pattern matching expression. This one defines a pattern consisting of a Get message and a Put message. The body of the chord is executed whenever there is a match; in this case when an instance of the class has received at least one Put and one Get message. It is good practice to keep the body of the chords short, this one is particularly trivial as it simply returns to the synchronous Get message the value received from the asynchronous Put message. All messages are queued up until there is match, at which point the matching messages are removed from the message queue and the body of the chord is executed. The blocked threads of all synchronous messages in a chord are then unblocked. We can illustrate this with the following example:

Thread A will run uninterrupted as it only sends asynchronous messages. Thread B will not block until the second call to Get(). First Put(3) gets queued up in the join, then the first Get message is queued too. At this point there is a match for our chord and the first Put and the first Get messages are removed from the queue, the body of the chord is executed, and it returns a value of 3 which is then returned by the synchronous Get message. The next Get message is queued up, but this time there is no queued up Put message and hence no match, so thread B is blocked. And remains blocked until the Put(7) message has been received, which provides a match and unblocks thread B. So what is the actual function of this first chord? It takes values from one or more threads without blocking and delivers them in a blocking fashion to consumer threads. This was achieved in essentially a single line of code and three of declarations, and with no need for locks, semaphores or any low-level construct. The synchronisation semantics which combines our messages is defined in a very clear fashion by the chord.

We see now how this approach differs from the standard low-level synchronisation constructs. Instead of being scattered all over the place, join-calculus centralizes the synchronization semantics with easy to define chords within a single class. This offers the benefits of easier maintenance, improved readability and facilitates debugging. Even a classically written buffer will typically end up with two methods coupled together via a lock and some form of signalling. Although the code can be hosted in a single class, the synchronization logic will be spread inside the body of the two methods, making it harder to read and understand.

As mentioned above, Polyphonic C# and Cw had language level support for joins. But it hasn’t made it to C# yet. There is however a VB language extension, called Concurrent Basic, which supports join-calculus.

A few years ago I decided to write a library implementation of join-calculus for C#. Library implementations usually imply some overhead and excessive verbosity and this case did not escape the rule. So the existing library suffers from some inefficiencies, which I will illustrate in the implementation of the above example for an AsyncBuffer:

    public class AsyncBuffer {

        public async Put(T t) { return put.Invoked(t); }
        public T Get() { return get.Invoked(); }

        private Join mJoin = new Join();
        private SyncMethod get;
        private AsyncMethod put;

        public AsyncBuffer() {
            get = mJoin.NewSyncMethod(Get);
            put = mJoin.NewAsyncMethod(Put);

            (get & put).Do((T t) => {
                return t;
            });
        }
    }

I investigated many different implementation options and I finally opted for this one. Two features of this approach were determinant in my choice (1) the messages are defined as public methods (2) the chord is expressed in a clear and easy to read fashion. I should mention that one of the approaches I tried relied on thousands of different overloaded delegates; this was made unusable by intellisense’s inability to deal with such large number of overloads, Visual Studio would hang for nearly a minute while generating the intellisense dropdown list.

Before moving to further examples let me list the features of my library:

• Messages accept any number of arguments (within the current implementation limit).
• Chords can contain multiple synchronous messages
• Asynchronous chords can be executed on
  • a new thread
  • the thread of the last incoming message
  • a thread pool
  • a synchronization context
• Synchronous messages support out arguments
• Chords can contain message multipliers
• Chords can be constructed programmatically
• Chords can be constructed and modified at runtime

Design guidelines:

• Join classes must be easy to use
• Chords must be easy to define and read
• Ease of debugging

I will illustrate these features with the following examples.

Synchronous buffer

The synchronous buffer will block on both Put and Get messages, the Put message will block until the Get message is sent, and vice-versa, the Get will block until Put has been called.

    public class SyncBuffer  {

        public void Put(T t) { put.Invoked(t); }
        public T Get() { return get.Invoked(); }

        private Join mJoin = new Join();

        private SyncMethod get;
        private SyncMethod put;

        public SyncBuffer() {
            get = mJoin.NewSyncMethod(Get);
            put = mJoin.NewSyncMethod(Put);

            (get & put).Do((T t) => {
                return t;
            });
        }
    }

This example illustrates the advantage of supporting chords with multiple synchronous messages; implementations without this feature requires an auxiliary asynchronous method to link the two synchronous messages.

Join many

This one turns out to be the simplest non-trivial example, the callers block until n messages have been received:

    public class JoinMany {

        public void Join() { join.Invoked(); }

        private Join mJoin= new Join();

        private SyncMethod join;

        public JoinMany(int n) {
            join = mJoin.NewSyncMethod(Join);

            (n*join).Do(() => { });
        }
    }

Note the n factor in the join definition which defines the multiplicity of the join-many construct.

Wait for many

This one will have a Wait message block until n asynchronous Signal messages have been received.

    public class WaitForMany {

        public void Wait() { wait.Invoked(); }
        public async Signal() { return signal.Invoked(); }

        private Join mJoin = new Join();

        private SyncMethod wait;
        private AsyncMethod signal;

        public WaitForMany(int n) {
            wait = mJoin.NewSyncMethod(Wait);
            signal = mJoin.NewAsyncMethod(Signal);

            (wait & n*signal).Do(() => { });
        }
    }

Note here again the n factor in the join definition.

I think that these examples illustrate beautifully the power of join-calculus. In essentially a single line of code, that is the definition of the chord, we have been able to define these classic concurrency constructs.

I am not claiming here that join-calculus should be used to implement these constructs in the real world. They would be far too inefficient; they are however an illustration of the power of join-calculus. I can see cases where such constructs are required in conjunction with other features in which case join-calculus would be your best option.

In the next post I will go through the other features of my join-calculus library.