Tuple Data Type.

Nice Notation.

Must admit that i love these parts of Computer Sciences that have elegant, scientific notation.

Tuples / pl: 'Krotki' / are nice that way, as well.

For example:
  (char, int8, int8, string) t1 := ('a', 1, 3, "sample string");
  (int8, int8) t2 := (2,3);


Uses.

Was thinking about how to implement Tuple Data Type in 'Ola' Programming Language.


Preconditions.

i think that every object used with 'Ola' Programming Language ... should have a 'name' string as a part of its runtime state, randomly generated at first, with Random Number Generator initialized with a Time Stamp.

i think it should be possible to rename any/every of object(s).

Succesful working of the Tuple Data Type depends on above preconditions. Without these preconditions, this article should be either edited or removed.


Implementation Considerations.

Was thinking about how to implement Tuple Data Type in 'Ola' Programming Language - and came with that a tuple - internally - should consist of:
- String Array with runtime object names,
- Map where object name string is key and TupleValue is value.
  Invariant: During Map's observable moments, name strings in Map are sorted alphabetically.
  TupleValue has:
  - object's type / not sure yet how to encode it /,
  - object's value / according with it's type /.


Benefits.

1. Using String Array and Map, we provide support for objects graph that can contain cycles.

Names in objects' runtime state are also important tool for avoiding 'infinite recursion' loops in graphs with cycles.


2. Thanks to String Array and Map data types used, it's cheap and easy to find n-th value in a tuple ... both n-th key, as well as n-th TupleValue.

/ Algorithmic time: Worst: O(1) for retrieving key, and Worst: O(1) for retrieving value /


For example:
  (int8, int8, int8) t := (1,5,3);
  String tk := t.getKey(2);
  TupleValue tv := t.getValue(2);


3. We can also quickly get String Array part of a Tuple ... in which an unsorted copy of keyset is kept.

/ Algorithmic time: Worst: O(1) /

For example:
  (int32, int8, int8, int8) t := (15,6,5,3);
  String[] keys := t.getKeys();


4. Giving a name to a tuple value is also cheap and easy,

/ Algorithmic time: Worst: O(1) /

For example:
  (int8, int8, int8) t := (2,4,3);
  t.setName(2, "name for 3");
  // both String Array, as well as Map's key are updated ... both need to be a part of a single atomic operation.


5. Searching for a tuple value by its name is also easy and cheap.

/ Algorithmic time of insertion/lookup in Java's LinkedHashMap is: Amortized Worst: O(1) /

For example:
  (char, int8, string, int8) t := ('2',4,"one",0);
  t.setName(2, "name for one");
  TupleValue tv := t.getTupleValueByName("name for one");


Links.
- Linda & Tuple Space,
- Algorithms' Time-Performance Metrics.

Linda & Tuple Space.

Introduction.

Linda & tuple space are work of Gelernter.

Linda is name derived from porn actress: Linda Lovelace, who later became 'a born again Christian' and a spokeswoman for the anti-pornography movement.




-=- Linda Lovelace. -=-


Linda is a language or notation that is used with tuple spaces, a mechanism that has uses in processes concurrency & synchronization.

There's one big and global tuple space. Processes communicate with each other by putting in the tuple space messages, and by retrieving from tuple space.

Processes are isolated, do not need to know anything about each other, processes do not need to exist at the same time. This helps to decouple objects, increasing software's quality.


'Tuple Space' has uses in the 'Token Game' - for modelling 'places', where tokens are stored, as well. Token Game uses Petri Nets idea, abstracted & concretized different way. Petri Nets are also called P/T Nets or Places / Transition Nets.


Tuple Type, Signature & State.

Tuple's signature is ordered list of data types stored in a tuple.

Tuple has statically determined length.

Tuple's state is it's values written in a binary format, concatenated.

In original work of Gelernter, tuple wasn's a type so a tuple could not contain tuples within. For 'Project Wraithstar's' purposes, tuple is a type.


Simple operations on the tuple space.

* Output(t)

Because of Linda being distributed asynchronous mechanism with the buffer of unlimited size, operation that puts a tuple into space is a nonblocking operation.

Tuple Space should be treated as a Multi-Set, that allows for putting multiple tuples of the same signature and state.

Operation Output(t) puts a tuple into a tuple space. If a tuple t is already present in the tuple space, another copy of t is put in the tuple space.


* Input(s)

A blocking operation that removes a tuple from space. Argument for this method is tuple's signature, for example:

Input(x: int32, c: char) / exact syntax in 'Ola' Programming Language is to be determined still /

If at a given moment there's no tuple with a given signature in the tuple space, then a process performing Input is blocked until requested tuple appears in the tuple space.

In original work of Gelernter, if tuple space contains many tuples with a given signature, then a choice of removed tuple is nondeterministic. There's a rule of fairness in original work as well, but for purpose of 'Project Wraithstar' - we'll assume that tuples with a given signature are put and removed as in a FIFO queue. Similarly processess that attempt to remove a tuple should use a timestamp associated with a request, as a part of UUID / Universally Unique ID /.


* Read(s)

Similar to Input(s), Read(s) retrieves a tuple with it's data from the tuple space - but does not remove it from tuple space.

Read(s) is a blocking operation, and depending on timestamps & UUIDs processess removing or retrieving tuple might be awakened in varying orders & amounts.


* Try_Input(s) and Try_Read(s).

Nonblocking versions of Input(s) and Read(s) methods.


Selective Choice.

There's option of specifying values of tuple's selected elements, of a tuple we wish to remove / retrieve from a tuple space.

For example we can remove a tuple with a signature (int32, char, int32) whose first value is 3. Appropriate instruction looks as follows:

Input(3, c: char, x: int32)


There are differencies between instruction semantics:
- Input (x, c)
- Input (x: int32, c)
- Input (x, c: char)
- Input (x: int32, c: char)


Gaps.

Linda has one more extension. In the tuple space, there can be stored tuples with 'gaps'.

'Gap' is a 'value' of a specified type, that 'matches' to any value of this type.

Gaps are noted as a star with a type.

For example, a tuple:

(3, * : char, 'a', * : int32)

Is a tuple with a signature:

(int32, char, char, int32)

Containing two gaps: on a second and fourth position.


Such tuple can be retrieved or removed from a tuple space, by performing any of given operations:

Input (3, 'c', x: char, 8)
Input (i: int32, x: char, 'a', j: int32)


Let's notice that every 'gap' has a strictly given type.


For putting gapped tuples into space, method Output can be used. In a gap-place we'll just write a type with a variable name, but variable name has no meaning here.

Output (3, c: char)

Will put into tuple space a tuple, that on a second coordinate has a type and is a gap.


Links.
- Linda as Database Management System,
- A written lecture about Linda, in a polish language,
- Linda & Concurrency,
- Tuple Data Type.