source: doc/proposals/tuples.md @ 90be0cf

Tuples
======

This is a proposal discusses update to Cforall tuples as they exist after
the work done by Robert Schluntz (after they were added to Cforall by
Rodolfo Esteves and to K-W C by Dave Till). The new features and ideas
discussed here are designed to address problems that have appeared as tuples
have been used in the past 6 years. Some or all of the changes discussed may
already be implemented.

The core change is breaking the current restructurable tuples into unstructured
and structured tuples. Unstructured tuples handle most of the existing uses,
with structured tuples filling in a few missing use cases.

Current State of Tuples
-----------------------
An overview of the current tuple design is the starting place for the proposal.

### Tuple Syntax

Currently, tuples have three main components: tuple types, tuple
expressions/values (constructing tuples), and tuple index expressions
(deconstructing tuples).

Current syntax for tuple types:

-   Nullary: [void] or []

        [void] f();
        [] f();

-   Unary: [TYPE]

        [int] f();
        [double] x = 1.5;

-   Multiary: [TYPE, TYPE, ...]

        [bool, char] f();
        [short, int, long] x;

Tuple types can appear anywhere regular types may be used, except for the
nullary tuple which can only appear where void can be used (usually return
types), with the exception of special case when void is used to make an empty
parameter list.

Current syntax for tuple expressions:

-   Nullary: (Same as `void`, use return without an expression.)

        [] f() { return; }

-   Unary: EXPR (in return only) or {EXPR}

        [int] f() { return 3; }
        [int] x = {3};

-   Multiary: [EXPR, EXPR, ...]

        [int, int] f() { return [3, 4]; }
        [bool, char, int] x = [true, 'a', 3];

Tuple expressions should be useable whenever an expression of that type is
expected. Issues with the current state will be discussed later.

Current syntax for tuple indexing is an integer constant, where its value
selects a tuple member, e.g.:

        [char, int] tup = ['a', 0];
        char ch = tup.0;
        int value = tup.1;

### Mass and Multi-Assignment

Two special forms of assignment can be used to set values in tuples: mass and
multi.  Mass assignment assigns every element in the destination tuple to a
single source value.

        [int, long, float] dst;
        int src = 4;
        dst = src;
        // Becomes: dst.0 = src; dst.1 = src; dst.2 = src;

Multi-assignment assigns every element in the destination tuple to the
corresponding element in the source tuple. Both tuples must be the same size
and the elements pairs must be assignment compatible conversions.

        [long, int, float] dst;
        [int, char, double] src = [1, 'a', 300.0];
        dst = src;
        // Becomes: dst.0 = src.0; dst.1 = src.1; dst.2 = src.1;

### Tuple Restructuring

Tuples can be restructured as part of overload resolution. Function calls
unpack tuples and repack tuples to match signatures. This semantics is a form
of implicit conversion and is considered during overload resolution.

A simple example is matching multiple parameters of a function to a single
argument expression, where each parameter is bound to a different element of
the returned tuple.

        [int, int] argFunc();
        void parmFunc(int a, int b, int c, int d);

        parmFunc(argFunc(), argFunc());

        // Roughly equivilent to:
        [int, int] fst = argFunc();
        [int, int] snd = argFunc();
        parmFunc(fst.0, fst.1, snd.0, snd.1);

### Tuple Casts

C-style casts can be used on tuples. These are usually conversion casts (casts
that perform operations on the cast type, as opposed to reinterpreting the
existing value).

Tuple casts can remove elements from the end of a tuple and apply a recursive
cast to any of the elements. As an example:

        [char, char, char] x = ['a', 'b', 'c'];
        ([int, char])x;

This casts the first element type of x from a char to an int and drops the last
element. The second line can be replaced with the following code, which creates
a new tuple by directly casting the kept elements of the old tuple:

        [(int)x.0, (char)x.1];

Note, tuple casting is more restricted than the implicit tuple restructuring.
It cannot do any restructuring beyond dropping the trailing elements of
tuples. For example,

        int i; char c; bool b;
        [i, b, c, i] = [i, [b, c], i];
        [int, [bool, char], int] w;
        [i, b, c, i] = w;
        [i, b, c] = ([int, [bool, char]])w;
        // But this does not work:
        [i, b, c, i] = ([int, bool, char, int])w;

