Assignment 4: 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.

For simplicity the function works at all types, not just tuple types.

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 "datastructure" 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.

On-line Resources

The following Erlang resources may be useful:

• Lectures on Erlang. (see in particular the resource controller example.)
• Exercises 5 and 6 (focus on the part on Erlang) will give you a head start for this assignment.
• Very nice tutorial on Erlang. Section "A Short Visit to Common Data Structures" and later deal with advanced topics, and you won't need to know them for this lab. Earlier sections are very relevant, though.
• Getting Started with the Erlang System.
• Tiny quick-start tutorial for Erlang.
• http://www.erlang.org/ – the Erlang home page. The main source of the following information.
• There is a nice page gathering the documentation of Erlang. See in particular the lists library for useful list processing functions.
• The Erlang Book (part 1) is now available free on line: pdf format. See also the notes on the more recent language extensions
• Some course notes on concurrent programming in Erlang.
• Some advice on Erlang programming style