Changes in / [ce02877:1661ad7]


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

Legend:

Unmodified
Added
Removed

  • doc/theses/jiada_liang_MMath/CFAenum.tex

    rce02877 r1661ad7  
    11\chapter{\CFA Enumeration}
    22
    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
    15 cfa-enumerator-list:
    16         cfa-enumerator
    17         cfa-enumerator, cfa-enumerator-list
    18 cfa-enumerator:
    19         enumeration-constant
    20         $\it inline$ identifier
    21         enumeration-constant = expression
    22 \end{cfa}
    23 
    24 A \newterm{\CFA enumeration}, or \newterm{\CFA enum}, has an optional type declaration in the bracket next to the @enum@ keyword.
    25 Without optional type declarations, the syntax defines \newterm{opaque enums}.
    26 Otherwise, \CFA enum with type declaration are \newterm{typed enums}.
    27 
    28 \section{Opaque Enum}
    29 \label{s:OpaqueEnum}
    30 Opaque enum is a special CFA enumeration type, where the internal representation is chosen by the compiler and hidden from users.
    31 Compared C enum, opaque enums are more restrictive in terms of typing, and cannot be implicitly converted to integers.
    32 Enumerators of opaque enum cannot have initializer. Declaring initializer in the body of opaque enum results in a compile error.
    33 \begin{cfa}
    34 enum@()@ Planets { MERCURY, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
    35 
    36 Planet p = URANUS;
    37 int 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.
    40 Opaque enumerations have two defining properties: @label@ (name) and @order@ (position), exposed to users by predefined @attribute functions@ , with the following signatures:
    41 \begin{cfa}
    42 forall( E ) {
    43         unsigned posn(E e);
    44         const char * s label(E e);
    45 };
    46 \end{cfa}
    47 With polymorphic type parameter E being substituted by enumeration types such as @Planet@.
    48 
    49 \begin{cfa}
    50 unsigned i = posn(VENUS); // 1
    51 char * s = label(MARS); // "MARS"
    52 \end{cfa}
    53 
    54 \subsection{Representation}
    55 The 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.
    56 Attribute function @posn@ performs type substitution on an expression from \CFA type to integral type.
    57 Names of enumerators are stored in a global data structure, with @label@ maps \CFA enumeration object to corresponding data.
    58 
    59 \section{Typed Enum}
     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.
     6Any enumeration extensions must be intuitive to C programmers both in syntax and semantics.
     7The following sections detail all of my new contributions to enumerations in \CFA.
     8
     9
     10\section{Aliasing}
     11
     12{\color{red}@***@}
     13C already provides @const@-style aliasing using the unnamed enumerator \see{\VRef{s:TypeName}}, even if the keyword @enum@ is misleading (@const@ is better).
     14However, given the existence of this form, it is straightforward to extend it with heterogeneous types, \ie types other than @int@.
     15\begin{cfa}
     16enum { Size = 20u, PI = 3.14159L, Jack = L"John" }; $\C{// not an ADT nor an enumeration}$
     17\end{cfa}
     18which matches with @const@ aliasing in other programming languages.
     19(See \VRef{s:CenumImplementation} on how @gcc@/@clang@ are doing this for integral types.)
     20Here, the type of each enumerator is the type of the initialization constant, \eg @typeof(20u)@ for @Size@ implies @unsigned int@.
     21Auto-initialization is impossible in this case because some types do not support arithmetic.
     22As 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
     28In C, unscoped enumerators present a \newterm{naming problem} when multiple enumeration types appear in the same scope with duplicate enumerator names.
     29There 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
     31The \CFA type-system allows extensive overloading, including enumerators.
     32Furthermore, \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.
     35Experience from \CFA developers is that the type system implicitly and correctly disambiguates the majority of overloaded names.
     36That 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}
     40enum E1 { First, Second, Third, Fourth };
     41enum E2 { @Fourth@, @Third@, @Second@, @First@ }; $\C{// same enumerator names}$
     42E1 f() { return Third; }                                $\C{// overloaded functions, different return types}$
     43E2 f() { return Fourth; }
     44void g( E1 e );
     45void h( E2 e );
     46void 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
     62An enumeration can be scoped, using @'!'@, so the enumerator constants are not projected into the enclosing scope.
     63\begin{cfa}
     64enum Week @!@ { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun };
     65enum RGB @!@ { Red, Green, Blue };
     66\end{cfa}
     67Now the enumerators \emph{must} be qualified with the associated enumeration type.
     68\begin{cfa}
     69Week week = @Week.@Mon;
     70week = @Week.@Sat;
     71RGB rgb = @RGB.@Red;
     72rgb = @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}
     76with ( @Week@, @RGB@ ) {                                $\C{// type names}$
     77         week = @Sun@;                                          $\C{// no qualification}$
     78         rgb = @Green@;
     79}
     80\end{cfa}
     81As 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}
    6085\label{s:EnumeratorTyping}
    6186
    6287\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.
    63 Figure~\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.
     88Figure~\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.
    6489Note, the synonyms @Liz@ and @Beth@ in the last declaration.
    6590Because 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
     92C has an implicit type conversion from an enumerator to its base type @int@.
     93Correspondingly, \CFA has an implicit (safe) conversion from a typed enumerator to its base type.
     94\begin{cfa}
     95char currency = Dollar;
     96string fred = Fred;                                             $\C{// implicit conversion from char * to \CFA string type}$
     97Person 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}
    66108
    67109\begin{figure}
    … …  
    75117        enum( @_Complex@ ) Plane { X = 1.5+3.4i, Y = 7+3i, Z = 0+0.5i };
    76118// pointer
    77         enum( @char *@ ) Name { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
     119        enum( @const char *@ ) Name { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
    78120        int i, j, k;
    79121        enum( @int *@ ) ptr { I = &i,  J = &j,  K = &k };
    80         enum( @int &@ ) ref { I = i,   J = j,   K = k };
     122@***@enum( @int &@ ) ref { I = i,   J = j,   K = k };
    81123// tuple
    82         enum( @[int, int]@ ) { T = [ 1, 2 ] }; $\C{// new \CFA type}$
     124@***@enum( @[int, int]@ ) { T = [ 1, 2 ] }; $\C{// new \CFA type}$
    83125// function
    84126        void f() {...}   void g() {...}
    … …  
    108150calling constructors happens at runtime (dynamic).
    109151
    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
    111 value of enumerator initializers. @value()@ functions maps an enum to an elements of the array.
    112 
    113 
    114 \subsection{Value Conversion}
    115 C has an implicit type conversion from an enumerator to its base type @int@.
    116 Correspondingly, \CFA has an implicit conversion from a typed enumerator to its base type.
    117 \begin{cfa}
    118 char currency = Dollar;
    119 void foo( char * );
    120 foo( Fred );
    121 \end{cfa}
    122 % \CFA enumeration being resolved as its base type because \CFA inserts an implicit @value()@ call on an \CFA enumeration.
    123 During the resolution of expression e with \CFA enumeration type, \CFA adds @value(e)@ as an additional candidate with an extra \newterm{value} cost.
    124 For expression @char currency = Dollar@, the is no defined conversion from Dollar (\CFA enumeration) type to basic type and the conversion cost is @infinite@,
    125 thus 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@.
    128 The resultin g conversion cost is a 8-tuple:
    129 @@(unsafe, value, poly, safe, sign, vars, specialization, reference)@@.
    130 
    131 \begin{cfa}
    132 void bar(int);
    133 enum(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 
    138 Month a = Februrary;    // (1), with cost (0, 1, 0, 0, 0, 0, 0, 0)
    139 double a = 5.5;                 // (2), with cost (1, 0, 0, 0, 0, 0, 0, 0)
    140 
    141 bar(a);
    142 \end{cfa}
    143 In 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}
    147 forall(T | @CfaEnum(T)@) void bar(T);
    148 
    149 bar(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}).
    152 Being 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
    154 try to resolve it as a @CfaEnum@, rather to insert a @value@ conversion.
    155 
    156 \subsection{Coercion}
    157 While 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 
    162 C auto-initialization works for the integral type @int@ with constant expressions.
    163 \begin{cfa}
    164 enum 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}
    169 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.
    170 
    171 % The notion of auto-initialization is generalized in \CFA enumertation E with base type T in the following way:
    172 When 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}
    185 while @?++( T )@ can be explicitly overloaded or implicitly overloaded with properly defined @one_t@ and @?+?(T, T)@.
    186 
    187 Unfortunately, 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.
    188 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.
    189 Nevertheless, the necessary language concepts exist to support this feature.
     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}
     157enum@()@ Mode { O_RDONLY, O_WRONLY, O_CREAT, O_TRUNC, O_APPEND };
     158Mode mode = O_RDONLY;
     159if ( mode == O_CREAT ) ...
     160bool b = mode == O_RDONLY || mode @<@ O_APPEND; $\C{// disallowed}$
     161int 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}
     172enum(int) Colour { Red, Blue, Green };
     173int w = Red;            $\C[1.5in]{// allowed}$
     174Colour color = 0;       $\C{// disallowed}\CRT$
     175\end{cfa}
     176Unfortunately, there must be one confusing case between C enumerations and \CFA enumeration for type @int@.
     177\begin{cfa}
     178enum Colour { Red = 42, Blue, Green };
     179enum(int) Colour2 { Red = 16, Blue, Green };
     180int w = Redy;           $\C[1.5in]{// 42}\CRT$
     181\end{cfa}
     182Programmer intuition is that the assignment to @w@ is ambiguous.
     183However, converting from @color@ to @int@ is zero cost (no conversion), while from @Colour2@ to @int@ is a safe conversion, which is a higher cost.
     184This 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}
     192enum( const char * ) Name { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
     193Name name = Fred;
     194sout | name | label( name ) | posn( name ) | value( name );
     195FRED Fred 0 FRED
     196\end{cfa}
     197The default meaning for an enumeration variable in an expression is its value.
     198
     199
     200\subsection{Range}
     201
     202The following helper function are used to access and control enumeration ranges (enumerating).
     203
     204The pseudo-function @countof@ (like @sizeof@) provides the size (range) of an enumeration or an enumeration instance.
     205\begin{cfa}
     206enum(int) Colour { Red, Blue, Green };
     207Colour c = Red
     208sout | countof( Colour ) | countof( c );
     2093 3
     210\end{cfa}
     211@countof@ is a pseudo-function because it takes a type as an argument.
     212The function @fromInt@ provides a safe subscript of the enumeration.
     213\begin{cfa}
     214Colour r = fromInt( prng( countof( Colour ) ) ); // select random colour
     215\end{cfa}
     216The functions @lowerBound@, @upperBound@, @succ@, and @pred@ are for enumerating.
     217\begin{cfa}
     218for ( Colour c = lowerBound();; ) {
     219        sout | c | nonl;
     220  if ( c == upperBound() ) break;
     221        c = succ( c );
     222}
     223\end{cfa}
     224Note, the mid-exit loop is necessary to prevent triggering a @succ@ bound check, as in:
     225\begin{cfa}
     226for ( Colour c = lowerBound(); c <= upperBound(); c = succ( c ) ) ... // generates error
     227\end{cfa}
     228When @c == upperBound()@, the loop control still invokes @succ( c )@, which causes an @enumBound@ exception.
     229Finally, there is operational overlap between @countof@ and @upperBound@.
     230
    190231
    191232\section{Enumeration Inheritance}
    192233
    193234\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).
    194 
    195 \begin{cfa}
    196 enum( char * ) Names { /* as above */ };
    197 enum( char * ) Names2 { @inline Names@, Jack = "JACK", Jill = "JILL" };
    198 enum( char * ) Names3 { @inline Names2@, Sue = "SUE", Tom = "TOM" };
    199 \end{cfa}
    200 
    201 Enumeration @Name2@ inherits all the enumerators and their values from enumeration @Names@ by containment, and a @Names@ enumeration is a @subtype@ of enumeration @Name2@.
     235\begin{cfa}
     236enum( const char * ) Names { Fred = "FRED", Mary = "MARY", Jane = "JANE" };
     237enum( const char * ) Names2 { @inline Names@, Jack = "JACK", Jill = "JILL" };
     238enum( const char * ) Names3 { @inline Names2@, Sue = "SUE", Tom = "TOM" };
     239\end{cfa}
     240Enumeration @Name2@ inherits all the enumerators and their values from enumeration @Names@ by containment, and a @Names@ enumeration is a subtype of enumeration @Name2@.
    202241Note, that enumerators must be unique in inheritance but enumerator values may be repeated.
    203242
    … …  
    207246Specifically, the inheritance relationship for @Names@ is:
    208247\begin{cfa}
    209 Names $\(\subset\)$ Names2 $\(\subset\)$ Names3 $\C{// enum type of Names}$
    210 \end{cfa}
    211 
    212 Inlined from \CFA enumeration @O@, new enumeration @N@ copies all enumerators from @O@, including those @O@ obtains through inheritance. Enumerators inherited from @O@
    213 keeps 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}
    215 enum() Phynchocephalia { Tuatara };
    216 enum() Squamata { Snake, Lizard };
    217 enum() Lepidosauromorpha { inline Phynchocephalia, inline Squamata, Kuehneosauridae };
    218 \end{cfa}
    219 Snake, for example, has the position 0 in Squamata, but 1 in Lepidosauromorpha as Tuatara inherited from Phynchocephalia is position 0 in Lepidosauromorpha.
    220 
    221 A subtype enumeration can be casted, or implicitly converted into its supertype, with a safe cost.
    222 \begin{cfa}
    223 enum Squamata squamata_lizard = Lizard;
    224 posn(quamata_lizard); // 1
    225 enum Lepidosauromorpha lepidosauromorpha_lizard = squamata_lizard;
    226 posn(lepidosauromorpha_lizard); // 2
    227 void foo( Lepidosauromorpha l );
    228 foo( squamata_lizard );
    229 posn( (Lepidosauromorpha) squamata_lizard ); // 2
    230 
    231 Lepidosauromorpha s = Snake;
    232 \end{cfa}
    233 The last expression in the preceding example is umabigious. While both @Squamata.Snake@ and @Lepidosauromorpha.Snake@ are valid candidate, @Squamata.Snake@ has
    234 an associated safe cost and \CFA select the zero cost candidate @Lepidosauromorpha.Snake@.
    235 
    236 As discussed in \VRef{s:OpaqueEnum}, \CFA chooses position as a representation of \CFA enum. Conversion involves both change of typing
    237 and possibly @position@.
    238 
    239 When 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}
    247 struct Enumerator;
    248 struct CFAEnum {
    249         vector<variant<CFAEnum, Enumerator>> members;
    250 };
    251 pair<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}
     248Names  $\(\subset\)$  Names2  $\(\subset\)$  Names3  $\C{// enum type of Names}$
     249\end{cfa}
     250A 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}
     252Names fred = Names.Fred;
     253(Names2)fred;   (Names3)fred;   (Names3)Names2.Jack;  $\C{// cast to super type}$
     254Names2 fred2 = fred;   Names3 fred3 = fred2;    $\C{// assign to super type}$
     255\end{cfa}
     256As well, there is the implicit cast to an enumerator's base-type.
     257\begin{cfa}
     258const char * name = fred;
     259\end{cfa}
    273260For the given function prototypes, the following calls are valid.
    274261\begin{cquote}
    … …  
    291278Note, 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.
    292279
     280
    293281\section{Enumerator Control Structures}
    294282
    … …  
    296284In most programming languages, an enumerator is implicitly converted to its value (like a typed macro substitution).
    297285However, enumerator synonyms and typed enumerations make this implicit conversion to value incorrect in some contexts.
    298 In these contexts, a programmer's intuition assumes an implicit conversion to position.
     286In these contexts, a programmer's initition assumes an implicit conversion to position.
    299287
    300288For 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

    rce02877 r1661ad7  
    5151        int va[r];
    5252}
     53
     54
    5355\end{clang}
    5456\end{tabular}
    … …  
    5759Dynamically initialized identifiers may appear in initialization and array dimensions in @g++@, which allows variable-sized arrays on the stack.
    5860Again, this form of aliasing is not an enumeration.
     61
    5962
    6063\section{C Enumeration}
    … …  
    154157Hence, initialization in the range @INT_MIN@..@INT_MAX@ is 4 bytes, and outside this range is 8 bytes.
    155158
     159
    156160\subsection{Usage}
    157161\label{s:Usage}
    … …  
    217221\bigskip
    218222While 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}
    222 Function 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
    223 with different entities as long as they are different in terms of the number and type of parameters.
    224 
    225 \begin{cfa}
    226 void f(); // (1)
    227 void f(int); // (2); Overloaded on the number of parameters
    228 void f(char); // (3); Overloaded on parameter type
    229 
    230 f('A');
    231 \end{cfa}
    232 In this case, the name f is overloaded with a nullity function and two arity functions with different parameters types. Exactly which precedures being executed
    233 is 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).
    234 Between 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
    235 and procedure (3) is being executed.
    236 
    237 \begin{cfa}
    238 int f(int); // (4); Overloaded on return type
    239 [int, int] f(int); // (5) Overloaded on the number of return value
    240 \end{cfa}
    241 The 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}
    245 Operators 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}
    248 enum Weekday { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };
    249 bool ?<?(const Weekday a, const Weekday b) {
    250         return ((int)a + 1);
    251 }
    252 Monday < Sunday; // False
    253 ?<?( Monday, Sunday ); // Equivalent syntax
    254 \end{cfa}
    255 Unary operators are functions that takes one argument and have name @operator?@ or @?operator@, where @?@ is the placeholders for operands.
    256 Binary operators are function with two parameters. They are overloadable with function name @?operator?@.
    257 
    258 \subsection{Constructor and Destructor}
    259 In \CFA, all objects are initialized by @constructors@ during its allocation, including basic types,
    260 which are initialized by auto-generated basic type constructors.
    261 
    262 Constructors are overloadable functions with name @?{}@, return @void@, and have at least one parameter, which is a reference
    263 to the object being constructored (Colloquially referred to "this" or "self" in other language).
    264 
    265 \begin{cfa}
    266 struct Employee {
    267         const char * name;
    268         double salary;
    269 };
    270 
    271 void ?{}( Employee& this, const char * name, double salary ) {
    272     this.name = name;
    273     this.salary = salary;
    274 }
    275 
    276 Employee Sara { "Sara Schmidt", 20.5 };
    277 \end{cfa}
    278 Like Python, the "self" reference is implicitly passed to a constructor. The Employee constructors takes two additional arugments used in its
    279 field initialization.
    280 
    281 A destructor in \CFA is a function that has name @^?{}@. It returns void, and take only one arugment as its "self".
    282 \begin{cfa}
    283 void ^?{}( Employee& this ) {
    284     free(this.name);
    285     this.name = 0p;
    286     this.salary = 0;
    287 }
    288 \end{cfa}
    289 Destructor 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{};
    293 Sara{ "Sara Craft", 20 };
    294 } // ^Sara{}
    295 \end{cfa}
    296 
    297 \subsection{Variable Overloading}
    298 C 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
    299 a 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
    302 happens when the inner scope variable and the outer scope ones have the same type.
    303 \begin{cfa}
    304 double i = 6.0;
    305 int i = 5;
    306 void foo( double i ) { sout | i; } // 6.0
    307 \end{cfa}
    308 
    309 \subsection{Special Literals}
    310 Literal 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),
    311 or an initial state.
    312 Awaring 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}
    314 struct S { int i, j; };
    315 void ?{}( S & this, @zero_t@ ) { this.i = 0; this.j = 0; } // zero_t, no parameter name allowed
    316 S s0 = @0@;
    317 \end{cfa}
    318 Overloading @zero_t@ for S provides new definition for @zero@ of type S.
    319 
    320 According 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
    321 such 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}
    325 int ?@!=@?( 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}
    336 Literal 1 is also special. Particularly in C, the pre-increment operator and post-increment operator can be interpreted in terms of @+= 1@.
    337 The logical @1@ in \CFA is represented by special type @one_t@.
    338 \begin{cfa}
    339 void ?{}( S & this, one_t ) { this.i = 1; this.j = 1; } // one_t, no parameter name allowed
    340 S & ?+=?( S & this, one_t ) { this.i += 1; this.j += 1; return op; }
    341 \end{cfa}
    342 Without 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}
    345 Parametric-Polymorphics functions are the functions that applied to all types. \CFA functions are parametric-polymorphics when
    346 they are written with the @forall@ clause.
    347 
    348 \begin{cfa}
    349 forall(T)
    350 T identity(T x) { return x; }
    351 identity(42);
    352 \end{cfa}
    353 The identity function accepts a value from any type as an arugment, and the type parameter @T@ is bounded to @int@ when the function
    354 is called with 42.
    355 
    356 The forall clause can takes @type assertions@ that restricts the polymorphics type.
    357 \begin{cfa}
    358 forall( T | { void foo(T); } )
    359 void bar(T t) { foo(t); }
    360 
    361 struct S {} s;
    362 void foo(struct S);
    363 
    364 bar(s);
    365 \end{cfa}
    366 The assertion on @T@ restricts the range of types for bar to only those implements foo with the matching a signature, so that bar()
    367 can call @foo@ in its body with type safe.
    368 Calling on type with no mathcing @foo()@ implemented, such as int, causes a compile time type assertion error.
    369 
    370 A @forall@ clause can asserts on multiple types and with multiple asserting functions. A common practice in \CFA is to group
    371 the asserting functions in to a named @trait@ .
    372 
    373 \begin{cfa}
    374 trait Bird(T) {
    375         int days_can_fly(T i);
    376         void fly(T t);
    377 };
    378 
    379 forall(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 
    387 struct Robin {} r;
    388 int days_can_fly(Robin r) { return 23; }
    389 void fly(Robin r) {}
    390 
    391 bird_fly( r );
    392 \end{cfa}
    393 
    394 Grouping type assertions into named trait effectively create a reusable interface for parametrics polymorphics types.
    395 
    396 \section{Expression Resolution}
    397 
    398 The overloading feature poses a challenge in \CFA expression resolution. Overloadeded identifiers can refer multiple
    399 candidates, with multiples being simultaneously valid. The main task of \CFA resolver is to identity a best candidate that
    400 involes less implicit conversion and polymorphism.
    401 
    402 \subsection{Conversion Cost}
    403 \label{s:ConversionCost}
    404 In C, function call arguments and function parameters do not need to be a exact match. When types mismatch, C performs an \newterm{implicit conversion}
    405 on argument to parameter type. The process is trivial with the exception on binary operators;  When types of operands are different,
    406 C nees to decide which operands need implicit conversion. C defines the resolution pattern as "usual arithmetic conversion",
    407 in which C looks for a \newterm{common type} between operands, and convert either one or both operands to the common type.
    408 Loosely 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.
    409 Such conversion is called "widening" or "safe conversion".
    410 
    411 C binary operators can be restated as 2-arity functions that overloaded with different parameters. "Usual arithmetic conversion" is to find a overloaded
    412 instance 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,
    417 and @safe@ is sum of degree of safe (widening) conversion.
    418 Sum of degree is a method to quantify C's integer and floating-point rank.
    419 Every pair of widening conversion types has been assigned with a \newterm{distance}, and distance between the two same type is 0.
    420 For 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.
    421 The 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.
    423 Among 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
    424 a candidate with the lowest @unsafe@ if possible.
    425 
    426 Assume the overloaded function @foo@ is called with two @int@ parameter. The cost for every overloaded @foo@ has been list along:
    427 \begin{cfa}
    428 void foo(char, char);                           // (2, 0, 0)
    429 void foo(char, int);                            // (1, 0, 0)
    430 forall(T, V) void foo(T, V);            // (0, 2, 0)
    431 forall(T)        void foo(T, T);                // (0, 2, 0)
    432 forall(T)        void foo(T, int);              // (0, 1, 0)
    433 void foo(long long, long);                      // (0, 0, 3)
    434 void foo(long, long);                           // (0, 0, 2)
    435 void foo(int, long);                            // (0, 0, 1)
    436 
    437 int i, j; foo(i, j);
    438 \end{cfa}
    439 The overloaded instances are ordered from the highest to the lowest cost, and \CFA select the last candidate.
    440 
    441 In 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)@@.
    443 with 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}
    453 The 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@
    455 makes 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
    456 restrictions 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
    460 there 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

    rce02877 r1661ad7  
    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,
    7 and therefore \CFA enumerations fulfills the type assertions with the combination.
    8 With the observation, we define trait @CfaEnum@:
     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@.
     8A \CFA enumeration satisfies all of these traits allowing it to interact with runtime features in \CFA.
     9Each trait is discussed in detail.
     10
     11The trait @CfaEnum@:
    912\begin{cfa}
    1013forall( E ) trait CfaEnum {
    … …  
    1316};
    1417\end{cfa}
    15 
    16 % The trait @TypedEnum@ extends @CfaEnum@ with an additional value() assertion:
    17 Typed enumerations are \CFA enumeration with an additional @value@ attribute. Extending
    18 CfaEnum traits, TypedEnum is a subset of CFAEnum that implements attribute function @value()@,
    19 which includes all typed enumerations.
     18asserts an enumeration type @E@ has named enumerator constants (@label@) with positions (@posn@).
     19
     20The trait @TypedEnum@ extends @CfaEnum@:
    2021\begin{cfa}
    2122forall( E, V | CfaEnum( E ) ) trait TypedEnum {
    … …  
    2324};
    2425\end{cfa}
    25 Type parameter V of TypedEnum trait binds to return type of @value()@, which is also the base
    26 type for typed enumerations. CfaEnum and TypedEnum triats constitues a CfaEnum function interfaces, as well a way to define functions
    27 over 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
    30 forall(  E, T | TypedEnum( E, T ) | { ?{}(string &, T ); } )
    31 string format_enum( E e ) { return label(E) + "(" + string(value(e)) + ")"; }
    32 
    33 // int is convertible to string; implemented in the standard library
    34 enum(int) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF };
    35 
    36 struct 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);
     26asserting an enumeration type @E@ can have homogeneous enumerator values of type @V@.
     27
     28The declarative syntax
     29\begin{cfa}
     30enum(T) E { A = ..., B = ..., C = ... };
     31\end{cfa}
     32creates an enumerated type E with @label@, @posn@ and @value@ implemented automatically.
     33\begin{cfa}
     34void foo( T t ) { ... }
     35void 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        }
    4041}
    41 enum(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 
    46 format_enum(RGB.Green); // "Green(65280)"
    47 format_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.
    53 Types does not need be defined as \CFA enumerations to work with CfaEnum traits. CfaEnum applies to any type
    54 with @label()@ and @value()@ being properly defined.
    55 Here is an example on how to extend a C enumeration to comply CfaEnum traits:
    56 \begin{cfa}
    57 enum Fruit { Apple, Banana, Cherry };                   $\C{// C enum}$
     42\end{cfa}
     43
     44Implementing general functions across all enumeration types is possible by asserting @CfaEnum( E, T )@, \eg:
     45\begin{cfa}
     46#include <string.hfa>
     47forall( E, T | CfaEnum( E, T ) | {unsigned int toUnsigned(T)} )
     48string formatEnum( E e ) {
     49        unsigned int v = toUnsigned( value( e ) );
     50        string out = label(e) + '(' + v +')';
     51        return out;
     52}
     53formatEnum( Week.Mon );
     54formatEnum( RGB.Green );
     55\end{cfa}
     56
     57\CFA does not define attribute functions for C-style enumeration.
     58But it is possible for users to explicitly implement enumeration traits for C enum and any other types.
     59\begin{cfa}
     60enum Fruit { Apple, Pear, Cherry };                     $\C{// C enum}$
    5861const char * label( Fruit f ) {
    59         choose( f ) {
     62        choose ( f ) {
    6063                case Apple: return "Apple";
    61                 case Banana: return "Banana";
     64                case Bear: return "Pear";
    6265                case Cherry: return "Cherry";
    6366        }
    6467}
    65 unsigned posn( Fruit f ) { return f; }
    66 char value( Fruit f ) {
    67         choose(f)  {
    68                 case Apple: return 'a';
    69                 case Banana: return 'b';
    70                 case Cherry: return 'c';
    71         }
    72 }
    73 
    74 format_enum(Cherry); // "Cherry(c)"
    75 \end{cfa}
    76 
    77 \subsection{Bounded and Serial}
    78 A bounded type defines a lower bound and a upper bound.
     68unsigned posn( Fruit f ) { return f; }
     69const char * value( Fruit f ) { return ""; } $\C{// value can return any non void type}$
     70formatEnum( Apple );                                            $\C{// Fruit is now a \CFA enum}$
     71\end{cfa}
     72
     73A 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}
     79enum@()@ Planets { MERCURY, VENUS, EARTH, MARS, JUPITER, SATURN, URANUS, NEPTUNE };
     80\end{cfa}
     81
     82
     83In addition, \CFA implements @Bound@ and @Serial@ for \CFA enumerations.
    7984\begin{cfa}
    8085forall( E ) trait Bounded {
    81         E lowerBound();
    82         E lowerBound();
    83 };
    84 
    85 \end{cfa}
    86 Both Bounded functions are implement for \CFA enumerations, with @lowerBound()@ returning the first enumerator and @upperBound()@ returning
    87 the last enumerator.
    88 \begin{cfa}
    89 Workday day = lowerBound();                                     $\C{// Mon}$
    90 Planet outermost = upperBound();                                $\C{// NEPTUNE}$
    91 \end{cfa}
    92 
    93 The lowerBound() and upperBound() are functions overloaded on return type only, means their type resolution solely depend on the outer context,
    94 including expected type as a function argument, or the left hand size of an assignment expression.
    95 Calling either function without a context results in a type ambiguity, except in the rare case where the type environment has only one
    96 type 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}$
    99 sout | @lowerBound()@;
    100 Workday day = first();          $\C{// day provides type Workday}$
     86        E first();
     87        E last();
     88};
     89\end{cfa}
     90The function @first()@ and @last()@ of enumerated type E return the first and the last enumerator declared in E, respectively. \eg:
     91\begin{cfa}
     92Workday day = first();                                  $\C{// Mon}$
     93Planet 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.
     96Calling 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}$
     99sout | @last()@;
     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 @Serial@ is a subset of @Bounded@, with functions maps elements against integers, as well implements a sequential order between members.
     102foo( last() );                                                  $\C{// argument provides type Planet}$
     103\end{cfa}
     104
     105The trait @Serial@:
    106106\begin{cfa}
    107107forall( E | Bounded( E ) ) trait Serial {
    108108        unsigned fromInstance( E e );
    109         E fromInt( unsigned int i );
     109        E fromInt( unsigned int posn );
    110110        E succ( E e );
    111111        E pred( E 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.
    117 Function @fromInstance()@ projects a @Bounded@ member to a number and @fromInt@ is the inverser. Function @succ()@ take an element, returns the "next"
    118 member in sequential order and @pred()@ returns the "last" member.
    119 
    120 A 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}.
    121 Calling @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.
    124 Unlike a cast, conversion between \CFA enumeration and integer with @Serial@ interface is type safe.
    125 Specifically for @fromInt@, \CFA abort if input i smaller than @fromInstance(lowerBound())@ or greater than @fromInstance(upperBound())@
    126 
    127 Function @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
    129 an 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}
    133 enum RGB {Red, Green, Blue};
    134 countof( RGB ); // (1)
    135 countof( Red ); // (2)
    136 \end{cfa}
    137 Both 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
    139 a 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 {... }@.
    142 If 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)@.
    144 If 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 
    150 With the @Bounded@ and @Serial@, a loop over enumeration can be implemented in the following ways:
    151 \begin{cfa}
    152 enum() E { ... }
    153 for( unsigned i = 0; i < countof(E); i++ ) { ... }
    154 for( E e = lowerBound(); ; e = succ(e) ) { ...; if (e == upperBound()) break; }
    155 
    156 forall( 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}
     112};
     113\end{cfa}
     114is a @Bounded@ trait, where elements can be mapped to an integer sequence.
     115A 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.
     117The mapping from a serial type to integer is defined by @fromInstance@, which returns the enumerator's position.
     118The inverse operation is @fromInt@, which performs a bound check using @first()@ and @last()@ before casting the integer into an enumerator.
     119Specifically, 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
     121The @succ( E e )@ and @pred( E e )@ imply the enumeration positions are consecutive and ordinal.
     122Specifically, 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()$.
     123The exception @enumRange@ is raised if the result of either operation is outside the range of type @E@.
    161124
    162125Finally, there is an associated trait defining comparison operators among enumerators.
    … …  
    193156
    194157
     158\section{Enumeration Variable}
     159
     160Although \CFA enumeration captures three different attributes, an enumeration instance does not store all this information.
     161The @sizeof@ a \CFA enumeration instance is always 4 bytes, the same size as a C enumeration instance (@sizeof( int )@).
     162It comes from the fact that:
     163\begin{enumerate}
     164\item
     165a \CFA enumeration is always statically typed;
     166\item
     167it is always resolved as one of its attributes regarding real usage.
     168\end{enumerate}
     169When creating an enumeration instance @colour@ and assigning it with the enumerator @Color.Green@, the compiler allocates an integer variable and stores the position 1.
     170The invocations of $positions()$, $value()$, and $label()$ turn into calls to special functions defined in the prelude:
     171\begin{cfa}
     172position( green );
     173>>> position( Colour, 1 ) -> int
     174value( green );
     175>>> value( Colour, 1 ) -> T
     176label( 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.
     180These 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}
     186enum(T) E { ... };
     187// backing data
     188T * E_values;
     189char ** E_labels;
     190\end{cfa}
     191Storing values and labels as arrays can sometimes help support enumeration features.
     192However, 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}
     204An \CFA enumeration with base type T can be used seamlessly as T, without explicitly calling the pseudo-function value.
     205\begin{cfa}
     206char * 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}
     215T_2 Foo(T1);
     216\end{cfa}
     217The @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
     227For 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
     232The 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
     240For @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}
     247char * green = "Green";
     248Colour green = Colour.Green; // "G"
     249
     250void bar(char * s) { return s; }
     251void foo(Colour c) { return value( c ); }
     252
     253foo( green ); // "G"
     254bar( 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}
     259Similarly, 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}
     261Colour green = Colour.Green;
     262void foo(Colour c) { sout | "It is an enum"; } // First foo
     263void foo(char * s) { sout | "It is a string"; } // Second foo
     264foo( green ); // "It is an enum"
     265\end{cfa}
     266Because @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}
     269The 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}
     272int s1;
     273\end{cfa}
     274The 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
     410An 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
     415A 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
     420C auto-initialization works for the integral type @int@ with constant expressions.
     421\begin{cfa}
     422enum 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}
     427The 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
     429The notion of auto-initialization can be generalized in \CFA through the trait @AutoInitializable@.
     430\begin{cfa}
     431forall(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}
     437In addition, there is an implicit enumeration counter, @ecnt@ of type @T@, managed by the compiler.
     438For example, the type @Odd@ satisfies @AutoInitializable@:
     439\begin{cfa}
     440struct Odd { int i; };
     441void ?{}( Odd & o, int v ) { if ( v & 1 ) o.i = v; else /* error not odd */ ; };
     442void ?{}( Odd & o, zero_t ) { o.i = 1; };
     443Odd ?++( Odd o ) { return (Odd){ o.i + 2 }; };
     444\end{cfa}
     445and implicit initialization is available.
     446\begin{cfa}
     447enum( Odd ) { A, B, C = 7, D };                 $\C{// 1, 3, 7, 9}$
     448\end{cfa}
     449where the compiler performs the following transformation and runs the code.
     450\begin{cfa}
     451enum( Odd ) {
     452        ?{}( ecnt, @0@ }  ?{}( A, ecnt },       ?++( ecnt )  ?{}( B, ecnt ),
     453        ?{}( ecnt, 7 )  ?{}( C, ecnt ), ?++( ecnt )  ?{}( D, ecnt )
     454};
     455\end{cfa}
     456
     457Unfortunately, auto-initialization is not implemented because \CFA is only a transpiler, relying on generated C code to perform the detail work.
     458C 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.
     459Nevertheless, the necessary language concepts exist to support this feature.
     460
     461
     462\section{Enumeration Features}
     463
     464
    195465\section{Iteration and Range}
    196466
    … …  
    273543for ( char * ch; labels( Alphabet ) )
    274544\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]
     560enum( char * ) Name { Jack = "Jack", Jill = "Jill" };
     561enum /* 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]
     565Name Fred;
     566void f( Name2 );
     567f( Fred );
     568\end{cfa}
     569If enumeration A declares @inline B@ in its enumeration body, enumeration A is the "inlining enum" and enumeration B is the "inlined enum".
     570
     571An 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]
     573enum /* 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}
     576Name.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]
     578with( 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]
     585enum( char * ) Colour {
     586        Red = "red", Blue = "blue", Green = "green"
     587};
     588\end{cfa}
     589An 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]
     593Colour c;
     594...
     595value( c ); // or c
     596\end{cfa}
     597An 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]
     602const char * Colour_labels [3] = { "Red", "Blue", "Green" };
     603const char * Colour_values [3] = { "red", "blue", "green" };
     604\end{cfa}
     605The \CFA compiles transforms the attribute expressions into array access.
     606\begin{cfa}[label=lst:attr_array_access]
     607position( c ) // c; an integer
     608value( c ); // Colour_values[c]
     609label( c ); // Colour_labels[c]
     610\end{cfa}
     611
     612To 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]
     617forall( 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
     627The 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]
     629forall(T)
     630class EnumDecl {
     631        T* values;
     632        char** label;
     633};
     634\end{cfa}
     635
     636The internal representation of an enumeration constant is @EnumInstType@.
     637An @EnumInstType@ has a reference to the \CFA-enumeration declaration and the position of the enumeration constant.
     638\begin{cfa}[label=lst:EnumInstType]
     639class EnumInstType {
     640        EnumDecl enumDecl;
     641        int position;
     642};
     643\end{cfa}
     644In 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]
     647const T * const values;
     648const char * label;
     649int length;
     650\end{cfa}
     651Companion 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".
     652Companion 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)}
     685Not sure its semantics yet, and it might replace a companion object.
     686\begin{cfa}[label=lst:companion_trait]
     687forall(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}
     695All 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}
     703enum(int) Weekday {
     704        Mon = 10, Tue, ...
     705};
     706
     707T value( enum Weekday<T> & this);
     708int position( enum Weekday<T> & this )
     709char * label( enum Weekday<T> & this )
     710
     711trait Companion obj = (enum(int)) Workday.Weekday;
     712value(obj); // 10
     713\end{cfa}
     714The 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
     719Companion objects make extending features for \CFA enumeration easy.
     720\begin{cfa}[label=lst:companion_user_definition]
     721char * charastic_string( Companion o, int position ) {
     722        return sprintf( "Label: %s; Value: %s", label( o, position ), value( o, position) );
     723}
     724printf( charactic_string ( Color, 1 ) );
     725>>> Label: Green; Value: G
     726\end{cfa}
     727Defining a function takes a Companion object effectively defines functions for all \CFA enumeration.
     728
     729The \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.
     730Therefore, a user can use the syntax with a user-defined enumeration function call:
     731\begin{cfa}[label=lst:companion_user_definition]
     732charactic_string( Color.Green ); // equivalent to charactic_string( Color, 1 )
     733>>> Label: Green; Value: G
     734\end{cfa}
     735Similarly, the user can work with the enumeration type itself: (see section ref...)
     736\begin{cfa}[ label=lst:companion_user_definition]
     737void print_enumerators ( Companion o ) {
     738        for ( c : Companion o ) {
     739                sout | label (c) | value( c ) ;
     740        }
     741}
     742print_enumerators( Colour );
     743\end{cfa}
     744
     745
     746\section{Declaration}
     747
     748The qualified enumeration syntax is dedicated to \CFA enumeration.
     749\begin{cfa}[label=lst:range_functions]
     750enum (type_declaration) name { enumerator = const_expr, enumerator = const_expr, ... }
     751\end{cfa}
     752A compiler stores the name, the underlying type, and all enumerators in an @enumeration table@.
     753During the $Validation$ pass, the compiler links the type declaration to the type's definition.
     754It 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.
     755If the declared type is not @AutoInitializable@, \CFA rejects the enumeration definition.
     756Otherwise, 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]
     759struct T { ... };
     760void ?{}( T & t, zero_t ) { ... };
     761void ?{}( T & t, one_t ) { ... };
     762T ?+?( T & lhs, T & rhs ) { ... };
     763
     764enum (T) Sample {
     765        Zero: 0 /* zero_t */,
     766        One: Zero + 1 /* ?+?( Zero, one_t ) */ , ...
     767};
     768\end{cfa}
     769Challenge: \\
     770The value of an enumerator, or the initializer, requires @const_expr@.
     771While 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.
     772Might 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]
     776Companion( 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.
     783But 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]
     789aggregation_name.field;
     790\end{cfa}
     791The qualified expression is not dedicated to \CFA enumeration.
     792It is a feature that is supported by other aggregation in \CFA as well, including a C enumeration.
     793When 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.
     795If 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]
     801enum Sample s1;
     802\end{cfa}
     803
     804The 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

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