| 1 | \chapter{Background} |
|---|
| 2 | |
|---|
| 3 | This chapter covers background material for C enumerations and \CFA features used in later discussions. |
|---|
| 4 | |
|---|
| 5 | |
|---|
| 6 | \section{C} |
|---|
| 7 | |
|---|
| 8 | As mentioned in \VRef{s:Aliasing}, it is common for C programmers to ``believe'' there are three equivalent forms of named constants. |
|---|
| 9 | \begin{clang} |
|---|
| 10 | #define Mon 0 |
|---|
| 11 | static const int Mon = 0; |
|---|
| 12 | enum { Mon }; |
|---|
| 13 | \end{clang} |
|---|
| 14 | \begin{enumerate}[leftmargin=*] |
|---|
| 15 | \item |
|---|
| 16 | For @#define@, the programmer must explicitly manage the constant name and value. |
|---|
| 17 | Furthermore, these C preprocessor macro names are outside the C type system and can incorrectly change random text in a program. |
|---|
| 18 | \item |
|---|
| 19 | The same explicit management is true for the @const@ declaration, and the @const@ variable cannot appear in constant-expression locations, like @case@ labels, array dimensions,\footnote{ |
|---|
| 20 | C allows variable-length array declarations (VLA), so this case does work. Still, it fails in \CC, which does not support VLAs, unless it is \lstinline{g++}.} immediate oper\-ands of assembler instructions and occupies storage. |
|---|
| 21 | \begin{clang} |
|---|
| 22 | $\$$ nm test.o |
|---|
| 23 | 0000000000000018 r Mon |
|---|
| 24 | \end{clang} |
|---|
| 25 | \item |
|---|
| 26 | Only the @enum@ form is managed by the compiler, is part of the language type-system, works in all C constant-expression locations, and normally does not occupy storage. |
|---|
| 27 | \end{enumerate} |
|---|
| 28 | |
|---|
| 29 | |
|---|
| 30 | \subsection{C \texorpdfstring{\lstinline{const}}{const}} |
|---|
| 31 | \label{s:Cconst} |
|---|
| 32 | |
|---|
| 33 | C can simulate the aliasing @const@ declarations \see{\VRef{s:Aliasing}}, with static and dynamic initialization. |
|---|
| 34 | \begin{cquote} |
|---|
| 35 | \begin{tabular}{@{}ll@{}} |
|---|
| 36 | \multicolumn{1}{@{}c}{\textbf{static initialization}} & \multicolumn{1}{c@{}}{\textbf{dynamic initialization}} \\ |
|---|
| 37 | \begin{clang} |
|---|
| 38 | static const int one = 0 + 1; |
|---|
| 39 | static const void * NIL = NULL; |
|---|
| 40 | static const double PI = 3.14159; |
|---|
| 41 | static const char Plus = '+'; |
|---|
| 42 | static const char * Fred = "Fred"; |
|---|
| 43 | static const int Mon = 0, Tue = Mon + 1, Wed = Tue + 1, |
|---|
| 44 | Thu = Wed + 1, Fri = Thu + 1, Sat = Fri + 1, Sun = Sat + 1; |
|---|
| 45 | \end{clang} |
|---|
| 46 | & |
|---|
| 47 | \begin{clang} |
|---|
| 48 | void foo() { |
|---|
| 49 | // auto scope only |
|---|
| 50 | const int r = random() % 100; |
|---|
| 51 | int va[r]; |
|---|
| 52 | } |
|---|
| 53 | \end{clang} |
|---|
| 54 | \end{tabular} |
|---|
| 55 | \end{cquote} |
|---|
| 56 | However, statically initialized identifiers cannot appear in constant-expression contexts, \eg @case@. |
|---|
| 57 | Dynamically initialized identifiers may appear in initialization and array dimensions in @g++@, which allows variable-sized arrays on the stack. |
|---|
| 58 | Again, this form of aliasing is not an enumeration. |
|---|
| 59 | |
|---|
| 60 | |
|---|
| 61 | \subsection{C Enumeration} |
|---|
| 62 | \label{s:CEnumeration} |
|---|
| 63 | |
|---|
| 64 | The C enumeration has the following syntax~\cite[\S~6.7.2.2]{C11}. |
|---|
| 65 | \begin{clang}[identifierstyle=\linespread{0.9}\it] |
|---|
| 66 | $\it enum$-specifier: |
|---|
| 67 | enum identifier$\(_{opt}\)$ { enumerator-list } |
|---|
| 68 | enum identifier$\(_{opt}\)$ { enumerator-list , } |
|---|
| 69 | enum identifier |
|---|
| 70 | enumerator-list: |
|---|
| 71 | enumerator |
|---|
| 72 | enumerator-list , enumerator |
|---|
| 73 | enumerator: |
|---|
| 74 | enumeration-constant |
|---|
| 75 | enumeration-constant = constant-expression |
|---|
| 76 | \end{clang} |
|---|
| 77 | The terms \emph{enumeration} and \emph{enumerator} used in this work \see{\VRef{s:Terminology}} come from the grammar. |
|---|
| 78 | The C enumeration semantics are discussed using examples. |
|---|
| 79 | |
|---|
| 80 | |
|---|
| 81 | \subsubsection{Type Name} |
|---|
| 82 | \label{s:TypeName} |
|---|
| 83 | |
|---|
| 84 | An \emph{unnamed} enumeration is used to provide aliasing \see{\VRef{s:Aliasing}} exactly like a @const@ declaration in other languages. |
|---|
| 85 | However, it is restricted to integral values. |
|---|
| 86 | \begin{clang} |
|---|
| 87 | enum { Size = 20, Max = 10, MaxPlus10 = Max + 10, @Max10Plus1@, Fred = -7 }; |
|---|
| 88 | \end{clang} |
|---|
| 89 | Here, the aliased constants are 20, 10, 20, 21, and -7. |
|---|
| 90 | Direct initialization is achieved by a compile-time expression that generates a constant value. |
|---|
| 91 | Indirect initialization (without an initializer, @Max10Plus1@) is called \newterm{auto-initialization}, where enumerators are assigned values from left to right, starting at zero or the next explicitly initialized constant, incrementing by @1@. |
|---|
| 92 | Because multiple independent enumerators can be combined, enumerators with the same values can occur. |
|---|
| 93 | The enumerators are @rvalues@, so the assignment is disallowed. |
|---|
| 94 | Finally, enumerators are \newterm{unscoped}, \ie enumerators declared inside of an @enum@ are visible (projected) outside into the enclosing scope of the @enum@ type. |
|---|
| 95 | This semantic is required for unnamed enumerations because there is no type name for scoped qualification. |
|---|
| 96 | |
|---|
| 97 | As noted, this aliasing declaration is not an enumeration, even though it is declared using an @enum@ in C. |
|---|
| 98 | While the semantics is misleading, this enumeration form matches with aggregate types: |
|---|
| 99 | \begin{cfa} |
|---|
| 100 | typedef struct @/* unnamed */@ { ... } S; |
|---|
| 101 | struct @/* unnamed */@ { ... } x, y, z; $\C{// questionable}$ |
|---|
| 102 | struct S { |
|---|
| 103 | union @/* unnamed */@ { $\C{// unscoped fields}$ |
|---|
| 104 | int i; double d ; char ch; |
|---|
| 105 | }; |
|---|
| 106 | }; |
|---|
| 107 | \end{cfa} |
|---|
| 108 | Hence, C programmers would expect this enumeration form to exist in harmony with the aggregate form. |
|---|
| 109 | |
|---|
| 110 | A \emph{named} enumeration is an enumeration: |
|---|
| 111 | \begin{clang} |
|---|
| 112 | enum @Week@ { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun }; |
|---|
| 113 | \end{clang} |
|---|
| 114 | and adopts the same semantics as direct and auto initialization. |
|---|
| 115 | For example, @Mon@ to @Wed@ are implicitly assigned with constants @0@--@2@, @Thu@ is explicitly set to constant @10@, and @Fri@ to @Sun@ are implicitly assigned with constants @11@--@13@. |
|---|
| 116 | As well, initialization may occur in any order. |
|---|
| 117 | \begin{clang} |
|---|
| 118 | enum Week { |
|---|
| 119 | Thu@ = 10@, Fri, Sat, Sun, |
|---|
| 120 | Mon@ = 0@, Tue, Wed@,@ $\C{// terminating comma}$ |
|---|
| 121 | }; |
|---|
| 122 | \end{clang} |
|---|
| 123 | Note the comma in the enumerator list can be a terminator or a separator, allowing the list to end with a dangling comma.\footnote{ |
|---|
| 124 | A terminating comma appears in other C syntax, \eg the initializer list.} |
|---|
| 125 | This feature allows enumerator lines to be interchanged without moving a comma. |
|---|
| 126 | Named enumerators are also unscoped. |
|---|
| 127 | |
|---|
| 128 | |
|---|
| 129 | \subsubsection{Implementation} |
|---|
| 130 | \label{s:CenumImplementation} |
|---|
| 131 | |
|---|
| 132 | Theoretically, a C enumeration \emph{variable} is an implementation-defined integral type large enough to hold all enumerator values. |
|---|
| 133 | In practice, C defines @int@~\cite[\S~6.4.4.3]{C11} as the underlying type for enumeration variables, restricting initialization to integral constants, which have type @int@ (unless qualified with a size suffix). |
|---|
| 134 | However, type @int@ is defined as: |
|---|
| 135 | \begin{quote} |
|---|
| 136 | A ``plain'' @int@ object has the natural size suggested by the architecture of the execution environment (large enough to contain any value in the range @INT_MIN@ to @INT_MAX@ as defined in the header @<limits.h>@).~\cite[\S~6.2.5(5)]{C11} |
|---|
| 137 | \end{quote} |
|---|
| 138 | However, @int@ means 4 bytes on both 32/64-bit architectures, which does not seem like the ``natural'' size for a 64-bit architecture. |
|---|
| 139 | Whereas @long int@ means 4 bytes on a 32-bit and 8 bytes on 64-bit architectures, and @long long int@ means 8 bytes on both 32/64-bit architectures, where 64-bit operations are simulated on 32-bit architectures. |
|---|
| 140 | \VRef[Figure]{f:gccEnumerationStorageSize} shows both @gcc@ and @clang@ partially ignore this specification and type the integral size of an enumerator based on its initialization. |
|---|
| 141 | Hence, initialization in the range @INT_MIN@..@INT_MAX@ results in a 4-byte enumerator, and outside this range, the enumerator is 8 bytes. |
|---|
| 142 | Note that @sizeof( typeof( IMin ) ) != sizeof( E )@, making the size of an enumerator different than is containing enumeration type, which seems inconsistent, \eg @sizeof( typeof( 3 ) ) == sizeof( int )@. |
|---|
| 143 | |
|---|
| 144 | \begin{figure} |
|---|
| 145 | \begin{cfa} |
|---|
| 146 | enum E { IMin = INT_MIN, IMax = INT_MAX, |
|---|
| 147 | ILMin = LONG_MIN, ILMax = LONG_MAX, |
|---|
| 148 | ILLMin = LLONG_MIN, ILLMax = LLONG_MAX }; |
|---|
| 149 | int main() { |
|---|
| 150 | printf( "%zd %zd\n%zd %zd\n%zd %d %d\n%zd %ld %ld\n%zd %ld %ld\n", |
|---|
| 151 | sizeof(enum E), sizeof(typeof(IMin)), |
|---|
| 152 | sizeof(int), sizeof(long int), |
|---|
| 153 | sizeof(IMin), IMin, IMax, |
|---|
| 154 | sizeof(ILMin), ILMin, ILMax, |
|---|
| 155 | sizeof(ILLMin), ILLMin, ILLMax ); |
|---|
| 156 | } |
|---|
| 157 | 8 4 |
|---|
| 158 | 4 -2147483648 2147483647 |
|---|
| 159 | 8 -9223372036854775808 9223372036854775807 |
|---|
| 160 | 8 -9223372036854775808 9223372036854775807 |
|---|
| 161 | \end{cfa} |
|---|
| 162 | \caption{\lstinline{gcc}/\lstinline{clang} Enumeration Storage Size} |
|---|
| 163 | \label{f:gccEnumerationStorageSize} |
|---|
| 164 | \end{figure} |
|---|
| 165 | |
|---|
| 166 | |
|---|
| 167 | \subsubsection{Usage} |
|---|
| 168 | \label{s:Usage} |
|---|
| 169 | |
|---|
| 170 | C proves an implicit \emph{bidirectional} conversion between an enumeration and its integral type and between two different enumerations. |
|---|
| 171 | \begin{clang} |
|---|
| 172 | enum Week week = Mon; $\C{// week == 0}$ |
|---|
| 173 | week = Fri; $\C{// week == 11}$ |
|---|
| 174 | int i = Sun; $\C{// implicit conversion to int, i == 13}$ |
|---|
| 175 | @week = 10000;@ $\C{// UNDEFINED! implicit conversion to Week}$ |
|---|
| 176 | |
|---|
| 177 | enum Season { Spring, Summer, Fall, Winter }; |
|---|
| 178 | @week = Winter;@ $\C{// UNDEFINED! implicit conversion to Week}$ |
|---|
| 179 | \end{clang} |
|---|
| 180 | While converting an enumerator to its underlying type is sound, the implicit conversion from the base or another enumeration type to an enumeration is a common source of error. |
|---|
| 181 | |
|---|
| 182 | Enumerators can appear in @switch@ and looping statements. |
|---|
| 183 | \begin{cfa} |
|---|
| 184 | enum Week { Mon, Tue, Wed, Thu, Fri, Sat, Sun }; |
|---|
| 185 | switch ( week ) { |
|---|
| 186 | case Mon ... Fri: $\C{// gcc case range}$ |
|---|
| 187 | printf( "weekday\n" ); |
|---|
| 188 | case Sat: case Sun: |
|---|
| 189 | printf( "weekend\n" ); |
|---|
| 190 | } |
|---|
| 191 | for ( enum Week day = Mon; day <= Sun; day += 1 ) { $\C{// step of 1}$ |
|---|
| 192 | printf( "day %d\n", day ); // 0-6 |
|---|
| 193 | } |
|---|
| 194 | \end{cfa} |
|---|
| 195 | For iterating using arithmetic to make sense, the enumerator values \emph{must} have a consecutive ordering with a fixed step between values. |
|---|
| 196 | For example, a previous gap introduced by @Thu = 10@ results in iterating over the values 0--13, where values 3--9 are not @Week@ values. |
|---|
| 197 | Note that the bidirectional conversion allows incrementing @day@: @day@ is converted to @int@, integer @1@ is added, and the result is converted back to @Week@ for the assignment to @day@. |
|---|
| 198 | For safety, \CC does not support the bidirectional conversion, and hence, an unsafe cast is necessary to increment @day@: @day = (Week)(day + 1)@. |
|---|
| 199 | |
|---|
| 200 | There is a C idiom that computes the number of enumerators in an enumeration automatically. |
|---|
| 201 | \begin{cfa} |
|---|
| 202 | enum E { A, B, C, D, @N@ }; // N == 4 |
|---|
| 203 | for ( enum E e = A; e < @N@; e += 1 ) ... |
|---|
| 204 | \end{cfa} |
|---|
| 205 | Serendipitously, the auto-incrementing counts the number of enumerators and puts the total into the last enumerator @N@. |
|---|
| 206 | This @N@ is often used as the dimension for an array associated with the enumeration. |
|---|
| 207 | \begin{cfa} |
|---|
| 208 | E array[@N@]; |
|---|
| 209 | for ( enum E e = A; e < N; e += 1 ) { |
|---|
| 210 | array[e] = e; |
|---|
| 211 | } |
|---|
| 212 | \end{cfa} |
|---|
| 213 | However, for non-consecutive ordering and non-integral typed enumerations, \see{\VRef{f:EumeratorTyping}}, this idiom fails. |
|---|
| 214 | |
|---|
| 215 | This idiom is often used with another C idiom for matching companion information. |
|---|
| 216 | For example, an enumeration may be linked with a companion array of printable strings. |
|---|
| 217 | \begin{cfa} |
|---|
| 218 | enum Integral_Type { chr, schar, uschar, sshort, ushort, sint, usint, ..., NO_OF_ITYPES }; |
|---|
| 219 | char * Integral_Name[@NO_OF_ITYPES@] = { |
|---|
| 220 | "char", "signed char", "unsigned char", |
|---|
| 221 | "signed short int", "unsigned short int", |
|---|
| 222 | "signed int", "unsigned int", ... |
|---|
| 223 | }; |
|---|
| 224 | enum Integral_Type @integral_type@ = ... |
|---|
| 225 | printf( "%s\n", Integral_Name[@integral_type@] ); // human readable type name |
|---|
| 226 | \end{cfa} |
|---|
| 227 | However, the companion idiom results in the \emph{harmonizing} problem because an update to the enumeration @Integral_Type@ often requires a corresponding update to the companion array \snake{Integral_Name}. |
|---|
| 228 | The requirement to harmonize is, at best, indicated by a comment before the enumeration. |
|---|
| 229 | This issue is exacerbated if enumeration and companion array are in different translation units. |
|---|
| 230 | |
|---|
| 231 | \bigskip |
|---|
| 232 | While C provides a true enumeration, it is restricted, has unsafe semantics, and does not provide helpful/advanced enumeration features in other programming languages. |
|---|
| 233 | |
|---|
| 234 | |
|---|
| 235 | \section{\texorpdfstring{\CFA}{Cforall}} |
|---|
| 236 | |
|---|
| 237 | \CFA in \emph{not} an object-oriented programming language, \ie functions cannot be nested in aggregate types, and hence, there is no \newterm{receiver} notation for calling functions, \eg @obj.method(...)@, where the first argument proceeds the call and becomes an implicit first (\lstinline[language=C++]{this}) parameter. |
|---|
| 238 | The following sections provide short descriptions of \CFA features needed further in the thesis. |
|---|
| 239 | Other \CFA features are presented in situ with short or no explanation because the feature is obvious to C programmers. |
|---|
| 240 | |
|---|
| 241 | |
|---|
| 242 | \subsection{Overloading} |
|---|
| 243 | |
|---|
| 244 | Overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources like included files. |
|---|
| 245 | \begin{quote} |
|---|
| 246 | There are only two hard things in Computer Science: cache invalidation and naming things. --- Phil Karlton |
|---|
| 247 | \end{quote} |
|---|
| 248 | Experience from \CC and \CFA developers is that the type system implicitly and correctly disambiguates the majority of overloaded names, \ie it is rare to get an incorrect selection or ambiguity, even among hundreds of overloaded (variables and) functions. |
|---|
| 249 | In many cases, a programmer has no idea there are name clashes, as they are silently resolved, simplifying the development process. |
|---|
| 250 | Depending on the language, ambiguous cases are resolved using some form of qualification and/or casting. |
|---|
| 251 | |
|---|
| 252 | |
|---|
| 253 | \subsection{Operator Overloading} |
|---|
| 254 | |
|---|
| 255 | Virtually all programming languages overload the arithmetic operators across the basic types using the number and type of parameters and returns. |
|---|
| 256 | Like \CC, \CFA also allows these operators to be overloaded with user-defined types. |
|---|
| 257 | The syntax for operator names uses the @'?'@ character to denote a parameter, \eg prefix and infix increment operators: @?++@, @++?@, and @?+?@. |
|---|
| 258 | \begin{cfa} |
|---|
| 259 | struct S { int i, j }; |
|---|
| 260 | S @?+?@( S op1, S op2 ) { return (S){ op1.i + op2.i, op1.j + op2.j }; } |
|---|
| 261 | S s1, s2; |
|---|
| 262 | s1 = s1 @+@ s2; $\C[1.75in]{// infix call}$ |
|---|
| 263 | s1 = @?+?@( s1, s2 ); $\C{// direct call}\CRT$ |
|---|
| 264 | \end{cfa} |
|---|
| 265 | The type system examines each call size and selects the best matching overloaded function based on the number and types of arguments. |
|---|
| 266 | If there are mixed-mode operands, @2 + 3.5@, the type system, like in C/\CC, attempts (safe) conversions, converting the argument type(s) to the parameter type(s). |
|---|
| 267 | |
|---|
| 268 | |
|---|
| 269 | \subsection{Function Overloading} |
|---|
| 270 | |
|---|
| 271 | Both \CFA and \CC allow function names to be overloaded as long as their prototypes differ in the number and type of parameters and returns. |
|---|
| 272 | \begin{cfa} |
|---|
| 273 | void f( void ); $\C[1.75in]{// (1): no parameter}$ |
|---|
| 274 | void f( char ); $\C{// (2): overloaded on the number and parameter type}$ |
|---|
| 275 | void f( int, int ); $\C{// (3): overloaded on the number and parameter type}$ |
|---|
| 276 | f( 'A' ); $\C{// select (2)}\CRT$ |
|---|
| 277 | \end{cfa} |
|---|
| 278 | In this case, the name @f@ is overloaded depending on the number and parameter types. |
|---|
| 279 | The type system examines each call size and selects the best match based on the number and types of arguments. |
|---|
| 280 | Here, the call @f( 'A' )@ is a perfect match for the number and parameter type of function (2). |
|---|
| 281 | |
|---|
| 282 | Ada, Scala, and \CFA type-systems also use the return type to pinpoint the best-overloaded name in resolving a call. |
|---|
| 283 | \begin{cfa} |
|---|
| 284 | int f( void ); $\C[1.75in]{// (4); overloaded on return type}$ |
|---|
| 285 | double f( void ); $\C{// (5); overloaded on return type}$ |
|---|
| 286 | int i = f(); $\C{// select (4)}$ |
|---|
| 287 | double d = f(); $\C{// select (5)}\CRT$ |
|---|
| 288 | \end{cfa} |
|---|
| 289 | |
|---|
| 290 | |
|---|
| 291 | \subsection{Variable Overloading} |
|---|
| 292 | Unlike almost all programming languages, \CFA has variable overloading within a scope, along with shadow overloading in nested scopes. |
|---|
| 293 | \begin{cfa} |
|---|
| 294 | void foo( double d ); |
|---|
| 295 | int v; $\C[1.75in]{// (1)}$ |
|---|
| 296 | double v; $\C{// (2) variable overloading}$ |
|---|
| 297 | foo( v ); $\C{// select (2)}$ |
|---|
| 298 | { |
|---|
| 299 | int v; $\C{// (3) shadow overloading}$ |
|---|
| 300 | double v; $\C{// (4) and variable overloading}$ |
|---|
| 301 | foo( v ); $\C{// select (4)}\CRT$ |
|---|
| 302 | } |
|---|
| 303 | \end{cfa} |
|---|
| 304 | The \CFA type system treats overloaded variables as an overloaded function returning a value with no parameters. |
|---|
| 305 | Hence, no significant effort is required to support this feature. |
|---|
| 306 | |
|---|
| 307 | |
|---|
| 308 | \subsection{Constructor and Destructor} |
|---|
| 309 | |
|---|
| 310 | While \CFA is not object-oriented, it adopts many language features commonly used in object-oriented languages; |
|---|
| 311 | these features are independent of object-oriented programming. |
|---|
| 312 | |
|---|
| 313 | All objects in \CFA are initialized by @constructors@ \emph{after} allocation and de-initialized \emph{before} deallocation. |
|---|
| 314 | \CC cannot have constructors for basic types because they have no aggregate type \lstinline[language=C++]{struct/class} in which to insert a constructor definition. |
|---|
| 315 | Like \CC, \CFA has multiple auto-generated constructors for every type. |
|---|
| 316 | |
|---|
| 317 | The prototype for the constructor/destructor are @void ?{}( T &, ... )@ and @void ^?{}( T &, ... )@, respectively. |
|---|
| 318 | The first parameter is logically the \lstinline[language=C++]{this} or \lstinline[language=Python]{self} in other object-oriented languages and implicitly passed. |
|---|
| 319 | \VRef[Figure]{f:CFAConstructorDestructor} shows an example of creating and using a constructor and destructor. |
|---|
| 320 | Both constructor and destructor can be explicitly called to reuse a variable. |
|---|
| 321 | |
|---|
| 322 | \begin{figure} |
|---|
| 323 | \begin{cfa} |
|---|
| 324 | struct Employee { |
|---|
| 325 | char * name; |
|---|
| 326 | double salary; |
|---|
| 327 | }; |
|---|
| 328 | void @?{}@( Employee & emp, char * nname, double nsalary ) with( emp ) { // auto qualification |
|---|
| 329 | name = aalloc( sizeof(nname) ); |
|---|
| 330 | strcpy( name, nname ); |
|---|
| 331 | salary = nsalary; |
|---|
| 332 | } |
|---|
| 333 | void @^?{}@( Employee & emp ) { |
|---|
| 334 | free( emp.name ); |
|---|
| 335 | } |
|---|
| 336 | { |
|---|
| 337 | Employee emp = { "Sara Schmidt", 20.5 }; $\C{// initialize with implicit constructor call}$ |
|---|
| 338 | ... // use emp |
|---|
| 339 | ^?{}( emp ); $\C{// explicit de-initialize}$ |
|---|
| 340 | ?{}( emp, "Jack Smith", 10.5 ); $\C{// explicit re-initialize}$ |
|---|
| 341 | ... // use emp |
|---|
| 342 | } $\C{// de-initialize with implicit destructor call}$ |
|---|
| 343 | \end{cfa} |
|---|
| 344 | \caption{\CFA Constructor and Destructor} |
|---|
| 345 | \label{f:CFAConstructorDestructor} |
|---|
| 346 | \end{figure} |
|---|
| 347 | |
|---|
| 348 | |
|---|
| 349 | \subsection{Special Literals} |
|---|
| 350 | |
|---|
| 351 | The C constants @0@ and @1@ have special meaning. |
|---|
| 352 | @0@ is the null pointer and is used in conditional expressions, where @if ( p )@ is rewritten @if ( p != 0 )@; |
|---|
| 353 | @1@ is an additive identity in unary operators @++@ and @--@. |
|---|
| 354 | Aware of their significance, \CFA provides a special type @zero_t@ and @one_t@ for custom types. |
|---|
| 355 | \begin{cfa} |
|---|
| 356 | struct S { int i, j; }; |
|---|
| 357 | void ?{}( S & this, @zero_t@ ) { this.i = 0; this.j = 0; } // zero_t, no parameter name allowed |
|---|
| 358 | int ?@!=@?( S this, @zero_t@ ) { return this.i != 0 && this.j != 0; } |
|---|
| 359 | S s = @0@; |
|---|
| 360 | if ( s @!= 0@ ) ... |
|---|
| 361 | \end{cfa} |
|---|
| 362 | Similarity, for @one_t@. |
|---|
| 363 | \begin{cfa} |
|---|
| 364 | void ?{}( S & this, @one_t@ ) { this.i = 1; this.j = 1; } // one_t, no parameter name allowed |
|---|
| 365 | S & ?++( S & this, @one_t@ ) { return (S){ this.i++, this.j++ }; } |
|---|
| 366 | \end{cfa} |
|---|
| 367 | |
|---|
| 368 | |
|---|
| 369 | \subsection{Polymorphic Functions} |
|---|
| 370 | |
|---|
| 371 | Polymorphic functions are the functions that apply to all types. |
|---|
| 372 | \CFA provides \newterm{parametric polymorphism} written with the @forall@ clause. |
|---|
| 373 | \begin{cfa} |
|---|
| 374 | @forall( T )@ T identity( T v ) { return v; } |
|---|
| 375 | identity( 42 ); |
|---|
| 376 | \end{cfa} |
|---|
| 377 | The @identity@ function accepts a value from any type as an argument and returns that value. |
|---|
| 378 | At the call size, the type parameter @T@ is bounded to @int@ from the argument @42@. |
|---|
| 379 | |
|---|
| 380 | For polymorphic functions to be useful, the @forall@ clause needs \newterm{type assertion}s that restrict the polymorphic types it accepts. |
|---|
| 381 | \begin{cfa} |
|---|
| 382 | forall( T @| { void foo( T ); }@ ) void bar( T t ) { @foo( t );@ } |
|---|
| 383 | struct S { ... } s; |
|---|
| 384 | void foo( struct S ); |
|---|
| 385 | bar( s ); |
|---|
| 386 | \end{cfa} |
|---|
| 387 | The assertion on @T@ restricts the range of types that can be manipulated by @bar@ to only those that implement @foo@ with the matching signature, allowing @bar@'s call to @foo@ in its body. |
|---|
| 388 | Unlike templates in \CC, which are macro expansions at the call site, \CFA polymorphic functions are compiled, passing the call-site assertion functions as hidden parameters. |
|---|
| 389 | |
|---|
| 390 | |
|---|
| 391 | \subsection{Trait} |
|---|
| 392 | |
|---|
| 393 | A @forall@ clause can assert many restrictions on multiple types. |
|---|
| 394 | A common practice is refactoring the assertions into a named \newterm{trait}, similar to other languages like Go and Rust. |
|---|
| 395 | \begin{cfa} |
|---|
| 396 | forall(T) trait @Bird@ { |
|---|
| 397 | int days_can_fly( T ); |
|---|
| 398 | void fly( T ); |
|---|
| 399 | }; |
|---|
| 400 | forall( B | @Bird@( B ) ) |
|---|
| 401 | void bird_fly( int days_since_born, B bird ) { |
|---|
| 402 | if ( days_since_born > days_can_fly( bird )) fly( bird ); |
|---|
| 403 | } |
|---|
| 404 | struct Robin {} robin; |
|---|
| 405 | int days_can_fly( Robin robin ) { return 23; } |
|---|
| 406 | void fly( Robin robin ) {} |
|---|
| 407 | bird_fly( 23, robin ); |
|---|
| 408 | \end{cfa} |
|---|
| 409 | Grouping type assertions into a named trait effectively creates a reusable interface for parametric polymorphic types. |
|---|
| 410 | |
|---|
| 411 | |
|---|
| 412 | \section{Expression Resolution} |
|---|
| 413 | |
|---|
| 414 | Overloading poses a challenge for all expression-resolution systems. |
|---|
| 415 | Multiple overloaded names give multiple candidates at a call site, and a resolver must pick a \emph{best} match, where ``best'' is defined by a series of heuristics based on safety and programmer intuition/expectation. |
|---|
| 416 | When multiple best matches exist, the resolution is ambiguous. |
|---|
| 417 | |
|---|
| 418 | The \CFA resolver attempts to identify the best candidate based on: first, the number of parameters and types, and second, when no exact match exists, the fewest implicit conversions and polymorphic variables. |
|---|
| 419 | Finding an exact match is not discussed here, because the mechanism is fairly straightforward, even when the search space is ample; |
|---|
| 420 | only finding a non-exact match is discussed in detail. |
|---|
| 421 | |
|---|
| 422 | |
|---|
| 423 | \subsection{Conversion Cost} |
|---|
| 424 | \label{s:ConversionCost} |
|---|
| 425 | |
|---|
| 426 | Most programming languages perform some implicit conversions among basic types to facilitate mixed-mode arithmetic; |
|---|
| 427 | otherwise, the program becomes littered with many explicit casts which do not match the programmer's expectations. |
|---|
| 428 | C is an aggressive language, providing conversions among almost all basic types, even when the conversion is potentially unsafe or not meaningful, \ie @float@ to @bool@. |
|---|
| 429 | C defines the resolution pattern as ``usual arithmetic conversion''~\cite[\S~6.3.1.8]{C11}, in which C looks for a \newterm{common type} between operands, and converts one or both operands to the common type. |
|---|
| 430 | A common type is the smallest type in terms of the size of representation that both operands can be converted into without losing their precision, called a \newterm{widening} or \newterm{safe conversion}. |
|---|
| 431 | |
|---|
| 432 | \CFA generalizes ``usual arithmetic conversion'' to \newterm{conversion cost}. |
|---|
| 433 | In the first design by Bilson~\cite{Bilson03}, conversion cost is a 3-tuple, @(unsafe, poly, safe)@ applied between each argument/parameter type, where: |
|---|
| 434 | \begin{enumerate} |
|---|
| 435 | \item |
|---|
| 436 | @unsafe@ is the number of precision losing (\newterm{narrowing} conversions), |
|---|
| 437 | \item |
|---|
| 438 | @poly@ is the number of polymorphic function parameters, and |
|---|
| 439 | \item |
|---|
| 440 | @safe@ is the sum of the degree of safe (widening) conversions. |
|---|
| 441 | \end{enumerate} |
|---|
| 442 | Sum of degree is a method to quantify C's integer and floating-point rank. |
|---|
| 443 | Every pair of widening conversion types is assigned a \newterm{distance}, and the distance between the two same types is 0. |
|---|
| 444 | For example, the distance from @char@ to @int@ is 2, from @int@ to @long@ is 1, and from @int@ to @long long int@ is 2. |
|---|
| 445 | This distance does not mirror C's rank system. |
|---|
| 446 | For example, the @char@ and @signed char@ ranks are the same in C, but the distance from @char@ to @signed char@ is assigned 1. |
|---|
| 447 | @safe@ cost is summing all pairs of arguments to parameter safe conversion distances. |
|---|
| 448 | Among the three costs in Bilson's model, @unsafe@ is the most significant cost, and @safe@ is the least significant, implying that \CFA always chooses a candidate with the lowest @unsafe@, if possible. |
|---|
| 449 | |
|---|
| 450 | For example, assume the overloaded function @foo@ is called with two @int@ parameters. |
|---|
| 451 | The cost for every overloaded @foo@ has been listed along with the following: |
|---|
| 452 | \begin{cfa} |
|---|
| 453 | void foo( char, char ); $\C[2.5in]{// (1) (2, 0, 0)}$ |
|---|
| 454 | void foo( char, int ); $\C{// (2) (1, 0, 0)}$ |
|---|
| 455 | forall( T, V ) void foo( T, V ); $\C{// (3) (0, 2, 0)}$ |
|---|
| 456 | forall( T ) void foo( T, T ); $\C{// (4) (0, 2, 0)}$ |
|---|
| 457 | forall( T ) void foo( T, int ); $\C{// (5) (0, 1, 0)}$ |
|---|
| 458 | void foo( long long, long ); $\C{// (6) (0, 0, 3)}$ |
|---|
| 459 | void foo( long, long ); $\C{// (7) (0, 0, 2)}$ |
|---|
| 460 | void foo( int, long ); $\C{// (8) (0, 0, 1)}$ |
|---|
| 461 | int i, j; |
|---|
| 462 | foo( i, j ); $\C{// convert j to long and call (8)}\CRT$ |
|---|
| 463 | \end{cfa} |
|---|
| 464 | The overloaded instances are ordered from the highest to the lowest cost, and \CFA selects the last candidate (8). |
|---|
| 465 | |
|---|
| 466 | In the next iteration of \CFA, Schluntz and Aaron~\cite{Moss18} expanded conversion cost to a 7-tuple with 4 additional categories, @(unsafe, poly, safe, sign, vars, specialization, reference)@, with the following interpretations: |
|---|
| 467 | \begin{itemize} |
|---|
| 468 | \item \textit{Unsafe} |
|---|
| 469 | \item \textit{Poly} |
|---|
| 470 | \item \textit{Safe} |
|---|
| 471 | \item \textit{Sign} is the number of sign/unsign variable conversions. |
|---|
| 472 | \item \textit{Vars} is the number of polymorphic type variables. |
|---|
| 473 | \item \textit{Specialization} is the negative value of the number of type assertions. |
|---|
| 474 | \item \textit{Reference} is number of reference-to-rvalue conversion. |
|---|
| 475 | \end{itemize} |
|---|
| 476 | The extended conversion-cost model looks for candidates that are more specific and less generic. |
|---|
| 477 | @vars@ disambiguates @forall( T, V ) foo( T, V )@ and @forall( T ) void foo( T, T )@, where the extra type parameter @V@ makes is more generic. |
|---|
| 478 | A more generic type means fewer constraints on its parameter types. |
|---|
| 479 | \CFA favours candidates with more restrictions on polymorphism, so @forall( T ) void foo( T, T )@ has lower cost. |
|---|
| 480 | @specialization@ is an arbitrary count-down value starting at zero. |
|---|
| 481 | For every type assertion in the @forall@ clause (no assertions in the above example), \CFA subtracts one from @specialization@. |
|---|
| 482 | More type assertions mean more constraints on argument types, making the function less generic. |
|---|
| 483 | |
|---|
| 484 | \CFA defines two special cost values: @zero@ and @infinite@. |
|---|
| 485 | A conversion cost is @zero@ when the argument and parameter have an exact match, and a conversion cost is @infinite@ when there is no defined conversion between the two types. |
|---|
| 486 | For example, the conversion cost from @int@ to a @struct S@ is @infinite@. |
|---|
| 487 | |
|---|
| 488 | In \CFA, the meaning of a C-style cast is determined by its @Cast Cost@. |
|---|
| 489 | For most cast-expression resolutions, a cast cost equals a conversion cost. |
|---|
| 490 | Cast cost exists as an independent matrix for conversion that cannot happen implicitly while being possible with an explicit cast. |
|---|
| 491 | These conversions are often defined as having an infinite conversion cost and a non-infinite cast cost. |
|---|
