Changes in / [1661ad7:ce02877]


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

Legend:

Unmodified
Added
Removed

  • doc/theses/jiada_liang_MMath/CFAenum.tex

    r1661ad7 rce02877  
    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
     9
     10\begin{cfa}[caption={CFA Enum},captionpos=b,label={l:CFAEnum}]
     11$\it enum$-specifier:
     12        enum @(type-specifier$\(_{opt}\)$)@ identifier$\(_{opt}\)$ { cfa-enumerator-list }
     13        enum @(type-specifier$\(_{opt}\)$)@ identifier$\(_{opt}\)$ { cfa-enumerator-list , }
     14        enum @(type-specifier$\(_{opt}\)$)@ identifier
     15cfa-enumerator-list:
     16        cfa-enumerator
     17        cfa-enumerator, cfa-enumerator-list
     18cfa-enumerator:
     19        enumeration-constant
     20        $\it inline$ identifier
     21        enumeration-constant = expression
     22\end{cfa}
     23
     24A \newterm{\CFA enumeration}, or \newterm{\CFA enum}, has an optional type declaration in the bracket next to the @enum@ keyword.
     25Without optional type declarations, the syntax defines \newterm{opaque enums}.
     26Otherwise, \CFA enum with type declaration are \newterm{typed enums}.
     27
     28\section{Opaque Enum}
     29\label{s:OpaqueEnum}
     30Opaque enum is a special CFA enumeration type, where the internal representation is chosen by the compiler and hidden from users.
     31Compared C enum, opaque enums are more restrictive in terms of typing, and cannot be implicitly converted to integers.
     32Enumerators of opaque enum cannot have initializer. Declaring initializer in the body of opaque enum results in a compile error.
     33\begin{cfa}
     34enum@()@ Planets { MERCURY, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
     35
     36Planet p = URANUS;
     37int i = VENUS; @// Error, VENUS cannot be converted into an integral type
     38\end{cfa}
     39% Each opaque enum has two @attributes@: @position@ and @label@. \CFA auto-generates @attribute functions@ @posn()@ and @label()@ for every \CFA enum to returns the respective attributes.
     40Opaque enumerations have two defining properties: @label@ (name) and @order@ (position), exposed to users by predefined @attribute functions@ , with the following signatures:
     41\begin{cfa}
     42forall( E ) {
     43        unsigned posn(E e);
     44        const char * s label(E e);
     45};
     46\end{cfa}
     47With polymorphic type parameter E being substituted by enumeration types such as @Planet@.
     48
     49\begin{cfa}
     50unsigned i = posn(VENUS); // 1
     51char * s = label(MARS); // "MARS"
     52\end{cfa}
     53
     54\subsection{Representation}
     55The underlying representation of \CFA enumeration object is its order, saved as an integral type. Therefore, the size of a \CFA enumeration is consistent with C enumeration.
     56Attribute function @posn@ performs type substitution on an expression from \CFA type to integral type.
     57Names of enumerators are stored in a global data structure, with @label@ maps \CFA enumeration object to corresponding data.
     58
     59\section{Typed Enum}
    8560\label{s:EnumeratorTyping}
    8661
    8762\CFA extends the enumeration declaration by parameterizing with a type (like a generic type), allowing enumerators to be assigned any values from the declared type.
    88 Figure~\ref{f:EumeratorTyping} shows a series of examples illustrating that all \CFA types can be use with an enumeration and each type's constants used to set the enumerator constants.
     63Figure~\ref{f:EumeratorTyping} shows a series of examples illustrating that all \CFA types can be use with an enumeration and each type's values used to set the enumerator constants.
    8964Note, the synonyms @Liz@ and @Beth@ in the last declaration.
    9065Because 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}
    10866
    10967\begin{figure}
    … …  
    11775        enum( @_Complex@ ) Plane { X = 1.5+3.4i, Y = 7+3i, Z = 0+0.5i };
    11876// pointer
    119         enum( @const char *@ ) Name { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
     77        enum( @char *@ ) Name { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
    12078        int i, j, k;
    12179        enum( @int *@ ) ptr { I = &i,  J = &j,  K = &k };
    122 @***@enum( @int &@ ) ref { I = i,   J = j,   K = k };
     80        enum( @int &@ ) ref { I = i,   J = j,   K = k };
    12381// tuple
    124 @***@enum( @[int, int]@ ) { T = [ 1, 2 ] }; $\C{// new \CFA type}$
     82        enum( @[int, int]@ ) { T = [ 1, 2 ] }; $\C{// new \CFA type}$
    12583// function
    12684        void f() {...}   void g() {...}
    … …  
    150108calling constructors happens at runtime (dynamic).
    151109
    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@.
    230 
     110@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
     111value of enumerator initializers. @value()@ functions maps an enum to an elements of the array.
     112
     113
     114\subsection{Value Conversion}
     115C has an implicit type conversion from an enumerator to its base type @int@.
     116Correspondingly, \CFA has an implicit conversion from a typed enumerator to its base type.
     117\begin{cfa}
     118char currency = Dollar;
     119void foo( char * );
     120foo( Fred );
     121\end{cfa}
     122% \CFA enumeration being resolved as its base type because \CFA inserts an implicit @value()@ call on an \CFA enumeration.
     123During the resolution of expression e with \CFA enumeration type, \CFA adds @value(e)@ as an additional candidate with an extra \newterm{value} cost.
     124For expression @char currency = Dollar@, the is no defined conversion from Dollar (\CFA enumeration) type to basic type and the conversion cost is @infinite@,
     125thus the only valid candidate is @value(Dollar)@.
     126
     127@Value@ is a new category in \CFA's conversion cost model. It is defined to be a more significant factor than a @unsafe@ but weight less than @poly@.
     128The resultin g conversion cost is a 8-tuple:
     129@@(unsafe, value, poly, safe, sign, vars, specialization, reference)@@.
     130
     131\begin{cfa}
     132void bar(int);
     133enum(int) Month !{
     134        January=31, February=29, March=31, April=30, May=31, June-30,
     135        July=31, August=31, September=30, October=31, November=30, December=31
     136};
     137
     138Month a = Februrary;    // (1), with cost (0, 1, 0, 0, 0, 0, 0, 0)
     139double a = 5.5;                 // (2), with cost (1, 0, 0, 0, 0, 0, 0, 0)
     140
     141bar(a);
     142\end{cfa}
     143In the previous example, candidate (1) has an value cost to parameter type int, with is lower than (2) as an unsafe conversion from double to int.
     144\CFA chooses value cost over unsafe cost and therefore @a@ of @bar(a)@ is resolved as an @Month@.
     145
     146\begin{cfa}
     147forall(T | @CfaEnum(T)@) void bar(T);
     148
     149bar(a);                                 // (3), with cost (0, 0, 1, 0, 0, 0, 0, 0)
     150\end{cfa}
     151% @Value@ is designed to be less significant than @poly@ to allow function being generic over \CFA enumeration (see ~\ref{c:trait}).
     152Being generic over @CfaEnum@ traits (a pre-defined interface for \CFA enums) is a practice in \CFA to implement functions over \CFA enumerations, as will see in chapter~\ref{c:trait}.
     153@Value@ is a being a more significant cost than @poly@ implies if a overloaeded function defined for @CfaEnum@ (and other generic type), \CFA always
     154try to resolve it as a @CfaEnum@, rather to insert a @value@ conversion.
     155
     156\subsection{Coercion}
     157While implicit conversion from a \CFA enumeration has been disabled, a explicit coercion cast to basic type is still possible to be consistent with C. In which case,
     158\CFA converts a \CFA enumeration variable as a basic type, with the value of the @position@ of the variable.
     159
     160\section{Auto Initialization}
     161
     162C auto-initialization works for the integral type @int@ with constant expressions.
     163\begin{cfa}
     164enum Alphabet ! {
     165        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,
     166        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
     167};
     168\end{cfa}
     169The 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.
     170
     171% The notion of auto-initialization is generalized in \CFA enumertation E with base type T in the following way:
     172When an enumerator @e@ does not have a initializer, if @e@ has enumeration type @E@ with base type @T@, \CFA auto-initialize @e@ with the following scheme:
     173\begin{enumerate}
     174% \item Enumerator 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.
     175\item if e is first enumerator, e is initialized with T's @zero_t@.
     176\item otherwise, if d is the enumerator defined just before e, with d has has been initialized with expression @l@ (@l@ can also be an auto-generated), e is initialized with @l++@.
     177% \CFA reports a compile time error if T has no $zero\_t$ constructor.
     178% Enumerator 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
     179% the result of @value(d)++@. If operator @?++@ is not defined for type T, \CFA reports a compile time error.
     180
     181% Unfortunately, auto-initialization is not implemented because \CFA is only a transpiler, relying on generated C code to perform the detail work.
     182% C 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.
     183% Nevertheless, the necessary language concepts exist to support this feature.
     184\end{enumerate}
     185while @?++( T )@ can be explicitly overloaded or implicitly overloaded with properly defined @one_t@ and @?+?(T, T)@.
     186
     187Unfortunately, auto-initialization with only constant expression is not enforced because \CFA is only a transpiler, relying on generated C code to perform the detail work.
     188C 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.
     189Nevertheless, the necessary language concepts exist to support this feature.
    231190
    232191\section{Enumeration Inheritance}
    233192
    234193\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@.
     194
     195\begin{cfa}
     196enum( char * ) Names { /* as above */ };
     197enum( char * ) Names2 { @inline Names@, Jack = "JACK", Jill = "JILL" };
     198enum( char * ) Names3 { @inline Names2@, Sue = "SUE", Tom = "TOM" };
     199\end{cfa}
     200
     201Enumeration @Name2@ inherits all the enumerators and their values from enumeration @Names@ by containment, and a @Names@ enumeration is a @subtype@ of enumeration @Name2@.
    241202Note, that enumerators must be unique in inheritance but enumerator values may be repeated.
    242203
    … …  
    246207Specifically, the inheritance relationship for @Names@ is:
    247208\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}
     209Names $\(\subset\)$ Names2 $\(\subset\)$ Names3 $\C{// enum type of Names}$
     210\end{cfa}
     211
     212Inlined from \CFA enumeration @O@, new enumeration @N@ copies all enumerators from @O@, including those @O@ obtains through inheritance. Enumerators inherited from @O@
     213keeps same @label@ and @value@, but @position@ may shift to the right if other enumerators or inline enumeration declared in prior of @inline A@.
     214\begin{cfa}
     215enum() Phynchocephalia { Tuatara };
     216enum() Squamata { Snake, Lizard };
     217enum() Lepidosauromorpha { inline Phynchocephalia, inline Squamata, Kuehneosauridae };
     218\end{cfa}
     219Snake, for example, has the position 0 in Squamata, but 1 in Lepidosauromorpha as Tuatara inherited from Phynchocephalia is position 0 in Lepidosauromorpha.
     220
     221A subtype enumeration can be casted, or implicitly converted into its supertype, with a safe cost.
     222\begin{cfa}
     223enum Squamata squamata_lizard = Lizard;
     224posn(quamata_lizard); // 1
     225enum Lepidosauromorpha lepidosauromorpha_lizard = squamata_lizard;
     226posn(lepidosauromorpha_lizard); // 2
     227void foo( Lepidosauromorpha l );
     228foo( squamata_lizard );
     229posn( (Lepidosauromorpha) squamata_lizard ); // 2
     230
     231Lepidosauromorpha s = Snake;
     232\end{cfa}
     233The last expression in the preceding example is umabigious. While both @Squamata.Snake@ and @Lepidosauromorpha.Snake@ are valid candidate, @Squamata.Snake@ has
     234an associated safe cost and \CFA select the zero cost candidate @Lepidosauromorpha.Snake@.
     235
     236As discussed in \VRef{s:OpaqueEnum}, \CFA chooses position as a representation of \CFA enum. Conversion involves both change of typing
     237and possibly @position@.
     238
     239When 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".
     240\CFA runs a the following algorithm to determine the offset for an enumerator to a super type.
     241% In a summary, \CFA loops over members (include enumerators and inline enums) of the supertype.
     242% If the member is the matching enumerator, the algorithm returns its position.
     243% 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
     244% the position in the current enumeration. Otherwises, it increase the offset by the size of inline enumeration.
     245
     246\begin{cfa}
     247struct Enumerator;
     248struct CFAEnum {
     249        vector<variant<CFAEnum, Enumerator>> members;
     250};
     251pair<bool, int> calculateEnumOffset( CFAEnum dst, Enumerator e ) {
     252        int offset = 0;
     253        for( auto v: dst.members ) {
     254                if ( v.holds_alternative<Enumerator>() ) {
     255                        auto m = v.get<Enumerator>();
     256                        if ( m == e ) return make_pair( true, 0 );
     257                        offset++;
     258                } else {
     259                        auto p = calculateEnumOffset( v, e );
     260                        if ( p.first ) return make_pair( true, offset + p.second );
     261                        offset += p.second;
     262                }
     263        }
     264        return make_pair( false, offset );
     265}
     266\end{cfa}
     267
     268% \begin{cfa}
     269% Names fred = Name.Fred;
     270% (Names2) fred; (Names3) fred; (Name3) Names.Jack;  $\C{// cast to super type}$
     271% Names2 fred2 = fred; Names3 fred3 = fred2; $\C{// assign to super type}$
     272% \end{cfa}
    260273For the given function prototypes, the following calls are valid.
    261274\begin{cquote}
    … …  
    278291Note, 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.
    279292
    280 
    281293\section{Enumerator Control Structures}
    282294
    … …  
    284296In most programming languages, an enumerator is implicitly converted to its value (like a typed macro substitution).
    285297However, enumerator synonyms and typed enumerations make this implicit conversion to value incorrect in some contexts.
    286 In these contexts, a programmer's initition assumes an implicit conversion to position.
     298In these contexts, a programmer's intuition assumes an implicit conversion to position.
    287299
    288300For example, an intuitive use of enumerations is with the \CFA @switch@/@choose@ statement, where @choose@ performs an implicit @break@ rather than a fall-through at the end of a @case@ clause.

  • doc/theses/jiada_liang_MMath/background.tex

    r1661ad7 rce02877  
    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}
     403\label{s:ConversionCost}
     404In C, function call arguments and function parameters do not need to be a exact match. When types mismatch, C performs an \newterm{implicit conversion}
     405on argument to parameter type. The process is trivial with the exception on binary operators;  When types of operands are different,
     406C nees to decide which operands need implicit conversion. C defines the resolution pattern as "usual arithmetic conversion",
     407in which C looks for a \newterm{common type} between operands, and convert either one or both operands to the common type.
     408Loosely defined, a common type is a the smallest type in terms of size of representation that both operands can be converted into without losing their precision.
     409Such conversion is called "widening" or "safe conversion".
     410
     411C binary operators can be restated as 2-arity functions that overloaded with different parameters. "Usual arithmetic conversion" is to find a overloaded
     412instance that for both arguments, the conversion to parameter type is a widening conversion to the smallest type.
     413
     414\CFA generalizes "usual arithmetic conversion" to \newterm{conversion cost}. In the first design by Bilson, conversion cost is a 3-tuple,
     415@(unsafe, poly, safe)@, where @unsafe@ the number of unsafe (narrorow conversion) from argument to parameter,
     416@poly@ is the number of polymorphic function parameter,
     417and @safe@ is sum of degree of safe (widening) conversion.
     418Sum of degree is a method to quantify C's integer and floating-point rank.
     419Every pair of widening conversion types has been assigned with a \newterm{distance}, and distance between the two same type is 0.
     420For example, the distance from char to int is 2, distance from integer to long is 1, and distance from int to long long int is 2.
     421The distance does not mirror C's rank system. For example, the rank of char and signed char are the same in C, but the distance from char to signed char is assigned with 1.
     422@safe@ cost is summing all pair of argument to parameter safe conversion distance.
     423Among the three in Bilson's model, @unsafe@ is the most significant cost and @safe@ is the least significant one, with an implication that \CFA always choose
     424a candidate with the lowest @unsafe@ if possible.
     425
     426Assume the overloaded function @foo@ is called with two @int@ parameter. The cost for every overloaded @foo@ has been list along:
     427\begin{cfa}
     428void foo(char, char);                           // (2, 0, 0)
     429void foo(char, int);                            // (1, 0, 0)
     430forall(T, V) void foo(T, V);            // (0, 2, 0)
     431forall(T)        void foo(T, T);                // (0, 2, 0)
     432forall(T)        void foo(T, int);              // (0, 1, 0)
     433void foo(long long, long);                      // (0, 0, 3)
     434void foo(long, long);                           // (0, 0, 2)
     435void foo(int, long);                            // (0, 0, 1)
     436
     437int i, j; foo(i, j);
     438\end{cfa}
     439The overloaded instances are ordered from the highest to the lowest cost, and \CFA select the last candidate.
     440
     441In the later iteration of \CFA, Schluntz and Aaron expanded conversion cost to a 7-tuple with 4 additional categories,
     442@@(unsafe, poly, safe, sign, vars, specialization, reference)@@.
     443with interpretation listed below:
     444\begin{itemize}
     445\item Unsafe
     446\item Poly
     447\item Safe
     448\item Sign is the number of sign/unsign variable conversion.
     449\item Vars is the number of polymorphics type variable.
     450\item Specialization is negative value of the number of type assertion.
     451\item Reference is number of reference-to-rvalue conversion.
     452\end{itemize}
     453The extended conversion cost models looks for candidates that are more specific and less generic.
     454@Var@s was introduced by Aaron to disambugate @forall(T, V) void foo(T, V)@ and @forall(T) void foo(T, T)@. The extra type parameter @V@
     455makes it more generic and less specific. More generic type means less constraints on types of its parameters. \CFA is in favor of candidates with more
     456restrictions on polymorphism so @forall(T) void foo(T, T)@ has lower cost. @Specialization@ is a value that always less than or equal to zero. For every type assertion in @forall@ clause, \CFA subtracts one from
     457@specialization@, starting from zero. More type assertions often means more constraints on argument type, and making the function less generic.
     458
     459\CFA defines two special cost value: @zero@ and @infinite@ A conversion cost is @zero@ when argument and parameter has exact match, and a conversion cost is @infinite@ when
     460there is no defined conversion between two types. For example, the conversion cost from int to a struct type S is @infinite@.

  • doc/theses/jiada_liang_MMath/implementation.tex

    r1661ad7 rce02877  
    1 \chapter{Enumeration Implementation}
    2 
    3 
    4 
    5 \section{Enumeration Traits}
    6 
    7 \CFA defines a set of traits containing operators and helper functions for @enum@.
    8 A \CFA enumeration satisfies all of these traits allowing it to interact with runtime features in \CFA.
    9 Each trait is discussed in detail.
    10 
    11 The trait @CfaEnum@:
     1\chapter{Enumeration Traits}
     2\label{c:trait}
     3
     4\section{CfaEnum and TypedEnum}
     5
     6\CFA defines attribute functions @label()@ and @posn()@ for all \CFA enumerations,
     7and therefore \CFA enumerations fulfills the type assertions with the combination.
     8With the observation, we define trait @CfaEnum@:
    129\begin{cfa}
    1310forall( E ) trait CfaEnum {
    … …  
    1613};
    1714\end{cfa}
    18 asserts an enumeration type @E@ has named enumerator constants (@label@) with positions (@posn@).
    19 
    20 The trait @TypedEnum@ extends @CfaEnum@:
     15
     16% The trait @TypedEnum@ extends @CfaEnum@ with an additional value() assertion:
     17Typed enumerations are \CFA enumeration with an additional @value@ attribute. Extending
     18CfaEnum traits, TypedEnum is a subset of CFAEnum that implements attribute function @value()@,
     19which includes all typed enumerations.
    2120\begin{cfa}
    2221forall( E, V | CfaEnum( E ) ) trait TypedEnum {
    … …  
    2423};
    2524\end{cfa}
    26 asserting an enumeration type @E@ can have homogeneous enumerator values of type @V@.
    27 
    28 The declarative syntax
    29 \begin{cfa}
    30 enum(T) E { A = ..., B = ..., C = ... };
    31 \end{cfa}
    32 creates an enumerated type E with @label@, @posn@ and @value@ implemented automatically.
    33 \begin{cfa}
    34 void foo( T t ) { ... }
    35 void bar(E e) {
    36         choose ( e ) {
    37                 case A: printf( "\%d", posn( e) );
    38                 case B: printf( "\%s", label( e ) );
    39                 case C: foo( value( e ) );
    40         }
    41 }
    42 \end{cfa}
    43 
    44 Implementing general functions across all enumeration types is possible by asserting @CfaEnum( E, T )@, \eg:
    45 \begin{cfa}
    46 #include <string.hfa>
    47 forall( E, T | CfaEnum( E, T ) | {unsigned int toUnsigned(T)} )
    48 string formatEnum( E e ) {
    49         unsigned int v = toUnsigned( value( e ) );
    50         string out = label(e) + '(' + v +')';
    51         return out;
    52 }
    53 formatEnum( Week.Mon );
    54 formatEnum( RGB.Green );
    55 \end{cfa}
    56 
    57 \CFA does not define attribute functions for C-style enumeration.
    58 But it is possible for users to explicitly implement enumeration traits for C enum and any other types.
    59 \begin{cfa}
    60 enum Fruit { Apple, Pear, Cherry };                     $\C{// C enum}$
     25Type parameter V of TypedEnum trait binds to return type of @value()@, which is also the base
     26type for typed enumerations. CfaEnum and TypedEnum triats constitues a CfaEnum function interfaces, as well a way to define functions
     27over all CfaEnum enumerations.
     28\begin{cfa}
     29// for all type E that implements value() to return type T, where T is a type that convertible to string
     30forall(  E, T | TypedEnum( E, T ) | { ?{}(string &, T ); } )
     31string format_enum( E e ) { return label(E) + "(" + string(value(e)) + ")"; }
     32
     33// int is convertible to string; implemented in the standard library
     34enum(int) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF };
     35
     36struct color_code { int R; int G; int B };
     37// Implement color_code to string conversion
     38?{}(string & this, struct color_code p ) {
     39        this = string(p.R) + ',' + string(p.G) + ',' + string(p.B);
     40}
     41enum(color_code) Rainbow {
     42        Red = {255, 0, 0}, Orange = {255, 127, 0}, Yellow = {255, 255, 0}, Green = {0, 255, 0},
     43        Blue = {0, 0, 255}, Indigo = {75, 0, 130}, Purple = {148, 0, 211}
     44};
     45
     46format_enum(RGB.Green); // "Green(65280)"
     47format_enum(Rainbow.Green); // "Green(0,255,0)"
     48\end{cfa}
     49
     50
     51% Not only CFA enumerations can be used with CfaEnum trait, other types that satisfy
     52% CfaEnum assertions are all valid.
     53Types does not need be defined as \CFA enumerations to work with CfaEnum traits. CfaEnum applies to any type
     54with @label()@ and @value()@ being properly defined.
     55Here is an example on how to extend a C enumeration to comply CfaEnum traits:
     56\begin{cfa}
     57enum Fruit { Apple, Banana, Cherry };                   $\C{// C enum}$
    6158const char * label( Fruit f ) {
    62         choose ( f ) {
     59        choose( f ) {
    6360                case Apple: return "Apple";
    64                 case Bear: return "Pear";
     61                case Banana: return "Banana";
    6562                case Cherry: return "Cherry";
    6663        }
    6764}
    68 unsigned posn( Fruit f ) { return f; }
    69 const char * value( Fruit f ) { return ""; } $\C{// value can return any non void type}$
    70 formatEnum( Apple );                                            $\C{// Fruit is now a \CFA enum}$
    71 \end{cfa}
    72 
    73 A type that implements trait @CfaEnum@, \ie, a type has no @value@, is called an opaque enum.
    74 
    75 % \section{Enumerator Opaque Type}
    76 
    77 % \CFA provides a special opaque enumeration type, where the internal representation is chosen by the compiler and only equality operations are available.
    78 \begin{cfa}
    79 enum@()@ Planets { MERCURY, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
    80 \end{cfa}
    81 
    82 
    83 In addition, \CFA implements @Bound@ and @Serial@ for \CFA enumerations.
     65unsigned posn( Fruit f ) { return f; }
     66char value( Fruit f ) {
     67        choose(f)  {
     68                case Apple: return 'a';
     69                case Banana: return 'b';
     70                case Cherry: return 'c';
     71        }
     72}
     73
     74format_enum(Cherry); // "Cherry(c)"
     75\end{cfa}
     76
     77\subsection{Bounded and Serial}
     78A bounded type defines a lower bound and a upper bound.
    8479\begin{cfa}
    8580forall( E ) trait Bounded {
    86         E first();
    87         E last();
    88 };
    89 \end{cfa}
    90 The function @first()@ and @last()@ of enumerated type E return the first and the last enumerator declared in E, respectively. \eg:
    91 \begin{cfa}
    92 Workday day = first();                                  $\C{// Mon}$
    93 Planet outermost = last();                              $\C{// NEPTUNE}$
    94 \end{cfa}
    95 @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.
    96 Calling either functions without a context results in a type ambiguity, except in the rare case where the type environment has only one enumeration.
    97 \begin{cfa}
    98 @first();@                                                              $\C{// ambiguous because both Workday and Planet implement Bounded}$
    99 sout | @last()@;
    100 Workday day = first();                                  $\C{// day provides type Workday}$
     81        E lowerBound();
     82        E lowerBound();
     83};
     84
     85\end{cfa}
     86Both Bounded functions are implement for \CFA enumerations, with @lowerBound()@ returning the first enumerator and @upperBound()@ returning
     87the last enumerator.
     88\begin{cfa}
     89Workday day = lowerBound();                                     $\C{// Mon}$
     90Planet outermost = upperBound();                                $\C{// NEPTUNE}$
     91\end{cfa}
     92
     93The lowerBound() and upperBound() are functions overloaded on return type only, means their type resolution solely depend on the outer context,
     94including expected type as a function argument, or the left hand size of an assignment expression.
     95Calling either function without a context results in a type ambiguity, except in the rare case where the type environment has only one
     96type overloads the functions, including \CFA enumerations, which has Bounded functions automatic defined.
     97\begin{cfa}
     98@lowerBound();@                 $\C{// ambiguous as both Workday and Planet implement Bounded}$
     99sout | @lowerBound()@;
     100Workday day = first();          $\C{// day provides type Workday}$
    101101void foo( Planet p );
    102 foo( last() );                                                  $\C{// argument provides type Planet}$
    103 \end{cfa}
    104 
    105 The trait @Serial@:
     102foo( last() );                      $\C{// argument provides type Planet}$
     103\end{cfa}
     104
     105@Serial@ is a subset of @Bounded@, with functions maps elements against integers, as well implements a sequential order between members.
    106106\begin{cfa}
    107107forall( E | Bounded( E ) ) trait Serial {
    108108        unsigned fromInstance( E e );
    109         E fromInt( unsigned int posn );
     109        E fromInt( unsigned int i );
    110110        E succ( E e );
    111111        E pred( E e );
    112 };
    113 \end{cfa}
    114 is a @Bounded@ trait, where elements can be mapped to an integer sequence.
    115 A type @T@ matching @Serial@ can project to an unsigned @int@ type, \ie an instance of type T has a corresponding integer value.
    116 %However, the inverse may not be possible, and possible requires a bound check.
    117 The mapping from a serial type to integer is defined by @fromInstance@, which returns the enumerator's position.
    118 The inverse operation is @fromInt@, which performs a bound check using @first()@ and @last()@ before casting the integer into an enumerator.
    119 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@.
    120 
    121 The @succ( E e )@ and @pred( E e )@ imply the enumeration positions are consecutive and ordinal.
    122 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()$.
    123 The exception @enumRange@ is raised if the result of either operation is outside the range of type @E@.
     112        unsigned Countof( E e );
     113};
     114\end{cfa}
     115
     116% A Serail type can project to an unsigned @int@ type, \ie an instance of type T has a corresponding integer value.
     117Function @fromInstance()@ projects a @Bounded@ member to a number and @fromInt@ is the inverser. Function @succ()@ take an element, returns the "next"
     118member in sequential order and @pred()@ returns the "last" member.
     119
     120A Serial type E may not be having a one-to-one mapping to integer because of bound. An integer that cannot be mapping to a member of E is called the member \newterm{out of bound}.
     121Calling @succ()@ on @upperBound@ or @pred()@ on @lowerBound()@ results in out of bound.
     122
     123\CFA implements Serial interface for CFA enumerations with \newterm{bound check} on @fromInt()@, @succ()@ and @pred()@, and abort the program if the function call results in out of bound.
     124Unlike a cast, conversion between \CFA enumeration and integer with @Serial@ interface is type safe.
     125Specifically for @fromInt@, \CFA abort if input i smaller than @fromInstance(lowerBound())@ or greater than @fromInstance(upperBound())@
     126
     127Function @Countof@ takes an object as a parameter and returns the number of elements in the Serial type, which is @fromInstance( upper ) - fromInstance( lower ) + 1@.
     128@Countof@ does not use its arugment as procedural input; it needs
     129an argument to anchor its polymorphic type T.
     130
     131\CFA has an expression @countof@ (lower case) that returns the number of enumerators defined for enumerations.
     132\begin{cfa}
     133enum RGB {Red, Green, Blue};
     134countof( RGB ); // (1)
     135countof( Red ); // (2)
     136\end{cfa}
     137Both expressions from the previous example are converted to constant expression @3@ with no function call at runtime.
     138@countof@ also works for any type T that defines @Countof@ and @lowerBound@, for which it turns into
     139a function call @Countof( T )@. The resolution step on expression @countof(e)@ works as the following with priority ordered:
     140\begin{enumerate}
     141\item Looks for an enumeration named e, such as @enum e {... }@.
     142If such an enumeration e exists, \CFA replace @countof(e)@  with constant expression with number of enumerator of e.
     143\item Looks for a non-enumeration type named e that defines @Countof@ and @lowerBound@, including e being a polymorphic type, such as @forall(e)@.
     144If type e exists, \CFA replaces it with @Countof(lowerBound())@, where lowerBound() is bounded to type e. 
     145\item Looks for an enumerator e that defined in enumeration E. If such an enumeration e exists, \CFA replace @countof(e)@ with constant expression with number of enumerator of E.
     146\item Looks for a name e in the context with expression type E. If such name e exists, \CFA replace @countof(e)@ with function call @Countof(e)@.
     147\item If 1-4 fail, \CFA reports a type error on expression @countof(e)@.
     148\end{enumerate}
     149
     150With the @Bounded@ and @Serial@, a loop over enumeration can be implemented in the following ways:
     151\begin{cfa}
     152enum() E { ... }
     153for( unsigned i = 0; i < countof(E); i++ ) { ... }
     154for( E e = lowerBound(); ; e = succ(e) ) { ...; if (e == upperBound()) break; }
     155
     156forall( T ) {
     157        for( unsigned i = 0; i < countof(T); i++ ) { ... }
     158        for( T e = lowerBound(); ; e = succ(e) ) { ...; if (e == upperBound()) break; }
     159}
     160\end{cfa}
    124161
    125162Finally, there is an associated trait defining comparison operators among enumerators.
    … …  
    156193
    157194
    158 \section{Enumeration Variable}
    159 
    160 Although \CFA enumeration captures three different attributes, an enumeration instance does not store all this information.
    161 The @sizeof@ a \CFA enumeration instance is always 4 bytes, the same size as a C enumeration instance (@sizeof( int )@).
    162 It comes from the fact that:
    163 \begin{enumerate}
    164 \item
    165 a \CFA enumeration is always statically typed;
    166 \item
    167 it is always resolved as one of its attributes regarding real usage.
    168 \end{enumerate}
    169 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.
    170 The invocations of $positions()$, $value()$, and $label()$ turn into calls to special functions defined in the prelude:
    171 \begin{cfa}
    172 position( green );
    173 >>> position( Colour, 1 ) -> int
    174 value( green );
    175 >>> value( Colour, 1 ) -> T
    176 label( green );
    177 >>> label( Colour, 1) -> char *
    178 \end{cfa}
    179 @T@ represents the type declared in the \CFA enumeration defined and @char *@ in the example.
    180 These generated functions are $Companion Functions$, they take an $companion$ object and the position as parameters.
    181 
    182 
    183 \section{Enumeration Data}
    184 
    185 \begin{cfa}
    186 enum(T) E { ... };
    187 // backing data
    188 T * E_values;
    189 char ** E_labels;
    190 \end{cfa}
    191 Storing values and labels as arrays can sometimes help support enumeration features.
    192 However, the data structures are the overhead for the programs. We want to reduce the memory usage for enumeration support by:
    193 \begin{itemize}
    194         \item Only generates the data array if necessary
    195         \item The compilation units share the data structures.
    196         No extra overhead if the data structures are requested multiple times.
    197 \end{itemize}
    198 
    199 
    200 \section{Unification}
    201 
    202 \section{Enumeration as Value}
    203 \label{section:enumeration_as_value}
    204 An \CFA enumeration with base type T can be used seamlessly as T, without explicitly calling the pseudo-function value.
    205 \begin{cfa}
    206 char * green_value = Colour.Green; // "G"
    207 // Is equivalent to
    208 // char * green_value = value( Color.Green ); "G"
    209 \end{cfa}
    210 
    211 
    212 \section{Unification Distance}
    213 
    214 \begin{cfa}
    215 T_2 Foo(T1);
    216 \end{cfa}
    217 The @Foo@ function expects a parameter with type @T1@. In C, only a value with the exact type T1 can be used as a parameter for @Foo@. In \CFA, @Foo@ accepts value with some type @T3@ as long as @distance(T1, T3)@ is not @Infinite@.
    218 
    219 @path(A, B)@ is a compiler concept that returns one of the following:
    220 \begin{itemize}
    221         \item Zero or 0, if and only if $A == B$.
    222         \item Safe, if B can be used as A without losing its precision, or B is a subtype of A.
    223         \item Unsafe, if B loses its precision when used as A, or A is a subtype of B.
    224         \item Infinite, if B cannot be used as A. A is not a subtype of B and B is not a subtype of A.
    225 \end{itemize}
    226 
    227 For example, @path(int, int)==Zero@, @path(int, char)==Safe@, @path(int, double)==Unsafe@, @path(int, struct S)@ is @Infinite@ for @struct S{}@.
    228 @distance(A, C)@ is the minimum sum of paths from A to C. For example, if @path(A, B)==i@, @path(B, C)==j@, and @path(A, C)=k@, then $$distance(A,C)==min(path(A,B), path(B,C))==i+j$$.
    229 
    230 (Skip over the distance matrix here because it is mostly irrelevant for enumeration discussion. In the actual implementation, distance( E, T ) is 1.)
    231 
    232 The arithmetic of distance is the following:
    233 \begin{itemize}
    234         \item $Zero + v= v$, for some value v.
    235         \item $Safe * k <  Unsafe$, for finite k.
    236         \item $Unsafe * k < Infinite$, for finite k.
    237         \item $Infinite + v = Infinite$, for some value v.
    238 \end{itemize}
    239 
    240 For @enum(T) E@, @path(T, E)==Safe@ and @path(E,T)==Infinite@. In other words, enumeration type E can be @safely@ used as type T, but type T cannot be used when the resolution context expects a variable with enumeration type @E@.
    241 
    242 
    243 \section{Variable Overloading and Parameter Unification}
    244 
    245 \CFA allows variable names to be overloaded. It is possible to overload a variable that has type T and an enumeration with type T.
    246 \begin{cfa}
    247 char * green = "Green";
    248 Colour green = Colour.Green; // "G"
    249 
    250 void bar(char * s) { return s; }
    251 void foo(Colour c) { return value( c ); }
    252 
    253 foo( green ); // "G"
    254 bar( green ); // "Green"
    255 \end{cfa}
    256 \CFA's conversion distance helps disambiguation in this overloading. For the function @bar@ which expects the parameter s to have type @char *@, $distance(char *,char *) == Zero$ while $distance(char *, Colour) == Safe$, the path from @char *@ to the enumeration with based type @char *@, \CFA chooses the @green@ with type @char *@ unambiguously. On the other hand, for the function @foo@, @distance(Colour, char *)@ is @Infinite@, @foo@ picks the @green@ with type @char *@.
    257 
    258 \section{Function Overloading}
    259 Similarly, functions can be overloaded with different signatures. \CFA picks the correct function entity based on the distance between parameter types and the arguments.
    260 \begin{cfa}
    261 Colour green = Colour.Green;
    262 void foo(Colour c) { sout | "It is an enum"; } // First foo
    263 void foo(char * s) { sout | "It is a string"; } // Second foo
    264 foo( green ); // "It is an enum"
    265 \end{cfa}
    266 Because @distance(Colour, Colour)@ is @Zero@ and @distance(char *, Colour)@ is @Safe@, \CFA determines the @foo( green )@ is a call to the first foo.
    267 
    268 \section{Attributes Functions}
    269 The pseudo-function @value()@ "unboxes" the enumeration and the type of the expression is the underlying type. Therefore, in the section~\ref{section:enumeration_as_value} when assigning @Colour.Green@ to variable typed @char *@, the resolution distance is @Safe@, while assigning @value(Color.Green) to @char *) has resolution distance @Zero@.
    270 
    271 \begin{cfa}
    272 int s1;
    273 \end{cfa}
    274 The generated code for an enumeration instance is simply an int. It is to hold the position of an enumeration. And usage of variable @s1@ will be converted to return one of its attributes: label, value, or position, concerning the @Unification@ rule
    275 
    276 % \section{Unification and Resolution (this implementation will probably not be used, safe as reference for now)}
    277 
    278 % \begin{cfa}
    279 % enum Colour( char * ) { Red = "R", Green = "G", Blue = "B"  };
    280 % \end{cfa}
    281 % The @EnumInstType@ is convertible to other types.
    282 % A \CFA enumeration expression is implicitly \emph{overloaded} with its three different attributes: value, position, and label.
    283 % The \CFA compilers need to resolve an @EnumInstType@ as one of its attributes based on the current context.
    284 
    285 % \begin{cfa}[caption={Null Context}, label=lst:null_context]
    286 % {
    287 %       Colour.Green;
    288 % }
    289 % \end{cfa}
    290 % In example~\ref{lst:null_context}, the environment gives no information to help with the resolution of @Colour.Green@.
    291 % In this case, any of the attributes is resolvable.
    292 % According to the \textit{precedence rule}, the expression with @EnumInstType@ resolves as @value( Colour.Green )@.
    293 % The @EnumInstType@ is converted to the type of the value, which is statically known to the compiler as @char *@.
    294 % When the compilation reaches the code generation, the compiler outputs code for type @char *@ with the value @"G"@.
    295 % \begin{cfa}[caption={Null Context Generated Code}, label=lst:null_context]
    296 % {
    297 %       "G";
    298 % }
    299 % \end{cfa}
    300 % \begin{cfa}[caption={int Context}, label=lst:int_context]
    301 % {
    302 %       int g = Colour.Green;
    303 % }
    304 % \end{cfa}
    305 % The assignment expression gives a context for the EnumInstType resolution.
    306 % The EnumInstType is used as an @int@, and \CFA needs to determine which of the attributes can be resolved as an @int@ type.
    307 % The functions $Unify( T1, T2 ): bool$ take two types as parameters and determine if one type can be used as another.
    308 % In example~\ref{lst:int_context}, the compiler is trying to unify @int@ and @EnumInstType@ of @Colour@.
    309 % $$Unification( int, EnumInstType<Colour> )$$ which turns into three Unification call
    310 % \begin{cfa}[label=lst:attr_resolution_1]
    311 % {
    312 %       Unify( int, char * ); // unify with the type of value
    313 %       Unify( int, int ); // unify with the type of position
    314 %       Unify( int, char * ); // unify with the type of label
    315 % }
    316 % \end{cfa}
    317 % \begin{cfa}[label=lst:attr_resolution_precedence]
    318 % {
    319 %       Unification( T1, EnumInstType<T2> ) {
    320 %               if ( Unify( T1, T2 ) ) return T2;
    321 %               if ( Unify( T1, int ) ) return int;
    322 %               if ( Unify( T1, char * ) ) return char *;
    323 %               Error: Cannot Unify T1 with EnumInstType<T2>;
    324 %       }
    325 % }
    326 % \end{cfa}
    327 % After the unification, @EnumInstType@ is replaced by its attributes.
    328 
    329 % \begin{cfa}[caption={Unification Functions}, label=lst:unification_func_call]
    330 % {
    331 %       T2 foo ( T1 ); // function take variable with T1 as a parameter
    332 %       foo( EnumInstType<T3> ); // Call foo with a variable has type EnumInstType<T3>
    333 %       >>>> Unification( T1, EnumInstType<T3> )
    334 % }
    335 % \end{cfa}
    336 % % The conversion can work backward: in restrictive cases, attributes of can be implicitly converted back to the EnumInstType.
    337 % Backward conversion:
    338 % \begin{cfa}[caption={Unification Functions}, label=lst:unification_func_call]
    339 % {
    340 %       enum Colour colour = 1;
    341 % }
    342 % \end{cfa}
    343 
    344 % \begin{cfa}[caption={Unification Functions}, label=lst:unification_func_call]
    345 % {
    346 %       Unification( EnumInstType<Colour>, int ) >>> label
    347 % }
    348 % \end{cfa}
    349 % @int@ can be unified with the label of Colour.
    350 % @5@ is a constant expression $\Rightarrow$ Compiler knows the value during the compilation $\Rightarrow$ turns it into
    351 % \begin{cfa}
    352 % {
    353 %       enum Colour colour = Colour.Green;
    354 % }
    355 % \end{cfa}
    356 % Steps:
    357 % \begin{enumerate}
    358 % \item
    359 % identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
    360 % \item
    361 % @unification( EnumInstType<Colour>, int )@: @position( EnumInstType< Colour > )@
    362 % \item
    363 % return the enumeration constant at position 1
    364 % \end{enumerate}
    365 % \begin{cfa}
    366 % {
    367 %       enum T (int) { ... } // Declaration
    368 %       enum T t = 1;
    369 % }
    370 % \end{cfa}
    371 % Steps:
    372 % \begin{enumerate}
    373 % \item
    374 % identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
    375 % \item
    376 % @unification( EnumInstType<Colour>, int )@: @value( EnumInstType< Colour > )@
    377 % \item
    378 % return the FIRST enumeration constant that has the value 1, by searching through the values array
    379 % \end{enumerate}
    380 % The downside of the precedence rule: @EnumInstType@ $\Rightarrow$ @int ( value )@ $\Rightarrow$ @EnumInstType@ may return a different @EnumInstType@ because the value can be repeated and there is no way to know which one is expected $\Rightarrow$ want uniqueness
    381 
    382 % \section{Casting}
    383 % Casting an EnumInstType to some other type T works similarly to unify the EnumInstType with T. For example:
    384 % \begin{cfa}
    385 % enum( int ) Foo { A = 10, B = 100, C = 1000 };
    386 % (int) Foo.A;
    387 % \end{cfa}
    388 % The \CFA-compiler unifies @EnumInstType<int>@ with int, with returns @value( Foo.A )@, which has statically known value 10. In other words, \CFA-compiler is aware of a cast expression, and it forms the context for EnumInstType resolution. The expression with type @EnumInstType<int>@ can be replaced by the compile with a constant expression 10, and optionally discard the cast expression.
    389 
    390 % \section{Value Conversion}
    391 % As discussed in section~\ref{lst:var_declaration}, \CFA only saves @position@ as the necessary information. It is necessary for \CFA to generate intermediate code to retrieve other attributes.
    392 
    393 % \begin{cfa}
    394 % Foo a; // int a;
    395 % int j = a;
    396 % char * s = a;
    397 % \end{cfa}
    398 % Assume stores a value x, which cannot be statically determined. When assigning a to j in line 2, the compiler @Unify@ j with a, and returns @value( a )@. The generated code for the second line will be
    399 % \begin{cfa}
    400 % int j = value( Foo, a )
    401 % \end{cfa}
    402 % Similarly, the generated code for the third line is
    403 % \begin{cfa}
    404 % char * j = label( Foo, a )
    405 % \end{cfa}
    406 
    407 
    408 \section{Enumerator Initialization}
    409 
    410 An enumerator must have a deterministic immutable value, either be explicitly initialized in the enumeration definition, or implicitly initialized by rules.
    411 
    412 
    413 \section{C Enumeration Rule}
    414 
    415 A C enumeration has an integral type. If not initialized, the first enumerator implicitly has the integral value 0, and other enumerators have a value equal to its $predecessor + 1$.
    416 
    417 
    418 \section{Auto Initialization}
    419 
    420 C auto-initialization works for the integral type @int@ with constant expressions.
    421 \begin{cfa}
    422 enum Alphabet ! {
    423         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,
    424         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
    425 };
    426 \end{cfa}
    427 The 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.
    428 
    429 The notion of auto-initialization can be generalized in \CFA through the trait @AutoInitializable@.
    430 \begin{cfa}
    431 forall(T) @trait@ AutoInitializable {
    432         void ?{}( T & o, T v );                         $\C{// initialization}$
    433         void ?{}( T & t, zero_t );                      $\C{// 0}$
    434         T ?++( T & t);                                          $\C{// increment}$
    435 };
    436 \end{cfa}
    437 In addition, there is an implicit enumeration counter, @ecnt@ of type @T@, managed by the compiler.
    438 For example, the type @Odd@ satisfies @AutoInitializable@:
    439 \begin{cfa}
    440 struct Odd { int i; };
    441 void ?{}( Odd & o, int v ) { if ( v & 1 ) o.i = v; else /* error not odd */ ; };
    442 void ?{}( Odd & o, zero_t ) { o.i = 1; };
    443 Odd ?++( Odd o ) { return (Odd){ o.i + 2 }; };
    444 \end{cfa}
    445 and implicit initialization is available.
    446 \begin{cfa}
    447 enum( Odd ) { A, B, C = 7, D };                 $\C{// 1, 3, 7, 9}$
    448 \end{cfa}
    449 where the compiler performs the following transformation and runs the code.
    450 \begin{cfa}
    451 enum( Odd ) {
    452         ?{}( ecnt, @0@ }  ?{}( A, ecnt },       ?++( ecnt )  ?{}( B, ecnt ),
    453         ?{}( ecnt, 7 )  ?{}( C, ecnt ), ?++( ecnt )  ?{}( D, ecnt )
    454 };
    455 \end{cfa}
    456 
    457 Unfortunately, auto-initialization is not implemented because \CFA is only a transpiler, relying on generated C code to perform the detail work.
    458 C 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.
    459 Nevertheless, the necessary language concepts exist to support this feature.
    460 
    461 
    462 \section{Enumeration Features}
    463 
    464 
    465195\section{Iteration and Range}
    466196
    … …  
    543273for ( char * ch; labels( Alphabet ) )
    544274\end{cfa}
    545 
    546 
    547 % \section{Non-uniform Type}
    548 % TODO: Working in Progress, might need to change other sections. Conflict with the resolution right now.
    549 
    550 % \begin{cfa}
    551 % enum T( int, char * ) {
    552 %        a=42, b="Hello World"
    553 % };
    554 % \end{cfa}
    555 % The enum T declares two different types: int and char *. The enumerators of T hold values of one of the declared types.
    556 
    557 \section{Enumeration Inheritance}
    558 
    559 \begin{cfa}[label=lst:EnumInline]
    560 enum( char * ) Name { Jack = "Jack", Jill = "Jill" };
    561 enum /* inferred */ Name2 { inline Name, Sue = "Sue", Tom = "Tom" };
    562 \end{cfa}
    563 \lstinline{Inline} allows Enumeration Name2 to inherit enumerators from Name1 by containment, and a Name enumeration is a subtype of enumeration Name2. An enumeration instance of type Name can be used where an instance of Name2 is expected.
    564 \begin{cfa}[label=lst:EnumInline]
    565 Name Fred;
    566 void f( Name2 );
    567 f( Fred );
    568 \end{cfa}
    569 If enumeration A declares @inline B@ in its enumeration body, enumeration A is the "inlining enum" and enumeration B is the "inlined enum".
    570 
    571 An enumeration can inline at most one other enumeration. The inline declaration must be placed before the first enumerator of the inlining enum. The inlining enum has all the enumerators from the inlined enum, with the same labels, values, and position.
    572 \begin{cfa}[label=lst:EnumInline]
    573 enum /* inferred */ Name2 { inline Name, Sue = "Sue", Tom = "Tom" };
    574 // is equivalent to enum Name2 { Jack = "Jack", Jill="Jill", Sue = "Sue", Tom = "Tom" };
    575 \end{cfa}
    576 Name.Jack is equivalent to Name2.Jack. Their attributes are all identical. Opening both Name and Name2 in the same scope will not introduce ambiguity.
    577 \begin{cfa}[label=lst:EnumInline]
    578 with( Name, Name2 ) { Jack; } // Name.Jack and Name2.Jack are equivalent. No ambiguity
    579 \end{cfa}
    580 
    581 \section{Implementation}
    582 
    583 \section{Static Attribute Expression}
    584 \begin{cfa}[label=lst:static_attr]
    585 enum( char * ) Colour {
    586         Red = "red", Blue = "blue", Green = "green"
    587 };
    588 \end{cfa}
    589 An enumerator expression returns its enumerator value as a constant expression with no runtime cost. For example, @Colour.Red@ is equivalent to the constant expression "red", and \CFA finishes the expression evaluation before generating the corresponding C code. Applying a pseudo-function to a constant enumerator expression results in a constant expression as well. @value( Colour.Red )@, @position( Colour. Red )@, and @label( Colour.Red )@ are equivalent to constant expression with char * value "red", int value 0, and char * value "Red", respectively.
    590 
    591 \section{Runtime Attribute Expression and Weak Referenced Data}
    592 \begin{cfa}[label=lst:dynamic_attr]
    593 Colour c;
    594 ...
    595 value( c ); // or c
    596 \end{cfa}
    597 An enumeration variable c is equivalent to an integer variable with the value of @position( c )@ In Example~\ref{lst:dynamic_attr}, the value of enumeration variable c is unknown at compile time. In this case, the pseudo-function calls are reduced to expression that returns the enumerator values at runtime.
    598 
    599 \CFA stores the variables and labels in @const@ arrays to provide runtime lookup for enumeration information.
    600 
    601 \begin{cfa}[label=lst:attr_array]
    602 const char * Colour_labels [3] = { "Red", "Blue", "Green" };
    603 const char * Colour_values [3] = { "red", "blue", "green" };
    604 \end{cfa}
    605 The \CFA compiles transforms the attribute expressions into array access.
    606 \begin{cfa}[label=lst:attr_array_access]
    607 position( c ) // c; an integer
    608 value( c ); // Colour_values[c]
    609 label( c ); // Colour_labels[c]
    610 \end{cfa}
    611 
    612 To avoid unnecessary memory usage, the labels and values array are only generated as needed, and only generate once across all compilation units. By default, \CFA defers the declaration of the label and value arrays until an call to attribute function with a dynamic value. If an attribute function is never called on a dynamic value of an enumerator, the array will never be allocated. Once the arrays are created, all compilation units share a weak reference to the allocation array.
    613 
    614 \section{Enum Prelude}
    615 
    616 \begin{cfa}[label=lst:enum_func_dec]
    617 forall( T ) {
    618         unsigned position( unsigned );
    619         T value( unsigned );
    620         char * label( unsigned );
    621 }
    622 \end{cfa}
    623 \CFA loads the declaration of enumeration function from the enum.hfa.
    624 
    625 \section{Internal Representation}
    626 
    627 The definition of an enumeration is represented by an internal type called @EnumDecl@. At the minimum, it stores all the information needed to construct the companion object. Therefore, an @EnumDecl@ can be represented as the following:
    628 \begin{cfa}[label=lst:EnumDecl]
    629 forall(T)
    630 class EnumDecl {
    631         T* values;
    632         char** label;
    633 };
    634 \end{cfa}
    635 
    636 The internal representation of an enumeration constant is @EnumInstType@.
    637 An @EnumInstType@ has a reference to the \CFA-enumeration declaration and the position of the enumeration constant.
    638 \begin{cfa}[label=lst:EnumInstType]
    639 class EnumInstType {
    640         EnumDecl enumDecl;
    641         int position;
    642 };
    643 \end{cfa}
    644 In the later discussion, we will use @EnumDecl<T>@ to symbolize a @EnumDecl@ parameterized by type T, and @EnumInstType<T>@ is a declared instance of @EnumDecl<T>@.
    645 
    646 \begin{cfa}[caption={Enum Type Functions}, label=lst:cforall_enum_data]
    647 const T * const values;
    648 const char * label;
    649 int length;
    650 \end{cfa}
    651 Companion data are necessary information to represent an enumeration. They are stored as standalone pieces, rather than a structure. Those data will be loaded "on demand".
    652 Companion data are needed only if the according pseudo-functions are called. For example, the value of the enumeration Workday is loaded only if there is at least one compilation that has call $value(Workday)$. Once the values are loaded, all compilations share these values array to reduce memory usage.
    653 
    654 
    655 % \section{(Rework) Companion Object and Companion Function}
    656 
    657 % \begin{cfa}[caption={Enum Type Functions}, label=lst:cforall_enum_functions]
    658 % forall( T )
    659 % struct Companion {
    660 %       const T * const values;
    661 %                const char * label;
    662 %       int length;
    663 % };
    664 % \end{cfa}
    665 % \CFA generates companion objects, an instance of structure that encloses @necessary@ data to represent an enumeration. The size of the companion is unknown at the compilation time, and it "grows" in size to compensate for the @usage@.
    666 
    667 % The companion object is singleton across the compilation (investigation).
    668 
    669 % \CFA generates the definition of companion functions.
    670 % Because \CFA implicitly stores an enumeration instance as its position, the companion function @position@ does nothing but return the position it is passed.
    671 % Companions function @value@ and @label@ return the array item at the given position of @values@ and @labels@, respectively.
    672 % \begin{cfa}[label=lst:companion_definition]
    673 % int position( Companion o, int pos ) { return pos; }
    674 % T value( Companion o, int pos ) { return o.values[ pos ]; }
    675 % char * label( Companion o, int pos ) { return o.labels[ pos ]; }
    676 % \end{cfa}
    677 % Notably, the @Companion@ structure definition, and all companion objects, are visible to users.
    678 % A user can retrieve values and labels defined in an enumeration by accessing the values and labels directly, or indirectly by calling @Companion@ functions @values@ and @labels@
    679 % \begin{cfa}[label=lst:companion_definition_values_labels]
    680 % Colour.values; // read the Companion's values
    681 % values( Colour ); // same as Colour.values
    682 % \end{cfa}
    683 
    684 \section{Companion Traits (experimental)}
    685 Not sure its semantics yet, and it might replace a companion object.
    686 \begin{cfa}[label=lst:companion_trait]
    687 forall(T1) {
    688         trait Companion(otype T2<otype T1>) {
    689                 T1 value((otype T2<otype T1> const &);
    690                 int position(otype T2<otype T1> const &);
    691                 char * label(otype T2<otype T1> const &);
    692         }
    693 }
    694 \end{cfa}
    695 All enumerations implicitly implement the Companion trait, an interface to access attributes. The Companion can be a data type because it fulfills to requirements to have concrete instances, which are:
    696 
    697 \begin{enumerate}
    698   \item The instance of enumeration has a single polymorphic type.
    699   \item Each assertion should use the type once as a parameter.
    700 \end{enumerate}
    701 
    702 \begin{cfa}
    703 enum(int) Weekday {
    704         Mon = 10, Tue, ...
    705 };
    706 
    707 T value( enum Weekday<T> & this);
    708 int position( enum Weekday<T> & this )
    709 char * label( enum Weekday<T> & this )
    710 
    711 trait Companion obj = (enum(int)) Workday.Weekday;
    712 value(obj); // 10
    713 \end{cfa}
    714 The enumeration comes with default implementation to the Companion traits functions. The usage of Companion functions would make \CFA allocates and initializes the necessary companion arrays, and return the data at the position represented by the enumeration.
    715 (...)
    716 
    717 \section{User Define Enumeration Functions}
    718 
    719 Companion objects make extending features for \CFA enumeration easy.
    720 \begin{cfa}[label=lst:companion_user_definition]
    721 char * charastic_string( Companion o, int position ) {
    722         return sprintf( "Label: %s; Value: %s", label( o, position ), value( o, position) );
    723 }
    724 printf( charactic_string ( Color, 1 ) );
    725 >>> Label: Green; Value: G
    726 \end{cfa}
    727 Defining a function takes a Companion object effectively defines functions for all \CFA enumeration.
    728 
    729 The \CFA compiler turns a function call that takes an enumeration instance as a parameter into a function call with a companion object plus a position.
    730 Therefore, a user can use the syntax with a user-defined enumeration function call:
    731 \begin{cfa}[label=lst:companion_user_definition]
    732 charactic_string( Color.Green ); // equivalent to charactic_string( Color, 1 )
    733 >>> Label: Green; Value: G
    734 \end{cfa}
    735 Similarly, the user can work with the enumeration type itself: (see section ref...)
    736 \begin{cfa}[ label=lst:companion_user_definition]
    737 void print_enumerators ( Companion o ) {
    738         for ( c : Companion o ) {
    739                 sout | label (c) | value( c ) ;
    740         }
    741 }
    742 print_enumerators( Colour );
    743 \end{cfa}
    744 
    745 
    746 \section{Declaration}
    747 
    748 The qualified enumeration syntax is dedicated to \CFA enumeration.
    749 \begin{cfa}[label=lst:range_functions]
    750 enum (type_declaration) name { enumerator = const_expr, enumerator = const_expr, ... }
    751 \end{cfa}
    752 A compiler stores the name, the underlying type, and all enumerators in an @enumeration table@.
    753 During the $Validation$ pass, the compiler links the type declaration to the type's definition.
    754 It ensures that the name of an enumerator is unique within the enumeration body, and checks if all values of the enumerator have the declaration type.
    755 If the declared type is not @AutoInitializable@, \CFA rejects the enumeration definition.
    756 Otherwise, it attempts to initialize enumerators with the enumeration initialization pattern. (a reference to a future initialization pattern section)
    757 
    758 \begin{cfa}[label=lst:init]
    759 struct T { ... };
    760 void ?{}( T & t, zero_t ) { ... };
    761 void ?{}( T & t, one_t ) { ... };
    762 T ?+?( T & lhs, T & rhs ) { ... };
    763 
    764 enum (T) Sample {
    765         Zero: 0 /* zero_t */,
    766         One: Zero + 1 /* ?+?( Zero, one_t ) */ , ...
    767 };
    768 \end{cfa}
    769 Challenge: \\
    770 The value of an enumerator, or the initializer, requires @const_expr@.
    771 While previously getting around the issue by pushing it to the C compiler, it might not work anymore because of the user-defined types, user-defined @zero_t@, @one_t@, and addition operation.
    772 Might not be able to implement a \emph{correct} static check.
    773 
    774 \CFA $autogens$ a Companion object for the declared enumeration.
    775 \begin{cfa}[label=lst:companion]
    776 Companion( T ) Sample {
    777         .values: { 0, 0+1, 0+1+1, 0+1+1+1, ... }, /* 0: zero_t, 1: one_t, +: ?+?{} */
    778         .labels: { "Zero", "One", "Two", "Three", ...},
    779         .length: /* number of enumerators */
    780 };
    781 \end{cfa}
    782 \CFA stores values as intermediate expressions because the result of the function call to the function @?+?{}(T&, T&)@ is statically unknown to \CFA.
    783 But the result is computed at run time, and the compiler ensures the @values@ are not changed.
    784 
    785 \section{Qualified Expression}
    786 
    787 \CFA uses qualified expression to address the scoping of \CFA-enumeration.
    788 \begin{cfa}[label=lst:qualified_expression]
    789 aggregation_name.field;
    790 \end{cfa}
    791 The qualified expression is not dedicated to \CFA enumeration.
    792 It is a feature that is supported by other aggregation in \CFA as well, including a C enumeration.
    793 When C enumerations are unscoped, the qualified expression syntax still helps to disambiguate names in the context.
    794 \CFA recognizes if the expression references a \CFA aggregation by searching the presence of @aggregation_name@ in the \CFA enumeration table.
    795 If the @aggregation_name@ is identified as a \CFA enumeration, the compiler checks if @field@ presents in the declared \CFA enumeration.
    796 
    797 \section{Instance Declaration}
    798 
    799 
    800 \begin{cfa}[label=lst:var_declaration]
    801 enum Sample s1;
    802 \end{cfa}
    803 
    804 The declaration \CFA-enumeration variable has the same syntax as the C-enumeration. Internally, such a variable will be represented as an EnumInstType.

  • doc/theses/jiada_liang_MMath/uw-ethesis.tex

    r1661ad7 rce02877  
    226226\input{intro}
    227227\input{background}
     228\input{CEnum}
    228229\input{CFAenum}
    229230\input{implementation}
    230231\input{relatedwork}
    231 \input{performance}
    232232\input{conclusion}
    233233
Note: See TracChangeset for help on using the changeset viewer.