The Actors Model and Haskell

September 8, 2007

Recently I have been playing around with Scala, and in particular, the Actors library. This encouraged me read the paper ‘Actors: A Model Of Concurrent Computation In Distributed Systems’ written by Gul A Agha. This paper enabled to me to start thinking of Actors in more general terms, rather than as a Scala library. To refine this knowledge I decided to experiment by implementing basic Actor functionality in Haskell.

Looking at the source of the Scala Actors library had discouraged me from this task, as it uses a lot Scala’s Object Orientated features to maintain an Actor’s state. There was one paragraph in Agha’s paper that stood out for me however:

Actors are computational agents which map each incoming communication to a 3-tuple consisting of:

  • a finite set of communications sent to other actors;
  • a new behaviour (which will govern the response to the next communication processed); and
  • a finite set of new actors created.

This paragraph suggests to me that Actors are no more than a function of type (in psuedo Haskell)

Communication -> ([Communication],Actor,[Actor])

It is not necessary to store state, as once the actor has processed the current communication it is replaced by a returned behaviour. This enabled me to see past the implementation details of the Scala library and focus on Actor concepts instead.

A second important point I took away from Agha’s paper was that Actor’s are a computation process that enables parallelism, but does not require it. A corollary of this is that implementations of the Actor model may use whatever threading model they deem appropriate. Scala developers have actually developed thread and event based version of actors, as well as allowing those two methods to be combined (there are many resources here). In my implementation I will take advantage of these loose requirements and choose the simplest method.

Terminology and Concepts

I thought it best if I give a brief overview of the terminology I use in my code and descriptions. I provide this as it may not be standard, but a mish mash of terms from Agha’s paper and Scala.

Tasks
Could also be called communications or messages. These are sent to the Mailbox of an Actor, where the Actor will execute a Behaviour based on this Task.
Mailbox
A queue of Tasks sent to an Actor.
Behaviour
A function or calculation that an actor performs upon receiving a communication.
Actor
A combination of a Mailbox and Behaviour.

Tasks

Agha defines a Task as a 3-tuple having a tag, mail address, and content. Not all these details will be required in the implementation.

  • Keeping a mail address is unnecessary, as the Task will be placed in a Mailbox immediately.
  • The tag is used to uniquely identify the Task. It is omitted also, and the responsibility of avoiding duplicate Tasks is placed on the programmer.

This leaves just the content. To keep it flexible this can be left as any Haskell type, so no code is necessary.

Mailbox

Next is the Mailbox, where tasks will be sent. Mailbox’s act as FIFO queues. It is important to note that these are likely to be written to by multiple threads.

Haskell’s STM library provides us with a data structure that meets these requirements. The semantics of TChan provide what I’m after and ensure that Mailboxes can be safely accessed from multiple threads. I can define the Mailbox type as equivalent to TChan.

I also write methods to create the mailbox, queue tasks, and receive tasks from the mailbox. These are basically wrappers around the standard TChan methods.

type Mailbox a = TChan a

new :: IO (Mailbox a)
new = atomically (newTChan)

pop :: Mailbox a -> IO a
pop = atomically . readTChan

push :: Mailbox a -> a -> IO ()
push to = atomically . writeTChan to

It’s important to note the call to readTChan in the pop function. If called on an empty TChan it will block its thread until a value becomes available.

Behaviours

Behaviours are executed by an Actor in response to a received Task. They return the Behaviour that should be executed in response to the next Task received.

Behaviours are able to communicate with Actors they are sent, they create, or are a part of. Any actors they are sent or they create are already in scope, but a reference to the containing Actor must also passed in.

I have used a Maybe type as the return value of a Behaviour. A return value of Nothing, indicating no subsequent Behaviour, will be used to indicate to Actor threads that they may terminate. An alternative would be to return a default, do nothing, Behaviour. I would need to look more closely at how Haskell terminates threads in this case though.

data Behaviour a = Behaviour {
  runBehaviour :: Actor a -> a -> IO (Maybe (Behaviour a))
}

To aid in the common cases of executing the same Behaviour for all Tasks or a one off Behaviour I define a couple of helper methods.

once :: (Actor a -> a -> IO ()) -> Behaviour a
once f = Behaviour $ \a m -> f a m >> return Nothing

loop :: (Actor a -> a -> IO ()) -> Behaviour a
loop f = Behaviour $ \a m -> f a m >> return (Just (loop f))

Actors

The previous concepts are brought together with the Actor type. An Actor is defined by a Mailbox and a Behaviour and is responsible for passing Tasks in the Mailbox to the appropriate Behaviour.

A function that creates an Actor from a given Behaviour is written that creates an empty Mailbox for the Actor. The send function for passing Tasks to an Actor is also given.

data Actor a = Actor { mbox :: Mailbox a, beh :: Behaviour a }