### Polymorphic Tuple Parameters

One kind of polymorphic parameter is the tuple type parameter, previously
noted by the `ttype` keyword and now marked by a tailing ellipses (`...`).
Although described as a tuple type, it is usually viewed as its flattened
sequence of types.

        // Fixed Length Max - Base Case:
        forall(T | { int ?>?( T, T ); })
        T max(T v1, T v2) { return v1 > v2 ? v1 : v2; }

        // Variable Length Max - Recursive:
        forall(T, Ts... | { T max(T, T); T max(Ts); })
        T max(T arg, Ts args) {
                return max(arg, max(args));
        }

This feature introduces a type name into scope (Ts). It is used as a type and
the value it declares (args) is a tuple value, and that the second assertion
"T max(Ts);" matches takes a single tuple, but with restructuring it can also
match functions that take a series of non-tuple arguments.

A good way to explain this is to show a partial implementation the following
call `max(int_a, int_b, int_c);` into actual code:

        void _thunk0(int v1, int v2) {
                return max{?>?}(v1, v2);
        }
        void _thunk1([int, int] tup) {
                return max{?>?}(tup.0, tup.1);
        }
        max{_thunk0, _thunk1}(int_a, [int_b, int_c]);

The part to highlight is that "_thunk1", one of the functions created to
make an inexact match that can be used as a call site into an exact match
so the function can be passed through function parameters.
Although, the tuple type `[int, int]` matches a parameter list `int, int`,
just with a bit of low lever restructuring.

In larger cases (with four or more parameters in the first case), the
recursive case will work similarly, creating an intermidate function to
restructure the tuple into a new call such as:

        void _thunk2([int, int, int] tup) {
                return max{_thunk0, _thunk1}(tup.0, [tup.1, tup.2]);
        }

Issues with the Current State
-----------------------------
There are a variety of problems with the current implementation which need to
be fixed.

### Tuples are not Objects

Spoilers: this proposal actually takes them even further away from being
objects, but illustrates why the current version is not as useful is it could
be.

Tuples do not have the lifetime operators (copy construction, copy assignment
and destructor) that define an object type in Cforall. This means they are
not polymorphic otypes, they are objects in C's usage of the word. This means
that tuples cannot be used as a single object in

