Changeset 1ca52db


Ignore:
Timestamp:
Mar 23, 2017, 5:20:29 PM (5 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
fe1b6a4
Parents:
89e1b16
Message:

Add more background and generics material to paper

Location:
doc
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/.gitignore

    r89e1b16 r1ca52db  
    1313*.ps
    1414*.toc
     15*.lof
     16*.lot
    1517*.synctex.gz
  • doc/generic_types/generic_types.bib

    r89e1b16 r1ca52db  
    2020    note        = {\href{http://plg.uwaterloo.ca/theses/DitchfieldThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-DitchfieldThesis.pdf}}
    2121}
     22
     23@mastersthesis{Schluntz17,
     24    author  = {Schluntz, Robert},
     25    title   = {Resource Management and Tuples in C$\mathbf{\forall}$},
     26    school      = {School of Computer Science, University of Waterloo},
     27    year        = 2017,
     28    address     = {Waterloo, Ontario, Canada, N2L 3G1},
     29    note    = {[[unpublished]]}
     30}
  • doc/generic_types/generic_types.tex

    r89e1b16 r1ca52db  
    2020        morekeywords={_Alignas,_Alignof,__alignof,__alignof__,asm,__asm,__asm__,_At,_Atomic,__attribute,__attribute__,auto,
    2121                _Bool,catch,catchResume,choose,_Complex,__complex,__complex__,__const,__const__,disable,dtype,enable,__extension__,
    22                 fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,_Static_assert,
     22                fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,sized,_Static_assert,
    2323                _Thread_local,throw,throwResume,trait,try,typeof,__typeof,__typeof__,zero_t},
    2424}%
     
    5757\acmJournal{PACMPL}
    5858
    59 \title{Generic Types with Efficient Dynamic Layout in \CFA{}}
     59\title{Generic and Tuple Types with Efficient Dynamic Layout in \CFA{}}
    6060
    6161\author{Aaron Moss}
     
    9595\email{pabuhr@uwaterloo.ca}
    9696
    97 \terms{generic, types}
    98 \keywords{generic types, polymorphic functions, Cforall}
     97\terms{generic, tuple, types}
     98\keywords{generic types, tuple types, polymorphic functions, C, Cforall}
    9999
    100100\begin{CCSXML}
     
    132132\section{Introduction \& Background}
    133133
    134 \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.
     134\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}:
     135\begin{enumerate}
     136\item The behaviour of standard C code must remain the same when translated by a \CFA{} compiler as when translated by a C compiler.
     137\item Standard C code must be as fast and as small when translated by a \CFA{} compiler as when translated by a C compiler.
     138\item \CFA{} code must be at least as portable as standard C code.
     139\item Extensions introduced by \CFA{} must be translated in the most efficient way possible.
     140\end{enumerate}
     141The 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.
     142
     143\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.
    135144
    136145\subsection{Polymorphic Functions}
     146\label{sec:poly-fns}
    137147
    138148\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):
     
    191201}
    192202\end{lstlisting}
     203This 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.
    193204
    194205@otype@ is essentially syntactic sugar for the following trait:
     
    198209        void ?{}(T*);  // default constructor
    199210        void ?{}(T*, T);  // copy constructor
    200         T ?=?(T*, T);  // assignment operator
     211        void ?=?(T*, T);  // assignment operator
    201212        void ^?{}(T*);  // destructor
    202213};
     214\end{lstlisting}
     215Given 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):
     216\begin{lstlisting}
     217void abs( size_t _sizeof_M, size_t _alignof_M,
     218                void (*_ctor_M)(void*), void (*_copy_M)(void*, void*),
     219                void (*_assign_M)(void*, void*), void (*_dtor_M)(void*),
     220                bool (*_lt_M)(void*, void*), void (*_neg_M)(void*, void*),
     221        void (*_ctor_M_zero)(void*, int),
     222                void* m, void* _rtn ) {  // polymorphic parameter and return passed as void*
     223        // M zero = { 0 };
     224        void* zero = alloca(_sizeof_M);  // stack allocate 0 temporary
     225        _ctor_M_zero(zero, 0);  // initialize using zero_t constructor
     226        // return m < zero ? -m : m;
     227        void *_tmp = alloca(_sizeof_M)
     228        _copy_M( _rtn,  // copy-initialize return value
     229                _lt_M( m, zero ) ?  // check condition
     230                 (_neg_M(m, _tmp), _tmp) :  // negate m
     231                 m);
     232        _dtor_M(_tmp); _dtor_M(zero);  // destroy temporaries
     233}
    203234\end{lstlisting}
    204235
     
    282313\end{lstlisting}
    283314
    284 \TODO{} Maybe move this after the rest of the discussion.
    285 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:
     315Though \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.
     316
     317\TODO{} Discuss caller-provided versus callee-provided offset arrays, layout functions.
     318
     319Whether 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.
     320
     321The 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:
    286322\begin{lstlisting}
    287323forall(dtype T)
     
    311347scalar(metres) marathon = half_marathon + half_marathon;
    312348scalar(litres) two_pools = swimming_pool + swimming_pool;
    313 marathon + swimming_pool; // ERRORv -- caught by compiler
     349marathon + swimming_pool; // ERROR -- caught by compiler
    314350\end{lstlisting}
    315351@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.
     
    323359\section{Related Work}
    324360
    325 \TODO{} Talk about \CC{}, Cyclone, \etc{}
    326 
    327 \section{Conclusion}
    328 
    329 \TODO{}
     361\TODO{} Talk about \CC{}, Cyclone, maybe D, Rust, \etc{}
     362
     363A 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.
     364
     365\section{Conclusion \& Future Work}
     366
     367\TODO{} Among future work, talk about ideas for selectively template-expanding code (on decls for specific types, or on calls for accessible decls).
    330368
    331369\bibliographystyle{ACM-Reference-Format}
Note: See TracChangeset for help on using the changeset viewer.