text:
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.
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.
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)
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.
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.
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.
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.
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.
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).
Solving the Santa Claus Problem with Conjunction
The Santa Claus problem is a concurrency problem that, like the Dining Philosophers problem, can be used to demonstrate your particular concurrency framework of choice. December seems like the right time of year to post a CHP solution that I hacked up at the CPA 2008 conference last year. It's short but rather primitive. Here's the statement of the problem, via Simon Peyton Jones (who made an STM solution in a chapter of Beautiful Code):
Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday). If awakened by a group of elves, he shows each of the group into his study, consults with them on toy R&D and finally shows them each out (allowing them to go back to work). Santa should give priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting.
The particularly tricky aspects of this problem are:
- Santa must make a choice between the reindeer and elves.
- Santa must give priority to the reindeer.
- The elves must come in groups of exactly three, even though there are ten of them.
Choice is easy in CHP, so the first item is not a problem. We saw in the last post how to emulate priority, so we can use that to solve the second point. The third item is difficult. Our barriers require all enrolled participants to synchronise, so we cannot use one barrier for all ten elves. We could introduce some intermediary agents to coordinate the elves, but that is a bit long-winded. Instead we can take a slightly brute-force approach combined with a CHP feature called conjunction.
The principle behind conjunction is straightforward. Usually you offer a choice such as read from channel c or read from channel d: readChannel c <-> readChannel d. This waits for the first of the two events, and executes it (it can never execute both options). A conjunction is when you want to read from channel c and read from channel d: readChannel c <&> readChannel d. Crucially, this will only read from both when both are available. If c is not ready, it will not read from d, and vice versa. It is both or none: an atomic item, if you like. Conjunction also has a list form, every.
One example of where this is useful is the aforementioned Dining Philosophers problem: a philosopher wishing to pick up his forks should execute syncBarrier leftFork <&> syncBarrier rightFork. That way he will either pick up both his forks or neither, thus eliminating the deadlock wherein each philosopher ends up holding one fork.
Conjunction Specifics
It is valid to offer conjunction as part of a choice; for example, (readChannel c <&> readChannel d) <-> readChannel e will wait to read from channels (c AND d) OR e. These choices can be overlapping, e.g. (readChannel c <&> readChannel d) <-> (readChannel d <&>readChannel e) waits for (c AND d) OR (d AND e).
The choices should be in disjunctive normal form (DNF): OR on the outside, AND in the bracket, so c AND (d OR e) is not valid. But AND does distribute over OR here, so this is equivalent to the DNF: (c AND d) or (c AND e). (The operators do not distribute in the opposite direction, so c OR (d AND e) is not equivalent to (c OR d) AND (c OR e), because the latter allows c and e to both happen, whereas the former does not.)
Conjunction and Barriers
Importantly for today's post, there is a correspondence between barriers (N participants, all N must synchronise together) and a conjunction of two-party barriers. Let's imagine for a moment that Santa wanted to meet with all ten of his elves. We could create a single barrier, enroll Santa and the ten elves, and get them all to synchronise on the barrier. The barrier would only complete when all eleven participants synchronised. But alternatively, we could create ten two-party barriers. We would enroll each elf on a different barrier, and enroll Santa on all of them. When they want to meet, the elves would all synchronise on their barrier (meaning their code is unchanged), while Santa would wait for the conjunction of all ten barriers. Each barrier would only complete when all of them complete, because of Santa waiting for the conjunfction of all of them, so we have the same semantics as we had when we had one barrier. These ten barriers would be dynamically fused into one barrier.
The Solution
Santa does not want to wait for all ten elves; he only wants to wait for three. We can implement this with a little brute-force. Labelling the elves A through J, we can make Santa wait for (A AND B AND C) OR (A AND B AND D) OR… (H AND I AND J). That's 120 possibilities. Not scalable, but the problem said ten elves so that's all we have to manage.
Let's finally get to some code. A reindeer waits for a random time, then synchronises on its barrier (i.e. tries to meet with Santa). An elf waits for a random time, then synchronises on its barrier (i.e. tries to meet with Santa). So, perhaps unexpectedly, a reindeer has exactly the same code as an elf. (This is also the case in Peyton Jones' solution). Here it is:
syncDelay :: EnrolledBarrier -> CHP () syncDelay b = forever (randomDelay >> syncBarrier b) where randomDelay = (liftIO $ randomRIO (500000, 1000000)) >>= waitFor reindeer :: EnrolledBarrier -> CHP () reindeer = syncDelay elf :: EnrolledBarrier -> CHP () elf = syncDelay
Our next job is to write the Santa process. Santa will take one barrier for the reindeer, and multiple barriers for the elves (one each). He will loop forever, first polling the reindeer (to give them priority) and otherwise choosing between the reindeer and the elves:
santa :: [EnrolledBarrier] -> EnrolledBarrier -> CHP () santa elfBars reindeerBar = forever (deliverToys </> (skip >> (deliverToys <-> meetThreeElves))) where
Now we need to define the helper processes. Delivering toys is straightforward; we just synchronise with the reindeer. The rest of the code deals with picking all groups of three elves, and making a choice between synchronising with each group:
deliverToys = syncBarrier reindeerBar meetThreeElves = alt [meetGroup g | g <- allGroupsThreeElves] meetGroup bars = every_ [syncBarrier bar | bar <- bars] allGroupsThreeElves = allNFrom 3 elfBars allNFrom n = filter ((== n) . length) . filterM (const [True, False])
The allNFrom is not important here, so I've used a concise (but probably inefficient) definition. Now that we have santa, our elves and our reindeer, all that remains is to put them together. To do this we use two wiring helper functions, enrollAll (that enrolls all of the processes on the given barrier) and enrollOneMany (that enrolls one process on all the barriers, and each of the other processes on one):
main :: IO () main = runCHP_VCRTraceAndPrint $ enrollOneMany (\elfBars -> enrollAll (newBarrierWithLabel "reindeer") (santa elfBars : replicate 9 reindeer) ) [(newBarrierWithLabel ("elf" ++ show n), elf) | n <- [0..9]]
That's it. Part of the reason that this code is quite short is that I've omitted all the print statements detailing what is going on (for example in Peyton Jones' version). These print statements were only there to observe the behaviour of the computation, and we can do that with CHP's built-in traces mechanism, just by using the runCHP_VCRTraceAndPrint function.
View-Centric Reasoning (VCR) traces, developed by Marc L. Smith and subsequently tweaked a little bit by me, display an ordered list of multisets, where each multiset holds independent events (events that did not have a sequential dependency on each other). This style makes it very easy to see from the output that our Santa Claus solution has the right sort of behaviour, viz:
< {elf3, elf4, elf5}, {elf0, elf6, elf7}, {reindeer}, {elf1, elf8, elf9}, {elf2, elf4, elf7}, {elf0, elf1, elf3}, {elf5, elf8, elf9}, {reindeer}, {elf3, elf6, elf7}, {elf0, elf1, elf9}, {elf2, elf4, elf8}, {reindeer}, {elf3, elf5, elf6}, {elf0, elf4, elf9}, {elf1, elf2, elf7}, {elf5, elf6, elf8}, {reindeer}, {elf0, elf1, elf3}, {elf4, elf7, elf9}, {elf2, elf5, elf8}, {elf0, elf1, elf6}, {reindeer}, {elf3, elf7, elf9}, {elf0, elf1, elf4}, {elf2, elf6, elf8}, {elf5, elf7, elf9}, {elf0, elf3, elf4}, {reindeer}, {elf1, elf2, elf6}, {elf5, elf7, elf8}, ...
Concise Solution
For those who like a bit of code golf (finding the shortest version of a program), I came up with this concise version of the whole solution:
import Control.Concurrent.CHP import Control.Concurrent.CHP.Traces import Control.Monad import Control.Monad.Trans import System.Random santa elves reindeer = forever $ syncBarrier reindeer </> (alt $ map (every_ . map syncBarrier) groups) where groups = filter ((== 3) . length) $ filterM (const [True, False]) elves main = runCHP_VCRTraceAndPrint $ enrollOneMany (enrollAll (newBarrierWithLabel "reindeer") . (: replicate 9 syncDelay) . santa) [(newBarrierWithLabel ("elf" ++ show n), syncDelay) | n <- [0..9]] where syncDelay = forever . (randomDelay >>) . syncBarrier randomDelay = (liftIO $ randomRIO (500000, 1000000)) >>= waitFor
Excluding the import statements, that's a solution to the Santa Claus problem in eight lines of Haskell. Rather difficult-to-follow Haskell, but that's usually the result of code golf.
The Problem with Parallel Participants Professing 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.
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:
END :: tick. REPEATABLE :: sendStatus. OPTIONAL :: moveIn; moveOut. EVENT :: END; OPTIONAL; REPEATABLE. EMPTY :: . SEQ :: EVENT ; SEQ EVENT.
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?


text:
Hang out, chat and watch PAX!
You can now filter search results with text. Example: "person: john" will search only person pages for "john".
It's got its share of holdover problems, but Madden NFL 15 at least represents a positive step forward for this series.
They may not make games like this anymore, but maybe they should. Larian's latest CRPG is a deeply satisfying turn-based adventure that rewards players with patience.
Diablo III is a great game that, despite its mouse-and-keyboard roots, adapts to consoles surprisingly well.
Franchise »
Aralbad is home to a cozy spa as well as a drying up lake.
Barrockstadt is the first stop on Kate's adventure and is home to a failing university. Here Kate learns a little bit of background information on the Youkols and how they began to domesticate mammoths.
Komkolzgrad is a nearly deserted Communist era mining facility with two large worker automata that overlook the train tracks.
A terminal where passengers or cargo aboard trains are transferred.
Syberia begins in the fictional French town of Valadilène. Here is where the Voralberg toy factory is located where the famous Voralberg Automatons were manufactured.
This edit will also create new pages on Giant Bomb for:
Until you earn 1000 points all your submissions need to be vetted by other
Giant Bomb users. This process takes no more than a few hours and we'll
send you an email once approved.
Because you're new to wiki editing, we sent your
submission off to our moderators to check it over. Most
changes are approved within a few hours. We'll send an
email when it is.
Once you've earned over points you'll be able
to bypass this step and make live edits to our system.
Until then, gain points by continuing to edit pages.
No changes were submitted, nothing was done! Please make changes to the wiki!
Thanks for continuing to improve the site. Some of your changes are
now live. However, some of your changes were sent to moderation because you do not
have enough points to make those live edits. You need points to
live edit the changes you commited.
For the changes that went through, our robot math gave you points for this
Thanks for continuing to improve the site. Your changes are
now live. Our robot math gave you points for this
Use your keyboard!
Log in to comment

subset: commoncrawl


text:
The Columbus Cottonmouths took on the visiting Louisiana IceGators in a possible playoff preview before a crowd of 1,643 at the Columbus Civic Center Sunday.
In a seesaw battle, the Snakes came from behind twice to post a 5-4 victory in their regular season home finale, snapping a three-game losing streak.
The Gators (69 points) are currently in second place behind only Pensacola (77), which has clinched the regular-season title. Louisiana has a six-point lead over third-place Peoria.
The Snakes (55) are sitting in seventh place in the SPHL standings, six points ahead of the Mississippi Surge and two points behind Knoxville (57).
The Cottonmouths end the regular season on the road next weekend at Biloxi against the Surge and Huntsville against the Havoc. There is no SPHL action on Sunday, so the playoff pairings will be determined late Saturday night.
If the season ended today, the Snakes and Gators would tangle in first-round action. As the higher seed, Louisiana would enjoy home ice advantage, hosting game one, followed by game two in Columbus in the best-of-three series.
In regular-season action, the Snakes are 3-2 against Louisiana, winning once on the road and twice at home. It is a match-up that the players believe is a favorable one.
"I think we match up pretty well," veteran defenseman Tom Maldonado said. "They are a great team, but we've seen them enough to know their tendencies."
Forward Sam Bowles agreed with Maldonado.
"We stack up well against them," Bowles said. "They are a good team but we are more disciplined. The question is who will stay out of the box."
Capitalizing on the IceGators' penalties was a key to the Snakes' victory on Sunday. They scored a whopping four times on the power play and tallied only one even strength goal.
"We went back and forth with the power play," Bowles said. "Both teams capitalized."
Jordan Draper was the offensive star, scoring four goals and adding an assist. Draper and linemate Matt Gingera have a friendly competition going. Gingera, who scored a goal on Sunday, leads the Snakes in scoring with 52 points and Draper is right behind him with 51. Gingera scored a career-high five goals against the Mississippi Surge on Feb. 28.
"Matt asked me after the game: 'You only got four?' ", Draper said. "Everybody came to play tonight. We had a little letdown, but they were tired. They were playing their third in three and had just come from Fayetteville."
The Snakes had to come from behind twice. They fell into an early 2-0 hole, tied it up 2-2, then had to rebound from a 4-2 deficit.
"We had to stick to the game plan," Bowles said. "We found ourselves down 4-2 and had to come back, but we'd already done it once."
The power play was clicking this weekend, as the Snakes scored on seven of their 15 chances.
"We talked a lot about the power play this week," Maldonado said. "One thing lacking was a sense of urgency. We fixed that the last two games."
Louisiana 1 1 2--4
Columbus 0 2 3--5
First period--1, Louisiana, Grant (Braid, McNeil) 9:01 PPG. Penalties--Aide, Columbus (fighting) :02; Barr, Louisiana (fighting) :02; Gray, Columbus (hooking) 7:57; Barr, Louisiana (interference) 9:14; Columbus, bench minor (too many men) 10:17; Brown, Louisiana (slashing) 13:01; Aide, Columbus (fighting) 16:21; Barr, Louisiana (fighting) 16:21.
Second period--2, Louisiana, McNeil (Stuart, K. Byczynski) 2:23 PPG; 3, Columbus, Draper (Gray, Bowles) 5:27 PPG; 4, Columbus, Draper (Gray, Bowles) 5:27 PPG. Penalties--Maldonado, Columbus (interference) 1:25; Arcibal, Columbus (unsportsmanlike conduct) 1:25; Burton, Louisiana (interference) 3:12; K. Byczynski, Louisiana (hooking) 5:01; McNeil, Louisiana (unsportsmanlike conduct) 5:01; Wilson, Louisiana (kneeing) 7:28; Bremner, Columbus (hooking) 10:03; Braid, Louisiana (tripping) 14:55; Shupe, Columbus (slashing) 17:48; K. Byzczynski, Louisiana (interference) 19:20.
Third period--5, Louisiana, Stuart (McNeil, Burton) 2:35; 6, Louisiana, Boyer (unassisted) 3:25; 7, Columbus, Gingera (Draper, Maldonado) 5:51 PPG; 8, Columbus, Draper (Maldonado) 14:05 PPG; 9, Columbus, Draper (Bowles) 14:11.
Shots on goal: Louisiana 7 10 6--23
Columbus 13 19 8--40
Power plays: Columbus 4 of 10; Louisiana 2 of 9.
Goaltenders: Loewen (win) 60:00 23 19 4; Smiley (loss) 18:37 40 35 5.
Referee: MacDougall. Linesmen: Madsen, Rawn.
Time: 2:34.
Attendance: 1,643.


text:
DécorLightingKitchenBed & BathOutdoorHome ImprovementBaby & KidsMore...Sales
free shippingon orders over $49*
Cabot L-Desk with Hutch and Lateral File
5 stars
Delivery was fast and love the table recommend it for home or office use.- Alvin in center
Bridgeport L-Shape Desk Office Suite
5 stars
I have had this desk for a few weeks and it is great. The quality and construction are excellent and looks just like the picture. All the drawers open and close perfectly no problems I am very- teresa in center
ndra,Harmony U-Shape Executive Workstation with Storage Drawers
4 stars
This desk is a great price for the money. As other reviews have stated, assembly is extremely time consuming. It took me the better half of two days to complete it but I was able to do it by myself. I- Amanda in center
Cotati Standard Desk Office Suite
5 stars
Very nice furniture. The top does scratch easily so I ordered a piece of glass to cover the top. Otherwise I really like it.- Michele in center


text:
Kukla's Korner Hockey
Hull On Woods
by Paul on 06/04/08 at 06:21 PM ET
Comments (0)
from the Hockey News,
"It's unfortunate that he would say that, because there's a guy I really admire," Hull told THN.com Wednesday. "I look to him as a Wayne Gretzky type of person that always does the right things and says the right things, not only for his sport but as an ambassador for sport in general.
Woods' insults seemed particularly baffling to Hull given his previous experience meeting the world's No. 1 golfer when Hull was still an active player for the Stars.
Filed in: NHL Talk, | KK Hockey | Permalink
Tags: brett+hull, tiger+woods
Be the first to comment.
Add a Comment
Please limit embedded image or media size to 575 pixels wide.
Add your own avatar by joining Kukla's Korner, or logging in and uploading one in your member control panel.
Captchas bug you? Join KK or log in and you won't have to bother.
Most Recent Blog Posts
What Will The Sharks Dressing Room Be Like?
Joe Sakic On The Retirement Of Jean-Sebastien Giguere
Linda Cohn Files Suit Against Hockey Arena After A Coin Change Machine Fell On Her
Brian Leetch On The New York Rangers
Don Cherry Does The Ice Bucket Challenge
Ryan Suter- Part Owner Of The Madison Capitols
Tim Leiweke Will Leave MLSE By June 30, 2015
Jay Harrison, Tyler Seguin And Joel Ward Talk Analytics
Previewing The Montreal Canadiens
About Kukla's Korner Hockey
Paul Kukla founded Kukla's Korner in 2005 and the site has since become the must-read site on the 'net for all the latest happenings around the NHL.
From breaking news to in-depth stories around the league, KK Hockey is updated with fresh stories all day long and will bring you the latest news as quickly as possible.
Email Paul anytime at email@example.com


text:
Sorry! The position you're looking for is no longer available. Check out other opportunities in Hunt Valley, MD below.
Results 181 — 190
Sort By:
CNC Tech
Aerotek — Ellicott City, MD
CNC Machinists - Manufacturing Description: We are currently hiring CNC Machinists for our clients Machining & Turning Division. Candidates will be responsible for set-up and operation of CNC Mills &…
Application Deadline: Available Year-round
OfficeTeam — Baltimore, MD
Looking for a forward thinking Receptionist/Office Assistant for a career development firm. Will be responsible for greeting clients/visitors, scheduling, answering phones, filing, data entry, reports…
Application Deadline: Available Year-round
Retail Loss Prevention/Security, Full Time: Baltimore, MD - Macy's Security Square
Macy's Retail — Baltimore, MD
Overview: The LP Detectives primary responsibility is to prevent the loss of company property while maintaining a safe business environment. Support stores efforts in providing the best customer serv…
Application Deadline: Available Year-round
Legal Assistant
Robert Half Legal — Baltimore, MD
Downtown law firm is seeking a LEGAL ASSISTANT to join their busy team. Ideal candidate will have a Bachelors degree in addition to prior office/legal experience - minimum of 3 years experience. The c…
Application Deadline: Available Year-round
File Clerk
Robert Half Legal — Baltimore, MD
Law firm in Baltimore City is in need of a file clerk. Must be able to sort files and must know the alphabet. Ideal candidate will have at least 2 years of recent office experience and interest in wor…
Application Deadline: Available Year-round
Executive Assistant for Haitian non-profit
Konbit Mizik Corp. — Virtual
Konbit Mizik Request for Unpaid Internship Konbit - (n. Haitian Creole) The act of the community coming together to achieve a common purpose or goal. Mizik - (n. Haitian Creole) Music. Konbit Mizik is…
Application Deadline: Available Year-round
Public Relations Intern
Fitness Galore — Virtual
Fitness Galore is premiere fitness and nutrition website. An e-zine dedicated to providing practical resources, tools and information to encourage, inspire and motivate people to achieve their goals. …
Application Deadline: Available Year-round
Africa Travel Marketing Firm Internship
Haute Escapes — Virtual
During this placement the hired candidate will support the organization in developing marketing and social media programs for Africa Escapes, a travel marketing company. The company produces marketing…
Application Deadline: Available Year-round
Marketing Intern
Lime Enterprises, LLC — Virtual
Lime enterprises is the worlds largest provider of high-quality furnished and unfurnished accommodations. Lime enterprises has expanded into a multi-faceted business catering to a diversified global m…
Application Deadline: 9/5/2014
fashion and marketing
jewelry manuafacturer — Virtual
Fashion Marketing Internship: Pancis Gems/ Rareset Rainbow the well know jewelry manufacturer, is seeking part-time interns for its marketing/ editorial department. Interns will work with management o…
Application Deadline: Available Year-round


text:
Yasser Arafat poisoning 'a smoking gun'
Professor David Barclay, a British forensic scientist retained by Al Jazeera to interpret the results of the Swiss tests, said the findings from Arafat's body confirmed the earlier results from traces of bodily fluids on his underwear, toothbrush and clothing.
In my opinion, it is absolutely certain that the cause of his illness was polonium poisoning. The levels present in him are sufficient to have caused death.
What we have got is the smoking gun - the thing that caused his illness and was given to him with malice.
Barclay said no one would have thought to look for polonium as a possible poison until the Litvinenko case, which occurred two years after Arafat's death.


text:
seriously look at this awful thing
No no no no no no no.
I'm sorry, if you're too stupid to make eggs in a pan, you don't get to have a horrible egg-dog on a wooden stick like it's some kind of carnival food. This product is a crime against gastronomy, and I want to find and destroy each and every example of it.
Someone needs to .gif the opening "has this ever happened to you?" frames stat.
- time-lordvictorious reblogged this from lulusaurus
- drizzydrakelvr likes this
- seeker-murmuration reblogged this from dynamicwaffles
- telephoneforanaxe reblogged this from dontstepinmypuddle
- attackonmakomori reblogged this from spacestepmom
- professionalsidehoe likes this
- aircalloway likes this
- foreverestel reblogged this from mrs-cucumberbachelor
- tetraodontiforme likes this
- unicorncupcakes4eva likes this
- unicorncupcakes4eva reblogged this from amazingphil
- angelnueva reblogged this from wowwoohoo
- lazy-pencil likes this
- rados130 reblogged this from melodicmane
- rados130 likes this
- decenizas reblogged this from msarano
- chingchingchang reblogged this from annethaisocial
- jinxednep likes this
- gwalnutsq likes this
- that-coolblue likes this
- alysonwright likes this
- twisteddrawings reblogged this from xxkittyy17xx
- twisteddrawings likes this
- cravincali likes this
- heartinspades reblogged this from purpleink9
- purpleink9 reblogged this from looking-glass-and-light
- zenosanalytic likes this
- glitchy-witch likes this
- whatmakesyewhahadotmp3 likes this
- msarano reblogged this from thewispsoftime
- bronzeandsassy reblogged this from wanhunnerpercent
- runthenwalk reblogged this from pottermoreorless
- i-decided-to-join-you reblogged this from hermionesharrypotteressays
- daydreamingexistentialist likes this
- hermionesharrypotteressays reblogged this from pottermoreorless
- dino-mazing reblogged this from pottermoreorless and added:
Not actually. The protein makeup of brownies vs. egg isn't the same. The brownies wouldn't hold together to keep the...
- pottermoreorless reblogged this from thetalkinggrilledcheese
- thetophat reblogged this from balenoj
- icecreamlaboratory likes this
- clinnomaniaa likes this
- urperiwinkle likes this
- musicalstories likes this
- pizzbruh likes this
- uhbsessively likes this
- blaseluxe likes this
- scarless-soul likes this
- insouciancevibes reblogged this from dstroys
- insouciancevibes likes this
- dstroys reblogged this from tinychatting
- balenoj reblogged this from caramel-bunny-bear
- Show more notes