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: