Changeset 336d0b3


Ignore:
Timestamp:
May 13, 2019, 1:11:40 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
768b3b4f, fdbd4fd
Parents:
4ab0669 (diff), 0727d97 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • doc/proposals/vtable.md

    r4ab0669 r336d0b3  
    88
    99The basic concept of a virtual table (vtable) is the same here as in most
    10 other languages. They will mostly contain function pointers although they
    11 should be able to store anything that goes into a trait.
    12 
    13 I also include notes on a sample implementation, which primarly exists to show
    14 there is a resonable implementation. The code samples for that are in a slight
    15 psudo-code to help avoid name mangling and keeps some CFA features while they
    16 would actually be writen in C.
     10other languages that use them. They will mostly contain function pointers
     11although they should be able to store anything that goes into a trait.
     12
     13I also include notes on a sample implementation, which primarily exists to show
     14there is a reasonable implementation. The code samples for that are in a slight
     15pseudo-code to help avoid name mangling and keeps some CFA features while they
     16would actually be written in C.
    1717
    1818Trait Instances
     
    2020
    2121Currently traits are completely abstract. Data types might implement a trait
    22 but traits are not themselves data types. This will change that and allow
    23 instances of traits to be created from instances of data types that implement
    24 the trait.
     22but traits are not themselves data types. Which is to say you cannot have an
     23instance of a trait. This proposal will change that and allow instances of
     24traits to be created from instances of data types that implement the trait.
     25
     26For example:
    2527
    2628    trait combiner(otype T) {
    27                 void combine(T&, int);
    28         };
     29        void combine(T&, int);
     30    };
    2931
    3032    struct summation {
    31                 int sum;
    32         };
    33 
    34         void ?{}( struct summation & this ) {
    35                 this.sum = 0;
    36         }
     33        int sum;
     34    };
     35
     36    void ?{}( struct summation & this ) {
     37        this.sum = 0;
     38    }
    3739
    3840    void combine( struct summation & this, int num ) {
    39                 this.sum = this.sum + num;
    40         }
    41 
    42         trait combiner obj = struct summation{};
    43         combine(obj, 5);
     41        this.sum = this.sum + num;
     42    }
     43
     44    trait combiner obj = struct summation{};
     45    combine(obj, 5);
    4446
    4547As with `struct` (and `union` and `enum`), `trait` might be optional when
     
    4951For traits to be used this way they should meet two requirements. First they
    5052should only have a single polymorphic type and each assertion should use that
    51 type once as a parameter. Extentions may later loosen these requirements.
    52 
    53 If a trait object is used it should generate a series of implicate functions
    54 each of which implements one of the functions required by the trait. So for
    55 combiner there is an implicate:
    56 
    57     void combine(trait combiner & this, int);
    58 
    59 This function is the one actually called at the end
     53type once as a parameter. Extensions may later loosen these requirements.
     54
     55Also note this applies to the final expanded list of assertions. Consider:
     56
     57    trait foo(otype T, otype U) {
     58        ... functions that use T once ...
     59    }
     60
     61    trait bar(otype S | foo(S, char)) {
     62        ... functions that use S once ...
     63    }
     64
     65In this example `bar` may be used as a type but `foo` may not.
     66
     67When a trait is used as a type it creates a generic object which combines
     68the base structure (an instance of `summation` in this case) and the vtable,
     69which is currently created and provided by a hidden mechanism.
     70
     71The generic object type for each trait also implements that trait. This is
     72actually the only means by which it can be used. The type of these functions
     73look something like this:
     74
     75    void combine(trait combiner & this, int num);
    6076
    6177The main use case for trait objects is that they can be stored. They can be
    62 passed into functions, but using the trait directly is prefred in this case.
     78passed into functions, but using the trait directly is preferred in this case.
    6379
    6480    trait drawable(otype T) {
     
    7894    }
    7995
    80 Currently these traits are limited to 1 trait parameter and functions should
    81 have exactly 1 parameter. We cannot abstract away pairs of types and still
    82 pass them into normal functions, which take them seperately.
    83 
    84 The second is required the because we need to get the vtable from somewhere.
    85 If there are 0 trait objects than no vtable is avalible, if we have more than
    86 1 than the vtables give conflicting answers on what underlying function to
    87 call. And even then the underlying type assumes a concrete type.
    88 
    89 This loop can sort of be broken by using the trait object directly in the
    90 signature. This has well defined meaning, but might not be useful.
     96The trait types can also be used in the types of assertions on traits as well.
     97In this usage they passed as the underlying object and vtable pair as they
     98are stored. The trait types can also be used in that trait's definition, which
     99means you can pass two instances of a trait to a single function. However the
     100look-up of the one that is not used to look up any functions, until another
     101function that uses that object in the generic/look-up location is called.
    91102
    92103    trait example(otype T) {
    93104        bool test(T & this, trait example & that);
    94105    }
     106
     107### Explanation Of Restrictions
     108
     109The two restrictions on traits that can be used as trait objects are:
     110
     1111.  Only one generic parameter may be defined in the trait's header.
     1122.  Each function assertion must have one parameter with the type of the
     113    generic parameter. They may or may not return a value of that type.
     114
     115Elsewhere in this proposal I suggest ways to broaden these requirements.
     116A simple example would be if a trait meets requirement 1 but not 2, then
     117the assertions that do not satisfy the exactly one parameter requirement can
     118be ignored.
     119
     120However I would like to talk about why these two rules are in place in the
     121first place and the problems that any exceptions to these rules must avoid.
     122
     123The problems appear when the dispatcher function which operates on the
     124generic object.
     125
     126    trait combiner(otype T, otype U) {
     127        void combine(T&, U);
     128    }
     129
     130This one is so strange I don't have proper syntax for it but let us say that
     131the concrete dispatcher would be typed as
     132`void combine(combiner(T) &, combiner(U));`. Does the function that combine
     133the two underlying types exist to dispatch too?
     134
     135Maybe not. If `combiner(T)` works with ints and `combiner(U)` is a char then
     136they could not be. It would have to enforce that all pairs of any types
     137that are wrapped in this way. Which would pretty much destroy any chance of
     138separate compilation.
     139
     140Even then it would be more expensive as the wrappers would have to carry ids
     141that you use to look up on an <number of types>+1 dimensional table.
     142
     143The second restriction has a similar issue but makes a bit more sense to
     144write out.
     145
     146    trait Series(otype T) {
     147        ... size, iterators, getters ...
     148        T join(T const &, T const &);
     149    }
     150
     151With the dispatcher typed as:
     152
     153    Series join(Series const &, Series const &);
     154
     155Because these instances are generic and hide the underlying implementation we
     156do not know what that implementation is. Unfortunately this also means the
     157implementation for the two parameters might not be the same. Once we have
     158two different types involved this devolves into the first case.
     159
     160We could check at run-time that the have the same underlying type, but this
     161would likely time and space overhead and there is no clear recovery path.
    95162
    96163#### Sample Implementation
     
    116183
    117184There may have to be special cases for things like copy construction, that
    118 might require a more sigificant wrapper. On the other hand moving could be
     185might require a more significant wrapper. On the other hand moving could be
    119186implemented by moving the pointers without any need to refer to the base
    120187object.
    121188
    122 ### Extention: Multiple Trait Parameters
    123 Currently, this gives traits two independent uses. They use the same syntax,
    124 except for limits boxable traits have, and yet don't really mix. The most
    125 natural way to do this is to allow trait instances to pick one parameter
    126 that they are generic over, the others they choose types to implement.
    127 
    128 The two ways to do the selection, the first is do it at the trait definition.
    129 Each trait picks out a single parameter which it can box (here the `virtual`
    130 qualifier). When you create an instance of a trait object you provide
    131 arguments like for a generic structure, but skip over the marked parameter.
    132 
    133     trait combiner(virtual otype T, otype Combined) {
    134         void combine(T &, Combined &);
    135     }
    136 
    137     trait combiner(int) int_combiner;
    138 
    139 The second is to do it at the instaniation point. A placeholder (here the
    140 keyword `virtual`) is used to explicately skip over the parameter that will be
    141 abstracted away, with the same rules as above if it was the marked parameter.
    142 
    143     trait combiner(otype T, otype Combined) {
    144         void combine(T &, Combined &);
    145     };
    146 
    147     trait combiner(virtual, int) int_combiner;
    148 
    149 Using both (first to set the default, second as a local override) would also
    150 work, although might be exessively complicated.
    151 
    152 This is useful in cases where you want to use a generic type, but leave part
    153 of it open and store partially generic result. As a simple example
    154 
    155     trait folder(otype T, otype In, otype Out) {
    156         void fold(T & this, In);
    157         Out fold_result(T & this);
    158     }
    159 
    160 Which allows you to fold values without putting them in a container. If they
    161 are already in a container this is exessive, but if they are generated over
    162 time this gives you a simple interface. This could for instance be used in
    163 a profile, where T changes for each profiling statistic and you can plug in
    164 multiple profilers for any run by adding them to an array.
     189### Extension: Multiple Trait Parameters
     190The base proposal in effect creates another use for the trait syntax that is
     191related to the ones currently in the language but is also separate from them.
     192The current uses generic functions and generic types, this new use could be
     193described as generic objects.
     194
     195A generic object is of a concrete type and has concrete functions that work on
     196it. It is generic in that it is a wrapper for an unknown type. Traits serve
     197a similar role here as in generic functions as they limit what the function
     198can be generic over.
     199
     200This combines the use allowing to have a generic type that is a generic
     201object. All but one of the trait's parameters is given a concrete type,
     202conceptually currying the trait to create a trait with on generic parameter
     203that fits the original restrictions. The resulting concrete generic object
     204type is different with each set of provided parameters and their values.
     205
     206Then it just becomes a question of where this is done. Again both examples use
     207a basic syntax to show the idea.
     208
     209    trait iterator(virtual otype T, otype Item) {
     210        bool has_next(T const &);
     211        Item get_next(T const *);
     212    }
     213
     214    iterator(int) int_it = begin(container_of_ints);
     215
     216The first option is to do it at the definition of the trait. One parameter
     217is selected (here with the `virtual` keyword, but other rules like "the first"
     218could also be used) and when an instance of the trait is created all the
     219other parameters must be provided.
     220
     221    trait iterator(otype T, otype Item) {
     222        bool has_next(T const &);
     223        Item get_next(T const *);
     224    }
     225
     226    iterator(virtual, int) int_it = begin(container_of_ints);
     227
     228The second option is to skip a parameter as part of the type instance
     229definition. One parameter is explicitly skipped (again with the `virtual`
     230keyword) and the others have concrete types. The skipped one is the one we
     231are generic on.
     232
     233Incidentally in both examples `container_of_ints` may itself be a generic
     234object and `begin` returns a generic iterator with unknown implementation.
     235
     236These options are not exclusive. Defining a default on the trait allows for
     237an object to be created as in the first example. However, whether the
     238default is provided or not, the second syntax can be used to pick a
     239parameter on instantiation.
    165240
    166241Hierarchy
    167242---------
    168243
    169 Virtual tables by them selves are not quite enough to implement the planned
    170 hierarchy system. An addition of type ids, implemented as pointers which
    171 point to your parent's type id, is required to actually create the shape of
    172 the hierarchy. However vtables would allow behaviour to be carried with the
    173 tree.
    174 
    175 The hierarchy would be a tree of types, of traits and structs. Currently we do
    176 not support structural extension, so traits form the internal nodes and
    177 structures the leaf nodes.
    178 
    179 The syntax is undecided but it will include a clause like `virtual (PARENT)`
    180 on trait and struct definitions. It marks out all types in a hierarchy.
    181 PARENT may be omitted, if it is this type is the root of a hierarchy. Otherwise
    182 it is the name of the type that is this type's parent in the hierarchy.
    183 
    184 Traits define a trait instance type that implements all assertions in this
    185 trait and its parents up until the root of the hierarchy. Each trait then
    186 defines a vtable type. Structures will also have a vtable type but it should
    187 be the same as their parent's.
    188 
    189 Trait objects within the tree can be statically cast to a parent type. Casts
    190 from a parent type to a child type are conditional, they check to make sure
    191 the underlying instance is an instance of the child type, or an instance of
    192 one of its children. The type then is recoverable at run-time.
    193 
    194 As with regular trait objects, calling a function on a trait object will cause
    195 a look-up on the the virtual table. The casting rules make sure anything that
    196 can be cast to a trait type will have all the function implementations for
    197 that trait.
    198 
    199 Converting from a concrete type (structures at the edge of the hierarchy) to
    200 an abstract type works the same as with normal trait objects, the underlying
    201 object is packaged with a virtual table pointer. Converting back to an abstract
    202 type requires confirming the underlying type matches, but then simply extracts
    203 the pointer to it.
    204 
    205 Exception Example:
     244We would also like to implement hierarchical relations between types.
     245
     246    AstNode
     247    |-ParseNode
     248    | |-Declaration
     249    | | |-DeclarationWithType
     250    | | |-StructureDeclaration
     251    | |-Statement
     252    | | |-CompoundStatement
     253    | |-Expression
     254    |-Type
     255
     256Virtual tables by themselves are not quite enough to implement this system.
     257A vtable is just a list of functions and there is no way to check at run-time
     258what these functions, we carry that knowledge with the table.
     259
     260This proposal adds type ids to check for position in the hierarchy and an
     261explicate syntax for establishing a hierarchical relation between traits and
     262their implementing types. The ids should uniquely identify each type and
     263allow retrieval of the type's parent if one exists. By recursion this allows
     264the ancestor relation between any two hierarchical types can be checked.
     265
     266The hierarchy is created with traits as the internal nodes and structures
     267as the leaf nodes. The structures may be used normally and the traits can
     268be used to create generic objects as in the first section (the same
     269restrictions apply). However these type objects store their type id which can
     270be recovered to figure out which type they are or at least check to see if
     271they fall into a given sub-tree at run-time.
     272
     273Here is an example of part of a hierarchy. The `virtual(PARENT)` syntax is
     274just an example. But when used it give the name of the parent type or if
     275empty it shows that this type is the root of its hierarchy.
    206276(Also I'm not sure where I got these casing rules.)
    207 
    208     trait exception(otype T) virtual() {
    209         char const * what(T & this);
    210     }
    211 
    212     trait io_error(otype T) virtual(exception) {
    213         FILE * which_file(T & this);
    214     }
    215 
    216     struct eof_error(otype T) virtual(io_error) {
    217         FILE * file;
    218     }
    219 
    220     char const * what(eof_error &) {
    221         return "Tried to read from an empty file.";
    222     }
    223 
    224     FILE * which_file(eof_error & this) {
    225         return eof_error.file;
    226     }
    227 
    228 Ast Example:
    229277
    230278    trait ast_node(otype T) virtual() {
     
    267315    }
    268316
     317### Extension: Structural Inheritance
     318An extension would be allow structures to be used as internal nodes on the
     319inheritance tree. Its child types would have to implement the same fields.
     320
     321The weaker restriction would be to convert the fields into field assertions
     322(Not implemented yet: `U T.x` means there is a field of type you on the type
     323T. Offset unknown and passed in/stored with function pointers.)
     324A concrete child would have to declare the same set of fields with the same
     325types. This is of a more functional style.
     326
     327The stronger restriction is that the fields of the parent are a prefix of the
     328child's fields. Possibly automatically inserted. This the imperative view and
     329may also have less overhead.
     330
     331### Extension: Unions and Enumerations
     332Currently there is no reason unions and enumerations, in the cases they
     333do implement the trait, could not be in the hierarchy as leaf nodes.
     334
     335It does not work with structural induction, but that could just be a compile
     336time check that all ancestors are traits or do not add field assertions.
     337
    269338#### Sample Implementation
    270339The type id may be as little as:
     
    275344
    276345Some linker magic would have to be used to ensure exactly one copy of each
    277 structure for each type exists in memory. There seem to be spectial once
     346structure for each type exists in memory. There seem to be special once
    278347sections that support this and it should be easier than generating unique
    279348ids across compilation units.
     
    300369
    301370### Virtual Casts
    302 To convert from a pointer to a type higher on the hierarchy to one lower on
    303 the hierarchy a check is used to make sure that the underlying type is also
    304 of that lower type.
    305 
    306 The proposed syntax for this is:
     371The generic objects may be cast up and down the hierarchy.
     372
     373Casting to an ancestor type always succeeds. From one generic type to another
     374is just a reinterpretation and could be implicate. Wrapping and unwrapping
     375a concrete type will probably use the same syntax as in the first section.
     376
     377Casting from an ancestor to a descendent requires a check. The underlying
     378type may or may not belong to the sub-tree headed by that descendent. For this
     379we introduce a new cast operator, which returns the pointer unchanged if the
     380check succeeds and null otherwise.
    307381
    308382    trait SubType * new_value = (virtual trait SubType *)super_type;
    309383
    310 It will return the same pointer if it does point to the subtype and null if
    311 it does not, doing the check and conversion in one operation.
    312 
    313 ### Inline vtables
     384For the following example I am using the as of yet finished exception system.
     385
     386    trait exception(otype T) virtual() {
     387        char const * what(T & this);
     388    }
     389
     390    trait io_error(otype T) virtual(exception) {
     391        FILE * which_file(T & this);
     392    }
     393
     394    struct eof_error(otype T) virtual(io_error) {
     395        FILE * file;
     396    }
     397
     398    char const * what(eof_error &) {
     399        return "Tried to read from an empty file.";
     400    }
     401
     402    FILE * which_file(eof_error & this) {
     403        return eof_error.file;
     404    }
     405
     406    bool handleIoError(exception * exc) {
     407        io_error * error = (virtual io_error *)exc;
     408        if (NULL == error) {
     409            return false;
     410        }
     411        ...
     412        return true;
     413    }
     414
     415### Extension: Implicate Virtual Cast Target
     416This is a small extension, even in the example above `io_error *` is repeated
     417in the cast and the variable being assigned to. Using return type inference
     418would allow the second type to be skipped in cases it is clear what type is
     419being checked against.
     420
     421The line then becomes:
     422
     423    io_error * error = (virtual)exc;
     424
     425### Extension: Inline vtables
    314426Since the structures here are usually made to be turned into trait objects
    315 it might be worth it to have fields on them to store the virtual table
     427it might be worth it to have fields in them to store the virtual table
    316428pointer. This would have to be declared on the trait as an assertion (example:
    317429`vtable;` or `T.vtable;`), but if it is the trait object could be a single
     
    320432There are also three options for where the pointer to the vtable. It could be
    321433anywhere, a fixed location for each trait or always at the front. For the per-
    322 trait solution an extention to specify what it is (example `vtable[0];`) which
     434trait solution an extension to specify what it is (example `vtable[0];`) which
    323435could also be used to combine it with others. So these options can be combined
    324436to allow access to all three options.
     
    344456the type declaration, including the functions that satisfy the trait, are
    345457all defined. Currently there are many points where this can happen, not all
    346 of them will have the same definitions and no way to select one over the
    347 other.
     458of them have the same definitions and no way to select one over the other.
    348459
    349460Some syntax would have to be added to specify the resolution point. To ensure
     
    395506
    396507These could also be placed inside functions. In which case both the name and
    397 the default keyword might be optional. If the name is ommited in an assignment
    398 the closest vtable is choosen (returning to the global default rule if no
    399 approprate local vtable is in scope).
     508the default keyword might be optional. If the name is omitted in an assignment
     509the closest vtable is chosen (returning to the global default rule if no
     510appropriate local vtable is in scope).
    400511
    401512### Site Based Resolution:
  • src/AST/porting.md

    r4ab0669 r336d0b3  
    9696
    9797`Expr`
    98 * Merged `inferParams`/`resnSlots` into union, as suggested by comment
     98* Merged `inferParams`/`resnSlots` into union, as suggested by comment in old version
     99  * does imply get_/set_ API, and some care about moving backward
    99100
    100101`Label`
Note: See TracChangeset for help on using the changeset viewer.