Concisely Expressing Behaviours with Process Combinators

The Problem

In recent posts we saw the phased-barrier pattern, wherein simulation entities perform various optional activities until the phase moves on. For example, our graph nodes were willing to send out their position to anyone that attempted to read it, until the phase ended. In a different simulation, space cells might be willing to send out information to anyone that attempted to read it and/or to accept a single new agent into the space and/or to send an agent away, until the phase ends. Programming these sorts of behaviours can become difficult. Let’s begin with coding up a single optional move action before the frame ends (commonly called a tick):

myproc1 = alt [tick, move >> tick]

This begins by offering move or tick; if tick happens we’re done, but if move happens then we wait for tick. Then we can add on repeatedly offering to send out our status:

myproc2 = alt [sendStatus >> myproc, tick, move >> myprocMoved]
  where
    myprocMoved = alt [sendStatus >> myprocMoved, tick]

We need two processes now to represent our two states (the optional move has or has not happened). By the time we change to an optional moveIn and optional moveOut, this approach has become unmanageable:

myproc3 = alt [ sendStatus >> myproc
              , tick
              , moveIn >> myprocMovedIn
              , moveOut >> myprocMovedOut]
  where
    myprocMovedIn = alt [ sendStatus >> myprocMovedIn
                        , tick
                        , moveOut >> myprocMovedInOut]
    myprocMovedOut = alt [ sendStatus >> myprocMovedOut
                         , tick
                         , moveIn >> myprocMovedInOut]
    myprocMovedInOut = alt [sendStatus >> myprocMovedInOut
                           , tick]

There is probably a half-way nice solution involving zippers, but I decided to clean up this mess with a set of process combinators that I have called behaviours. Here is how I express those three pieces of code with behaviours:

myproc1 = offer (once move `alongside` endWhen tick)

myproc2 = offer (repeatedly sendStatus
                 `alongside` once move
                 `alongside` endWhen tick)

myproc3 = offer (repeatedly sendStatus
                 `alongside` once moveIn
                 `alongside` once moveOut
                 `alongside` endWhen tick)

Rather than the combinatorial explosion of states, we now have a nice readable description of the process behaviours that scales up nicely.

Behaviour Combinators

In this section we’ll explore the full-set of combinators, with their types:

offer :: CHPBehaviour a -> CHP a
alongside :: CHPBehaviour a -> CHPBehaviour b -> CHPBehaviour (a, b)
alongside_ :: CHPBehaviour a -> CHPBehaviour b -> CHPBehaviour ()

The offer function executes the given description of behaviours. The alongside_ operator, which is commutative and associative, joins together two behaviours.

Terminal Behaviours

The behaviours can be constructed with two fundamentally different types of behaviour. The first is a terminal behaviour, i.e. one that ends the current set of behaviours. The endWhen combinator returns from the outer call to offer when it happens:

endWhen :: CHP a -> CHPBehaviour a

Multiple endWhen behaviours are allowed in one offer, but only one will ever happen (because the call to offer will return before a second could happen). This gives rise to the law (ignoring return types):

endWhen p `alongside` endWhen q == endWhen (p <-> q)

(This, in combination with the commutativity and associativity of alongside, means that all behaviours with multiple endWhen calls can be reduced to a behaviour with a single endWhen call.)

Repeated Behaviours

The second class of behaviour is the one that offers an event 0 or more times. The once combinator has an upper-limit of one occurrence, which is really a special case of upTo which takes a specified upper bound, and there is also repeatedly which has no upper bound (and offers the event endlessly until an endWhen event happens to end the offer):

once :: CHP a -> CHPBehaviour (Maybe a)
upTo :: Int -> CHP a -> CHPBehaviour [a]
repeatedly :: CHP a -> CHPBehaviour [a]

Repeatedly has a similar law to endWhen:

repeatedly p `alongside` repeatedly q == repeatedly (p <-> q)

