Index: doc/proposals/vtable.md =================================================================== --- doc/proposals/vtable.md (revision 24662ff50dfb325fe8845d2ec497b66224708e7d) +++ doc/proposals/vtable.md (revision 24662ff50dfb325fe8845d2ec497b66224708e7d) @@ -0,0 +1,177 @@ +Proposal For Use of Virtual Tables +================================== + +This is an adaptation of the earlier virtual proposal, updating it with new +ideas, reframing it and laying out more design decisions. + +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. + +This should replace the virtual proposal, although all not all features have +been converted to the new design. + +Trait Instances +--------------- + +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. + + trait combiner(otype T) { + void combine(T&, int); + }; + + struct summation { + 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); + +Internally a trait object is a pair of pointers. One to an underlying object +and the other to the vtable. All calls on an trait are implemented by looking +up the matching function pointer and passing the underlying object and the +remaining arguments to it. + +Trait objects can be copied and moved by copying and moving the pointers. +They should also be able to own or borrow the underlying object. + +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 hierachy 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 hierachy. 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 runtime. + +As with regular trait objects, calling a function on a trait object will cause +a lookup 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 hierchy) to +an abstract type works the same as with normal trait objects, the underlying +object is packaged with a virtal table pointer. Converting back to an abstract +type requires confirming the underlying type matches, but then simply extracts +the pointer to it. + +### 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 +pointer. This would have to be declared on the trait as an assertion, but if +it is the trait object could be a single pointer. + +It is trival to do if the field with the virtual table pointer is fixed. +Otherwise some trickery with pointing to the field and storing the offset in +the virtual table to recover the main object would have to be used. + +### Virtual Tables as Types +Here we consider encoding plus the implementation of functions on it. Which +is to say in the type hierarchy structures aren't concrete types anymore, +instead they are parent types to vtables, which combine the encoding and +implementation. + +Resolution Scope +---------------- + +What is the scope of a resolution? When are the functions in a vtable decided +and how broadly is this applied? + +### Type Level: +Each structure has a single resolution for all of the functions in the +virtual trait. This is how many languages that implement this or similar +features do it. + +The main thing CFA would need to do it this way is some single point where +the type declaration, including the functions that satify 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. + +Some syntax would have to be added. All resolutions can be found at compile +time and a single vtable created for each type at compilation time. + +### Explicate Resolution Points: +Slightly looser than the above, there are explicate points where the vtables +are resolved, but there is no limit on the number of resolution points that +might be provided. Each time a object is bound to a trait, one of the +resolutions is selected. This might be the most flexable option. + +An syntax would have to be provided as above. There may also be the option +to name resolution points so that you can choose between them. This also +could come with the ablity to forward declare them. + +Especially if they are not named, these resolution points should be able to +appear in functions, where the scoping rules can be used to select one. +However this also means that stack-allocated functions can end up in the +vtable. + +### Site Based Resolution: +Every place in code where the binding of a vtable to an object occurs has +its own resolution. Syntax-wise this is the simplest as it should be able +to use just the existing declarations and the conversion to trait object. +It also is very close to the current polymorphic reolution rules. + +This works as the explicate resolution points except the resolution points +are implicate and their would be no selection of which resolution to use. The +closest (current) resolution is always selected. + +This could easily lead to an explosition of vtables as it has the most fine +grained resolution the number of bindings in a single scope (that produces +the same binding) could be quite high. Merging identical vtables might help +reduce that. + +Vtable Lifetime Issues +---------------------- + +Vtables interact badly with the thunk issue. Conceptually vtables are static +like type/function data they carry, as those decitions are made by the +resolver at compile time. + +Stack allocated functions interact badly with this because they are not +static. There are serveral ways to try to resolve this, however without a +general solution most can only buy time. + +Filling in some fields of a static vtable could cause issues on a recursive +call. And then we are still limited by the lifetime of the stack functions, as +the vtable with stale pointers is still a problem. + +Dynamically allocated vtables introduces memory management overhead and +requires some way to differentate between dynamic and statically allocated +tables. The stale function pointer problem continues unless those becomes +dynamically allocated as well which gives us the same costs again. + +Stack allocating the vtable seems like the best issue. The vtable's lifetime +is now the limiting factor but it should be effectively the same as the +shortest lifetime of a function assigned to it. However this still limits the +lifetime "implicately" and returns to the original problem with thunks.