Changeset 8cb2ff6 for doc/theses
- Timestamp:
- Aug 6, 2024, 11:09:05 PM (5 weeks ago)
- Branches:
- master
- Children:
- d7cb0f7
- Parents:
- bd686f0
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/jiada_liang_MMath/trait.tex
rbd686f0 r8cb2ff6 2 2 \label{c:trait} 3 3 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}. 5 With this combination, it is possible to write a polymorphic function over an enumerated type. 6 \begin{c++} 9 7 #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@: 8 template<typename T> @concept Enumerable@ = std::is_enum<T>::value; 9 template<@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 } 14 int main() { 15 enum E { A = 42, B, C } e = C; 16 e = f( e ); 17 } 18 44 44 19 \end{c++} 20 The @std::is_enum@ and other \CC @traits@ are a compile-time interfaces to query type information. 21 While 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 23 The 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 28 Traits @CfaEnum@ and @TypedEnum@ define the enumeration attributes: @label@, @posn@, @value@, and @Countof@. 29 These traits support polymorphic functions for \CFA enumeration, \eg: 30 \begin{cfa} 31 forall( E ) | @CfaEnum( E )@ ) 32 void f( E e ) { 33 // access enumeration properties for e 34 } 35 \end{cfa} 36 37 Trait @CfaEnum@ defines attribute functions @label@ and @posn@ for all \CFA enumerations, and internally \CFA enumerations fulfills this assertion. 31 38 \begin{cfa} 32 39 forall( E ) trait CfaEnum { … … 35 42 }; 36 43 \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. 44 This trait covers opaque enumerations that do not have an explicit @value@. 45 46 The trait @TypedEnum@ extends @CfaEnum@ with the @value@ assertion for typed enumerations. 42 47 \begin{cfa} 43 48 forall( E, V | CfaEnum( E ) ) trait TypedEnum { … … 45 50 }; 46 51 \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 } 52 Here, the associate type-parameter @V@ is the base type of the typed enumeration, and hence, the return type of @value@. 53 These two traits provide a way to define functions over all \CFA enumerations. 54 55 For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows a generalized enumeration formatter for any enumeration type. 56 The formatter prints an enumerator name and its value in the form @"label( value )"@. 57 The trait for @format_enum@ requires a function named @str@ for printing the value (payload) of the enumerator. 58 Hence, enumeration defines how its value appear and @format_enum@ displays this value within the label name. 59 60 \begin{figure} 61 \begin{cfa} 62 forall( @E, V | TypedEnum( E, V )@ | { string str( V ); } ) $\C{// format any enumeration}$ 63 string format_enum( E e ) { 64 return label( e ) + '(' + str( value( e ) ) + ')'; $\C{// "label( value )"}$ 65 } 66 enum(size_t) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF }; 67 // string library has conversion function str from size_t to string 68 69 struct color_code { int R, G, B; }; 63 70 enum(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 }; 73 string 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 } 76 int 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 85 Other types may work with traits @CfaEnum@ and @TypedEnum@, by supplying appropriate @label@, @posn@, and @value@ functions. 86 For 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} 90 enum Fruit { Apple, Banana, Cherry }; $\C{// C enum}$ 91 const char * @label@( Fruit f ) { 92 static const char * labels[] = { "Apple", "Banana", "Cherry" }; 93 return labels[f]; 94 } 95 int @posn@( Fruit f ) { return f; } 96 int @value@( Fruit f ) { 97 static const char values[] = { 'a', 'b', 'c' }; 98 return values[f]; 99 } 100 sout | 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 109 At the start of this chapter, the \CC concept is introduced to constraint template types, \eg: 110 \begin{c++} 111 concept Enumerable = std::is_enum<T>::value; 112 \end{c++} 113 Here, @concept@ is referring directly to types with kind @enum@; 114 other @concept@s can refer to all types with kind @int@ with @long@ or @long long@ qualifiers, \etc. 115 Hence, the @concept@ is a first level of restriction allowing only the specified kinds of types and rejecting others. 116 The template expansion is the second level of restriction verifying if the type passing the @concept@ test provides the necessary functionality. 117 Hence, a @concept@ is querying precise aspects of the programming language set of types. 118 119 Alternatively, 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. 120 Hence, the \CFA enumeration traits never connected with the specific @enum@ kind. 121 Instead, anything that can look like the @enum@ kind is considered an enumeration (duck typing). 122 However, 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 124 One 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. 125 For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows that pre-existing C enumerations can be upgraded to work and play with new \CFA enumeration facilities. 126 Another 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. 128 128 129 129 130 130 \section{Bounded and Serial} 131 A bounded type defines a lower bound and a upper bound. 131 132 A bounded trait defines a lower and upper bound for a type. 132 133 \begin{cfa} 133 134 forall( E ) trait Bounded { … … 135 136 E lowerBound(); 136 137 }; 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} 139 Both functions are necessary for the implementation of \CFA enumeration, with @lowerBound@ returning the first enumerator and @upperBound@ returning the last enumerator. 140 \begin{cfa} 141 enum(int) Week { Mon, Tue, Wed, Thu, Fri, Sat, Sun }; 142 enum(int) Fruit { Apple, Banana, Cherry }; 143 Week first_day = lowerBound(); $\C{// Mon}$ 144 Fruit last_fruit = upperBound(); $\C{// Cherry}$ 145 \end{cfa} 146 The @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. 147 Calling either function without a context results in a type ambiguity, unless the type environment has only one type overloading the functions. 148 \begin{cfa} 149 sout | @lowerBound()@; $\C[2.5in]{// ambiguous as Week and Fruit implement Bounded}$ 150 void foo( Fruit ); 151 foo( lowerBound() ); $\C{// parameter provides type Fruit}$ 152 Week day = upperBound(); $\C{// day provides type Week}\CRT$ 153 \end{cfa} 154 155 Trait @Serial@ is a subset of @Bounded@, with functions mapping enumerators to integers, and implementing a sequential order between enumerators. 159 156 \begin{cfa} 160 157 forall( E | Bounded( E ) ) trait Serial { 161 unsignedfromInstance( E e );158 int fromInstance( E e ); 162 159 E fromInt( unsigned int i ); 160 E pred( E e ); 163 161 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} 165 Function @fromInstance@ projects a @Bounded@ member to a number and @fromInt@ is the inverse. 166 Function @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} 168 sout | fromInstance( Wed ) | fromInt( 2 ) | succ( Wed ) | pred( Wed ); 169 2 Wed Thu Tue 170 \end{cfa} 171 Bound 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} 173 fromInt( 100 ); 174 Cforall Runtime error: call to fromInt has index 100 outside of enumeration range 0-6. 175 \end{cfa} 176 Function @fromInstance@ or a position cast using @(int)@ is always safe, \ie within the enumeration range. 177 178 Function @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; 180 as such, @countof( enum-type)@ becomes a compile-time constant. 181 @Countof@ works on an any type that matches the @Serial@ trait. 182 Hence, @Countof@ does not use its argument; 183 only the parameter type is needed to compute the range size. 184 \begin{cfa} 185 int 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 )@. 193 The resolution step on expression @countof( E )@ are: 193 194 \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 {... }@. 196 If 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 )@. 198 If 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@. 200 If 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@. 202 If 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 )@. 201 204 \end{enumerate} 202 205 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 209 The 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 207 212 208 213 \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 215 A for-loop consists of loop control and body. 216 The loop control is often a 3-tuple: initializers, stopping condition, and advancement. 217 It 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. 218 Such 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.) 220 This style of iteration can be written for an enumeration using functions from the @Bounded@ and @Serial@ traits: 221 \begin{cfa} 222 enum() E { A, B, C, D }; 223 for ( unsigned int i = 0; i < countof(E); i += 1 ) $\C{// (1)}$ 224 sout | label( fromInt( i ) ) | nonl; 225 sout | nl; 226 for ( E e = lowerBound(); ; e = succ(e) ) { $\C{// (2)}$ 227 sout | label(e) | nonl; 228 if (e == upperBound()) break; 229 } 230 sout | nl; 231 A B C D 232 A B C D 233 \end{cfa} 234 235 A caveat in writing loop control using @pred@ and @succ@ is unintentionally exceeding the range. 236 \begin{cfa} 237 for ( E e = upperBound(); e >= lowerBound(); e = pred( e ) ) {} 238 for ( E e = lowerBound(); e <= upperBound(); e = succ( e ) ) {} 239 \end{cfa} 240 Both 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. 241 These 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. 235 242 236 243 237 244 \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 246 Instead of writing the traditional 3-tuple loop control, \CFA supports a \newterm{range loop}. 247 \begin{cfa} 248 for ( @E e; A ~= D@ ) { sout | label( e ) | nonl; } sout | nl; 249 for ( @e; A ~= D@ ) { sout | label( e ) | nonl; } sout | nl; 250 for ( @E e; A -~= D@ ) { sout | label( e ) | nonl; } sout | nl; 251 for ( @e; A -~= D ~ 2@ ) { sout | label( e ) | nonl; } sout | nl; 252 \end{cfa} 253 Every range loop above has an index declaration and a @range@ bounded by \newterm{left bound} @A@ and \newterm{right bound} @D@. 254 If the index declaration-type is omitted, the index type is the type of the lower bound (@typeof( A )@). 255 If 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. 256 If 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.) 258 A range can be suffixed by a positive \newterm{step}, \eg @~ 2@, so advancement is incremented/decremented by step. 259 260 Finally, 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} 262 for ( e; @E@ ) sout | label( e ) | nonl; sout | nl; $\C{// A B C D}$ 263 for ( e; @-~= E@ ) sout | label( e ) | nonl; sout | nl; $\C{// D C B A}$ 264 \end{cfa} 265 For a \CFA enumeration, the loop enumerates over all enumerators of the enumeration. 266 For 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@. 267 If the range type is not a \CFA enumeration or does not match trait @Serial@, it is compile-time error. 268 270 269 271 270 \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@. 273 These definitions require the operand types be the same and the appropriate comparison is made using the the positions of the operands. 274 \begin{cfa} 275 forall( E | CfaEnum( E ) | Serial( E ) ) @{@ $\C{// distribution block}$ 278 276 // comparison 279 277 int ?==?( E l, E r ); $\C{// true if l and r are same enumerators}$ … … 283 281 int ?>?( E l, E r ); $\C{// true if l is an enumerator after r}$ 284 282 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. 286 Distribution blocks can be nested.) 287 288 \CFA implements a few arithmetic operators for @CfaEnum@. 289 Unlike advancement functions in @Serial@, these operators perform direct arithmetic, so there is no implicit bound checks. 290 \begin{cfa} 291 forall( E | CfaEnum( E ) | Serial( E ) ) { $\C{// distribution block}$ 293 292 // comparison 294 293 E ++?( E & l ); … … 303 302 \end{cfa} 304 303 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} 304 Lastly, \CFA does not define @zero_t@ for \CFA enumeration. 305 Users can define the boolean @false@ for \CFA enumerations on their own, \eg: 306 \begin{cfa} 307 forall( E | CfaEnum( E ) ) 308 int ?!=?( E lhs, zero_t ) { 309 return posn( lhs ) != 0; 310 } 311 \end{cfa} 312 which effectively turns the first enumeration to a logical @false@ and @true@ for the others.
Note: See TracChangeset
for help on using the changeset viewer.