Context Navigation

-                      re00b10d
+                      rcaf2cba
 \chapter{Introduction}
+Naming values is a common practice in mathematics and engineering, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MHz (1E6), etc.
+Naming is also commonly used to represent many other numerical phenomenon, such as days of the week, months of a year, floors of a building (basement), specific times (noon, New Years).
+Many programming languages capture this important software engineering capability through a mechanism called an \Newterm{enumeration}.
+An enumeration is similar to other programming-language types by providing a set of constrained values, but adds the ability to name \emph{all} the values in the set.
+Note, all enumeration names must be unique but different names can represent the same value (eight note, quaver), which are synonyms.
+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.
+Constants can be overloaded among types, \eg @0@ is a null pointer, and zero for integral and floating-point types.
+Hence, each primary constant has a symbolic name referring to its internal representation, and these names are dictated by language syntax related to types.
+In theory, there are an infinite set of primary names per type.
+Specifically, an enumerated type restricts its values to a fixed set of named constants.
+While all types are restricted to a fixed set of values because of the underlying von Neumann architecture, and hence, to a corresponding set of constants, \eg @3@, @3.5@, @3.5+2.1i@, @'c'@, @"abc"@, etc., these values are not named, other than the programming-language supplied constant names.
+Secondary naming is a common practice in mathematics and engineering, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MHz (1E6), and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc.
+Many programming languages capture this important software-engineering capability through a mechanism called \Newterm{constant} or \Newterm{literal} naming, where a secondary name is aliased to a primary name.
+In some cases, secondary naming is \Newterm{pure}, where the matching internal representation can be chosen arbitrarily, and only equality operations are available, \eg @O_RDONLY@, @O_WRONLY@, @O_CREAT@, @O_TRUNC@, @O_APPEND@.
+Because a secondary name is a constant, it cannot appear in a mutable context, \eg \mbox{$\pi$ \lstinline{= 42}} is meaningless, and a constant has no address, \ie it is an \Newterm{rvalue}\footnote{
+The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}.
+Fundamentally, all enumeration systems have an \Newterm{enumeration} type with an associated set of \Newterm{enumerator} names.
+An enumeration has three universal attributes, \Newterm{label}, \Newterm{position}, and \Newterm{value}, as shown by this representative enumeration, where position and value can be different.
+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.
+Many programming languages capture these groupings through a mechanism called an \Newterm{enumeration}.
+\begin{quote}
+enumerate (verb, transitive).
+To count, ascertain the number of;
+\emph{more
+usually, to mention (a number of things or persons) separately, as if for the
+purpose of counting};
+to specify as in a list or catalogue.~\cite{OED}
+\end{quote}
+Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are restricted to its secondary names.
+It is possible to enumerate among set names without having an ordering among the set elements.
+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.
+This independence from internal representation allows multiple names to have the same representation (eight note, quaver), giving synonyms.
+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.
+Ordering allows iterating among the enumeration set using relational operators and advancement, \eg
+\begin{cfa}
+for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ...
+\end{cfa}
+rather than listing a proper subset of enumeration names.
+In this work, the term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name.
+An enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}, as shown by this representative enumeration.
 \begin{cquote}
 \small\sf\setlength{\tabcolsep}{3pt}
 \begin{tabular}{rccccccccccc}
 \it\color{red}enumeration & \multicolumn{7}{c}{\it\color{red}enumerators}       \\
 $\downarrow$\hspace*{25pt} & \multicolumn{7}{c}{$\downarrow$}                           \\
 @enum@ Weekday \{                               & Mon,  & Tue,  & Wed,  & Thu,  & Fri,  & Sat,  & Sun \};       \\
 \it\color{red}label                             & Mon   & Tue   & Wed   & Thu   & Fri   & Sat   & Sun           \\
 \it\color{red}position                  & 0             & 1             & 2             & 3             & 4             & 5             & 6                     \\
 \it\color{red}value                             & 0             & 1             & 2             & 3             & 4             & 5             & 6
+\begin{tabular}{rcccccccr}
+\it\color{red}enumeration       & \multicolumn{8}{c}{\it\color{red}enumerators} \\
+$\downarrow$\hspace*{25pt}      & \multicolumn{8}{c}{$\downarrow$}                              \\
+@enum@ Weekday \{                       & Mon,  & Tue,  & Wed,  & Thu,  & Fri,  & Sat,  & Sun   & \};   \\
+\it\color{red}label                     & Mon   & Tue   & Wed   & Thu   & Fri   & Sat   & Sun   &               \\
+\it\color{red}order                     & 0             & 1             & 2             & 3             & 4             & 5             & 6             &               \\
+\it\color{red}value                     & 0             & 1             & 2             & 3             & 4             & 5             & 6             &
 \end{tabular}
 \end{cquote}
