Skip to content

Dining with a lost uncle philosopher

by Frank Sauer on March 14th, 2015

For some reason the actor model has always felt natural and somewhat familiar to me and I never really knew why until recently. Even when I was first dabbling in Erlang, which is when I first saw them ‘officially’, it felt familiar even though the language was completely alien.

Recently, I was going through some old stuff from my college days and stumbled on an old 1988 technical report from the Philips Research Laboratories containing a collection of papers on a language called POOL-T (pl and parpl documentation release 3.0, May 1988). I had taken a class back in early 1989, the goal of which was to learn two new programming languages, implement the same project in both and then write a report comparing and contrasting the two languages based on the implementations of that project. I do not remember the reasons why, but I chose Smalltalk and POOL-T. I suspect I took the class as an excuse to learn Smalltalk and I have no idea why I even knew about the existence of POOL-T… They sure knew how to name things though; POOL (Parallel Object oriented Language) was designed to run on DOOM (Decentralized Object oriented Machine)!

As I started to read this report, to my surprise its content again felt very familiar…. Objects in POOL-T feel a lot like what we call actors today, as we’ll see in the examples below. I do not know if the researchers at Philips were aware of Erlang and the OTP at the time they developed it. It is more likely that both POOL-T and the Erlang actor model were at least in part based on the 1973 paper that introduced the actor model: “A Universal Modular Actor Formalism for Artificial Intelligence” by Carl Hewitt, Peter Bishop and Richard Steiger.

However, it is also entirely possible the similarity is coincidental and perhaps POOL-T is not based on actors at all… more on this later.

Let’s look at an example POOL-T program (Excerpt from a larger Dining Philosopher example from the POOL-T User Manual by Lex Augusteijn, Nov 23, 1987) and see if these objects are actually actors:

CLASS Fork

  METHOD pickup () Fork :
    RETURN SELF
  END pickup

  METHOD putdown () Fork :
    RETURN SELF
  END putdown

  ROUTINE new () Fork :
    RETURN NEW 
  END new

  BODY
    DO TRUE THEN
      ANSWER (pickup);
      ANSWER (putdown)
    OD
END Fork

CLASS Room
  VAR occupancy, max_occupancy: Integer

  METHOD init(max : Integer) Room :
    max_occupancy <- max;
    occupancy <- 0;
    RETURN SELF
  END init

  METHOD enter () Room :
    occupancy <- occupancy + 1;
    RETURN SELF
  END enter

  METHOD exit () Room :
    occupancy <- occupancy - 1;
    RETURN SELF
  END exit

  ROUTINE new (max: Integer) Room :
    RETURN NEW ! init(max)
  END new

  BODY
    ANSWER (init);
    DO TRUE THEN
       SEL occupancy > 0             ANSWER(exit)
        OR occupancy < max_occupancy ANSWER(enter)
       LES
    OD
END Room

Let's look at forks first as they are the simplest. They are created using the routine new (think of a routine as a static method). A new fork is assumed to be lying on the table right after creation. The BODY of a POOL-T class describes a process that starts executing when an instance is created. Each POOL-T object has its own active process! Forks can answer two messages, pickup and putdown, however, they have to alternate - a fork can not be picked up twice in succession without being putdown first. This behavior is represented by the infinite loop DO TRUE ... OD and the sequence of ANSWER statements in it. The ANSWER statement states that the object executing it is prepared to answer any message listed in its list of method ids (here it lists only one in each case). When an ANSWER statement is executed the object selects a message that has arrived and whose method name occurs in the list of the ANSWER statement (you can use ALL to stand for all methods). If no such message has yet arrived, the object keeps waiting until one does arrive (which may take forever). If there is more than one such message, the one that arrived first is selected. This feels very much like an actor, in fact the Akka actor would look something like this:


case object Pickup
case object Putdown

class Fork extends Actor {

  def receive = onTable

  def onTable: Receive = {
    case Pickup => context become inUse
  }

  def inUse: Receive = {
    case Putdown => context become onTable
  }
}

