Changeset ff3fc93


Ignore:
Timestamp:
Jul 28, 2016, 4:15:51 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, ctor, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, memory, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
2750cde, ac43954
Parents:
d5905a2
Message:

Minor edits to Comp II draft

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/aaron_comp_II/comp_II.tex

    rd5905a2 rff3fc93  
    8585
    8686\CFA\footnote{Pronounced ``C-for-all'', and written \CFA, CFA, or \CFL.} is an evolutionary modernization of the C programming language currently being designed and built at the University of Waterloo by a team led by Peter Buhr.
    87 Features added to C by \CFA include name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others.
    88 These features make \CFA significantly more powerful and expressive than C, but impose a significant compile-time cost to implement, particularly in the expression resolver, which must evaluate the typing rules of a much more complex type system.
     87\CFA adds multiple features to C, including name overloading, user-defined operators, parametric-polymorphic routines, and type constructors and destructors, among others.
     88These features make \CFA significantly more powerful and expressive than C, but impose a significant compile-time cost to support, particularly in the expression resolver, which must evaluate the typing rules of a much more complex type system.
    8989The primary goal of this proposed research project is to develop a sufficiently performant expression resolution algorithm, experimentally validate its performance, and integrate it into \Index*{CFA-CC}, the \CFA reference compiler.
    9090Secondary goals of this project include the development of various new language features for \CFA; parametric-polymorphic (``generic'') types have already been designed and implemented, and reference types and user-defined conversions are under design consideration.
    91 The experimental performance-testing architecture for resolution algorithms will also be used to determine the compile-time cost of adding such new features to the \CFA type system.
     91The experimental performance-testing architecture for resolution algorithms will also be used to determine the compile-time cost of adding such new features to the \CFA type system.
     92More broadly, this research should provide valuable data for implementers of compilers for other programming languages with similarly powerful static type systems.
    9293
    9394\section{\CFA}
     
    9899\subsection{Polymorphic Functions}
    99100The most significant feature \CFA adds is parametric-polymorphic functions.
    100 Such functions are written using a ©forall© clause, the feature that gave the language its name:
     101Such functions are written using a ©forall© clause (which gives the language its name):
    101102\begin{lstlisting}
    102103forall(otype T)
     
    126127
    127128Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions.
    128 For instance, ©twice© could have been define as below, using the \CFA syntax for operator overloading:
     129For instance, ©twice© could have been defined as below, using the \CFA syntax for operator overloading:
    129130\begin{lstlisting}
    130131forall(otype S | { S ?+?(S, S); })
     
    132133\end{lstlisting}
    133134This version of ©twice© will work for any type ©S© that has an addition operator defined for it, and it could have been used to satisfy the type assertion on ©four_times©.
    134 The compiler accomplishes this by creating a wrapper function calling ©twice // (2)© with ©S© bound to ©double©, then providing this wrapper function to ©four_times©\footnote{©twice // (2)© could have had a type parameter named ©T©; \CFA specifies a renaming the type parameters, which would avoid the name conflict with the parameter ©T© of ©four_times©.}.
     135The compiler accomplishes this by creating a wrapper function calling ©twice // (2)© with ©S© bound to ©double©, then providing this wrapper function to ©four_times©\footnote{©twice // (2)© could also have had a type parameter named ©T©; \CFA specifies renaming of the type parameters, which would avoid the name conflict with the type variable ©T© of ©four_times©.}.
    135136
    136137Finding appropriate functions to satisfy type assertions is essentially a recursive case of expression resolution, as it takes a name (that of the type assertion) and attempts to match it to a suitable declaration in the current scope.
    137138If a polymorphic function can be used to satisfy one of its own type assertions, this recursion may not terminate, as it is possible that function will be examined as a candidate for its own type assertion unboundedly repeatedly.
    138139To avoid infinite loops, the current \Index*{CFA-CC} compiler imposes a fixed limit on the possible depth of recursion, similar to that employed by most \Index*[C++]{\CC} compilers for template expansion; this restriction means that there are some semantically well-typed expressions which cannot be resolved by {CFA-CC}.
    139 One area of potential improvement this project proposes to investigate is the possibility of using the compiler's knowledge of the current set of declarations to make a more precise judgement of when further type assertion satisfaction recursion will not produce a well-typed expression.
     140One area of potential improvement this project proposes to investigate is the possibility of using the compiler's knowledge of the current set of declarations to more precicely determine when further type assertion satisfaction recursion will not produce a well-typed expression.
    140141
    141142\subsection{Name Overloading}
     
    168169Such a conversion system should be simple for user programmers to utilize, and fit naturally with the existing design of implicit conversions in C; ideally it would also be sufficiently powerful to encode C's usual arithmetic conversions itself, so that \CFA only has one set of rules for conversions.
    169170
    170 Glen Ditchfield \textbf{TODO CITE} has laid out a framework for using polymorphic conversion constructor functions to create a directed acyclic graph (DAG) of conversions.
     171Ditchfield\cite{Ditchfield:conversions} has laid out a framework for using polymorphic conversion constructor functions to create a directed acyclic graph (DAG) of conversions.
    171172A monomorphic variant of these functions can be used to mark a conversion arc in the DAG as only usable as the final step in a conversion.
    172173With these two types of conversion arcs, separate DAGs can be created for the safe and the unsafe conversions, and conversion cost can be represented as path length through the DAG.
     
    207208\CFA adds \emph{tuple types} to C, a facility for referring to multiple values with a single identifier.
    208209A variable may name a tuple, and a function may return one.
    209 Particularly relevantly for resolution, a tuple may be automatically \emph{destructured} into a list of values, as in the ©swap© function below:
     210Particularly relevantly for resolution, a tuple may be implicitly \emph{destructured} into a list of values, as in the call to ©swap© below:
    210211\begin{lstlisting}
    211212[char, char] x = [ '!', '?' ];
     
    215216
    216217x = swap( x ); // destructure [char, char] x into two elements of parameter list
    217 // ^ can't use int x for parameter, not enough arguments to swap
     218// can't use int x for parameter, not enough arguments to swap
    218219\end{lstlisting}
    219220Tuple destructuring means that the mapping from the position of a subexpression in the argument list to the position of a paramter in the function declaration is not straightforward, as some arguments may be expandable to different numbers of parameters, like ©x© above.
     
    250251
    251252The research goal of this project is to develop a performant expression resolver for \CFA; this analysis suggests two primary areas of investigation to accomplish that end.
    252 The first is efficient argument-parameter matching; Bilson\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing {CFA-CC} compiler \textbf{TODO:} \textit{look up and lit review}.
     253The first is efficient argument-parameter matching; Bilson\cite{Bilson03} mentions significant optimization opportunities available in the current literature to improve on the existing {CFA-CC} compiler.
     254%TODO: look up and lit review
    253255The second, and likely more fruitful, area of investigation is heuristics and algorithmic approaches to reduce the number of argument interpretations considered in the common case; given the large ($p+1$) exponent on number of interpretations considered in the runtime analysis, even small reductions here could have a significant effect on overall resolver runtime.
    254256The discussion below presents a number of largely orthagonal axes for expression resolution algorithm design to be investigated, noting prior work where applicable.
    255257
    256258\subsection{Argument-Parameter Matching}
    257 The first axis we consider is argument-parameter matching - whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
     259The first axis we consider is argument-parameter matching --- whether the type matching for a candidate function to a set of candidate arguments is directed by the argument types or the parameter types.
    258260
    259261\subsubsection{Argument-directed (``Bottom-up'')}
     
    296298\subsubsection{On Arguments}
    297299Another approach would be to generate a set of possible implicit conversions for each set of interpretations of a given argument.
    298 This would have the benefit of detecting ambiguous interpretations of arguments at the level of the argument rather than its containing call, and would also never find more than one interpretation of the argument with a given type.
     300This would have the benefit of detecting ambiguous interpretations of arguments at the level of the argument rather than its containing call, would also never find more than one interpretation of the argument with a given type, and would re-use calculation of implicit conversions between function candidates.
    299301On the other hand, this approach may unncessarily generate argument interpretations that will never match a parameter, wasting work.
    300302
     
    321323Under this approach the \CFA resolver could, for instance, try expression interpretations in the following order:
    322324\begin{enumerate}
    323 \item All interpretations with no polymorphic type binding or implicit conversions.
     325\item Interpretations with no polymorphic type binding or implicit conversions.
    324326\item Interpretations containing no polymorphic type binding and at least one safe implicit conversion.
    325327\item Interpretations containing polymorphic type binding, but only safe implicit conversions.
     
    370372The experimental results will also provide some empirical sense of the compile-time cost of various language features by comparing the results of the most performant resolver variant that supports the feature with the most performant resolver variant that doesn't, a useful capability to guide language design.
    371373
     374This proposed project should provide valuable data on how to implement a performant compiler for modern programming languages such as \CFA with powerful static type systems, specifically targeting the feature interaction between name overloading and implicit conversions.
     375
    372376\appendix
    373377\section{Completion Timeline}
  • doc/bibliography/cfa.bib

    rd5905a2 rff3fc93  
    16231623    year        = 1974,
    16241624}
     1625
     1626@unpublished{Ditchfield:conversions,
     1627        contributer = {a3moss@uwaterloo.ca},
     1628        author = {Glen Ditchfield},
     1629        title = {Conversions for {Cforall}},
     1630        note = {\href{http://plg.uwaterloo.ca/~cforall/Conversions/index.html}{http://\-plg.uwaterloo.ca/\-\textasciitilde cforall/\-Conversions/\-index.html}},
     1631        month = {Nov},
     1632        year = {2002},
     1633        urldate = {28 July 2016},
     1634}
     1635
    16251636
    16261637@techreport{Dijkstra65,
Note: See TracChangeset for help on using the changeset viewer.