Choose Anything: adding an Alternative instance

The alt function in CHP allows you to make a choice between performing several actions. You can choose, for example, between reading on one channel and writing on another. Agents can choose to move left or right, buffers can choose between reading or writing, servers can choose between reading from several clients. The alt function takes blocks of code and chooses between the leading actions — some people find this slightly surprising, but I think it simplifies code, and it is also entirely in line with the original CSP calculus.

The Problem with alt

The alt function has always had a slight ugliness though. Some leading actions do not support choice, for example: parallel compositions, lifted IO actions, or channel creation. That is, what should something like this code do:

alt [newChannel, liftIO (putStrLn 6), writeChannel c 6 <||> writeChannel d 7]

My solution to dealing with the items that didn’t support choice was to issue a run-time error if you tried to include them in a choice (as above). I don’t like run-time errors caused by bad code — but in this instance I couldn’t use the type system to pick up the error at compile-time without making all CHP code a lot more verbose. It’s always irked me to have this possibility of a run-time error.

One related feature is that the skip process is somewhat magic. The skip process has type CHP () and does nothing. It’s very tempting to define skip = return (). But SKIP has another property in CHP: it’s always ready in a choice. Choosing between a return statement (on its own), e.g. alt [return (), writeChannel c 0], would trigger a run-time error, so skip had to be defined differently. (Note that choosing alt [skip, return 0 >>= writeChannel c] is fine; CHP obeys the monad laws, so the leading action of the second item is actually writeChannel — the return melts away when it has an action following it.)

There is one easy solution to getting rid of the run-time error in alt: make choosing between any CHP action valid. All the existing choice-supporting actions work as before. But all of the others: creating channels, enrolling, parallel compositions, poisoning, claiming shared channels, lifted IO actions and solitary return statements (and probably more I’ve forgotten) are now valid in a choice, and are considered always-ready. In CSP terms, they are all prefixed by the process SKIP. This change has been included in CHP 2.2.0.

This doesn’t break any existing CHP code, it just makes more code technically valid (and simplifies some of the implementation a little). Now skip is simply defined as return (), and is not at all special. A little while back I explained the poll function, which I wrote at the time as:

poll :: CHP a -> CHP (Maybe a)
poll c = (Just <$> c) </> (skip >> return Nothing)

This can now be written even more straightforwardly:

poll :: CHP a -> CHP (Maybe a)
poll c = (Just <$> c) </> (return Nothing)

Alternative

Since I wrote the first version of CHP I’ve come into contact with a lot more Haskell — including type-classes such as Applicative and Alternative. Alternative defines a choice operator, <|> and some associated items: empty, the unit of choice, and the functions some and many that optionally produce 0+ or 1+ items respectively. The default definition of many is revealing:

many v = some v <|> pure []

This suggests several things. Firstly, a right-biased choice operator is going to be pretty useless here. It’s not clear whether Alternative instances should display left-bias or no bias (the documentation only states that it should be associative, which all biases would satisfy), but left-bias looks most useful, and is probably most expected. Secondly, it is expected than an item constructed with pure should be a valid choice: this wasn’t the case previously (pure = return, of course), but it is with the changes described above.

Our instance is trivially constructed (and is included in CHP 2.2.0 onwards):

instance Alternative CHP where
  empty = stop
  (<|>) = (</>)

It seems silly not to provide it. This does leave me with three choice operators in CHP: “<->“, “</>” and “<|>“, which all do exactly the same thing — my original intention in providing the first two was that the first wasn’t guaranteed to have bias, but the middle one was guaranteed to have some bias — they actually share the same definition, though. If I was designing CHP all over again I might dump both my choice operators and just use Alternative. That would break pretty much all existing CHP code, though, so it’s too big a change to do suddenly. I may deprecate my choice operators in favour of Alternative though, and maybe remove them in the future.

Our earlier poll operation is actually already featured in the Control.Applicative module, based on the Alternative type-class, and is called optional. As a final note, I went looking for an equivalent to CHP’s alt/priAlt for Alternative. It turns out to be the asum function from Data.Foldable (thanks, Hoogle!):

asum = foldr (<|>) empty

I might stick with the alt/priAlt synonyms for that one though, for clarity (and stop for empty, too, due to its CSP origin). Besides which, asum is defined in terms of <|> — in fact, in CHP the operator </> is defined in terms of priAlt rather than the other way around, because priAlt is more efficient when you have lots of guards.