www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: DMD 1.022 and 2.005 DCSP solution

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
Oct 07 2007