Changeset e561551 for doc/theses


Ignore:
Timestamp:
Jul 24, 2024, 1:49:16 PM (5 months ago)
Author:
JiadaL <j82liang@…>
Branches:
master
Children:
a03ed29
Parents:
18d7aaf
Message:

Save current progress for pull

Location:
doc/theses/jiada_liang_MMath
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/jiada_liang_MMath/CFAenum.tex

    r18d7aaf re561551  
    22
    33
    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 \begin{comment}
    10         Not support.
    11 \end{comment}
    12 % \section{Aliasing}
    13 
    14 % C already provides @const@-style aliasing using the unnamed enumerator \see{\VRef{s:TypeName}}, even if the name @enum@ is misleading (@const@ would be better).
    15 % Given the existence of this form, it is straightforward to extend it with types other than @int@.
    16 % \begin{cfa}
    17 % enum E { Size = 20u, PI = 3.14159L, Jack = L"John" };
    18 % \end{cfa}
    19 % which matches with @const@ aliasing in other programming languages.
    20 % Here, the type of the enumerator is the type of the initialization constant, \eg @typeof(20u)@ for @Size@ implies @unsigned int@.
    21 % Auto-initialization is restricted to the case where all constants are @int@, matching with C.
    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-had of assignment and function parameter, to pinpoint the best overloaded name.
    33 % Furthermore, \CFA uses the left-hand of assignment in type resolution to pinpoint the best overloaded name.
    34 Finally, qualification and casting are provided to disambiguate any ambiguous situations.
    35 \begin{cfa}
    36 enum E1 { First, Second, Third, Fourth };
    37 enum E2 { @Fourth@, @Third@, @Second@, @First@ }; $\C{// same enumerator names}$
    38 E1 f() { return Third; }                                $\C{// overloaded functions, different return types}$
    39 E2 f() { return Fourth; }
    40 void g(E1 e);
    41 void h(E2 e);
    42 void foo() {
    43         E1 e1 = First;   E2 e2 = First;         $\C{// initialization}$
    44         e1 = Second;   e2 = Second;                     $\C{// assignment}$
    45         e1 = f();   e2 = f();                           $\C{// function return}$
    46         g(First); h(First);                                     $\C{// function parameter}$
    47         int i = @E1.@First + @E2.@First;        $\C{// disambiguate with qualification}$
    48         int j = @(E1)@First + @(E2)@First;      $\C{// disambiguate with cast}$
    49 }
    50 \end{cfa}
    51 \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.
    52 Experience from \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.
    53 Any ambiguity can be resolved using qualification or casting.
    54 
    55 
    56 \section{Enumerator Scoping}
    57 
    58 An enumeration can be scoped, using @'!'@, so the enumerator constants are not projected into the enclosing scope.
    59 \begin{cfa}
    60 enum Week @!@ { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun };
    61 enum RGB @!@ { Red, Green, Blue };
    62 \end{cfa}
    63 Now the enumerators \emph{must} be qualified with the associated enumeration type.
    64 \begin{cfa}
    65 Week week = @Week.@Mon;
    66 week = @Week.@Sat;
    67 RGB rgb = @RGB.@Red;
    68 rgb = @RGB.@Blue;
    69 \end{cfa}
    70 It is possible to toggle back to unscoping using the \CFA @with@ clause/statement (see also \CC \lstinline[language=c++]{using enum} in Section~\ref{s:C++RelatedWork}).
    71 \begin{cfa}
    72 with ( @Week@, @RGB@ ) {                                $\C{// type names}$
    73          week = @Sun@;                                          $\C{// no qualification}$
    74          rgb = @Green@;
    75 }
    76 \end{cfa}
    77 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.
    78 
    79 
    80 \section{Enumeration Traits}
    81 
    82 \CFA defines the set of traits containing operators and helper functions for @enum@.
    83 A \CFA enumeration satisfies all of these traits allowing it to interact with runtime features in \CFA.
    84 Each trait is discussed in detail.
    85 
    86 The trait @CfaEnum@:
    87 \begin{cfa}
    88 forall( E ) trait CfaEnum {
    89         char * label( E e );
    90         unsigned int posn( E e );
    91 };
    92 \end{cfa}
    93 
    94 describes an enumeration as a named constant with position. And @TypeEnum@
    95 \begin{cfa}
    96 forall( E, V ) trait TypeEnum {
    97         V value( E e );
    98 };     
    99 \end{cfa}
    100 asserts two types @E@ and @T@, with @T@ being the base type for the enumeration @E@.
    101 
    102 The declarative syntax
    103 \begin{cfa}
    104 enum(T) E { A = ..., B = ..., C = ... };
    105 \end{cfa}
    106 creates an enumerated type E with @label@, @posn@ and @value@ implemented automatically.
    107 
    108 \begin{cfa}
    109 void foo( T t ) { ... }
    110 void bar(E e) {
    111         choose (e) {
    112                 case A: printf("\%d", posn(e));
    113                 case B: printf("\%s", label(e));
    114                 case C: foo(value(e));
    115         }
    116 }
    117 \end{cfa}
    118 
    119 Implementing general functions across all enumeration types is possible by asserting @CfaEnum( E, T )@, \eg:
    120 \begin{cfa}
    121 #include <string.hfa>
    122 forall( E, T | CfaEnum( E, T ) | {unsigned int toUnsigned(T)} )
    123 string formatEnum( E e ) {
    124         unsigned int v = toUnsigned(value(e));
    125         string out = label(e) + '(' + v +')';
    126         return out;
    127 }
    128 printEunm( Week.Mon );
    129 printEnum( RGB.Green );
    130 \end{cfa}
    131 
    132 \CFA does not define attribute functions for C style enumeration. But it is possilbe for users to explicitly implement
    133 enumeration traits for C enum and any other types.
    134 
    135 \begin{cfa}
    136 enum Fruit { Apple, Bear, Cherry };                     $\C{// C enum}$
    137 char * label(Fruit f) {
    138         switch(f) {
    139                 case Apple: "A"; break;
    140                 case Bear: "B"; break;
    141                 case Cherry: "C"; break;
    142         }
    143 }
    144 unsigned posn(Fruit f) { return f; }
    145 char* value(Fruit f) { return ""; }             $\C{// value can return any non void type}$
    146 formatEnum( Apple );                                                    $\C{// Fruit is now a Cfa enum}$
    147 \end{cfa}
    148 
    149 A type that implements trait @CfaEnum@, \ie, a type has no @value@, is called an opaque enum.
    150 
    151 % \section{Enumerator Opaque Type}
    152 
    153 % \CFA provides a special opaque enumeration type, where the internal representation is chosen by the compiler and only equality operations are available.
     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\CFA extends the enumeration declaration by parameterizing with a type (like a generic type).
     9\begin{clang}[identifierstyle=\linespread{0.9}\it]
     10$\it enum$-specifier:
     11        enum @(type-specifier$\(_{opt}\)$)@ identifier$\(_{opt}\)$ { enumerator-list-noinit }
     12        enum @(type-specifier$\(_{opt}\)$)@ identifier$\(_{opt}\)$ { enumerator-list-noinit , }
     13        enum @(type-specifier$\(_{opt}\)$)@ identifier
     14enumerator-list-noinit:
     15        enumeration-constant
     16        enumerator-list-noinit , enumeration-constant
     17\end{clang}
     18\CFA enumerations, or \CFA enums, have optional type declaration in a bracket next to the enum keyword.
     19Without optional type declarations, the syntax defines "opaque enums".
     20Otherwise, \CFA enum with type declaration are "typed enums".
     21
     22\section{Opaque Enum}
     23\label{s:OpaqueEnum}
     24Opaque enum is a special CFA enumeration type, where the internal representation is chosen by the compiler and hidden from users.
     25Compared C enum, opaque enums are more restrictive in terms of typing, and cannot be implicitly converted to integers.
     26Enumerators of opaque enum cannot have initializer. Declaring initializer in the body of opaque enum results in a syntax error.
    15427\begin{cfa}
    15528enum@()@ Planets { MERCURY, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
    156 \end{cfa}
    157 
    158 
    159 In addition, \CFA implements @Bound@ and @Serial@ for \CFA Enums.
    160 \begin{cfa}
    161 forall( E ) trait Bounded {
    162         E first();
    163         E last();
    164 };
    165 \end{cfa}
    166 The function @first()@ and @last()@ of enumerated type E return the first and the last enumerator declared in E, respectively. \eg:
    167 \begin{cfa}
    168 Workday day = first();                                  $\C{// Mon}$
    169 Planet outermost = last();                              $\C{// NEPTUNE}$
    170 \end{cfa}
    171 @first()@ and @last()@ are overloaded with return types only, so in the example, the enumeration type is found on the left-hand side of the assignment.
    172 Calling either functions without a context results in a type ambiguity, except in the rare case where the type environment has only one enumeration.
    173 \begin{cfa}
    174 @first();@                                                              $\C{// ambiguous because both Workday and Planet implement Bounded}$
    175 sout | @last()@;
    176 Workday day = first();                                  $\C{// day provides type Workday}$
    177 void foo( Planet p );
    178 foo( last() );                                                  $\C{// parameter provides type Planet}$
    179 \end{cfa}
    180 
    181 The trait @Serial@:
    182 \begin{cfa}
    183 forall( E | Bounded( E ) ) trait Serial {
    184         unsigned fromInstance( E e );
    185         E fromInt( unsigned int posn );
    186         E succ( E e );
    187         E pred( E e );
    188 };
    189 \end{cfa}
    190 is a @Bounded@ trait, where elements can be mapped to an integer sequence.
    191 A type @T@ matching @Serial@ can project to an unsigned @int@ type, \ie an instance of type T has a corresponding integer value.
    192 %However, the inverse may not be possible, and possible requires a bound check.
    193 The mapping from a serial type to integer is defined by @fromInstance@, which returns the enumerator's position.
    194 The inverse operation is @fromInt@, which performs a bound check using @first()@ and @last()@ before casting the integer into an enumerator.
    195 Specifically, for enumerator @E@ declaring $N$ enumerators, @fromInt( i )@ returns the $i-1_{th}$ enumerator, if $0 \leq i < N$, or raises the exception @enumBound@.
    196 
    197 The @succ( E e )@ and @pred( E e )@ imply the enumeration positions are consecutive and ordinal.
    198 Specifically, if @e@ is the $i_{th}$ enumerator, @succ( e )@ returns the $i+1_{th}$ enumerator when $e \ne last()$, and @pred( e )@ returns the $i-1_{th}$ enumerator when $e \ne first()$.
    199 The exception @enumRange@ is raised if the result of either operation is outside the range of type @E@.
    200 
    201 Finally, there is an associated trait defining comparison operators among enumerators.
    202 \begin{cfa}
    203 forall( E, T | CfaEnum( E, T ) ) {
    204         // comparison
    205         int ?==?( E l, E r );           $\C{// true if l and r are same enumerators}$
    206         int ?!=?( E l, E r );           $\C{// true if l and r are different enumerators}$
    207         int ?!=?( E l, zero_t );        $\C{// true if l is not the first enumerator}$
    208         int ?<?( E l, E r );            $\C{// true if l is an enumerator before r}$
    209         int ?<=?( E l, E r );           $\C{// true if l before or the same as r}$
    210         int ?>?( E l, E r );            $\C{// true if l is an enumerator after r}$
    211         int ?>=?( E l, E r );           $\C{// true if l after or the same as r}$         
    212 }
    213 \end{cfa}
     29
     30Planet p = URANUS;
     31@int i = VENUS; // Error, VENUS cannot be converted into an integral type@
     32\end{cfa}
     33Each 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.
     34\begin{cfa}
     35// Auto-generated
     36int posn(Planet p);
     37char * s label(Planet p);
     38\end{cfa}
     39
     40\begin{cfa}
     41unsigned i = posn(VENUS); // 1
     42char * s = label(MARS); // "MARS"
     43\end{cfa}
     44
     45% \subsection{Representation}
     46\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
     47cfa enum to its integral representation.
     48
     49Labels information are stored in a global array. @label()@ is a function that maps enum position to an element of the array.
    21450
    21551\section{Typed Enum}
    … …  
    22056Note, the synonyms @Liz@ and @Beth@ in the last declaration.
    22157Because enumerators are constants, the enumeration type is implicitly @const@, so all the enumerator types in Figure~\ref{f:EumeratorTyping} are logically rewritten with @const@.
    222 
    223 C has an implicit type conversion from an enumerator to its base type @int@.
    224 Correspondingly, \CFA has an implicit (safe) conversion from a typed enumerator to its base type.
    225 \begin{cfa}
    226 char currency = Dollar;
    227 string fred = Fred;                                             $\C{// implicit conversion from char * to \CFA string type}$
    228 Person student = Beth;
    229 \end{cfa}
    230 
    231 % \begin{cfa}
    232 % struct S { int i, j; };
    233 % enum( S ) s { A = { 3,  4 }, B = { 7,  8 } };
    234 % enum( @char@ ) Currency { Dollar = '$\textdollar$', Euro = '$\texteuro$', Pound = '$\textsterling$'  };
    235 % enum( @double@ ) Planet { Venus = 4.87, Earth = 5.97, Mars = 0.642  }; // mass
    236 % enum( @char *@ ) Colour { Red = "red", Green = "green", Blue = "blue"  };
    237 % enum( @Currency@ ) Europe { Euro = '$\texteuro$', Pound = '$\textsterling$' }; // intersection
    238 % \end{cfa}
    23958
    24059\begin{figure}
    … …  
    281100calling constructors happens at runtime (dynamic).
    282101
     102@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
     103value of enumerator initializers. @value()@ functions maps an enum to an elements of the array.
     104
     105
     106\subsection{Implicit Conversion}
     107C has an implicit type conversion from an enumerator to its base type @int@.
     108Correspondingly, \CFA has an implicit (safe) conversion from a typed enumerator to its base type.
     109\begin{cfa}
     110char currency = Dollar;
     111string fred = Fred;                                             $\C{// implicit conversion from char * to \CFA string type}$
     112Person student = Beth;
     113\end{cfa}
     114
     115% The implicit conversion is accomplished by the compiler adding @value()@ function calls as a candidate with safe cost. Therefore, the expression
     116% \begin{cfa}
     117% char currency = Dollar;
     118% \end{cfa}
     119% is equivalent to
     120% \begin{cfa}
     121% char currency = value(Dollar);
     122% \end{cfa}
     123% Such conversion an @additional@ safe
     124
     125The implicit conversion is accomplished by the resolver adding call to @value()@ functions as a resolution candidate with a @implicit@ cost.
     126Implicit cost is an additional category to Aaron's cost model. It is more signicant than @unsafe@ to have
     127the compiler choosing implicit conversion over the narrowing conversion; It is less signicant to @poly@
     128so that function overloaded with enum traits will be selected over the implicit. @Enum trait@ will be discussed in the chapter.
     129
     130Therefore, \CFA conversion cost is 8-tuple
     131@@(unsafe, implicit, poly, safe, sign, vars, specialization, reference)@@
     132
     133\section{Auto Initialization}
     134
     135C auto-initialization works for the integral type @int@ with constant expressions.
     136\begin{cfa}
     137enum Alphabet ! {
     138        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,
     139        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
     140};
     141\end{cfa}
     142The 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.
     143
     144% The notion of auto-initialization can be generalized in \CFA through the trait @AutoInitializable@.
     145% \begin{cfa}
     146% forall(T) @trait@ AutoInitializable {
     147%       void ?{}( T & o, T v );                         $\C{// initialization}$
     148%       void ?{}( T & t, zero_t );                      $\C{// 0}$
     149%       T ?++( T & t);                                          $\C{// increment}$
     150% };
     151% \end{cfa}
     152% In addition, there is an implicit enumeration counter, @ecnt@ of type @T@, managed by the compiler.
     153% For example, the type @Odd@ satisfies @AutoInitializable@:
     154% \begin{cfa}
     155% struct Odd { int i; };
     156% void ?{}( Odd & o, int v ) { if ( v & 1 ) o.i = v; else /* error not odd */ ; };
     157% void ?{}( Odd & o, zero_t ) { o.i = 1; };
     158% Odd ?++( Odd o ) { return (Odd){ o.i + 2 }; };
     159% \end{cfa}
     160% and implicit initialization is available.
     161% \begin{cfa}
     162% enum( Odd ) { A, B, C = 7, D };                       $\C{// 1, 3, 7, 9}$
     163% \end{cfa}
     164% where the compiler performs the following transformation and runs the code.
     165% \begin{cfa}
     166% enum( Odd ) {
     167%       ?{}( ecnt, @0@ }  ?{}( A, ecnt },       ?++( ecnt )  ?{}( B, ecnt ),
     168%       ?{}( ecnt, 7 )  ?{}( C, ecnt ), ?++( ecnt )  ?{}( D, ecnt )
     169% };
     170% \end{cfa}
     171
     172The notion of auto-initialization is generalized in \CFA enum in the following way:
     173Enumerator 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.
     174\CFA reports a compile time error if T has no $zero\_t$ constructor.
     175Enumerator 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
     176the result of @value(d)++@. If operator @?++@ is not defined for type T, \CFA reports a compile time error.
     177
     178Unfortunately, auto-initialization is not implemented because \CFA is only a transpiler, relying on generated C code to perform the detail work.
     179C 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.
     180Nevertheless, the necessary language concepts exist to support this feature.
     181
     182
     183
    283184\section{Enumeration Inheritance}
    284185
    … …  
    291192\end{cfa}
    292193
    293 Enumeration @Name2@ inherits all the enumerators and their values from enumeration @Names@ by containment, and a @Names@ enumeration is a subtype of enumeration @Name2@.
     194Enumeration @Name2@ inherits all the enumerators and their values from enumeration @Names@ by containment, and a @Names@ enumeration is a @subtype@ of enumeration @Name2@.
    294195Note, that enumerators must be unique in inheritance but enumerator values may be repeated.
    295196
    … …  
    301202Names $\(\subset\)$ Names2 $\(\subset\)$ Names3 $\C{// enum type of Names}$
    302203\end{cfa}
    303 A subtype can be cast to its supertype, assigned to a supertype variable, or be used as a function argument that expects the supertype.
    304 \begin{cfa}
    305 Names fred = Name.Fred;
    306 (Names2) fred; (Names3) fred; (Name3) Names.Jack;  $\C{// cast to super type}$
    307 Names2 fred2 = fred; Names3 fred3 = fred2; $\C{// assign to super type}$
    308 \end{cfa}
     204
     205Inlined from \CFA enumeration @O@, new enumeration @N@ copies all enumerators from @O@, including those @O@ obtains through inheritance. Enumerators inherited from @O@
     206keeps same @label@ and @value@, but @position@ may shift to the right if other enumerators or inline enumeration declared in prior of @inline A@.
     207\begin{cfa}
     208enum() Phynchocephalia { Tuatara };
     209enum() Squamata { Snake, Lizard };
     210enum() Lepidosauromorpha { inline Phynchocephalia, inline Squamata, Kuehneosauridae };
     211\end{cfa}
     212Snake, for example, has the position 0 in Squamata, but 1 in Lepidosauromorpha as Tuatara inherited from Phynchocephalia is position 0 in Lepidosauromorpha.
     213
     214A subtype enumeration can be casted, or implicitly converted into its supertype, with a safe cost.
     215\begin{cfa}
     216enum Squamata squamata_lizard = Lizard;
     217posn(quamata_lizard); // 1
     218enum Lepidosauromorpha lepidosauromorpha_lizard = squamata_lizard;
     219posn(lepidosauromorpha_lizard); // 2
     220void foo( Lepidosauromorpha l );
     221foo( squamata_lizard );
     222posn( (Lepidosauromorpha) squamata_lizard ); // 2
     223
     224Lepidosauromorpha s = Snake;
     225\end{cfa}
     226The last expression in the preceding example is umabigious. While both @Squamata.Snake@ and @Lepidosauromorpha.Snake@ are valid candidate, @Squamata.Snake@ has
     227an associated safe cost and \CFA select the zero cost candidate @Lepidosauromorpha.Snake@.
     228
     229As discussed in \VRef{s:OpaqueEnum}, \CFA chooses position as a representation of \CFA enum. Conversion involves both change of typing
     230and possibly @position@.
     231
     232When 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".
     233\CFA runs a the following algorithm to determine the offset for an enumerator to a super type.
     234% In a summary, \CFA loops over members (include enumerators and inline enums) of the supertype.
     235% If the member is the matching enumerator, the algorithm returns its position.
     236% 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
     237% the position in the current enumeration. Otherwises, it increase the offset by the size of inline enumeration.
     238
     239\begin{cfa}
     240struct Enumerator;
     241struct CFAEnum {
     242        vector<variant<CFAEnum, Enumerator>> members;
     243};
     244pair<bool, int> calculateEnumOffset( CFAEnum dst, Enumerator e ) {
     245        int offset = 0;
     246        for( auto v: dst.members ) {
     247                if ( v.holds_alternative<Enumerator>() ) {
     248                        auto m = v.get<Enumerator>();
     249                        if ( m == e ) return make_pair( true, 0 );
     250                        offset++;
     251                } else {
     252                        auto p = calculateEnumOffset( v, e );
     253                        if ( p.first ) return make_pair( true, offset + p.second );
     254                        offset += p.second;
     255                }
     256        }
     257        return make_pair( false, offset );
     258}
     259\end{cfa}
     260
     261% \begin{cfa}
     262% Names fred = Name.Fred;
     263% (Names2) fred; (Names3) fred; (Name3) Names.Jack;  $\C{// cast to super type}$
     264% Names2 fred2 = fred; Names3 fred3 = fred2; $\C{// assign to super type}$
     265% \end{cfa}
    309266For the given function prototypes, the following calls are valid.
    310267\begin{cquote}
    … …  
    326283\end{cquote}
    327284Note, 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.
     285
     286
     287
     288\section{Enumeration Traits}
     289
     290\CFA defines the set of traits containing operators and helper functions for @enum@.
     291A \CFA enumeration satisfies all of these traits allowing it to interact with runtime features in \CFA.
     292Each trait is discussed in detail.
     293
     294The trait @CfaEnum@:
     295\begin{cfa}
     296forall( E ) trait CfaEnum {
     297        char * label( E e );
     298        unsigned int posn( E e );
     299};
     300\end{cfa}
     301
     302describes an enumeration as a named constant with position. And @TypeEnum@
     303\begin{cfa}
     304forall( E, V ) trait TypeEnum {
     305        V value( E e );
     306};     
     307\end{cfa}
     308asserts two types @E@ and @T@, with @T@ being the base type for the enumeration @E@.
     309
     310The declarative syntax
     311\begin{cfa}
     312enum(T) E { A = ..., B = ..., C = ... };
     313\end{cfa}
     314creates an enumerated type E with @label@, @posn@ and @value@ implemented automatically.
     315
     316\begin{cfa}
     317void foo( T t ) { ... }
     318void bar(E e) {
     319        choose (e) {
     320                case A: printf("\%d", posn(e));
     321                case B: printf("\%s", label(e));
     322                case C: foo(value(e));
     323        }
     324}
     325\end{cfa}
     326
     327Implementing general functions across all enumeration types is possible by asserting @CfaEnum( E, T )@, \eg:
     328\begin{cfa}
     329#include <string.hfa>
     330forall( E, T | CfaEnum( E, T ) | {unsigned int toUnsigned(T)} )
     331string formatEnum( E e ) {
     332        unsigned int v = toUnsigned(value(e));
     333        string out = label(e) + '(' + v +')';
     334        return out;
     335}
     336printEunm( Week.Mon );
     337printEnum( RGB.Green );
     338\end{cfa}
     339
     340\CFA does not define attribute functions for C style enumeration. But it is possilbe for users to explicitly implement
     341enumeration traits for C enum and any other types.
     342
     343\begin{cfa}
     344enum Fruit { Apple, Bear, Cherry };                     $\C{// C enum}$
     345char * label(Fruit f) {
     346        switch(f) {
     347                case Apple: "A"; break;
     348                case Bear: "B"; break;
     349                case Cherry: "C"; break;
     350        }
     351}
     352unsigned posn(Fruit f) { return f; }
     353char* value(Fruit f) { return ""; }             $\C{// value can return any non void type}$
     354formatEnum( Apple );                                                    $\C{// Fruit is now a Cfa enum}$
     355\end{cfa}
     356
     357A type that implements trait @CfaEnum@, \ie, a type has no @value@, is called an opaque enum.
     358
     359% \section{Enumerator Opaque Type}
     360
     361% \CFA provides a special opaque enumeration type, where the internal representation is chosen by the compiler and only equality operations are available.
     362\begin{cfa}
     363enum@()@ Planets { MERCURY, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
     364\end{cfa}
     365
     366
     367In addition, \CFA implements @Bound@ and @Serial@ for \CFA Enums.
     368\begin{cfa}
     369forall( E ) trait Bounded {
     370        E first();
     371        E last();
     372};
     373\end{cfa}
     374The function @first()@ and @last()@ of enumerated type E return the first and the last enumerator declared in E, respectively. \eg:
     375\begin{cfa}
     376Workday day = first();                                  $\C{// Mon}$
     377Planet outermost = last();                              $\C{// NEPTUNE}$
     378\end{cfa}
     379@first()@ and @last()@ are overloaded with return types only, so in the example, the enumeration type is found on the left-hand side of the assignment.
     380Calling either functions without a context results in a type ambiguity, except in the rare case where the type environment has only one enumeration.
     381\begin{cfa}
     382@first();@                                                              $\C{// ambiguous because both Workday and Planet implement Bounded}$
     383sout | @last()@;
     384Workday day = first();                                  $\C{// day provides type Workday}$
     385void foo( Planet p );
     386foo( last() );                                                  $\C{// parameter provides type Planet}$
     387\end{cfa}
     388
     389The trait @Serial@:
     390\begin{cfa}
     391forall( E | Bounded( E ) ) trait Serial {
     392        unsigned fromInstance( E e );
     393        E fromInt( unsigned int posn );
     394        E succ( E e );
     395        E pred( E e );
     396};
     397\end{cfa}
     398is a @Bounded@ trait, where elements can be mapped to an integer sequence.
     399A type @T@ matching @Serial@ can project to an unsigned @int@ type, \ie an instance of type T has a corresponding integer value.
     400%However, the inverse may not be possible, and possible requires a bound check.
     401The mapping from a serial type to integer is defined by @fromInstance@, which returns the enumerator's position.
     402The inverse operation is @fromInt@, which performs a bound check using @first()@ and @last()@ before casting the integer into an enumerator.
     403Specifically, for enumerator @E@ declaring $N$ enumerators, @fromInt( i )@ returns the $i-1_{th}$ enumerator, if $0 \leq i < N$, or raises the exception @enumBound@.
     404
     405The @succ( E e )@ and @pred( E e )@ imply the enumeration positions are consecutive and ordinal.
     406Specifically, if @e@ is the $i_{th}$ enumerator, @succ( e )@ returns the $i+1_{th}$ enumerator when $e \ne last()$, and @pred( e )@ returns the $i-1_{th}$ enumerator when $e \ne first()$.
     407The exception @enumRange@ is raised if the result of either operation is outside the range of type @E@.
     408
     409Finally, there is an associated trait defining comparison operators among enumerators.
     410\begin{cfa}
     411forall( E, T | CfaEnum( E, T ) ) {
     412        // comparison
     413        int ?==?( E l, E r );           $\C{// true if l and r are same enumerators}$
     414        int ?!=?( E l, E r );           $\C{// true if l and r are different enumerators}$
     415        int ?!=?( E l, zero_t );        $\C{// true if l is not the first enumerator}$
     416        int ?<?( E l, E r );            $\C{// true if l is an enumerator before r}$
     417        int ?<=?( E l, E r );           $\C{// true if l before or the same as r}$
     418        int ?>?( E l, E r );            $\C{// true if l is an enumerator after r}$
     419        int ?>=?( E l, E r );           $\C{// true if l after or the same as r}$         
     420}
     421\end{cfa}
     422
     423
     424
     425
    328426
    329427\section{Enumerator Control Structures}

  • doc/theses/jiada_liang_MMath/background.tex

    r18d7aaf re561551  
    129129
    130130
    131 \subsection{Implementation}
    132 
    133 In theory, a C enumeration \emph{variable} is an implementation-defined integral type large enough to hold all enumerator values.
     131\subsection{Representation}
     132
     133C standard specifies enumeration \emph{variable} is an implementation-defined integral type large enough to hold all enumerator values.
    134134In practice, C uses @int@ as the underlying type for enumeration variables, because of the restriction to integral constants, which have type @int@ (unless qualified with a size suffix).
    135 
    136135
    137136\subsection{Usage}
    … …  
    198197\bigskip
    199198While C provides a true enumeration, it is restricted, has unsafe semantics, and does provide useful enumeration features in other programming languages.
     199
     200\section{\CFA Polymorphism}
     201\subsection{Function Overloading}
     202Function 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
     203with different entities as long as they are different in terms of the number and type of parameters.
     204
     205\begin{cfa}
     206void f(); // (1)
     207void f(int); // (2); Overloaded on the number of parameters
     208void f(char); // (3); Overloaded on parameter type
     209
     210f('A');
     211\end{cfa}
     212In this case, the name f is overloaded with a nullity function and two arity functions with different parameters types. Exactly which precedures being executed
     213is 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).
     214Between 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
     215and procedure (3) is being executed.
     216
     217\begin{cfa}
     218int f(int); // (4); Overloaded on return type
     219[int, int] f(int); // (5) Overloaded on the number of return value
     220\end{cfa}
     221The function declarations (4) and (5) show the ability of \CFA functions overloaded with different return value, a feature that is not shared by C++.
     222
     223
     224\subsection{Operator Overloading}
     225Operators in \CFA are specialized function and are overloadable by with specially-named functions represents the syntax used to call the operator.
     226% For example, @bool ?==?T(T lhs, T rhs)@ overloads equality operator for type T, where @?@ is the placeholders for operands for the operator.
     227\begin{cfa}
     228enum Weekday { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };
     229bool ?<?(const Weekday a, const Weekday b) {
     230        return ((int)a + 1);
     231}
     232Monday < Sunday; // False
     233?<?( Monday, Sunday ); // Equivalent syntax
     234\end{cfa}
     235Unary operators are functions that takes one argument and have name @operator?@ or @?operator@, where @?@ is the placeholders for operands.
     236Binary operators are function with two parameters. They are overloadable with function name @?operator?@.
     237
     238\subsection{Constructor and Destructor}
     239In \CFA, all objects are initialized by @constructors@ during its allocation, including basic types,
     240which are initialized by constructors default-generated by a compiler.
     241
     242Constructors are overloadable functions with name @?{}@, return @void@, and have at least one parameter, which is a reference
     243to the object being constructored (Colloquially referred to "this" or "self" in other language).
     244
     245\begin{cfa}
     246struct Employee {
     247        const char * name;
     248        double salary;
     249};
     250
     251void ?{}( Employee& this, const char * name, double salary ) {
     252    this.name = name;
     253    this.salary = salary;
     254}
     255
     256Employee Sara { "Sara Schmidt", 20.5 };
     257\end{cfa}
     258Like Python, the "self" reference is implicitly passed to a constructor. The Employee constructors takes two additional arugments used in its
     259field initialization.
     260
     261A destructor in \CFA is a function that has name @^?{}@. It returns void, and take only one arugment as its "self".
     262\begin{cfa}
     263void ^?{}( Employee& this ) {
     264    free(this.name);
     265    this.name = 0p;
     266    this.salary = 0;
     267}
     268\end{cfa}
     269Destructor can be explicitly evoked as a function call, or implicitly called at the end of the block in which the object is delcared.
     270\begin{cfa}
     271{
     272^Sara{};
     273Sara{ "Sara Craft", 20 };
     274} // ^Sara{}
     275\end{cfa}
     276
     277\subsection{Variable Overloading}
     278C 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
     279a variable in an outer scope, the outer scope variable is "shadowed" by the inner scope variable and cannot be accessed directly.
     280
     281\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
     282happens when the inner scope variable and the outer scope ones have the same type.
     283\begin{cfa}
     284double i = 6.0;
     285int i = 5;
     286void foo( double i ) { sout | i; } // 6.0
     287\end{cfa}
     288
     289\subsection{Special Literals}
     290Literal 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),
     291or an initial state.
     292Awaring of its significance, \CFA provides a special type for the 0 literal, @zero_t@, to define the logical @zero@ for custom types.
     293\begin{cfa}
     294struct S { int i, j; };
     295void ?{}( S & this, @zero_t@ ) { this.i = 0; this.j = 0; } // zero_t, no parameter name allowed
     296S s0 = @0@;
     297\end{cfa}
     298Overloading @zero_t@ for S provides new definition for @zero@ of type S.
     299
     300According 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
     301such as @if()@ and @while()@ only runs it true clause when its predicate @not equals@ to @0@.
     302
     303\CFA generalizes this concept and allows to logically overloads the boolean value for any type by overloading @not equal@ comparison against @zero_t@.
     304\begin{cfa}
     305int ?@!=@?( S this, @zero_t@ ) { return this.i != 0 && this.j != 0; }
     306\end{cfa}
     307
     308% In C, the literal 0 represents the Boolean value false. The expression such as @if (x)@ is equivalent to @if (x != 0)@ .
     309% \CFA allows user to define the logical zero for a custom type by overloading the @!=@ operation against a special type, @zero_t@,
     310% so that an expression with the custom type can be used as a predicate without the need of conversion to the literal 0.
     311% \begin{cfa}
     312% struct S s;
     313% int ?!=?(S, zero_t);
     314% if (s) {}
     315% \end{cfa}
     316Literal 1 is also special. Particularly in C, the pre-increment operator and post-increment operator can be interpreted in terms of @+= 1@.
     317The logical @1@ in \CFA is represented by special type @one_t@.
     318\begin{cfa}
     319void ?{}( S & this, one_t ) { this.i = 1; this.j = 1; } // one_t, no parameter name allowed
     320S & ?+=?( S & this, one_t ) { this.i += 1; this.j += 1; return op; }
     321\end{cfa}
     322Without explictly overloaded by a user, \CFA uses the user-defined @+=(S&, one_t)@ to interpret @?++@ and @++?@, as both are polymorphic functions in \CFA.
     323
     324\subsection{Polymorphics Functions}
     325Parametric-Polymorphics functions are the functions that applied to all types. \CFA functions are parametric-polymorphics when
     326they are written with the @forall@ clause.
     327
     328\begin{cfa}
     329forall(T)
     330T identity(T x) { return x; }
     331identity(42);
     332\end{cfa}
     333The identity function accepts a value from any type as an arugment, and the type parameter @T@ is bounded to @int@ when the function
     334is called with 42.
     335
     336The forall clause can takes @type assertions@ that restricts the polymorphics type.
     337\begin{cfa}
     338forall( T | { void foo(T); } )
     339void bar(T t) { foo(t); }
     340
     341struct S {} s;
     342void foo(struct S);
     343
     344bar(s);
     345\end{cfa}
     346The assertion on @T@ restricts the range of types for bar to only those implements foo with the matching a signature, so that bar()
     347can call @foo@ in its body with type safe.
     348Calling on type with no mathcing @foo()@ implemented, such as int, causes a compile time type assertion error.
     349
     350A @forall@ clause can asserts on multiple types and with multiple asserting functions. A common practice in \CFA is to group
     351the asserting functions in to a named @trait@ .
     352
     353\begin{cfa}
     354trait Bird(T) {
     355        int days_can_fly(T i);
     356        void fly(T t);
     357};
     358
     359forall(B | Bird(B)) {
     360        void bird_fly(int days_since_born, B bird) {
     361                if (days_since_born > days_can_fly(bird)) {
     362                        fly(bird);
     363                }
     364        }
     365}
     366
     367struct Robin {} r;
     368int days_can_fly(Robin r) { return 23; }
     369void fly(Robin r) {}
     370
     371bird_fly( r );
     372\end{cfa}
     373
     374Grouping type assertions into named trait effectively create a reusable interface for parametrics polymorphics types.
     375
     376\section{Expression Resolution}
     377
     378The overloading feature poses a challenge in \CFA expression resolution. Overloadeded identifiers can refer multiple
     379candidates, with multiples being simultaneously valid. The main task of \CFA resolver is to identity a best candidate that
     380involes less implicit conversion and polymorphism.
     381
     382\subsection{Conversion Cost}
     383In C, functions argument and parameter type does not need to be exact match, and the compiler performs an @implicit conversion@ on argument.
     384\begin{cfa}
     385void foo(double i);
     386foo(42);
     387\end{cfa}
     388The implicit conversion in C is relatively simple because of the abscence of overloading, with the exception of binary operators, for which the
     389compiler needs to find a common type of both operands and the result. The pattern is known as "usual arithmetic conversions".
     390
     391\CFA generalizes C implicit conversion to function overloading as a concept of @conversion cost@.
     392Initially designed by Bilson, conversion cost is a 3-tuple, @(unsafe, poly, safe)@, where unsafe is the number of narrowing conversion,
     393poly is the count of polymorphics type binding, and safe is the sum of the degree of widening conversion. Every
     394basic 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.
     395
     396Aaron extends conversion cost to a 7-tuple,
     397@@(unsafe, poly, safe, sign, vars, specialization, reference)@@. The summary of Aaron's cost model is the following:
     398\begin{itemize}
     399\item Unsafe is the number of argument that implicitly convert to a type with high rank.
     400\item Poly accounts for number of polymorphics binding in the function declaration.
     401\item Safe is sum of distance (add reference/appendix later).
     402\item Sign is the number of sign/unsign variable conversion.
     403\item Vars is the number of polymorphics type declared in @forall@.
     404\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.
     405\item Reference is number of lvalue-to-rvalue conversion.
     406\end{itemize}

  • doc/theses/jiada_liang_MMath/implementation.tex

    r18d7aaf re561551  
    11\chapter{Enumeration Implementation}
    2 
    3 
    4 \section{Enumeration Variable}
    5 
    6 Although \CFA enumeration captures three different attributes, an enumeration instance does not store all this information.
    7 The @sizeof@ a \CFA enumeration instance is always 4 bytes, the same size as a C enumeration instance (@sizeof( int )@).
    8 It comes from the fact that:
    9 \begin{enumerate}
    10 \item
    11 a \CFA enumeration is always statically typed;
    12 \item
    13 it is always resolved as one of its attributes regarding real usage.
    14 \end{enumerate}
    15 When creating an enumeration instance @colour@ and assigning it with the enumerator @Color.Green@, the compiler allocates an integer variable and stores the position 1.
    16 The invocations of $positions()$, $value()$, and $label()$ turn into calls to special functions defined in the prelude:
    17 \begin{cfa}
    18 position( green );
    19 >>> position( Colour, 1 ) -> int
    20 value( green );
    21 >>> value( Colour, 1 ) -> T
    22 label( green );
    23 >>> label( Colour, 1) -> char *
    24 \end{cfa}
    25 @T@ represents the type declared in the \CFA enumeration defined and @char *@ in the example.
    26 These generated functions are $Companion Functions$, they take an $companion$ object and the position as parameters.
    27 
    282
    293\section{Enumeration Data}
Note: See TracChangeset for help on using the changeset viewer.