Deadlines

Lab 3: Linda tuplespace

The objective of this assignment is to design and implement an Erlang module which implements a Linda-style tuple space and provides some of the standard tuple-space primitives.

The Interface

The interface to the module must consist of the following collection of functions:

new() – returns the PID of a new (empty) tuplespace.

in(TS,Pattern) – returns a tuple matching Pattern from tuplespace TS. Note that this operation will block if there is no such tuple.

out(TS,Tuple) – puts Tuple into the tuplespace TS.

Representing Tuples and Patterns

In the interface functions, tuples are naturally represented by Erlang tuples. The representation of patterns – in the definition of the in function - should use a single "wild card" pattern any. The following Erlang function match defines when a pattern (the first argument) matches a given tuple (the second argument):

match(any,_) -> true;

match(P,Q) when is_tuple(P), is_tuple(Q)
                -> match(tuple_to_list(P),tuple_to_list(Q));
match([P|PS],[L|LS]) -> case match(P,L) of
                              true -> match(PS,LS);
                              false -> false
                         end;
match(P,P) -> true;
match(_,_) -> false.

Implementation and Submission Notes

The implementation of the tuplespace does not have to use an efficient data structure – although ideally your code should be written is such a way that it should be easy to replace your internal representation of the tuplespace with a more efficient one.

Requirements

• Together with a tuplespace module, your files should also contain a module which briefly explains, using runnable examples, how the tuplespace module is to be used. These examples should also help test the tuplespace.

• When you write your tests for the module make sure that you use concurrency. You cannot reasonably test a concurrent "data structure" using a single thread. In addition, your test should demonstrate that the in(TS,Pattern) is indeed a blocking primitive. We strongly suggest that the implementation is also tested against this self-explanatory script. However, your own tests must be original.

• In order that bugs are easier to notice (for all of us) please use spawn_link function instead of spawn

• Make sure that your tuplespace will work for any tuples – do not assume that client tuples will never contain certain atoms. A client should not be able to break the implementation by inserting "bad" tuples. The proper way of ensuring that is through tagging, as outlined in the Erlang Programming Rules here and here.

• Whenever your solution uses communicating processes, use unique references for associating a response with a request. Hint: use make_ref().

• Your solution may not have polling (one symptom is for example sending messages from the server to the server itself).

• You must name your tuplespace module ts.erl

• Make sure that your submission works with the test.erl module mentioned earlier.