Changeset 0bda8d7 for doc/theses/jiada_liang_MMath
- Timestamp:
- Sep 15, 2024, 7:53:45 PM (5 weeks ago)
- Branches:
- master
- Children:
- c329bca, eaeba79
- Parents:
- 175a750e
- Location:
- doc/theses/jiada_liang_MMath
- Files:
-
- 4 edited
-
CFAenum.tex (modified) (12 diffs)
-
Cenum.tex (modified) (2 diffs)
-
relatedwork.tex (modified) (12 diffs)
-
trait.tex (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/jiada_liang_MMath/CFAenum.tex
r175a750e r0bda8d7 136 136 \section{Implementation} 137 137 138 \CFA-cc is isa transpiler translating \CFA code into C, which is compiled by a C compiler.139 During transpil ation, \CFA-cc breaks a \CFA enumeration definition into a definition of a C enumeration with the same name and auxiliary arrays: a label and value array for a typed enumeration.138 \CFA-cc is a transpiler translating \CFA code into C, which is compiled by a C compiler. 139 During transpiling, \CFA-cc breaks a \CFA enumeration definition into a definition of a C enumeration with the same name and auxiliary arrays: a label and value array for a typed enumeration. 140 140 For example: 141 141 \begin{cfa} … … 157 157 Therefore, a \CFA enumeration variable has the same underlying representation as its generated C enumeration. 158 158 This semantics implies a \CFA enumeration variable uses the same storage as a C enumeration variable, that @posn@ can use as its underlying representation, and the label and value arrays take little storage. 159 It should be possible to eliminate dthe two arrays if unused, either by \CFA if local to a translation unit and unused, or by the linker if global but unreferenced.159 It should be possible to eliminate the two arrays if unused, either by \CFA if local to a translation unit and unused, or by the linker if global but unreferenced. 160 160 Also, the label and value arrays are declared @static@ and initialized with constants, so the arrays are allocated in the @.data@ section and initialized before program execution. 161 Hence, there is no addition execution cost unless new enumeration features are use, and storage usage is minimal as the number of enumerations in a program is small as is the number of enumerators in an enumeration.161 Hence, there is no additional execution cost unless new enumeration features are used, and storage usage is minimal as the number of enumerations in a program is small as is the number of enumerators in an enumeration. 162 162 163 163 Along with the enumeration definition, \CFA-cc generates definitions of the attribute functions, @posn@, @label@ and @value@, for each enumeration: … … 171 171 Note, the cast to @int@ is actually an internal reinterpreted cast added before type resolution to stop further reduction on the expression by the type resolver \see{\VRef{s:ValueConversion}} and removed in code generation. 172 172 Finally, to further mitigate \CFA enumeration costs, calls to @label@ and @value@ with an enumeration constant are unrolled into the appropriate constant expression, although this could be left to the backend C compiler. 173 Hence, in space and time costs, \CFA enumerations follow the C philosophy of only paying for what is used, modulo some future work to convince the linker to remove un accessed @label@ and @value@ arrays, possibly with @weak@ attributes.173 Hence, in space and time costs, \CFA enumerations follow the C philosophy of only paying for what is used, modulo some future work to convince the linker to remove un-accessed @label@ and @value@ arrays, possibly with @weak@ attributes. 174 174 175 175 … … 258 258 \label{s:CFAInheritance} 259 259 260 \CFA Plan-9 inheritance may be used with \CFA enumerations, where Plan-9 inheritance is containment inheritance with implicit un scoping (like a nested unnamed @struct@/@union@ in C).260 \CFA Plan-9 inheritance may be used with \CFA enumerations, where Plan-9 inheritance is containment inheritance with implicit un-scoping (like a nested unnamed @struct@/@union@ in C). 261 261 Containment is nominative: an enumeration inherits all enumerators from another enumeration by declaring an @inline statement@ in its enumerator lists. 262 262 \begin{cfa} … … 280 280 The base type must be consistent between subtype and supertype. 281 281 When an enumeration inherits enumerators from another enumeration, it copies the enumerators' @value@ and @label@, even if the @value@ is auto-initialized. 282 However, the position of the underlying representation is the order of the enumerator in the new enumeration.282 However, the underlying representation's position is the enumerator's order in the new enumeration. 283 283 \begin{cfa} 284 284 enum() E1 { B }; $\C{// B}$ … … 287 287 enum() E4 { A, inline E3, F}; $\C{// A {\color{blue}[\(_{E3}\)} {\color{red}[\(_{E1}\)} B {\color{red}]} {\color{red}[\(_{E2}\)} C D {\color{red}]} E {\color{blue}]} F}$ 288 288 \end{cfa} 289 In th eexample, @B@ is at position 0 in @E1@ and @E3@, but position 1 in @E4@ as @A@ takes position 0 in @E4@.289 In this example, @B@ is at position 0 in @E1@ and @E3@, but position 1 in @E4@ as @A@ takes position 0 in @E4@. 290 290 @C@ is at position 0 in @E2@, 1 in @E3@, and 2 in @E4@. 291 291 @D@ is at position 1 in @E2@, 2 in @E3@, and 3 in @E4@. … … 331 331 332 332 As discussed in \VRef{s:OpaqueEnum}, \CFA chooses position as a representation of a \CFA enumeration variable. 333 When a cast or implicit conversion moves an enumeration from subtype to supertype, the position can be unchanged or increase .333 When a cast or implicit conversion moves an enumeration from subtype to supertype, the position can be unchanged or increased. 334 334 \CFA determines the position offset with an \newterm{offset calculation} function. 335 335 … … 368 368 The algorithm iterates over the members in @dst@ to find @src@. 369 369 If a member is an enumerator of @dst@, the positions of all subsequent members are incremented by one. 370 If the current member is @dst@, the function returns true indicating \emph{found} and the accumulated offset.370 If the current member is @dst@, the function returns true, indicating \emph{found} and the accumulated offset. 371 371 Otherwise, the algorithm recurses into the current @CFAEnum@ @m@ to check if its @src@ is convertible to @m@. 372 372 If @src@ is convertible to the current member @m@, this means @src@ is a subtype-of-subtype of @dst@. … … 378 378 \section{Control Structures} 379 379 380 Enumerators can be used in multiplecontexts.380 Enumerators are used in various contexts. 381 381 In most programming languages, an enumerator is implicitly converted to its value (like a typed macro substitution). 382 However, enumerator synonyms and typed enumerations make this implicit conversion to value incorrect in some contexts.383 In these contexts, a programmer's intuition assumes an implicit conversion to position.382 However, in some contexts, enumerator synonyms and typed enumerations make this implicit conversion to value incorrect. 383 A programmer's intuition assumes an implicit conversion to position in these contexts. 384 384 385 385 For example, an intuitive use of enumerations is with the \CFA @switch@/@choose@ statement, where @choose@ performs an implicit @break@ rather than a fall-through at the end of a @case@ clause. … … 442 442 \end{cfa} 443 443 The enumeration type is syntax sugar for looping over all enumerators and assigning each enumerator to the loop index, whose type is inferred from the range type. 444 The prefix @+~=@ or @-~=@ iterate forward or backward sthrough the inclusive enumeration range, where no prefix defaults to @+~=@.444 The prefix @+~=@ or @-~=@ iterate forward or backward through the inclusive enumeration range, where no prefix defaults to @+~=@. 445 445 446 446 C has an idiom for @if@ and loop predicates of comparing the predicate result ``not equal to 0''. … … 449 449 while ( p /* != 0 */ ) ... 450 450 \end{cfa} 451 This idiom extends to enumerations because there is a boolean conversion in terms of the enumeration value,if and only if such a conversion is available.451 This idiom extends to enumerations because there is a boolean conversion regarding the enumeration value if and only if such a conversion is available. 452 452 For example, such a conversion exists for all numerical types (integral and floating-point). 453 453 It is possible to explicitly extend this idiom to any typed enumeration by overloading the @!=@ operator. … … 482 482 \end{cfa} 483 483 \footnotetext{C uses symbol \lstinline{'='} for designator initialization, but \CFA changes it to \lstinline{':'} because of problems with tuple syntax.} 484 This approach is also necessary for a predefined typed enumeration (unchangeable) , when additional secondary-information needto be added.484 This approach is also necessary for a predefined typed enumeration (unchangeable) when additional secondary information needs to be added. 485 485 The array subscript operator, namely @?[?]@, is overloaded so that when a \CFA enumerator is used as an array index, it implicitly converts to its position over value to sustain data harmonization. 486 486 This behaviour can be reverted by explicit overloading: -
doc/theses/jiada_liang_MMath/Cenum.tex
r175a750e r0bda8d7 3 3 \CFA supports legacy C enumeration using the same syntax for backward compatibility. 4 4 A C-style enumeration in \CFA is called a \newterm{C Enum}. 5 The semantics of the C Enum ismostly consistent with C with some restrictions.5 The semantics of the C Enum are mostly consistent with C with some restrictions. 6 6 The following sections detail all of my new contributions to enumerations in C. 7 7 … … 52 52 enum RGB @!@ { Red, Green, Blue }; 53 53 \end{cfa} 54 Now the enumerators \emph{must} be qualified with the associated enumeration type.54 Now, the enumerators \emph{must} be qualified with the associated enumeration type. 55 55 \begin{cfa} 56 56 Week week = @Week.@Mon; -
doc/theses/jiada_liang_MMath/relatedwork.tex
r175a750e r0bda8d7 497 497 498 498 To indirectly enumerate, \Csharp's Enum library provides @Enum.GetValues@, 499 % a pseudo-method that retrieves an array of the enumeration constants for looping over an enumeration type or variable (expensive operation).500 499 a static member of abstract Enum type that return a reference to an array of all enumeration constants. 501 Internally, a Enum type has a static member called @fieldInfoHash@ -- a @Hashtable@ that stores enumerators information.500 Internally, an Enum type has a static member called @fieldInfoHash@ -- a @Hashtable@ that stores information about enumerators. 502 501 The field is populated on-demand: it only contains information if a @reflection@ like @GetValues@ is called. 503 502 As an optimization, this information is cached, so the cost of reflection is paid once throughout the lifetime of a program. … … 539 538 const V = 3.1; const W = 3.1; 540 539 \end{Go} 541 Since these declarations are immutable variables, they are unscoped and Go has no overloading. If no type declarationprovided, Go infers540 These declarations defined immutable and unscoped variables, and Go has no naming overloading. If no type declaration is provided, Go infers 542 541 type from the initializer expression. 543 542 … … 552 551 subsequent identifiers can be implicitly or explicitly initialized. 553 552 Implicit initialization always uses the \emph{previous} (predecessor) constant expression initializer. 554 A constant block can still use explicit declarations, and following constants inherit that type.553 A constant block can still use explicit declarations, and the following constants inherit that type. 555 554 \begin{Go} 556 555 type BigInt int64 … … 559 558 const ( S @int@ = 0; T; USA @string@ = "USA"; U; V @float32@ = 3.1; W ) 560 559 \end{Go} 561 Typing the first constant and implicit initializing is still not a enumeration because there is no unique type for the constant block;562 nothing stops other constant blocks from havingthe same type.560 Typing the first constant and implicit initializing is still not an enumeration because there is no unique type for the constant block; 561 Nothing stops other constant blocks from being of the same type. 563 562 564 563 Each @const@ declaration provides an implicit \emph{compile-time} integer counter starting at @0@, called \lstinline[language=Go]{iota}, which is post-incremented after each constant declaration. … … 643 642 Week day = Week.Sat; 644 643 \end{Java} 645 The enumerator's members are scoped requiring qualification.644 The enumerator's members are scoped, requiring qualification. 646 645 The value of an enumeration instance is restricted to its enumerators. 647 646 … … 722 721 @EnumSet@ is enumerable because it extends @AbstractSet@ interfaces and thus supports direct enumerating via @forEach@. 723 722 It also has subset operation @range@ and it is possible to add to and remove from members of the set. 724 @EnumSet@ supports more enumeration features, but it is not an enumeration type : it is a set of enumerators from a pre-defineenum.723 @EnumSet@ supports more enumeration features, but it is not an enumeration type; it is a set of enumerators from a pre-defined enum. 725 724 726 725 An enumeration type cannot declare an array dimension nor can an enumerator be used as a subscript. … … 841 840 % However, there is no mechanism to iterate through an enumeration without casting to integral and positions versus values is not handled. 842 841 Like C/\CC, there is no mechanism to iterate through an enumeration. 843 It can only be approximated by a loop over a range of enumerator and only works if the enumerator values are a sequence of natural numbers.842 It can only be approximated by a loop over a range of enumerators and only works if the enumerator values are a sequence of natural numbers. 844 843 \begin{c++} 845 844 for d in Week::Mon as isize ..= Week::Sun as isize { … … 913 912 % for integral types, there is auto-incrementing. 914 913 As well, it is possible to type associated values of enumeration cases with a common type. 915 When enumeration cases are typed with a common integral type, Swift auto-initialize enumeration cases following the same initialization scheme as C language.914 When enumeration cases are typed with a common integral type, Swift auto-initializes enumeration cases following the same initialization scheme as C language. 916 915 If an enumeration is typed with @string@, its cases are auto-initialized to case names (labels). 917 916 \begin{cquote} … … 965 964 \end{cquote} 966 965 Enumerating is accomplished by inheriting from @CaseIterable@ protocol, which has a static @enum.@ @allCases@ property that returns a collection of all the cases for looping over an enumeration type or variable. 967 Like \CFA, Swift's default enumerator output is the case name (label). An enumerator of a typed enumeration has a ttribute966 Like \CFA, Swift's default enumerator output is the case name (label). An enumerator of a typed enumeration has an attribute 968 967 @rawValue@ that return its case value. 969 968 \begin{swift} … … 1015 1014 % Conversion from @rawValue@ to enumerator may fail (bad lookup), so the result is an optional value. 1016 1015 In the previous example, the initialization of @opt@ fails if there is no enumeration value equal to 0, resulting in a @nil@ value. 1017 Initialization from a raw value is considered a expensive operation because it requires a value lookup.1016 Initialization from a raw value is considered an expensive operation because it requires a value lookup. 1018 1017 1019 1018 … … 1040 1039 Mon : 1 Tue : 2 Wed : 3 Thu : 10 Fri : !11! Sat : 4 Sun : !12! 1041 1040 \end{python} 1042 @auto@ is controlled by member @_generate_next_value_()@, which by default return one plus the highest value among enumerators, and can be overridden:1041 @auto@ is controlled by member @_generate_next_value_()@, which by default returns one plus the highest value among enumerators, and can be overridden: 1043 1042 \begin{python} 1044 1043 @staticmethod … … 1061 1060 it is not an ADT because the enumerator names are not constructors. 1062 1061 1063 An enumerator initialized with the same value is an alias and invisible at the enumeration level, \ie the alias is substituted for its aliase e.1062 An enumerator initialized with the same value is an alias and invisible at the enumeration level, \ie the alias is substituted for its aliases. 1064 1063 \begin{python} 1065 1064 class WeekD(Enum): Mon = 1; Tue = 2; Wed = 3; Thu = !10!; Fri = !10!; Sat = !10!; Sun = !10! -
doc/theses/jiada_liang_MMath/trait.tex
r175a750e r0bda8d7 18 18 44 44 19 19 \end{c++} 20 The @std::is_enum@ and other \CC @traits@ are acompile-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.20 The @std::is_enum@ and other \CC @traits@ are 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 assertions to be satisfied by a polymorphic type. 22 22 23 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. … … 35 35 \end{cfa} 36 36 \newpage 37 Trait @CfaEnum@ defines attribute functions @label@ and @posn@ for all \CFA enumerations, and internally \CFA enumerations fulfill sthis assertion.37 Trait @CfaEnum@ defines attribute functions @label@ and @posn@ for all \CFA enumerations, and internally \CFA enumerations fulfill this assertion. 38 38 \begin{cfa} 39 39 forall( E ) trait CfaEnum { … … 55 55 For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows a generalized enumeration formatter for any enumeration type. 56 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 printingthe value (payload) of the enumerator.58 Hence, enumeration defines how its value appear and @format_enum@ displays this value within the label name.57 The trait for @format_enum@ requires a function named @str@ to print the value (payload) of the enumerator. 58 Hence, enumeration defines how its value appears, and @format_enum@ displays this value within the label name. 59 59 60 60 \begin{figure} … … 113 113 Here, @concept@ is referring directly to types with kind @enum@; 114 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 restrictionallowing only the specified kinds of types and rejecting others.115 Hence, the @concept@ is the first level of restriction, allowing only the specified kinds of types and rejecting others. 116 116 The template expansion is the second level of restriction verifying if the type passing the @concept@ test provides the necessary functionality. 117 117 Hence, a @concept@ is querying precise aspects of the programming language set of types. 118 118 119 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.120 Hence, the \CFA enumeration traits are never connected with the specific @enum@ kind. 121 121 Instead, anything that can look like the @enum@ kind is considered an enumeration (static structural typing). 122 122 However, Scala, Go, and Rust traits are nominative: a type explicitly declares a named trait to be of its type, while in \CFA, any type implementing all requirements declared in a trait implicitly satisfy its restrictions. … … 144 144 Fruit last_fruit = upperBound(); $\C{// Cherry}$ 145 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.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 side of an assignment expression. 147 147 Calling either function without a context results in a type ambiguity, unless the type environment has only one type overloading the functions. 148 148 \begin{cfa} … … 177 177 Function @fromInstance@ or a position cast using @(int)@ is always safe, \ie within the enumeration range. 178 178 179 Function @Countof@ is the generic counterpart to the built in pseudo-function @countof@.179 Function @Countof@ is the generic counterpart to the built-in pseudo-function @countof@. 180 180 @countof@ only works on enumeration types and instances, so it is locked into the language type system; 181 181 as such, @countof( enum-type)@ becomes a compile-time constant. 182 @Countof@ works on an any type that matches the @Serial@ trait.182 @Countof@ works on any type that matches the @Serial@ trait. 183 183 Hence, @Countof@ does not use its argument; 184 184 only the parameter type is needed to compute the range size. … … 197 197 If such an enumeration @E@ exists, replace @countof( E )@ with the number of enumerators. 198 198 \item Look for a non-enumeration type named @E@ that defines @Countof@ and @lowerBound@, including @E@ being a polymorphic type, such as @forall( E )@. 199 If type @E@ exists, replace sit with @Countof(lowerBound())@, where @lowerBound@ is defined for type @E@.199 If type @E@ exists, replace it with @Countof(lowerBound())@, where @lowerBound@ is defined for type @E@. 200 200 \item Look for an enumerator @A@ defined in enumeration @E@. 201 201 If such an enumerator @A@ exists, replace @countof( A )@ with the number of enumerators in @E@. 202 \item Look for a name @A@ in the lexical context with t ype @E@.203 If such name @A@ exists, replace @countof( A )@ withfunction call @Countof( E )@.202 \item Look for a name @A@ in the lexical context with the type @E@. 203 If the name @A@ exists, replace @countof( A )@ with a function call @Countof( E )@. 204 204 \item If 1-4 fail, report a type error on expression @countof( E )@. 205 205 \end{enumerate} … … 209 209 210 210 The fundamental aspect of an enumeration type is the ability to enumerate over its enumerators. 211 \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 \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 transitions to @while@ loop. 212 212 213 213 … … 216 216 A for-loop consists of loop control and body. 217 217 The loop control is often a 3-tuple: initializers, looping condition, and advancement. 218 It is a common practice to declare one or more loop-index variables in initializers, determineswhether the variables satisfy the loop condition, and update the variables in advancement.218 It is a common practice to declare one or more loop-index variables in initializers, whether the variables satisfy the loop condition, and update the variables in advancement. 219 219 Such a variable is called an \newterm{index} and is available for reading and writing within the loop body. 220 220 (Some languages make the index read-only in the loop body.) … … 239 239 for ( E e = lowerBound(); e <= upperBound(); e = succ( e ) ) {} 240 240 \end{cfa} 241 Both of these loops look correct but fail because the se 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 Both of these loops look correct but fail because there 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. 242 242 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 has at least one enumerator. 243 243 … … 272 272 273 273 \CFA overloads the comparison operators for \CFA enumeration satisfying traits @Serial@ and @CfaEnum@. 274 These definitions require the operand types be the sameand the appropriate comparison is made using the the positions of the operands.274 These definitions require the operand types to be the same, and the appropriate comparison is made using the the positions of the operands. 275 275 \begin{cfa} 276 276 forall( E | CfaEnum( E ) | Serial( E ) ) @{@ $\C{// distribution block}$ … … 284 284 @}@ 285 285 \end{cfa} 286 (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 eliminate dtedious repeated qualification.286 (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 eliminates tedious repeated qualification. 287 287 Distribution blocks can be nested.) 288 288 289 289 \CFA implements a few arithmetic operators for @CfaEnum@. 290 290 % Unlike advancement functions in @Serial@, these operators perform direct arithmetic, so there is no implicit bound checks. 291 Bound checks are added to these operations to ensure the outputs fulfill sthe @Bounded@ invariant.291 Bound checks are added to these operations to ensure the outputs fulfill the @Bounded@ invariant. 292 292 \begin{cfa} 293 293 forall( E | CfaEnum( E ) | Serial( E ) ) { $\C{// distribution block}$ … … 312 312 } 313 313 \end{cfa} 314 which effectively turns the first enumeration to a logical @false@ and @true@ for the others.314 which effectively turns the first enumeration into a logical @false@ and @true@ for the others.
Note: See TracChangeset
for help on using the changeset viewer.
