Changeset 336d0b3

Timestamp:

May 13, 2019, 1:11:40 PM (6 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

768b3b4f, fdbd4fd

Parents:

4ab0669 (diff), 0727d97 (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

Files:

• doc/proposals/vtable.md (modified) (11 diffs)
• src/AST/Expr.hpp (added)
• src/AST/porting.md (modified) (1 diff)

doc/proposals/vtable.md

@@ -8 +8 @@
 
 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.
-
-I also include notes on a sample implementation, which primarly exists to show
-there is a resonable implementation. The code samples for that are in a slight
-psudo-code to help avoid name mangling and keeps some CFA features while they
-would actually be writen in C.
+other languages that use them. They will mostly contain function pointers
+although they should be able to store anything that goes into a trait.
+
+I also include notes on a sample implementation, which primarily exists to show
+there is a reasonable implementation. The code samples for that are in a slight
+pseudo-code to help avoid name mangling and keeps some CFA features while they
+would actually be written in C.
 
 Trait Instances
@@ -20 +20 @@
 
 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.
+but traits are not themselves data types. Which is to say you cannot have an
+instance of a trait. This proposal will change that and allow instances of
+traits to be created from instances of data types that implement the trait.
+
+For example:
 
     trait combiner(otype T) {
-                void combine(T&, int);
-        };
+        void combine(T&, int);
+    };
 
     struct summation {
-                int sum;
-        };
-
-        void ?{}( struct summation & this ) {
-                this.sum = 0;
-        }
+        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);
+        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
@@ -49 +51 @@
 For traits to be used this way they should meet two requirements. First they
 should only have a single polymorphic type and each assertion should use that
-type once as a parameter. Extentions may later loosen these requirements.
-
-If a trait object is used it should generate a series of implicate functions
-each of which implements one of the functions required by the trait. So for
-combiner there is an implicate:
-
-    void combine(trait combiner & this, int);
-
-This function is the one actually called at the end
+type once as a parameter. Extensions may later loosen these requirements.
+
+Also note this applies to the final expanded list of assertions. Consider:
+
+    trait foo(otype T, otype U) {
+        ... functions that use T once ...
+    }
+
+    trait bar(otype S | foo(S, char)) {
+        ... functions that use S once ...
+    }
+
+In this example `bar` may be used as a type but `foo` may not.
+
+When a trait is used as a type it creates a generic object which combines
+the base structure (an instance of `summation` in this case) and the vtable,
+which is currently created and provided by a hidden mechanism.
+
+The generic object type for each trait also implements that trait. This is
+actually the only means by which it can be used. The type of these functions
+look something like this:
+
+    void combine(trait combiner & this, int num);
 
 The main use case for trait objects is that they can be stored. They can be
-passed into functions, but using the trait directly is prefred in this case.
+passed into functions, but using the trait directly is preferred in this case.
 
     trait drawable(otype T) {
@@ -78 +94 @@
     }
 
-Currently these traits are limited to 1 trait parameter and functions should
-have exactly 1 parameter. We cannot abstract away pairs of types and still
-pass them into normal functions, which take them seperately.
-
-The second is required the because we need to get the vtable from somewhere.
-If there are 0 trait objects than no vtable is avalible, if we have more than
-1 than the vtables give conflicting answers on what underlying function to
-call. And even then the underlying type assumes a concrete type.
-
-This loop can sort of be broken by using the trait object directly in the
-signature. This has well defined meaning, but might not be useful.
+The trait types can also be used in the types of assertions on traits as well.
+In this usage they passed as the underlying object and vtable pair as they
+are stored. The trait types can also be used in that trait's definition, which
+means you can pass two instances of a trait to a single function. However the
+look-up of the one that is not used to look up any functions, until another
+function that uses that object in the generic/look-up location is called.
 
     trait example(otype T) {
         bool test(T & this, trait example & that);
     }