There are several reasons for this. The fluid nature of tuples (flattening
and restructuring) means that matching against a tuple type is fluid in some
inconvent ways.

        forall(T, U) void ?{}([T, U] & this;
        void ?{}([int, int, int] & this);
        // What constructor(s) should be used here?
        [int, [int, int]] pair;

Should the polymorpic constructor be applied twice or should the tuple be
restructured and the three element constructor be used? This is not really
something a user should be wondering about (especially since tuples should
always be simple containers wrapping their elements).

### Providing TType Arguments is Inconsistent

The syntax for ttype arguments is slightly inconsistent. It has not come up
much yet, because you do not directly provide ttype polymorphic arguments to
functions and there are very few existing use-cases for ttype structures.

        forall(T, Us...)
        void function(T head, Us tail) {}

        forall(T, Us...)
        struct Type {};

        int a;  bool b;  char c;
        function(a, b, c);
        function(a, [b, c]);
        // Doesn't work: Type(int, bool, char) x;
        Type(int, [bool, char]) x;

The `function` case works either way because the tuple value can be
restructured if it does not match exactly. The `Type` case though does not
allow restructuring when the type is passed as a type value. This may be
the most correct form, but seems surprising compared to the common use.

### Unary Tuple Value Syntax

Unary tuples don't use the standard tuple syntax and one of the two alternate
syntax options your may use instead doesn't work consistently. Solving both
of these issues would help with consistency.

### Syntax Conflict

The tuple syntax conflicts with designators and the C23 (C++-style) attribute
syntax.

        int a[10] = { [2] = 3 };

Here [2] = 3 is an array designator, but has the same syntax as an assignment
to a tuple of references, it isn't until the resolver determains that 2 is
not a reference that that case can be ruled out.

        [[ unused ]] [[int, int], int] x;

Here the opening `[[` could be a nested tuple or the beginning of an
attribute, the parser can't figure out until later.

These conflicts break C compatibility goals of Cforall. Designators had to
their syntax change and Cforall cannot parse the new attributes.
The behaviour of these cases, if they could be parsed, should be unchanged.

Change in Model
---------------
This proposal modifies the existing tuples to better handle its main use
cases. There are some use cases that are no longer handled, so in addition
to changing the existing "restructured tuples" to "unstructured tuples"
(or packs) a new "structured tuple" is added in the form of struct tuple.

The new tuples is even more "unstructured" than before. New tuples are
considered a sequence of types or typed entities. These packs are then unpacked
into the surrounding context. Put differently, tuples are now flattened as much
as possible, with some places (like parameter lists) being treated as an
implicit tuple and the tuple being flattened into that.

Structured tuples are now a separate feature: a structure called "tuple".
These are polymorphic structures; an instance should act as a structure, except
its fields are accessed using indices instead of field names. Experience so far
is that structured tuples are not used often, but fill in the use cases that
unstructured tuples no longer support.

Note that the underlying implementation might not actually look like this,
but this is how it should seem to the user.

Changed Features
----------------
Some of the concrete changes to the features of the language.

### Unstructured Tuple / Pack Type

The evolution of our current tuples (called packs in an attempt to make the
names more distinct). They work like the current tuples except they are
always flattened. You might still be able to declare nested tuples, but these
are not meaningful, they are flattened to a single level and, where
approprate, is inlined into the sounding content.

        [bool, [char, int], long] x;
        // Becomes:
        [bool, char, int, long] x;

        void f(bool a0, [char, [int, long]] a1, float a2);
        // Becomes:
        void f(bool a0, char a1_0, int a1_1, long a1_2, float a2);

        [,] f(int a0, [,] a1, [bool,] a2);
        // Becomes:
        void f(int a0, bool a2);

This actually means that tuples do not participate in overload resolution
in the way the do currently. Restructuring is always free because they are
always reduced to the same form as part of type matching.

Packs are still not object types and do not have lifetime functions. They
cannot be used as object types, nor as any data type, but they can be still
used as ttypes.

(Unless they need to have lifetime functions for other features.)

### Structured Tuple Type

There is a standard library or built-in type named `tuple`, it does not need
a special syntax to write types or values. The type definition might need
some primitive support, but if supported as a regular type would look
something like this:

        forall(Ts...)
        struct tuple {
                inline Ts all;
        };

This type wraps up an unstructured tuple, in this case a pack of members,
and gives it "edges" and so structure. It also gives tuples an interface
more like a normal structure type, for the anonymous structure use case.

The struct tuple does have lifetime functions, can use list initializer
syntax and otherwise be treated as a normal structure. You can use regular
member access syntax to convert the struct tuple into a unstructured pack,
writing `object.all`.

The `inline` modifier is a new specialized feature to allow you use tuple
index expressions directly on the type. With or without inline you should
be able to chain a tuple index expression onto the member expression, such
as `object.all.1`. The inline specifier allows you to skip the middle
and use `object.1`.

More complex operations can usually be preformed by taking the pack out of
the struct tuple and acting on it. Polymorphic operations only have to go one
level down to get to base operations, there is no need for recursive
construction, nor manually coding different sizes of tuple. This should give
most of the ease of working with a primitive tuple, because effectively you
are except it has been given fixed edges.

A tuple struct should also be an object type, and let's you pass multiple
values through a single polymorphic slot.

A note on the naming here, because there are more pieces that need names
instead of symbols. The name `tuple` follows because that is the common name,
although this means this is now the default tuple in some sense. The name of
the pack was picked to work with inline and make the difference between `.0`
and `.all` clear. (If inline doesn't work then `get` might be a better name.)

### Type Qualifier Distribution

Because tuples are no longer object types, applying type modifiers to them,
such as cv-qualifiers and pointers, no longer makes sense. That syntax is
now considered distribution, applying the type modifier to each element of
the tuple.

Previously `const [int, bool] &` would mean a const reference to a tuple of an
integer and a boolean. Now it means an alias for `[const int &, const bool &]`,
a tuple of a reference to a constant integer and a reference to a constant
boolean. This also applies to polymorphic tuple type packs `Ts &` in
polymorphic functions.

This new approach can specify restrictions on tuple variables as for a single
type variable. For example, this approach can replace the special cased tuple
operations multi-assignment (N-to-N) and mass-assignment (1-to-N).

        // Multi-Assignment
        forall(T, Us... |
                        { T & ?=?(T &, T const &); Us & ?=?(Us &, Us const &); })
        [T, Us] & ?=?(T & dst, Us & dsts, T const & src, Us const & srcs) {
                dst = src;
                dsts = srcs;
                return [dst, dsts];
        }

        // Mass-Assignment
        forall(T, U, Vs... |
                        { U & ?=?(U &, T const &); Vs & ?=?(Vs &, T const &); })
        [U, Vs] & ?=?(U & dst, Vs & dsts, T const & src) {
                dst = src;
                dsts = src;
                return [dst, dsts];
        }

These may not work exactly as given (for one, the copy assignment assertion
in the first function would likely be redundant/conflicting with the implicit
assertions on the parameters), but they show the pattern. Multi-assignment
also would be very hard to write with simple tuple types, because the
relationship between the two halves of the parameter list does have to line
up, that cannot be enforced with two different tuples.

This example doesn't have to be implemented this way because we do have the
special case operations for these already.

### Type Packs

This approach is not a new feature, but a reframing/extension of existing tuple
tuple polymorphic parameters as polymorphic type packs. The old `Vars...`
syntax introduces a pack of types into scope. It can be used in much the same
way as a tuple, but in some new ways to.

The primary existing use remains: to use a polymorphic pack in a parameter
list, both as part of an assertion and in the signature of the main
function. The difference is that this is not an enclosed tuple, but a series of
types. The only effective difference this makes is it does not prefer to match
another tuple/pack.

This pattern continues to a parameter defined with a pack of types, which
is considered a pack of parameters, and the name it introduces is a pack
of variables, or a flattened tuple.

        forall(Params...)
        void function(Params values);

New use cases include declarations of members and variables. For example, the
creation of a structured tuple structure:

        forall(Fields...)
        struct tuple {
                Fields get;
        };

This is again, treated as a pack of members. They have the same layout as
if they were written out by hand. Now, the name get is still accessed as if
it was a regular, singular, member. The result of that expression is a
pack expression, a tuple of all the field accesses, which can be used with a
tuple index expression to access the underlying members. For example:

        tuple(bool, char, int) data = { ... };
        // This expression:
        data.get.2;
        // Is the same as (if the fields had these names):
        data.[__anonymous0, __anonymous1, __anonymous2].2;

For local declarations it works similarly, except the name introduced is
directly usable as a tuple instead of going through a member access.

        forall(Objects...)
        void function( ??? ) {
                ???
                Objects objs = ???;
                ???
        }

### Tuple Pack Restructuring

Implicit restructuring still occurs, but is not considered as part of
overload resolution. The structure of tuples is ignored, where individual
tuples begin or end is not considered, just the sequence of types.

This can be viewed as flattening both sides (the arguments/caller and the
parameters/callee) before type resolution. Both any nested packs and packs
into any larger context:

        call(false, ['a', [-7,]], 3.14)
        // Inline Nesting:
        call(false, ['a', -7], 3.14)
        // Inline into Context:
        call(false, 'a', -7, 3.14)

The main context where tuples are inlined are parameter lists, in that you
can consider a parameter list as a single pack. Return types could be viewed
in this way, but because they are presented in a single type, they are
already wrapped in a tuple.

        [int, [bool, char]] f();
        // Inline Nesting:
        [int, bool, char] f();

This also happens "after" any polymorphic parameters are instantiated.

Empty packs are also collapsed, logically being removed or replaced with
void as in the following example:

        // For example, this function:
        forall(Ts...) Ts example(int first, Ts middle, int last);
        // With Ts = [,], should not be treated as:
        [,] example(int first, [,] middle, int last);
        // But instead:
        void example(int first, int last);

Or closer to it, there are some slight differences between the nullary tuple
and void, for instance creating some instances for consistency with the other
tuple types.

The struct tuple is never implicitly restructured.

### Tuple Declaration/Deconstruction

Declaring a tuple acts as a pack of variable declarations. When this is done
with a written out type (as opposed to a polymorphic parameter above), then the
elements of the tuple can be named.

        [int quo, int rem] quorem = divmod(a, b);

Here `ret` refers to the tuple, the entire pack, while `quo` and `rem`
give explicit names to elements of the tuple. Not all the names have to be
provided, at the very least, any element name can be omitted if the pack name
is provided, and the pack name can be omitted if all the element names are
provided. That would ensure every element can be accessed, but it could be
reduced even more, effectively immediately dropping some values if there is
no named to access it.

This does not add any new functionality, more it is a qualify of life feature
making it very easy to give elements of a tuple descriptive names
instead of trying to combine a name for the whole tuple with an index.
(`quo` and `rem` vs. `quorem.0` and `quorem.1`)

### Tuple Casts

Tuple casts are no longer allowed to do any restructuring. Internal
restructuring would not be useful, as there is no internal structure.
Dropping tail elements could be added back in but it is a narrow use case
so it may be replaced with other features (for example: tuple slicing).

        // Allowed:
        ([bool, short])tuple_bool_char;
        ([int, float])tuple_float_float;

        // Forbidden:
        ([int, int, int])tuple_int_int;
        ([long, [float, int]])tuple_long_float_int;

### New Tuple Literal Syntax

In addition to the main redesign of this proposal, the syntax is updated to
be more consistant. It is now a "[]" list with "," separators and a ","/comma
terminator that is optional for tuples with 2 or more elements (those that
already have a comma in them) and manditory in other tuples.

It should also be symmetric between types and value, differing only in that
an element (ITEM below) of a tuple type is a type and the element of a tuple
value is a value.

-   Nullary Tuple: [,]
-   Unary Tuples: [ITEM,]
-   Multiary Tuples: [ITEM, ITEM] [ITEM, ITEM,] [ITEM, ITEM, ITEM] ...

Currently, although syntax is provided to write them, but manually writing
a nullary or unary tuple should be very rare. This is because a nullary tuple
can either be erased or treated as void, while unary tuples can be treated
as their element type. Similary for nested tuples, can be treated as the
flattened tuple.

(Update: Orignal nullary tuple proposal was `[]`, but that had some issues.)

### TType Argument Syntax

It would be nice to seamlessly provide packs of types in polymorphic
argument lists, however doing so requires a new restriction.

As an example of the change, consider providing arguments to a polymorphic
structure with a otype and a ttype parameter.

        forall(T, Us...) struct D {...};
        D(int, [,])            // D(int)
        D(bool, [char,])       // D(bool, char)
        D(long, [int, short])  // D(long, int, short)

This is a nice syntaxtic improvement for the common case, it does restrict
some of the more complex cases, such as cases with two ttypes. There are
various restrictions on this for functions. If the rules make it unambigous
then the grouping could be omitted, or a more advanced version, it can be
ommited only in the indivual cases where it is unambigous.

### Tuple Slicing (Range Tuple Indexing)

(Disclaimer: this is a bit more impulsive, see end for notes.)

This is an extension to tuple indexing. Currently, only single location of a
tuple can be index, extracting the element at that location. By extending the
index expression to be a list-range a multiple sub-tuples can be extracted.

        ['a', 'b', 'c', 'd', 'e', 'f'].0~3
        ['a', 'b', 'c', 'd', 'e', 'f'].1~5~2
        // Produces:
        ['a', 'b', 'c']
        ['b', 'd']

In words, the first indexes the first 3 tuple elements (0, 1, 2, stopping
before index 3) and the second indexes elements starting at index 1, stoping
before index 5 going in steps of 2. This does not allow for arbitary
selections, but it covers many common slices.

To get the new tuple, the range has to be constructed and traversed at compile
time. The size of the range is the size of the result tuple, with each element
in the result tuple decided by the matching element of the range, which gives
the index of the original tuple to place there.  The type of the indices may be
an integral type, but all indices must be in range, otherwise it is a compile
time error.

In terms of the existing range loops, if you could write this dynamically, it
would look something like this:

        // Implementation of: output = input.RANGE
        dyn output = []
        for ( index : RANGE ) { output = [output, input.index] }

The result of the expression is only has to be considered a tuple if the
range has two or more values, otherwise it can be considered void or the same
as indexing the single value in the range.

Some closing notes, this is dependent on generalized range expressions.
The iterators proposal has a section on some new range types, this feature
is intended to be built on that feature. Not simply reuse some of the syntax
that is also used in the special for loop. This may add some requirements
about the compile-time evaluation on range expressions to make sure these
expressions can be evaluated at compile-time.

Implementation
--------------
An overview of the implementation details of the new proposal.

### Structured Tuple

There is actually a decision point here. If it can be implemented entirely
in the standard library, that would be good. If it cannot, it can actually
be implemented as the same primitive implementation as we use now and may be
how unstructured tuple packs are implemented.

### Member Pack Implementation

Implementing member packs can use the same pattern as current built-in tuple
syntax. This is a two stage process, first is by ... then the it can be
handled by the existing code for polymorphic but not variadic structures.

        forall(Ts...)
        struct tuple {
                Ts get;
        };

So when used with diffences length an hidden declaration is created which
has the pack parameter replaced with the approprate number of object type
parameters. Such as in the following examples:

        struct tuple$0 {
        };

        forall(Ts$0)
        struct tuple$1 {
                Ts$0 get$0;
        };

        forall(Ts$0, Ts$1)
        struct tuple$2 {
                Ts$0 get$0;
                Ts$1 get$1;
        };

Then it can be handled by the regular boxing code. Detection of these cases
will have to changed because it is no longer a single case. But the pattern
does work if the structure has additional fields in it, as they are just
placed before and after the pack.

        forall(U, Ts...)
        struct blob {
                int header;
                Ts data;
                U footer;
        };

        forall(U, Ts$0, Ts$1)
        struct blob$2 {
                int header;
                Ts$0 data$0;
                Ts$1 data$1;
                U footer;
        };

The `inline` member pack just effects the resolver. It should be expanded out
to the member access and then the tuple index expression.

### Local Declaration Pack

Packs of local declarations can be handled very differently if they are
concrete or not. Concrete packs can be writen out in full (even if some
individual elements are polymorphic) can be inlined directly, expanding out
into a series of object declarations.

        [A, B] local = func();
        call(local);

        A local$0;
        B local$1;
        ?{}([&local$0, &local$1], func());
        call([local$0, local$1]);

In the polymorphic case though, that entire group needs to be reduced to a
block that can put into a generic function. Here we can use something like
the currently existing implementation, where the entire tuple an opaque
bundle, passed to adapters and thunks for handling.

This is also how tuple declarations are implemented. In the concrete case the
element names are real and the pack name is replaced with a tuple expression
of the elements. In the polymorphic case the pack name is real and the
element names are replaced with tuple index expressions.

### Unstructured Tuple Implementation

Unstructured tuples have two general implementation stratagies. Either they
are erased and the packs inlined into their context, or they are wrapped
up as like a structured tuple, generally using the current implementation.

For example, if a concrete pack (size and all the types are known), appears
in a parameter list the pack can be split and inlined into the argument list.

        void function(int a, [bool, char, short] b, float c);
        // Becomes:
        void function(int a, bool b0, char b1, short b2, float c);

On the other hand, if a polymorphic pack appears in the same place, it will
have to be wrapped up in a dynamic structure so it different instances can

        forall(Ts...)
        void function(int a, Ts b, float c);
        // Becomes (after the implicit packing and unpacking operations):
        forall(T)
        void function(int a, T* b, float c);

### AST Updates

The AST may already be capable of representing most of this. I have only
identified one feature that definitely will now work in the current AST, and
that are the object like tuple declarations with named elements.

Particularly, an object declaration cannot name elements of the tuple.
To this end a new node type, `TupleDecl`,
should be added to handle tuple deconstruction declarations
(other cases can still be handled with `ObjectDecl`).

This would act much like a `FunctionDecl` except for tuples, narrowing the
possible types, to `TupleType` instances instead of `FunctionType` instances,
and storing some additional information. In this case, the names of the
elements of the tuples.

(I'm not actually going to decide the implementation now, but some early
examination of the problem suggests that it might be better off wrapping a
series of `ObjectDecl` rather than just some strings to hold the names.)

Related Features in Other Languages
-----------------------------------
Other languages have similar features. Organized by the related feature,
then language (this does mean we can and do hit languages multiple times).

(In hindsight, I may have gone overboard with the number of examples.)

### Structured Tuples

There are many languages with structured tuples. Usually just called tuples,
but they usually follow the same rules as a polymorphic anonymous structures,
that is to say N types are provided to create a new N-arity tuple. They also
usually have some special syntax to index the tuples, because there are no
field names.

#### Rust

Rust has the standard tuples as a primitive in the language. Each arity of
tuple is a different polymorphic type.

Tuple types and expressions are written with a parenthesized, comma separated
list of types or expressions. To avoid confusion with the grouping "(...)",
one-element tuples must have a trailing comma (and larger tuples may have a
trailing comma).

        const empty: () = ();
        const single: (usize,) = (12,)
        const double: (usize, isize) = (34, -56);

Element access uses similar syntax to field access (that is "."), but uses an
integer literal instead of a field name (for example: "pair.1"). Tuples
support pattern matching with similar syntax to their expression form.

Some tuple features only apply up to 12-arity tuples.
It is not directly stated, but I believe the difference in the more limited
features are implemented in the standard library, one for each arity of tuple.

-   https://doc.rust-lang.org/std/primitive.tuple.html
-   https://doc.rust-lang.org/reference/types/tuple.html
-   https://doc.rust-lang.org/reference/expressions/tuple-expr.html

#### C++

Implemented as a template type defined in the standard library. No special
language features exist to support this, due to the power of C++'s template
meta-programming.

C++ is also one of the few languages with support for variadic polymorphic
types, so there is one template that defines all the types. It is written
as `std::tuple<TYPE...>`, where "TYPE..." is any number of comma separated
types. This is the standard notation for template type instances.

There is no special syntax for member access of a tuple. A template function is
used, e.g., `std::get<0>( tuple )`.

C++ is an interesting case because it is one of the few cases where no part
of the tuple system is built-in. It is entirely created in the standard
library using templates. This also has massive error messages when something
goes wrong, hopefully our version of struct tuple will reduce the problem.

C++ also has structured binding, a kind of limited pattern matching. In a
structured binding declaration, you can write an auto typed declaration where
a list of identifiers in a `[]` replaces the single identifier.

        auto [first, second] = getSize2Tuple();

The base type has to be `auto` because the base type for each element varies.
Still, qualifiers (cv and reference) on the auto will be distributed to types
on the individual members.

The type bound to the binding may be an array, a "plain" structure or any
type that implements the tuple-like interface (`std::tuple_size` and
`std::tuple_element`).

-   https://en.cppreference.com/w/cpp/utility/tuple
-   https://en.cppreference.com/w/cpp/language/structured_binding

#### Haskell

Haskell has a special syntax for tuples, but otherwise they are completely
normal polymorphic types. Because of this, tuples have a maximum size.
Haskell (98) supports tuples of up to 15 elements and the standard library
has functions for tuples of up to 7 elements.

The syntax for tuples is a comma separated list of elements. Either element
types to create a tuple type, or element values to create a tuple value. The
context decides among them, such as `(6, "six")` or `(Bool, Char, Int)`.

Also all the elements can be removed, getting an expression like "(,)" or
"(,,,)", which can be then be used as a function, for a type, or an expression.

Haskell supports pattern matching as the main way to extract values from a
tuple, although helper functions "fst" and "snd" are provided for field
access on two element tuples.

Haskell does not have 0 or 1-element tuples. The nil type, written "()" for
both type and value, is effectively the 0 element tuple. There is also a type
called "Solo" that is a polymorphic structure with one field and is used as
the 1-element tuple, but has regular Haskell data-type syntax.

-   https://www.haskell.org/onlinereport/basic.html

#### OCaml

OCaml only supports multi-element (2 or more) tuples.  It does have the `unit`
type, which has one value, written `()`. Tuple types are written as a '*'
separated list of types, tuple values are written as ',' separated list of
expressions. Pattern matching tuples is supported and uses the same syntax as
values. Parenthesizing these lists is only needed for grouping.

-   https://ocaml.org/docs/basic-data-types#tuples

#### Swift

Swift has tuple types that use the basic parenthesized, comma separated list of
types or values. It only supports 0 and 2 or more element tuples (the `Void`
type is an alias for the empty tuple type).

Swift also supports named tuples. Names can be added before the tuple element,
both for the tuple type and value. The syntax is a name followed by a colon,
e.g., `(first: int, second: int)`. These names are a fixed part of the type,
and can be used as part of field access notation (otherwise numbers are used
in-place of field names `tuple.0` vs. `tuple.first`).

-   https://docs.swift.org/swift-book/documentation/the-swift-programming-language/types/#Tuple-Type

#### Python

In Python tuples are immutable lists. Because they are dynamically typed,
there is only one tuple type `tuple`.

It also has various named tuples. The first, namedtuple, allows naming the
elements of the tuple. The second, NamedTuple, is actually a way of creating a
typed record in a normally untyped language.

-   https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range
-   https://docs.python.org/3/library/collections.html#collections.namedtuple
-   https://docs.python.org/3/library/typing.html#typing.NamedTuple

#### LISP
As LISP is dynamically typed, its `cons` data type is an untyped pair and is
(perhaps infamously) the main constructor of all compound data types.  The
function `cons` takes two arguments and builds a pair. Functions `car` and
`cdr` get the first and second elements of the pair.

### Packs
Packs (or unstructured tuples) are a much less common feature. In fact, there
might just be one language, C++, that supports packs. The most common use
case for unstructured tuples is returning multiple values, so there is a
comparison to languages that have that as a special feature.

#### Go
Go does not have built in tuple types, but it has multi-return syntax that
looks like the tuple syntax of many other languages.

```
func main() {
        i, j := returnIntInt()
        ...
}

func returnIntInt() (int, int) {
        return 12, 34
}
```

Go can unpack multiple return values and pass them all to a function, but
the unpacked tuple must match the parameter list exactly.

```
func acceptIntInt(a int, b int) {
        fmt.Println(a, b)
}
```

-   https://golangdocs.com/functions-in-golang
-   https://go.dev/src/go/types/tuple.go

#### Lua
Lua is a scripting language that is dynamically typed and stack based. Although
the stack is usually only directly visible in the C-API, it does allow any
function to return any number of values, one, zero or more, from any return
expression.

```
local funcion f()
        return 12, 34
end

local i, j = f()
```

The last argument in an argument list can be an expression - function call -
with multiple results and all the results are passed to the function after
other arguments.

Because Lua is dynamically typed, multiple return values are allowed anywhere
and the length of the value listed is adjusted, discarding any extra values
and filling in new values with the value `nil`. This is also used if a
function is called with the incorrect number of arguments.

-   https://lua.org/
-   https://lua.org/manual/5.4/manual.html#3.4.12

#### C++

We return to C++ to view template parameter packs. These are the symmetric
with our pack feature (and both are even used to construct the structured
tuples in the last section).

C++ template parameter packs are a modification that can be applied to any
template parameter, so the parameter now takes a series of arguments instead
of just one. These are used in pack expansion,
which usually expand to a comma separated list, but it can also be a chain of
boolean binary operator applications. For example, if the parameter
`typename... Ts` is in scope, then you can declare `std::tuple<Ts...>` to
introduce a tuple type, if Ts = bool, char, int then the type becomes
`std::tuple<bool, char, int>`.

A common use is for perfect argument forwarding, which shows some different
uses of the pattern:

```
template<typename inner_t>
class Outer {
        inner_t inner;
public:
        template<typename... Args>
        Outer(Args&&... args) : inner(std::forward<Args>(args)...) {}
};
```

In the first application, `Args&&... args` both uses a pack and introduces
another one. `Arg0&& arg0, Arg1&& arg1, Arg2&& arg2, ...` is the pattern
it expands too. The `&&` is used to copy the argument type's reference
qualifier (the default can strip references away).

The second application, `std::forward<Args>(args)...` uses two packs. These
are expanded in parallel, and must be the same length (in this case they
always will be). It also helps show that the `...` is actually the bit doing
the expansion, it is a suffix "operator" to the expansion pattern.

There are also fold expressions that use binary operators to combine a pack
into a single expression. For example, you can write a variadic sum function
that compiles down to the primitive additions.

```
template<typename... Args>
int sum(Args&&... args) {
        return (args + ... + 0);
}
```

C++ is about the best you could ask for in this area, but it does a lot of work
at compile time to make this happen.

-   https://en.cppreference.com/w/cpp/language/template_parameters
-   https://en.cppreference.com/w/cpp/language/parameter_pack
-   https://en.cppreference.com/w/cpp/language/fold