Index: doc/proposals/vtable.md =================================================================== --- doc/proposals/vtable.md (revision 686f731009686a6516b3765a330ea882719321f4) +++ doc/proposals/vtable.md (revision 0727d97a496de36de89a35cb96c00a6772a97d98) @@ -8,11 +8,11 @@ The basic concept of a virtual table (vtable) is the same here as in most -other languages. They will mostly contain function pointers although they -should be able to store anything that goes into a trait. - -I also include notes on a sample implementation, which primarly exists to show -there is a resonable implementation. The code samples for that are in a slight -psudo-code to help avoid name mangling and keeps some CFA features while they -would actually be writen in C. +other languages that use them. They will mostly contain function pointers +although they should be able to store anything that goes into a trait. + +I also include notes on a sample implementation, which primarily exists to show +there is a reasonable implementation. The code samples for that are in a slight +pseudo-code to help avoid name mangling and keeps some CFA features while they +would actually be written in C. Trait Instances @@ -20,26 +20,28 @@ Currently traits are completely abstract. Data types might implement a trait -but traits are not themselves data types. This will change that and allow -instances of traits to be created from instances of data types that implement -the trait. +but traits are not themselves data types. Which is to say you cannot have an +instance of a trait. This proposal will change that and allow instances of +traits to be created from instances of data types that implement the trait. + +For example: trait combiner(otype T) { - void combine(T&, int); - }; + void combine(T&, int); + }; struct summation { - int sum; - }; - - void ?{}( struct summation & this ) { - this.sum = 0; - } + int sum; + }; + + void ?{}( struct summation & this ) { + this.sum = 0; + } void combine( struct summation & this, int num ) { - this.sum = this.sum + num; - } - - trait combiner obj = struct summation{}; - combine(obj, 5); + this.sum = this.sum + num; + } + + trait combiner obj = struct summation{}; + combine(obj, 5); As with `struct` (and `union` and `enum`), `trait` might be optional when @@ -49,16 +51,30 @@ For traits to be used this way they should meet two requirements. First they should only have a single polymorphic type and each assertion should use that -type once as a parameter. Extentions may later loosen these requirements. - -If a trait object is used it should generate a series of implicate functions -each of which implements one of the functions required by the trait. So for -combiner there is an implicate: - - void combine(trait combiner & this, int); - -This function is the one actually called at the end +type once as a parameter. Extensions may later loosen these requirements. + +Also note this applies to the final expanded list of assertions. Consider: + + trait foo(otype T, otype U) { + ... functions that use T once ... + } + + trait bar(otype S | foo(S, char)) { + ... functions that use S once ... + } + +In this example `bar` may be used as a type but `foo` may not. + +When a trait is used as a type it creates a generic object which combines +the base structure (an instance of `summation` in this case) and the vtable, +which is currently created and provided by a hidden mechanism. + +The generic object type for each trait also implements that trait. This is +actually the only means by which it can be used. The type of these functions +look something like this: + + void combine(trait combiner & this, int num); The main use case for trait objects is that they can be stored. They can be -passed into functions, but using the trait directly is prefred in this case. +passed into functions, but using the trait directly is preferred in this case. trait drawable(otype T) { @@ -78,19 +94,70 @@ } -Currently these traits are limited to 1 trait parameter and functions should -have exactly 1 parameter. We cannot abstract away pairs of types and still -pass them into normal functions, which take them seperately. - -The second is required the because we need to get the vtable from somewhere. -If there are 0 trait objects than no vtable is avalible, if we have more than -1 than the vtables give conflicting answers on what underlying function to -call. And even then the underlying type assumes a concrete type. - -This loop can sort of be broken by using the trait object directly in the -signature. This has well defined meaning, but might not be useful. +The trait types can also be used in the types of assertions on traits as well. +In this usage they passed as the underlying object and vtable pair as they +are stored. The trait types can also be used in that trait's definition, which +means you can pass two instances of a trait to a single function. However the +look-up of the one that is not used to look up any functions, until another +function that uses that object in the generic/look-up location is called. trait example(otype T) { bool test(T & this, trait example & that); } + +### Explanation Of Restrictions + +The two restrictions on traits that can be used as trait objects are: + +1. Only one generic parameter may be defined in the trait's header. +2. Each function assertion must have one parameter with the type of the + generic parameter. They may or may not return a value of that type. + +Elsewhere in this proposal I suggest ways to broaden these requirements. +A simple example would be if a trait meets requirement 1 but not 2, then +the assertions that do not satisfy the exactly one parameter requirement can +be ignored. + +However I would like to talk about why these two rules are in place in the +first place and the problems that any exceptions to these rules must avoid. + +The problems appear when the dispatcher function which operates on the +generic object. + + trait combiner(otype T, otype U) { + void combine(T&, U); + } + +This one is so strange I don't have proper syntax for it but let us say that +the concrete dispatcher would be typed as +`void combine(combiner(T) &, combiner(U));`. Does the function that combine +the two underlying types exist to dispatch too? + +Maybe not. If `combiner(T)` works with ints and `combiner(U)` is a char then +they could not be. It would have to enforce that all pairs of any types +that are wrapped in this way. Which would pretty much destroy any chance of +separate compilation. + +Even then it would be more expensive as the wrappers would have to carry ids +that you use to look up on an +1 dimensional table. + +The second restriction has a similar issue but makes a bit more sense to +write out. + + trait Series(otype T) { + ... size, iterators, getters ... + T join(T const &, T const &); + } + +With the dispatcher typed as: + + Series join(Series const &, Series const &); + +Because these instances are generic and hide the underlying implementation we +do not know what that implementation is. Unfortunately this also means the +implementation for the two parameters might not be the same. Once we have +two different types involved this devolves into the first case. + +We could check at run-time that the have the same underlying type, but this +would likely time and space overhead and there is no clear recovery path. #### Sample Implementation @@ -116,115 +183,96 @@ There may have to be special cases for things like copy construction, that -might require a more sigificant wrapper. On the other hand moving could be +might require a more significant wrapper. On the other hand moving could be implemented by moving the pointers without any need to refer to the base object. -### Extention: Multiple Trait Parameters -Currently, this gives traits two independent uses. They use the same syntax, -except for limits boxable traits have, and yet don't really mix. The most -natural way to do this is to allow trait instances to pick one parameter -that they are generic over, the others they choose types to implement. - -The two ways to do the selection, the first is do it at the trait definition. -Each trait picks out a single parameter which it can box (here the `virtual` -qualifier). When you create an instance of a trait object you provide -arguments like for a generic structure, but skip over the marked parameter. - - trait combiner(virtual otype T, otype Combined) { - void combine(T &, Combined &); - } - - trait combiner(int) int_combiner; - -The second is to do it at the instaniation point. A placeholder (here the -keyword `virtual`) is used to explicately skip over the parameter that will be -abstracted away, with the same rules as above if it was the marked parameter. - - trait combiner(otype T, otype Combined) { - void combine(T &, Combined &); - }; - - trait combiner(virtual, int) int_combiner; - -Using both (first to set the default, second as a local override) would also -work, although might be exessively complicated. - -This is useful in cases where you want to use a generic type, but leave part -of it open and store partially generic result. As a simple example - - trait folder(otype T, otype In, otype Out) { - void fold(T & this, In); - Out fold_result(T & this); - } - -Which allows you to fold values without putting them in a container. If they -are already in a container this is exessive, but if they are generated over -time this gives you a simple interface. This could for instance be used in -a profile, where T changes for each profiling statistic and you can plug in -multiple profilers for any run by adding them to an array. +### Extension: Multiple Trait Parameters +The base proposal in effect creates another use for the trait syntax that is +related to the ones currently in the language but is also separate from them. +The current uses generic functions and generic types, this new use could be +described as generic objects. + +A generic object is of a concrete type and has concrete functions that work on +it. It is generic in that it is a wrapper for an unknown type. Traits serve +a similar role here as in generic functions as they limit what the function +can be generic over. + +This combines the use allowing to have a generic type that is a generic +object. All but one of the trait's parameters is given a concrete type, +conceptually currying the trait to create a trait with on generic parameter +that fits the original restrictions. The resulting concrete generic object +type is different with each set of provided parameters and their values. + +Then it just becomes a question of where this is done. Again both examples use +a basic syntax to show the idea. + + trait iterator(virtual otype T, otype Item) { + bool has_next(T const &); + Item get_next(T const *); + } + + iterator(int) int_it = begin(container_of_ints); + +The first option is to do it at the definition of the trait. One parameter +is selected (here with the `virtual` keyword, but other rules like "the first" +could also be used) and when an instance of the trait is created all the +other parameters must be provided. + + trait iterator(otype T, otype Item) { + bool has_next(T const &); + Item get_next(T const *); + } + + iterator(virtual, int) int_it = begin(container_of_ints); + +The second option is to skip a parameter as part of the type instance +definition. One parameter is explicitly skipped (again with the `virtual` +keyword) and the others have concrete types. The skipped one is the one we +are generic on. + +Incidentally in both examples `container_of_ints` may itself be a generic +object and `begin` returns a generic iterator with unknown implementation. + +These options are not exclusive. Defining a default on the trait allows for +an object to be created as in the first example. However, whether the +default is provided or not, the second syntax can be used to pick a +parameter on instantiation. Hierarchy --------- -Virtual tables by them selves are not quite enough to implement the planned -hierarchy system. An addition of type ids, implemented as pointers which -point to your parent's type id, is required to actually create the shape of -the hierarchy. However vtables would allow behaviour to be carried with the -tree. - -The hierarchy would be a tree of types, of traits and structs. Currently we do -not support structural extension, so traits form the internal nodes and -structures the leaf nodes. - -The syntax is undecided but it will include a clause like `virtual (PARENT)` -on trait and struct definitions. It marks out all types in a hierarchy. -PARENT may be omitted, if it is this type is the root of a hierarchy. Otherwise -it is the name of the type that is this type's parent in the hierarchy. - -Traits define a trait instance type that implements all assertions in this -trait and its parents up until the root of the hierarchy. Each trait then -defines a vtable type. Structures will also have a vtable type but it should -be the same as their parent's. - -Trait objects within the tree can be statically cast to a parent type. Casts -from a parent type to a child type are conditional, they check to make sure -the underlying instance is an instance of the child type, or an instance of -one of its children. The type then is recoverable at run-time. - -As with regular trait objects, calling a function on a trait object will cause -a look-up on the the virtual table. The casting rules make sure anything that -can be cast to a trait type will have all the function implementations for -that trait. - -Converting from a concrete type (structures at the edge of the hierarchy) to -an abstract type works the same as with normal trait objects, the underlying -object is packaged with a virtual table pointer. Converting back to an abstract -type requires confirming the underlying type matches, but then simply extracts -the pointer to it. - -Exception Example: +We would also like to implement hierarchical relations between types. + + AstNode + |-ParseNode + | |-Declaration + | | |-DeclarationWithType + | | |-StructureDeclaration + | |-Statement + | | |-CompoundStatement + | |-Expression + |-Type + +Virtual tables by themselves are not quite enough to implement this system. +A vtable is just a list of functions and there is no way to check at run-time +what these functions, we carry that knowledge with the table. + +This proposal adds type ids to check for position in the hierarchy and an +explicate syntax for establishing a hierarchical relation between traits and +their implementing types. The ids should uniquely identify each type and +allow retrieval of the type's parent if one exists. By recursion this allows +the ancestor relation between any two hierarchical types can be checked. + +The hierarchy is created with traits as the internal nodes and structures +as the leaf nodes. The structures may be used normally and the traits can +be used to create generic objects as in the first section (the same +restrictions apply). However these type objects store their type id which can +be recovered to figure out which type they are or at least check to see if +they fall into a given sub-tree at run-time. + +Here is an example of part of a hierarchy. The `virtual(PARENT)` syntax is +just an example. But when used it give the name of the parent type or if +empty it shows that this type is the root of its hierarchy. (Also I'm not sure where I got these casing rules.) - - trait exception(otype T) virtual() { - char const * what(T & this); - } - - trait io_error(otype T) virtual(exception) { - FILE * which_file(T & this); - } - - struct eof_error(otype T) virtual(io_error) { - FILE * file; - } - - char const * what(eof_error &) { - return "Tried to read from an empty file."; - } - - FILE * which_file(eof_error & this) { - return eof_error.file; - } - -Ast Example: trait ast_node(otype T) virtual() { @@ -267,4 +315,25 @@ } +### Extension: Structural Inheritance +An extension would be allow structures to be used as internal nodes on the +inheritance tree. Its child types would have to implement the same fields. + +The weaker restriction would be to convert the fields into field assertions +(Not implemented yet: `U T.x` means there is a field of type you on the type +T. Offset unknown and passed in/stored with function pointers.) +A concrete child would have to declare the same set of fields with the same +types. This is of a more functional style. + +The stronger restriction is that the fields of the parent are a prefix of the +child's fields. Possibly automatically inserted. This the imperative view and +may also have less overhead. + +### Extension: Unions and Enumerations +Currently there is no reason unions and enumerations, in the cases they +do implement the trait, could not be in the hierarchy as leaf nodes. + +It does not work with structural induction, but that could just be a compile +time check that all ancestors are traits or do not add field assertions. + #### Sample Implementation The type id may be as little as: @@ -275,5 +344,5 @@ Some linker magic would have to be used to ensure exactly one copy of each -structure for each type exists in memory. There seem to be spectial once +structure for each type exists in memory. There seem to be special once sections that support this and it should be easier than generating unique ids across compilation units. @@ -300,18 +369,61 @@ ### Virtual Casts -To convert from a pointer to a type higher on the hierarchy to one lower on -the hierarchy a check is used to make sure that the underlying type is also -of that lower type. - -The proposed syntax for this is: +The generic objects may be cast up and down the hierarchy. + +Casting to an ancestor type always succeeds. From one generic type to another +is just a reinterpretation and could be implicate. Wrapping and unwrapping +a concrete type will probably use the same syntax as in the first section. + +Casting from an ancestor to a descendent requires a check. The underlying +type may or may not belong to the sub-tree headed by that descendent. For this +we introduce a new cast operator, which returns the pointer unchanged if the +check succeeds and null otherwise. trait SubType * new_value = (virtual trait SubType *)super_type; -It will return the same pointer if it does point to the subtype and null if -it does not, doing the check and conversion in one operation. - -### Inline vtables +For the following example I am using the as of yet finished exception system. + + trait exception(otype T) virtual() { + char const * what(T & this); + } + + trait io_error(otype T) virtual(exception) { + FILE * which_file(T & this); + } + + struct eof_error(otype T) virtual(io_error) { + FILE * file; + } + + char const * what(eof_error &) { + return "Tried to read from an empty file."; + } + + FILE * which_file(eof_error & this) { + return eof_error.file; + } + + bool handleIoError(exception * exc) { + io_error * error = (virtual io_error *)exc; + if (NULL == error) { + return false; + } + ... + return true; + } + +### Extension: Implicate Virtual Cast Target +This is a small extension, even in the example above `io_error *` is repeated +in the cast and the variable being assigned to. Using return type inference +would allow the second type to be skipped in cases it is clear what type is +being checked against. + +The line then becomes: + + io_error * error = (virtual)exc; + +### Extension: Inline vtables Since the structures here are usually made to be turned into trait objects -it might be worth it to have fields on them to store the virtual table +it might be worth it to have fields in them to store the virtual table pointer. This would have to be declared on the trait as an assertion (example: `vtable;` or `T.vtable;`), but if it is the trait object could be a single @@ -320,5 +432,5 @@ There are also three options for where the pointer to the vtable. It could be anywhere, a fixed location for each trait or always at the front. For the per- -trait solution an extention to specify what it is (example `vtable[0];`) which +trait solution an extension to specify what it is (example `vtable[0];`) which could also be used to combine it with others. So these options can be combined to allow access to all three options. @@ -344,6 +456,5 @@ the type declaration, including the functions that satisfy the trait, are all defined. Currently there are many points where this can happen, not all -of them will have the same definitions and no way to select one over the -other. +of them have the same definitions and no way to select one over the other. Some syntax would have to be added to specify the resolution point. To ensure @@ -395,7 +506,7 @@ These could also be placed inside functions. In which case both the name and -the default keyword might be optional. If the name is ommited in an assignment -the closest vtable is choosen (returning to the global default rule if no -approprate local vtable is in scope). +the default keyword might be optional. If the name is omitted in an assignment +the closest vtable is chosen (returning to the global default rule if no +appropriate local vtable is in scope). ### Site Based Resolution: