Francis asked:

I still don’t understand what this is for. Can you describe an example application from a user’s point of view?

Also, in what way is it selected which tuple is extracted from the bag when you extract them. Does it filter on them? Or select one at random? Or what?

Suppose we have a bag containing three tuples:

("foo", "bar", "baz")
(1, 2, 3)
(1, "bar", 3)

Tuple selection is done by pattern matching, so for example:

("foo", ANY, ANY)   ->  ("foo", "bar", "baz")
(ANY, "bar", ANY)   ->  either ("foo", "bar", "baz") or (1, "bar", 3)
(ANY, ANY, 3)       ->  either (1, 2, 3) or (1, "bar", 3)

In the original Linda system, patterns are typed so that we could ask for (string, “bar”, string) or (int, “bar”, int), and get tuples matching the types. An even more powerful system might enable matching with expressions, e.g. (int < 2, left(string, 2)=”ba”, int > 2).

If several tuples match the pattern supplied by the user, only one is returned (in the case of my implementation, the first one it finds; which one this will be is determined by the behaviour of the search algorithm).

Suppose we have placed 100 tuples into the tuple space, and we want to read them out in the order in which they were written in. The tuple space itself does not know or care about the order in which tuples were placed in it, so we must place an index value in each of the tuples and match on that value: (ANY, index). This incidentally means that we can read the values out in a specified order even if they were not written in in that order.

Consider a writer outputting the results of a breadth-first binary tree traversal, where the nodes are indexed. They might be written out in the order:

5
3              8
1       4     6
2              7

A reader process would be able to pick up the nodes in order, as they became available. Hence, it would block until the writer had written (5, 3, 8, 1), then pick up (1), then block until the writer had written (4, 6, 2), then pick up (2, 3, 4, 5, 6), then block until the writer had written (7), then pick up (7, 8).

Now for an example application, something less theoretical. Suppose we wish to distribute multiple concurrent searches or computations over a bank of several machines. Think SETI at home, or Google. Tuple spaces provide a simple co-ordination language for many collaborating agents to participate in this process. A process (or group of processes) posts tuples and then waits for a response to arrive from somewhere. Another process (or group of processes) looks for tuples like the ones the first (group of) process(es) posted, and responds to them. None of the processes has to know about the existence of any other process for this to work.

Here is a good introduction to the Linda system, which explains the rationale and some typical uses at greater length.