+
+### Explanation Of Restrictions
+
+The two restrictions on traits that can be used as trait objects are:
+
+1.  Only one generic parameter may be defined in the trait's header.
+2.  Each function assertion must have one parameter with the type of the
+    generic parameter. They may or may not return a value of that type.
+
+Elsewhere in this proposal I suggest ways to broaden these requirements.
+A simple example would be if a trait meets requirement 1 but not 2, then
+the assertions that do not satisfy the exactly one parameter requirement can
+be ignored.
+
+However I would like to talk about why these two rules are in place in the
+first place and the problems that any exceptions to these rules must avoid.
+
+The problems appear when the dispatcher function which operates on the
+generic object.
+
+    trait combiner(otype T, otype U) {
+        void combine(T&, U);
+    }
+
+This one is so strange I don't have proper syntax for it but let us say that
+the concrete dispatcher would be typed as
+`void combine(combiner(T) &, combiner(U));`. Does the function that combine
+the two underlying types exist to dispatch too?
+
+Maybe not. If `combiner(T)` works with ints and `combiner(U)` is a char then
+they could not be. It would have to enforce that all pairs of any types
+that are wrapped in this way. Which would pretty much destroy any chance of
+separate compilation.
+
+Even then it would be more expensive as the wrappers would have to carry ids
+that you use to look up on an <number of types>+1 dimensional table.
+
+The second restriction has a similar issue but makes a bit more sense to
+write out.
+
+    trait Series(otype T) {
+        ... size, iterators, getters ...
+        T join(T const &, T const &);
+    }
+
+With the dispatcher typed as:
+
+    Series join(Series const &, Series const &);
+
+Because these instances are generic and hide the underlying implementation we
+do not know what that implementation is. Unfortunately this also means the
+implementation for the two parameters might not be the same. Once we have
+two different types involved this devolves into the first case.
+
+We could check at run-time that the have the same underlying type, but this
+would likely time and space overhead and there is no clear recovery path.
 
 #### Sample Implementation
@@ -116 +183 @@
 
 There may have to be special cases for things like copy construction, that
-might require a more sigificant wrapper. On the other hand moving could be
+might require a more significant wrapper. On the other hand moving could be
 implemented by moving the pointers without any need to refer to the base
 object.
 
-### Extention: Multiple Trait Parameters
-Currently, this gives traits two independent uses. They use the same syntax,
-except for limits boxable traits have, and yet don't really mix. The most
-natural way to do this is to allow trait instances to pick one parameter
-that they are generic over, the others they choose types to implement.
-
-The two ways to do the selection, the first is do it at the trait definition.
-Each trait picks out a single parameter which it can box (here the `virtual`
-qualifier). When you create an instance of a trait object you provide
-arguments like for a generic structure, but skip over the marked parameter.
-
-    trait combiner(virtual otype T, otype Combined) {
-        void combine(T &, Combined &);
-    }
-
-    trait combiner(int) int_combiner;
-
-The second is to do it at the instaniation point. A placeholder (here the
-keyword `virtual`) is used to explicately skip over the parameter that will be
-abstracted away, with the same rules as above if it was the marked parameter.
-
-    trait combiner(otype T, otype Combined) {
-        void combine(T &, Combined &);
-    };
-
-    trait combiner(virtual, int) int_combiner;
-
-Using both (first to set the default, second as a local override) would also
-work, although might be exessively complicated.
-
-This is useful in cases where you want to use a generic type, but leave part
-of it open and store partially generic result. As a simple example
-
-    trait folder(otype T, otype In, otype Out) {
-        void fold(T & this, In);
-        Out fold_result(T & this);
-    }
-
-Which allows you to fold values without putting them in a container. If they
-are already in a container this is exessive, but if they are generated over
-time this gives you a simple interface. This could for instance be used in
-a profile, where T changes for each profiling statistic and you can plug in
-multiple profilers for any run by adding them to an array.
+### Extension: Multiple Trait Parameters
+The base proposal in effect creates another use for the trait syntax that is
+related to the ones currently in the language but is also separate from them.
+The current uses generic functions and generic types, this new use could be
+described as generic objects.
+
+A generic object is of a concrete type and has concrete functions that work on
+it. It is generic in that it is a wrapper for an unknown type. Traits serve
+a similar role here as in generic functions as they limit what the function
+can be generic over.
+
+This combines the use allowing to have a generic type that is a generic
+object. All but one of the trait's parameters is given a concrete type,
+conceptually currying the trait to create a trait with on generic parameter
+that fits the original restrictions. The resulting concrete generic object
+type is different with each set of provided parameters and their values.
+
+Then it just becomes a question of where this is done. Again both examples use
+a basic syntax to show the idea.
+
+    trait iterator(virtual otype T, otype Item) {
+        bool has_next(T const &);
+        Item get_next(T const *);
+    }
+
+    iterator(int) int_it = begin(container_of_ints);
+
+The first option is to do it at the definition of the trait. One parameter
+is selected (here with the `virtual` keyword, but other rules like "the first"
+could also be used) and when an instance of the trait is created all the
+other parameters must be provided.
+
+    trait iterator(otype T, otype Item) {
+        bool has_next(T const &);
+        Item get_next(T const *);
+    }
+
+    iterator(virtual, int) int_it = begin(container_of_ints);
+
+The second option is to skip a parameter as part of the type instance
+definition. One parameter is explicitly skipped (again with the `virtual`
+keyword) and the others have concrete types. The skipped one is the one we
+are generic on.
+
+Incidentally in both examples `container_of_ints` may itself be a generic
+object and `begin` returns a generic iterator with unknown implementation.
+
+These options are not exclusive. Defining a default on the trait allows for
+an object to be created as in the first example. However, whether the
+default is provided or not, the second syntax can be used to pick a
+parameter on instantiation.
 
 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.
