Changeset 1ca52db for doc

Timestamp:

Mar 23, 2017, 5:20:29 PM (8 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, 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:

• 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 (added)

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,_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 +57 @@
 \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 +95 @@
 \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 +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. 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 +201 @@
 }
 \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 +209 @@
         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 +313 @@
 \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 +347 @@
 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 +359 @@
 \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}