Changeset 0318c7a for doc/aaron_comp_II

Jul 21, 2016, 10:45:11 AM (8 years ago)
Aaron Moss <a3moss@…>
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, ctor, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Added sections on constructors and destructors, generic types to comp II draft

1 edited


  • doc/aaron_comp_II/comp_II.tex

    rfd603d8 r0318c7a  
    163163In addition to the multiple interpretations of an expression produced by name overloading, \CFA also supports all of the implicit conversions present in C, producing further candidate interpretations for expressions.
    164164C does not have a traditionally-defined inheritance hierarchy of types, but the C standard's rules for the ``usual arithmetic conversions'' define which of the built-in types are implicitly convertable to which other types, and the relative cost of any pair of such conversions from a single source type.
    165 \CFA adds to the usual arithmetic conversions rules for determining the cost of binding a polymorphic type variable in a function call; such bindings are cheaper than any \emph{unsafe} (narrowing) conversion, {e.g.} ©int© to ©char©, but more expensive than any \emph{safe} (widening) conversion, {e.g.} ©int© to ©double©.
     165\CFA adds to the usual arithmetic conversions rules for determining the cost of binding a polymorphic type variable in a function call; such bindings are cheaper than any \emph{unsafe} (narrowing) conversion, \eg ©int© to ©char©, but more expensive than any \emph{safe} (widening) conversion, \eg ©int© to ©double©.
    166166The expression resolution problem, then, is to find the unique minimal-cost interpretation of each expression in the program, where all identifiers must be matched to a declaration, implicit conversions or polymorphic bindings of the result of an expression may increase the cost of the expression, and which subexpression interpretation is minimal-cost may be disambiguated by context.
    175175Open research questions on this topic include whether a conversion graph can be generated that represents each allowable conversion in C with a unique minimal-length path, such that the path lengths accurately represent the relative costs of the conversions, whether such a graph representation can be usefully augmented to include user-defined types as well as built-in types, and whether the graph can be efficiently represented and included in the expression resolver.
     177\subsection{Constructors \& Destructors}
     178Rob Shluntz, a current member of the \CFA research team, has added constructors and destructors to \CFA.
     179Each type has an overridable default-generated zero-argument constructor, copy constructor, assignment operator, and destructor; for struct types these functions each call their equivalents on each field of the struct.
     180This affects expression resolution because an ©otype© type variable ©T© implicitly adds four type assertions, one for each of these four functions, so assertion resolution is pervasive in \CFA polymorphic functions, even those without any explicit type assertions.
    177182\subsection{Generic Types}
     183The author has added a generic type capability to \CFA, designed to efficiently and naturally integrate with \CFA's existing polymorphic functions.
     184A generic type can be declared by placing a ©forall© specifier on a struct or union declaration, and instantiated using a parenthesized list of types after the type name:
     186forall(otype R, otype S) struct pair {
     187    R first;
     188    S second;
     191forall(otype T)
     192T value( pair(const char*, T) *p ) { return p->second; }
     194pair(const char*, int) p = { "magic", 42 };
     195int magic = value( &p );
     197For \emph{concrete} generic types, that is, those where none of the type parameters depend on polymorphic type variables (like ©pair(const char*, int)© above), the struct is essentially template expanded to a new struct type; for \emph{polymorphic} generic types (such as ©pair(const char*, T)© above), member access is handled by a runtime calculation of the field offset, based on the size and alignment information of the polymorphic parameter type.
     198The default-generated constructors, destructor \& assignment operator for a generic type are polymorphic functions with the same list of type parameters as the generic type definition.
     200Aside from giving users the ability to create more parameterized types than just the built-in pointer, array \& function types, the combination of generic types with polymorphic functions and implicit conversions makes the edge case where a polymorphic function can match its own assertions much more common, as follows:
     202\item A polymorphic implicit conversion (such as the built-in conversion from ©void*© to any other pointer type) applied to an expression can produce an expression of any type.
     203\item If we attempt to use a generic type with ©otype© parameters (such as ©box© above) for this type, the ©otype© parameters on the constructors, \etc will also need to be resolved, and will have no constraints on what they may be.
     204\item Attempting to match some yet-to-be-determined specialization of the generic type to this ©otype© parameter will create a recursive case of the default constructor, \etc matching their own type assertions, creating an unboundedly deep nesting of the generic type inside itself.
     206As discussed above, any \CFA expression resolver must handle this possible infinite recursion somehow, but the combination of generic types with other language features makes this particular edge case occur somewhat frequently in user code.
    179208\subsection{Multiple Return Values}
    181210\subsection{Reference Types}
    182211% TODO discuss rvalue-to-lvalue conversion here
     213\subsection{Literal Types}
     214% TODO talk about zero_t, one_t here, implication that some common expressions will have many outbound implicit conversions
     216\subsection{Deletable Functions}
    184218\section{Expression Resolution}
Note: See TracChangeset for help on using the changeset viewer.