Changes in / [fe1b6a4:578b637]

Location:

doc

Files:

• generic_types/.gitignore (modified) (1 diff)
• generic_types/generic_types.bib (modified) (1 diff)
• generic_types/generic_types.tex (modified) (9 diffs)
• rob_thesis/.gitignore (deleted)

doc/generic_types/.gitignore

@@ -13 +13 @@
 *.ps
 *.toc
-*.lof
-*.lot
 *.synctex.gz

doc/generic_types/generic_types.bib

@@ -20 +20 @@
     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]]}
-}

doc/generic_types/generic_types.tex

@@ -20 +20 @@
         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,sized,_Static_assert,
+                fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,_Static_assert,
                 _Thread_local,throw,throwResume,trait,try,typeof,__typeof,__typeof__,zero_t},
 }%
@@ -57 +57 @@
 \acmJournal{PACMPL}
 
-\title{Generic and Tuple Types with Efficient Dynamic Layout in \CFA{}}
+\title{Generic Types with Efficient Dynamic Layout in \CFA{}}
 
 \author{Aaron Moss}
@@ -95 +95 @@
 \email{pabuhr@uwaterloo.ca}
 
-\terms{generic, tuple, types}
-\keywords{generic types, tuple types, polymorphic functions, C, Cforall}
+\terms{generic, types}
+\keywords{generic types, polymorphic functions, Cforall}
 
 \begin{CCSXML}
@@ -132 +132 @@
 \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. 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.
+\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.
 
 \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): 
@@ -201 +191 @@
 }
 \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:
@@ -209 +198 @@
         void ?{}(T*);  // default constructor
         void ?{}(T*, T);  // copy constructor
-        void ?=?(T*, T);  // assignment operator
+        T ?=?(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}
 
@@ -313 +282 @@
 \end{lstlisting}
 
-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:
+\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:
 \begin{lstlisting}
 forall(dtype T)
@@ -347 +311 @@
 scalar(metres) marathon = half_marathon + half_marathon;
 scalar(litres) two_pools = swimming_pool + swimming_pool;
-marathon + swimming_pool; // ERROR -- caught by compiler
+marathon + swimming_pool; // ERRORv -- 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.
@@ -359 +323 @@
 \section{Related Work}
 
-\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).
+\TODO{} Talk about \CC{}, Cyclone, \etc{}
+
+\section{Conclusion}
+
+\TODO{}
 
 \bibliographystyle{ACM-Reference-Format}