Changeset 33218c6 for doc/proposals

Timestamp:

Jul 26, 2017, 12:19:41 PM (8 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

b947fb2

Parents:

e0a653d (diff), ea91c42 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

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
+(implicit) and strict (explicit). Relaxed is the simpler case that uses the
+existing trait system with the addition of trait references and vtables.
+Strict adds some constraints and requires some additional notation but allows
+for down-casting.
+
+Relaxed Virtual Inheritance:
 
 Imagine the following code :
@@ -20 +28 @@
 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 };
@@ -41 +49 @@
 }
 
-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 implemented, 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 supported 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 implementation would be :
 
 trait drawable(otype T) {
@@ -73 +81 @@
 };
 
-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 explicitly given, or a strong convention would have to be
+enforced (e.g. implementation of trait functions is always drawn from the
+first polymorphic parameter).
+
+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 implementation. 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, initially forbidden, see extension.
+
+Extension: Multi-parameter Virtual Traits:
+
+This implementation can be extended 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 organized 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 implicitly 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 a prefix of a
+child's vtable has the same format as its 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
+conversions from trait references to more particular references, which works
+if the underlying type is, or is a child of, the new trait type.
+
+Extension: 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 separate vtable for each tree the structure is in.
+
+Extension: Multi-parameter Strict Virtual
+
+If a trait has multiple parameters then one must be called out to be the one
+we generate separate vtables for, as in :
+
+trait example(otype T, otype U) virtual(T) ...
+
+This can generate a separate vtable for each U for which all the T+U
+implementations are provided. These are then separate nodes in the tree (or
+the root of different trees) as if each was created individually. Providing a
+single unique instance of these nodes would be the most difficult aspect of
+this extension, possibly intractable, though with sufficient hoisting and
+link-once duplication it may be possible.
+
+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 *);
+};
+
+Extension: Structural Inheritance
+
+Currently traits must be the internal nodes and structs the leaf nodes.
+Structs could be made internal nodes as well, in which case the child structs
+would likely structurally inherit the fields of their parents.
+
+
+Storing the Virtual Lookup Table (vtable):
+
+We have so far 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 required). For strict virtual this must happen at the
+global scope and forbidding 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 implicitly.
+
+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 compatibility 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 then 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 retrieve 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
+then there should be some way to retrieve 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.