Changeset 12c4a5f for doc/proposals


Ignore:
Timestamp:
Oct 23, 2024, 4:18:15 PM (8 weeks ago)
Author:
Andrew Beach <ajbeach@…>
Branches:
master
Children:
90be0cf
Parents:
42d81a7
Message:

Folding in feedback to the tuple proposal and rewriting the last rewrite.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/proposals/tuples.md

    r42d81a7 r12c4a5f  
    22======
    33
    4 Tuples were introduced by Dave Till in K-W C, added to CFA by Rodolfo Esteves,
    5 and extended by Robert Schluntz. This proposal discusses updates for CFA tuples
    6 to address problems that have appeared in their usage over the past 6 years.
    7 The proposal attempts to address problems by adding new functionality, updating
    8 existing features, and removing some problematic ones.
     4This is a proposal discusses update to Cforall tuples as they exist after
     5the work done by Robert Schluntz (after they were added to Cforall by
     6Rodolfo Esteves and to K-W C by Dave Till). The new features and ideas
     7discussed here are designed to address problems that have appeared as tuples
     8have been used in the past 6 years. Some or all of the changes discussed may
     9already be implemented.
    910
    1011The core change is breaking the current restructurable tuples into unstructured
    … …  
    1415Current State of Tuples
    1516-----------------------
    16 An overview of the current tuples design is the starting place for the proposal.
     17An overview of the current tuple design is the starting place for the proposal.
    1718
    1819### Tuple Syntax
    … …  
    2223(deconstructing tuples).
    2324
    24 Current syntax for tuple types.
     25Current syntax for tuple types:
    2526
    2627-   Nullary: [void] or []
     28
     29        [void] f();
     30        [] f();
     31
    2732-   Unary: [TYPE]
    28 -   Nary: [TYPE, TYPE, ...]
    29 
    30 Tuple types can appear in a function return and parameter declaration, or a
    31 tuple variable declaration. Note, the Nullary tuple is only meaningful in the
    32 return context,
    33 
    34         void f(...);   // equivalent
    35         [void] f(...);
    36         [] f(...);
    37 
    38 as C does not support a void declaration.
    39 
    40         int f( void x );    // disallowed
    41         int f( [void] x );
    42         int f( [] x );
     33
     34        [int] f();
     35        [double] x = 1.5;
     36
     37-   Multiary: [TYPE, TYPE, ...]
     38
     39        [bool, char] f();
     40        [short, int, long] x;
     41
     42Tuple types can appear anywhere regular types may be used, except for the
     43nullary tuple which can only appear where void can be used (usually return
     44types), with the exception of special case when void is used to make an empty
     45parameter list.
    4346
    4447Current syntax for tuple expressions:
    … …  
    4649-   Nullary: (Same as `void`, use return without an expression.)
    4750
    48         [] f( ) { return; }
    49         [] f( ) { return [] ; }
    50 
    51 -   Unary:
    52 
    53         [int] f( ) { return 3; }
    54         [int] f( ) { return [3]; }
    55 
    56 -   Nary: [EXPR, EXPR]
    57 
    58         [int,int] f( ) { return [3,4]; }
    59 
    60 Currently, there is a parsing problem for nullary and unary tuple expression,
    61 which is being looked at. Hence, only these two forms work.
    62 
    63         [] f( ) { return; } // nullary
    64         [int] f( ) { return 3; } // unary
    65    
     51        [] f() { return; }
     52
     53-   Unary: EXPR (in return only) or {EXPR}
     54
     55        [int] f() { return 3; }
     56        [int] x = {3};
     57
     58-   Multiary: [EXPR, EXPR, ...]
     59
     60        [int, int] f() { return [3, 4]; }
     61        [bool, char, int] x = [true, 'a', 3];
     62
     63Tuple expressions should be useable whenever an expression of that type is
     64expected. Issues with the current state will be discussed later.
     65
    6666Current syntax for tuple indexing is an integer constant, where its value
    6767selects a tuple member, e.g.:
    6868
    69         [char, int] tup;
    70         tup = ['a', 0];
    71         char ch = t.0; // select first tuple member
    72         int value = t.1; // select second tuple member
     69        [char, int] tup = ['a', 0];
     70        char ch = tup.0;
     71        int value = tup.1;
    7372
    7473### Mass and Multi-Assignment
    … …  
    7978
    8079        [int, long, float] dst;
    81         int src = 4
    82         dst = src;  // => dst.0 = src; dst.1 = src; dst.2 = src
     80        int src = 4;
     81        dst = src;
     82        // Becomes: dst.0 = src; dst.1 = src; dst.2 = src;
    8383
    8484Multi-assignment assigns every element in the destination tuple to the
    8585corresponding element in the source tuple. Both tuples must be the same size
    86 and the elements assignment compatible => conversions.
     86and the elements pairs must be assignment compatible conversions.
    8787
    8888        [long, int, float] dst;
    8989        [int, char, double] src = [1, 'a', 300.0];
    90         dst = src;   // => dst.0 = src.0; dst.1 = src.1; dst.2 = src.1
     90        dst = src;
     91        // Becomes: dst.0 = src.0; dst.1 = src.1; dst.2 = src.1;
    9192
    9293### Tuple Restructuring
    … …  
    110111        parmFunc(fst.0, fst.1, snd.0, snd.1);
    111112
    112 There are few languages supporting multiple return-values as a standalone
    113 feature (SETL). Go has multiple return-values but restricts their use in
    114 matching arguments to parameters.
    115 
    116         func argFunc() (int, int) {
    117             return 3, 7
    118         }
    119         func parmFunc( a int, b int ) {
    120              fmt.Println(a, b )
    121         }
    122         func main() {
    123              parmFunc2( argFunc() ); // arguments must match exactly with parameters
    124         }
    125 
    126113### Tuple Casts
    127114
    … …  
    150137        [int, [bool, char], int] w;
    151138        [i, b, c, i] = w;
    152         [i, b, c, i] = ([int, bool, char, int])w; // fails
    153         [i, b, c] = ([int, [bool, char]])w; // works
     139        [i, b, c] = ([int, [bool, char]])w;
     140        // But this does not work:
     141        [i, b, c, i] = ([int, bool, char, int])w;
    154142
    155143### Polymorphic Tuple Parameters
    … …  
    160148sequence of types.
    161149
    162         forall( T | { int ?>?( T, T ); } )
    163         T max( T v1, T v2 ) { return v1 > v2 ? v1 : v2; }  // base case
    164 
    165         forall(T, Ts... | { T max(T, T); T max(Ts); })  // recursive case
     150        // Fixed Length Max - Base Case:
     151        forall(T | { int ?>?( T, T ); })
     152        T max(T v1, T v2) { return v1 > v2 ? v1 : v2; }
     153
     154        // Variable Length Max - Recursive:
     155        forall(T, Ts... | { T max(T, T); T max(Ts); })
    166156        T max(T arg, Ts args) {
    167157                return max(arg, max(args));
    168158        }
    169159
    170 This feature introduces a type name into scope (Ts). It is used as a type but
    171 because the tuple is flattened, the second assertion "T max(Ts);" matches types
    172 with multiple parameters (the `...`), although it is used as a tuple function
    173 inside the function body (max(args)).
    174 
    175 The first non-recursive max function is the polymorphic base-case for the
    176 recursion, i.e., find the maximum of two identically typed values with a
    177 greater-than (>) operator.  The second recursive max function takes two
    178 parameters, a T and a Ts tuple, handling all argument lengths greater than two.
    179 The recursive function computes the maximum for the first argument and the
    180 maximum value of the rest of the tuple.  The call of max with one argument is
    181 the recursive call, where the tuple is converted into two arguments by taking
    182 the first value (lisp car) from the tuple pack as the first argument
    183 (flattening) and the remaining pack becomes the second argument (lisp cdr).
    184 The recursion stops when the tuple is empty.  For example, max( 2, 3, 4 )
    185 matches with the recursive function, which performs return max( 2, max( [3, 4]
    186 ) ) and one more step yields return max( 2, max( 3, 4 ) ), so the tuple is
    187 empty.
    188 
     160This feature introduces a type name into scope (Ts). It is used as a type and
     161the value it declares (args) is a tuple value, and that the second assertion
     162"T max(Ts);" matches takes a single tuple, but with restructuring it can also
     163match functions that take a series of non-tuple arguments.
     164
     165A good way to explain this is to show a partial implementation the following
     166call `max(int_a, int_b, int_c);` into actual code:
     167
     168        void _thunk0(int v1, int v2) {
     169                return max{?>?}(v1, v2);
     170        }
     171        void _thunk1([int, int] tup) {
     172                return max{?>?}(tup.0, tup.1);
     173        }
     174        max{_thunk0, _thunk1}(int_a, [int_b, int_c]);
     175
     176The part to highlight is that "_thunk1", one of the functions created to
     177make an inexact match that can be used as a call site into an exact match
     178so the function can be passed through function parameters.
     179Although, the tuple type `[int, int]` matches a parameter list `int, int`,
     180just with a bit of low lever restructuring.
     181
     182In larger cases (with four or more parameters in the first case), the
     183recursive case will work similarly, creating an intermidate function to
     184restructure the tuple into a new call such as:
     185
     186        void _thunk2([int, int, int] tup) {
     187                return max{_thunk0, _thunk1}(tup.0, [tup.1, tup.2]);
     188        }
    189189
    190190Issues with the Current State
    … …  
    199199be.
    200200
    201 Because of the fluid nature of tuples (flattening/structuring), routines like
    202 constructions, destructor, or assignment do not make sense, e.g. this
    203 constructor matches multiple a tuple types:
    204 
    205         void ?{} ( [int, int, int] ? this );
    206         [int, [int, int]] x; // all match constructor type by flattening
    207         [int,  int, int]  y;
    208         [[int, int], int] z;
    209 
    210 as could a similarly typed destructor or assignment operator.  This prevents
    211 tuples from being interwoven with regular polymorphic code.
     201Tuples do not have the lifetime operators (copy construction, copy assignment
     202and destructor) that define an object type in Cforall. This means they are
     203not polymorphic otypes, they are objects in C's usage of the word. This means
     204that tuples cannot be used as a single object in
     205
     206There are several reasons for this. The fluid nature of tuples (flattening
     207and restructuring) means that matching against a tuple type is fluid in some
     208inconvent ways.
     209
     210        forall(T, U) void ?{}([T, U] & this;
     211        void ?{}([int, int, int] & this);
     212        // What constructor(s) should be used here?
     213        [int, [int, int]] pair;
     214
     215Should the polymorpic constructor be applied twice or should the tuple be
     216restructured and the three element constructor be used? This is not really
     217something a user should be wondering about (especially since tuples should
     218always be simple containers wrapping their elements).
    212219
    213220### Providing TType Arguments is Inconsistent
    … …  
    217224functions and there are very few existing use-cases for ttype structures.
    218225
    219 Passing arguments to a function inlines the arguments
    220 while passing them to a polymorphic type requires them to be
    221 enclosed in a tuple. Compare `function(x, y, z)` with `Type(A, [B, C])`.
    222 
    223 This did not come up previously as there was little reason to explicitly
    224 provide ttype arguments. They are implicit for functions and there is very
    225 little use case for a ttype on a struct or union.
     226        forall(T, Us...)
     227        void function(T head, Us tail) {}
     228
     229        forall(T, Us...)
     230        struct Type {};
     231
     232        int a;  bool b;  char c;
     233        function(a, b, c);
     234        function(a, [b, c]);
     235        // Doesn't work: Type(int, bool, char) x;
     236        Type(int, [bool, char]) x;
     237
     238The `function` case works either way because the tuple value can be
     239restructured if it does not match exactly. The `Type` case though does not
     240allow restructuring when the type is passed as a type value. This may be
     241the most correct form, but seems surprising compared to the common use.
     242
     243### Unary Tuple Value Syntax
     244
     245Unary tuples don't use the standard tuple syntax and one of the two alternate
     246syntax options your may use instead doesn't work consistently. Solving both
     247of these issues would help with consistency.
    226248
    227249### Syntax Conflict
    228250
    229 The tuple syntax conflicts with designators and the new C++-style attribute
     251The tuple syntax conflicts with designators and the C23 (C++-style) attribute
    230252syntax.
    231253
    232         struct S { int a[10]; } = { [2] = 3 }; // [2] looks like a tuple
    233         [[ unused ]] [[3, 4]]; // look ahead problem
     254        int a[10] = { [2] = 3 };
     255
     256Here [2] = 3 is an array designator, but has the same syntax as an assignment
     257to a tuple of references, it isn't until the resolver determains that 2 is
     258not a reference that that case can be ruled out.
     259
     260        [[ unused ]] [[int, int], int] x;
     261
     262Here the opening `[[` could be a nested tuple or the beginning of an
     263attribute, the parser can't figure out until later.
    234264
    235265These conflicts break C compatibility goals of Cforall. Designators had to
    236266their syntax change and Cforall cannot parse the new attributes.
    237 
    238 Although most of this redesign is about the semantics of tuples, but an update
    239 to tuple syntax that removes these conflicts would improve the compatibility of
    240 Cforall going forward (and also open up the new attribute syntax for cforall
    241 features).
     267The behaviour of these cases, if they could be parsed, should be unchanged.
    242268
    243269Change in Model
    244270---------------
    245271This proposal modifies the existing tuples to better handle its main use
    246 cases. There are some use cases that are no longer handled, and a new
    247 struct tuple is added to cover those cases.
    248 
    249 The new tuples is even more "unstructured" than before.  New tuples are
     272cases. There are some use cases that are no longer handled, so in addition
     273to changing the existing "restructured tuples" to "unstructured tuples"
     274(or packs) a new "structured tuple" is added in the form of struct tuple.
     275
     276The new tuples is even more "unstructured" than before. New tuples are
    250277considered a sequence of types or typed entities. These packs are then unpacked
    251278into the surrounding context. Put differently, tuples are now flattened as much
    … …  
    259286unstructured tuples no longer support.
    260287
    261 Note that the underlying implementation might not actually look like this.
     288Note that the underlying implementation might not actually look like this,
     289but this is how it should seem to the user.
    262290
    263291Changed Features
    … …  
    265293Some of the concrete changes to the features of the language.
    266294
     295### Unstructured Tuple / Pack Type
     296
     297The evolution of our current tuples (called packs in an attempt to make the
     298names more distinct). They work like the current tuples except they are
     299always flattened. You might still be able to declare nested tuples, but these
     300are not meaningful, they are flattened to a single level and, where
     301approprate, is inlined into the sounding content.
     302
     303        [bool, [char, int], long] x;
     304        // Becomes:
     305        [bool, char, int, long] x;
     306
     307        void f(bool a0, [char, [int, long]] a1, float a2);
     308        // Becomes:
     309        void f(bool a0, char a1_0, int a1_1, long a1_2, float a2);
     310
     311        [,] f(int a0, [,] a1, [bool,] a2);
     312        // Becomes:
     313        void f(int a0, bool a2);
     314
     315This actually means that tuples do not participate in overload resolution
     316in the way the do currently. Restructuring is always free because they are
     317always reduced to the same form as part of type matching.
     318
     319Packs are still not object types and do not have lifetime functions. They
     320cannot be used as object types, nor as any data type, but they can be still
     321used as ttypes.
     322
     323(Unless they need to have lifetime functions for other features.)
     324
    267325### Structured Tuple Type
    268326
    269 There is a standard library or built-in type named `tuple`, it does not need a
    270 special syntax to write types or instances. The type definition might need some
    271 primitive support, but if supported as a regular type would look something like
    272 this:
     327There is a standard library or built-in type named `tuple`, it does not need
     328a special syntax to write types or values. The type definition might need
     329some primitive support, but if supported as a regular type would look
     330something like this:
    273331
    274332        forall(Ts...)
    275333        struct tuple {
    276                 inline Ts all; // inline all specified fields
     334                inline Ts all;
    277335        };
    278336
    279 This type is constructed the same way as most types, a list initializer with
    280 each tuple argument, and the lifetime functions (construction, assignment and
    281 destruction) work the same. Field access works two ways, the first is accessing
    282 the `all` field, effectively converting the structured tuple into an
    283 unstructured tuple, the other is to use tuple indexing directly on the
    284 structure as if it is an unstructured tuple.
    285 
    286 (If `inline` does not work, just rename all to `get`. It does make things a bit
    287 longer but has no change in functionality. If the `all` access does not work,
    288 that is more problematic, and tuple slicing might provide a work around.)
     337This type wraps up an unstructured tuple, in this case a pack of members,
     338and gives it "edges" and so structure. It also gives tuples an interface
     339more like a normal structure type, for the anonymous structure use case.
     340
     341The struct tuple does have lifetime functions, can use list initializer
     342syntax and otherwise be treated as a normal structure. You can use regular
     343member access syntax to convert the struct tuple into a unstructured pack,
     344writing `object.all`.
     345
     346The `inline` modifier is a new specialized feature to allow you use tuple
     347index expressions directly on the type. With or without inline you should
     348be able to chain a tuple index expression onto the member expression, such
     349as `object.all.1`. The inline specifier allows you to skip the middle
     350and use `object.1`.
     351
     352More complex operations can usually be preformed by taking the pack out of
     353the struct tuple and acting on it. Polymorphic operations only have to go one
     354level down to get to base operations, there is no need for recursive
     355construction, nor manually coding different sizes of tuple. This should give
     356most of the ease of working with a primitive tuple, because effectively you
     357are except it has been given fixed edges.
     358
     359A tuple struct should also be an object type, and let's you pass multiple
     360values through a single polymorphic slot.
     361
     362A note on the naming here, because there are more pieces that need names
     363instead of symbols. The name `tuple` follows because that is the common name,
     364although this means this is now the default tuple in some sense. The name of
     365the pack was picked to work with inline and make the difference between `.0`
     366and `.all` clear. (If inline doesn't work then `get` might be a better name.)
    289367
    290368### Type Qualifier Distribution
    … …  
    330408up, that cannot be enforced with two different tuples.
    331409
     410This example doesn't have to be implemented this way because we do have the
     411special case operations for these already.
     412
    332413### Type Packs
    333414
    … …  
    371452
    372453For local declarations it works similarly, except the name introduced is
    373 directly usable as a tuple.
     454directly usable as a tuple instead of going through a member access.
    374455
    375456        forall(Objects...)
    … …  
    380461        }
    381462
     463### Tuple Pack Restructuring
     464
     465Implicit restructuring still occurs, but is not considered as part of
     466overload resolution. The structure of tuples is ignored, where individual
     467tuples begin or end is not considered, just the sequence of types.
     468
     469This can be viewed as flattening both sides (the arguments/caller and the
     470parameters/callee) before type resolution. Both any nested packs and packs
     471into any larger context:
     472
     473        call(false, ['a', [-7,]], 3.14)
     474        // Inline Nesting:
     475        call(false, ['a', -7], 3.14)
     476        // Inline into Context:
     477        call(false, 'a', -7, 3.14)
     478
     479The main context where tuples are inlined are parameter lists, in that you
     480can consider a parameter list as a single pack. Return types could be viewed
     481in this way, but because they are presented in a single type, they are
     482already wrapped in a tuple.
     483
     484        [int, [bool, char]] f();
     485        // Inline Nesting:
     486        [int, bool, char] f();
     487
     488This also happens "after" any polymorphic parameters are instantiated.
     489
     490Empty packs are also collapsed, logically being removed or replaced with
     491void as in the following example:
     492
     493        // For example, this function:
     494        forall(Ts...) Ts example(int first, Ts middle, int last);
     495        // With Ts = [,], should not be treated as:
     496        [,] example(int first, [,] middle, int last);
     497        // But instead:
     498        void example(int first, int last);
     499
     500Or closer to it, there are some slight differences between the nullary tuple
     501and void, for instance creating some instances for consistency with the other
     502tuple types.
     503
     504The struct tuple is never implicitly restructured.
     505
    382506### Tuple Declaration/Deconstruction
    383507
    … …  
    386510elements of the tuple can be named.
    387511
    388         [int quo, int rem] ret = divmod(a, b);
     512        [int quo, int rem] quorem = divmod(a, b);
    389513
    390514Here `ret` refers to the tuple, the entire pack, while `quo` and `rem`
    … …  
    396520no named to access it.
    397521
    398 PAB: I do understand the point of this.
     522This does not add any new functionality, more it is a qualify of life feature
     523making it very easy to give elements of a tuple descriptive names
     524instead of trying to combine a name for the whole tuple with an index.
     525(`quo` and `rem` vs. `quorem.0` and `quorem.1`)
    399526
    400527### Tuple Casts
    … …  
    405532so it may be replaced with other features (for example: tuple slicing).
    406533
    407 ### Forbidden Tuples
    408 
    409 The unstructured tuple cannot represent all the types that the previous
    410 semi-structured tuple could. These cases still exist in various ways,
    411 specifically in the internals of a polymorphic type, but in general should be
    412 considered in their reduced form.
    413 
    414 Forbidding some of these tuples may remove ambiguity and solve some syntax
    415 conflicts that currently exist.
    416 
    417 Nullary, or 0 element tuples, are equivalent to void, the type that carries
    418 no data, because they do not either. It should either be replaced with void
    419 or removed entirely when it appears in a larger sequence.
    420 
    421         // For example, this function:
    422         forall(Ts...) Ts example(int first, ????)
    423         // With Ts = [], should not be treated as:
    424         [] example(int first, [] middle, int last);
    425         // But instead:
    426         void example(int first, int last);
    427 
    428 Unary, or 1 element tuples, should be the same as their element type. That
    429 is to say a single type in an unstructured tuple is a no-op.
    430 
    431 Lastly, nested tuples are always flattened to a one-depth tuple.  This means
    432 that `[bool, [char, int], float]` is resolved as `[bool, char, int, float]`,
    433 with the internal structure of the tuple ignored.
    434 
    435 The flatten into a large sequence rule mentioned above is actually just an
    436 application of this. Unstructured tuples can already be restructured, even at
    437 the top level of an function call. This can be expressed by considering the
    438 argument list as a tuple:
    439 
    440         call(false, ['a', -7], 3.14)
    441         call([false, ['a', -7], 3.14])
    442         call([false, 'a', -7, 3.14])
    443         call(false, 'a', -7, 3.14)
    444 
    445 The ability to write nested tuples may remain so tuple deconstruction can be
    446 used to name a slice of the tuple.
     534        // Allowed:
     535        ([bool, short])tuple_bool_char;
     536        ([int, float])tuple_float_float;
     537
     538        // Forbidden:
     539        ([int, int, int])tuple_int_int;
     540        ([long, [float, int]])tuple_long_float_int;
     541
     542### New Tuple Literal Syntax
     543
     544In addition to the main redesign of this proposal, the syntax is updated to
     545be more consistant. It is now a "[]" list with "," separators and a ","/comma
     546terminator that is optional for tuples with 2 or more elements (those that
     547already have a comma in them) and manditory in other tuples.
     548
     549It should also be symmetric between types and value, differing only in that
     550an element (ITEM below) of a tuple type is a type and the element of a tuple
     551value is a value.
     552
     553-   Nullary Tuple: [,]
     554-   Unary Tuples: [ITEM,]
     555-   Multiary Tuples: [ITEM, ITEM] [ITEM, ITEM,] [ITEM, ITEM, ITEM] ...
     556
     557Currently, although syntax is provided to write them, but manually writing
     558a nullary or unary tuple should be very rare. This is because a nullary tuple
     559can either be erased or treated as void, while unary tuples can be treated
     560as their element type. Similary for nested tuples, can be treated as the
     561flattened tuple.
     562
     563(Update: Orignal nullary tuple proposal was `[]`, but that had some issues.)
     564
     565### TType Argument Syntax
     566
     567It would be nice to seamlessly provide packs of types in polymorphic
     568argument lists, however doing so requires a new restriction.
     569
     570As an example of the change, consider providing arguments to a polymorphic
     571structure with a otype and a ttype parameter.
     572
     573        forall(T, Us...) struct D {...};
     574        D(int, [,])            // D(int)
     575        D(bool, [char,])       // D(bool, char)
     576        D(long, [int, short])  // D(long, int, short)
     577
     578This is a nice syntaxtic improvement for the common case, it does restrict
     579some of the more complex cases, such as cases with two ttypes. There are
     580various restrictions on this for functions. If the rules make it unambigous
     581then the grouping could be omitted, or a more advanced version, it can be
     582ommited only in the indivual cases where it is unambigous.
    447583
    448584### Tuple Slicing (Range Tuple Indexing)
    … …  
    454590index expression to be a list-range a multiple sub-tuples can be extracted.
    455591
    456         [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].0~2,5~9~2
    457 
    458 produces the tuple
    459 
    460         [0, 1, 2, 5, 7, 9]
    461 
    462 (Note the position and values are the same to simplify the example.) That is,
    463 index the first 3 tuple elements, and then indexes elements 5 to 9 in steps of
    464 2. Not all selections are possible with this mechanism (e.g., index the
    465 Fibonacci elements), but it covers many cases.
     592        ['a', 'b', 'c', 'd', 'e', 'f'].0~3
     593        ['a', 'b', 'c', 'd', 'e', 'f'].1~5~2
     594        // Produces:
     595        ['a', 'b', 'c']
     596        ['b', 'd']
     597
     598In words, the first indexes the first 3 tuple elements (0, 1, 2, stopping
     599before index 3) and the second indexes elements starting at index 1, stoping
     600before index 5 going in steps of 2. This does not allow for arbitary
     601selections, but it covers many common slices.
    466602
    467603To get the new tuple, the range has to be constructed and traversed at compile
    … …  
    486622The iterators proposal has a section on some new range types, this feature
    487623is intended to be built on that feature. Not simply reuse some of the syntax
    488 that is also used in the special for loop. And compile-time evaluation may
    489 need to be improved.
    490 
    491 PAB, I don't understand this last part as the index range is compile time not
    492 runtime.
     624that is also used in the special for loop. This may add some requirements
     625about the compile-time evaluation on range expressions to make sure these
     626expressions can be evaluated at compile-time.
    493627
    494628Implementation
    … …  
    496630An overview of the implementation details of the new proposal.
    497631
    498 ### Structured Tuple Implementation
    499 
    500 Under the hood, unstructured tuples are implemented as structured tuples, with
    501 the restructuring code inserted wherever needed.  In short, the base
    502 implementation should stay mostly the same.
    503 
    504 PAB: The current implementation does not use convert unstructured tuples to
    505 structured tuples. Look at the code generated for
    506 
    507         int x, y;
    508         [x, y] = 3;
    509         [x, y] = [y, x];
    510 
    511 
    512 Actually inlining tuples can be done in some cases, it may even help with
    513 some forms like a fixed tuple decomposition. However, polymorphic tuples
    514 still need to be reduced to a single generic form, which would be a
    515 polymorphic container, a tuple.
     632### Structured Tuple
     633
     634There is actually a decision point here. If it can be implemented entirely
     635in the standard library, that would be good. If it cannot, it can actually
     636be implemented as the same primitive implementation as we use now and may be
     637how unstructured tuple packs are implemented.
     638
     639### Member Pack Implementation
     640
     641Implementing member packs can use the same pattern as current built-in tuple
     642syntax. This is a two stage process, first is by ... then the it can be
     643handled by the existing code for polymorphic but not variadic structures.
     644
     645        forall(Ts...)
     646        struct tuple {
     647                Ts get;
     648        };
     649
     650So when used with diffences length an hidden declaration is created which
     651has the pack parameter replaced with the approprate number of object type
     652parameters. Such as in the following examples:
     653
     654        struct tuple$0 {
     655        };
     656
     657        forall(Ts$0)
     658        struct tuple$1 {
     659                Ts$0 get$0;
     660        };
     661
     662        forall(Ts$0, Ts$1)
     663        struct tuple$2 {
     664                Ts$0 get$0;
     665                Ts$1 get$1;
     666        };
     667
     668Then it can be handled by the regular boxing code. Detection of these cases
     669will have to changed because it is no longer a single case. But the pattern
     670does work if the structure has additional fields in it, as they are just
     671placed before and after the pack.
     672
     673        forall(U, Ts...)
     674        struct blob {
     675                int header;
     676                Ts data;
     677                U footer;
     678        };
     679
     680        forall(U, Ts$0, Ts$1)
     681        struct blob$2 {
     682                int header;
     683                Ts$0 data$0;
     684                Ts$1 data$1;
     685                U footer;
     686        };
     687
     688The `inline` member pack just effects the resolver. It should be expanded out
     689to the member access and then the tuple index expression.
     690
     691### Local Declaration Pack
     692
     693Packs of local declarations can be handled very differently if they are
     694concrete or not. Concrete packs can be writen out in full (even if some
     695individual elements are polymorphic) can be inlined directly, expanding out
     696into a series of object declarations.
     697
     698        [A, B] local = func();
     699        call(local);
     700
     701        A local$0;
     702        B local$1;
     703        ?{}([&local$0, &local$1], func());
     704        call([local$0, local$1]);
     705
     706In the polymorphic case though, that entire group needs to be reduced to a
     707block that can put into a generic function. Here we can use something like
     708the currently existing implementation, where the entire tuple an opaque
     709bundle, passed to adapters and thunks for handling.
     710
     711This is also how tuple declarations are implemented. In the concrete case the
     712element names are real and the pack name is replaced with a tuple expression
     713of the elements. In the polymorphic case the pack name is real and the
     714element names are replaced with tuple index expressions.
     715
     716### Unstructured Tuple Implementation
     717
     718Unstructured tuples have two general implementation stratagies. Either they
     719are erased and the packs inlined into their context, or they are wrapped
     720up as like a structured tuple, generally using the current implementation.
     721
     722For example, if a concrete pack (size and all the types are known), appears
     723in a parameter list the pack can be split and inlined into the argument list.
     724
     725        void function(int a, [bool, char, short] b, float c);
     726        // Becomes:
     727        void function(int a, bool b0, char b1, short b2, float c);
     728
     729On the other hand, if a polymorphic pack appears in the same place, it will
     730have to be wrapped up in a dynamic structure so it different instances can
     731
     732        forall(Ts...)
     733        void function(int a, Ts b, float c);
     734        // Becomes (after the implicit packing and unpacking operations):
     735        forall(T)
     736        void function(int a, T* b, float c);
    516737
    517738### AST Updates
    518739
    519 The current AST cannot represent all the new features. Particularly, an
    520 object declaration cannot name elements of the tuple. To this end a new
    521 node type, `TupleDecl`, should be added to handle tuple deconstruction
    522 declarations (other cases can still be handled with `ObjectDecl`).
     740The AST may already be capable of representing most of this. I have only
     741identified one feature that definitely will now work in the current AST, and
     742that are the object like tuple declarations with named elements.
     743
     744Particularly, an object declaration cannot name elements of the tuple.
     745To this end a new node type, `TupleDecl`,
     746should be added to handle tuple deconstruction declarations
     747(other cases can still be handled with `ObjectDecl`).
    523748
    524749This would act much like a `FunctionDecl` except for tuples, narrowing the
    … …  
    527752elements of the tuples.
    528753
    529 PAB: the following parses:
    530 
    531         [int x, int y] foo( int p );
    532 
    533 and discussed by Till.
    534 
    535754(I'm not actually going to decide the implementation now, but some early
    536755examination of the problem suggests that it might be better off wrapping a
    537756series of `ObjectDecl` rather than just some strings to hold the names.)
    538757
    539 ### Field Packs
    540 
    541 Field packs in structures probably have to be written out in full by the
    542 specialization pass. If not, it could have some negative effects on layout,
    543 causing a structure to take up extra space. It may be able to reuse some of the
    544 specialization code for the existing tuples.
    545 
    546758Related Features in Other Languages
    547759-----------------------------------
    548 Other languages have similar features. Organized by the related feature.
     760Other languages have similar features. Organized by the related feature,
     761then language (this does mean we can and do hit languages multiple times).
    549762
    550763(In hindsight, I may have gone overboard with the number of examples.)
    … …  
    584797-   https://doc.rust-lang.org/reference/expressions/tuple-expr.html
    585798
    586 #### C++ tuple
     799#### C++
    587800
    588801Implemented as a template type defined in the standard library. No special
    … …  
    598811used, e.g., `std::get<0>( tuple )`.
    599812
     813C++ is an interesting case because it is one of the few cases where no part
     814of the tuple system is built-in. It is entirely created in the standard
     815library using templates. This also has massive error messages when something
     816goes wrong, hopefully our version of struct tuple will reduce the problem.
     817
    600818C++ also has structured binding, a kind of limited pattern matching. In a
    601 structured binding declaration, you can write an auto typed declaration with
    602 a list of identifiers in a `[]` list.
    603 For example, `auto [first, second] = getSize2Tuple();`.
     819structured binding declaration, you can write an auto typed declaration where
     820a list of identifiers in a `[]` replaces the single identifier.
     821
     822        auto [first, second] = getSize2Tuple();
     823
     824The base type has to be `auto` because the base type for each element varies.
     825Still, qualifiers (cv and reference) on the auto will be distributed to types
     826on the individual members.
     827
     828The type bound to the binding may be an array, a "plain" structure or any
     829type that implements the tuple-like interface (`std::tuple_size` and
     830`std::tuple_element`).
    604831
    605832-   https://en.cppreference.com/w/cpp/utility/tuple
    606833-   https://en.cppreference.com/w/cpp/language/structured_binding
    607834
    608 PAB: I do not understand the syntax `auto [first, second]`. Where does it come
    609 from?
    610 
    611 #### C++ template
    612 
    613 C++ templates can take various types of parameters, including parameter
    614 packs. These contain series of values. These are used in pack expansion,
     835#### Haskell
     836
     837Haskell has a special syntax for tuples, but otherwise they are completely
     838normal polymorphic types. Because of this, tuples have a maximum size.
     839Haskell (98) supports tuples of up to 15 elements and the standard library
     840has functions for tuples of up to 7 elements.
     841
     842The syntax for tuples is a comma separated list of elements. Either element
     843types to create a tuple type, or element values to create a tuple value. The
     844context decides among them, such as `(6, "six")` or `(Bool, Char, Int)`.
     845
     846Also all the elements can be removed, getting an expression like "(,)" or
     847"(,,,)", which can be then be used as a function, for a type, or an expression.
     848
     849Haskell supports pattern matching as the main way to extract values from a
     850tuple, although helper functions "fst" and "snd" are provided for field
     851access on two element tuples.
     852
     853Haskell does not have 0 or 1-element tuples. The nil type, written "()" for
     854both type and value, is effectively the 0 element tuple. There is also a type
     855called "Solo" that is a polymorphic structure with one field and is used as
     856the 1-element tuple, but has regular Haskell data-type syntax.
     857
     858-   https://www.haskell.org/onlinereport/basic.html
     859
     860#### OCaml
     861
     862OCaml only supports multi-element (2 or more) tuples.  It does have the `unit`
     863type, which has one value, written `()`. Tuple types are written as a '*'
     864separated list of types, tuple values are written as ',' separated list of
     865expressions. Pattern matching tuples is supported and uses the same syntax as
     866values. Parenthesizing these lists is only needed for grouping.
     867
     868-   https://ocaml.org/docs/basic-data-types#tuples
     869
     870#### Swift
     871
     872Swift has tuple types that use the basic parenthesized, comma separated list of
     873types or values. It only supports 0 and 2 or more element tuples (the `Void`
     874type is an alias for the empty tuple type).
     875
     876Swift also supports named tuples. Names can be added before the tuple element,
     877both for the tuple type and value. The syntax is a name followed by a colon,
     878e.g., `(first: int, second: int)`. These names are a fixed part of the type,
     879and can be used as part of field access notation (otherwise numbers are used
     880in-place of field names `tuple.0` vs. `tuple.first`).
     881
     882-   https://docs.swift.org/swift-book/documentation/the-swift-programming-language/types/#Tuple-Type
     883
     884#### Python
     885
     886In Python tuples are immutable lists. Because they are dynamically typed,
     887there is only one tuple type `tuple`.
     888
     889It also has various named tuples. The first, namedtuple, allows naming the
     890elements of the tuple. The second, NamedTuple, is actually a way of creating a
     891typed record in a normally untyped language.
     892
     893-   https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range
     894-   https://docs.python.org/3/library/collections.html#collections.namedtuple
     895-   https://docs.python.org/3/library/typing.html#typing.NamedTuple
     896
     897#### LISP
     898As LISP is dynamically typed, its `cons` data type is an untyped pair and is
     899(perhaps infamously) the main constructor of all compound data types.  The
     900function `cons` takes two arguments and builds a pair. Functions `car` and
     901`cdr` get the first and second elements of the pair.
     902
     903### Packs
     904Packs (or unstructured tuples) are a much less common feature. In fact, there
     905might just be one language, C++, that supports packs. The most common use
     906case for unstructured tuples is returning multiple values, so there is a
     907comparison to languages that have that as a special feature.
     908
     909#### Go
     910Go does not have built in tuple types, but it has multi-return syntax that
     911looks like the tuple syntax of many other languages.
     912
     913```
     914func main() {
     915        i, j := returnIntInt()
     916        ...
     917}
     918
     919func returnIntInt() (int, int) {
     920        return 12, 34
     921}
     922```
     923
     924Go can unpack multiple return values and pass them all to a function, but
     925the unpacked tuple must match the parameter list exactly.
     926
     927```
     928func acceptIntInt(a int, b int) {
     929        fmt.Println(a, b)
     930}
     931```
     932
     933-   https://golangdocs.com/functions-in-golang
     934-   https://go.dev/src/go/types/tuple.go
     935
     936#### Lua
     937Lua is a scripting language that is dynamically typed and stack based. Although
     938the stack is usually only directly visible in the C-API, it does allow any
     939function to return any number of values, one, zero or more, from any return
     940expression.
     941
     942```
     943local funcion f()
     944        return 12, 34
     945end
     946
     947local i, j = f()
     948```
     949
     950The last argument in an argument list can be an expression - function call -
     951with multiple results and all the results are passed to the function after
     952other arguments.
     953
     954Because Lua is dynamically typed, multiple return values are allowed anywhere
     955and the length of the value listed is adjusted, discarding any extra values
     956and filling in new values with the value `nil`. This is also used if a
     957function is called with the incorrect number of arguments.
     958
     959-   https://lua.org/
     960-   https://lua.org/manual/5.4/manual.html#3.4.12
     961
     962#### C++
     963
     964We return to C++ to view template parameter packs. These are the symmetric
     965with our pack feature (and both are even used to construct the structured
     966tuples in the last section).
     967
     968C++ template parameter packs are a modification that can be applied to any
     969template parameter, so the parameter now takes a series of arguments instead
     970of just one. These are used in pack expansion,
    615971which usually expand to a comma separated list, but it can also be a chain of
    616972boolean binary operator applications. For example, if the parameter
    … …  
    643999
    6441000There are also fold expressions that use binary operators to combine a pack
    645 into a single expression. For example, `args + ... + 0` which adds every
    646 element of the `args` pack together.
     1001into a single expression. For example, you can write a variadic sum function
     1002that compiles down to the primitive additions.
     1003
     1004```
     1005template<typename... Args>
     1006int sum(Args&&... args) {
     1007        return (args + ... + 0);
     1008}
     1009```
    6471010
    6481011C++ is about the best you could ask for in this area, but it does a lot of work
    … …  
    6521015-   https://en.cppreference.com/w/cpp/language/parameter_pack
    6531016-   https://en.cppreference.com/w/cpp/language/fold
    654 
    655 #### Haskell
    656 
    657 Haskell has a special syntax for tuples, but otherwise they are completely
    658 normal polymorphic types. Because of this, tuples have a maximum size.
    659 Haskell (98) supports tuples of up to 15 elements and the standard library
    660 has functions for tuples of up to 7 elements.
    661 
    662 The syntax for tuples is a comma separated list of elements. Either element
    663 types to create a tuple type, or element values to create a tuple value. The
    664 context decides among them, such as `(6, "six")` or `(Bool, Char, Int)`.
    665 
    666 Also all the elements can be removed, getting an expression like "(,)" or
    667 "(,,,)", which can be then be used as a function, for a type, or an expression.
    668 
    669 Haskell supports pattern matching as the main way to extract values from a
    670 tuple, although helper functions "fst" and "snd" are provided for field
    671 access on two element tuples.
    672 
    673 Haskell does not have 0 or 1-element tuples. The nil type, written "()" for
    674 both type and value, is effectively the 0 element tuple. There is also a type
    675 called "Solo" that is a polymorphic structure with one field and is used as
    676 the 1-element tuple, but has regular Haskell data-type syntax.
    677 
    678 -   https://www.haskell.org/onlinereport/basic.html
    679 
    680 #### OCaml
    681 
    682 OCaml only supports multi-element (2 or more) tuples.  It does have the `unit`
    683 type, which has one value, written `()`. Tuple types are written as a '*'
    684 separated list of types, tuple values are written as ',' separated list of
    685 expressions. Pattern matching tuples is supported and uses the same syntax as
    686 values. Parenthesizing these lists is only needed for grouping.
    687 
    688 -   https://ocaml.org/docs/basic-data-types#tuples
    689 
    690 #### Swift
    691 
    692 Swift has tuple types that use the basic parenthesized, comma separated list of
    693 types or values. It only supports 0 and 2 or more element tuples (the `Void`
    694 type is an alias for the empty tuple type).
    695 
    696 Swift also supports named tuples. Names can be added before the tuple element,
    697 both for the tuple type and value. The syntax is a name followed by a colon,
    698 e.g., `(first: int, second: int)`. These names are a fixed part of the type,
    699 and can be used as part of field access notation (otherwise numbers are used
    700 in-place of field names `tuple.0` vs. `tuple.first`).
    701 
    702 -   https://docs.swift.org/swift-book/documentation/the-swift-programming-language/types/#Tuple-Type
    703 
    704 #### Python
    705 
    706 In Python tuples are immutable lists. Because they are dynamically typed,
    707 there is only one tuple type `tuple`.
    708 
    709 It also has various named tuples. The first, namedtuple, allows naming the
    710 elements of the tuple. The second, NamedTuple, is actually a way of creating a
    711 typed record in a normally untyped language.
    712 
    713 -   https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range
    714 -   https://docs.python.org/3/library/collections.html#collections.namedtuple
    715 -   https://docs.python.org/3/library/typing.html#typing.NamedTuple
    716 
    717 #### LISP
    718 As LISP is dynamically typed, its `cons` data type is an untyped pair and is
    719 (perhaps infamously) the main constructor of all compound data types.  The
    720 function `cons` takes two arguments and builds a pair. Functions `car` and
    721 `cdr` get the first and second elements of the pair.
    722 
    723 ### Packs
    724 Packs (or unstructured tuples) are a much less common feature. In fact, there
    725 might just be one language, C++, that supports packs. The most common use
    726 case for unstructured tuples is returning multiple values, so there is a
    727 comparison to languages that have that as a special feature.
    728 
    729 #### Go
    730 Go does not have built in tuple types, but it has multi-return syntax that
    731 looks like the tuple syntax of many other languages.
    732 
    733 ```
    734 func main() {
    735         i, j := returnIntInt()
    736         ...
    737 }
    738 
    739 func returnIntInt() (int, int) {
    740         return 12, 34
    741 }
    742 ```
    743 
    744 -   https://golangdocs.com/functions-in-golang
    745 -   https://go.dev/src/go/types/tuple.go
    746 
    747 #### Lua
    748 Lua is a scripting language that is dynamically typed and stack based. Although
    749 the stack is usually only directly visible in the C-API, it does allow any
    750 function to return any number of values, even a single return, in the return
    751 expression
    752 
    753 ```
    754 local funcion f()
    755         return 12, 34
    756 end
    757 
    758 local i, j = f()
    759 ```
Note: See TracChangeset for help on using the changeset viewer.