Changeset c1fb1f2


Ignore:
Timestamp:
Mar 28, 2017, 4:51:47 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:
3ed64ff
Parents:
41cd57c0
Message:

Update abstract and related work

Location:
doc/generic_types
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.bib

    r41cd57c0 rc1fb1f2  
    3434}
    3535
     36@techreport{C++Concepts,
     37    type = {International Standard},
     38    keywords    = {ISO/IEC TS 19217:2015},
     39    contributer = {a3moss@uwaterloo.ca},
     40    key         = {{ISO/IEC} {TS} 19217},
     41    title       = {Information technology -- Programming languages -- {C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Extensions for concepts},
     42    institution = {International Standard Organization},
     43    address     = {http://www.iso.org},
     44    year        = 2015
     45}
     46
    3647@phdthesis{Ditchfield92,
    3748    keywords    = {C, parametric polymorphism, overloading},
     
    4354    address     = {Waterloo, Ontario, Canada, N2L 3G1},
    4455    note        = {\href{http://plg.uwaterloo.ca/theses/DitchfieldThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-DitchfieldThesis.pdf}}
     56}
     57
     58@article{Gro06,
     59 author = {Grossman, Dan},
     60 title = {Quantified Types in an Imperative Language},
     61 journal = {ACM Trans. Program. Lang. Syst.},
     62 issue_date = {May 2006},
     63 volume = {28},
     64 number = {3},
     65 month = may,
     66 year = {2006},
     67 issn = {0164-0925},
     68 pages = {429--475},
     69 numpages = {47},
     70 url = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/1133651.1133653},
     71 doi = {10.1145/1133651.1133653},
     72 acmid = {1133653},
     73 publisher = {ACM},
     74 address = {New York, NY, USA},
    4575}
    4676
  • doc/generic_types/generic_types.tex

    r41cd57c0 rc1fb1f2  
    1010\newcommand{\CCfourteen}{\rm C\kern-.1em\hbox{+\kern-.25em+}14} % C++14 symbolic name
    1111\newcommand{\CCseventeen}{\rm C\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name
     12\newcommand{\CCtwenty}{\rm C\kern-.1em\hbox{+\kern-.25em+}20} % C++20 symbolic name
    1213
    1314\newcommand{\TODO}{\textbf{TODO}}
     
    123124
    124125\begin{abstract}
    125 \TODO{} Write abstract.
     126The 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.
    126127\end{abstract}
    127128
     
    299300\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.
    300301
     302\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:
     303\begin{lstlisting}
     304forall(otype Key | { bool ?==?(Key, Key); bool ?<? (Key, Key); })
     305struct sorted_set;
     306\end{lstlisting}
     307
    301308\subsection{Concrete Generic Types}
    302309
     
    353360
    354361\subsection{Applications}
     362\label{sec:generic-apps}
    355363
    356364The 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:
     
    696704The @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.
    697705
    698 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.
     706In 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)@.
    699707
    700708\TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).
     
    791799\section{Related Work}
    792800
    793 \TODO{} Talk about \CC{}, Cyclone, maybe D, Rust, \etc{}
    794 
    795 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.
     801\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.
     802
     803Cyclone 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.
     804
     805Go 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.
    796806
    797807\section{Conclusion \& Future Work}
Note: See TracChangeset for help on using the changeset viewer.