Changes in / [c0e7723:67e8e192]


Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/generic_types/generic_types.tex

    rc0e7723 r67e8e192  
    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.
     
    960961hence runtime checks are necessary to safely down-cast objects.
    961962The most notable difference among the implementations is in optimizations: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while the C and \CCV lack generic-type capability {\color{red}(AWKWARD) to store generic objects via pointers to separately-allocated objects}.
     963% The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV lack such a capability and instead must store generic objects via pointers to separately-allocated objects.
    962964For the print benchmark, idiomatic printing is used: the C and \CFA variants used @cstdio.h@, while the \CC and \CCV variants used @iostream@.
    963965Preliminary tests show the difference has little runtime effect.
     
    10711073D 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.
    10721074Rust also possesses much more powerful abstraction capabilities for writing generic code than Go.
    1073 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.
    1074 \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.
    10751077
    10761078
Note: See TracChangeset for help on using the changeset viewer.