Let's examine the Room class next. Rooms are also created using the new routine. In this case the new object is sent an init message with the maximum occupancy for the new room. The initialization of rooms is enforced by the process described in the BODY as the first and ONLY message it is willing to answer is the init message. Only after init has been answered can a room be entered, but only if the maximum occupancy has not been reached. Furthermore, a room can be exited, but only if it still has occupants. Note the SEL statement represents the conditional answering of messages. It is executed as follows (from "Definition of the programming language POOL-T", 1986 by Pierre America):

  1. All guards are evaluated in the order in which they are specified in the program text
  2. All commands whose guards evaluated to false are discarded
  3. The set of methods from the ANSWER statement of one of the SEL clauses is determined
  4. The set of all messages that have arrived for this object and whose method identifier is in the above set is determined
  5. If this set of messages is empty, and there are open guarded commands without an ANSWER statement, the textually first of them is selected. Its statement sequence after THEN is executed if present and the SEL terminates
  6. If this set of messages is empty and there is no open guarded command without an ANSWER statement, the object waits until a message that belongs to this set arrives, and then proceeds with this message
  7. If this set of messages is not empty, the message that arrived first is selected. The first guarded command is chosen whose ANSWER statement contains the method named in the message. Of this guarded command, first the ANSWER statement is executed, then the statement sequence after THEN (if present). After that the select statement terminates.

This SEL statement also translates quite naturally:


case class Init(max: Int)
case object Enter
case object Exit

class Room extends Actor {

  def receive = init

  def init: Receive = {
    case Init(max) => context become ready(max, 0)
  }

  def ready(max_occupancy: Int, occupancy: Int): Receive = {
    case Enter if occupancy < max_occupancy => 
      context become ready(max_occupancy, occupancy + 1)
    case Exit  if (occupancy > 0 => 
      context become ready(max_occupancy, occupancy - 1)
  }
}

So at first glance, all of the above sounds a LOT like actors... Messages are sent using !, they are queued up at the receiver, and they may or may not be answered... The SEL feels a lot like a pattern match with guards used in the receive method of an Akka actor.

So are POOL-T objects in fact actors?

To find out, let's look at the body (just the body for brevity) of the Philosopher class and how it makes use of the rooms and forks and sends messages to these objects:

CLASS Philosopher
 ...
BODY
  ANSWER (init)
  DO TRUE THEN
    think();
    room ! enter();
    lfork ! pickup() ; rfork ! pickup();
    eat();
    lfork ! putdown(); rfork ! putdown();
    room ! exit();
  OD
END Philosopher

It turns out the room and forks are used like locks and this will only work as intended if ! is synchronous and blocks... So, the ! is not asynchronous as in the actor model, but concurrency can be achieved by having statements in a POST block following the RETURN statement in a receiving method. These are executed after the return value is returned to the sender and execute in parallel with the sender. The language spec states this about the send expression:

... Finally the message, consisting of the indicated method identifier and the parameters is sent to the destination object. When it is answered by the destination object, the corresponding method is invoked with the parameters filled in and the result is sent back. This result is then the result of the send expression.

And about the RETURN and POST section:

...After that, the RETURN expression is evaluated and the result of this expression is returned to the object that sent the message. The part of the execution so far is called the "render-vous": the sending object is waiting for the receiving one to process its message. After the rendezvous both objects will execute independently. Finally the post processing section (if present) is executed and then the answer statement terminates. So it is possible for the sender of the message to resume its execution while the receiver is executing the post-processing section.

And there we have it. Even though at first glance POOL-T objects feel like actors, the semantics of ! are in fact the opposite of actors and it would be hard to consider POOL-T objects actors for this reason alone. According to the Message Passing semantics of the actor model asynchronous communication between actors is a core feature of the actor model. Therefore POOL-T is much more like CSP instead. It would be much harder to implement the Philosopher with actors for forks and the room, but a quick google shows that it can and has in fact be done; see Victor Klang's post Dining Hakkers but to me this doesn't feel nearly as natural as the synchronous POOL-T implementation.

From → programming, scala

No comments yet

Leave a Reply

You must be logged in to post a comment.