Actor versus Join Concurrency

This post tries to shed some light on the differences and commonalities between actor and join style concurrency and explains its connection to multi-set rewrite rules.

Recently, I've published two libraries supporting

• Actor concurrency, see here, and
  
• Join concurrency, see here
  

Coordination via multi-set rewrite rules with guards

Both libraries support similar forms of coordination primitives in terms of multi-set rewrite rules with guards. For example, consider

Seller x, Buyer x --> "do something"

which says that if there's a seller and a buyer where both agree on the object x to be sold, then we execute the right-hand side "do something".

What's the connection to rewrite rules? Well, in case there's "Seller Obj" and "Buyer Obj", both will be rewritten to "do something". It's natural to view sellers and buyers as resources. To rewrite multiple resources, we simply use multi-set rewrite rules. For example,

A, A --> "blah"

will remove two occurences of "A" by "blah".

Lesson learned so far. The basic coordination primitives behind actor and join style concurrency are expressed in terms of multi-set rewrite rules. In the join setting, these multi-set rewrite rules are commonly referred to as join-patterns. However, please take note that Erlang-style actors only support single-headed rewrite rules and join-style concurrency as found in JoCaml, Polyphonic C or Claudio Russo's Joins librariy does not support guards (both features are supported by the above mentioned libaries).

Assuming we agree on a common set of multi-set rewrite rules (possibly with guards), what's the difference then between actor and join concurrency?

Actor concurrency

In the actor setting, we commonly assume that multi-set rewrite are applied sequentially. In the special case of Erlang's single-headed rewrite rules, we start scanning the mailbox (that's the place where sellers, buyers etc are stored) from left to right. For each mailbox element (often referred to as message aka method or even constraint in the rewrite setting), we then try the single-headed rewrite rules from top to bottom, until a match is found. In the general case of multi-set (headed) rewrite rules, we can assume that things can get a bit more tricky. Check out the paper below for a formal sequential execution semantics

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

But if rewrite rules are executed sequentially where does concurrency come in? Well, we can have concurrent actors which communicate by sending each other messages (aka methods or constraints). The messages itself are processed and executed sequentially by each actor. You may therefore argue that the behavior of each actor is completely deterministic.

Join concurrency

In the join setting, the place where methods (aka messages or constraints) are kept is commonly referred to as a "store". Any multi-set rewrite rule can fire as soon as we find a match for its left-hand side among the st of stored methods. The only condition is that if two rewrite rules fire concurrently, they must operate on non-overlapping parts.

Summary

Both styles of concurrency use the same coordination primitive, i.e. multi-set rewrite rules. I'd argue that actor and join concurrency serve different purposes (hence, are equally useful). One can emulate the other but I prefer to have efficient support for both of them (not via emulation).

NOTE: I wrote this post are seeing these comments on reddit.com:

• Actor model concurrency for Haskell
  
• Multi-set rewrite rules with guards and a parallel execution scheme
  

So, having a blog is possibly useful after all :)

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