Playing with Actors
-------------------
As I hinted in an earlier post, I have some vague plans for a
distributed public MOO-like system based on Carl Hewitt's actor model
of computation [1]. Under this model computations proceed by a large
number of "actors" (atomic units of computation) asynchronously
passing messages to one another. Besides being a useful way to think
about concurrency formally, the model has many practical applications.
(E.g. Erlang, although that was developed independently.)
Today I wanted to write about some of my recent attempts to get to
grips with the basics of the actor model by implementing some of its
ideas in (can you guess?) Scheme. Before we get started though, I
need to include the following warning:
I AM NOT A REAL COMPUTER SCIENTIST.
I.e. don't believe anything you read here!
Okay, now that's out of the way...
The basic capabilities of actors are very simple. As stated on the
Wikipedia page [2], an actor is a computational entity which, upon
receipt of a message, may do any of the following:
(1) send messages to other actors whose address it has,
(2) create new actors,
(3) update its "behaviour", i.e. how the actor will respond to
subsequent messages.
That's essentially it. There are some interesting side effects to
this list. For instance, (1) implies that actor addresses must be
"unforgeable" (otherwise actors could "guess" another's address and
send it a message). Also, (3) suggests that the processing of a
message must be somehow atomic on the scale of the actor.
Okay, so how can we go about modeling this in Scheme? (Actually,
Scheme and the actor model have some interesting shared history, in
that Sussman and Steele actually designed Scheme with the goal of
experimenting with this model. [3]) To begin, we need a way of
representing an actor. But what is an actor? From the description
above, it is simply some kind of "address" associated with a
"behaviour", where a "behaviour" describes a procedure for responding
to messages.
Aha! Scheme has a wonderful way of representing procedures: the
lambda expression! So here's our first code snippet:
(define actor-table (make-hash-table))
(define (make-actor-with-address address behaviour)
(hash-table-set! actor-table address behaviour)
address)
This defines a global hash table to store the mapping from addresses
to behaviours, as well as a procedure which adds a address->behaviour
pair to that table. The value returned is the address.
Of course, this method for making actors is a bit clumsy - we want
each actor to be given some unique address, not one that is
predetermined by the creator. (Using predetermined addresses would no
doubt lead to violations of rule (1).) Thus we also define
(define next-actor-address 1)
(define (make-actor behaviour)
(make-actor-with-address next-actor-address behaviour)
(let ((address next-actor-address))
(set! next-actor-address (+ next-actor-address 1))
address))
This is a fairly silly approach, but with some discipline on the part
of the programmer it does ensure that each actor is given a unique
address.
Okay, so far so good. Now how do we go about sending messages to
actors? To start thinking about this, lets define a message dispatch
procedure:
(define (dispatch-message address message)
(let ((behaviour (hash-table-ref/default actor-table address '())))
(if (null? behaviour)
(print "Warning: discarded message " message
" to unknown actor " address)
(let ((value (apply behaviour (cons address message))))
(case value
((sleep) 'do-nothing)
((done) (hash-table-delete! actor-table address))
(else
(hash-table-set! actor-table address value)))))))
All this does is take an address and a message (some arbitrary scheme
object), look the address up in the hash table to find the
corresponding behaviour, then apply this behaviour to the both the
actor address and the message object. (Sneaking in the actor address
allows the actor to send messages to itself.)
The only non-obvious part is what is done with the return value of the
behaviour procedure. It's non-obvious precisely because this is not
indicated at all by the model itself since there's no requirement that
actors return a response to a received message, nor even that actors
implicitly know from whom a given message comes. Because of this,
we're free to use the return value of the behaviour procedure in any
way we like, and in the case above I've chosen to interpret the return
value as the means of signifying actor behaviour updates. Symbols
'sleep and 'done are used to respectively keep the same behaviour and
delete the actor from the hash map. Otherwise the response is assumed
to be a new procedure to use as the actor's behaviour.
Our implementation now has a fairly concrete actor representation.
The only thing that's really missing at this point is a way to "send"
messages, i.e. schedule them to be delivered asynchronously to actors
using the above dispatch mechanism.
This is probably a good point to emphasize the difference between
concurrency and parallelism. Parallelism involves multiple tasks
literally running at the same time, which requires multiple cores,
CPUs, computers or whatever. Concurrency is a more general concept
that describes tasks whose overall execution spans the same period of
time, but doesn't necessarily require that the two tasks are ever
simultaneously being executed: interleaving the steps in the tasks is
enough. Why is this important? Because it means that for our
purposes of exploring the model, it's enough to forget about threads,
mutexes etc and instead implement the core of our actor processing
machine using a simple FIFO queue.
(define message-queue (make-fifo))
Here make-fifo returns a FIFO "f" to which a object "x" can be added
using (fifo-push f x) and from which objects can be retrieved using
(fifo-pop f). With this queue in place, the send-message function is
easy:
(define (send-message actor . message)
(fifo-push message-queue (cons actor message)))
I.e. sending a message amounts to simply adding it to the FIFO queue.
"That's great," I hear you say, "but how on earth does anything get
run?" Easy! We just set up a loop to iteratively dispatch messages
at the end of the queue to their intended destination, like so:
(define (next-addressed-msg)
(if (fifo-empty? message-queue)
'()
(fifo-pop message-queue)))
(define (process-next-message)
(let ((addressed-msg (next-addressed-msg)))
(if (null? addressed-msg)
'()
(let ((address (car addressed-msg))
(message (cdr addressed-msg)))
(dispatch-message address message)))))
(define (run)
(unless (null? (process-next-message))
(run)))
Done!
Okay, so let's try it out! To do this I'm going to steal
the first and simplest factorial example from a wonderful
blog post [5] by Dale Schumacher. (I found his posts really
fascinating in general, take a look!) This involves defining
two actors as follows:
(define println
(make-actor
(lambda (self . message)
(apply print message)
'sleep)))
(define factorial
(make-actor
(lambda (self customer . message)
(match message
((n) (send-message self customer n 1) 'sleep)
((0 acc) (send-message customer acc) 'sleep)
((n acc) (send-message self customer (- n 1) (* acc n)) 'sleep)))))
(I'm cheating a little by using the pattern matching macro implemented
in Chicken's "matchable" egg, but it clarifies things hugely.)
The first actor "println" simply prints any message it gets. This may
seem like a peculiar inclusion in our first example, but remember that
actors don't return values - they can only send more messages. We use
the println actor as the destination for the result of the
computation.
The second actor "factorial" does all of the work. Firstly, note that
its message structure is actually broken down into two parts: the
"customer" argument and the "message" argument. The "customer" part
tells factorial where the result of the computation should eventually
be sent, while the "message" part is either a simple positive integer
n, or a pair (n acc). In the former case, factorial sends _itself_ a
message of the form (n 1). In the latter case, it again sends itself
a message but this time (n-1 acc*n). This continues until factorial
receives a message of the form (0 acc) at which point acc holds the
result which factorial passes on to whatever actor has the address
contained in "customer".
To actually try this out we can kick the process off by evaluating the
following two forms:
(send-message factorial println 5)
(run)
The first adds a message (asking factorial to send the factorial of 5
to the actor whose address is bound to println) to the message queue.
The second simply dispatches messages from that queue until none
remain. The result is, unsurprisingly,
120
What's actually going on here? To get a better picture we can use the
time-honoured trick of sprinkling print statements everywhere to trace
the execution. Lets make our program tell us whenever a message is
queued and dispatched. Furthermore, lets give the actors
human-readable address names to make the trace even easier to read.
The result of the above evaluation is then
Queued message (println 5) to factorial
Dispatching message (println 5) to factorial
Queued message (println 5 1) to factorial
Dispatching message (println 5 1) to factorial
Queued message (println 4 5) to factorial
Dispatching message (println 4 5) to factorial
Queued message (println 3 20) to factorial
Dispatching message (println 3 20) to factorial
Queued message (println 2 60) to factorial
Dispatching message (println 2 60) to factorial
Queued message (println 1 120) to factorial
Dispatching message (println 1 120) to factorial
Queued message (println 0 120) to factorial
Dispatching message (println 0 120) to factorial
Queued message (120) to println
Dispatching message (120) to println
120
We can now clearly see the sequence of messages that produced the
final result, which was dutifully sent to the println actor to be
displayed on the screen.
Now here's an interesting question: what happens when we schedule two
separate factorial evaluations simultaneously?
Let's try computing 5! and 7!:
(send-message factorial println 5)
(send-message factorial println 7)
(run)
The result is as we'd expect, although note that the ordering
here is a product of the scheduler implementation and is not
defined by the abstract model:
120
5040
Okay, that seems to work. What does the message trace look like
for this?
Queued message (println 5) to factorial
Queued message (println 7) to factorial
Dispatching message (println 5) to factorial
Queued message (println 5 1) to factorial
Dispatching message (println 7) to factorial
Queued message (println 7 1) to factorial
Dispatching message (println 5 1) to factorial
Queued message (println 4 5) to factorial
Dispatching message (println 7 1) to factorial
Queued message (println 6 7) to factorial
Dispatching message (println 4 5) to factorial
Queued message (println 3 20) to factorial
Dispatching message (println 6 7) to factorial
Queued message (println 5 42) to factorial
Dispatching message (println 3 20) to factorial
Queued message (println 2 60) to factorial
Dispatching message (println 5 42) to factorial
Queued message (println 4 210) to factorial
Dispatching message (println 2 60) to factorial
Queued message (println 1 120) to factorial
Dispatching message (println 4 210) to factorial
Queued message (println 3 840) to factorial
Dispatching message (println 1 120) to factorial
Queued message (println 0 120) to factorial
Dispatching message (println 3 840) to factorial
Queued message (println 2 2520) to factorial
Dispatching message (println 0 120) to factorial
Queued message (120) to println
Dispatching message (println 2 2520) to factorial
Queued message (println 1 5040) to factorial
Dispatching message (120) to println
120
Dispatching message (println 1 5040) to factorial
Queued message (println 0 5040) to factorial
Dispatching message (println 0 5040) to factorial
Queued message (5040) to println
Dispatching message (5040) to println
5040
Wow! Notice that the computations of both factorials are interleaved,
but the two computations do not interfere with one another at all.
More than that, the factorial actor doesn't ever know or care to which
computation the message being processed actually belongs. This is
possible because the state of the computation is entirely specified by
the content of the messages flying around.
Is it possible to store state in the actor behaviours themselves? Of
course! Again stealing (ahem borrowing) from [4] we can create an
actor that works as a counter:
(define ((make-counter-behaviour value) self customer . args)
(match args
(('get) (send-message customer value) 'sleep)
(('inc delta) (make-counter-behaviour (+ value delta)))))
Here we've actually defined a higher order procedure to construct
behaviour procedures for us. A given counter behaviour responds to
'get and 'inc messages: 'get sends the a value (defined by the
behaviour) to a customer actor, while 'inc replaces the existing
behaviour with a new one in which the value is increased by some
amount.
Here's what it looks like in practice:
(define counter (make-actor (make-counter-behaviour 0)))
(send-and-run counter println 'get)
(send-message counter println 'inc 3)
(send-message counter println 'get)
(send-message counter println 'inc 2)
(send-message counter println 'get)
(run)
The result is exactly what you'd expect:
0
3
5
and the trace is as follows:
Queued message (println get) to counter
Dispatching message (println get) to counter
Queued message (0) to println
Dispatching message (0) to println
0
Queued message (println inc 3) to counter
Queued message (println get) to counter
Queued message (println inc 2) to counter
Queued message (println get) to counter
Dispatching message (println inc 3) to counter
Updating behaviour of counter
Dispatching message (println get) to counter
Queued message (3) to println
Dispatching message (println inc 2) to counter
Updating behaviour of counter
Dispatching message (println get) to counter
Queued message (5) to println
Dispatching message (3) to println
3
Dispatching message (5) to println
5
Again, remember that the precise _order_ in which the messages arrive
is not defined by the model and thus is entirely implementation
dependent. This of course means that the result is in some sense
stochastic: not well defined. However, what's I think is important is
that - provided the model is implemented in line with the above three
rules - none of the synchronization headaches often associated with
concurrent programming can occur. None of this is magic of course,
its' just that the model enforces a discipline which avoids these
difficulties. (State is local to actors, never shared between actors,
and message responses are atomic.)
Anyway, I hope you found that as fun as I did! The code for these
exercises can be cloned from git://thelambdalab.xyz/actors.git or you
can browse it via gopher [5].
Until next time, fellow gophers.
--
[1]: http://worrydream.com/refs/Hewitt-ActorModel.pdf
[2]: https://en.wikipedia.org/wiki/Actor_model
[3]: doi:10.1023/A:1010079421970
[4]: http://www.dalnefre.com/wp/2010/05/deconstructing-the-actor-model/
[5]: gopher://thelambdalab.xyz/1/scripts/browse-git.scm|actors.git