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

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

receive
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

receive
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



Download



Available via

http://hackage.haskell.org

(look for the actor library among the Concurrency packages)

Overview



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.


Details



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



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.

send



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




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




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




kill :: PID msg -> IO ()


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

Examples



The below examples are part of the distribution.

Chain.hs



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


PingPong.hs



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

MarketPlace.hs



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