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.
-
December 6, 2009 at 12:38 pmConcisely Expressing Behaviours with Process Combinators « Communicating Haskell Processes
-
December 21, 2009 at 3:02 pmSticky Platelets in a Pipeline (Part 1) « Communicating Haskell Processes
-
January 19, 2010 at 1:41 pmThe Process Composition Monad « Communicating Haskell Processes
-
March 28, 2010 at 9:40 pmAbstractions for Message-Passing « Communicating Haskell Processes
-
January 10, 2011 at 12:37 pmInterleaving « Communicating Haskell Processes