- Timestamp:
- Apr 2, 2017, 2:54:55 PM (8 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:
- ea73caf
- Parents:
- 0788c03d (diff), ee89ad43 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - Location:
- doc
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/bibliography/cfa.bib
r0788c03d r53f9448 2719 2719 implementations are the same. 2720 2720 } 2721 } 2722 2723 @online{GCCExtensions, 2724 contributer = {a3moss@uwaterloo.ca}, 2725 key = {{GNU}}, 2726 title = {Extensions to the {C} Language Family}, 2727 year = 2014, 2728 url = {https://gcc.gnu.org/onlinedocs/gcc-4.7.2/gcc/C-Extensions.html}, 2729 urldate = {2017-04-02} 2721 2730 } 2722 2731 -
doc/generic_types/generic_types.tex
r0788c03d r53f9448 117 117 118 118 \begin{abstract} 119 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 installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. 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 that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. Prior projects have attempted similar goals ~\cite{C++,Grossman06} but failed to honour C programming-style, e.g., adding object-oriented,functional programming with garbage collection is a non-starter for many C developers. Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and engineers. This paper describes only two \CFA extensions, generic and tuple types, and how they are implemented in accordance with these principles.119 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 installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more. 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 that provides modern safety and productivity features while still ensuring strong backwards compatibility with C and its programmers. Prior projects have attempted similar goals but failed to honour C programming-style; for instance, adding object-oriented or functional programming with garbage collection is a non-starter for many C developers. Specifically, \CFA is designed to have an orthogonal feature-set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code-bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and engineers. This paper describes only two \CFA extensions, generic and tuple types, and how they are implemented in accordance with these principles. 120 120 \end{abstract} 121 121 … … 133 133 \item Extensions introduced by \CFA must be translated in the most efficient way possible. 134 134 \end{enumerate} 135 The purpose of these goals is to ensure that existing C code-bases can be converted to \CFA incrementally and with minimal effort, and that programmers who know C can productively generate \CFA code without training beyond the features they wish to employ. In its current implementation, \CFA is compiled by translating it to the GCC-dialect of C , allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3).136 137 \CFA has been previously extended with polymorphic functions and name overloading (including operator overloading) ~\citep{Bilson03}, and deterministically-executed constructors and destructors~\citep{Schluntz17}. This paper describes how generic and tuple types are designed and implemented in \CFA in accordance with both the backward compatibility goals and existing features described above.135 The purpose of these goals is to ensure that existing C code-bases can be converted to \CFA incrementally and with minimal effort, and that programmers who know C can productively generate \CFA code without training beyond the features they wish to employ. In its current implementation, \CFA is compiled by translating it to the GCC-dialect of C~\citep{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3). 136 137 \CFA has been previously extended with polymorphic functions and name overloading (including operator overloading) by \citet{Bilson03}, and deterministically-executed constructors and destructors by \citet{Schluntz17}. This paper describes how generic and tuple types are designed and implemented in \CFA in accordance with both the backward compatibility goals and existing features described above. 138 138 139 139 … … 141 141 \label{sec:poly-fns} 142 142 143 \CFA's polymorphism was originally formalized by ~\citet{Ditchfield92}, and first implemented by~\citet{Bilson03}. The signature feature of \CFA is parametric-polymorphic functions; such functions are written using a @forall@ clause (which gives the language its name):143 \CFA's polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}. The signature feature of \CFA is parametric-polymorphic functions; such functions are written using a @forall@ clause (which gives the language its name): 144 144 \begin{lstlisting} 145 145 `forall( otype T )` T identity( T val ) { return val; } … … 156 156 int val = twice( twice( 3.7 ) ); 157 157 \end{lstlisting} 158 which works for any type @T@ with an addition operator defined. The translator accomplishes this polymorphism by creating a wrapper function for calling @+@ with @T@ bound to @double@, then providing this function to the first call of @twice@. It then has the option of using the same @twice@ again and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type in its type analysis. The first approach has a late conversion from integer to floating-point on the final assignment, while the second has an eager conversion to integer. \CFA minimize the number of conversions and their potential to lose information, so it selects the first approach.158 which works for any type @T@ with an addition operator defined. The translator accomplishes this polymorphism by creating a wrapper function for calling @+@ with @T@ bound to @double@, then providing this function to the first call of @twice@. It then has the option of using the same @twice@ again and converting the result to @int@ on assignment, or creating another @twice@ with type parameter @T@ bound to @int@ because \CFA uses the return type in its type analysis. The first approach has a late conversion from integer to floating-point on the final assignment, while the second has an eager conversion to integer. \CFA minimizes the number of conversions and their potential to lose information, so it selects the first approach. 159 159 160 160 Monomorphic specializations of polymorphic functions can satisfy polymorphic type-assertions. … … 175 175 \end{lstlisting} 176 176 @qsort@ and @bsearch@ can only be called with arguments for which there exists a function named @<@ taking two arguments of the same type and returning an @int@ value. 177 Here, the buil d-in monomorphic specialization of @<@ for type @double@ is passed as an additional implicit parameter to the calls of @qsort@ and @bsearch@.177 Here, the built-in monomorphic specialization of @<@ for type @double@ is passed as an additional implicit parameter to the calls of @qsort@ and @bsearch@. 178 178 179 179 Crucial to the design of a new programming language are the libraries to access thousands of external features. … … 207 207 \CC's type-system cannot disambiguate between the two versions of @bsearch@ because it does not use the return type in overload resolution, nor can \CC separately compile a templated @bsearch@. 208 208 209 Call-site inferencing and nested functions provide a localized form of inher tance. For example, @qsort@ only sorts in asending order using @<@. However, it is trivial to locally change this behaviour:209 Call-site inferencing and nested functions provide a localized form of inheritance. For example, @qsort@ only sorts in ascending order using @<@. However, it is trivial to locally change this behaviour: 210 210 \begin{lstlisting} 211 211 { … … 251 251 % \end{lstlisting} 252 252 \begin{lstlisting} 253 trait sum able( otype T ) {254 const T 0; $\C{// variable zero}$253 trait summable( otype T ) { 254 void ?{}(T*, zero_t); $\C{// constructor from 0 literal}$ 255 255 T ?+?( T, T ); $\C{// assortment of additions}$ 256 256 T ?+=?( T *, T ); … … 258 258 T ?++( T * ); 259 259 }; 260 forall( otype T | sum able( T ) )260 forall( otype T | summable( T ) ) 261 261 T sum( T a[$\,$], size_t dimension ) { 262 T total = 0; $\C{// instantiate T, select0}$262 T total = { 0 }; $\C{// instantiate T from 0}$ 263 263 for ( unsigned int i = 0; i < dimension; i += 1 ) 264 264 total += a[i]; $\C{// select appropriate +}$ … … 278 278 }; 279 279 \end{lstlisting} 280 Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @sum@ function produces generated code something like the following (simplified for clarity and brevity) :280 Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @sum@ function produces generated code something like the following (simplified for clarity and brevity) \TODO{} fix example, maybe elide, it's likely too long with the more complicated function: 281 281 \begin{lstlisting} 282 282 void abs( size_t _sizeof_M, size_t _alignof_M, … … 670 670 If assertion arguments must match exactly, then the call to @g@ cannot be resolved, since the expected type of @f@ is flat, while the only @f@ in scope requires a tuple type. Since tuples are fluid, this requirement reduces the usability of tuples in polymorphic code. To ease this pain point, function parameter and return lists are flattened for the purposes of type unification, which allows the previous example to pass expression resolution. 671 671 672 This relaxation is made possible by extending the existing thunk generation scheme, as described by ~\citet{Bilson03}. Now, whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function:672 This relaxation is made possible by extending the existing thunk generation scheme, as described by \citet{Bilson03}. Now, whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function: 673 673 \begin{lstlisting} 674 674 int _thunk(int _p0, double _p1, double _p2) {
Note: See TracChangeset
for help on using the changeset viewer.