Tuesday, 28 October 2008

Multi-set rewrite rules with guards and a parallel execution scheme

Latest news/updates

  • Sat Dec 6 18:34:20 CET 2008:

    • Parallel join pattern with guards and propagation extension built on top of multisetrewrite.
    • Check here here for more information.

  • Wed Nov 12 11:08:47 CET 2008:

    • New multisetrewrite-0.1.1 version uploaded to hackage
    • Includes more examples, a CHRSolver.hs and Join.hs abstraction
      built on top of multi-set rewrite
    • Some fun examples using these abstractions: GossipingGirls and BaggerProblem.

Brief description

We provide a library for multi-set rewrite rules with guards. Rewrite rules are executed concurrently as long as they operate on non-overlapping left-hand sides. We make use of highly-concurrent, non-blocking data structures based on CAS lists. Thus, we can parallelize concurrent rule executions on a multi-core architecture.

The library is similar in style to the below described actor library. The difference is that while actors run concurrently, their receive clauses (sort of multi-set rewrite rules) are only executed sequentially.


The multisetrewrite library is implemented in Haskell and available


(look for the multisetrewrite library among the Concurrency packages)


The library comes with two examples (will hopefully increase over time).

Concurrent stack

The gist of the multi-set rewrite rules describing a concurrent stack (the actual example in Stack.hs is more verbose, after all it's 'only' a library and not
a new compiler).

[push x, pop y] .->. y := x

[push x, stack s] .->. stack (x:s)

[pop y, stack s] `when` (isNotEmptyStack s) .->. let (x:xs) = s
y := x
stack xs

push is synchronous whereas pop and stack are asynchronous. The above shows how to encode join-patterns via multisetrewrite. We are more expressive than join-patterns because we also support guards, non-linear (aka shared) variables (doesn't show up in the above).

CHR solver

On top of multisetrewrite we implement a CHR solver. See CHR.hs in the distribution.
To illustrate the expressive power, we implement the mergesort algorithm
via multi-set rewrite rules.

Here's the gist of the rules (as said above already, the actual implementation is more verbose).

Leq(x,a) \ Leq(x,b) when a < b <==> Leq(a,b)
Merge(n,a), Merge(n,b) when a < b <==> \Leq(a,b),\Merge(n+1,a)

Points to note:

  • The right-hand side of the first rule uses a mix of propagation and simplification. Leq(x,a) is propagated (ie not removed) whereas Leq(x,b) is simplified.
  • We make use of non-linear variables and guards in both rules.

Monday, 20 October 2008

Actors with Multi-Headed Receive Clauses

The actor model provides high-level concurrency abstractions to coordinate simultaneous computations by message passing. Languages implementing the actor model such as Erlang commonly only support single-headed pattern matching over received messages.

Martin Sulzmann, Edmund S. L. Lam, Peter Van Weert:
Actors with Multi-headed Message Receive Patterns.
COORDINATION 2008: 315-330

we propose an extension of the Actor model with receive clauses supporting multi-headed message patterns.

Here's a simple example of a market-place actor

Seller x, Buyer x -> "match found"

We employ the combination of multiple messages in a receive pattern and non-linear patterns to test for a matching seller and a buyer. Non-linear patterns are in fact a short-hand for guards. That is, the above is equivalent to

Seller x, Buyer y when x == y -> "match found"

The formal details of a such an enriched actor model are described in the above mentioned paper. We have also implemented the system as a library extension in Haskell. More on this below.

Haskell-Actor Implementation


Available via


(look for the actor library among the Concurrency packages)


The Haskell-Actor implementation makes use of

  • Haskell channels to represent the actors mailbox, and
  • user-definable pattern matching implemented via type class overloading.

Haskell channels provide the basic abstraction to write (send) and read (receive) from a channel (mailbox). Thus, we can straightforwardly model actors with *single-headed* receive clauses. That is, we read messages one at a time and check for the occurrence of a specific message. The novelty of Haskell-Actor mailboxes is that we can test for the ocurrence of multiple messages via *multi-headed* receive clauses (see the above market-place example).

Messages are user-definable via Haskell data types. The user needs to provide some boiler-plate code (type class instances) to define message pattern matching.


To use Haskell-Actor library you'll need
to understand the following combinators.

  • receive
  • send
  • createActor
  • runActor
  • kill

We'll discuss each of the above in turn.


receive is similar to case statements in Haskell. One difference is that we can match against multiple messages (see the above market-place actor).

Haskell doesn't allow us to overload the pattern matching syntax (it's a library extension). We solve this by providing (generic) primitives to implement multi-headed message pattern matching in receive clauses by providing a (generic) set of primitives which need to be extended by the user for the specific message type (described as a data type).

