Changes in / [336d0b3:4ab0669]

1 deleted
2 edited


  • doc/proposals/

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

    r336d0b3 r4ab0669  
    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
     98* Merged `inferParams`/`resnSlots` into union, as suggested by comment
Note: See TracChangeset for help on using the changeset viewer.