Automated Wiring of Message-Passing Processes

A CHP program consists of many concurrent processes, wired together. They can be wired together with channels of any type (here, colour indicates the type the channel carries) that may be connected in one direction or the other:

They can also be joined with non-phased barriers (which come in one colour, black):

 

Connection Example 1

Now consider this pair of processes, p that requires an incoming purple channel and outgoing red channel, and q that requires an incoming red channel and outgoing green channel:

It is incredibly obvious what is needed to wire them up: a red channel from p to q. Once the two processes are connected in this way, they will become a new process, r, that requires an incoming purple channel (which will be passed to p) and an outgoing green channel (which will be passed to q):

 

Connection Example 2

It remains obvious even for this slightly more complicated example, where p requires an incoming purple channel and a pair (outgoing red channel, incoming blue channel), and q requires a pair (incoming red channel, outgoing blue channel) and a pair (outgoing green channel, incoming beige channel):

Their composition into r is:

 

Connection Example 3

Finally, there is an example where p takes one argument — a pair (outgoing red channel, enrolled barrier) — and q takes two arguments — a pair (incoming red channel, enrolled barrier), and an Int:

They compose into a process that only requires one argument, the Int:

 
 

Connectable Operators

It is child’s play to work out how to connect the processes — and the user code should be just as easy. I recently added the Connectable type-class to CHP to facilitate this kind of simple wiring. I’ll come to the implementation, but first here are the examples again, along with the code to wire them up (the type for r can be inferred from the type of p and q, but I give all the types anyway):

p :: Chanin Purple -> Chanout Red -> CHP ()
q :: Chanin Red -> Chanout Green -> CHP ()
r :: Chanin Purple -> Chanout Green -> CHP ()
r = p <=> q

 
 

p :: Chanin Purple -> (Chanout Red, Chanin Blue) -> CHP ()
q :: (Chanin Red, Chanout Blue) -> (Chanout Green, Chanin Beige) -> CHP ()
r :: Chanin Purple -> (Chanout Green, Chanin Beige) -> CHP ()
r = p <=> q

 
 

p :: (Chanout Red, EnrolledBarrier) -> CHP ()
q :: (Chanin Red, EnrolledBarrier) -> Int -> CHP ()
r :: Int -> CHP ()
r = p |<=> q

Note that the <=> operator is for when both processes take two parameters, and there are slight variants for other situations; for example, |<=> for when the left-hand side only takes one parameter (the bar indicates that this could be at the left-hand end of a pipeline of such processes).

Connectable Implementation

The implementation is simple enough that I will show it here. We have our Connectable type-class:

class Connectable l r where
  connect :: ((l, r) -> CHP a) -> CHP a

Given a CHP process requiring the two things connected, it will connect them for the duration of the process and run it. So we have simple instances for channels and barriers:

instance Connectable (Chanout a) (Chanin a) where
  connect p = newChannelWR >>= p
instance Connectable (Chanin a) (Chanout a) where
  connect p = newChannelRW >>= p
instance Connectable EnrolledBarrier EnrolledBarrier where
  connect p = do b <- newBarrier
                 enroll b $ \b0 -> enroll b $ \b1 -> p (b0, b1)

Then the real power comes from the instances for pairs, triples and so on:

instance (Connectable al ar, Connectable bl br) =>
    Connectable (al, bl) (ar, br) where
  connect p = connect (\(ax, ay) -> connect (\(bx, by) ->
                p ((ax, bx), (ay, by))))

This instance means that any two corresponding pairs of connectable things are also connectable. This means that we can define our useful process composition operator and use it everywhere on all sorts of types:

(<=>) :: Connectable l r =>
          (a -> l -> CHP ()) -> (r -> b -> CHP ()) -> a -> b -> CHP ()
(<=>) p q x y = p x |<=>| flip q y

(|<=>|) :: Connectable l r => (l -> CHP ()) -> (r -> CHP ()) -> CHP ()
(|<=>|) p q = connect (\(x, y) -> p x <|*|> q y)

Now that we have this notion of connectable things, we can define further functions to connect a list of processes in a pipeline and so on (these are provided for you in CHP). My favourite function, which is required very often if you build 2D simulations, is the wrappedGrid operator, forthcoming in CHP 1.8.0. Given a data-type to represent 4-way connectivity:

data FourWay above below left right
  = FourWay { above :: above, below :: below, left :: left, right :: right }

And provided above can connect to below, and left to right, we can wire up a list of lists of processes (i.e. a 2D grid in waiting) into a torus, that is a grid where the top edge connects to the bottom edge and the left edge to the right edge (as is often the case in old arcade games):

wrappedGrid :: (Connectable above below, Connectable left right) =>
  [[FourWay above below left right -> CHP a]] -> CHP [[a]]

The implementation is a little fiddly — but I can define it once in the CHP library, and you can use it with whatever channels and barriers you use to connect up your four-way wrapped-round 2D grid. I’m also going to define a similar operator for 8-way connectivity. By capturing the notion of two things being connectable, we are able to build operators and helper functions for such common topologies without caring whether the individual components are connected by channels of Ints, Strings, MyCustomDataType or by barriers.

About these ads