• Mikola Lysenko (47/51) Oct 07 2007 Well, here's how you would do a bounded buffer in DCSP (D Communicating ...

Mikola Lysenko <mclysenk mtu.edu> writes:

David Brown Wrote:

 I'll give an inverse challenge (which I'm going to try and meet, see
 below): Implement a standard threading problem, such as bounded buffers
 using only the Phobos thread primitives.  The solution may not use anything
 outside of std.thread for synchronization.

Well, here's how you would do a bounded buffer in DCSP (D Communicating
Sequential Processes):


void boundedBuffer(T, int B)
(
	WriteChannel!(T) get,
	ReadChannel!(T) put,
	lazy bool done
)
{
	size_t pos = 0;
	T[] buffer = new T[B];

	while(!done())
	{
		alternative(
			guard(pos > 0 && get.write(buffer[pos-1]), { pos--; }),
			guard(pos < B && put.read(buffer[pos]), { pos++; }),
			done()
		);
	}
}


Which you could then use in the following way:



auto get = new Channel!(int);
auto put = new Channel!(int);

bool done = false;

parallel(
boundedBuffer!(int, 10)(get, put, done),
{
	for(int i=0; i<100; i++)
	{
		put.write(i);
		writefln("writing %s", i);
	}
},
{
	for(int i=0; i<100; i++)
	{
		int x;
		get.read(x);
		writefln("reading %s", x);
	}

	done = true;
});

A few quick notes about DCSP:  First, it is not anywhere near a finished
product, which means that it would be ill advised to consider using it for
anything practical.  Next, it is inspired largely by process calculi which use
point-to-point channels for communication.  That means that processes block on
both reads and writes on when they communicate.

The alternative statement in this code is also a bit tricky.  It basically
forces the code to wait until one of the guarded conditions is true.  After
which, it executes the code in the body of the condition.  Guarded conditions
can be boolean expressions, channel read/writes, or barrier synchronization. 
Only one guarded condition is carried out per alt block.  If no condition is
satisfied, the process waits.

There are several theoretical advantages to this approach, most notably it
makes it possible to use certain results from type theory to prove the
properties about some concurrent programs at compile time.  (such as deadlock
freedom, assured progress etc.)  Essentially these features would be embedded
into the types of various items within the library when you write, and then
checked by the template processor, though more work is still needed before
these capabilities can be realized.

Ultimately more work will be needed to get something practical working, but
process calculi form an interesting direction for future concurrent programming
languages.

-Mik