Archive
Sticky Platelet Pipeline — Finally Tickless
Tick and Tickless
A little while ago I posted an example of a simulation, with platelets moving down a pipeline together. When platelets bumped into each other, they stayed stuck together forever in a clot, and moved (or stayed put) together. The original code used a tick barrier, as many of my simulation examples do, to keep the simulation in lock-step. An alternative way to keep the simulation in lock-step is to make sure that every process in the pipeline communicates exactly once with its neighbours each timestep, which makes the tick barrier redundant. In this post I will show how to make my previous platelet example tickless, using this alternative method. I will be working in the formal Communicating Sequential Processes algebra, CSP (with a small extension); a Haskell implementation will follow in my next post.
The Ticking Version, in CSPc
We will start by looking at the ticking (original) version of the simulation in CSP. In fact, I will be using CSPc (CSP with conjunction); CSP doesn’t have the idea of conjunction in it, so I am using /\ as an added conjunction operator (akin to the logical conjunction operator) that conjoins two events into a single event that will occur when, and only when, both of its constituent events occur. All of the processes in this post are site processes: they represent a piece of space in the pipeline that does not move, and may or may not be occupied by a single platelet. A site that is occupied by a platelet is said to be full; otherwise it is empty. Let’s begin with the full site process:
FULL(prev, next) = FULL_WILLING(prev, next) |~| FULL_STATIONARY(prev, next)
The full process is making an internal choice between being willing to move this time-step and being stationary for the time-step. The internal choice means that FULL will make the decision itself and no other outside process (collectively referred to in CSP as its environment) can influence the decision. In our original Haskell implementation we made the choice randomly; a site would be stationary in 5% of the time-steps, and willing in the other 95% of time-steps. The stationary process refuses to do anything until the end of the time-step at which point it loops round to become the FULL process again:
FULL_STATIONARY(prev, next) = tick -> FULL(prev, next)
In contrast, the willing process offers two choices. It will move forwards if the process before it in the pipeline signals that is empty, or if the process before it in the pipeline is willing to move too. (So it will move if the process before it is empty, or full and willing, but not if the process before it is full and stationary.) We specify this using our conjunction operator:
FULL_WILLING(prev, next)
= prev.move /\ next.move -> tick -> FULL(prev, next)
[] prev.empty /\ next.move -> tick -> EMPTY(prev, next)
[] tick -> FULL(prev, next)
(/\ binds most tightly above, then ->, and [] binds least tightly.) This model is an accurate rendering of my original CHP program, but it contains a race hazard. It is possible that a site that is willing to move in a time-step does not do so and ticks instead; if all the sites in a clot (a contiguous group of full cells) were willing, they could just tick repeatedly and never move at all. The details of the CHP library’s implementation prevented this occurring in my original CHP program (and hence I did not realise there was a race hazard), but it is a sin to rely on a library’s implementation of synchronisation for your concurrent program to be correct. (If I had been able to model-check this code, I could have discovered this problem; see the summary at the end.) The problem could be removed if we gave priority to the movement event; see the previous discussion of priority on this blog and Gavin Lowe’s paper on implementing priority with a small extension to CSP.
The empty site is as long as the full site, but that is because it is repetitive:
EMPTY(prev, next)
= prev.move -> ((next.empty -> tick -> FULL(prev, next))
[] (tick -> FULL(prev, next)))
[] next.empty -> ((prev.move -> tick -> FULL(prev, next))
[] (tick -> EMPTY(prev, next)))
[] tick -> EMPTY(prev, next)
The empty site is willing to optionally accept a movement from behind it in the pipeline and/or signal to the process ahead of it that it is empty, before ticking. Like the full site, this again has the race hazard that it could tick without accepting the movement of a willing platelet from behind it.
To wire up our pipeline, we start with N EMPTY sites in a row (with the next event of each connected to the prev event of the following process as you would expect) synchronising on the tick event together with a GENERATOR at the beginning, but the END process does not need to synchronise on the tick event — the latter two processes being defined as follows:
GENERATOR(next) = ON(next) ; OFF(next) ; OFF(next) ; GENERATOR(next)
ON(next) = next.move -> tick -> SKIP
[] tick -> SKIP
OFF(next) = tick -> SKIP
END(prev) = prev.move -> END(prev)
The generator sends out a platelet every three steps (and again has the aforementioned problem that EMPTY and FULL have). The END process doesn’t need to synchronise on the tick event because it all it does is synchronise on move as frequently possible; the FULL process already rate-limits itself to one move event per time-step, so this is acceptable behaviour. In this ticking CSP version, we don’t really need this END process at all, but it’s instructive to include it because our tickless version will need one. The CSP up to this point makes up the full model of our original clotting program (minus the wiring, which isn’t very interesting).
The Tickless Version, in CSPc
The design of the tickless version is more complicated than the original version. In a simulation with a tick event, we can use implicit signalling. Each process will offer to perform some actions, then eventually it must agree to synchronise on the tick event (if all the processes didn’t eventually tick, we’d get deadlock!). So you can gain information if you offer a choice of event A with your neighbour, or tick with everyone, and the tick happens. This means that your neighbour did not choose to offer event A to you before it offered tick. We often use this implicit information in the simulation. In the previous platelets code, a full site not willing to move would not offer a movement, and would wait for a tick. A full site willing to move would offer to move with its neighbours, but if tick happened instead, it knew that one of its neighbours was not willing to move, and they had implicitly agreed to stay put by synchronising on tick instead. (The idea is good, but my use of it above led to the problem where willing platelets may not end up moving — this can be solved in the tickless version, though.)
If we want to remove the tick event from our pipeline, we therefore have to add more events between the processes, to allow them to explicitly communicate what they used to implicitly communicate. Peter Welch suggested a possible solution — but he saw that his suggestion had the problem now revealed in the original version, mentioned above. I was able to improve on his idea to remove the problem, and I describe my improvement to his solution here. The tickless version involves introducing two new events (besides move and empty) that indicate further information: canstay and muststay.
If there was only one stay value, then that is all that full stationary sites would offer. But willing full sites would also have to offer to stay, in order to synchronise with stationary neighbours (if one platelet in the clot stays they all must). So all willing sites would offer to stay, and this could allow a clot of willing platelets to agree to stay even though they were all willing to move. This is the same problem as we had in our ticking version. To remove the problem, we differentiate the events offered by a full stationary site (who will offer muststay) and a full willing site (who will offer canstay). Here is how they are used in the new FULL_WILLING process:
FULL_WILLING(prev, next)
= prev.empty /\ next.move -> EMPTY (prev, next)
[] prev.move /\ next.move -> FULL (prev, next)
[] prev.empty /\ next.canstay -> FULL (prev, next)
[] prev.canstay /\ next.canstay -> FULL (prev, next)
[] prev.muststay /\ next.muststay -> FULL (prev, next)
The first two cases are just as before, in the original version. The middle case is for when the process is at the beginning of the clot; it synchronises on empty with the process behind it, and canstay with the process ahead of it in the clot. The last two cases can be thought of as perpetuating the canstay/muststay event through the pipeline.
The new FULL_STATIONARY process is as follows:
FULL_STATIONARY(prev, next)
prev.empty /\ next.muststay -> FULL (prev, next)
[] prev.muststay /\ next.muststay -> FULL (prev, next)
[] prev.canstay /\ next.muststay -> FULL (prev, next)
The first case is for if this process is at the beginning of the clot; it synchronises on empty with the process behind it, and muststay with the process ahead of it. Looking up at the FULL_WILLING process, we can see that any FULL_WILLING process (from the last case) and any FULL_STATIONARY process (from the middle case immediately above) that synchronises on muststay with the process behind it will also synchronise on muststay with the process ahead of it. So if the process at the start of the clot synchronises on muststay, all processes ahead of it in the clot will also synchronise on muststay (by induction).
The third case of the FULL_STATIONARY process indicates that the processes behind the stationary one may offer canstay, and it will then offer muststay to all the processes ahead of it. The canstay event will only be offered from the previous process if it is in the FULL_WILLING state (FULL_STATIONARY only offers muststay to the process ahead of it, and we will see shortly that EMPTY only offers empty to the process ahead of it), which must then synchronise either on canstay with the process behind that (which, again, must be a FULL_WILLING process) or empty (which means it’s the start of the clot). All the full processes after FULL_STATIONARY, following the logic in the previous paragraph, will synchronise on muststay regardless of their state.
The new EMPTY process is as follows:
EMPTY(prev, next) = prev.empty /\ next.empty -> EMPTY (prev, next) [] prev.muststay /\ next.empty -> EMPTY (prev, next) [] prev.move /\ next.empty -> FULL (prev, next)
All cases offer the empty event to the process ahead of it. It will accept from behind: the empty case (when the previous site is empty), the move case (when the previous site is full and able to move forward) and the muststay event (when the previous site is part of a clot that cannot move). It does not accept the canstay event, which is crucial, for reasons explained in the next section.
The new ON, OFF and END processes are:
ON(next) = next.move -> SKIP [] next.canstay -> SKIP OFF(next) = next.empty -> SKIP END(prev) = prev.empty -> END(prev) [] prev.muststay -> END(prev) [] prev.move -> END(prev)
You can think of as ON as being the “forward half” of a FULL_WILLING site that is receiving empty from behind it; similarly, OFF is the forward half of an EMPTY site and END is the “backward half” of an EMPTY site.
Proofs
Since conjunction is an extra feature in CSP, there is no direct model-checking support for it. (We have designed a mapping from CSPc to CSP, but that causes a state space explosion and does not yet have automated tool support.) I will offer instead, inductive proofs about clots. By proving a statement for the beginning site, and optional middle/end sites based on the neighbour behind them, this should inductively cover all non-empty clots. This can be done by considering the pairings of prev and next events, to see when offering a set of events from the previous site, what might be offered to its next neighbour.
So, let us consider a clot of willing platelets. The site at the beginning of the clot can only synchronise on prev.empty (as that is all the empty site before it will offer). Therefore the site at the beginning of a clot will only offer move or canstay to the next site. Any middle site that synchronises on move or canstay with the previous site will offer the same thing to the next site. So inductively the last site of the clot will only offer move or canstay. We can see that the empty site following the clot will only accept move, not canstay, so a clot of willing processes may only move and may not stay put. This solves the problem that we had with the ticking version, and is why the EMPTY process does not offer to synchronise on canstay. (This result also shows that any line of sites at the beginning of a clot will only offer move or canstay to the sites ahead of it.)
Now let us consider a clot with one or more stationary platelets somewhere along its length (but not the beginning). We have seen in the previous paragraph that the willing sites at the beginning of the pipeline will offer move or canstay to the first stationary site in the clot. This stationary site appearing after these willing sites will only accept canstay, and will then offer muststay ahead of it. We can see that all full sites, stationary and willing, will only synchronise on prev.muststay with next.muststay, so regardless of the stationary/willing state of sites ahead of the first stationary site, muststay will be the event offered at the end of the clot. The empty site will accept this, and so a clot with one or more stationary sites after the beginning will all agree to stay. If a stationary site is at the beginning, it will synchronise on prev.empty and next.muststay, and then the rest of the clot will also synchronise on muststay, so again the clot will stay put. Thus any clot with one or more stationary sites will stay put.
Summary
So we have a system, expressed in a few lines of CSPc, of a sticky platelet simulation without a tick event. I will show a translation to CHP in the next post, which works the same as the original version (minus the potential problem). This work is interesting from a formal perspective because we have no direct support to model check this CSP, due to the conjunction extension. We have devised a mapping from CSPc to CSP, but it generates a large number of events; I believe it would be in the order of 4^N for this problem. We don’t have a tool to generate the CSP just yet, and even if we could, I suspect the model checker may choke on that size of problem. However, by taking advantage of conceptual features of the simulation, namely clots, I was able to perform some inductive reasoning about the problem. The reasoning was aided by the neat symmetry of the problem; each site in the pipeline offered a pair of (prev, next) events in conjunction, which could be thought as a sort of normal form.
From a practical perspective, it can be seen that this is not really a very concurrent simulation. The chained conjunction along the pipeline means that all processes must resolve their actions for the time-step together, and really the power of the simulation is in the resolution of all the choices (which could be written as a single sequential/functional piece of code: transforming the list of all platelets at time-step T to the list of all platelets at time-step T+1), not in the concurrency of the sites. The advantage of the way we constructed our solution is that we have encoded the behaviour of each site by only referring to the two neighbours of a site. These are local rules, that when resolved for all sites, produce the emergent behaviour of sticky platelets bumping, forming clots, and advancing down the pipeline together. There is no global visibility of the system in our code (only in the run-time system) to complicate things. This investigation of emergent behaviour is part of the ongoing CoSMoS research project that uses process-oriented technologies to produce this kind of simulation, and which builds on the original work of the TUNA project from which this blood clotting example is taken.
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.
Darcs
This post is tangentially related to CHP.
Version control is a key tool when programming. Recently, much work has gone into distributed version control systems (DVCS) that dispense with the requirement to have a single central repository, and allow a distributed, loosely-connected network of repositories. There are many DVCS systems out there, but I use darcs (which happens to be written in Haskell) whenever I can. All my Haskell code lives in darcs repositories, and this post is intended to detail a little of how I use it.
Darcs and CHP
Here is the structure of my darcs repositories for CHP across my three development machines (no prizes for guessing my machine naming scheme) for the past few weeks:
Each box is a repository, with the thin arrow-less lines indicating the directory structure. The empty-headed arrows indicate the ways in which patches are pushed and pulled (they are pushed in the direction of the arrow, and pulled in the opposite direction). The directions of the horizontal arrows are far from arbitrary; while both my laptop and university machine can SSH into my home machine (middle), neither of the outer two can be contacted via SSH. Hence they also cannot push and pull directly between each other.
I have about ten repositories in that diagram, which is probably typical for CHP. I tend not to do much work in the top three (the main repositories on each machine, akin to trunks), they are mainly pass-through repositories as I shift patches around. All the work is done in the lower repositories (branches, if you like), which may exist on several of the machines (e.g. the split repository for the recent 2.0 split) and have patches passed between them regularly, or may exist only on one machine. I am usually logged in to two of the machines at once, so that I can push my patches across and test them on several different GHC versions (until last week, all three machines had distinct versions of GHC: 6.8, 6.10, 6.12).
For my other major Haskell project, Tock (which I will also make a post about soon), I could make a similar diagram, but extended on to it are the repositories of the maintainer, Adam. He accepts my emailed patches into one repository to examine them, then he pushes to his main repository, and then later on pushes the patches to the webserver. So my working copy can be about seven repositories away from the publicly visible “trunk”, but it’s absolutely painless for both of us. There is a limit on how many branches is sensible of course, but darcs makes branching so easy that the branch of a branch is no trouble, even when that might make you uneasy in older version control systems.
I should probably make the CHP repository available on a webserver somewhere — please say if that’s something you’d be interested in. But such a public repository is unlikely to be much more up to date than the latest release. This is a combination of keeping my work in branches, and of my fairly regular release policy. You can see from the above diagram that I don’t necessarily release from the top middle repository (which is the closest I have to a “trunk”), although generally all the changes do eventually reach that repository.
Branch and Merge: Hunky
Darcs has easy branching and merging (especially compared to VCS systems like Subversion). One use I often make of branching is to get a clean copy of the repository. darcs get . foo will create a clean copy in the foo directory — i.e. a copy without any unrecorded changes. This is useful, for example, when you discover a bug and want to know if it was there before you made your current changes.
Darcs record has a particularly useful hunk-oriented interface. It interactively shows you all the changes you’ve made, and you can pick which ones you want to form a part of the current commit. This nicely reflects the fact that just because you made two changes to the same file, it doesn’t mean they have to end up in the same commit: for example, they may be fixing different bugs, but you happened to notice the presence of one while fixing another. So you can fix them both, then record them separately. This page shows an example. And I gather that hunk-splitting (which would make them even better) is coming in the next major release.
Other uses for Darcs
It’s not just Haskell code — in fact, even my home directory is a darcs repository (with my settings files recorded in it):
neil@beast ~: darcs show files . ./.nanorc ./.hscolour ./.bash_everywhere ./.emacs ./.ssh ./.ssh/config
That way, when I get access to a new machine, I just darcs get from my home machine and I have the settings for my favourite editors and for bash (once I source that bash file in my .bashrc on the local machine). It’s an amazingly useful idea (thanks to Adam Sampson), and it means that if I modify any settings on any machine, I can record a patch and push it to my main home machine, then pull it onto all the other machines at a later date. So all my editor macros and so on can be easily kept up to date on all my machines, and I can rollback any change I make later on, if needed.
Summary and Donations
I imagine many Haskell programmers are already using darcs, and are aware of its usefulness. The Darcs team are currently running a bit of a fund-raising drive. If you use darcs as much as I do, perhaps you can consider donating a little by way of thanks. If you’re not a darcs and/or DVCS user, hopefully this post shows why it’s useful.
Splitting CHP
Riddle Me This
Q: When is a library not a library?
A: When it’s two, or three.
The CHP library has been growing progressively larger, and I have noticed something about a lot of the recent additions: several of them are entire modules that import Control.Concurrent.CHP. That is, they are extensions that build upon the existing library without requiring any access to the internal details of the library, and without being used or exported by the core of the library. This means that there is now a significant chunk of the library that I can safely break off and make its own library, titled chp-plus, that depends on the public interface of the chp library.
The Split
At first, I was resistant to the idea of splitting. I think it is more appealing to new users to have everything in one library rather than split between two; the latter suggests unwanted complexity. However, it is perhaps nice to have a smaller core library to offer, with further capabilities set aside — this was something that came up when comparing CHP to CML. The split delineates the core basic API (channels, barriers, enrollment and parallel) from the more sophisticated constructs that can sit on top of these (connectable, behaviours, and so on). The split also makes maintenance a little easier, by reducing the amount of functionality in the core library, and means that the core should develop slowly while the chp-plus package will likely develop more quickly. It also allows me to trim down the set of dependencies of the core library; CHP no longer depends on QuickCheck, for example (chp-plus does instead).
I decided to go ahead and make the split. I have taken the opportunity to remove the deprecated BroadcastChannels module, and the Utils module — the latter having been generalised and superseded by the Connect module. I have bumped up the chp version number to 2.0.0 as part of the change, and have released chp-plus 1.0.0 (as usual, all this is on hackage and can be installed using cabal). I suspect that chp-plus will fast outpace chp; aside from anything else, chp-plus can add new features without affecting chp, but any major changes to chp would probably require a chp-plus change too. For users, there should be little change required. Where previously you put “chp” in your build-depends field in cabal, you should now put “chp == 2.*, chp-plus == 1.*” or similar. You will need to transition from using the Utils module to Connect — most of the old operators are now encompassed in the new single <=> operator. Put a comment below if have any troubles.
The Third Package
Alongside these two packages, I’ve also split off a very small piece of functionality that has always been out of place in the CHP library. The LoopWhileT monad transformer adds simple easy looping support on top of an existing monad. You can place your whiles at the beginning of a block (generally known as a while loop), at the end (generally known as a do-while loop) and anywhere in the middle, including multiple times (generally known as do-while-do, and sadly lacking in almost all imperative languages). Each time a while is reached, the test is made, and if it fails the loop is broken, otherwise execution continues around the loop. This is all packaged up and documented in the loop-while package on Hackage if you’re interested in it, and is totally stand-alone. CHP now depends on it, mainly in order to provide a useful MonadCHP instance, but with cabal install this shouldn’t be a problem. I don’t expect loop-while to change much so you should only need to install it once and not worry about it.
Summary
CHP has now become two packages, chp-2.0.0 and chp-plus-1.0.0, with a side release of loop-while-1.0.0. I realise this will be slightly irksome for the existing users of the library to switch, but I hope that in the long run the split makes things easier for everyone. Not much code has been changed, only the library organisation, so the main thing you will need to adjust is your build system — and any use of the Utils module. I’ve also fixed some problems involving GHC 6.12, by using the deepseq library instead of parallel (as, confusingly, I only needed deepseq in CHP — for the strict send commands) because the release of parallel-2.x confused things a bit. This may cause problems if you are still using GHC 6.8, but I think it may be time that I stopped worrying about supporting GHC 6.8. If you have any troubles installing on GHC 6.10 or 6.12, just let me know.
CHP vs CML, Forking and Picky Receivers
CHP is a Haskell library that implements message-passing concurrency — and so is CML, a Haskell implementation of the concurrency features of Concurrent ML. Recently, someone asked on reddit what the differences are between the CHP and CML libraries. So in this post, I will perform a comparison by going through the API of the CML Haskell package and seeing how to implement the same functionality in CHP.
CML Events in CHP
CML is organised around Event types. An Event represents a sort of future synchronisation, that can be engaged in using the function sync :: Event a -> IO a. CHP doesn’t have this distinction as such; all events are monadic actions, and you engage in them when you execute them in the CHP monad. So in effect, anything of type Event a in CML is just CHP a in CHP. CML has a choose :: [Event a] -> Event a function for choosing between such events, which is identical to CHP’s function alt :: [CHP a] -> CHP a.
CML has a wrap :: Event a -> (a -> IO b) -> Event b function that allows you to specify a post-synchronisation operation. Given that we have already seen that the Event type is the CHP monad and that we would execute the operation in the CHP monad rather than IO, this operation in CHP would be something like wrapCHP :: CHP a -> (a -> CHP b) -> CHP b. I’m sure many Haskell programmers will recognise this as the type of monadic bind (>>=), and indeed monadic bind has the same semantics of wrap; it can choose and synchronise on the left-hand event, then later execute the right-hand operation with the result.
CML has a guard :: IO (Event a) -> Event a event for specifying a pre-synchronisation operation that is run every time a synchronisation is attempted on the given event. I have not come across this particular feature before, but it would be interesting to see how to achieve a similar effect in CHP if anyone has a use case for the guard function. CML also has a wrapabort :: IO () -> Event a -> Event a that allows you to specify an action to execute if the event is not chosen. Like guard, I am not sure what I might use this function for. It would be relatively easy to wrap up an alt to execute abort actions for non-chosen guards, though.
Forking
CML has a “fork and forget” spawning operator, spawn :: IO () -> IO ThreadId, that is really a synonym for forkIO. There are philosophical issues here. Fork and forget, which is present in many concurrency frameworks, can be very useful to set off processes that you just want to set going and not interact with, or to launch daemon processes that should run for the program’s lifetime. One problem with it is that the semantics are not always immediately clear — to what extent are the processes forgotten? For example, what do you think the output of this program will be?
import Control.Concurrent main = forkIO (threadDelay 1000 >> putStrLn "Hello World?")
The question is: will the Haskell program wait for all the forked processes to finish before the main program finishes, i.e. will the text be printed? The answer seems to be: no; on my GHC 6.10.3 system, if I compile the above with -threaded and run it, there is no output, even if I take the delay down to zero. So if you want to wait for a particular forked process to complete before your program ends, you’ll need to add mechanisms to do so yourself. Or rather: when your main program finishes, you had better be sure that all the forked processes have finished, or that you are sure that you don’t care if they are still running.
To help with such issues, CHP offers runParallel, which we’ve seen a lot, but also something that I call scoped forking. There are two basic operations in scoped forking, centred around a monad transformer called ForkingT. (You can use ForkingT on any monad that is a member of the MonadCHP type-class, i.e. that has CHP at the bottom. The most obvious thing is to have the ForkingT CHP monad, but you can also have ForkingT (StateT Int CHP) or similar.) You fork off a process within this transformer using fork :: MonadCHP m => CHP () -> ForkingT m (). This forks off the first parameter, and is an action in the ForkingT transformed monad. You initiate one of these blocks using forking :: MonadCHP m => ForkingT m a -> m a. The important thing is that when the ForkingT block (the first parameter) finishes its own execution, the call to forking does not return until every forked process has also finished. So you can fork off as many processes as you like in the forking block, but at the end, you must wait for them all to finish.
So between runParallel and forking (the only mechanisms for running processes concurrently in CHP), there is always a defined, clear point in your program at which you will wait for any concurrent sub-processes to terminate. When your outer-most runCHP call finishes, it is not possible for these to still be any CHP processes running, so there is no confusion or race hazards involving termination semantics as there is with fork-and-forget functions such as forkIO.
Channels
Back to CML — the last item to cover is channels. CML has a type Channel a. It’s not clear from the documentation whether these channels support multiple readers and/or multiple writers, but let’s assume for simplicity that they don’t, and thus that this is the same as CHP’s OneToOneChannel a. There is a channel :: IO (Channel a) function for creating channels which is the same as CHP’s oneToOneChannel :: CHP (OneToOneChannel a). There is also a function to write to a channel, transmit :: Channel a -> a -> Event (), which is the same as CHP’s writeChannel :: Chanout a -> a -> CHP () except that CHP has the concept of channel-ends which CML does not. CHP uses channel-ends to make it clear that when a process is passed a Chanout end, it will be writing to that end of the channel, and cannot read from it. In this way, the directionality of the channels becomes apparent in the types, and there is some static guarantee of the patterns of usage of channels.
CML’s operation for reading from a channel is more interesting: receive :: Channel a -> (a -> Bool) -> Event a. The second parameter is a function that allows you to decide whether you want to engage in reading from the channel, based on the value being offered. Interestingly, the CSP calculus contains this feature, but it is not something I have added to CHP. I believe Erlang effectively also offers something like this (by pattern-matching on messages in a process’s message queue). I can see uses for this, and in CHP you would have to implement something like this by sending values on different channels, and choosing based on the channel the value was being communicated on rather than the value itself. I should perhaps add this to CHP in future, but for now this is a useful CML feature that CHP does not support. Without this aspect, receive is equivalent to CHP’s readChannel :: Chanin a -> CHP a.
Conclusions
The main difference between the features of CML and CHP are that CML is a nice small library, and CHP is a larger library with many more features (barriers, clocks, conjunction, parallel operators, poison, more channel types, traces, and the new higher-level features like the connectable type-class and behaviours). I think CHP subsumes CML for the features I want, but obviously I’m very biased. CML does have the benefit of operating in the IO monad, which can be more convenient than CHP’s eponymous monad. The reason for having the CHP monad is to support poison (more cleanly than using exceptions) and tracing, two features not present in CML.
In terms of the implementation, CHP uses STM and has a lot of logic to support some of the extra features (especially conjunction), but only uses as many threads as you would expect (one per thread of execution). CML uses MVars and has relatively simple algorithms, although they do spawn a lot of threads — from what I can understand of skimming the code, choose spawns off a new thread for every possibility being offered. The transactional events library does something similar. In contrast, CHP spawns off no threads for an alt call, and just performs one (potentially expensive) memory transaction then blocks until it is woken up by another thread offering to synchronise with it. That said, I expect CML may be faster than CHP for common cases.
Differences aside, CML and CHP are similar in their approach to concurrency (I can’t remember if CML was influenced by the CSP calculus, but it certainly has a similar approach to concurrency), so many of the design patterns should transfer between the two libraries — especially if CML’s developers were to add barriers in a future version.
Sticky Platelets in a Pipeline (Part 2)
In my last post I showed the infrastructure and logic of a simple simulation of some sticky blood platelets moving through a blood vessel. I added the video to the end of that post; in this post I will explain how the visualisation was implemented.
In most CHP simulations there is a barrier (typically named tick) that is used to keep all the simulation entities synchronised, so that they all proceed through the discrete time-steps together. When it comes to visualising simulations, we could add a separate channel through which to report the status of all the simulation entities to a central drawing process, but this feels like a waste when all the processes are already synchronising together. CHP has reduce channels (many-to-one) that are the opposite of (one-to-many) broadcast channels; in a reduce channel, all the writers send in their data to a single reader, and all must send together before the communication is complete. So a simple way to achieve visualisation is to transform the tick barrier into a reduce channel, which has the same synchronisation behaviour, but that also allows data to be sent to some drawing process.
The simulation entities don’t need to know the details of all this, so we hide it using a send action that I’ve called a tick action:
type TickAction = SendAction (Maybe (Platelet, Bool)) data Platelet = Platelet GLfloat
Note that I’ve also had to tweak the type in the platelet from last time to make working with the OpenGL library a bit easier. The only change to the site process (and plateletGenerator and plateletPrinter processes) is related to the change in the tick event to being an action. Here is the site process in full:
site :: Chanin (Maybe Platelet) -> Chanout (Maybe Platelet)
-> TickAction -> CHP ()
site prevIn nextOut act = foreverFeed (maybe empty full) Nothing
where
tickWith = sendAction act
empty = join . fst <$> offer
( (once $ readChannel prevIn)
`alongside` (once $ writeChannel nextOut Nothing)
`alongside` (endWhen $ tickWith Nothing)
)
full platelet
= do r <- liftIO $ randomRIO (0, (1::Double))
let moving = r >= 0.05
tick = tickWith (Just (platelet, moving))
mv = readChannel prevIn <&> writeChannel nextOut (Just platelet)
probablyMove = if moving then fst <$> mv else stop
fromMaybe (Just platelet) . fst <$>
offer ((once probablyMove) `alongside` endWhen tick)
Synchronising on the tick barrier has become engaging in the tick event, where we must pass in that optional pair Maybe (Platelet, Bool); the first item is the platelet currently occupying the site, and the boolean indicates whether the platelet was willing to move on this time-step. If the site is empty, the Nothing value is sent.
The status values end up passed to the draw function, which is fairly boring (it draws a vertical bar) — we are only interested in its type:
data ScreenLocation = ScreenLocation Int deriving (Eq, Ord) draw :: ScreenLocation -> Maybe (Platelet, Bool) -> IO ()
This is called from the drawProcess:
drawProcess :: ReduceChanin (Map.Map ScreenLocation (Maybe (Platelet, Bool)))
-> CHP ()
drawProcess input
= do displayIO <- embedCHP_ $
do x <- readChannel input
liftIO $ do startFrame
mapM_ (uncurry draw) (Map.toList x)
endFrame
...
Note that drawProcess takes the input end of a reduce channel which carries a map from ScreenLocation (a one-dimensional location in our simple example) to the Maybe (Platelet, Bool) values we saw. Reduce channels in CHP must carry a monoid type, because the monoid instance is used to join all the many values from the writers into a single value (using mappend/mconcat, but in a non-deterministic order — so make sure the monoid is commutative).
The Map type (from Data.Map) is a monoid that has union as its mappend operation. This is exactly what we want; each site process will send in a singleton Map with their specific screen location mapped to their current status, and using the monoid instance these maps will all be joined (quite safely, since each sender will have a different location, and hence a distinct key entry in its Map) into one big map, that can then be fed into the draw function as we saw above.
We don’t trouble the site process with knowing its location; instead, we wrap up the location in the send action. It is easy to construct send actions that apply a function to a value before it is sent, so we apply a function that takes a status value, and turns it into the singleton Map just discussed. This is all done as part of the wiring up of the process network, based on the version from last time:
main :: IO ()
main = runCHP_ $
do status <- manyToOneChannel
pipelineConnectCompleteT
(enrollAll (return $ writer status) . zipWith withSend locationList)
plateletGenerator (replicate numSites site) plateletPrinter
<|*|> drawProcess (reader status)
where
numSites = screenSize - 2
locationList = map ScreenLocation [0..(screenSize-1)]
withSend k p c = p $ makeSendAction' c (Map.singleton k)
The withSend function does the wrapping of the modification function with the send action. Each site is given a location from the list, including the generator and printer processes; otherwise this function is the same as the version from part 1.
I’ve omitted the OpenGL code, which is much the same as my previous examples. But here, again, is the video showing the results of the visualisation:
Choose from WMV format (suitable for Windows) or MPEG format (suitable for Linux, etc).
Turning the tick barrier into a reduce channel is often an easy way to visualise a simulation, and doesn’t require too much change to the code. As I said last time, the video is nothing compared to the TUNA videos which are very impressive, and some of which were generated by distributing the code over a cluster — a topic I hope to come to in CHP at some point in the future.
Sticky Platelets in a Pipeline (Part 1)
This post brings together concepts from several recent posts, including behaviours, conjunction and channel wiring. It is based on the work in the completed TUNA project, which has some stunning videos of blood clotting (and some images if you prefer):
I’m going to cut down the TUNA example greatly, to blog-post size. What we are going to be simulating is sticky objects in a pipeline, for example sticky blood platelets moving through a blood vessel. Our platelets will be represented as data that is passed between active “site” processes; our blood vessel will be a one-dimensional pipeline of site processes. Each process will be connected to its neighbours with a channel that can pass platelets. All the processes will be enrolled on the tick barrier, as is customary in CHP simulations.
We’ll begin the code with a helper function (one that I would like to see in the standard library) that iterates forever with a state value being passed through, and our platelet data type:
foreverFeed :: Monad m => (a -> m a) -> a -> m b foreverFeed f x = f x >>= foreverFeed f data Platelet = Platelet Float
The data in the platelet type is a colour value that I will use for visualisation in the next part of this guide. This is set randomly by the platelet generator at the beginning of the pipeline:
plateletGenerator :: Chanout (Maybe Platelet)
-> EnrolledBarrier
-> CHP ()
plateletGenerator out tick = forever $ on >> off >> off
where
on = do platelet <- Just . Platelet <$> liftIO (randomRIO (0, 0.5))
offerAll [ once (writeChannel out platelet)
, endWhen (syncBarrier tick) ]
off = offerAll [once (writeChannel out Nothing), endWhen (syncBarrier tick)]
The pipeline generates platelets regularly, one every three time-steps (this is coded as the simple on-off-off sequence). When it is performing an “on” time-step, it generates a platelet with a random shade, then uses behaviours to offer to once send the platelet until tick happens (i.e. the frame is over). The next site in the pipeline may not take the new platelet if the site is full and not moving this time-step, so the platelet may get discarded in that case. In the off state, the generator waits for the tick to end the frame, but also offers to tell the site ahead of it that the generator is empty (signified by sending Nothing rather than Just a platelet).
The main logic is in the site process, which also has two states, empty and full:
site :: Chanin (Maybe Platelet)
-> Chanout (Maybe Platelet)
-> EnrolledBarrier
-> CHP ()
site prevIn nextOut tick = foreverFeed (maybe empty full) Nothing
where
empty :: CHP (Maybe Platelet)
full :: Platelet -> CHP (Maybe Platelet)
Each time, if there is Just a platelet returned by the function, the next state will be full, otherwise it will be empty. The initial state is empty (the Nothing value). The empty state consists of three possible behaviours:
empty = join . fst <$> offer
( (once $ readChannel prevIn)
`alongside` (once $ writeChannel nextOut Nothing)
`alongside` (endWhen $ syncBarrier tick)
)
In an empty state, a site will read in a new platelet from the previous site in the pipeline (if available), it will offer to communicate to the next site in the pipeline that it is empty, and it will finish this behaviour when the tick event happens. The value returned is the result of reading from the channel, which will be Nothing if no read occurred or if we read in a Nothing value (and hence the site remains empty) or Just the result of the read if it did happen and was a platelet (in which case the site will become full). It is possible to reduce the amount of communications happening with empty processes, but I want to keep this example simple if I can.
The full state is as follows:
full platelet
= do r <- liftIO $ randomRIO (0, (1::Double))
let
move = readChannel prevIn <&> writeChannel nextOut (Just platelet)
probablyMove = if r < 0.05 then stop else fst <$> move
fromMaybe (Just platelet) . fst <$>
(offer $
once probablyMove
`alongside` endWhen (syncBarrier tick)
)
We will pick this code apart, bit by bit. It is primarily an offer between the tick to end the frame and another behaviour, called probablyMove. When the site is full, it has a 5% chance of refusing to do anything, meaning that a single platelet will not move in 5% of time-steps. So it starts by generating a random number between 0 and 1. If this is under 0.05 (i.e. a 5% chance), the probablyMove behaviour is stop, meaning it will not move — the site will just wait for the end of the frame in these 5% of cases.
In the other 95% of the time-steps, a move is offered, using conjunction. The site offers to read a value from the previous channel (which may be Just a platelet, or a Nothing value signifying the site was empty) and send on its current platelet, shuffling the platelets along the pipeline. So its overall behaviour is that it will send on its current platelet, if and only if: the previous site is empty, or the previous site is full and willing to send its platelet on (it won’t be willing 5% of the time). So a platelet can only move if there is no-one behind it, or if the platelet behind it moves too.
The implications of this behaviour are that once platelets are in adjoining cells, they only move on together. Thus any platelets that bump together form a notional clot that stays together forever after. This clot is not explicitly programmed and has no representation in the program. It is emergent behaviour that arises out of the local rules of the site process; each site only communicates with the site either side of it, and yet the program logic means that clots that are tens of platelets long could form, and would be unbreakable.
The other neat thing that arises out of the logic comes from the 5% chance. In 5% of time-steps a platelet will not move. (This is what allows the platelets to bump together in the first place.) Since a clot can only move when all its platelets move, a two-platelet clot has a roughly 10% chance of not moving (really: 1 – 0.95^2), and a three-platelet clot has about a 14% chance of not moving (1 – 0.95^3). So big clots will move slower, which means that the platelets behind become more likely to join on. Despite only having a local probability of not moving, we get the behaviour that larger clots are less likely to be able to move.
Enough on the site process; at the end of the pipeline is a platelet printer, that swallows up any platelets and prints out how large each clot was that reached the end of the pipeline:
plateletPrinter :: Chanin (Maybe Platelet) -> EnrolledBarrier -> CHP ()
plateletPrinter input tick
= foreverFeed plateletPrinter' []
where
plateletPrinter' ps
= do mp <- join . fst <$> offer (once (readChannel input)
`alongside` endWhen (syncBarrier tick))
let ps' = ps ++ [mp]
(test, text) = maybe (isNothing, "Blank")
(const (isJust, "Clot"))
(head ps')
(chunk, rest) = span test ps'
if null chunk || null rest
then return ps'
else do let status = text ++ ", size: " ++ show (length chunk)
liftIO $ putStrLn status
return rest
And finally we must wire up all of this. Thankfully, our new connectable helper functions make this quite easy, and short:
main :: IO ()
main = runCHP_ $
pipelineConnectCompleteT (enrollAll newBarrier)
plateletGenerator (replicate numSites site) plateletPrinter
where
numSites = 100
If we compile and run this program, we get a print-out of clot sizes:
Blank, size: 103 Clot, size: 1 Blank, size: 51 Clot, size: 4 Blank, size: 2 Clot, size: 1
That is terribly unexciting, so I’m going to give a sneak video preview of a visualisation that I will go through in my next post. The 1D pipeline of sites is visualised left-to-right, with each tall bar being a platelet (or black for empty). When the bar flashes white, this is in the 5% of cases where the platelet is refusing to move. Hence you can see that when the larger clots form, the white flashes of the various platelets prevent the clot from moving:
Choose from WMV format (suitable for Windows) or MPEG format (suitable for Linux, etc).
The Problem with Parallel Participants Professing Priority
Priority
There are two kinds of priority in the CHP style of concurrent programming: priority on processes and priority on events. Priority on processes is about specifying that a high-priority process P should run whenever possible, at the expense of a low-priority process Q. This is difficult to co-ordinate across multiple cores (especially if lightweight threads are used, as in Haskell) and isn’t offered by all run-times. The priority I am interested in discussing in this post is that of events: specifying that if two events A and B are ready to complete, A should happen in preference to B.
There is an immediate problem with local priorities over events, where each process separately specifies its priorities to the events it is offering. Imagine that you offer to either go to the cinema, or go bowling, and you prefer (i.e. give priority to) the cinema. Your friend also offers to go to the cinema or to go bowling, but they prefer (give priority to) bowling. For a one-off choice of doing one thing, there is no amount of algorithmic cleverness that can resolve such situations to the satisfaction of both parties. So local priorities,where both sides can specify their own priorities, are fairly meaningless because in general they cannot be resolved correctly.
One way to solve this is to only allow one side to specify a priority. The occam language did this; only processes reading from channels were allowed to specify priority, not the writers. (In fact, only processes reading from channels were allowed to offer a choice!) This means that the priorities can always be satisfied because you only have one set of priorities to resolve in each choice. This falls down with barriers — it becomes difficult to specify which synchronising process of many is allowed to offer priorities.
Another solution is to have global priorities instead. If we specify up-front that the cinema is always better than bowling, there can be no dispute when we make our offers for activities for the evening. This could be implemented, for example, by assigning a global integer priority to all events (perhaps with 0 as the default). I gather that global priorities make things difficult for formal reasoning in CSP, but that does not mean we cannot use it.
CHP and Prioritised Choice
So what does CHP do? Events do not currently have global priority (although I would like to implement it at some point). There is an unprioritised choice operator, <-> (with a list form: alt), which is commutative and associative. But there is also a prioritised choice operator, </> (with a list form: priAlt), which is associative but not, of course, commutative. Its existence is partly a historical hangover from the first version of CHP (which was a more direct conversion from occam), and it has some slightly intricate semantics, which I’ll describe here in terms of the list form.
The relative positions in the list of any guards involving reading from channels, writing to channels, or synchronising on barriers are discounted. So priAlt [readChannel c, syncBarrier b] is the same as priAlt [syncBarrier b, readChannel c]. The position of any stop guards is irrelevant because they will never trigger. The position of any skip guards is important in relation to all the other guards. priAlt (skip : others) is guaranteed to choose the first guard, regardless of what comes after. Similarly, priAlt (initialGuards ++ [skip] ++ otherGuards) will never choose any of the otherGuards, but if any of the initialGuards are ready, they will be chosen in preference to the skip. Effectively, skip is like an early terminator for the list of guards passed to priAlt (but don’t go overboard — I don’t think passing an infinite list of guards will work, even if skip is early on). In contrast, the presence of skip guards in an unprioritised choice is generally wrong; the outcome of alt [readChannel c, skip] is non-deterministic, even if c is ready.
Polling
Generally in my examples on the blog, I have always avoided the use of priAlt and </> in favour of alt and <-> because the former is only really different to the latter when skip guards are present, and thus the latter form, being more clearly an unprioritised choice, is better. There is one, slightly inelegant, use for prioritised choice though: polling. Imagine that you want to poll to see if a channel is ready. If it is, you are happy to read from it, but if it’s not ready yet, you want to continue on and do something else. That is easy to capture: readChannel c </> skip. In fact, it is possible to capture this as a helper function:
poll :: CHP a -> CHP (Maybe a) poll c = (Just <$> c) </> (skip >> return Nothing)
You can even nest these things; this code will check channels c and d for readiness (if both are ready, either might be taken), and return Nothing only if neither is ready:
poll (alt [readChannel c, readChannel d])
It is also important to be aware that this polling is only a snapshot of the current state. If you poll channel c, you have no guarantee that the result of the poll will still hold by the time you get the result. So if you poll channel c, and find it is not ready, it may have turned ready by the time you examine the result and make a subsequent decision. A particularly bad use would be to have both ends polling: if one process continually polls to read from c, and the other process continually polls to write to c, depending on timing, it is quite possible that no communication will ever take place. It is only really a good idea to use polling if you know the other end will stay committed to the action once offered (i.e. that it is not offering a choice of events).
Emulating Priority
This pattern can also be used to give one event a form of priority over another. This code:
readChannel c </> (skip >> alt [readChannel c, readChannel d])
First checks to see if c was ready. If so, it takes it, otherwise it waits for the next event of c and d. So it gives a form of priority to c. This is not foolproof priority; if another process later offers c and d there is no guarantee that c will be chosen, so it only provides real priority if different processes are offering the events involved.
Concisely Expressing Behaviours with Process Combinators
The Problem
In recent posts we saw the phased-barrier pattern, wherein simulation entities perform various optional activities until the phase moves on. For example, our graph nodes were willing to send out their position to anyone that attempted to read it, until the phase ended. In a different simulation, space cells might be willing to send out information to anyone that attempted to read it and/or to accept a single new agent into the space and/or to send an agent away, until the phase ends. Programming these sorts of behaviours can become difficult. Let’s begin with coding up a single optional move action before the frame ends (commonly called a tick):
myproc1 = alt [tick, move >> tick]
This begins by offering move or tick; if tick happens we’re done, but if move happens then we wait for tick. Then we can add on repeatedly offering to send out our status:
myproc2 = alt [sendStatus >> myproc, tick, move >> myprocMoved]
where
myprocMoved = alt [sendStatus >> myprocMoved, tick]
We need two processes now to represent our two states (the optional move has or has not happened). By the time we change to an optional moveIn and optional moveOut, this approach has become unmanageable:
myproc3 = alt [ sendStatus >> myproc
, tick
, moveIn >> myprocMovedIn
, moveOut >> myprocMovedOut]
where
myprocMovedIn = alt [ sendStatus >> myprocMovedIn
, tick
, moveOut >> myprocMovedInOut]
myprocMovedOut = alt [ sendStatus >> myprocMovedOut
, tick
, moveIn >> myprocMovedInOut]
myprocMovedInOut = alt [sendStatus >> myprocMovedInOut
, tick]
There is probably a half-way nice solution involving zippers, but I decided to clean up this mess with a set of process combinators that I have called behaviours. Here is how I express those three pieces of code with behaviours:
myproc1 = offer (once move `alongside` endWhen tick)
myproc2 = offer (repeatedly sendStatus
`alongside` once move
`alongside` endWhen tick)
myproc3 = offer (repeatedly sendStatus
`alongside` once moveIn
`alongside` once moveOut
`alongside` endWhen tick)
Rather than the combinatorial explosion of states, we now have a nice readable description of the process behaviours that scales up nicely.
Behaviour Combinators
In this section we’ll explore the full-set of combinators, with their types:
offer :: CHPBehaviour a -> CHP a alongside :: CHPBehaviour a -> CHPBehaviour b -> CHPBehaviour (a, b) alongside_ :: CHPBehaviour a -> CHPBehaviour b -> CHPBehaviour ()
The offer function executes the given description of behaviours. The alongside_ operator, which is commutative and associative, joins together two behaviours.
Terminal Behaviours
The behaviours can be constructed with two fundamentally different types of behaviour. The first is a terminal behaviour, i.e. one that ends the current set of behaviours. The endWhen combinator returns from the outer call to offer when it happens:
endWhen :: CHP a -> CHPBehaviour a
Multiple endWhen behaviours are allowed in one offer, but only one will ever happen (because the call to offer will return before a second could happen). This gives rise to the law (ignoring return types):
endWhen p `alongside` endWhen q == endWhen (p <-> q)
(This, in combination with the commutativity and associativity of alongside, means that all behaviours with multiple endWhen calls can be reduced to a behaviour with a single endWhen call.)
Repeated Behaviours
The second class of behaviour is the one that offers an event 0 or more times. The once combinator has an upper-limit of one occurrence, which is really a special case of upTo which takes a specified upper bound, and there is also repeatedly which has no upper bound (and offers the event endlessly until an endWhen event happens to end the offer):
once :: CHP a -> CHPBehaviour (Maybe a) upTo :: Int -> CHP a -> CHPBehaviour [a] repeatedly :: CHP a -> CHPBehaviour [a]
Repeatedly has a similar law to endWhen:
repeatedly p `alongside` repeatedly q == repeatedly (p <-> q)
(Which again means that any behaviour with multiple repeatedly calls can be reduced to a behaviour with a single repeatedly call.)
All of these combinators assume that you do not need to preserve any state between occurrences of the event. However, particularly for repeatedly, you may need to pass state around, so there is an extra repeatedlyRecurse function:
repeatedlyRecurse :: (a -> CHP (b, a)) -> a -> CHPBehaviour [b]
Here, a is the type of the state, and b is the type of the results. The arguments to this function are arranged in an order that allows you to write:
repeatedlyRecurse (runStateT myStateAction) initialState
Which is useful to run a behaviour in the StateT s CHP monad.
This behaviours feature was added to CHP recently, and will crop up in several future posts. I’m beginning to develop several of these higher levels of abstraction on top of CHP, and I’m interested to see where it can take me. The key thing that enables the process combinators seen here and in the recent post on connecting processes, besides the powerful type system, is the ability to pass processes as arguments to the combinators; both processes that are ready to run (i.e. of type CHP a) and processes that still require some arguments (e.g. of the form a -> b -> CHP c). In Haskell this is as easy as passing around functions is, but in other languages it is either horribly clunky (e.g. C++) or impossible (e.g. occam).
Theory — Grammars
I realised when developing this system of behaviours that my combinators looked a little familiar. Users of Parsec may recognise the concepts behind repeatedly and once as being similar to many1 and optional. My library is not a parser, but this similarity suggests that what I am really doing with these combinators is expressing a form of grammar: a grammar on the CSP trace of the program (the list of events that the program performed).
My grammars are a little different to standard grammars in that order barely matters: the only ordering that really matters is that the endWhen events must come last. This is in contrast to most other grammars where order is all-important (e.g. function name then double colon then type). This means that not many grammar systems are suited to expressing my desired grammar, e.g. upTo 10 a `alongside` repeatedly b `alongside` endWhen c describes any sequence that ends in a c, and has as many bs as you like, with at most ten as, which can occur anywhere in that sequence before the c.
If you look at the clunky definitions at the beginning of this post (that did not use behaviours) you can see that this is really a Context-Free Grammar (CFG) version of my required behaviour. Clearly, though, a CFG is not the ideal way to express myself, as it becomes combinatorially larger as you add more options (in contrast to my behaviours, where it just involved adding one item on the end). So I wondered if there was any grammar system that more closely corresponded to my behaviour combinators.
One promising answer to that question seems to be two-level grammars: intuitively, a grammar that generates a grammar (think meta-programming, where you use a program to generate a program). Google does not provide much accessible information on the subject, and the wikipedia page is not too helpful. Thankfully, my university library holds a copy of “Grammars for Programming Languages” by Cleaveland and Uzgalis (1977, Elsevier), which turns out to be a very nice little book on the matter. Based only on a few hours reading the middle of the book, I have had a crack at representing my behaviours with a two-level grammar:
Metaproductions
END :: tick. REPEATABLE :: sendStatus. OPTIONAL :: moveIn; moveOut. EVENT :: END; OPTIONAL; REPEATABLE. EMPTY :: . SEQ :: EVENT ; SEQ EVENT.
Hyper-rules
g: g’, END. g’: EMPTY; SEQ check. OPTIONAL SEQ check: OPTIONAL symbol, SEQ check, OPTIONAL notin SEQ. REPEATABLE SEQ check: REPEATABLE symbol, SEQ check. EVENT check: EVENT symbol.
This may seem long, but the idea is that you only need to change the top three lines of the meta-productions to suit your program; the rest of it is like a set of helper functions (including notin, which is defined in the book, but I’ve omitted the definition here). Adding the upTo combinator should not be too much harder. If anyone reading this is familiar with two-level grammars, I’d appreciate knowing if what I have written above is actually correct! Alternatively, if you know of more suitable ways to express the grammar, please let me know — for example, would attribute grammars be suitable?