For example, consider the following simple message type found in the Chain.hs example

data Msg = Blah deriving (Eq,Show)

There are two things, the user needs to provide.

  • Hash-map: Message are indexed based on their constructor names to speed up the search for matching message patterns.

    valhashOp = HashOp { numberOfTables = 1, hashMsg = \ _ -> 1 }

  • Specific pattern matcher:

    instance EMatch Msg where
    match tags m1 m2 = return (m1 == m2, tags)

    We extend the generic matcher by a message specific case.

By providing the hash-map and the message-specific matcher, we can define an actor which waits for the 'Blah' message to arrive and then sends the same message to its neighbor.

actorChain neighbor self =
receive self
[ [Blah] .->. send (toPID neighbor) Blah ]

NOTE: The receive statement is similar to case statements in Haskell. That is, we make explicit the actor/mailbox to which we apply a list of receive clauses. In Erlang, the actor/mailbox is implicit.


Given the pid (process identification number, similar to Erlang) we can send a message to an actor. For example,

send (toPID neighbor) Blah

toPID is a primitive which extracts the pid from the neighbor actor


createActor :: HashOp msg -> IO (Act msg)

creates a new actor for a specific message type, given
a hash-map. For example,

(initialActor :: Act Msg) <- createActor valhashOp


runActor :: Act msg -> (Act msg -> IO ()) -> IO ()

We spawn a new (Haskell) thread in which we apply the first argument (the actor) to the second argument (the behavior). For example,

runActor curr (actorChain prev)

where curr refers to the current actor and prev to the previous actor.


kill :: PID msg -> IO ()

simply kills the thread (we don't kill any sub-actor threads, must be taken care of by the user).


The below examples are part of the distribution.


Creates some n number of actors which pass around some message.


The standard ping-pong actor example. Simply call the main function and see what's happening.


A market-place using server and client actors. Call the main function to invoke the server. To invoke a client open a new terminal and execute 'telnet localhost 4242' for connecting clients to the server. You'll be asked for your name (sent to the server and the server informs everybody about new clients) and what item you'd like to sell or buy. The server then checks for matching buyers and sellers.

This example uses pattern variables and multi-headed pattern receive clauses.
Pattern variable need to be created explicitly because we implement actors
(i.e. pattern matching over messages) as a library.
Here are some code snippets.

; x <- newVar :: IO (VAR String)
; let go =
receive client
[ [arrivedMsg x] .->.
do { v1 <- readVar x
; hPutStrLn hdl ("\n Arrived: " ++ show v1)
; go
, ... ]

We explicitly create a pattern variable x which we then
use in the message pattern 'arrivedMsg x'.

To distinguish between values and variables we use 'lifted' types.

data L a = Val a
| Var (VAR a) deriving Eq
-- see ActorBase.hs for the internal variable representation
-- (only for the curious reader/user)

data MsgClient = Arrived (L String)
-- notifies about newly arrived clients

It's of course pretty clumsy to write down lifted types.
Here's a nicer (type class) interface.

-- client interface
class ArrivedMsg a where
arrivedMsg :: a -> MsgClient

instance ArrivedMsg (VAR String) where
arrivedMsg x = Arrived (Var x)
instance ArrivedMsg String where
arrivedMsg s = Arrived (Val s)

In case of many different types of messages/constructors, this 'boilerplate' code is straightforward but tedious to write down. We should eventually look into Template Haskell (future work).