Bartosz Milewski's Programming Cafe

Is the Actor model just another name for message passing between threads? In other words, can you consider a Java Thread object with a message queue an Actor? Or is there more to the Actor model? Bartosz investigates.

I’ll start with listing various properties that define the Actor Model. I will discuss implementation options in several languages.

Concurrency

Actors are objects that execute concurrently. Well, sort of. Erlang, for instance, is not an object-oriented language, so we can’t really talk about “objects”. An actor in Erlang is represented by a thing called a Process ID (Pid). But that’s nitpicking. The second part of the statement is more interesting. Strictly speaking, an actor may execute concurrently but at times it will not. For instance, in Scala, actor code may be executed by the calling thread.

Caveats aside, it’s convenient to think of actors as objects with a thread inside.

Message Passing

Actors communicate through message passing. Actors don’t communicate using shared memory (or at least pretend not to). The only way data may be passed between actors is through messages.

Erlang has a primitive send operation denoted by the exclamation mark. To send a message Msg to the process (actor) Pid you write:

Pid ! Msg

The message is copied to the address space of the receiver, so there is no sharing.

If you were to imitate this mechanism in Java, you would create a Thread object with a mailbox (a concurrent message queue), with no public methods other than put and get for passing messages. Enforcing copy semantics in Java is impossible so, strictly speaking, mailboxes should only store built-in types. Note that passing a Java Strings is okay, since strings are immutable.

-Typed messages

Here’s the first conundrum: in Java, as in any statically typed language, messages have to be typed. If you want to process more than one type of messages, it’s not enough to have just one mailbox per actor. In Erlang, which is dynamically typed, one canonical mailbox per actor suffices. In Java, mailboxes have to be abstracted from actors. So an actor may have one mailbox for accepting strings, another for integers, etc. You build actors from those smaller blocks.

But having multiple mailboxes creates another problem: How to block, waiting for messages from more than one mailbox at a time without breaking the encapsulation? And when one of the mailboxes fires, how to retrieve the correct type of a message from the appropriate mailbox? I’ll describe a few approaches.

-Pattern matching

Scala, which is also a statically typed language, uses the power of functional programming to to solve the typed messages problem. The receive statement uses pattern matching, which can match different types. It looks like a switch statements whose case labels are patterns. A pattern may specify the type it expects. You may send a string, or an integer, or a more complex data structure to an actor. A single receive statement inside the actor code may match any of those.

receive {
    case s: String => println("string: "+ s)
    case i: Int => println("integer: "+ i)
    case m => println("unknown: "+ m)
}

In Scala the type of a variable is specified after the colon, so s:String declares the variable s of the type String. The last case is a catch-all.

This is a very elegant solution to a difficult problem of marrying object-oriented programming to functional programming–a task at which Scala exceeds.

-Casting

Of course, we always have the option of escaping the type system. A mailbox could be just a queue of Objects. When a message is received, the actor could try casting it to each of the expected types in turn or use reflection to find out the type of the message. Here’s what Martin Odersky, the creator of Scala, has to say about it:

The most direct (some would say: crudest) form of decomposition uses the type-test and type-cast instructions available in Java and many other languages.

In the paper he co-authored with Emir and Williams (Matching Objects With Patterns) he gives the following evaluation of this method:

Evaluation: Type-tests and type-casts require zero overhead for the class hierarchy. The pattern matching itself is very verbose, for both shallow and deep patterns. In particular, every match appears as both a type-test and a subsequent type-cast. The scheme raises also the issue that type-casts are potentially unsafe because they can raise ClassCastExceptions. Type-tests and type-casts completely expose representation. They have mixed characteristics with respect to extensibility. On the one hand, one can add new variants without changing the framework (because there is nothing to be done in the framework itself). On the other hand, one cannot invent new patterns over existing variants that use the same syntax as the type-tests and type-casts.

The best one could do in C++ or D is to write generic code that hides casting from the client. Such generic code could use continuations to process messages after they’ve been cast. A continuation is a function that you pass to another function to be executed after that function completes (strictly speaking, a real continuation never returns, so I’m using this word loosely). The above example could be rewritten in C++ as:

void onString(std::string const & s) {
    cout << "string: " << s << std::endl;
}
void onInt(int i) {
    cout << "integer: " << i << std::endl;
}

