Changeset 48b76d03 for doc


Ignore:
Timestamp:
Mar 24, 2024, 9:12:11 AM (3 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
f5212ca
Parents:
caf2cba
Message:

fine tune justification for enumerations

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/jiada_liang_MMath/intro.tex

    rcaf2cba r48b76d03  
    22
    33All types in a programming language must have a set of constants, and these constants have primary names, \eg integral types have constants @-1@, @17@, @12345@, \etc.
    4 Constants can be overloaded among types, \eg @0@ is a null pointer, and zero for integral and floating-point types.
     4Constants can be overloaded among types, \eg @0@ is a null pointer for all pointer types, and the value zero for integral and floating-point types.
    55Hence, each primary constant has a symbolic name referring to its internal representation, and these names are dictated by language syntax related to types.
    66In theory, there are an infinite set of primary names per type.
    … …  
    1212The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}.
    1313
    14 Secondary names can form an (ordered) set, \eg days of the week, months of a year, floors of a building (basement, ground, 1st), colours in a fan deck (gator-belly blue, sky-blue pink), \etc.
     14Secondary names can form an (ordered) set, \eg days of the week, months of a year, floors of a building (basement, ground, 1st), colours in a rainbow, \etc.
    1515Many programming languages capture these groupings through a mechanism called an \Newterm{enumeration}.
    1616\begin{quote}
    … …  
    2424Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are restricted to its secondary names.
    2525It is possible to enumerate among set names without having an ordering among the set elements.
    26 For example, the days of the week are enumerated Monday to Sunday, the weekdays are Monday to Friday, the weekend is Saturday and Sunday, and every second weekday is Monday, Wednesday, Friday, and Sunday.
     26For example, the week, the weekdays, the weekend, and every second day of the week.
     27\begin{cfa}[morekeywords={in}]
     28for ( cursor in Mon, Tue, Wed, Thu, Fri, Sat, Sun } ... $\C[3.75in]{// week}$
     29for ( cursor in Mon, Tue, Wed, Thu, Fri } ...   $\C{// weekday}$
     30for ( cursor in Thu, Fri } ...                                  $\C{// weekend}$
     31for ( cursor in Mon, Wed, Fri, Sun } ...                $\C{// every second day of week}\CRT$
     32\end{cfa}
    2733This independence from internal representation allows multiple names to have the same representation (eight note, quaver), giving synonyms.
    28 A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday comes before Friday and Friday comes after.
     34A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday is before Friday and Friday is after.
    2935Ordering allows iterating among the enumeration set using relational operators and advancement, \eg
    3036\begin{cfa}
    3137for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ...
    3238\end{cfa}
    33 rather than listing a proper subset of enumeration names.
     39Here the internal representations for the secondary names are \emph{generated} rather than listing a subset of names.
    3440
    35 In this work, the term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name.
    36 An enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}, as shown by this representative enumeration.
     41
     42\section{Terminology}
     43
     44The term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name.
     45As well, an enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}.
    3746\begin{cquote}
    38 \small\sf\setlength{\tabcolsep}{3pt}
     47\sf\setlength{\tabcolsep}{3pt}
    3948\begin{tabular}{rcccccccr}
    4049\it\color{red}enumeration       & \multicolumn{8}{c}{\it\color{red}enumerators} \\
    4150$\downarrow$\hspace*{25pt}      & \multicolumn{8}{c}{$\downarrow$}                              \\
    42 @enum@ Weekday \{                       & Mon,  & Tue,  & Wed,  & Thu,  & Fri,  & Sat,  & Sun   & \};   \\
    43 \it\color{red}label                     & Mon   & Tue   & Wed   & Thu   & Fri   & Sat   & Sun   &               \\
    44 \it\color{red}order                     & 0             & 1             & 2             & 3             & 4             & 5             & 6             &               \\
    45 \it\color{red}value                     & 0             & 1             & 2             & 3             & 4             & 5             & 6             &
     51@enum@ Weekday \{                       & Mon,  & Tue,  & Wed,  & Thu,  & Fri,  & Sat,  & Sun = 42      & \};   \\
     52\it\color{red}label                     & Mon   & Tue   & Wed   & Thu   & Fri   & Sat   & Sun           &               \\
     53\it\color{red}order                     & 0             & 1             & 2             & 3             & 4             & 5             & 6                     &               \\
     54\it\color{red}value                     & 0             & 1             & 2             & 3             & 4             & 5             & 42            &
    4655\end{tabular}
    4756\end{cquote}
    4857Here, the enumeration @Weekday@ defines the enumerator labels @Mon@, @Tue@, @Wed@, @Thu@, @Fri@, @Sat@ and @Sun@.
    4958The implicit ordering implies the successor of @Tue@ is @Mon@ and the predecessor of @Tue@ is @Wed@, independent of any associated enumerator values.
     59The value is the constant represented by the secondary name, which can be implicitly or explicitly set.
     60
    5061Specifying complex ordering is possible:
    5162\begin{cfa}
    … …  
    5667For @E2@, there is the total ordering @A@ $<$ @{B, C}@ $<$ @{D, E}@ $<$ @F@.
    5768Only flat total-ordering among enumerators is considered in this work.
    58 Finally, the values are the same as the ordering, but they can be set independently and be of any type.
    5969
    6070
    61 \section{Enumeration Motivation}
     71\section{Motivation}
    6272
    6373Some programming languages only provide secondary renaming, which can be simulated by an enumeration without ordering.
    … …  
    6676enum { Size = 20, Pi = 3.14159 };   // unnamed enumeration $\(\Rightarrow\)$ no ordering
    6777\end{cfa}
    68 Without a type name, it is impossible to create an iterating cursor.
    69 It is still possible to compare the internal representations, if that is meaningful, \eg @Size < Pi@.
     78In both cases, it is possible to compare the secondary names, \eg @Size < Pi@, if that is meaningful;
     79however, without an enumeration type-name, it is impossible to create an iterator cursor.
    7080
    7181Secondary renaming can similate an enumeration, but with extra effort.
    … …  
    7787const Sun = 1, Mon = 2, Tue = 3, Wed = 4, Thu = 5, Fri = 6, Sat = 7;
    7888\end{cfa}
     89Finally, there is no common type to create a type-checked instance or iterator cursor.
    7990Hence, there is only a weak equivalence between secondary naming and enumerations, justifying the enumeration type in a programming language.
    8091
    … …  
    94105Hence, a variant is dynamically typed, as in a dynamic-typed programming-language, but the set of types is statically bound, similar to some aspects of dynamic gradual-typing~\cite{Gradual Typing}.
    95106Knowing which type is in a variant instance is crucial for correctness.
    96 Occasionally, it is possible to statically determine, all regions where each variant type is used, so no runtime checking is necessary.
    97 Otherwise, a tag is required to denote the particular type in the variant.
    98 The tag can be implicitly set by the compiler on assignment, or explicitly set by the programmer.
    99 Finally, some mechanism is necessary to dynamically test the tag and branch to a section of code to safely manipulate the value, \eg type pattern-matching.
    100 \begin{cfa}
    101 Variant v = 3; // implicitly set tag to 0
    102 switch( v ) { // know the type or test the tag
     107Occasionally, it is possible to statically determine, all regions where each variant type is used, so a tag and runtime checking is unnecessary;
     108otherwise, a tag is required to denote the particular type in the variant and the tag checked at runtime using some form of type pattern-matching.
     109
     110The tag can be implicitly set by the compiler on assignment, or explicitly set by the program\-mer.
     111Type pattern-matching is then used to dynamically test the tag and branch to a section of code to safely manipulate the value, \eg:
     112\begin{cfa}[morekeywords={match}]
     113Variant v = 3;  // implicitly set tag to 0
     114@match@( v ) {    // know the type or test the tag
    103115        case int { /* only access i field in v */ }
    104116        case double { /* only access d field in v */ }
    … …  
    108120For safety, either all variant types must be listed or a @default@ case must exist with no field accesses.
    109121
    110 To simulate an enumeration with a variant, the tag is re-purposed for either ordering or value and the types are omitted.
     122To simulate an enumeration with a variant, the tag is re-purposed for either ordering or value and the variant types are omitted.
    111123\begin{cfa}
    112124variant Weekday {
    … …  
    124136\end{cfa}
    125137While enumerating among tag names is possible:
    126 \begin{cfa}
    127 for ( Mon, Wed, Fri, Sun ) ...
     138\begin{cfa}[morekeywords={in}]
     139for ( cursor in Mon, Wed, Fri, Sun ) ...
    128140\end{cfa}
    129141ordering for iteration would require a \emph{magic} extension, such as a special @enum@ variant, because it has no meaning for a regular variant, \ie @int@ < @double@.
    130142
    131143However, if a special @enum@ variant allows the tags to be heterogeneously typed, ordering must fall back on case positioning, as many types have incomparable values.
    132 Iterating using tag ordering and heterogeneous types, requires pattern matching.
     144Iterating using tag ordering and heterogeneous types, also requires pattern matching.
    133145\begin{cfa}
    134146for ( cursor = Mon; cursor <= Fri; cursor = succ( cursor) ) {
    … …  
    140152}
    141153\end{cfa}
    142 If the variant type or number of loop steps changes, the pattern must be adjusted.
    143 If the start/stop values are dynamic, it is impossible to statically determine if all variant types are listed.
     154If the variant type adds/removes types or the loop range changes, the pattern matching must be adjusted.
     155As well, if the start/stop values are dynamic, it is impossible to statically determine if all variant types are listed.
    144156
    145157Forcing the notion of enumerating into variant types is ill formed and confusing.
    146 Hence, there is only a weak equivalence between enumerations and variant type, justifying the enumeration type in a programming language.
     158Hence, there is only a weak equivalence between an enumeration and variant type, justifying the enumeration type in a programming language.
    147159
    148160
    … …  
    152164On the surface, enumerations seem like a simple type.
    153165However, when extended with advanced features, enumerations become complex for both the type system and the implementation.
     166
     167\begin{enumerate}
     168\item
     169overloading
     170\item
     171scoping
     172\item
     173typing
     174\item
     175subset
     176\item
     177inheritance
     178\end{enumerate}
Note: See TracChangeset for help on using the changeset viewer.