Non Standard Vectors and Tuples
A non-standard vector is a vector where the 0th element is not a non-negative integer. The utility
of non-standard vectors is that they can be used to construct other data types like tuples.
Tuples in Shen are not primitive to Kλ but are represented in the Shen sysfile code as non-standard
three element vectors where the 0th element is a tag 'tuple' indicating that the vector represents a
tuple and the next two elements are the first and second elements of that tuple. The basic operations
such as '@p', 'fst' and 'snd' are easily definable as is the recognisor 'tuple?'.
Because tuples are defined internally using Kλ primitives as non-standard vectors, the type system of
Shen does not recognise them as standard vectors and hence, though they can be manipulated using vector
operations they cannot be manipulated like this in a type secure way (i.e. with type checking enabled).
Only '@p', 'fst' and 'snd' can be used. The significance of this is that with type checking enabled, tuples
are immutable objects; that is they cannot be destructively changed with 'address->' or 'vector->', merely
interrogated for their parts or combined into other data structures.
The identity of tuples with non-standard vectors is purely one of convenience. In platforms which support
tuples as a native type, the native type may be used. However the following equations must hold.
1. The recognisor 'tuple?' returns 'true' to tuples, but not to any other type checked Shen datatype.
2. The tuple (@p 1 2) is printed off as such.
3. @p is a two place function which associates to the right; (@p a b c) is just (@p a (@p b c)).
4. (fst (@p a b)) = a and (snd (@p a b)) = b for all a and b.