receive<std::string, int> (&onString, &onInt);

where receive is a variadic template (available in C++0x). It would do the dynamic casting and call the appropriate function to process the result. The syntax is awkward and less flexible than that of Scala, but it works.

The use of lambdas might make things a bit clearer. Here’s an example in D using lambdas (function literals), courtesy Sean Kelly and Jason House:

receive(
    (string s){ writefln("string: %s", s); },
    (int i){ writefln("integer: %s", i); }
);

Interestingly enough, Scala’s receive is a library function with the pattern matching block playing the role of a continuation. Scala has syntactic sugar to make lambdas look like curly-braced blocks of code. Actually, each case statement is interpreted by Scala as a partial function–a function that is not defined for all values (or types) of arguments. The pattern matching part of case becomes the isDefinedAt method of this partial function object, and the code after that becomes its apply method. Of course, partial functions could also be implemented in C++ or D, but with a lot of superfluous awkwardness–lambda notation doesn’t help when partial functions are involved.

-Isolation

Finally, there is the problem of isolation. A message-passing system must be protected from data sharing. As long as the message is a primitive type and is passed by value (or an immutable type passed by reference), there’s no problem. But when you pass a mutable Object as a message, in reality you are passing a reference (a handle) to it. Suddenly your message is shared and may be accessed by more than one thread at a time. You either need additional synchronization outside of the Actor model or risk data races. Languages that are not strictly functional, including Scala, have to deal with this problem. They usually pass this responsibility, conveniently, to the programmer.

-Kilim

Java is not a good language to implement the Actor model. You can extend Java though, and there is one such extension worth mentioning called Kilim by Sriram Srinivasan and Alan Mycroft from Cambridge, UK. Messages in Kilim are restricted to objects with no internal aliasing, which have move semantics. The pre-processor (weaver) checks the structure of messages and generates appropriate Java code for passing them around. I tried to figure out how Kilim deals with waiting on multiple mailboxes, but there isn’t enough documentation available on the Web. The authors mention using the select statement, but never provide any details or examples.

Correction: Sriram was kind enough to provide an example of the use of select:

int n = Mailbox.select(mb0, mb1, .., timeout);

The return value is the index of the mailbox, or -1 for the timeout. Composability is an important feature of the message passing model.

Dynamic Networks

Everything I described so far is common to CSP (Communicating Sequential Processes) and the Actor model. Here’s what makes actors more general:

Connections between actors are dynamic. Unlike processes in CSP, actors may establish communication channels dynamically. They may pass messages containing references to actors (or mailboxes). They can then send messages to those actors. Here’s a Scala example:

receive {
    case (name: String, actor: Actor) =>
        actor ! lookup(name)
}

The original message is a tuple combining a string and an actor object. The receiver sends the result of lookup(name) to the actor it has just learned about. Thus a new communication channel between the receiver and the unknown actor can be established at runtime. (In Kilim the same is possible by passing mailboxes via messages.)

Actors in D

The D programming language with my proposed race-free type system could dramatically improve the safety of message passing. Race-free type system distinguishes between various types of sharing and enforces synchronization when necessary. For instance, since an Actor would be shared between threads, it would have to be declared shared. All objects inside a shared actor, including the mailbox, would automatically inherit the shared property. A shared message queue inside the mailbox could only store value types, unique types with move semantics, or reference types that are either immutable or are monitors (provide their own synchronization). These are exactly the types of messages that may be safely passed between actors. Notice that this is more than is allowed in Erlang (value types only) or Kilim (unique types only), but doesn’t include “dangerous” types that even Scala accepts (not to mention Java or C++).

I will discuss message queues in the next installment.

I started writing a post about implementing actors in D when I realized that there was something wrong with the way thread spawning interacts with data sharing. Currently D’s Thread class closely mimics its Java counterpart, so I started wondering if this may be a more general problem–a problem with mixing object-oriented paradigm with multithreading.

In functional languages like Erlang or Concurrent ML, you start a thread by calling a function–spawn or create, respectively. The argument to this function is another function–the one to be executed in a new thread. If you think of a new thread as a semi-separate application, the thread function is its “main”. You may also pass arguments to it–the equivalent of argc, argv, only more general. Those arguments are, of course, passed by value (we’re talking functional programming after all).

