Changeset c1fb1f2f for doc/generic_types

Timestamp:

Mar 28, 2017, 4:51:47 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:

3ed64ff

Parents:

41cd57c0

Message:

Update abstract and related work

Location:

doc/generic_types

Files:

• generic_types.bib (modified) (2 diffs)
• generic_types.tex (modified) (6 diffs)

doc/generic_types/generic_types.bib

@@ -34 +34 @@
 }
 
+@techreport{C++Concepts,
+    type = {International Standard},
+    keywords    = {ISO/IEC TS 19217:2015},
+    contributer = {a3moss@uwaterloo.ca},
+    key         = {{ISO/IEC} {TS} 19217},
+    title       = {Information technology -- Programming languages -- {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Extensions for concepts},
+    institution = {International Standard Organization},
+    address     = {http://www.iso.org},
+    year        = 2015
+}
+
 @phdthesis{Ditchfield92,
     keywords    = {C, parametric polymorphism, overloading},
@@ -43 +54 @@
     address     = {Waterloo, Ontario, Canada, N2L 3G1},
     note        = {\href{http://plg.uwaterloo.ca/theses/DitchfieldThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-DitchfieldThesis.pdf}}
+}
+
+@article{Gro06,
+ author = {Grossman, Dan},
+ title = {Quantified Types in an Imperative Language},
+ journal = {ACM Trans. Program. Lang. Syst.},
+ issue_date = {May 2006},
+ volume = {28},
+ number = {3},
+ month = may,
+ year = {2006},
+ issn = {0164-0925},
+ pages = {429--475},
+ numpages = {47},
+ url = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/1133651.1133653},
+ doi = {10.1145/1133651.1133653},
+ acmid = {1133653},
+ publisher = {ACM},
+ address = {New York, NY, USA},
 }
 

doc/generic_types/generic_types.tex

@@ -10 +10 @@
 \newcommand{\CCfourteen}{\rm C\kern-.1em\hbox{+\kern-.25em+}14} % C++14 symbolic name
 \newcommand{\CCseventeen}{\rm C\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name
+\newcommand{\CCtwenty}{\rm C\kern-.1em\hbox{+\kern-.25em+}20} % C++20 symbolic name
 
 \newcommand{\TODO}{\textbf{TODO}}
@@ -123 +124 @@
 
 \begin{abstract}
-\TODO{} Write abstract.
+The C programming language is a foundational technology for modern computing, with millions of lines of code implementing everything from commercial operating systems to hobby projects. This installed base of code and the programmers who produced it represent a massive software engineering investment spanning decades. Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. The goal of the \CFA{} project is to create an extension of C which provides modern safety and productivity features while still providing strong backwards compatibility with C. Particularly, \CFA{} is designed to have an orthogonal feature set based closely on the C programming paradigm, so that \CFA{} features can be added incrementally to existing C codebases, and C programmers can learn \CFA{} extensions on an as-needed basis, preserving investment in existing engineers and code. This paper describes how generic and tuple types are implemented in \CFA{} in accordance with these principles.
 \end{abstract}
 
@@ -299 +300 @@
 \CFA{} classifies generic types as either \emph{concrete} or \emph{dynamic}. Dynamic generic types vary in their in-memory layout depending on their type parameters, while concrete generic types have a fixed memory layout regardless of type parameters. A type may have polymorphic parameters but still be concrete; \CFA{} refers to such types as \emph{dtype-static}. Polymorphic pointers are an example of dtype-static types -- @forall(dtype T) T*@ is a polymorphic type, but for any @T@ chosen, @T*@ will have exactly the same in-memory representation as a @void*@, and can therefore be represented by a @void*@ in code generation.
 
+\CFA{} generic types may also specify constraints on their argument type that will be checked by the compiler. For example, consider the following declaration of a sorted set type, which will ensure that the set key supports comparison and tests for equality:
+\begin{lstlisting}
+forall(otype Key | { bool ?==?(Key, Key); bool ?<? (Key, Key); })
+struct sorted_set;
+\end{lstlisting}
+
 \subsection{Concrete Generic Types}
 
@@ -353 +360 @@
 
 \subsection{Applications}
+\label{sec:generic-apps}
 
 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:
@@ -696 +704 @@
 The @new@ function provides the combination of type-safe @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically allocated objects. This provides the type-safety of @new@ in \CC{}, without the need to specify the allocated type, thanks to return-type inference.
 
-In the call to @new@, @Pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. To satisfy the assertion, a constructor with an interface compatible with @void ?{}(Pair(int, char) *, int, char)@ must exist in the current scope, which (1) may be specialized to match.
+In the call to @new@, @Pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. The constructor (1) may be specialized to  satisfy the assertion for a constructor with an interface compatible with @void ?{}(Pair(int, char) *, int, char)@.
 
 \TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).
@@ -791 +799 @@
 \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.
+\CC{} is the existing language it is most natural to compare \CFA{} to, as they are both more modern extensions to C with backwards source compatibility. The most fundamental difference in approach between \CC{} and \CFA{} is their approach to this C compatibility. \CC{} does provide fairly strong source backwards compatibility with C, but is a dramatically more complex language than C, and imposes a steep learning curve to use many of its extension features. For instance, in a break from general C practice, template code is typically written in header files, with a variety of subtle restrictions implied on its use by this choice, while the other polymorphism mechanism made available by \CC{}, class inheritance, requires programmers to learn an entirely new object-oriented programming paradigm; the interaction between templates and inheritance is also quite complex. \CFA{}, by contrast, has a single facility for polymorphic code, one which supports separate compilation and the existing procedural paradigm of C code. 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, and, until concepts \citep{C++Concepts} are standardized (currently anticipated for \CCtwenty{}), \CC{} provides no way to specify the requirements of a generic function in code beyond compilation errors for template expansion failures. By contrast, the explicit nature of assertions in \CFA{} allows polymorphic functions to be separately compiled, and for their requirements to be checked by the compiler; similarly, \CFA{} generic types may be opaque, unlike \CC{} template classes.
+
+Cyclone also provides capabilities for polymorphic functions and existential types \citep{Gro06}, similar in concept to \CFA{}'s @forall@ functions and generic types. Cyclone existential types can include function pointers in a construct similar to a virtual function table, but these pointers must be explicitly initialized at some point in the code, a tedious and potentially error-prone process. Furthermore, Cyclone's polymorphic functions and types are restricted in that they may only abstract over types with the same layout and calling convention as @void*@, in practice only pointer types and @int@ - in \CFA{} terms, all Cyclone polymorphism must be dtype-static. This provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, but is more restrictive than \CFA{}'s more general model.
+
+Go and Rust are both modern, compiled languages with abstraction features similar to \CFA{} traits, \emph{interfaces} in Go and \emph{traits} in Rust. However, both languages represent dramatic departures from C in terms of language model, and neither has the same level of compatibility with C as \CFA{}. Go is a garbage-collected language, imposing the associated runtime overhead, and complicating foreign-function calls with the neccessity of accounting for data transfer between the managed Go runtime and the unmanaged C runtime. Furthermore, while generic types and functions are available in Go, they are limited to a small fixed set provided by the compiler, with no language facility to define more. Rust is not garbage-collected, and thus has a lighter-weight runtime that is more easily interoperable with C. It also possesses much more powerful abstraction capabilities for writing generic code than Go. On the other hand, Rust's borrow-checker, while it does provide strong safety guarantees, is complex and difficult to learn, and imposes a distinctly idiomatic programming style on Rust. \CFA{}, with its more modest safety features, is significantly easier to port C code to, while maintaining the idiomatic style of the original source.
 
 \section{Conclusion \& Future Work}