Changeset 0bda8d7


Ignore:
Timestamp:
Sep 15, 2024, 7:53:45 PM (4 weeks ago)
Author:
JiadaL <j82liang@…>
Branches:
master
Children:
c329bca, eaeba79
Parents:
175a750e
Message:

Small updates

Location:
doc/theses/jiada_liang_MMath
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/jiada_liang_MMath/CFAenum.tex

    r175a750e r0bda8d7  
    136136\section{Implementation}
    137137
    138 \CFA-cc is is a transpiler translating \CFA code into C, which is compiled by a C compiler.
    139 During transpilation, \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.
     139During 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.
    140140For example:
    141141\begin{cfa}
     
    157157Therefore, a \CFA enumeration variable has the same underlying representation as its generated C enumeration.
    158158This 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 eliminated the two arrays if unused, either by \CFA if local to a translation unit and unused, or by the linker if global but unreferenced.
     159It 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.
    160160Also, 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.
     161Hence, 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.
    162162
    163163Along with the enumeration definition, \CFA-cc generates definitions of the attribute functions, @posn@, @label@ and @value@, for each enumeration:
     
    171171Note, 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.
    172172Finally, 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 unaccessed @label@ and @value@ arrays, possibly with @weak@ attributes.
     173Hence, 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.
    174174
    175175
     
    258258\label{s:CFAInheritance}
    259259
    260 \CFA Plan-9 inheritance may be used with \CFA enumerations, where Plan-9 inheritance is containment inheritance with implicit unscoping (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).
    261261Containment is nominative: an enumeration inherits all enumerators from another enumeration by declaring an @inline statement@ in its enumerator lists.
    262262\begin{cfa}
     
    280280The base type must be consistent between subtype and supertype.
    281281When 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.
     282However, the underlying representation's position is the enumerator's order in the new enumeration.
    283283\begin{cfa}
    284284enum() E1 { B };                                                                        $\C{// B}$
     
    287287enum() 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}$
    288288\end{cfa}
    289 In the example, @B@ is at position 0 in @E1@ and @E3@, but position 1 in @E4@ as @A@ takes position 0 in @E4@.
     289In this example, @B@ is at position 0 in @E1@ and @E3@, but position 1 in @E4@ as @A@ takes position 0 in @E4@.
    290290@C@ is at position 0 in @E2@, 1 in @E3@, and 2 in @E4@.
    291291@D@ is at position 1 in @E2@, 2 in @E3@, and 3 in @E4@.
     
    331331
    332332As 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.
     333When a cast or implicit conversion moves an enumeration from subtype to supertype, the position can be unchanged or increased.
    334334\CFA determines the position offset with an \newterm{offset calculation} function.
    335335
     
    368368The algorithm iterates over the members in @dst@ to find @src@.
    369369If 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.
     370If the current member is @dst@, the function returns true, indicating \emph{found} and the accumulated offset.
    371371Otherwise, the algorithm recurses into the current @CFAEnum@ @m@ to check if its @src@ is convertible to @m@.
    372372If @src@ is convertible to the current member @m@, this means @src@ is a subtype-of-subtype of @dst@.
     
    378378\section{Control Structures}
    379379
    380 Enumerators can be used in multiple contexts.
     380Enumerators are used in various contexts.
    381381In 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.
     382However, in some contexts, enumerator synonyms and typed enumerations make this implicit conversion to value incorrect.
     383A programmer's intuition assumes an implicit conversion to position in these contexts.
    384384
    385385For 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.
     
    442442\end{cfa}
    443443The 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 backwards through the inclusive enumeration range, where no prefix defaults to @+~=@.
     444The prefix @+~=@ or @-~=@ iterate forward or backward through the inclusive enumeration range, where no prefix defaults to @+~=@.
    445445
    446446C has an idiom for @if@ and loop predicates of comparing the predicate result ``not equal to 0''.
     
    449449while ( p /* != 0 */  ) ...
    450450\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.
     451This idiom extends to enumerations because there is a boolean conversion regarding the enumeration value if and only if such a conversion is available.
    452452For example, such a conversion exists for all numerical types (integral and floating-point).
    453453It is possible to explicitly extend this idiom to any typed enumeration by overloading the @!=@ operator.
     
    482482\end{cfa}
    483483\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 need to be added.
     484This approach is also necessary for a predefined typed enumeration (unchangeable) when additional secondary information needs to be added.
    485485The 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.
    486486This behaviour can be reverted by explicit overloading:
  • doc/theses/jiada_liang_MMath/Cenum.tex

    r175a750e r0bda8d7  
    33\CFA supports legacy C enumeration using the same syntax for backward compatibility.
    44A C-style enumeration in \CFA is called a \newterm{C Enum}.
    5 The semantics of the C Enum is mostly consistent with C with some restrictions.
     5The semantics of the C Enum are mostly consistent with C with some restrictions.
    66The following sections detail all of my new contributions to enumerations in C.
    77
     
    5252enum RGB @!@ { Red, Green, Blue };
    5353\end{cfa}
    54 Now the enumerators \emph{must} be qualified with the associated enumeration type.
     54Now, the enumerators \emph{must} be qualified with the associated enumeration type.
    5555\begin{cfa}
    5656Week week = @Week.@Mon;
  • doc/theses/jiada_liang_MMath/relatedwork.tex

    r175a750e r0bda8d7  
    497497
    498498To 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).
    500499a 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.
     500Internally, an Enum type has a static member called @fieldInfoHash@ -- a @Hashtable@ that stores information about enumerators.
    502501The field is populated on-demand: it only contains information if a @reflection@ like @GetValues@ is called.
    503502As an optimization, this information is cached, so the cost of reflection is paid once throughout the lifetime of a program.
     
    539538const V = 3.1;  const W = 3.1;
    540539\end{Go}
    541 Since these declarations are immutable variables, they are unscoped and Go has no overloading. If no type declaration provided, Go infers
     540These declarations defined immutable and unscoped variables, and Go has no naming overloading. If no type declaration is provided, Go infers
    542541type from the initializer expression.
    543542
     
    552551subsequent identifiers can be implicitly or explicitly initialized.
    553552Implicit 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.
     553A constant block can still use explicit declarations, and the following constants inherit that type.
    555554\begin{Go}
    556555type BigInt int64
     
    559558const ( S @int@ = 0; T; USA @string@ = "USA"; U; V @float32@ = 3.1; W )
    560559\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 having the same type.
     560Typing the first constant and implicit initializing is still not an enumeration because there is no unique type for the constant block;
     561Nothing stops other constant blocks from being of the same type.
    563562
    564563Each @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.
     
    643642Week day = Week.Sat;
    644643\end{Java}
    645 The enumerator's members are scoped requiring qualification.
     644The enumerator's members are scoped, requiring qualification.
    646645The value of an enumeration instance is restricted to its enumerators.
    647646
     
    722721@EnumSet@ is enumerable because it extends @AbstractSet@ interfaces and thus supports direct enumerating via @forEach@.
    723722It 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-define enum.
     723@EnumSet@ supports more enumeration features, but it is not an enumeration type; it is a set of enumerators from a pre-defined enum.
    725724
    726725An enumeration type cannot declare an array dimension nor can an enumerator be used as a subscript.
     
    841840% However, there is no mechanism to iterate through an enumeration without casting to integral and positions versus values is not handled.
    842841Like 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.
     842It 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.
    844843\begin{c++}
    845844for d in Week::Mon as isize ..= Week::Sun as isize {
     
    913912% for integral types, there is auto-incrementing.
    914913As 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.
     914When enumeration cases are typed with a common integral type, Swift auto-initializes enumeration cases following the same initialization scheme as C language.
    916915If an enumeration is typed with @string@, its cases are auto-initialized to case names (labels).
    917916\begin{cquote}
     
    965964\end{cquote}
    966965Enumerating 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 attribute
     966Like \CFA, Swift's default enumerator output is the case name (label). An enumerator of a typed enumeration has an attribute
    968967@rawValue@ that return its case value.
    969968\begin{swift}
     
    10151014% Conversion from @rawValue@ to enumerator may fail (bad lookup), so the result is an optional value.
    10161015In 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.
     1016Initialization from a raw value is considered an expensive operation because it requires a value lookup.
    10181017
    10191018
     
    10401039Mon : 1 Tue : 2 Wed : 3 Thu : 10 Fri : !11! Sat : 4 Sun : !12!
    10411040\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:
    10431042\begin{python}
    10441043@staticmethod
     
    10611060it is not an ADT because the enumerator names are not constructors.
    10621061
    1063 An enumerator initialized with the same value is an alias and invisible at the enumeration level, \ie the alias is substituted for its aliasee.
     1062An enumerator initialized with the same value is an alias and invisible at the enumeration level, \ie the alias is substituted for its aliases.
    10641063\begin{python}
    10651064class 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  
    181844 44
    1919\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.
     20The @std::is_enum@ and other \CC @traits@ are 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 assertions to be satisfied by a polymorphic type.
    2222
    2323The following sections cover the underlying implementation features I created to generalize and restrict enumerations in the \CFA type-system using the @trait@ mechanism.
     
    3535\end{cfa}
    3636\newpage
    37 Trait @CfaEnum@ defines attribute functions @label@ and @posn@ for all \CFA enumerations, and internally \CFA enumerations fulfills this assertion.
     37Trait @CfaEnum@ defines attribute functions @label@ and @posn@ for all \CFA enumerations, and internally \CFA enumerations fulfill this assertion.
    3838\begin{cfa}
    3939forall( E ) trait CfaEnum {
     
    5555For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows a generalized enumeration formatter for any enumeration type.
    5656The 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.
     57The trait for @format_enum@ requires a function named @str@ to print the value (payload) of the enumerator.
     58Hence, enumeration defines how its value appears, and @format_enum@ displays this value within the label name.
    5959
    6060\begin{figure}
     
    113113Here, @concept@ is referring directly to types with kind @enum@;
    114114other @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.
     115Hence, the @concept@ is the first level of restriction, allowing only the specified kinds of types and rejecting others.
    116116The template expansion is the second level of restriction verifying if the type passing the @concept@ test provides the necessary functionality.
    117117Hence, a @concept@ is querying precise aspects of the programming language set of types.
    118118
    119119Alternatively, 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.
     120Hence, the \CFA enumeration traits are never connected with the specific @enum@ kind.
    121121Instead, anything that can look like the @enum@ kind is considered an enumeration (static structural typing).
    122122However, 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.
     
    144144Fruit last_fruit = upperBound();                        $\C{// Cherry}$
    145145\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.
     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 side of an assignment expression.
    147147Calling either function without a context results in a type ambiguity, unless the type environment has only one type overloading the functions.
    148148\begin{cfa}
     
    177177Function @fromInstance@ or a position cast using @(int)@ is always safe, \ie within the enumeration range.
    178178
    179 Function @Countof@ is the generic counterpart to the builtin pseudo-function @countof@.
     179Function @Countof@ is the generic counterpart to the built-in pseudo-function @countof@.
    180180@countof@ only works on enumeration types and instances, so it is locked into the language type system;
    181181as 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.
    183183Hence, @Countof@ does not use its argument;
    184184only the parameter type is needed to compute the range size.
     
    197197If such an enumeration @E@ exists, replace @countof( E )@  with the number of enumerators.
    198198\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, replaces it with @Countof(lowerBound())@, where @lowerBound@ is defined for type @E@.
     199If type @E@ exists, replace it with @Countof(lowerBound())@, where @lowerBound@ is defined for type @E@.
    200200\item Look for an enumerator @A@ defined in enumeration @E@.
    201201If 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 type @E@.
    203 If such name @A@ exists, replace @countof( A )@ with function call @Countof( E )@.
     202\item Look for a name @A@ in the lexical context with the type @E@.
     203If the name @A@ exists, replace @countof( A )@ with a function call @Countof( E )@.
    204204\item If 1-4 fail, report a type error on expression @countof( E )@.
    205205\end{enumerate}
     
    209209
    210210The 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.
    212212
    213213
     
    216216A for-loop consists of loop control and body.
    217217The 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, determines whether the variables satisfy the loop condition, and update the variables in advancement.
     218It 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.
    219219Such a variable is called an \newterm{index} and is available for reading and writing within the loop body.
    220220(Some languages make the index read-only in the loop body.)
     
    239239for ( E e = lowerBound(); e <= upperBound(); e = succ( e ) ) {}
    240240\end{cfa}
    241 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.
     241Both 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.
    242242These 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.
    243243
     
    272272
    273273\CFA overloads the comparison operators for \CFA enumeration satisfying traits @Serial@ and @CfaEnum@.
    274 These definitions require the operand types be the same and the appropriate comparison is made using the the positions of the operands.
     274These definitions require the operand types to be the same, and the appropriate comparison is made using the the positions of the operands.
    275275\begin{cfa}
    276276forall( E | CfaEnum( E ) | Serial( E ) ) @{@ $\C{// distribution block}$
     
    284284@}@
    285285\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 eliminated tedious 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.
    287287Distribution blocks can be nested.)
    288288
    289289\CFA implements a few arithmetic operators for @CfaEnum@.
    290290% 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 fulfills the @Bounded@ invariant.
     291Bound checks are added to these operations to ensure the outputs fulfill the @Bounded@ invariant.
    292292\begin{cfa}
    293293forall( E | CfaEnum( E ) | Serial( E ) ) { $\C{// distribution block}$
     
    312312}
    313313\end{cfa}
    314 which effectively turns the first enumeration to a logical @false@ and @true@ for the others.
     314which effectively turns the first enumeration into a logical @false@ and @true@ for the others.
Note: See TracChangeset for help on using the changeset viewer.