createActor :: Behaviour a -> IO (Actor a)
createActor b = new >>= return . flip Actor b

send :: Actor a -> a -> IO ()
send to = push (mbox to)

Actors are responsible for the execution of Behaviours in response to Tasks. To perform this, I define three methods:

  • step takes the first Task (waiting for one, if there is none) and passes it to the Actor’s current Behaviour. On completion of the Behaviour it creates a new Actor with the same Mailbox and the returned Behaviour.
  • run executes a series of these cycles, terminating when Nothing is returned by the Behaviour.
  • start executes this cycle on its own thread.

 

step :: Actor a -> IO (Maybe (Actor a))
step a = pop (mbox a) >>= runBehaviour (beh a) a >>=
  return . maybe Nothing (\b -> Just (Actor (mbox a) b))

run :: Actor a -> IO ()
run a = step a >>= maybe (return ()) run

start :: Actor a -> IO ()
start a = forkIO (run a) >> return ().

This completes an implementation of basic Actor behaviour.

Example

I’ll use an example from Agha’s writing, calculating factorials, to demonstrate the use of the functions I’ve just presented. This example does not benefit from the Actors approach, as the algorithm is not well suited to parallelization. Also, it does not handle erroneous input. It does however, provide a quick demonstration of Actors executing in Haskell.

First I define the Tasks that will be passed around. There is a Factorial task, which takes an Integer, being the factorial to calculate, and a destination Actor, where the result will be sent.

The second is a simple Task, that can be used to pass around single values.

data Factorial n dest = Factorial Integer (Actor (Value Integer))

data Value n = Value n
  deriving Show

The first actor defined is created with an Integer parameter and a destination Actor to which it will send its result. This actor will wait for a Value message. Once received it will multiply it by its Integer parameter and send the answer to the destination Actor.

multiplyActor dest n = createActor $ once $ multiplyBehaviour dest n
multiplyBehaviour dest n _ (Value k) = send dest (Value (n*k))

The result actor receives a Value and displays it. This will be used to display the final answer.

resultActor = createActor $ once $
  \_ (Value n) -> putStrLn ("Result:" ++ (show n))

The factorial actor follows the algorithm displayed in Agha’s work. It will create and start a multiplyActor which will wait for a Value task. It will then send a Factorial task instructing itself to calculate the factorial of n-1 and send the result to the newly created multiplyActor.

factorialActor = createActor $ loop $ factorialBehaviour

factorialBehaviour _ (Factorial 0 r) = send r (Value 1)
factorialBehaviour self (Factorial n r) = do
  m <- multiplyActor r n
  start m
  send self (Factorial (n-1) m)

To begin the computation it is necessary to start up the Actors and send an initial message. The factorial function below does this. Note that the result Actor is started with the run method to execute it on the same thread that factorial is called from. This means the function won’t terminate until resultActor recieves a Value task indicating the factorial calcuation has completed.

factorial n = do
  r <- resultActor
  a <- factorialActor
  start a
  send a (Factorial n r)
  run r

Testing in ghci

> factorial 6
Result:720
> factorial 20
Result:2432902008176640000

Summary

I have quite happy with what I have achieved in this experiment. It has taken only a small amount of code to create s simple, but working, implementation of the Actors model. I’m sure it is not without flaws or short comings, but I look forward to testing it out on more problems and extending it.

About these ads

3 Responses to “The Actors Model and Haskell”

  1. Levi Says:

    You may be interested to know that the Scheme language was initially an experiment to further understand the Actor model, too. See http://www.acm.org/crossroads/xrds1-2/scheme.html for a bibliographic reference, if you’d like to know more about it.

  2. Toyvo Yanksi Says:

    Your code looks clean. Interesting. I’m also thinking how to map Actors to Haskell syntax.

    There are just this practical feature I miss here (or maybe just don’t see): the ability to defer messages. You can find it in both Erlang and Scala receive constructs – if none of the following patterns match, the message is deferred to be processed later.

    However you seem to do a simple pop.

    In addition, IMHO ‘pop’ and ‘push’ are a little confusing as in many languages they refer to a LIFO stack, while you are using a FIFO channel.

    Finally, why do you need atomic access guaranteed by STM and TChan here? Would a Chan suffice? I think Chan is ok with many writer threads and a reader thread.

    Will be glad to read more of your code. Consider posting to http://hpaste.org – it highlights your syntax.

  3. lstephen Says:

    Levi: Thanks for the interesting link.

    Toyvo: I wasn’t sure how to implement the deferred message feature. Scala uses a PartialFunction class, which I don’t think has any equivalent in Haskell, and I couldn’t see a clean way to implement it. I’m not sure how Erlang does this. So, for simplicity, I left it out for now.

    I probably could use a Chan instead of a TChan. I’m not sure of the reasons for choosing one over the other.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: