[dmd-concurrency] CSP: Communicating sequential processes

[Robert Jacques]

Communicating sequential processes and pi calculus are one of the other  
major schools of message passing. There's been some interest in it, so I'm  
digging out and summarizing some old notes of mine. I view implementing  
CSP as a good use case for D's message passing architecture; i.e. one  
should be able to write a CSP library and have it compose gracefully with  
other concurrent libraries. Most of the active research in this area is  
being done by the University of Kent  
(http://www.cs.kent.ac.uk/projects/ofa/kroc/).

CSP is built around the concept of a channel; essentially typed,  
half-duplex, synchronous point-to-point single item message passing. This  
is great for a fibers/co-routine based implementation, but bad for the  
cluster/network. The asynchronous channels, would naturally have the  
opposite properties. One of the other design patterns that works well with  
single item channels are generators (or really any fast producer/slow  
consumer problem).

Channel: Several CSP implementations have found it useful to add some  
addition state to a channel and/or have built some higher level primitives  
on-top of them.
-close/poison: closes / shuts down a channel. Very useful for  
producer/consumer processing loops. It may be useful to separate poison  
 from close, i.e chan.poison(exception).
-valid: true if the channel isn't closed/poisoned.
-blackhole: chan.send is a no-op, and chan.receive throws an exception
-broadcast/delta: 1 to N messaging
-N-way: N to N messaging
-Paraplex: Converts N T sends into a T[N] send
-Deparaplex: Converts a T[N] send into N T sends

Select: One of the key flow control primatives in CSP is the  
select/alternative. This really simplifies certain usages and is  
particularly useful in GUIs, i.e. Plan9  
(http://plan9.bell-labs.com/sys/doc/acme.pdf,  
http://plan9.bell-labs.com/sys/doc/81/2.pdf). A select statement waits on  
several guard statements. A guard statement takes either a lazy bool or a  
channel and a function/delegate. The guard it ready if the boolean is true  
or if there is a value waiting in the channel. If multiple guards are  
ready, the select only executes the first one, as determined by the  
scheduler (either round robin or priority)

while(!a_done && !b_done) {
     select(
       guard(chan1,(int v) { writefln("from chan1: ",v);}),
       guard(chan2 ,foo),                                  // ->  
foo(chan2.recv);
       guard(a_done && b_done, { writefln(“We're done”);}),
    );
}

Mobile: Essentially a unique type. It is called mobile based on it's  
usage: it's used for data that moves, i.e. is mobile between processes.

Barrier: A barrier synchronization primitive. I believe something similar  
for threads is already in druntime, though there isn't support for threads  
or network processes as far as I know.
-enroll: enrolls (adds) this process to the barrier
-resign: resigns (removes) this process from the barrier
-sync: blocks until all enrolled processes have called sync

Bucket: A bucket synchronization primitive. Again, a thread-only version  
is in druntime
-fall_into: causes this process to block until the bucket is flushed
-flush: unblocks all processes waiting on the bucket.
-flush(int N): unblock N processes from the bucket

parallel: Run multiple delegates/functions concurrently, with an implicit  
join at the end, e.g.
Channel!(int) c;
parallel( { writefln("Sending a hi-five…"); c = 5; },
           { writefln("Received a ", c());          } );

Sequence/serial: take a bunch of processes and run them sequentially

Skip: A process that terminates immediately or a guard that’s always ready

Stop: A process that does nothing but doesn’t terminate

More Useful links:
http://www.ibm.com/developerworks/java/library/j-csp3.html
http://www.ibm.com/developerworks/java/library/j-jtp11234/
http://www.ibm.com/developerworks/java/library/j-jtp10264/
http://www.cs.kent.ac.uk/projects/ofa/c++csp/

An aside: I ran across CREW (Concurrent read, exclusive write) locks again  
while making this. These have always seemed perfect for D as it has both  
const and shared/synchronized method modifiers. I don't think there's any  
blockers for implementing this, so should I file a bugzilla enhancement  
request, so it gets onto the big long todo list?