Changeset b23d969


Ignore:
Timestamp:
Apr 15, 2017, 2:31:54 PM (7 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:
67e8e192
Parents:
f891424
Message:

edits up to end of tuples section

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    rf891424 rb23d969  
    174174\end{center}
    175175\lstMakeShortInline@%
    176 Love it or hate it, C is extremely popular, highly used, and one of the few system's languages.
     176Love it or hate it, C is extremely popular, highly used, and one of the few systems languages.
    177177In many cases, \CC is often used solely as a better C.
    178178Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive.
     
    185185(4) Extensions introduced by \CFA must be translated in the most efficient way possible.
    186186These goals ensure existing C code-bases can be converted to \CFA incrementally with minimal effort, and C programmers can productively generate \CFA code without training beyond the features being used.
    187 Unfortunately, \CC is actively diverging from C, so incremental additions require significant effort and training, coupled with multiple legacy design-choices that cannot be updated.
     187\CC is often used similarly, but has the paired disadvantages of multiple legacy design-choices that cannot be updated and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project.
    188188
    189189\CFA is currently implemented as a source-to-source translator from \CFA to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3).
     
    209209If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@).
    210210
    211 In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments show this overhead is similar to \CC virtual-function calls.
     211In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual-function calls.
    212212An advantage of this design is that, unlike \CC template-functions, \CFA polymorphic-functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.
    213213
    214 Since bare polymorphic-types provide only a narrow set of available operations, \CFA provides a \emph{type assertion}~\cite{alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.
     214Since bare polymorphic-types provide a restricted set of available operations, \CFA provides a \emph{type assertion}~\cite{alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type-variable.
    215215For example, the function @twice@ can be defined using the \CFA syntax for operator overloading:
    216216\begin{lstlisting}
     
    367367
    368368One of the known shortcomings of standard C is that it does not provide reusable type-safe abstractions for generic data structures and algorithms.
    369 Broadly speaking, there are three approaches to create data structures in C.
     369Broadly speaking, there are three approaches to implement abstract data structures in C.
    370370One approach is to write bespoke data structures for each context in which they are needed.
    371371While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures.
    372 A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, and does allow the use of common code for common functionality.
     372A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@; an approach which does allow reuse of code for common functionality.
    373373However, basing all polymorphism on @void *@ eliminates the type-checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that would not otherwise be needed.
    374374A third approach to generic code is to use preprocessor macros, which does allow the generated code to be both generic and type-checked, but errors may be difficult to interpret.
    375375Furthermore, writing and using preprocessor macros can be unnatural and inflexible.
    376376
    377 Other languages use \emph{generic types}, \eg \CC and Java, to produce type-safe abstract data-types.
     377\CC, Java, and other languages use \emph{generic types} to produce type-safe abstract data-types.
    378378\CFA also implements generic types that integrate efficiently and naturally with the existing polymorphic functions, while retaining backwards compatibility with C and providing separate compilation.
    379 However, for known concrete parameters, the generic type can be inlined, like \CC templates.
     379However, for known concrete parameters, the generic type definition can be inlined, like \CC templates.
    380380
    381381A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration, and instantiated using a parenthesized list of types after the type name:
     
    397397
    398398\CFA classifies generic types as either \emph{concrete} or \emph{dynamic}.
    399 Concrete have a fixed memory layout regardless of type parameters, while dynamic vary in memory layout depending on their type parameters.
     399Concrete types have a fixed memory layout regardless of type parameters, while dynamic types vary in memory layout depending on their type parameters.
    400400A type may have polymorphic parameters but still be concrete, called \emph{dtype-static}.
    401401Polymorphic pointers are an example of dtype-static types, \eg @forall(dtype T) T *@ is a polymorphic type, but for any @T@, @T *@  is a fixed-sized pointer, and therefore, can be represented by a @void *@ in code generation.
     
    435435Though \CFA implements concrete generic-types efficiently, it also has a fully general system for dynamic generic types.
    436436As 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.
    437 Dynamic generic-types also have an \emph{offset array} containing structure member-offsets.
    438 A dynamic generic-union needs no such offset array, as all members are at offset 0 but size and alignment are still necessary.
     437Dynamic generic-types also have an \emph{offset array} containing structure-member offsets.
     438A dynamic generic-union needs no such offset array, as all members are at offset 0, but size and alignment are still necessary.
    439439Access to members of a dynamic structure is provided at runtime via base-displacement addressing with the structure pointer and the member offset (similar to the @offsetof@ macro), moving a compile-time offset calculation to runtime.
    440440
     
    946946
    947947\section{Evaluation}
     948\label{sec:eval}
    948949
    949950Though \CFA provides significant added functionality over C, these added features have a low runtime penalty.
     
    10721073D restricts garbage collection to its own heap by default, while Rust is not garbage-collected, and thus has a lighter-weight runtime more interoperable with C.
    10731074Rust also possesses much more powerful abstraction capabilities for writing generic code than Go.
    1074 On the other hand, Rust's borrow-checker, provides strong safety guarantees but is complex and difficult to learn, and imposes a distinctly idiomatic programming style.
    1075 \CFA, with its more modest safety features, ports directly to C code, while maintaining the idiomatic style of the original source.
     1075On the other hand, Rust's borrow-checker provides strong safety guarantees but is complex and difficult to learn and imposes a distinctly idiomatic programming style.
     1076\CFA, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source.
    10761077
    10771078
Note: See TracChangeset for help on using the changeset viewer.