Linda, originally proposed by Nicholas Carriero and David Gelernter, is a model of process communication using a small set of well-defined primitives, operating on a tuple space. 

Interestingly, Sicstus Prolog comes with a library that implements Linda (both Server and Client).  I played with it a little bit and really enjoyed it. In this article, I would like share my experience. 

The Linda server process acts like a tuple space or blackboard on which one or more client processes can read and write. Here are the operations that the client processes can perform:

out(X) => Write the tuple X to the tuple space

in(X) => Read and remove the tuple X from the tuple space

rd(X) => Read, but not remove, the tuple X from the tuple space

While out always succeeds, both in and rd will block until the required tuple becomes available.

Two other predicates, in_noblock(X) and rd_noblock(X) will return with failure if the tuple is not available in the tuple space.

The original Linda system had one more operation called eval, but that is not supported in Sicstus Prolog’s implementation.

By the way, a tuple is similar to a struct or record found in many programming languages, and can have any number of fields.

The overall process communication is shown in the following diagram:

As you can see, processes (client processes in the diagram) do not communicate among themselves directly. A process posts one or more tuples on the tuple space and other processes respond to that by posting other tuples. This is a loosely-coupled model. 

In the example I am going to discuss, we have the following processes:

Server process => This acts as the tuple space or blackboard

Text Parser Process => This is a client process that parses simple English sentences and returns the corresponding parse tree

Math Process => Another trivial client process that can perform Sum, Product and Square root on numbers.

Simple Client => This client process makes use of the Parser and Math processes

Although technically the different processes could all be run on different computers (Windows machines in my case), I chose to run them on the same desktop computer for the sake of convenience.

Let me start the Linda server process first. This serves as the tuple space. I use the address printed by the server process to start the remaining three client processes. You can see that the server echoes the connection established with the clients.

Here is an image showing the Parser and Math servers after the launch:

Finally, let us start the simple client that allows us to communicate with the servers:

We will use the Simple client console to perform some parsing and math tasks. The parser process uses my iLexicon library and implements a simple DCG-based parser for a subset of English. Given a word, it can return its parts-of-speech (POS) and also check whether a given <word, pos> is valid. See this image.

In the above, the client asks for the POS of the word anger. The parser server responds with the relevant POS, in this case, it is both noun and verb. Please note that the client process posts this request on the blackboard (tuple space) and is not directly communicating with the parser server (when you see the source code you will understand how). As explained earlier, every interaction between processes is entirely through the tuple space.

The third command in the client process asks for the parse tree of the sentence “cats are friendly”. Once again, the parser server responds by parsing the given sentence and sending back the parse tree. Here is the parse tree for this sentence:

The above parse tree is based on the DCG rules I have implemented in the parser. There is nothing sacred about it.

Next, let us try to parse a slightly longer sentence:

Here is the corresponding parse tree.

OK, time to switch to the Math processor. To make things slightly more interesting, let us start one more math processor and pose some math-related queries on the client.

You can see that the math operations are promptly responded to by one of the math processes. Here is the image showing the three processes in action. 

Both the math processes are polling the tuple space for tuples that they can handle and when a matching tuple is posted by the client process, one of them non-deterministically grabs it, processes it and posts the reply back to the tuple space. This is then picked up by the client, which is waiting for the result.

Nice, isn’t it? We can thus add processes dynamically to scale up, or remove processes to scale down, but the client is completely unaware of this. That is the benefit of loose coupling.

I am sure you are curious to look at the source. Let me not disappoint you. Here is the source for launching the tuple space server:

Here is the parser server source:

The above does not include the code for the DCG and iLexicon functionality.

The first part of the math server source given below shows the main predicates that interact with the tuple space.

The actual computation of the math operations is shown below. No magic here.

Finally, here is how the client process looks like:

That is it. Hope I managed to convey the basic idea of the Linda system. As mentioned in the beginning, I have implemented this example in Sicstus Prolog on windows.

Have a Merry Christmas and a wonderful holiday season! See you again in the New Year!

Tags: Distributed Computing, Linda Tuple Space, Prolog