Context Navigation

-                      rac10576
+                      rd49bfa8
 Proposal for virtual functionality
+There are two types of virtual inheritance in this proposal, relaxed
+(implicate) and strict (explicate). Relaxed is the simpler case that uses the
+existing trait system with the addition of trait references and vtables.
+Strict adds some constrants and requires some additional notation but allows
+for down-casting.
+Relaxed Virtual Inheritance:
 Imagine the following code :
 …
 void draw(line*);
 While all the members of this simple UI support drawing creating a UI that easily
 supports both these UI requires some tedious boiler-plate code :
+While all the members of this simple UI support drawing creating a UI that
+easily supports both these UI requires some tedious boiler-plate code :
 enum type_t { text, line };
 …
+}
+While this code will work as indented, adding any new widgets or any new widget behaviors
+requires changing existing code to add the desired functionality. To ease this maintenance
+effort required CFA introduces the concept of dynamic types, in a manner similar to C++.
+A simple usage of dynamic type with the previous example would look like :
+drawable* objects[10];
+While this code will work as indented, adding any new widgets or any new
+widget behaviors requires changing existing code to add the desired
+functionality. To ease this maintenance effort required CFA introduces the
+concept of trait references.
+Using trait references to implement the above gives the following :
+trait drawable objects[10];
 fill_objects(objects);
 while(running) {
       for(drawable* object : objects) {
+      for(drawable object : objects) {
             draw(object);
+      }
+}
+However, this is not currently do-able in the current CFA and furthermore is not
+possible to implement statically. Therefore we need to add a new feature to handle
+having dynamic types like this (That is types that are found dynamically not types
+that change dynamically).
+C++ uses inheritance and virtual functions to find the
+desired type dynamically. CFA takes inspiration from this solution.
+What we really want to do is express the fact that calling draw() on a object
+should find the dynamic type of the parameter before calling the routine, much like the
+hand written example given above. We can express this by adding the virtual keyword on
+the parameter of the constraints on our trait:
+The keyword trait is optional (by the same rules as the struct keyword). This
+is not currently suported in CFA and the lookup is not possible to implement
+statically. Therefore we need to add a new feature to handle having dynamic
+lookups like this.
+What we really want to do is express the fact that calling draw() on a trait
+reference should find the underlying type of the given parameter and find how
+it implements the routine, as in the example with the enumeration and union.
+For instance specifying that the drawable trait reference looks up the type
+of the first argument to find the implemenation would be :
 trait drawable(otype T) {
 …
 };
+This expresses the idea that drawable is similar to an abstract base class in C++ and
+also gives meaning to trying to take a pointer of drawable. That is anything that can
+be cast to a drawable pointer has the necessary information to call the draw routine on
+that type. Before that drawable was only a abstract type while now it also points to a
+piece of storage which specify which behavior the object will have at run time.
+This storage needs to be allocate somewhere. C++ just adds an invisible pointer at
+the beginning of the struct but we can do something more explicit for users, actually
+have a visible special field :
+struct text {
+      char* text;
+      vtable drawable;
+};
+struct line{
+      vtable drawable;
+      vec2 start;
+      vec2 end;
+};
+With these semantics, adding a "vtable drawable" means that text pointers and line pointers are now
+convertible to drawable pointers. This conversion will not necessarily be a type only change however, indeed,
+the drawable pointer will point to the field "vtable drawable" not the head of the struct. However, since all
+the types are known at compile time, converting pointers becomes a simple offset operations.
+The vtable field contains a pointer to a vtable which contains all the information needed for the caller
+to find the function pointer of the desired behavior.
+One of the limitations of this design is that it does not support double dispatching, which
+concretely means traits cannot have routines with more than one virtual parameter. This design
+would have many ambiguities if it did support multiple virtual parameter. A futher limitation is
+that traits over more than one type cannot have vtables meaningfully defined for them, as the
+particular vtable to use would be a function of the other type(s) the trait is defined over.
+It is worth noting that the function pointers in these vtables are bound at object construction, rather than
+function call-site, as in Cforall's existing polymorphic functions. As such, it is possible that two objects
+with the same static type would have a different vtable (consider what happens if draw(line*) is overridden
+between the definitions of two line objects). Given that the virtual drawable* erases static types though,
+this should not be confusing in practice. A more distressing possibility is that of creating an object that
+outlives the scope of one of the functions in its vtable. This is certainly a possible bug, but it is of a
+type that C programmers are familiar with, and should be able to avoid by the usual methods.
+Extensibility.
+One of the obvious critics of this implementation is that it lacks extensibility for classes
+that cannot be modified (ex: Linux C headers). However this solution can be extended to
+allow more extensibility by adding "Fat pointers".
+Indeed, users could already "solve" this issue by writing their own fat pointers as such:
+trait MyContext(otype T) {
+      void* get_stack(virtual T*)
+};
+void* get_stack(ucontext_t *context);
+struct fat_ucontext_t {
+      vtable MyContext;
+      ucontext_t *context;
+}
+//Tedious forwarding routine
+void* get_stack(fat_ucontext_t *ptr) {
+      return get_stack(ptr->context);
+}
+However, users would have to write all the virtual methods they want to override and make
+them all simply forward to the existing method that takes the corresponding POCO(Plain Old C Object).
+The alternative we propose is to use language level fat pointers :
+trait MyContext(otype T) {
+      void* get_stack(virtual T*)
+};
+void* get_stack(ucontext_t *context);
+//The type vptr(ucontext_t) all
+vptr(ucontext_t) context;
+These behave exactly as the previous example but all the forwarding routines are automatically generated.
+Bikeshedding.
+It may be desirable to add fewer new keywords than discussed in this proposal; it is possible that "virtual"
+could replace both "vtable" and "vptr" above with unambiguous contextual meaning. However, for purposes of
+clarity in the design discussion it is beneficial to keep the keywords for separate concepts distinct.
+This could be implied in simple cases like this one (single parameter on the
+trait and single generic parameter on the function). In more complex cases it
+would have to be explicately given, or a strong convention would have to be
+enforced.
+Once a function in a trait has been marked as virtual it defines a new
+function that takes in that trait's reference and then dynamically calls the
+underlying type implemenation. Hence a trait reference becomes a kind of
+abstract type, cannot be directly instantiated but can still be used.
+One of the limitations of this design is that it does not support double
+dispatching, which concretely means traits cannot have routines with more than
+one virtual parameter. The program must have a single table to look up the
+function on. Using trait references with traits with more than one parameter
+is also restricted, inistially forbidden, see extention.
+Extention: Multi-parameter Virtual Traits:
+This implementation can be extented to traits with multiple parameters if
+one is called out as being the virtual trait. For example :
+trait iterator(otype T, dtype Item) {
+        Maybe(Item) next(virtual T *);
+}
+iterator(int) generators[10];
+Which creates a collection of iterators that produce integers, regardless of
+how those iterators are implemented. This may require a note that this trait
+is virtual on T and not Item, but noting it on the functions may be enough.
+Strict Virtual Inheritance:
+One powerful feature relaxed virtual does not support is the idea of down
+casting. Once something has been converted into a trait reference there is
+very little we can do to recover and of the type information, only the trait's
+required function implementations are kept.
+To allow down casting strict virtual requires that all traits and structures
+involved be orginized into a tree. Each trait or struct must have a unique
+position on this tree (no multiple inheritance).
+This is declared as follows :
+trait error(otype T) virtual {
+        const char * msg(T *);
+}
+trait io_error(otype T) virtual error {
+        FILE * src(T *);
+}
+struct eof_error virtual io_error {
+        FILE * fd;
+};
+So the trait error is the head of a new tree and io_error is a child of it.
+Also the parent trait is implicately part of the assertions of the children,
+so all children implement the same operations as the parent. By the unique
+path down the tree, we can also uniquely order them so that prefixs of a
+child's vtable has the same format as the parent's.
+This gives us an important extra feature, runtime checking of the parent-child
+relationship with a C++ dynamic_cast like operation. Allowing checked
+convertions from trait references to more particular references, which works
+if the underlying type is, or is a child of, the new trait type.
+Extention: Multiple Parents
+Although each trait/struct must have a unique position on each tree, it could
+have positions on multiple trees. All this requires is the ability to give
+multiple parents, as here :
+trait region(otype T) virtual drawable, collider;
+The restriction being, the parents must come from different trees. This
+object (and all of its children) can be cast to either tree. This is handled
+by generating a seperate vtable for each tree the structure is in.
+Extention: Multi-parameter Strict Virtual
+If a trait has multiple parameters than one must be called out to be the one
+we generate seperate vtables for, as in :
+trait example(otype T, otype U) virtual(T) ...
+This can generate a seperate vtable for each U for which all the T+U
+implementations are provided. These are then seperate nodes in the tree (or
+the root of different trees) as if each was created individually.
+Example:
+trait argument(otype T) virtual {
+        char short_name(virtual T *);
+        bool is_set(virtual T *);
+};
+trait value_argument(otype T, otype U) virtual(T) argument {
+        U get_value(virtual T *);
+};
+Extention: Structural Inheritance
+Currently traits must be the internal nodes and structs the leaf nodes.
+Structs could be made internal nodes as well, and might specify structural
+inheritance.
+Storing the Virtual Lookup Table (vtable):
+We have so fare been silent on how the vtable is created, stored and accessed.
+Creation happens at compile time. Function pointers are found by using the
+same best match rules as elsewhere (additional rules for defaults from the
+parent may or may not be reqired). For strict virtual this must happen at the
+global scope and forbiding static functions, to ensure that a single unique
+vtable is created. Similarly, there may have to be stricter matching rules
+for the functions that go into the vtable, possibly requiring an exact match.
+Relaxed virtual could relax both restrictions, if we allow different vtable
+at different conversion (struct to trait reference) sites. If it is allowed
+local functions being bound to a vtable could cause issues when they go out
+of scope, however this should follow the lifetime rules most C programs
+already follow implicately.
+Most vtables should be stored statically, the only exception being some of
+the relaxed vtables that could have local function pointers. These may be able
+to be stack allocated. All vtables should be immutable and require no manual
+cleanup.
+Access has two main options:
+The first is through the use of fat pointers, or a tuple of pointers. When the
+object is converted to a trait reference, the pointers to its vtables are
+stored along side it.
+This allows for compatability with existing structures (such as those imported
+from C) and is the default storage method unless a different one is given.
+The other is by inlining the vtable pointer as "intrusive vtables". This adds
+a field to the structure to the vtable. The trait reference than has a single
+pointer to this field, the vtable includes an offset to find the beginning of
+the structure again.
+This is used if you specify a vtable field in the structure. If given in the
+trait the vtable pointer in the trait reference can then become a single
+pointer to the vtable field and use that to recover the original object
+pointer as well as retrive all operations.
+trait drawable(otype T) {
+        vtable drawable;
+};
+struct line {
+        vtable drawable;
+        vec2 start;
+        vec2 end;
+};
+This inline code allows trait references to be converted to plain pointers
+(although they still must be called specially). The vtable field may just be
+an opaque block of memory or it may allow user access to the vtable. If so
+than there should be some way to retrive the type of the vtable, which will be
+autogenerated and often unique.
+Keyword Usage:
+It may be desirable to add fewer new keywords than discussed in this proposal.
+It is possible that "virtual" could replace both "vtable" above with
+unambiguous contextual meaning. However, for purposes of clarity in the design
+discussion it is beneficial to keep the keywords for separate concepts distinct.
+Trait References and Operations:
+sizeof(drawable) will return the size of the trait object itself. However :
+line a_line;
+drawable widget = a_line;
+sizeof(widget);
+Will instead return the sizeof the underlying object, although the trait must
+require that its implementation is sized for there to be a meaningful value
+to return. You may also get the size of the trait reference with
+sizeof(&widget);
+Calling free on a trait reference will free the memory for the object. It will
+leave the vtables alone, as those are (always?) statically allocated.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset d49bfa8 for doc/proposals

Legend:

doc/proposals/virtual.txt

Download in other formats: