Ignore:
Timestamp:
Aug 6, 2024, 11:09:05 PM (4 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
d7cb0f7
Parents:
bd686f0
Message:

proofread trait chapter

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/jiada_liang_MMath/trait.tex

    rbd686f0 r8cb2ff6  
    22\label{c:trait}
    33
    4 % Despite parametric polymorphism being a pivotal feature of \CFA, for a long time, there was not
    5 % a technique to write functions being polymorphic over enumerated types.
    6 \CC introduced @std::is_enum@ trait on \CC{11} and @concepts@ on \CC{20}; with the combination, users can
    7 write function polymorphic over enumerated type in \CC:
    8 \begin{cfa}
     4\CC introduced the @std::is_enum@ trait in \CC{11} and concept feature in \CC{20}.
     5With this combination, it is possible to write a polymorphic function over an enumerated type.
     6\begin{c++}
    97#include <type_traits>
    10 
    11 template<typename T>
    12 @concept Enumerable = std::is_enum<T>::value;@
    13 
    14 template<@Enumerable@ T>
    15 void f(T) {}
    16 \end{cfa}
    17 The @std::is_enum@ and other \CC @traits@ are a compile-time interfaces to query type information.
    18 While named the same as @trait@, it is orthogonal to \CFA trait, as the latter being defined as
    19 a collection of assertion to be satisfied by a polymorphic type.
    20 
    21 \CFA provides @CfaEnum@ and @TypedEnum@ traits to supports polymorphic functions for \CFA enumeration:
    22 \begin{cfa}
    23 forall(T | @CfaEnum(T)@)
    24 void f(T) {}
    25 \end{cfa}
    26 
    27 \section{CfaEnum and TypedEnum}
    28 \CFA defines attribute functions @label()@ and @posn()@ for all \CFA enumerations,
    29 and therefore \CFA enumerations fulfills the type assertions with the combination.
    30 With the observation, we define trait @CfaEnum@:
     8template<typename T>  @concept Enumerable@  =  std::is_enum<T>::value;
     9template<@Enumerable@ E>  E  f( E e ) { $\C{// constrainted type}$
     10        E w = e;                                                        $\C{// alloction and copy}$
     11        cout << e << ' ' << w << endl;          $\C{// value}$
     12        return w;                                                       $\C{// copy}$
     13}
     14int main() {
     15        enum E { A = 42, B, C } e = C;
     16        e = f( e );
     17}
     1844 44
     19\end{c++}
     20The @std::is_enum@ and other \CC @traits@ are a compile-time interfaces to query type information.
     21While named the same as @trait@ in other programming languages, it is orthogonal to the \CFA trait, with the latter being defined as a collection of assertion to be satisfied by a polymorphic type.
     22
     23The following sections cover the underlying implementation features I created to generalize and restrict enumerations in the \CFA type-system using the @trait@ mechanism.
     24
     25
     26\section{Traits \lstinline{CfaEnum} and \lstinline{TypedEnum}}
     27
     28Traits @CfaEnum@ and @TypedEnum@ define the enumeration attributes: @label@, @posn@, @value@, and @Countof@.
     29These traits support polymorphic functions for \CFA enumeration, \eg:
     30\begin{cfa}
     31forall( E ) | @CfaEnum( E )@ )
     32void f( E e ) {
     33        // access enumeration properties for e
     34}
     35\end{cfa}
     36
     37Trait @CfaEnum@ defines attribute functions @label@ and @posn@ for all \CFA enumerations, and internally \CFA enumerations fulfills this assertion.
    3138\begin{cfa}
    3239forall( E ) trait CfaEnum {
    … …  
    3542};
    3643\end{cfa}
    37 
    38 % The trait @TypedEnum@ extends @CfaEnum@ with an additional value() assertion:
    39 Typed enumerations are \CFA enumeration with an additional @value@ attribute. Extending
    40 CfaEnum traits, TypedEnum is a subset of CFAEnum that implements attribute function @value()@,
    41 which includes all typed enumerations.
     44This trait covers opaque enumerations that do not have an explicit @value@.
     45
     46The trait @TypedEnum@ extends @CfaEnum@ with the @value@ assertion for typed enumerations.
    4247\begin{cfa}
    4348forall( E, V | CfaEnum( E ) ) trait TypedEnum {
    … …  
    4550};
    4651\end{cfa}
    47 Type parameter V of TypedEnum trait binds to return type of @value()@, which is also the base
    48 type for typed enumerations. CfaEnum and TypedEnum triats constitues a CfaEnum function interfaces, as well a way to define functions
    49 over all CfaEnum enumerations.
    50 \begin{cfa}
    51 // for all type E that implements value() to return type T, where T is a type that convertible to string
    52 forall(  E, T | TypedEnum( E, T ) | { ?{}(string &, T ); } )
    53 string format_enum( E e ) { return label(E) + "(" + string(value(e)) + ")"; }
    54 
    55 // int is convertible to string; implemented in the standard library
    56 enum(int) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF };
    57 
    58 struct color_code { int R; int G; int B };
    59 // Implement color_code to string conversion
    60 ?{}(string & this, struct color_code p ) {
    61         this = string(p.R) + ',' + string(p.G) + ',' + string(p.B);
    62 }
     52Here, the associate type-parameter @V@ is the base type of the typed enumeration, and hence, the return type of @value@.
     53These two traits provide a way to define functions over all \CFA enumerations.
     54
     55For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows a generalized enumeration formatter for any enumeration type.
     56The formatter prints an enumerator name and its value in the form @"label( value )"@.
     57The trait for @format_enum@ requires a function named @str@ for printing the value (payload) of the enumerator.
     58Hence, enumeration defines how its value appear and @format_enum@ displays this value within the label name.
     59
     60\begin{figure}
     61\begin{cfa}
     62forall( @E, V | TypedEnum( E, V )@ | { string str( V ); } ) $\C{// format any enumeration}$
     63string format_enum( E e ) {
     64        return label( e ) + '(' + str( value( e ) ) + ')'; $\C{// "label( value )"}$
     65}
     66enum(size_t) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF };
     67// string library has conversion function str from size_t to string
     68
     69struct color_code { int R, G, B; };
    6370enum(color_code) Rainbow {
    64         Red = {255, 0, 0}, Orange = {255, 127, 0}, Yellow = {255, 255, 0}, Green = {0, 255, 0},
    65         Blue = {0, 0, 255}, Indigo = {75, 0, 130}, Purple = {148, 0, 211}
    66 };
    67 
    68 format_enum(RGB.Green); // "Green(65280)"
    69 format_enum(Rainbow.Green); // "Green(0,255,0)"
    70 \end{cfa}
    71 
    72 
    73 % Not only CFA enumerations can be used with CfaEnum trait, other types that satisfy
    74 % CfaEnum assertions are all valid.
    75 Types does not need be defined as \CFA enumerations to work with CfaEnum traits. CfaEnum applies to any type
    76 with @label()@ and @value()@ being properly defined.
    77 Here is an example on how to extend a C enumeration to comply CfaEnum traits:
    78 \begin{cfa}
    79 enum Fruit { Apple, Banana, Cherry };                   $\C{// C enum}$
    80 const char * label( Fruit f ) {
    81         choose( f ) {
    82                 case Apple: return "Apple";
    83                 case Banana: return "Banana";
    84                 case Cherry: return "Cherry";
    85         }
    86 }
    87 unsigned posn( Fruit f ) { return f; }
    88 char value( Fruit f ) {
    89         choose(f)  {
    90                 case Apple: return 'a';
    91                 case Banana: return 'b';
    92                 case Cherry: return 'c';
    93         }
    94 }
    95 
    96 format_enum(Cherry); // "Cherry(c)"
    97 \end{cfa}
    98 
    99 \section{Discussion: Static Type Information}
    100 @CfaEnum@ and @TypedEnum@ are approximations to \CFA Enumerations and Typed Enumerations: they are not
    101 assertions on a type being an enumerated type,
    102 but rather types being shared an interfaces with \CFA enumerations.
    103 \CC's @type_traits@ is fundamentally different than \CFA's traits: \CC's @type_traits@ are descriptions
    104 of compile time type information
    105 \footnote{Concepts can check if a \CC class implement a certain method,
    106 but it is to probe a static type information of a class having a such member.}
    107 , while \CFA's trait describe how a type can be used,
    108 which is a closer paradigm to a trait system in languages such as Scala and Rust.
    109 However, Scala and Rust's traits are nominative:
    110 a type explicitly declare a named traits to be of its type; while in \CFA,
    111 type implements all functions declares in a trait to implicitly be of the trait type.
    112 
    113 If to support static type information, \CFA needs new piece of syntax to distinguish static type
    114 query from function calls, for example:
    115 \begin{cfa}
    116 forall(T | { T::is_enum; });
    117 \end{cfa}
    118 When to call a polymorphic function @foo(T)@ with assertions set @S@ and function call argument @a@, \CFA
    119 determines if there is an overloaded name @a@ that has non-zero conversion cost to all assertions in @S@.
    120 As a consequence, @is_enum@ can be a \CFA directive that immediately trim down the search space of @a@ to
    121 be some enumerated types. In fact, because \CFA stores symbols maps to enumeration in a standalone data structure.
    122 Limiting search space to enumeration improve on \CFA resolution speed.
    123 
    124 While assertion on static type information seems improvement on expressivity, it is a challenge to
    125 extend its capability without a fully functional pre-processsor that evaluate constant expression as \CC
    126 compilers does. The described @is_enum@ manipulate compiler behaviour, which cannot be easily extended to
    127 other usage cases. Therefore, \CFA currently does not support @is_enum@ and utalizes traits as a workaround.
     71        Red = {255, 0, 0}, Orange = {255, 127, 0}, Yellow = {255, 255, 0}, Green = {0, 255, 0}, // ...
     72};
     73string str( color_code cc ) with( cc ) {        $\C{// format payload, "ddd,ddd,ddd"}$
     74        return str( R ) + ',' + str( G ) + ',' + str( B ); $\C{// "R,G,B"}$
     75}
     76int main() {
     77        sout | format_enum( RGB.Green );                $\C{// "Green(65280)"}$
     78        sout | format_enum( Rainbow.Green );    $\C{// "Green(0,255,0)"}$
     79}
     80\end{cfa}
     81\caption{Generalized Enumeration Formatter}
     82\label{f:GeneralizedEnumerationFormatter}
     83\end{figure}
     84
     85Other types may work with traits @CfaEnum@ and @TypedEnum@, by supplying appropriate @label@, @posn@, and @value@ functions.
     86For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} extends a (possibly predefined) C enumeration to work with all the \CFA extensions.
     87
     88\begin{figure}
     89\begin{cfa}
     90enum Fruit { Apple, Banana, Cherry };           $\C{// C enum}$
     91const char * @label@( Fruit f ) {
     92        static const char * labels[] = { "Apple", "Banana", "Cherry" };
     93        return labels[f];
     94}
     95int @posn@( Fruit f ) { return f; }
     96int @value@( Fruit f ) {
     97        static const char values[] = { 'a', 'b', 'c' };
     98        return values[f];
     99}
     100sout | format_enum( Cherry );                           $\C{// "Cherry(c)"}$
     101\end{cfa}
     102\caption{Generalized Enumeration Formatter}
     103\label{f:GeneralizedEnumerationFormatter}
     104\end{figure}
     105
     106
     107\section{Discussion: Genericity}
     108
     109At the start of this chapter, the \CC concept is introduced to constraint template types, \eg:
     110\begin{c++}
     111concept Enumerable = std::is_enum<T>::value;
     112\end{c++}
     113Here, @concept@ is referring directly to types with kind @enum@;
     114other @concept@s can refer to all types with kind @int@ with @long@ or @long long@ qualifiers, \etc.
     115Hence, the @concept@ is a first level of restriction allowing only the specified kinds of types and rejecting others.
     116The template expansion is the second level of restriction verifying if the type passing the @concept@ test provides the necessary functionality.
     117Hence, a @concept@ is querying precise aspects of the programming language set of types.
     118
     119Alternatively, languages using traits, like \CFA, Scala, Go, and Rust, are defining a restriction based on a set of operations, variables, or structure fields that must exist to match with usages in a function or aggregate type.
     120Hence, the \CFA enumeration traits never connected with the specific @enum@ kind.
     121Instead, anything that can look like the @enum@ kind is considered an enumeration (duck typing).
     122However, Scala, Go, and Rust traits are nominative: a type explicitly declares a named traits to be of its type, while in \CFA, the type implements all functions declared in a trait to implicitly satisfy a polymorphic function/type needs.
     123
     124One of the key differences between concepts and traits, which is leveraged heavily by \CFA, is the ability to apply new \CFA features to C legacy code.
     125For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows that pre-existing C enumerations can be upgraded to work and play with new \CFA enumeration facilities.
     126Another example is adding constructors and destructors to pre-existing C types by simply declaring them for the old C type.
     127\CC fails at certain levels of legacy extension because many of the new \CC features must appear \emph{within} an aggregate definition, where it is impossible to change legacy library types.
    128128
    129129
    130130\section{Bounded and Serial}
    131 A bounded type defines a lower bound and a upper bound.
     131
     132A bounded trait defines a lower and upper bound for a type.
    132133\begin{cfa}
    133134forall( E ) trait Bounded {
    … …  
    135136        E lowerBound();
    136137};
    137 
    138 \end{cfa}
    139 Both Bounded functions are implement for \CFA enumerations, with @lowerBound()@ returning the first enumerator and @upperBound()@ returning
    140 the last enumerator.
    141 \begin{cfa}
    142 Workday day = lowerBound();                                     $\C{// Mon}$
    143 Planet outermost = upperBound();                                $\C{// NEPTUNE}$
    144 \end{cfa}
    145 
    146 The lowerBound() and upperBound() are functions overloaded on return type only, means their type resolution solely depend on the outer context,
    147 including expected type as a function argument, or the left hand size of an assignment expression.
    148 Calling either function without a context results in a type ambiguity, except in the rare case where the type environment has only one
    149 type overloads the functions, including \CFA enumerations, which has Bounded functions automatic defined.
    150 \begin{cfa}
    151 @lowerBound();@                 $\C{// ambiguous as both Workday and Planet implement Bounded}$
    152 sout | @lowerBound()@;
    153 Workday day = first();          $\C{// day provides type Workday}$
    154 void foo( Planet p );
    155 foo( last() );                      $\C{// argument provides type Planet}$
    156 \end{cfa}
    157 
    158 @Serial@ is a subset of @Bounded@, with functions maps elements against integers, as well implements a sequential order between members.
     138\end{cfa}
     139Both functions are necessary for the implementation of \CFA enumeration, with @lowerBound@ returning the first enumerator and @upperBound@ returning the last enumerator.
     140\begin{cfa}
     141enum(int) Week { Mon, Tue, Wed, Thu, Fri, Sat, Sun };
     142enum(int) Fruit { Apple, Banana, Cherry };
     143Week first_day = lowerBound();                          $\C{// Mon}$
     144Fruit last_fruit = upperBound();                        $\C{// Cherry}$
     145\end{cfa}
     146The @lowerBound@ and @upperBound@ are functions overloaded on return type only, meaning their type resolution depends solely on the call-site context, such as the parameter type for a function argument or the left hand size of an assignment expression.
     147Calling either function without a context results in a type ambiguity, unless the type environment has only one type overloading the functions.
     148\begin{cfa}
     149sout | @lowerBound()@;      $\C[2.5in]{// ambiguous as Week and Fruit implement Bounded}$
     150void foo( Fruit );
     151foo( lowerBound() );            $\C{// parameter provides type Fruit}$
     152Week day = upperBound();        $\C{// day provides type Week}\CRT$
     153\end{cfa}
     154
     155Trait @Serial@ is a subset of @Bounded@, with functions mapping enumerators to integers, and implementing a sequential order between enumerators.
    159156\begin{cfa}
    160157forall( E | Bounded( E ) ) trait Serial {
    161         unsigned fromInstance( E e );
     158        int fromInstance( E e );
    162159        E fromInt( unsigned int i );
     160        E pred( E e );
    163161        E succ( E e );
    164         E pred( E e );
    165         unsigned Countof( E e );
    166 };
    167 \end{cfa}
    168 
    169 % A Serail type can project to an unsigned @int@ type, \ie an instance of type T has a corresponding integer value.
    170 Function @fromInstance()@ projects a @Bounded@ member to a number and @fromInt@ is the inverser. Function @succ()@ take an element, returns the "next"
    171 member in sequential order and @pred()@ returns the "last" member.
    172 
    173 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}.
    174 Calling @succ()@ on @upperBound@ or @pred()@ on @lowerBound()@ results in out of bound.
    175 
    176 \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.
    177 Unlike a cast, conversion between \CFA enumeration and integer with @Serial@ interface is type safe.
    178 Specifically for @fromInt@, \CFA abort if input i smaller than @fromInstance(lowerBound())@ or greater than @fromInstance(upperBound())@
    179 
    180 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@.
    181 @Countof@ does not use its arugment as procedural input; it needs
    182 an argument to anchor its polymorphic type T.
    183 
    184 \CFA has an expression @countof@ (lower case) that returns the number of enumerators defined for enumerations.
    185 \begin{cfa}
    186 enum RGB {Red, Green, Blue};
    187 countof( RGB );
    188 countof( Red );
    189 \end{cfa}
    190 Both expressions from the previous example are converted to constant expression @3@ with no function call at runtime.
    191 @countof@ also works for any type T that defines @Countof@ and @lowerBound@, for which it turns into
    192 a function call @Countof( T )@. The resolution step on expression @countof(e)@ works as the following with priority ordered:
     162        unsigned Countof( E );
     163};
     164\end{cfa}
     165Function @fromInstance@ projects a @Bounded@ member to a number and @fromInt@ is the inverse.
     166Function @pred@ takes an enumerator and returns the previous enumerator, if there is one, in sequential order, and @succ@ returns the next enumerator.
     167\begin{cfa}
     168sout | fromInstance( Wed ) | fromInt( 2 ) | succ( Wed ) | pred( Wed );
     1692 Wed Thu Tue
     170\end{cfa}
     171Bound checking is provided for @fromInt@, @pred@, and @succ@, and the program is terminated if the lower or upper bound is exceeded, \eg:
     172\begin{cfa}
     173fromInt( 100 );
     174Cforall Runtime error: call to fromInt has index 100 outside of enumeration range 0-6.
     175\end{cfa}
     176Function @fromInstance@ or a position cast using @(int)@ is always safe, \ie within the enumeration range.
     177
     178Function @Countof@ is the generic counterpart to the builtin pseudo-function @countof@.
     179@countof@ only works on enumeration types and instances, so it is locked into the language type system;
     180as such, @countof( enum-type)@ becomes a compile-time constant.
     181@Countof@ works on an any type that matches the @Serial@ trait.
     182Hence, @Countof@ does not use its argument;
     183only the parameter type is needed to compute the range size.
     184\begin{cfa}
     185int Countof( E ) {
     186        E upper = upperBound();
     187        E lower = lowerBound();
     188        return fromInstance( upper ) + fromInstance( lower ) + 1;
     189}
     190\end{cfa}
     191
     192@countof@ also works for any type @E@ that defines @Countof@ and @lowerBound@, becoming a call to @Countof( E )@.
     193The resolution step on expression @countof( E )@ are:
    193194\begin{enumerate}
    194 \item Looks for an enumeration named e, such as @enum e {... }@.
    195 If such an enumeration e exists, \CFA replace @countof(e)@  with constant expression with number of enumerator of e.
    196 \item Looks for a non-enumeration type named e that defines @Countof@ and @lowerBound@, including e being a polymorphic type, such as @forall(e)@.
    197 If type e exists, \CFA replaces it with @Countof(lowerBound())@, where lowerBound() is bounded to type e. 
    198 \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.
    199 \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)@.
    200 \item If 1-4 fail, \CFA reports a type error on expression @countof(e)@.
     195\item Look for an enumeration named @E@, such as @enum E {... }@.
     196If such an enumeration @E@ exists, replace @countof( E )@  with the number of enumerators.
     197\item Look for a non-enumeration type named @E@ that defines @Countof@ and @lowerBound@, including @E@ being a polymorphic type, such as @forall( E )@.
     198If type @E@ exists, replaces it with @Countof(lowerBound())@, where @lowerBound@ is defined for type @E@.
     199\item Look for an enumerator @A@ defined in enumeration @E@.
     200If such an enumerator @A@ exists, replace @countof( A )@ with the number of enumerators in @E@.
     201\item Look for a name @A@ in the lexical context with type @E@.
     202If such name @A@ exists, replace @countof( A )@ with function call @Countof( E )@.
     203\item If 1-4 fail, report a type error on expression @countof( E )@.
    201204\end{enumerate}
    202205
    203 \section{Iterating Over An Enumeration}
    204 An fundamental aspect of an enumerated type is to be able to enumerate over its enumerators. \CFA supports \newterm{for} loops,
    205 \newterm{while} loop, and \newterm{range} loop. This section covers @for@ loops and @range@ loops for
    206 enumeration, but the concept transition to @while@ loop.
     206
     207\section{Enumerating}
     208
     209The fundamental aspect of an enumeration type is the ability to enumerate over its enumerators.
     210\CFA supports \newterm{for} loops, \newterm{while} loop, and \newterm{range} loop. This section covers @for@ loops and @range@ loops for enumeration, but the concept transition to @while@ loop.
     211
    207212
    208213\subsection{For Loop}
    209 A for loop is constitued by a loop control and a loop body.
    210 A loop control is often a 3-tuple, separated by semicolons: initializers, condition, and an expression. It is a common practice to declare
    211 a variable, often in initializers, that be used in the condition and updated in the expression or loop body. Such variable is called \newterm{index}.
    212 
    213 % With implemented @Bounded@ and @Serial@ interface for \CFA enumeration, a @for@ loop that iterates over \CFA enumeration can be implemented as the following:
    214 A @for@ loop iterates an enumeration can be written with functions from @Bounded@ and @Serial@ interfaces:
    215 \begin{cfa}
    216 enum() Chars { A, B, C, D };
    217 for( unsigned i = 0; i < countof(E); i++ ) { sout | label(e); }         $\C{// (1) A B C D}$
    218 for( Chars e = lowerBound(); ; e = succ(e) ) { $\C{// (2)}$
    219         sout |label((Chars)fromInt(i)) |' ';
    220         if (e == upperBound()) break;
    221 }
    222 \end{cfa}
    223 
    224 A caveat in writing loop using finite number as index is that the number can unintentionally be out the range:
    225 \begin{cfa}
    226 for( unsigned i = countof(Chars) - 1; i >= 0; i-- ) {}                          $\C{// 3}$
    227 for( Chars e = lowerBound(); e <= upperBound(); e = succ(e) ) {}        $\C{// 4}$
    228 for( Chars e = upperBound(); e >= lowerBound(); e = pred(e) ) {}        $\C{// 5}$
    229 \end{cfa}
    230 Loop (3) is a value underflow: when @i@ reaches to @0@, decrement statement will still execute and cause
    231 the @unsigned int@ value @i@ wraps to @UINT_MAX@, which fails to loop test and the loop cannot terminate.
    232 
    233 In loop (4) and (5), when @e@ is at the @Bound@ (@upperBound@/@lowerBound@) and @succ@/@pred@ will result in @out of bounded@, \CFA
    234 aborts its execution. Therefore, it is necessary to implement the condtional break within the loop body.
     214
     215A for-loop consists of loop control and body.
     216The loop control is often a 3-tuple: initializers, stopping condition, and advancement.
     217It is a common practice to declare one or more loop-index variables in initializers, checked these variables for stopping iteration, and updated the variables in advancement.
     218Such a variable is called an \newterm{index} and is available for reading and writing within the loop body.
     219(Some languages make the index read-only in the loop body.)
     220This style of iteration can be written for an enumeration using functions from the @Bounded@ and @Serial@ traits:
     221\begin{cfa}
     222enum() E { A, B, C, D };
     223for ( unsigned int i = 0; i < countof(E); i += 1 ) $\C{// (1)}$
     224        sout | label( fromInt( i ) ) | nonl;
     225sout | nl;
     226for ( E e = lowerBound(); ; e = succ(e) ) {     $\C{// (2)}$
     227        sout | label(e) | nonl;
     228  if (e == upperBound()) break;
     229}
     230sout | nl;
     231A B C D
     232A B C D
     233\end{cfa}
     234
     235A caveat in writing loop control using @pred@ and @succ@ is unintentionally exceeding the range.
     236\begin{cfa}
     237for ( E e = upperBound(); e >= lowerBound(); e = pred( e ) ) {}
     238for ( E e = lowerBound(); e <= upperBound(); e = succ( e ) ) {}
     239\end{cfa}
     240Both of these loops look correct but fail because these is an additional bound check within the advancement \emph{before} the conditional test to stop the loop, resulting in a failure at the endpoints of the iteration.
     241These loops must be restructured by moving the loop test to the end of the loop (@do-while@), as in loop (2) above, which is safe because an enumeration always at least one enumerator.
    235242
    236243
    237244\subsection{Range Loop}
    238 Instead of specifying condition, \CFA supports @range loops@, for which a user specifies a range of values.
    239 \begin{cfa}[label=lst:range_functions_2]
    240 for ( Chars e; A ~= D ) { sout | label(e); }            $\C{// (6)}$
    241 for ( e; A ~= D ) { sout | label(e); }                          $\C{// (7)}$
    242 for ( Chars e; A -~= D ) { sout | label(e); }           $\C{// (8) D C B A}$
    243 for ( e; A -~=D ~ 2 ) { sout | label(e); }              $\C{// (9) D B }$
    244 \end{cfa}
    245 Every range loop above has an index declaration, and a @range@ bounded by \newterm{left bound} @A@ and \newterm{right bound} @D@.
    246 An index declaration can have an optional type declaration, without which \CFA
    247 implicitly declares index variable to be the type of the bounds (@typeof(A)@).
    248 If a range is joined by @~=@ (range up equal) operator, the index variable will be initialized by
    249 the @left bound@, and change incrementally until its position exceeds @right bound@.
    250 On the other hand, if a range is defined with @-~=@ (range down equal) operation, the index variable will
    251 have the value of the @right bound@. It change decrementally until its position is less than the @left bound@.
    252 A range can be suffixed by an positive integal \newterm{step}, joined by @~@. The loop @(9)@ declares a step size of 2 so that
    253 e updates @pred(pred(e))@ in every iteration.
    254 
    255 \CFA manipulates the position of the index variable and breaks the loop if an index update can result in @out of range@.
    256 
    257 \CFA provides a shorthand for range loop over a \CFA enumeration or a @Serial@:
    258 \begin{cfa}[label=lst:range_functions_2]
    259 for ( e; Chars ) { sout | label(e); }           $\C{// (10) A B C D}$
    260 for ( e; E ) {                                                          $\C{// forall(E | CfaEnum(E) | Serial(E)) }$
    261     sout | label(e);
    262 }
    263 \end{cfa}
    264 The shorthand syntax has a type name expression (@Char@ and @E@) as its range. If the range expression does not name
    265 a \CFA enumeration or a @Serial@, \CFA reports a compile time error. When type name as range is a \CFA enumeration,
    266 it turns into a loop that iterates all enumerators of the type. If the type name is a @Serial@, the index variable
    267 will be initialized as the @lowerBound@. The loop control checks the index's position against the position of @upperBound@,
    268 and terminate the loop when the index has a position greater than the @upperBound@. \CFA does not update the index with
    269 @succ@ but manipulate its position directly to avoid @out of bound@.
     245
     246Instead of writing the traditional 3-tuple loop control, \CFA supports a \newterm{range loop}.
     247\begin{cfa}
     248for ( @E e; A ~= D@ ) { sout | label( e ) | nonl; } sout | nl;
     249for ( @e; A ~= D@ ) { sout | label( e ) | nonl; } sout | nl;
     250for ( @E e; A -~= D@ ) { sout | label( e ) | nonl; } sout | nl;
     251for ( @e; A -~= D ~ 2@ ) { sout | label( e ) | nonl; } sout | nl;
     252\end{cfa}
     253Every range loop above has an index declaration and a @range@ bounded by \newterm{left bound} @A@ and \newterm{right bound} @D@.
     254If the index declaration-type is omitted, the index type is the type of the lower bound (@typeof( A )@).
     255If a range is joined by @~=@ (range up equal) operator, the index variable is initialized by the left bound and advanced by 1 until it is greater than the right bound.
     256If a range is joined by @-~=@ (range down equal) operator, the index variable is initialized by the right bound and advanced by -1 until it is less than the left bound.
     257(Note, functions @pred@ and @succ@ are not used for advancement, so the advancement problem does not occur.)
     258A range can be suffixed by a positive \newterm{step}, \eg @~ 2@, so advancement is incremented/decremented by step.
     259
     260Finally, a shorthand for enumerating over the entire set of enumerators (the most common case) is using the enumeration type for the range.
     261\begin{cfa}
     262for ( e; @E@ ) sout | label( e ) | nonl; sout | nl; $\C{// A B C D}$
     263for ( e; @-~= E@ ) sout | label( e ) | nonl; sout | nl; $\C{// D C B A}$
     264\end{cfa}
     265For a \CFA enumeration, the loop enumerates over all enumerators of the enumeration.
     266For a type matching the @Serial@ trait: the index variable is initialized to @lowerBound@ and loop control checks the index's value for greater than the @upperBound@.
     267If the range type is not a \CFA enumeration or does not match trait @Serial@, it is compile-time error.
     268
    270269
    271270\section{Overload Operators}
    272 % Finally, there is an associated trait defining comparison operators among enumerators.
    273 \CFA preemptively overloads comparison operators for \CFA enumeration with @Serial@ and @CfaEnum@.
    274 They defines that two enumerators are equal only if the are the same enumerator, and compartors are
    275 define for order comparison.
    276 \begin{cfa}
    277 forall( E | CfaEnum( E ) | Serial( E ) ) {
     271
     272\CFA overloads the comparison operators for \CFA enumeration satisfying traits @Serial@ and @CfaEnum@.
     273These definitions require the operand types be the same and the appropriate comparison is made using the the positions of the operands.
     274\begin{cfa}
     275forall( E | CfaEnum( E ) | Serial( E ) ) @{@ $\C{// distribution block}$
    278276        // comparison
    279277        int ?==?( E l, E r );           $\C{// true if l and r are same enumerators}$
    … …  
    283281        int ?>?( E l, E r );            $\C{// true if l is an enumerator after r}$
    284282        int ?>=?( E l, E r );           $\C{// true if l after or the same as r}$
    285 }
    286 \end{cfa}
    287 
    288 \CFA implements few arithmetic operators for @CfaEnum@. Unlike update functions in @Serial@, these
    289 operator does not have bound checks, which rely on @upperBound@ and @lowerBound@. These operators directly manipulate
    290 position, the underlying representation of a \CFA enumeration.
    291 \begin{cfa}
    292 forall( E | CfaEnum( E ) | Serial( E ) ) {
     283@}@
     284\end{cfa}
     285(Note, all the function prototypes are wrapped in a distribution block, where all qualifiers preceding the block are distributed to each declaration with the block, which eliminated tedious repeated qualification.
     286Distribution blocks can be nested.)
     287
     288\CFA implements a few arithmetic operators for @CfaEnum@.
     289Unlike advancement functions in @Serial@, these operators perform direct arithmetic, so there is no implicit bound checks.
     290\begin{cfa}
     291forall( E | CfaEnum( E ) | Serial( E ) ) { $\C{// distribution block}$
    293292        // comparison
    294293        E ++?( E & l );
    … …  
    303302\end{cfa}
    304303
    305 Lastly, \CFA does not define @zero_t@ for \CFA enumeration. Users can define the boolean false for
    306 \CFA enumerations on their own. Here is an example:
    307 \begin{cfa}
    308 forall(E | CfaEnum(E))
    309 bool ?!=?(E lhs, zero_t) {
    310         return posn(lhs) != 0;
    311 }
    312 \end{cfa}
    313 which effectively turns the first enumeration as a logical false and true for others.
    314 
    315 % \begin{cfa}
    316 % Count variable_a = First, variable_b = Second, variable_c = Third, variable_d = Fourth;
    317 % p(variable_a); // 0
    318 % p(variable_b); // 1
    319 % p(variable_c); // "Third"
    320 % p(variable_d); // 3
    321 % \end{cfa}
    322 
    323 
    324 % \section{Iteration and Range}
    325 
    326 
    327 
    328 % % It is convenient to iterate over a \CFA enumeration value, \eg:
    329 % \CFA implements \newterm{range loop} for \CFA enumeration using the enumerated traits. The most basic form of @range loop@ is the follows:
    330 % \begin{cfa}[label=lst:range_functions]
    331 % for ( Alphabet alph; Alphabet ) { sout | alph; }
    332 % >>> A B C ... D
    333 % \end{cfa}
    334 % % The @range loops@ iterates through all enumerators in the order defined in the enumeration.
    335 % % @alph@ is the iterating enumeration object, which returns the value of an @Alphabet@ in this context according to the precedence rule.
    336 % Enumerated @range loop@ extends the \CFA grammar as it allows a type name @Alphabet@
    337 
    338 % \textbullet\ \CFA offers a shorthand for iterating all enumeration constants:
    339 % \begin{cfa}[label=lst:range_functions]
    340 % for ( Alphabet alph ) { sout | alph; }
    341 % >>> A B C ... D
    342 % \end{cfa}
    343 
    344 % The following are examples for constructing for-control using an enumeration. Note that the type declaration of the iterating variable is optional, because \CFA can infer the type as EnumInstType based on the range expression, and possibly convert it to one of its attribute types.
    345 
    346 % \textbullet\ H is implicit up-to exclusive range [0, H).
    347 % \begin{cfa}[label=lst:range_function_1]
    348 % for ( alph; Alphabet.D ) { sout | alph; }
    349 % >>> A B C
    350 % \end{cfa}
    351 
    352 % \textbullet\ ~= H is implicit up-to inclusive range [0,H].
    353 % \begin{cfa}[label=lst:range_function_2]
    354 % for ( alph; ~= Alphabet.D ) { sout | alph; }
    355 % >>> A B C D
    356 % \end{cfa}
    357 
    358 % \textbullet\ L ~ H is explicit up-to exclusive range [L,H).
    359 % \begin{cfa}[label=lst:range_function_3]
    360 % for ( alph; Alphabet.B ~ Alphabet.D  ) { sout | alph; }
    361 % // for ( Alphabet alph = Alphabet.B; alph < Alphabet.D; alph += 1  ); 1 is one_t
    362 % >>> B C
    363 % \end{cfa}
    364 
    365 % \textbullet\ L ~= H is explicit up-to inclusive range [L,H].
    366 % \begin{cfa}[label=lst:range_function_4]
    367 % for ( alph; Alphabet.B ~= Alphabet.D  ) { sout | alph; }
    368 % >>> B C D
    369 % \end{cfa}
    370 
    371 % \textbullet\ L -~ H is explicit down-to exclusive range [H,L), where L and H are implicitly interchanged to make the range down-to.
    372 % \begin{cfa}[label=lst:range_function_5]
    373 % for ( alph; Alphabet.D -~ Alphabet.B  ) { sout | alph; }
    374 % >>> D C
    375 % \end{cfa}
    376 
    377 % \textbullet\ L -~= H is explicit down-to exclusive range [H,L], where L and H are implicitly interchanged to make the range down-to.
    378 % \begin{cfa}[label=lst:range_function_6]
    379 % for ( alph; Alphabet.D -~= Alphabet.B  ) { sout | alph; }
    380 % >>> D C B
    381 % \end{cfa}
    382 
    383 % A user can specify the ``step size'' of an iteration. There are two different stepping schemes of enumeration for-loop.
    384 % \begin{cfa}[label=lst:range_function_stepping]
    385 % enum(int) Sequence { A = 10, B = 12, C = 14, D = 16, D  = 18 };
    386 % for ( s; Sequence.A ~= Sequence.D ~ 1  ) { sout | alph; }
    387 % >>> 10 12 14 16 18
    388 % for ( s; Sequence.A ~= Sequence.D; s+=1  ) { sout | alph; }
    389 % >>> 10 11 12 13 14 15 16 17 18
    390 % \end{cfa}
    391 % The first syntax is stepping to the next enumeration constant, which is the default stepping scheme if not explicitly specified. The second syntax, on the other hand, is to call @operator+=@ @one_type@ on the @value( s )@. Therefore, the second syntax is equivalent to
    392 % \begin{cfa}[label=lst:range_function_stepping_converted]
    393 % for ( typeof( value(Sequence.A) ) s=value( Sequence.A ); s <= Sequence.D; s+=1  ) { sout | alph; }
    394 % >>> 10 11 12 13 14 15 16 17 18
    395 % \end{cfa}
    396 
    397 % % \PAB{Explain what each loop does.}
    398 
    399 % It is also possible to iterate over an enumeration's labels, implicitly or explicitly:
    400 % \begin{cfa}[label=lst:range_functions_label_implicit]
    401 % for ( char * alph; Alphabet )
    402 % \end{cfa}
    403 % This for-loop implicitly iterates every label of the enumeration, because a label is the only valid resolution to @ch@ with type @char *@ in this case.
    404 % If the value can also be resolved as the @char *@, you might iterate the labels explicitly with the array iteration.
    405 % \begin{cfa}[label=lst:range_functions_label_implicit]
    406 % for ( char * ch; labels( Alphabet ) )
    407 % \end{cfa}
     304Lastly, \CFA does not define @zero_t@ for \CFA enumeration.
     305Users can define the boolean @false@ for \CFA enumerations on their own, \eg:
     306\begin{cfa}
     307forall( E | CfaEnum( E ) )
     308int ?!=?( E lhs, zero_t ) {
     309        return posn( lhs ) != 0;
     310}
     311\end{cfa}
     312which effectively turns the first enumeration to a logical @false@ and @true@ for the others.
Note: See TracChangeset for help on using the changeset viewer.