In non-functional languages it’s possible and often desirable to share data between threads. It’s very important to know which variables are shared and which aren’t, because shared variables require special handling–they need synchronization. You may share global variables with a thread, or you may pass shared variables to it during thread creation. You may also provide access to more shared variables during the thread’s lifetime by attaching and detaching them from the original shared variables–that’s how message queues may be described in this language.

In the object-oriented world everything is an object so, predictably, a (capital letter) Thread is an object too. An object combines data with code. There is a piece of data associated with every thread–the thread ID or a handle–and there are things you can do to a thread, like pause it, wait for its termination, etc.

But there’s more: A Thread in Java has a thread function. It’s a method called run. The user defines his or her own thread by inheriting from Thread and overriding run. Since run takes no arguments, data has to be passed to the new thread by making it part of the derived thread object. In general a thread object contains two types of data: shared and non-shared. The non-shared data are the value arguments passed by the creator to the thread function, possibly some return values, plus state used internally by the thread function. Thread data may form some logical abstraction or, as it often happens, have the structure of a kitchen sink after a dinner party.

Because of the presence of shared state, a Thread object must be considered shared, thus requiring synchronization. As I described in my previous posts, public methods of a shared object must either be synchronized or lock free. But what about the run method? It cannot be synchronized because that would make the whole thread object inaccessible to other threads, including its creator (which may be okay for a daemon thread, but wold be a fatal flaw in general).

It makes perfect sense for run to be private, since nobody should call it from the outside (or, for that matter, from the inside). But the reason for private methods not requiring synchronization is that they are only called from public methods, which must be synchronized. This is not true for run—run is not called from under any lock! So essentially run has unfettered access to all (potentially shared) data stored in this. Unless the programmer is very disciplined, the potential for data races is high. And that’s where Java stands right now (the Runnable interface has the same problems).

If you’ve been following my blog, you know that I’m working on a type system that eliminates races. If I can convince Walter and Andrei, this system might be implemented in the D programming language. As I mentioned, D’s treatment of threads comes directly from Java and therefore is inherently unsafe. Like in Java, D’s Thread object has a run method.

So how could D, with the race-free type system, improve on Java? One possibility is to make the run method lockfree. A lockfree method (public or private) is not synchronized but its access to this is severely restricted. It can only operate on lockfree data members (if any), unless it takes the object’s lock or calls a synchronized method (all public methods of a shared object are, by default, synchronized). Let me give you a small example:

class Counter: Thread {
public:
    // public methods are implicitly synchronized
    void inc() { ++_cnt; }
    void dec() { --_cnt; }
private:
    override void run() lockfree {
        inc(); // ok: calling a synchronized method
        wait(10000);
        synchronized(this) { // ok: explicit synchronization on this
            _cnt = _cnt * _cnt;
        }
        // _cnt /= 2; // error: not synchronized!
    }
    int _cnt;
}
// usage:
auto cnt = new shared Counter;
cnt.start;
cnt.inc;
cnt.join;

This approach would work and guarantee freedom from races, but I don’t think it fits D. Unlike Java, which is so OO that even main is a method of an object, D is a multi-paradigm language. It doesn’t have to force threads into an OO paradigm. And the thread function, being a thread equivalent of main doesn’t have to be a method of any object. In my opinion, the functional approach to thread creation would serve D much better.

Here’s how I see it:

class Counter {
public:
    void inc() { ++_cnt; }
    void dec() { --_cnt; }
    int get() const { return _cnt; }
    void set(int cnt) { _cnt = cnt; }
private:
    int _cnt;
}

void counterFun(shared Counter cnt) {
    cnt.inc;
    Thread.sleep(10000);
    synchronized(cnt) {
        int c = cnt.get;
        cnt.set(c * c);
    }
}
// usage:
auto cnt = new shared Counter;
Thread thr = Thread.spawn(&counterFun, cnt);
thr.start;
cnt.inc;
thr.join;

I find it more logical to have start and join operate on a different object, thr, rather than on the counter, cnt. The static template method spawn accepts a function that takes an arbitrary number of arguments that are either values or shared or unique objects. In particular, you could pass to it your (shared) communication channels or message queues to implement the message-passing paradigm.

Such spawn primitive could be used to build more complex classes–including the equivalents of a Java’s Thread or a Scala’s Actor.