(Which again means that any behaviour with multiple repeatedly calls can be reduced to a behaviour with a single repeatedly call.)

All of these combinators assume that you do not need to preserve any state between occurrences of the event. However, particularly for repeatedly, you may need to pass state around, so there is an extra repeatedlyRecurse function:

repeatedlyRecurse :: (a -> CHP (b, a)) -> a -> CHPBehaviour [b]

Here, a is the type of the state, and b is the type of the results. The arguments to this function are arranged in an order that allows you to write:

repeatedlyRecurse (runStateT myStateAction) initialState

Which is useful to run a behaviour in the StateT s CHP monad.

This behaviours feature was added to CHP recently, and will crop up in several future posts. I’m beginning to develop several of these higher levels of abstraction on top of CHP, and I’m interested to see where it can take me. The key thing that enables the process combinators seen here and in the recent post on connecting processes, besides the powerful type system, is the ability to pass processes as arguments to the combinators; both processes that are ready to run (i.e. of type CHP a) and processes that still require some arguments (e.g. of the form a -> b -> CHP c). In Haskell this is as easy as passing around functions is, but in other languages it is either horribly clunky (e.g. C++) or impossible (e.g. occam).

 

---

 
 

Theory — Grammars

I realised when developing this system of behaviours that my combinators looked a little familiar. Users of Parsec may recognise the concepts behind repeatedly and once as being similar to many1 and optional. My library is not a parser, but this similarity suggests that what I am really doing with these combinators is expressing a form of grammar: a grammar on the CSP trace of the program (the list of events that the program performed).

My grammars are a little different to standard grammars in that order barely matters: the only ordering that really matters is that the endWhen events must come last. This is in contrast to most other grammars where order is all-important (e.g. function name then double colon then type). This means that not many grammar systems are suited to expressing my desired grammar, e.g. upTo 10 a `alongside` repeatedly b `alongside` endWhen c describes any sequence that ends in a c, and has as many bs as you like, with at most ten as, which can occur anywhere in that sequence before the c.

If you look at the clunky definitions at the beginning of this post (that did not use behaviours) you can see that this is really a Context-Free Grammar (CFG) version of my required behaviour. Clearly, though, a CFG is not the ideal way to express myself, as it becomes combinatorially larger as you add more options (in contrast to my behaviours, where it just involved adding one item on the end). So I wondered if there was any grammar system that more closely corresponded to my behaviour combinators.

One promising answer to that question seems to be two-level grammars: intuitively, a grammar that generates a grammar (think meta-programming, where you use a program to generate a program). Google does not provide much accessible information on the subject, and the wikipedia page is not too helpful. Thankfully, my university library holds a copy of “Grammars for Programming Languages” by Cleaveland and Uzgalis (1977, Elsevier), which turns out to be a very nice little book on the matter. Based only on a few hours reading the middle of the book, I have had a crack at representing my behaviours with a two-level grammar:

Metaproductions

END :: tick.
REPEATABLE :: sendStatus.
OPTIONAL :: moveIn; moveOut.

EVENT :: END; OPTIONAL; REPEATABLE.
EMPTY :: .
SEQ :: EVENT ; SEQ EVENT.

Hyper-rules

g: g’, END.
g’: EMPTY; SEQ check.

OPTIONAL SEQ check: OPTIONAL symbol, SEQ check, OPTIONAL notin SEQ.
REPEATABLE SEQ check: REPEATABLE symbol, SEQ check.
EVENT check: EVENT symbol.

This may seem long, but the idea is that you only need to change the top three lines of the meta-productions to suit your program; the rest of it is like a set of helper functions (including notin, which is defined in the book, but I’ve omitted the definition here). Adding the upTo combinator should not be too much harder. If anyone reading this is familiar with two-level grammars, I’d appreciate knowing if what I have written above is actually correct! Alternatively, if you know of more suitable ways to express the grammar, please let me know — for example, would attribute grammars be suitable?