-
-Exception Example:
+We would also like to implement hierarchical relations between types.
+
+    AstNode
+    |-ParseNode
+    | |-Declaration
+    | | |-DeclarationWithType
+    | | |-StructureDeclaration
+    | |-Statement
+    | | |-CompoundStatement
+    | |-Expression
+    |-Type
+
+Virtual tables by themselves are not quite enough to implement this system.
+A vtable is just a list of functions and there is no way to check at run-time
+what these functions, we carry that knowledge with the table.
+
+This proposal adds type ids to check for position in the hierarchy and an
+explicate syntax for establishing a hierarchical relation between traits and
+their implementing types. The ids should uniquely identify each type and
+allow retrieval of the type's parent if one exists. By recursion this allows
+the ancestor relation between any two hierarchical types can be checked.
+
+The hierarchy is created with traits as the internal nodes and structures
+as the leaf nodes. The structures may be used normally and the traits can
+be used to create generic objects as in the first section (the same
+restrictions apply). However these type objects store their type id which can
+be recovered to figure out which type they are or at least check to see if
+they fall into a given sub-tree at run-time.
+
+Here is an example of part of a hierarchy. The `virtual(PARENT)` syntax is
+just an example. But when used it give the name of the parent type or if
+empty it shows that this type is the root of its hierarchy.
 (Also I'm not sure where I got these casing rules.)
-
-    trait exception(otype T) virtual() {
-        char const * what(T & this);
-    }
-
-    trait io_error(otype T) virtual(exception) {
-        FILE * which_file(T & this);
-    }
-
-    struct eof_error(otype T) virtual(io_error) {
-        FILE * file;
-    }
-
-    char const * what(eof_error &) {
-        return "Tried to read from an empty file.";
-    }
-
-    FILE * which_file(eof_error & this) {
-        return eof_error.file;
-    }
-
-Ast Example:
 
     trait ast_node(otype T) virtual() {
@@ -267 +315 @@
     }
 
+### Extension: Structural Inheritance
+An extension would be allow structures to be used as internal nodes on the
+inheritance tree. Its child types would have to implement the same fields.
+
+The weaker restriction would be to convert the fields into field assertions
+(Not implemented yet: `U T.x` means there is a field of type you on the type
+T. Offset unknown and passed in/stored with function pointers.)
+A concrete child would have to declare the same set of fields with the same
+types. This is of a more functional style.
+
+The stronger restriction is that the fields of the parent are a prefix of the
+child's fields. Possibly automatically inserted. This the imperative view and
+may also have less overhead.
+
+### Extension: Unions and Enumerations
+Currently there is no reason unions and enumerations, in the cases they
+do implement the trait, could not be in the hierarchy as leaf nodes.
+
+It does not work with structural induction, but that could just be a compile
+time check that all ancestors are traits or do not add field assertions.
+
 #### Sample Implementation
 The type id may be as little as:
@@ -275 +344 @@
 
 Some linker magic would have to be used to ensure exactly one copy of each
-structure for each type exists in memory. There seem to be spectial once
+structure for each type exists in memory. There seem to be special once
 sections that support this and it should be easier than generating unique
 ids across compilation units.
@@ -300 +369 @@
 
 ### Virtual Casts
-To convert from a pointer to a type higher on the hierarchy to one lower on
-the hierarchy a check is used to make sure that the underlying type is also
-of that lower type.
-
-The proposed syntax for this is:
+The generic objects may be cast up and down the hierarchy.
+
+Casting to an ancestor type always succeeds. From one generic type to another
+is just a reinterpretation and could be implicate. Wrapping and unwrapping
+a concrete type will probably use the same syntax as in the first section.
+
+Casting from an ancestor to a descendent requires a check. The underlying
+type may or may not belong to the sub-tree headed by that descendent. For this
+we introduce a new cast operator, which returns the pointer unchanged if the
+check succeeds and null otherwise.
 
     trait SubType * new_value = (virtual trait SubType *)super_type;
 
-It will return the same pointer if it does point to the subtype and null if
-it does not, doing the check and conversion in one operation.
-
-### Inline vtables
+For the following example I am using the as of yet finished exception system.
+
+    trait exception(otype T) virtual() {
+        char const * what(T & this);
+    }
+
+    trait io_error(otype T) virtual(exception) {
+        FILE * which_file(T & this);
+    }
+
+    struct eof_error(otype T) virtual(io_error) {
+        FILE * file;
+    }
+
+    char const * what(eof_error &) {
+        return "Tried to read from an empty file.";
+    }
+
+    FILE * which_file(eof_error & this) {
+        return eof_error.file;
+    }
+
+    bool handleIoError(exception * exc) {
+        io_error * error = (virtual io_error *)exc;
+        if (NULL == error) {
+            return false;
+        }
+        ...
+        return true;
+    }
+
+### Extension: Implicate Virtual Cast Target
+This is a small extension, even in the example above `io_error *` is repeated
+in the cast and the variable being assigned to. Using return type inference
+would allow the second type to be skipped in cases it is clear what type is
+being checked against.
+
+The line then becomes:
+
+    io_error * error = (virtual)exc;
+
+### Extension: 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
+it might be worth it to have fields in them to store the virtual table
 pointer. This would have to be declared on the trait as an assertion (example:
 `vtable;` or `T.vtable;`), but if it is the trait object could be a single
@@ -320 +432 @@
 There are also three options for where the pointer to the vtable. It could be
 anywhere, a fixed location for each trait or always at the front. For the per-
-trait solution an extention to specify what it is (example `vtable[0];`) which
+trait solution an extension to specify what it is (example `vtable[0];`) which
 could also be used to combine it with others. So these options can be combined
 to allow access to all three options.
@@ -344 +456 @@
 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.
+of them have the same definitions and no way to select one over the other.
 
 Some syntax would have to be added to specify the resolution point. To ensure
@@ -395 +506 @@
 
 These could also be placed inside functions. In which case both the name and
-the default keyword might be optional. If the name is ommited in an assignment
-the closest vtable is choosen (returning to the global default rule if no
-approprate local vtable is in scope).
+the default keyword might be optional. If the name is omitted in an assignment
+the closest vtable is chosen (returning to the global default rule if no
+appropriate local vtable is in scope).
 
 ### Site Based Resolution:

src/AST/porting.md

@@ -96 +96 @@
 
 `Expr`
-* Merged `inferParams`/`resnSlots` into union, as suggested by comment
+* Merged `inferParams`/`resnSlots` into union, as suggested by comment in old version
+  * does imply get_/set_ API, and some care about moving backward
 
 `Label`