Proposal For Use of Virtual Tables ================================== This is an adaptation of the earlier virtual proposal, updating it with new ideas, re-framing it and laying out more design decisions. It should eventually replace the earlier proposal, but not all features and syntax have been converted to the new design. 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. 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); As with `struct` (and `union` and `enum`), `trait` might be optional when using the trait as a type name. A trait may be used in assertion list as before. 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 moved by moving the pointers. Almost all other operations require some functions to be implemented on the underlying type. Depending on what is in the virtual table a trait type could be a dtype or otype. 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. ### 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 trivial 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 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. 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. ### Explicit Resolution Points: Slightly looser than the above, there are explicit 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 flexible 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 ability 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 resolution rules. This works as the explicit resolution points except the resolution points are implicit and their would be no selection of which resolution to use. The closest (current) resolution is always selected. This could easily lead to an explosion 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 decisions are made by the resolver at compile time. Stack allocated functions interact badly with this because they are not static. There are several 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 differentiate 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 "implicitly" and returns to the original problem with thunks.