Home > Uncategorized > The Process Composition Monad

The Process Composition Monad

Process Wiring

Process-oriented programming, as embodied in the CHP library, implements programs as parallel compositions of components. It’s a pleasantly recursive concept; the components themselves are usually parallel compositions of further components. These parallel compositions involve connecting up (or wiring up, to use a more tangible metaphor) the processes so that they can communicate with each other. This can sometimes look a bit spaghetti-like; at worst, it involves declaring all the channels and barriers (effectively naming every wire in the system!) and passing them to the right place, and enrolling on the barriers at the right point. One wrong use of a name (e.g. this recent problem on haskell-cafe, which can all too easily happen) can ruin your program, and the type system can’t protect you if the channels carry the same type.

One way to safe-guard against mis-wiring is to capture common wiring patterns in combinators. Just as you should never write a function that alters every item in a list using explicit recursion (you should use map instead), you should never wire up a pipeline long-hand, and should instead use the connectable combinators. Similarly, there are enrolling helper functions that can ease the use of barriers.

Problems with Combinators

Sometimes the combinators in CHP can remain more awkward than I would like. For example, CHP has an enrollAll function. For this post, I’m going to simplify it to have this type:

enrollAll :: Barrier -> [EnrolledBarrier -> CHP a] -> CHP [a]

It takes a barrier, then enrolls all the processes in the list on the barrier and runs them all in parallel, returning a list of results. Now imagine that you have two barriers (a and b), and a list of processes (ps) of type [EnrolledBarrier -> EnrolledBarrier -> CHP a] and you want to enroll all the processes once on each barrier. It turns out you can’t do this with enrollAll; the function doesn’t compose. So I added enrollAllT:

enrollAllT :: Barrier -> [EnrolledBarrier -> a] -> ([a] -> CHP b) -> CHP b

This function does compose; we can now run our processes using one of these two lines:

enrollAllT a ps (enrollAll b)
enrollAllT a ps (\ps' -> enrollAllT b ps' runParallel)

There are several other functions like enrollAll (such as the function for wiring up a pipeline of processes) that shared the same problem of not allowing repeated composition, and that could have similar changes made to fix it. This seems to be a common pattern (partially compose some processes, then delegate to a further composition function), and so I set about trying to capture it somehow. This being Haskell, it was no great surprise that I ended up with a monad.

The Composed monad

I came up with the Composed monad (in lieu of a better name). Its definition can be written as:

newtype Composed a = Composed { runWith :: forall b. (a -> CHP b) -> CHP b }

I found this slightly confusing at first; I didn’t expect the type a, the return type of the monadic action, to be on the left of the runWith function looking like a parameter. What this type says, though, is that if you give me a Composed a block and a function that can take its return type a and turn it into a CHP action returning type b (i.e. give me: a -> CHP b), I will give back a parcelled up CHP b action, by feeding my return value to the function you give me. The monad instance is as follows:

instance Monad Composed where
  return x = Composed ($ x)
  (>>=) m f = Composed (\r -> m `runWith` ((`runWith` r) . f))

This monad crops up all over the place. It can be written as forall b. ContT b CHP a, the continuation-passing monad transformer on top of CHP. (Dan Piponi has explained why ContT’s cousin Cont has been called the mother of all monads.) Edward Kmett, in turn, labels this the Codensity monad of CHP. (I’m not sure if the continuation-passing monad is usually used how I end up using it here, though.) The monad can be executed with runWith, or with a slightly easier helper function:

run :: Composed [CHP a] -> CHP [a]
run p = p `runWith` runParallel

The Composed monad is also an instance of MonadCHP, meaning you can lift CHP actions into it:

instance MonadCHP Composed where
  liftCHP x = Composed (x >>=)

The Two Styles of Use

I can use this new monad in two different styles. One is to return enrolled items from function calls, using functions such as:

enrollR :: Barrier -> Composed EnrolledBarrier
enrollR b = Composed (enroll b)

(Point-free style is not possible due to the rank-2 type.) You could then write programs such as:

do a <- liftCHP newBarrier
   b <- liftCHP newBarrier
   a0 <- enrollR a
   b0 <- enrollR b
   b1 <- enrollR b
   return [p a0 b0, q b1]

The order in the monad here represents a sort of scoping. When you enroll on the barrier using enrollR, any items later in the monadic “sequence” are within the scope of that enrollment. (After I implemented this, I saw similar code in Maciej Piechotka’s aforementioned haskell-cafe post, so perhaps this is a common way to handle this idiom via a monad.)

That is a fairly simple use of the monad, where the functions return enrolled items and then we wire up. We can also support a slightly different style, with functions such as this:

enrollAllR :: Barrier -> [EnrolledBarrier -> a] -> Composed [a]
enrollAllR b ps = Composed (enrollAllT b ps)

Here, the function does not return a list of enrolled barriers, but instead the list of partially wired up processes (of some type a, which is typically something along the lines of EnrolledBarrier -> Chanout Int -> CHP String, i.e. a CHP process requiring further parameters). So our earlier enrollAllT a ps (enrollAll b) line is written in this monad as:

run (enrollAllR a ps >>= enrollAllR b)

Or, for those who like point-free style:

run (enrollAllR b <=< enrollAllR a $ ps)

Summary

The difference can perhaps best be summarised by showing the types of two versions of enrollR:

enrollR :: Barrier -> Composed EnrolledBarrier
enrollRS :: Barrier -> (EnrolledBarrier -> a) -> Composed a

The first style returns the enrolled barrier to use later on, whereas the latter takes some sort of process and passes the enrolled barrier into it, returning the process, now with one more argument taken care of. I am still exploring which style is best. The first style seems easier for simple functions, but for more complex functions the latter seems more elegant. I also have slight reservations about how easy it will be for users to get their head around the use of this monad, in either style. Comments are welcome.

About these ads
Categories: Uncategorized
  1. No comments yet.
  1. March 28, 2010 at 9:40 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: