[24662ff] | 1 | Proposal For Use of Virtual Tables
|
---|
| 2 | ==================================
|
---|
| 3 |
|
---|
| 4 | This is an adaptation of the earlier virtual proposal, updating it with new
|
---|
[1b94115] | 5 | ideas, re-framing it and laying out more design decisions. It should
|
---|
| 6 | eventually replace the earlier proposal, but not all features and syntax have
|
---|
| 7 | been converted to the new design.
|
---|
[24662ff] | 8 |
|
---|
| 9 | The 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 | Trait Instances
|
---|
| 14 | ---------------
|
---|
| 15 |
|
---|
| 16 | Currently traits are completely abstract. Data types might implement a trait
|
---|
| 17 | but traits are not themselves data types. This will change that and allow
|
---|
| 18 | instances of traits to be created from instances of data types that implement
|
---|
| 19 | the trait.
|
---|
| 20 |
|
---|
| 21 | trait combiner(otype T) {
|
---|
| 22 | void combine(T&, int);
|
---|
| 23 | };
|
---|
| 24 |
|
---|
| 25 | struct summation {
|
---|
| 26 | int sum;
|
---|
| 27 | };
|
---|
| 28 |
|
---|
| 29 | void ?{}( struct summation & this ) {
|
---|
| 30 | this.sum = 0;
|
---|
| 31 | }
|
---|
| 32 |
|
---|
| 33 | void combine( struct summation & this, int num ) {
|
---|
| 34 | this.sum = this.sum + num;
|
---|
| 35 | }
|
---|
| 36 |
|
---|
| 37 | trait combiner obj = struct summation{};
|
---|
| 38 | combine(obj, 5);
|
---|
| 39 |
|
---|
[1b94115] | 40 | As with `struct` (and `union` and `enum`), `trait` might be optional when
|
---|
| 41 | using the trait as a type name. A trait may be used in assertion list as
|
---|
| 42 | before.
|
---|
| 43 |
|
---|
[24662ff] | 44 | Internally a trait object is a pair of pointers. One to an underlying object
|
---|
| 45 | and the other to the vtable. All calls on an trait are implemented by looking
|
---|
| 46 | up the matching function pointer and passing the underlying object and the
|
---|
| 47 | remaining arguments to it.
|
---|
| 48 |
|
---|
[1b94115] | 49 | Trait objects can be moved by moving the pointers. Almost all other operations
|
---|
| 50 | require some functions to be implemented on the underlying type. Depending on
|
---|
| 51 | what is in the virtual table a trait type could be a dtype or otype.
|
---|
[24662ff] | 52 |
|
---|
| 53 | Hierarchy
|
---|
| 54 | ---------
|
---|
| 55 |
|
---|
| 56 | Virtual tables by them selves are not quite enough to implement the planned
|
---|
| 57 | hierarchy system. An addition of type ids, implemented as pointers which
|
---|
| 58 | point to your parent's type id, is required to actually create the shape of
|
---|
| 59 | the hierarchy. However vtables would allow behaviour to be carried with the
|
---|
| 60 | tree.
|
---|
| 61 |
|
---|
[1b94115] | 62 | The hierarchy would be a tree of types, of traits and structs. Currently we do
|
---|
[24662ff] | 63 | not support structural extension, so traits form the internal nodes and
|
---|
| 64 | structures the leaf nodes.
|
---|
| 65 |
|
---|
| 66 | The syntax is undecided but it will include a clause like `virtual (PARENT)`
|
---|
| 67 | on trait and struct definitions. It marks out all types in a hierarchy.
|
---|
[1b94115] | 68 | PARENT may be omitted, if it is this type is the root of a hierarchy. Otherwise
|
---|
[24662ff] | 69 | it is the name of the type that is this type's parent in the hierarchy.
|
---|
| 70 |
|
---|
| 71 | Traits define a trait instance type that implements all assertions in this
|
---|
| 72 | trait and its parents up until the root of the hierarchy. Each trait then
|
---|
| 73 | defines a vtable type. Structures will also have a vtable type but it should
|
---|
| 74 | be the same as their parent's.
|
---|
| 75 |
|
---|
| 76 | Trait objects within the tree can be statically cast to a parent type. Casts
|
---|
| 77 | from a parent type to a child type are conditional, they check to make sure
|
---|
| 78 | the underlying instance is an instance of the child type, or an instance of
|
---|
[1b94115] | 79 | one of its children. The type then is recoverable at run-time.
|
---|
[24662ff] | 80 |
|
---|
| 81 | As with regular trait objects, calling a function on a trait object will cause
|
---|
[1b94115] | 82 | a look-up on the the virtual table. The casting rules make sure anything that
|
---|
[24662ff] | 83 | can be cast to a trait type will have all the function implementations for
|
---|
| 84 | that trait.
|
---|
| 85 |
|
---|
[1b94115] | 86 | Converting from a concrete type (structures at the edge of the hierarchy) to
|
---|
[24662ff] | 87 | an abstract type works the same as with normal trait objects, the underlying
|
---|
[1b94115] | 88 | object is packaged with a virtual table pointer. Converting back to an abstract
|
---|
[24662ff] | 89 | type requires confirming the underlying type matches, but then simply extracts
|
---|
| 90 | the pointer to it.
|
---|
| 91 |
|
---|
| 92 | ### Inline vtables
|
---|
| 93 | Since the structures here are usually made to be turned into trait objects
|
---|
| 94 | it might be worth it to have fields on them to store the virtual table
|
---|
| 95 | pointer. This would have to be declared on the trait as an assertion, but if
|
---|
| 96 | it is the trait object could be a single pointer.
|
---|
| 97 |
|
---|
[1b94115] | 98 | It is trivial to do if the field with the virtual table pointer is fixed.
|
---|
[24662ff] | 99 | Otherwise some trickery with pointing to the field and storing the offset in
|
---|
| 100 | the virtual table to recover the main object would have to be used.
|
---|
| 101 |
|
---|
| 102 | ### Virtual Tables as Types
|
---|
| 103 | Here we consider encoding plus the implementation of functions on it. Which
|
---|
| 104 | is to say in the type hierarchy structures aren't concrete types anymore,
|
---|
| 105 | instead they are parent types to vtables, which combine the encoding and
|
---|
| 106 | implementation.
|
---|
| 107 |
|
---|
| 108 | Resolution Scope
|
---|
| 109 | ----------------
|
---|
| 110 |
|
---|
| 111 | What is the scope of a resolution? When are the functions in a vtable decided
|
---|
| 112 | and how broadly is this applied?
|
---|
| 113 |
|
---|
| 114 | ### Type Level:
|
---|
| 115 | Each structure has a single resolution for all of the functions in the
|
---|
| 116 | virtual trait. This is how many languages that implement this or similar
|
---|
| 117 | features do it.
|
---|
| 118 |
|
---|
| 119 | The main thing CFA would need to do it this way is some single point where
|
---|
[1b94115] | 120 | the type declaration, including the functions that satisfy the trait, are
|
---|
[24662ff] | 121 | all defined. Currently there are many points where this can happen, not all
|
---|
| 122 | of them will have the same definitions and no way to select one over the
|
---|
| 123 | other.
|
---|
| 124 |
|
---|
| 125 | Some syntax would have to be added. All resolutions can be found at compile
|
---|
| 126 | time and a single vtable created for each type at compilation time.
|
---|
| 127 |
|
---|
[1b94115] | 128 | ### Explicit Resolution Points:
|
---|
| 129 | Slightly looser than the above, there are explicit points where the vtables
|
---|
[24662ff] | 130 | are resolved, but there is no limit on the number of resolution points that
|
---|
| 131 | might be provided. Each time a object is bound to a trait, one of the
|
---|
[1b94115] | 132 | resolutions is selected. This might be the most flexible option.
|
---|
[24662ff] | 133 |
|
---|
| 134 | An syntax would have to be provided as above. There may also be the option
|
---|
| 135 | to name resolution points so that you can choose between them. This also
|
---|
[1b94115] | 136 | could come with the ability to forward declare them.
|
---|
[24662ff] | 137 |
|
---|
| 138 | Especially if they are not named, these resolution points should be able to
|
---|
| 139 | appear in functions, where the scoping rules can be used to select one.
|
---|
| 140 | However this also means that stack-allocated functions can end up in the
|
---|
| 141 | vtable.
|
---|
| 142 |
|
---|
| 143 | ### Site Based Resolution:
|
---|
| 144 | Every place in code where the binding of a vtable to an object occurs has
|
---|
| 145 | its own resolution. Syntax-wise this is the simplest as it should be able
|
---|
| 146 | to use just the existing declarations and the conversion to trait object.
|
---|
[1b94115] | 147 | It also is very close to the current polymorphic resolution rules.
|
---|
[24662ff] | 148 |
|
---|
[1b94115] | 149 | This works as the explicit resolution points except the resolution points
|
---|
| 150 | are implicit and their would be no selection of which resolution to use. The
|
---|
[24662ff] | 151 | closest (current) resolution is always selected.
|
---|
| 152 |
|
---|
[1b94115] | 153 | This could easily lead to an explosion of vtables as it has the most fine
|
---|
[24662ff] | 154 | grained resolution the number of bindings in a single scope (that produces
|
---|
| 155 | the same binding) could be quite high. Merging identical vtables might help
|
---|
| 156 | reduce that.
|
---|
| 157 |
|
---|
| 158 | Vtable Lifetime Issues
|
---|
| 159 | ----------------------
|
---|
| 160 |
|
---|
| 161 | Vtables interact badly with the thunk issue. Conceptually vtables are static
|
---|
[1b94115] | 162 | like type/function data they carry, as those decisions are made by the
|
---|
[24662ff] | 163 | resolver at compile time.
|
---|
| 164 |
|
---|
| 165 | Stack allocated functions interact badly with this because they are not
|
---|
[1b94115] | 166 | static. There are several ways to try to resolve this, however without a
|
---|
[24662ff] | 167 | general solution most can only buy time.
|
---|
| 168 |
|
---|
| 169 | Filling in some fields of a static vtable could cause issues on a recursive
|
---|
| 170 | call. And then we are still limited by the lifetime of the stack functions, as
|
---|
| 171 | the vtable with stale pointers is still a problem.
|
---|
| 172 |
|
---|
| 173 | Dynamically allocated vtables introduces memory management overhead and
|
---|
[1b94115] | 174 | requires some way to differentiate between dynamic and statically allocated
|
---|
[24662ff] | 175 | tables. The stale function pointer problem continues unless those becomes
|
---|
| 176 | dynamically allocated as well which gives us the same costs again.
|
---|
| 177 |
|
---|
| 178 | Stack allocating the vtable seems like the best issue. The vtable's lifetime
|
---|
| 179 | is now the limiting factor but it should be effectively the same as the
|
---|
| 180 | shortest lifetime of a function assigned to it. However this still limits the
|
---|
[1b94115] | 181 | lifetime "implicitly" and returns to the original problem with thunks.
|
---|