Assignment 3: Linda in Erlang

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.
• Your solution may not have polling (one symptom is for example sending messages from the server to the server itself).
• Please name your tuplespace module ts.erl
• Please include the file test.erl (described above) in your submission.

On-line Resources

The following Erlang resources may be useful:

• Lectures on Erlang. (see in particular the resource controller example.)
• Exercises 5 and 6 (especially the part on Erlang) will give you a head start for this assignment.
• 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
• Getting Started with the Erlang System. You might want to jump straight to the quick-start version.
• Some course notes on concurrent programming in Erlang.
• Some advice on Erlang programming style