Changeset b23d969
- Timestamp:
- Apr 15, 2017, 2:31:54 PM (7 years ago)
- 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
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/generic_types/generic_types.tex
rf891424 rb23d969 174 174 \end{center} 175 175 \lstMakeShortInline@% 176 Love it or hate it, C is extremely popular, highly used, and one of the few system 's languages.176 Love it or hate it, C is extremely popular, highly used, and one of the few systems languages. 177 177 In many cases, \CC is often used solely as a better C. 178 178 Nonetheless, C, first standardized over thirty years ago, lacks many features that make programming in more modern languages safer and more productive. … … 185 185 (4) Extensions introduced by \CFA must be translated in the most efficient way possible. 186 186 These 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. 188 188 189 189 \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). … … 209 209 If this extra information is not needed, \eg for a pointer, the type parameter can be declared as a \emph{data type} (or @dtype@). 210 210 211 In \CFA, the polymorphism runtime-cost is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experimentsshow this overhead is similar to \CC virtual-function calls.211 In \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. 212 212 An 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. 213 213 214 Since bare polymorphic-types provide only a narrowset 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.214 Since 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. 215 215 For example, the function @twice@ can be defined using the \CFA syntax for operator overloading: 216 216 \begin{lstlisting} … … 367 367 368 368 One 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 createdata structures in C.369 Broadly speaking, there are three approaches to implement abstract data structures in C. 370 370 One approach is to write bespoke data structures for each context in which they are needed. 371 371 While 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 commoncode for common functionality.372 A 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. 373 373 However, 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. 374 374 A 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. 375 375 Furthermore, writing and using preprocessor macros can be unnatural and inflexible. 376 376 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. 378 378 \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.379 However, for known concrete parameters, the generic type definition can be inlined, like \CC templates. 380 380 381 381 A 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: … … 397 397 398 398 \CFA classifies generic types as either \emph{concrete} or \emph{dynamic}. 399 Concrete have a fixed memory layout regardless of type parameters, while dynamicvary in memory layout depending on their type parameters.399 Concrete types have a fixed memory layout regardless of type parameters, while dynamic types vary in memory layout depending on their type parameters. 400 400 A type may have polymorphic parameters but still be concrete, called \emph{dtype-static}. 401 401 Polymorphic 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. … … 435 435 Though \CFA implements concrete generic-types efficiently, it also has a fully general system for dynamic generic types. 436 436 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. 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.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. 439 439 Access 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. 440 440 … … 946 946 947 947 \section{Evaluation} 948 \label{sec:eval} 948 949 949 950 Though \CFA provides significant added functionality over C, these added features have a low runtime penalty. … … 1072 1073 D 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. 1073 1074 Rust 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.1075 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. 1076 \CFA, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source. 1076 1077 1077 1078
Note: See TracChangeset
for help on using the changeset viewer.