# Changeset 1ca52db

Ignore:
Timestamp:
Mar 23, 2017, 5:20:29 PM (6 years ago)
Branches:
aaron-thesis, arm-eh, 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:
fe1b6a4
Parents:
89e1b16
Message:

Add more background and generics material to paper

Location:
doc
Files:
3 edited

### Legend:

Unmodified
 r89e1b16 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]]} }
 r89e1b16 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}, }% \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} \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} \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): } \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: 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} \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) 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. \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}