Archive

Posts Tagged ‘connectable’

Sticky Platelets in a Pipeline (Part 1)

December 21, 2009 2 comments

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).

Automated Wiring of Message-Passing Processes

December 2, 2009 5 comments

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

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

 

Connection Example 1

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

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

 

Connection Example 2

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

Their composition into r is:

 

Connection Example 3

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

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

 
 

Connectable Operators

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

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

 
 

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

 
 

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

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

Connectable Implementation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Categories: Uncategorized Tags:
Follow

Get every new post delivered to your Inbox.