Changes in / [957453d:8b28a52]

File:

• doc/proposals/virtual.txt (modified) (4 diffs)

doc/proposals/virtual.txt

@@ -1 +1 @@
 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 :
@@ -28 +20 @@
 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 };
@@ -49 +41 @@
 }
 
-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.
+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++.
 
-Using trait references to implement the above gives the following :
+A simple usage of dynamic type with the previous example would look like :
 
-trait drawable objects[10];
+drawable* objects[10];
 fill_objects(objects);
 
 while(running) {
-      for(drawable object : objects) {
+      for(drawable* object : objects) {
             draw(object);
       }
 }
 
-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.
+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).
 
-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.
+C++ uses inheritance and virtual functions to find the
+desired type dynamically. CFA takes inspiration from this solution.
 
-For instance specifying that the drawable trait reference looks up the type
-of the first argument to find the implemenation would be :
+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:
 
 trait drawable(otype T) {
@@ -81 +73 @@
 };
 
-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.
+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.
 
-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.
+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 :
 
-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.
+struct text {
+      char* text;
+      vtable drawable;
+};
 
-Extention: Multi-parameter Virtual Traits:
+struct line{
+      vtable drawable;
+      vec2 start;
+      vec2 end;
+};
 
-This implementation can be extented to traits with multiple parameters if
-one is called out as being the virtual trait. For example :
+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.
 
-trait iterator(otype T, dtype Item) {
-        Maybe(Item) next(virtual T *);
+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;
 }
 
-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 *);
+//Tedious forwarding routine
+void* get_stack(fat_ucontext_t *ptr) {
+      return get_stack(ptr->context);
 }
 
-trait io_error(otype T) virtual error {
-        FILE * src(T *);
-}
+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).
 
-struct eof_error virtual io_error {
-        FILE * fd;
+The alternative we propose is to use language level fat pointers :
+
+trait MyContext(otype T) {
+      void* get_stack(virtual T*)
 };
 
-So the trait error is the head of a new tree and io_error is a child of it.
+void* get_stack(ucontext_t *context);
 
-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.
+//The type vptr(ucontext_t) all
+vptr(ucontext_t) context;
 
-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.
+These behave exactly as the previous example but all the forwarding routines are automatically generated.
 
-Extention: Multiple Parents
+Bikeshedding.
 
-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 :
+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.
 
-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.