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 .