Changeset 96de72b
- Timestamp:
- Aug 6, 2024, 4:01:50 AM (5 weeks ago)
- Branches:
- master
- Children:
- 1c957a11
- Parents:
- 0e6cf54c
- Location:
- doc/theses/jiada_liang_MMath
- Files:
-
- 1 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/jiada_liang_MMath/intro.tex
r0e6cf54c r96de72b 299 299 \begin{enumerate} 300 300 \item 301 overloading: 302 \item 303 scoping 304 \item 305 typing 306 \item 307 subseting 308 \item 309 inheritance 301 overloading: provides a general pattern to overload functions, literal, and variable for polymorphic enumerations. 302 \item 303 scoping: implement name spacing scheme for enumerations. 304 \item 305 safety: define a safe enumeration conversion scheme. 306 \item 307 harmonization: allows enumeration to carry data. 308 \item 309 inheritance: define containment inheritance for enumerations. 310 310 \end{enumerate} 311 311 -
doc/theses/jiada_liang_MMath/trait.tex
r0e6cf54c r96de72b 185 185 \begin{cfa} 186 186 enum RGB {Red, Green, Blue}; 187 countof( RGB ); // (1)188 countof( Red ); // (2)187 countof( RGB ); 188 countof( Red ); 189 189 \end{cfa} 190 190 Both expressions from the previous example are converted to constant expression @3@ with no function call at runtime. … … 201 201 \end{enumerate} 202 202 203 With the @Bounded@ and @Serial@, a loop over enumeration can be implemented in the following ways: 204 \begin{cfa} 205 enum() E { ... } 206 for( unsigned i = 0; i < countof(E); i++ ) { ... } 207 for( E e = lowerBound(); ; e = succ(e) ) { ...; if (e == upperBound()) break; } 208 209 forall( T ) { 210 for( unsigned i = 0; i < countof(T); i++ ) { ... } 211 for( T e = lowerBound(); ; e = succ(e) ) { ...; if (e == upperBound()) break; } 212 } 213 \end{cfa} 214 215 Finally, there is an associated trait defining comparison operators among enumerators. 216 \begin{cfa} 217 forall( E, T | CfaEnum( E, T ) ) { 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. 207 208 \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. 235 236 237 \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@. 270 271 \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 ) ) { 218 278 // comparison 219 279 int ?==?( E l, E r ); $\C{// true if l and r are same enumerators}$ 220 280 int ?!=?( E l, E r ); $\C{// true if l and r are different enumerators}$ 221 int ?!=?( E l, zero_t ); $\C{// true if l is not the first enumerator}$222 281 int ?<?( E l, E r ); $\C{// true if l is an enumerator before r}$ 223 282 int ?<=?( E l, E r ); $\C{// true if l before or the same as r}$ 224 283 int ?>?( E l, E r ); $\C{// true if l is an enumerator after r}$ 225 int ?>=?( E l, E r ); $\C{// true if l after or the same as r}$ 226 } 227 \end{cfa} 228 229 As an alternative, users can define the boolean conversion for CfaEnum: 230 284 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 ) ) { 293 // comparison 294 E ++?( E & l ); 295 E --?( E & l ); 296 E ?+=? ( E & l, one_t ); 297 E ?-=? ( E & l, one_t ); 298 E ?+=? ( E & l, int i ); 299 E ?-=? ( E & l, int i ); 300 E ?++( E & l ); 301 E ?--( E & l ); 302 } 303 \end{cfa} 304 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: 231 307 \begin{cfa} 232 308 forall(E | CfaEnum(E)) … … 235 311 } 236 312 \end{cfa} 237 which effectively turns the first enumeration as a logical zero and non-zero for others. 238 239 \begin{cfa} 240 Count variable_a = First, variable_b = Second, variable_c = Third, variable_d = Fourth; 241 p(variable_a); // 0 242 p(variable_b); // 1 243 p(variable_c); // "Third" 244 p(variable_d); // 3 245 \end{cfa} 246 247 248 \section{Iteration and Range} 249 250 It is convenient to iterate over a \CFA enumeration value, \eg: 251 \begin{cfa}[label=lst:range_functions] 252 for ( Alphabet alph; Alphabet ) { sout | alph; } 253 >>> A B C ... D 254 \end{cfa} 255 The for-loop uses the enumeration type @Alphabet@ its range, and iterates through all enumerators in the order defined in the enumeration. 256 @alph@ is the iterating enumeration object, which returns the value of an @Alphabet@ in this context according to the precedence rule. 257 258 \textbullet\ \CFA offers a shorthand for iterating all enumeration constants: 259 \begin{cfa}[label=lst:range_functions] 260 for ( Alphabet alph ) { sout | alph; } 261 >>> A B C ... D 262 \end{cfa} 263 264 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. 265 266 \textbullet\ H is implicit up-to exclusive range [0, H). 267 \begin{cfa}[label=lst:range_function_1] 268 for ( alph; Alphabet.D ) { sout | alph; } 269 >>> A B C 270 \end{cfa} 271 272 \textbullet\ ~= H is implicit up-to inclusive range [0,H]. 273 \begin{cfa}[label=lst:range_function_2] 274 for ( alph; ~= Alphabet.D ) { sout | alph; } 275 >>> A B C D 276 \end{cfa} 277 278 \textbullet\ L ~ H is explicit up-to exclusive range [L,H). 279 \begin{cfa}[label=lst:range_function_3] 280 for ( alph; Alphabet.B ~ Alphabet.D ) { sout | alph; } 281 // for ( Alphabet alph = Alphabet.B; alph < Alphabet.D; alph += 1 ); 1 is one_t 282 >>> B C 283 \end{cfa} 284 285 \textbullet\ L ~= H is explicit up-to inclusive range [L,H]. 286 \begin{cfa}[label=lst:range_function_4] 287 for ( alph; Alphabet.B ~= Alphabet.D ) { sout | alph; } 288 >>> B C D 289 \end{cfa} 290 291 \textbullet\ L -~ H is explicit down-to exclusive range [H,L), where L and H are implicitly interchanged to make the range down-to. 292 \begin{cfa}[label=lst:range_function_5] 293 for ( alph; Alphabet.D -~ Alphabet.B ) { sout | alph; } 294 >>> D C 295 \end{cfa} 296 297 \textbullet\ L -~= H is explicit down-to exclusive range [H,L], where L and H are implicitly interchanged to make the range down-to. 298 \begin{cfa}[label=lst:range_function_6] 299 for ( alph; Alphabet.D -~= Alphabet.B ) { sout | alph; } 300 >>> D C B 301 \end{cfa} 302 303 A user can specify the ``step size'' of an iteration. There are two different stepping schemes of enumeration for-loop. 304 \begin{cfa}[label=lst:range_function_stepping] 305 enum(int) Sequence { A = 10, B = 12, C = 14, D = 16, D = 18 }; 306 for ( s; Sequence.A ~= Sequence.D ~ 1 ) { sout | alph; } 307 >>> 10 12 14 16 18 308 for ( s; Sequence.A ~= Sequence.D; s+=1 ) { sout | alph; } 309 >>> 10 11 12 13 14 15 16 17 18 310 \end{cfa} 311 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 312 \begin{cfa}[label=lst:range_function_stepping_converted] 313 for ( typeof( value(Sequence.A) ) s=value( Sequence.A ); s <= Sequence.D; s+=1 ) { sout | alph; } 314 >>> 10 11 12 13 14 15 16 17 18 315 \end{cfa} 316 317 % \PAB{Explain what each loop does.} 318 319 It is also possible to iterate over an enumeration's labels, implicitly or explicitly: 320 \begin{cfa}[label=lst:range_functions_label_implicit] 321 for ( char * alph; Alphabet ) 322 \end{cfa} 323 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. 324 If the value can also be resolved as the @char *@, you might iterate the labels explicitly with the array iteration. 325 \begin{cfa}[label=lst:range_functions_label_implicit] 326 for ( char * ch; labels( Alphabet ) ) 327 \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}
Note: See TracChangeset
for help on using the changeset viewer.