Changes in / [878b1385:5aeb1a9]


Ignore:
Location:
doc/theses/jiada_liang_MMath
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/jiada_liang_MMath/CFAenum.tex

    r878b1385 r5aeb1a9  
    11\chapter{\CFA Enumeration}
    22
    3 
    4 \CFA supports C enumeration using the same syntax and semantics for backwards compatibility.
    5 \CFA also extends C-Style enumeration by adding a number of new features that bring enumerations inline with other modern programming languages.
    6 Any enumeration extensions must be intuitive to C programmers both in syntax and semantics.
    7 The following sections detail all of my new contributions to enumerations in \CFA.
    8 
    9 
    10 \section{Aliasing}
    11 
    12 {\color{red}@***@}
    13 C already provides @const@-style aliasing using the unnamed enumerator \see{\VRef{s:TypeName}}, even if the keyword @enum@ is misleading (@const@ is better).
    14 However, given the existence of this form, it is straightforward to extend it with heterogeneous types, \ie types other than @int@.
    15 \begin{cfa}
    16 enum { Size = 20u, PI = 3.14159L, Jack = L"John" }; $\C{// not an ADT nor an enumeration}$
    17 \end{cfa}
    18 which matches with @const@ aliasing in other programming languages.
    19 (See \VRef{s:CenumImplementation} on how @gcc@/@clang@ are doing this for integral types.)
    20 Here, the type of each enumerator is the type of the initialization constant, \eg @typeof(20u)@ for @Size@ implies @unsigned int@.
    21 Auto-initialization is impossible in this case because some types do not support arithmetic.
    22 As seen in \VRef{s:EnumeratorTyping}, this feature is just a shorthand for multiple typed-enumeration declarations.
    23 
    24 
    25 \section{Enumerator Visibility}
    26 \label{s:EnumeratorVisibility}
    27 
    28 In C, unscoped enumerators present a \newterm{naming problem} when multiple enumeration types appear in the same scope with duplicate enumerator names.
    29 There is no mechanism in C to resolve these naming conflicts other than renaming one of the duplicates, which may be impossible if the conflict comes from system include files.
    30 
    31 The \CFA type-system allows extensive overloading, including enumerators.
    32 Furthermore, \CFA uses the environment, such as the left-hand of assignment and function arguments, to pinpoint the best overloaded name.
    33 \VRef[Figure]{f:EnumeratorVisibility} shows enumeration overloading and how qualification and casting are used to disambiguate ambiguous situations.
    34 \CFA overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources, like include files.
    35 Experience from \CFA developers is that the type system implicitly and correctly disambiguates the majority of overloaded names.
    36 That is, it is rare to get an incorrect selection or ambiguity, even among hundreds of overloaded variables and functions, that requires disambiguation using qualification or casting.
    37 
    38 \begin{figure}
    39 \begin{cfa}
    40 enum E1 { First, Second, Third, Fourth };
    41 enum E2 { @Fourth@, @Third@, @Second@, @First@ }; $\C{// same enumerator names}$
    42 E1 f() { return Third; }                                $\C{// overloaded functions, different return types}$
    43 E2 f() { return Fourth; }
    44 void g( E1 e );
    45 void h( E2 e );
    46 void foo() {                                                    $\C{// different resolutions and dealing with ambiguities}$
    47         E1 e1 = First;   E2 e2 = First;         $\C{// initialization}$
    48         e1 = Second;   e2 = Second;                     $\C{// assignment}$
    49         e1 = f();   e2 = f();                           $\C{// function return}$
    50         g( First );   h( First );                       $\C{// function argument}$
    51         int i = @E1.@First + @E2.@First;        $\C{// disambiguate with qualification}$
    52         int j = @(E1)@First + @(E2)@First;      $\C{// disambiguate with cast}$
    53 }
    54 \end{cfa}
    55 \caption{Enumerator Visibility and Disambiguating}
    56 \label{f:EnumeratorVisibility}
    57 \end{figure}
    58 
    59 
    60 \section{Enumerator Scoping}
    61 
    62 An enumeration can be scoped, using @'!'@, so the enumerator constants are not projected into the enclosing scope.
    63 \begin{cfa}
    64 enum Week @!@ { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun };
    65 enum RGB @!@ { Red, Green, Blue };
    66 \end{cfa}
    67 Now the enumerators \emph{must} be qualified with the associated enumeration type.
    68 \begin{cfa}
    69 Week week = @Week.@Mon;
    70 week = @Week.@Sat;
    71 RGB rgb = @RGB.@Red;
    72 rgb = @RGB.@Blue;
    73 \end{cfa}
    74 {\color{red}@***@}It is possible to toggle back to unscoped using the \CFA @with@ clause/statement (see also \CC \lstinline[language=c++]{using enum} in Section~\ref{s:C++RelatedWork}).
    75 \begin{cfa}
    76 with ( @Week@, @RGB@ ) {                                $\C{// type names}$
    77          week = @Sun@;                                          $\C{// no qualification}$
    78          rgb = @Green@;
    79 }
    80 \end{cfa}
    81 As in Section~\ref{s:EnumeratorVisibility}, opening multiple scoped enumerations in a @with@ can result in duplicate enumeration names, but \CFA implicit type resolution and explicit qualification/casting handle this localized scenario.
    82 
    83 
    84 \section{Enumerator Typing}
     3% \CFA supports C enumeration using the same syntax and semantics for backwards compatibility.
     4% \CFA also extends C-Style enumeration by adding a number of new features that bring enumerations inline with other modern programming languages.
     5% Any enumeration extensions must be intuitive to C programmers both in syntax and semantics.
     6% The following sections detail all of my new contributions to enumerations in \CFA.
     7\CFA extends the enumeration declaration by parameterizing with a type (like a generic type).
     8\begin{clang}[identifierstyle=\linespread{0.9}\it]
     9$\it enum$-specifier:
     10        enum @(type-specifier$\(_{opt}\)$)@ identifier$\(_{opt}\)$ { cfa-enumerator-list }
     11        enum @(type-specifier$\(_{opt}\)$)@ identifier$\(_{opt}\)$ { cfa-enumerator-list , }
     12        enum @(type-specifier$\(_{opt}\)$)@ identifier
     13cfa-enumerator-list:
     14        cfa-enumerator
     15        cfa-enumerator, cfa-enumerator-list
     16cfa-enumerator:
     17        enumeration-constant
     18        $\it inline$ identifier
     19        enumeration-constant = expression
     20\end{clang}
     21A \newterm{\CFA enumeration}, or \newterm{\CFA enum}, has an optional type declaration in the bracket next to the @enum@ keyword.
     22Without optional type declarations, the syntax defines "opaque enums".
     23Otherwise, \CFA enum with type declaration are "typed enums".
     24
     25\section{Opaque Enum}
     26\label{s:OpaqueEnum}
     27Opaque enum is a special CFA enumeration type, where the internal representation is chosen by the compiler and hidden from users.
     28Compared C enum, opaque enums are more restrictive in terms of typing, and cannot be implicitly converted to integers.
     29Enumerators of opaque enum cannot have initializer. Declaring initializer in the body of opaque enum results in a syntax error.
     30\begin{cfa}
     31enum@()@ Planets { MERCURY, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
     32
     33Planet p = URANUS;
     34@int i = VENUS; // Error, VENUS cannot be converted into an integral type@
     35\end{cfa}
     36Each opage enum has two @attributes@: @position@ and @label@. \CFA auto-generates @attribute functions@ @posn()@ and @label()@ for every \CFA enum to returns the respective attributes.
     37\begin{cfa}
     38// Auto-generated
     39int posn(Planet p);
     40char * s label(Planet p);
     41\end{cfa}
     42
     43\begin{cfa}
     44unsigned i = posn(VENUS); // 1
     45char * s = label(MARS); // "MARS"
     46\end{cfa}
     47
     48% \subsection{Representation}
     49\CFA uses chooses signed int as the underlying representation of an opaque enum variable, holding the value of enumeration position. Therefore, @posn()@ is in fact a cast that bypassing type system, converting an
     50cfa enum to its integral representation.
     51
     52Labels information are stored in a global array. @label()@ is a function that maps enum position to an element of the array.
     53
     54\section{Typed Enum}
    8555\label{s:EnumeratorTyping}
    8656
    … …  
    8959Note, the synonyms @Liz@ and @Beth@ in the last declaration.
    9060Because enumerators are constants, the enumeration type is implicitly @const@, so all the enumerator types in Figure~\ref{f:EumeratorTyping} are logically rewritten with @const@.
    91 
    92 C has an implicit type conversion from an enumerator to its base type @int@.
    93 Correspondingly, \CFA has an implicit (safe) conversion from a typed enumerator to its base type.
    94 \begin{cfa}
    95 char currency = Dollar;
    96 string fred = Fred;                                             $\C{// implicit conversion from char * to \CFA string type}$
    97 Person student = Beth;
    98 \end{cfa}
    99 
    100 % \begin{cfa}
    101 % struct S { int i, j; };
    102 % enum( S ) s { A = { 3,  4 }, B = { 7,  8 } };
    103 % enum( @char@ ) Currency { Dollar = '$\textdollar$', Euro = '$\texteuro$', Pound = '$\textsterling$'  };
    104 % enum( @double@ ) Planet { Venus = 4.87, Earth = 5.97, Mars = 0.642  }; // mass
    105 % enum( @char *@ ) Colour { Red = "red", Green = "green", Blue = "blue"  };
    106 % enum( @Currency@ ) Europe { Euro = '$\texteuro$', Pound = '$\textsterling$' }; // intersection
    107 % \end{cfa}
    10861
    10962\begin{figure}
    … …  
    12073        int i, j, k;
    12174        enum( @int *@ ) ptr { I = &i,  J = &j,  K = &k };
    122 @***@enum( @int &@ ) ref { I = i,   J = j,   K = k };
     75        enum( @int &@ ) ref { I = i,   J = j,   K = k };
    12376// tuple
    124 @***@enum( @[int, int]@ ) { T = [ 1, 2 ] }; $\C{// new \CFA type}$
     77        enum( @[int, int]@ ) { T = [ 1, 2 ] }; $\C{// new \CFA type}$
    12578// function
    12679        void f() {...}   void g() {...}
    … …  
    150103calling constructors happens at runtime (dynamic).
    151104
    152 
    153 \section{Opaque Enumeration}
    154 
    155 \CFA provides a special opaque (pure) enumeration type with only assignment and equality operations, and no implicit conversion to any base-type.
    156 \begin{cfa}
    157 enum@()@ Mode { O_RDONLY, O_WRONLY, O_CREAT, O_TRUNC, O_APPEND };
    158 Mode mode = O_RDONLY;
    159 if ( mode == O_CREAT ) ...
    160 bool b = mode == O_RDONLY || mode @<@ O_APPEND; $\C{// disallowed}$
    161 int www @=@ mode;                                               $\C{// disallowed}$
    162 \end{cfa}
    163 
    164 
    165 \section{Enumeration Operators}
    166 
    167 
    168 \subsection{Conversion}
    169 
    170 \CFA only proves an implicit safe conversion between an enumeration and its base type (like \CC), whereas C allows an unsafe conversion from base type to enumeration.
    171 \begin{cfa}
    172 enum(int) Colour { Red, Blue, Green };
    173 int w = Red;            $\C[1.5in]{// allowed}$
    174 Colour color = 0;       $\C{// disallowed}\CRT$
    175 \end{cfa}
    176 Unfortunately, there must be one confusing case between C enumerations and \CFA enumeration for type @int@.
    177 \begin{cfa}
    178 enum Colour { Red = 42, Blue, Green };
    179 enum(int) Colour2 { Red = 16, Blue, Green };
    180 int w = Redy;           $\C[1.5in]{// 42}\CRT$
    181 \end{cfa}
    182 Programmer intuition is that the assignment to @w@ is ambiguous.
    183 However, converting from @color@ to @int@ is zero cost (no conversion), while from @Colour2@ to @int@ is a safe conversion, which is a higher cost.
    184 This semantics means fewer backwards-compatibility issues with overloaded C and \CFA enumerators.
    185 
    186 
    187 \subsection{Properties}
    188 
    189 \VRef{s:Terminology} introduced three fundamental enumeration properties: label, position, and value.
    190 \CFA provides direct access to these three properties via the functions: @label@, @posn@, and @value@.
    191 \begin{cfa}
    192 enum( const char * ) Name { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
    193 Name name = Fred;
    194 sout | name | label( name ) | posn( name ) | value( name );
    195 FRED Fred 0 FRED
    196 \end{cfa}
    197 The default meaning for an enumeration variable in an expression is its value.
    198 
    199 
    200 \subsection{Range}
    201 
    202 The following helper function are used to access and control enumeration ranges (enumerating).
    203 
    204 The pseudo-function @countof@ (like @sizeof@) provides the size (range) of an enumeration or an enumeration instance.
    205 \begin{cfa}
    206 enum(int) Colour { Red, Blue, Green };
    207 Colour c = Red
    208 sout | countof( Colour ) | countof( c );
    209 3 3
    210 \end{cfa}
    211 @countof@ is a pseudo-function because it takes a type as an argument.
    212 The function @fromInt@ provides a safe subscript of the enumeration.
    213 \begin{cfa}
    214 Colour r = fromInt( prng( countof( Colour ) ) ); // select random colour
    215 \end{cfa}
    216 The functions @lowerBound@, @upperBound@, @succ@, and @pred@ are for enumerating.
    217 \begin{cfa}
    218 for ( Colour c = lowerBound();; ) {
    219         sout | c | nonl;
    220   if ( c == upperBound() ) break;
    221         c = succ( c );
    222 }
    223 \end{cfa}
    224 Note, the mid-exit loop is necessary to prevent triggering a @succ@ bound check, as in:
    225 \begin{cfa}
    226 for ( Colour c = lowerBound(); c <= upperBound(); c = succ( c ) ) ... // generates error
    227 \end{cfa}
    228 When @c == upperBound()@, the loop control still invokes @succ( c )@, which causes an @enumBound@ exception.
    229 Finally, there is operational overlap between @countof@ and @upperBound@.
     105@value@ is an @attribute@ that defined for typed enum along with position and label. @values@ of a typed enum are stored in a global array of declared typed, initialized with
     106value of enumerator initializers. @value()@ functions maps an enum to an elements of the array.
     107
     108
     109\subsection{Implicit Conversion}
     110C has an implicit type conversion from an enumerator to its base type @int@.
     111Correspondingly, \CFA has an implicit (safe) conversion from a typed enumerator to its base type.
     112\begin{cfa}
     113char currency = Dollar;
     114string fred = Fred;                                             $\C{// implicit conversion from char * to \CFA string type}$
     115Person student = Beth;
     116\end{cfa}
     117
     118% The implicit conversion is accomplished by the compiler adding @value()@ function calls as a candidate with safe cost. Therefore, the expression
     119% \begin{cfa}
     120% char currency = Dollar;
     121% \end{cfa}
     122% is equivalent to
     123% \begin{cfa}
     124% char currency = value(Dollar);
     125% \end{cfa}
     126% Such conversion an @additional@ safe
     127
     128The implicit conversion is accomplished by the resolver adding call to @value()@ functions as a resolution candidate with a @implicit@ cost.
     129Implicit cost is an additional category to Aaron's cost model. It is more signicant than @unsafe@ to have
     130the compiler choosing implicit conversion over the narrowing conversion; It is less signicant to @poly@
     131so that function overloaded with enum traits will be selected over the implicit. @Enum trait@ will be discussed in the chapter.
     132
     133Therefore, \CFA conversion cost is 8-tuple
     134@@(unsafe, implicit, poly, safe, sign, vars, specialization, reference)@@
     135
     136\section{Auto Initialization}
     137
     138C auto-initialization works for the integral type @int@ with constant expressions.
     139\begin{cfa}
     140enum Alphabet ! {
     141        A = 'A', B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
     142        a = 'a', b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
     143};
     144\end{cfa}
     145The complexity of the constant expression depends on the level of runtime computation the compiler implements, \eg \CC \lstinline[language={[GNU]C++}]{constexpr} provides complex compile-time computation across multiple types, which blurs the compilation/runtime boundary.
     146
     147% The notion of auto-initialization can be generalized in \CFA through the trait @AutoInitializable@.
     148% \begin{cfa}
     149% forall(T) @trait@ AutoInitializable {
     150%       void ?{}( T & o, T v );                         $\C{// initialization}$
     151%       void ?{}( T & t, zero_t );                      $\C{// 0}$
     152%       T ?++( T & t);                                          $\C{// increment}$
     153% };
     154% \end{cfa}
     155% In addition, there is an implicit enumeration counter, @ecnt@ of type @T@, managed by the compiler.
     156% For example, the type @Odd@ satisfies @AutoInitializable@:
     157% \begin{cfa}
     158% struct Odd { int i; };
     159% void ?{}( Odd & o, int v ) { if ( v & 1 ) o.i = v; else /* error not odd */ ; };
     160% void ?{}( Odd & o, zero_t ) { o.i = 1; };
     161% Odd ?++( Odd o ) { return (Odd){ o.i + 2 }; };
     162% \end{cfa}
     163% and implicit initialization is available.
     164% \begin{cfa}
     165% enum( Odd ) { A, B, C = 7, D };                       $\C{// 1, 3, 7, 9}$
     166% \end{cfa}
     167% where the compiler performs the following transformation and runs the code.
     168% \begin{cfa}
     169% enum( Odd ) {
     170%       ?{}( ecnt, @0@ }  ?{}( A, ecnt },       ?++( ecnt )  ?{}( B, ecnt ),
     171%       ?{}( ecnt, 7 )  ?{}( C, ecnt ), ?++( ecnt )  ?{}( D, ecnt )
     172% };
     173% \end{cfa}
     174
     175The notion of auto-initialization is generalized in \CFA enum in the following way:
     176Enumerator e is the first enumerator of \CFA enumeration E with base type T. If e declares no no initializer, e is auto-initialized by the $zero\_t$ constructor of T.
     177\CFA reports a compile time error if T has no $zero\_t$ constructor.
     178Enumerator e is an enumerator of base-type T enumeration E that position i, where $i \neq 0$. And d is the enumerator with position @i-1@, e is auto-initialized with
     179the result of @value(d)++@. If operator @?++@ is not defined for type T, \CFA reports a compile time error.
     180
     181Unfortunately, auto-initialization is not implemented because \CFA is only a transpiler, relying on generated C code to perform the detail work.
     182C does not have the equivalent of \CC \lstinline[language={[GNU]C++}]{constexpr}, and it is currently beyond the scope of the \CFA project to implement a complex runtime interpreter in the transpiler.
     183Nevertheless, the necessary language concepts exist to support this feature.
     184
    230185
    231186
    … …  
    233188
    234189\CFA Plan-9 inheritance may be used with enumerations, where Plan-9 inheritance is containment inheritance with implicit unscoping (like a nested unnamed @struct@/@union@ in C).
    235 \begin{cfa}
    236 enum( const char * ) Names { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
    237 enum( const char * ) Names2 { @inline Names@, Jack = "JACK", Jill = "JILL" };
    238 enum( const char * ) Names3 { @inline Names2@, Sue = "SUE", Tom = "TOM" };
    239 \end{cfa}
    240 Enumeration @Name2@ inherits all the enumerators and their values from enumeration @Names@ by containment, and a @Names@ enumeration is a subtype of enumeration @Name2@.
     190
     191\begin{cfa}
     192enum( char * ) Names { /* as above */ };
     193enum( char * ) Names2 { @inline Names@, Jack = "JACK", Jill = "JILL" };
     194enum( char * ) Names3 { @inline Names2@, Sue = "SUE", Tom = "TOM" };
     195\end{cfa}
     196
     197Enumeration @Name2@ inherits all the enumerators and their values from enumeration @Names@ by containment, and a @Names@ enumeration is a @subtype@ of enumeration @Name2@.
    241198Note, that enumerators must be unique in inheritance but enumerator values may be repeated.
    242199
    … …  
    246203Specifically, the inheritance relationship for @Names@ is:
    247204\begin{cfa}
    248 Names  $\(\subset\)$  Names2  $\(\subset\)$  Names3  $\C{// enum type of Names}$
    249 \end{cfa}
    250 A subtype can be cast to its supertype, assigned to a supertype variable, or used as a function argument that expects the supertype.
    251 \begin{cfa}
    252 Names fred = Names.Fred;
    253 (Names2)fred;   (Names3)fred;   (Names3)Names2.Jack;  $\C{// cast to super type}$
    254 Names2 fred2 = fred;   Names3 fred3 = fred2;    $\C{// assign to super type}$
    255 \end{cfa}
    256 As well, there is the implicit cast to an enumerator's base-type.
    257 \begin{cfa}
    258 const char * name = fred;
    259 \end{cfa}
     205Names $\(\subset\)$ Names2 $\(\subset\)$ Names3 $\C{// enum type of Names}$
     206\end{cfa}
     207
     208Inlined from \CFA enumeration @O@, new enumeration @N@ copies all enumerators from @O@, including those @O@ obtains through inheritance. Enumerators inherited from @O@
     209keeps same @label@ and @value@, but @position@ may shift to the right if other enumerators or inline enumeration declared in prior of @inline A@.
     210\begin{cfa}
     211enum() Phynchocephalia { Tuatara };
     212enum() Squamata { Snake, Lizard };
     213enum() Lepidosauromorpha { inline Phynchocephalia, inline Squamata, Kuehneosauridae };
     214\end{cfa}
     215Snake, for example, has the position 0 in Squamata, but 1 in Lepidosauromorpha as Tuatara inherited from Phynchocephalia is position 0 in Lepidosauromorpha.
     216
     217A subtype enumeration can be casted, or implicitly converted into its supertype, with a safe cost.
     218\begin{cfa}
     219enum Squamata squamata_lizard = Lizard;
     220posn(quamata_lizard); // 1
     221enum Lepidosauromorpha lepidosauromorpha_lizard = squamata_lizard;
     222posn(lepidosauromorpha_lizard); // 2
     223void foo( Lepidosauromorpha l );
     224foo( squamata_lizard );
     225posn( (Lepidosauromorpha) squamata_lizard ); // 2
     226
     227Lepidosauromorpha s = Snake;
     228\end{cfa}
     229The last expression in the preceding example is umabigious. While both @Squamata.Snake@ and @Lepidosauromorpha.Snake@ are valid candidate, @Squamata.Snake@ has
     230an associated safe cost and \CFA select the zero cost candidate @Lepidosauromorpha.Snake@.
     231
     232As discussed in \VRef{s:OpaqueEnum}, \CFA chooses position as a representation of \CFA enum. Conversion involves both change of typing
     233and possibly @position@.
     234
     235When converting a subtype to a supertype, the position can only be a larger value. The difference between the position in subtype and in supertype is an "offset".
     236\CFA runs a the following algorithm to determine the offset for an enumerator to a super type.
     237% In a summary, \CFA loops over members (include enumerators and inline enums) of the supertype.
     238% If the member is the matching enumerator, the algorithm returns its position.
     239% If the member is a inline enumeration, the algorithm trys to find the enumerator in the inline enumeration. If success, it returns the position of enumerator in the inline enumeration, plus
     240% the position in the current enumeration. Otherwises, it increase the offset by the size of inline enumeration.
     241
     242\begin{cfa}
     243struct Enumerator;
     244struct CFAEnum {
     245        vector<variant<CFAEnum, Enumerator>> members;
     246};
     247pair<bool, int> calculateEnumOffset( CFAEnum dst, Enumerator e ) {
     248        int offset = 0;
     249        for( auto v: dst.members ) {
     250                if ( v.holds_alternative<Enumerator>() ) {
     251                        auto m = v.get<Enumerator>();
     252                        if ( m == e ) return make_pair( true, 0 );
     253                        offset++;
     254                } else {
     255                        auto p = calculateEnumOffset( v, e );
     256                        if ( p.first ) return make_pair( true, offset + p.second );
     257                        offset += p.second;
     258                }
     259        }
     260        return make_pair( false, offset );
     261}
     262\end{cfa}
     263
     264% \begin{cfa}
     265% Names fred = Name.Fred;
     266% (Names2) fred; (Names3) fred; (Name3) Names.Jack;  $\C{// cast to super type}$
     267% Names2 fred2 = fred; Names3 fred3 = fred2; $\C{// assign to super type}$
     268% \end{cfa}
    260269For the given function prototypes, the following calls are valid.
    261270\begin{cquote}
    … …  
    277286\end{cquote}
    278287Note, the validity of calls is the same for call-by-reference as for call-by-value, and @const@ restrictions are the same as for other types.
    279 
    280288
    281289\section{Enumerator Control Structures}

  • doc/theses/jiada_liang_MMath/background.tex

    r878b1385 r5aeb1a9  
    5151        int va[r];
    5252}
    53 
    54 
    5553\end{clang}
    5654\end{tabular}
    … …  
    5957Dynamically initialized identifiers may appear in initialization and array dimensions in @g++@, which allows variable-sized arrays on the stack.
    6058Again, this form of aliasing is not an enumeration.
    61 
    6259
    6360\section{C Enumeration}
    … …  
    157154Hence, initialization in the range @INT_MIN@..@INT_MAX@ is 4 bytes, and outside this range is 8 bytes.
    158155
    159 
    160156\subsection{Usage}
    161157\label{s:Usage}
    … …  
    221217\bigskip
    222218While C provides a true enumeration, it is restricted, has unsafe semantics, and does not provide useful enumeration features in other programming languages.
     219
     220\section{\CFA Polymorphism}
     221\subsection{Function Overloading}
     222Function overloading is programming languages feature wherein functions may share the same name, but with different function signatures. In both C++ and \CFA, function names can be overloaded
     223with different entities as long as they are different in terms of the number and type of parameters.
     224
     225\begin{cfa}
     226void f(); // (1)
     227void f(int); // (2); Overloaded on the number of parameters
     228void f(char); // (3); Overloaded on parameter type
     229
     230f('A');
     231\end{cfa}
     232In this case, the name f is overloaded with a nullity function and two arity functions with different parameters types. Exactly which precedures being executed
     233is determined based on the passing arguments. The last expression of the preceding example calls f with one arguments, narrowing the possible candidates down to (2) and (3).
     234Between those, function argument 'A' is an exact match to the parameter expected by (3), while needing an @implicit conversion@ to call (2). The compiler determines (3) is the better candidates among
     235and procedure (3) is being executed.
     236
     237\begin{cfa}
     238int f(int); // (4); Overloaded on return type
     239[int, int] f(int); // (5) Overloaded on the number of return value
     240\end{cfa}
     241The function declarations (4) and (5) show the ability of \CFA functions overloaded with different return value, a feature that is not shared by C++.
     242
     243
     244\subsection{Operator Overloading}
     245Operators in \CFA are specialized function and are overloadable by with specially-named functions represents the syntax used to call the operator.
     246% For example, @bool ?==?T(T lhs, T rhs)@ overloads equality operator for type T, where @?@ is the placeholders for operands for the operator.
     247\begin{cfa}
     248enum Weekday { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };
     249bool ?<?(const Weekday a, const Weekday b) {
     250        return ((int)a + 1);
     251}
     252Monday < Sunday; // False
     253?<?( Monday, Sunday ); // Equivalent syntax
     254\end{cfa}
     255Unary operators are functions that takes one argument and have name @operator?@ or @?operator@, where @?@ is the placeholders for operands.
     256Binary operators are function with two parameters. They are overloadable with function name @?operator?@.
     257
     258\subsection{Constructor and Destructor}
     259In \CFA, all objects are initialized by @constructors@ during its allocation, including basic types,
     260which are initialized by auto-generated basic type constructors.
     261
     262Constructors are overloadable functions with name @?{}@, return @void@, and have at least one parameter, which is a reference
     263to the object being constructored (Colloquially referred to "this" or "self" in other language).
     264
     265\begin{cfa}
     266struct Employee {
     267        const char * name;
     268        double salary;
     269};
     270
     271void ?{}( Employee& this, const char * name, double salary ) {
     272    this.name = name;
     273    this.salary = salary;
     274}
     275
     276Employee Sara { "Sara Schmidt", 20.5 };
     277\end{cfa}
     278Like Python, the "self" reference is implicitly passed to a constructor. The Employee constructors takes two additional arugments used in its
     279field initialization.
     280
     281A destructor in \CFA is a function that has name @^?{}@. It returns void, and take only one arugment as its "self".
     282\begin{cfa}
     283void ^?{}( Employee& this ) {
     284    free(this.name);
     285    this.name = 0p;
     286    this.salary = 0;
     287}
     288\end{cfa}
     289Destructor can be explicitly evoked as a function call, or implicitly called at the end of the block in which the object is delcared.
     290\begin{cfa}
     291{
     292^Sara{};
     293Sara{ "Sara Craft", 20 };
     294} // ^Sara{}
     295\end{cfa}
     296
     297\subsection{Variable Overloading}
     298C and C++ disallow more than one variable declared in the same scope with the same name. When a variable declare in a inner scope has the same name as
     299a variable in an outer scope, the outer scope variable is "shadowed" by the inner scope variable and cannot be accessed directly.
     300
     301\CFA has variable overloading: multiple variables can share the same name in the same scope, as long as they have different type. Name shadowing only
     302happens when the inner scope variable and the outer scope ones have the same type.
     303\begin{cfa}
     304double i = 6.0;
     305int i = 5;
     306void foo( double i ) { sout | i; } // 6.0
     307\end{cfa}
     308
     309\subsection{Special Literals}
     310Literal 0 has special meanings within different contexts: it can means "nothing" or "empty", an additive identity in arithmetic, a default value as in C (null pointer),
     311or an initial state.
     312Awaring of its significance, \CFA provides a special type for the 0 literal, @zero_t@, to define the logical @zero@ for custom types.
     313\begin{cfa}
     314struct S { int i, j; };
     315void ?{}( S & this, @zero_t@ ) { this.i = 0; this.j = 0; } // zero_t, no parameter name allowed
     316S s0 = @0@;
     317\end{cfa}
     318Overloading @zero_t@ for S provides new definition for @zero@ of type S.
     319
     320According to the C standard, @0@ is the @only@ false value. Any values compares equals to @0@ is false, and not euqals @0@ is true. As a consequence, control structure
     321such as @if()@ and @while()@ only runs it true clause when its predicate @not equals@ to @0@.
     322
     323\CFA generalizes this concept and allows to logically overloads the boolean value for any type by overloading @not equal@ comparison against @zero_t@.
     324\begin{cfa}
     325int ?@!=@?( S this, @zero_t@ ) { return this.i != 0 && this.j != 0; }
     326\end{cfa}
     327
     328% In C, the literal 0 represents the Boolean value false. The expression such as @if (x)@ is equivalent to @if (x != 0)@ .
     329% \CFA allows user to define the logical zero for a custom type by overloading the @!=@ operation against a special type, @zero_t@,
     330% so that an expression with the custom type can be used as a predicate without the need of conversion to the literal 0.
     331% \begin{cfa}
     332% struct S s;
     333% int ?!=?(S, zero_t);
     334% if (s) {}
     335% \end{cfa}
     336Literal 1 is also special. Particularly in C, the pre-increment operator and post-increment operator can be interpreted in terms of @+= 1@.
     337The logical @1@ in \CFA is represented by special type @one_t@.
     338\begin{cfa}
     339void ?{}( S & this, one_t ) { this.i = 1; this.j = 1; } // one_t, no parameter name allowed
     340S & ?+=?( S & this, one_t ) { this.i += 1; this.j += 1; return op; }
     341\end{cfa}
     342Without explictly overloaded by a user, \CFA uses the user-defined @+=(S&, one_t)@ to interpret @?++@ and @++?@, as both are polymorphic functions in \CFA.
     343
     344\subsection{Polymorphics Functions}
     345Parametric-Polymorphics functions are the functions that applied to all types. \CFA functions are parametric-polymorphics when
     346they are written with the @forall@ clause.
     347
     348\begin{cfa}
     349forall(T)
     350T identity(T x) { return x; }
     351identity(42);
     352\end{cfa}
     353The identity function accepts a value from any type as an arugment, and the type parameter @T@ is bounded to @int@ when the function
     354is called with 42.
     355
     356The forall clause can takes @type assertions@ that restricts the polymorphics type.
     357\begin{cfa}
     358forall( T | { void foo(T); } )
     359void bar(T t) { foo(t); }
     360
     361struct S {} s;
     362void foo(struct S);
     363
     364bar(s);
     365\end{cfa}
     366The assertion on @T@ restricts the range of types for bar to only those implements foo with the matching a signature, so that bar()
     367can call @foo@ in its body with type safe.
     368Calling on type with no mathcing @foo()@ implemented, such as int, causes a compile time type assertion error.
     369
     370A @forall@ clause can asserts on multiple types and with multiple asserting functions. A common practice in \CFA is to group
     371the asserting functions in to a named @trait@ .
     372
     373\begin{cfa}
     374trait Bird(T) {
     375        int days_can_fly(T i);
     376        void fly(T t);
     377};
     378
     379forall(B | Bird(B)) {
     380        void bird_fly(int days_since_born, B bird) {
     381                if (days_since_born > days_can_fly(bird)) {
     382                        fly(bird);
     383                }
     384        }
     385}
     386
     387struct Robin {} r;
     388int days_can_fly(Robin r) { return 23; }
     389void fly(Robin r) {}
     390
     391bird_fly( r );
     392\end{cfa}
     393
     394Grouping type assertions into named trait effectively create a reusable interface for parametrics polymorphics types.
     395
     396\section{Expression Resolution}
     397
     398The overloading feature poses a challenge in \CFA expression resolution. Overloadeded identifiers can refer multiple
     399candidates, with multiples being simultaneously valid. The main task of \CFA resolver is to identity a best candidate that
     400involes less implicit conversion and polymorphism.
     401
     402\subsection{Conversion Cost}
     403In C, functions argument and parameter type does not need to be exact match, and the compiler performs an @implicit conversion@ on argument.
     404\begin{cfa}
     405void foo(double i);
     406foo(42);
     407\end{cfa}
     408The implicit conversion in C is relatively simple because of the abscence of overloading, with the exception of binary operators, for which the
     409compiler needs to find a common type of both operands and the result. The pattern is known as "usual arithmetic conversions".
     410
     411\CFA generalizes C implicit conversion to function overloading as a concept of @conversion cost@.
     412Initially designed by Bilson, conversion cost is a 3-tuple, @(unsafe, poly, safe)@, where unsafe is the number of narrowing conversion,
     413poly is the count of polymorphics type binding, and safe is the sum of the degree of widening conversion. Every
     414basic type in \CFA has been assigned with a @distance to Byte@, or @distance@, and the degree of widening conversion is the difference between two distances.
     415
     416Aaron extends conversion cost to a 7-tuple,
     417@@(unsafe, poly, safe, sign, vars, specialization, reference)@@. The summary of Aaron's cost model is the following:
     418\begin{itemize}
     419\item Unsafe is the number of argument that implicitly convert to a type with high rank.
     420\item Poly accounts for number of polymorphics binding in the function declaration.
     421\item Safe is sum of distance (add reference/appendix later).
     422\item Sign is the number of sign/unsign variable conversion.
     423\item Vars is the number of polymorphics type declared in @forall@.
     424\item Specialization is opposite number of function declared in @forall@. More function declared implies more constraint on polymorphics type, and therefore has the lower cost.
     425\item Reference is number of lvalue-to-rvalue conversion.
     426\end{itemize}

  • doc/theses/jiada_liang_MMath/implementation.tex

    r878b1385 r5aeb1a9  
    11\chapter{Enumeration Implementation}
    2 
    3 
    42
    53\section{Enumeration Traits}
Note: See TracChangeset for help on using the changeset viewer.