Changeset 48b76d03 for doc/theses
- Timestamp:
- Mar 24, 2024, 9:12:11 AM (4 months ago)
- Branches:
- master
- Children:
- f5212ca
- Parents:
- caf2cba
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/jiada_liang_MMath/intro.tex
rcaf2cba r48b76d03 2 2 3 3 All 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 , andzero for integral and floating-point types.4 Constants 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. 5 5 Hence, each primary constant has a symbolic name referring to its internal representation, and these names are dictated by language syntax related to types. 6 6 In theory, there are an infinite set of primary names per type. … … 12 12 The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}. 13 13 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.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 rainbow, \etc. 15 15 Many programming languages capture these groupings through a mechanism called an \Newterm{enumeration}. 16 16 \begin{quote} … … 24 24 Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are restricted to its secondary names. 25 25 It 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. 26 For example, the week, the weekdays, the weekend, and every second day of the week. 27 \begin{cfa}[morekeywords={in}] 28 for ( cursor in Mon, Tue, Wed, Thu, Fri, Sat, Sun } ... $\C[3.75in]{// week}$ 29 for ( cursor in Mon, Tue, Wed, Thu, Fri } ... $\C{// weekday}$ 30 for ( cursor in Thu, Fri } ... $\C{// weekend}$ 31 for ( cursor in Mon, Wed, Fri, Sun } ... $\C{// every second day of week}\CRT$ 32 \end{cfa} 27 33 This 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.34 A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday is before Friday and Friday is after. 29 35 Ordering allows iterating among the enumeration set using relational operators and advancement, \eg 30 36 \begin{cfa} 31 37 for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ... 32 38 \end{cfa} 33 rather than listing a proper subset of enumerationnames.39 Here the internal representations for the secondary names are \emph{generated} rather than listing a subset of names. 34 40 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 44 The term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name. 45 As well, an enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}. 37 46 \begin{cquote} 38 \s mall\sf\setlength{\tabcolsep}{3pt}47 \sf\setlength{\tabcolsep}{3pt} 39 48 \begin{tabular}{rcccccccr} 40 49 \it\color{red}enumeration & \multicolumn{8}{c}{\it\color{red}enumerators} \\ 41 50 $\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 & 46 55 \end{tabular} 47 56 \end{cquote} 48 57 Here, the enumeration @Weekday@ defines the enumerator labels @Mon@, @Tue@, @Wed@, @Thu@, @Fri@, @Sat@ and @Sun@. 49 58 The implicit ordering implies the successor of @Tue@ is @Mon@ and the predecessor of @Tue@ is @Wed@, independent of any associated enumerator values. 59 The value is the constant represented by the secondary name, which can be implicitly or explicitly set. 60 50 61 Specifying complex ordering is possible: 51 62 \begin{cfa} … … 56 67 For @E2@, there is the total ordering @A@ $<$ @{B, C}@ $<$ @{D, E}@ $<$ @F@. 57 68 Only 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.59 69 60 70 61 \section{ EnumerationMotivation}71 \section{Motivation} 62 72 63 73 Some programming languages only provide secondary renaming, which can be simulated by an enumeration without ordering. … … 66 76 enum { Size = 20, Pi = 3.14159 }; // unnamed enumeration $\(\Rightarrow\)$ no ordering 67 77 \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@.78 In both cases, it is possible to compare the secondary names, \eg @Size < Pi@, if that is meaningful; 79 however, without an enumeration type-name, it is impossible to create an iterator cursor. 70 80 71 81 Secondary renaming can similate an enumeration, but with extra effort. … … 77 87 const Sun = 1, Mon = 2, Tue = 3, Wed = 4, Thu = 5, Fri = 6, Sat = 7; 78 88 \end{cfa} 89 Finally, there is no common type to create a type-checked instance or iterator cursor. 79 90 Hence, there is only a weak equivalence between secondary naming and enumerations, justifying the enumeration type in a programming language. 80 91 … … 94 105 Hence, 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}. 95 106 Knowing 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 107 Occasionally, it is possible to statically determine, all regions where each variant type is used, so a tag and runtime checking is unnecessary; 108 otherwise, 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 110 The tag can be implicitly set by the compiler on assignment, or explicitly set by the program\-mer. 111 Type 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}] 113 Variant v = 3; // implicitly set tag to 0 114 @match@( v ) { // know the type or test the tag 103 115 case int { /* only access i field in v */ } 104 116 case double { /* only access d field in v */ } … … 108 120 For safety, either all variant types must be listed or a @default@ case must exist with no field accesses. 109 121 110 To simulate an enumeration with a variant, the tag is re-purposed for either ordering or value and the types are omitted.122 To simulate an enumeration with a variant, the tag is re-purposed for either ordering or value and the variant types are omitted. 111 123 \begin{cfa} 112 124 variant Weekday { … … 124 136 \end{cfa} 125 137 While enumerating among tag names is possible: 126 \begin{cfa} 127 for ( Mon, Wed, Fri, Sun ) ...138 \begin{cfa}[morekeywords={in}] 139 for ( cursor in Mon, Wed, Fri, Sun ) ... 128 140 \end{cfa} 129 141 ordering 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@. 130 142 131 143 However, 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.144 Iterating using tag ordering and heterogeneous types, also requires pattern matching. 133 145 \begin{cfa} 134 146 for ( cursor = Mon; cursor <= Fri; cursor = succ( cursor) ) { … … 140 152 } 141 153 \end{cfa} 142 If the variant type or number of loop steps changes, the patternmust be adjusted.143 If the start/stop values are dynamic, it is impossible to statically determine if all variant types are listed.154 If the variant type adds/removes types or the loop range changes, the pattern matching must be adjusted. 155 As well, if the start/stop values are dynamic, it is impossible to statically determine if all variant types are listed. 144 156 145 157 Forcing the notion of enumerating into variant types is ill formed and confusing. 146 Hence, there is only a weak equivalence between enumerationsand variant type, justifying the enumeration type in a programming language.158 Hence, there is only a weak equivalence between an enumeration and variant type, justifying the enumeration type in a programming language. 147 159 148 160 … … 152 164 On the surface, enumerations seem like a simple type. 153 165 However, when extended with advanced features, enumerations become complex for both the type system and the implementation. 166 167 \begin{enumerate} 168 \item 169 overloading 170 \item 171 scoping 172 \item 173 typing 174 \item 175 subset 176 \item 177 inheritance 178 \end{enumerate}
Note: See TracChangeset
for help on using the changeset viewer.