LINDA - Notes

LINDA is a data-oriented synchronization and communication language mechanism.
It consists of a Tuple Space (TS) into which processes output tuples and from
which processes input tuples.  The commands are process-centric (not Tuple
Space centric), so Out(x,y,z) puts a three-tuple into the TS (outputs it from
the process) and In(a,b) blocks the calling process until a matching two-tuple
can be found in the TS, then when one or more matchin two-tuple is found, one
of the matching two-tuples is removed from the TS and input to the calling
process.  Thus the TS implements a form of distributed associative memory.

Tuples
Tuples may have any number of elements, and the elements are typed.  While
in the TS, the values of the elements within a tuple cannot change; they
remain constant.  Tuples may only be inserted or removed from the TS, they
may not be modified in place.  In some implementations, a read command (Rd)
is supplied to read a tuple without removing it (this is an optimization
for the case in which an In is followed by an Out with the exact same tuple).

Out
The Out construct takes a k-tuple of constants or expressions, evaluates the
expressions and inserts the resulting tuple (containing the computed values)
into the TS.  It does not block.  There may be any number of identical tuples
in the TS (i.e., assuming no In statements remove any of the tuples inserted,
1000 Out("X") statements will result in 1000 1-tuples each consisting of the 
string "X").

In
The In construct is somewhat more complex.  It takes a k-tuple of constants,
expressions, or reference variables as its arguments, then seeks to match
this k-tuple with the tuples in the TS.  Use of reference variables, indicated
by the presence of "?" in front of the variable name, sets the variable to
the corresponding value in the selected tuple, allowing IPC via the TS.

For a tuple to match the template supplied to the In statement, it must
	1) be of the same degree (e.g., a 3-tuple cannot match at 2-tuple,
		only other 3-tuples);
	2) match the element types pairwise (e.g., a 2-tuple consisting of
		a string and an integer cannot match a 2-tuple consisting
		of two strings, nor one consisting of two integers, nor one
		consisting of an integer followed by a string; it can only
		match a 2-tuple consisting of a string followed by an integer);
	3) match the constants or expressions in the template exactly (e.g.,
		the statement In("A", 5) can only match the tuple ("A", 5),
		while the statement In("A", ?x) matches ("A", 5) and ("A", 4),
		but not ("B", 5), assuming that x is of type integer).

If more than one tuple matches the template, then any one of the matching 
tuples may be selected for removal.  If two or more processes execute In
statements that match the same tuple, then at most one of them will remove
the tuple from the TS.

Example 1: Binary Semaphore 

	Semaphore			LINDA
		Semaphore Declaration & Initialization -
semaphore S = 1;	->	Initializer process:
				Out("Semaphore", "S");
		Semaphore Use -
P(S);			->	In("Semaphore", "S");

V(S);			->	Out("Semaphore", "S");

Example 2: Shared Variable Increment
		Declaration & Initialization -
shared int i = N;	->	Initializer process:
semaphore mutex = 1;		Out("i", N);

		Use
P(mutex);			int my_i;
i := i+1;		->	In("i", ?my_i);
V(mutex);		->	Out("i", my_i+1);