+Here, the \Newterm{enumeration} @Weekday@ defines the ordered \Newterm{enumerator}s @Mon@, @Tue@, @Wed@, @Thu@, @Fri@, @Sat@ and @Sun@.
+By convention, the successor of @Tue@ is @Mon@ and the predecessor of @Tue@ is @Wed@, independent of the associated enumerator constant values, implying an ordering among the enumerators.
+As well, the value can be explicitly set so it is different from the position.
+Because an enumerator is a constant, it cannot appear in a mutable context, \eg @Mon = Sun@ is meaningless, and an enumerator has no address, \ie it is an \Newterm{rvalue}\footnote{
+The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}.
+Here, the enumeration @Weekday@ defines the enumerator labels @Mon@, @Tue@, @Wed@, @Thu@, @Fri@, @Sat@ and @Sun@.
+The implicit ordering implies the successor of @Tue@ is @Mon@ and the predecessor of @Tue@ is @Wed@, independent of any associated enumerator values.
+Specifying complex ordering is possible:
+\begin{cfa}
+enum E1 { $\color{red}[\(_1\)$ {A, B}, $\color{blue}[\(_2\)$ C $\color{red}]\(_1\)$, {D, E} $\color{blue}]\(_2\)$ }; $\C{// overlapping square brackets}$
+enum E2 { {A, {B, C} }, { {D, E}, F };  $\C{// nesting}$
+\end{cfa}
+For @E1@, there is the partial ordering among @A@, @B@ and @C@, and @C@, @D@ and @E@, but not among @A@, @B@ and @D@, @E@.
+For @E2@, there is the total ordering @A@ $<$ @{B, C}@ $<$ @{D, E}@ $<$ @F@.
+Only flat total-ordering among enumerators is considered in this work.
+Finally, the values are the same as the ordering, but they can be set independently and be of any type.
-On the surface, enumerations seem like a simple type.
-However, when extended with features available in other language types, enumerations become a complex.
+The goal of this work is to to extend the simple and unsafe enumeration type in the C programming-language into a sophisticated and safe type in the \CFA programming-language, while maintain backwards compatibility with C.
+\section{Enumeration Motivation}
+Some programming languages only provide secondary renaming, which can be simulated by an enumeration without ordering.
+\begin{cfa}
+const Size = 20, Pi = 3.14159;
+enum { Size = 20, Pi = 3.14159 };   // unnamed enumeration $\(\Rightarrow\)$ no ordering
+\end{cfa}
+Without a type name, it is impossible to create an iterating cursor.
+It is still possible to compare the internal representations, if that is meaningful, \eg @Size < Pi@.
+Secondary renaming can similate an enumeration, but with extra effort.
+\begin{cfa}
+const Mon = 1, Tue = 2, Wed = 3, Thu = 4, Fri = 5, Sat = 6, Sun = 7;
+\end{cfa}
+Furthermore, reordering the enumerators requires manual renumbering.
+\begin{cfa}
+const Sun = 1, Mon = 2, Tue = 3, Wed = 4, Thu = 5, Fri = 6, Sat = 7;
+\end{cfa}
+Hence, there is only a weak equivalence between secondary naming and enumerations, justifying the enumeration type in a programming language.
+A variant (algebraic) type is often promoted as a kind of enumeration, \ie a varient type can simulate an enumeration.
+A variant type is a tagged-union, where the possible types may be heterogeneous.
+\begin{cfa}
+@variant@ Variant {
+        @int tag;@  // optional/implicit: 0 => int, 1 => double, 2 => S
+        @union {@ // implicit
+                case int i;
+                case double d;
+                case struct S { int i, j; } s;
+        @};@
+};
+\end{cfa}
+Crucially, the union implies instance storage is shared by all of the variant types.
+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}.
+Knowing which type is in a variant instance is crucial for correctness.
+Occasionally, it is possible to statically determine, all regions where each variant type is used, so no runtime checking is necessary.
+Otherwise, a tag is required to denote the particular type in the variant.
+The tag can be implicitly set by the compiler on assignment, or explicitly set by the programmer.
+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.
+\begin{cfa}
+Variant v = 3; // implicitly set tag to 0
+switch( v ) { // know the type or test the tag
+        case int { /* only access i field in v */ }
+        case double { /* only access d field in v */ }
+        case S { /* only access s field in v */ }
+}
+\end{cfa}
+For safety, either all variant types must be listed or a @default@ case must exist with no field accesses.
+To simulate an enumeration with a variant, the tag is re-purposed for either ordering or value and the types are omitted.
+\begin{cfa}
+variant Weekday {
+        int tag; // implicit 0 => Mon, ..., 6 => Sun
+        @case Mon;@ // no type
+        ...
+        @case Sun;@
+};
+\end{cfa}
+The type system ensures tag setting and testing are correct.
+However, the enumeration operations are limited to the available tag operations, \eg pattern matching.
+\begin{cfa}
+Weekday weekday = Mon;
+if ( @dynamic_cast(Mon)@weekday ) ... // test tag == Mon
+\end{cfa}
+While enumerating among tag names is possible:
+\begin{cfa}
+for ( Mon, Wed, Fri, Sun ) ...
+\end{cfa}
+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@.
+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.
+Iterating using tag ordering and heterogeneous types, requires pattern matching.
+\begin{cfa}
+for ( cursor = Mon; cursor <= Fri; cursor = succ( cursor) ) {
+        switch( cursor ) {
+                case Mon { /* access special type for Mon */ }
+                ...
+                case Fri { /* access special type for Fri */ }
+        }
+}
+\end{cfa}
+If the variant type or number of loop steps changes, the pattern must be adjusted.
+If the start/stop values are dynamic, it is impossible to statically determine if all variant types are listed.
+Forcing the notion of enumerating into variant types is ill formed and confusing.
+Hence, there is only a weak equivalence between enumerations and variant type, justifying the enumeration type in a programming language.
 \section{Contributions}
+The goal of this work is to to extend the simple and unsafe enumeration type in the C programming-language into a sophisticated and safe type in the \CFA programming-language, while maintain backwards compatibility with C.
+On the surface, enumerations seem like a simple type.
+However, when extended with advanced features, enumerations become complex for both the type system and the implementation.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset caf2cba

Legend:

doc/theses/jiada_liang_MMath/intro.tex

Download in other formats: