Message Queue

This is a design for an ObjectOriented kind of virtual machine.

MessageQueues can be a way to implement AsynchronousProgramming without LockBasedSynchronization. MessageQueues can have problems with overflow or underflow. SendReceiveReply is a synchronous programming technique that does not exhibit that problem.

In pure ActorLanguages, control is concurrent by default, and MessageQueues can be used to enforce sequential threads of control or serialized access to objects (for example vat message queues in EeLanguage or "serializers" in Act2).

MessageQueue implementation

You have a message queue and a message loop. The message loop looks like this:

 while(queue not empty)
 { let message x = front of the queue;
   pop the queue;
   dispatch x to its destination;
 }
 program ends

The destinations are all objects. Basically a message consists of three fields:

destination object
message name
message parameters

Provoked by a message, an object may compute and then post more messages. An object may also change its internal state (although interesting things can happen if the object is not permitted to have an internal state -- if it must receive that information as part of the message. This information would have to include references to other objects.)

If there is always one message in the queue at any given time, then this method of computation reduces to ContinuationPassingStyle. It eliminates the HollywoodProblem because objects never call each other; instead they post messages to each other.

If an object wants a message to "return" it has to attach a "continuation" to the message, and the recipient has to be able to use that continuation in order to post a return message.

Another way to look at this is message rewriting. Every method of an object is a rewrite rule which rewrites a message into another message, which is then posted in the queue. See RewriteRules.

ObjectOrientation is optional. You could view every method as a RewriteRule? and every object as a collection of closely related rewrite rules.

It is possible for an object not to post any messages, or to post more than one message. This causes multiple paths of computation to occur. It makes a MessageQueue seem more powerful than RewriteRules (although you can view this machine as rewriting the entire MessageQueue). It is possible for the virtual machine to dispatch messages simultaneously, if they are available. It doesn't make any difference to the outcome if it does.

For interactive computing, it is possible to modify this loop slightly:

 post "begin program" message to queue;
 mainloop: while(true)
 { while (queue is not empty)
   { pop message x from queue;
     if (x is the terminate message) { break mainloop; };
     dispatch message x;
   }
   while (there is no user input) wait;
   post user input to queue;
 }

Another interesting side effect of the MessageQueue is that you become highly aware of the fact that control structures are stateful. No longer can you do something like this:

 if (condition)
 { call method a;
   call method b with results from a as parameter;
 }
 else
 { call method b with 0 as parameter;
 }

How do you replace those calls with message posts? You have to pass continuations in the messages. The continuation must contain the state of the control structure.

"The first messaging system had a separate process for managing queues and enqueueing and dequeueing messages. After we worked with that for a few years we realized we didn't really need all the process context switches that required."

Does this mean you just deposited them on the queue directly?

Yes. The enqueueing process put messages on the queue without first sending them to a queue manager process.

What was the motivation for using a separate process originially?

I don't know. I've seen that MQ Series uses a separate queue manager process, so the original authors may have been inspired by that. The fact that queues exist outside the scope of the processes that use them may lead folks to believe they have to have a process that "owns" them. When we realized the operating system could own them we reduced the number of process context switches and more than doubled the throughput speed.

See ModelsOfComputation.