Index: doc/generic_types/.gitignore =================================================================== --- doc/generic_types/.gitignore (revision 89e1b16d05935066e64637eb65d157b36ee24ad0) +++ doc/generic_types/.gitignore (revision 1ca52db4ee57d04b401c8b21816639da5b4043b7) @@ -13,3 +13,5 @@ *.ps *.toc +*.lof +*.lot *.synctex.gz Index: doc/generic_types/generic_types.bib =================================================================== --- doc/generic_types/generic_types.bib (revision 89e1b16d05935066e64637eb65d157b36ee24ad0) +++ doc/generic_types/generic_types.bib (revision 1ca52db4ee57d04b401c8b21816639da5b4043b7) @@ -20,2 +20,11 @@ note = {\href{http://plg.uwaterloo.ca/theses/DitchfieldThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-DitchfieldThesis.pdf}} } + +@mastersthesis{Schluntz17, + author = {Schluntz, Robert}, + title = {Resource Management and Tuples in C$\mathbf{\forall}$}, + school = {School of Computer Science, University of Waterloo}, + year = 2017, + address = {Waterloo, Ontario, Canada, N2L 3G1}, + note = {[[unpublished]]} +} Index: doc/generic_types/generic_types.tex =================================================================== --- doc/generic_types/generic_types.tex (revision 89e1b16d05935066e64637eb65d157b36ee24ad0) +++ doc/generic_types/generic_types.tex (revision 1ca52db4ee57d04b401c8b21816639da5b4043b7) @@ -20,5 +20,5 @@ morekeywords={_Alignas,_Alignof,__alignof,__alignof__,asm,__asm,__asm__,_At,_Atomic,__attribute,__attribute__,auto, _Bool,catch,catchResume,choose,_Complex,__complex,__complex__,__const,__const__,disable,dtype,enable,__extension__, - fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,_Static_assert, + fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,sized,_Static_assert, _Thread_local,throw,throwResume,trait,try,typeof,__typeof,__typeof__,zero_t}, }% @@ -57,5 +57,5 @@ \acmJournal{PACMPL} -\title{Generic Types with Efficient Dynamic Layout in \CFA{}} +\title{Generic and Tuple Types with Efficient Dynamic Layout in \CFA{}} \author{Aaron Moss} @@ -95,6 +95,6 @@ \email{pabuhr@uwaterloo.ca} -\terms{generic, types} -\keywords{generic types, polymorphic functions, Cforall} +\terms{generic, tuple, types} +\keywords{generic types, tuple types, polymorphic functions, C, Cforall} \begin{CCSXML} @@ -132,7 +132,17 @@ \section{Introduction \& Background} -\CFA{}\footnote{Pronounced ``C-for-all'', and written \CFA{} or Cforall.} is an evolutionary extension of the C programming language which aims to add modern language features to C while maintaining both source compatibility with C and a familiar mental model for programmers. This paper describes how generic types are designed and implemented in \CFA{}, and how they interact with \CFA{}'s polymorphic functions. +\CFA{}\footnote{Pronounced ``C-for-all'', and written \CFA{} or Cforall.} is an evolutionary extension of the C programming language which aims to add modern language features to C while maintaining both source compatibility with C and a familiar mental model for programmers. Four key design goals were set out in the original design of \CFA{} \citep{Bilson03}: +\begin{enumerate} +\item The behaviour of standard C code must remain the same when translated by a \CFA{} compiler as when translated by a C compiler. +\item Standard C code must be as fast and as small when translated by a \CFA{} compiler as when translated by a C compiler. +\item \CFA{} code must be at least as portable as standard C code. +\item Extensions introduced by \CFA{} must be translated in the most efficient way possible. +\end{enumerate} +The purpose of these goals is to ensure that existing C codebases can be converted to \CFA{} incrementally and with minimal effort, and that programmers who already know C can productively produce \CFA{} code without extensive training beyond the extension features they wish to employ. + +\CFA{} has been previously extended with polymorphic functions and name overloading (including operator overloading) \citep{Bilson03}, and deterministically-executed constructors and destructors \citep{Schluntz17}. This paper describes how generic and tuple types are designed and implemented in \CFA{} in accordance with both the backward compatibility goals and existing features described above. \subsection{Polymorphic Functions} +\label{sec:poly-fns} \CFA{}'s polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}. The signature feature of \CFA{} is parametric-polymorphic functions; such functions are written using a @forall@ clause (which gives the language its name): @@ -191,4 +201,5 @@ } \end{lstlisting} +This capability allows specifying the same set of assertions in multiple locations, without the repetition and likelihood of mistakes that come with manually writing them out for each function declaration. @otype@ is essentially syntactic sugar for the following trait: @@ -198,7 +209,27 @@ void ?{}(T*); // default constructor void ?{}(T*, T); // copy constructor - T ?=?(T*, T); // assignment operator + void ?=?(T*, T); // assignment operator void ^?{}(T*); // destructor }; +\end{lstlisting} +Given this information, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @abs@ function above would produce generated code something like the following (simplified for clarity and brevity): +\begin{lstlisting} +void abs( size_t _sizeof_M, size_t _alignof_M, + void (*_ctor_M)(void*), void (*_copy_M)(void*, void*), + void (*_assign_M)(void*, void*), void (*_dtor_M)(void*), + bool (*_lt_M)(void*, void*), void (*_neg_M)(void*, void*), + void (*_ctor_M_zero)(void*, int), + void* m, void* _rtn ) { // polymorphic parameter and return passed as void* + // M zero = { 0 }; + void* zero = alloca(_sizeof_M); // stack allocate 0 temporary + _ctor_M_zero(zero, 0); // initialize using zero_t constructor + // return m < zero ? -m : m; + void *_tmp = alloca(_sizeof_M) + _copy_M( _rtn, // copy-initialize return value + _lt_M( m, zero ) ? // check condition + (_neg_M(m, _tmp), _tmp) : // negate m + m); + _dtor_M(_tmp); _dtor_M(zero); // destroy temporaries +} \end{lstlisting} @@ -282,6 +313,11 @@ \end{lstlisting} -\TODO{} Maybe move this after the rest of the discussion. -This re-use of dtype-static struct instantiations enables some useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T*@ as a type-checked replacement for @void*@, as in this example, which takes a @qsort@ or @bsearch@-compatible comparison routine and creates a similar lexicographic comparison for pairs of pointers: +Though \CFA{} implements concrete generic types efficiently, it also has a fully-general system for computing with dynamic generic types. As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. Dynamic generic structs also come with an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0.}. Access to members\footnote{The \lstinline@offsetof@ macro is implmented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where neccessary. + +\TODO{} Discuss caller-provided versus callee-provided offset arrays, layout functions. + +Whether a type is concrete, dtype-static, or dynamic is decided based solely on the type parameters and @forall@ clause on the struct declaration. This allows opaque forward declarations of generic types like @forall(otype T) struct Box;@ -- like in C, all uses of @Box(T)@ can be in a separately compiled translation unit, and callers from other translation units will know the proper calling conventions to use. If the definition of a struct type was included in the determination of dynamic or concrete, some further types may be recognized as dtype-static (\eg, @forall(otype T) struct unique_ptr { T* p };@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in this way is judged to be an appropriate trade-off. + +The re-use of dtype-static struct instantiations enables some useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T*@ as a type-checked replacement for @void*@, as in this example, which takes a @qsort@ or @bsearch@-compatible comparison routine and creates a similar lexicographic comparison for pairs of pointers: \begin{lstlisting} forall(dtype T) @@ -311,5 +347,5 @@ scalar(metres) marathon = half_marathon + half_marathon; scalar(litres) two_pools = swimming_pool + swimming_pool; -marathon + swimming_pool; // ERRORv -- caught by compiler +marathon + swimming_pool; // ERROR -- caught by compiler \end{lstlisting} @scalar@ is a dtype-static type, so all uses of it will use a single struct definition, containing only a single @unsigned long@, and can share the same implementations of common routines like @?+?@ -- these implementations may even be separately compiled, unlike \CC{} template functions. However, the \CFA{} type-checker will ensure that matching types are used by all calls to @?+?@, preventing nonsensical computations like adding the length of a marathon to the volume of an olympic pool. @@ -323,9 +359,11 @@ \section{Related Work} -\TODO{} Talk about \CC{}, Cyclone, \etc{} - -\section{Conclusion} - -\TODO{} +\TODO{} Talk about \CC{}, Cyclone, maybe D, Rust, \etc{} + +A major difference between the approaches of \CC{} and \CFA{} to polymorphism is that the set of assumed properties for a type is \emph{explicit} in \CFA{}. One of the major limiting factors of \CC{}'s approach is that templates cannot be separately compiled. In contrast, the explicit nature of assertions allows \CFA{}'s polymorphic functions to be separately compiled. + +\section{Conclusion \& Future Work} + +\TODO{} Among future work, talk about ideas for selectively template-expanding code (on decls for specific types, or on calls for accessible decls). \bibliographystyle{ACM-Reference-Format} Index: doc/rob_thesis/.gitignore =================================================================== --- doc/rob_thesis/.gitignore (revision 1ca52db4ee57d04b401c8b21816639da5b4043b7) +++ doc/rob_thesis/.gitignore (revision 1ca52db4ee57d04b401c8b21816639da5b4043b7) @@ -0,0 +1,17 @@ +# generated by latex +*.aux +*.bbl +*.blg +*.brf +*.dvi +*.idx +*.ilg +*.ind +*.log +*.out +*.pdf +*.ps +*.toc +*.lof +*.lot +*.synctex.gz