Context Navigation

-                      rc148966
+                      r4da9142
 \chapter{Introduction}
+All types in a programming language must have a set of constants, and these constants have \Newterm{primary names}, \eg integral types have constants @-1@, @17@, @12345@, \etc.
+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.
+All types in a programming language must have a set of constants, and these constants have \Newterm{primary names}, \eg integral types have constants @-1@, @17@, @0xff@, floating-point types have constants @5.3@, @2.3E-5@, @0xff.ffp0@, character types have constants @'a'@, @"abc\n"@, \mbox{\lstinline{u8"}\texttt{\guillemotleft{na\"{i}ve}\guillemotright}\lstinline{"}}, \etc.
+Con\-stants 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.
+(In \CFA, the primary constants @0@ and @1@ can be overloaded for any type.)
 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.
 \Newterm{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.
+\Newterm{Secondary naming} is a common practice in mathematics, engineering and computer science, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MB (mega byte, 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@.
+(The names the thing.)
+Its common purpose is to eliminate duplication of the primary constant throughout a program.
+For example, the secondary name replaces its primary name, thereafter changing the binding of the secondary to primary name automatically distributes the rebinding throughout the program.
+In some cases, secondary naming is \Newterm{opaque}, 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.}.
 …
 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}
+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{OEDenumerate}
 \end{quote}
 Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are restricted to hold only the secondary names.
+Within an enumeration set, the enumeration names must be unique, and instances of an enumerated type are \emph{often} restricted to hold only the secondary names.
 It is possible to enumerate among set names without having an ordering among the set elements.
 For example, the week, the weekdays, the weekend, and every second day of the week.
 …
 for ( cursor in Mon, Tue, Wed, Thu, Fri, Sat, Sun } ... $\C[3.75in]{// week}$
 for ( cursor in Mon, Tue, Wed, Thu, Fri } ...   $\C{// weekday}$
 for ( cursor in Thu, Fri } ...                                  $\C{// weekend}$
+for ( cursor in Sat, Sun } ...                                  $\C{// weekend}$
 for ( cursor in Mon, Wed, Fri, Sun } ...                $\C{// every second day of week}\CRT$
 \end{cfa}
 This independence from internal representation allows multiple names to have the same representation (eight note, quaver), giving synonyms.
+This independence from internal representation allows multiple names to have the same representation (eighth note, quaver), giving synonyms.
 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.
 Ordering allows iterating among the enumeration set using relational operators and advancement, \eg
 …
 for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ...
 \end{cfa}
+Here the internal representations for the secondary names are \emph{generated} rather than listing a subset of names.
+Here the internal representations for the secondary names are logically \emph{generated} rather than listing a subset of names.
+Hence, the fundamental aspects of an enumeration are:
+\begin{enumerate}
+\item
+It defines a type from which instants can be generated.
+\item
+The type lists a finite set of secondary names, which become its primary constants.
+This differentiates an enumeration from general types with an infinite number of primary constants.
+\item
+An enumeration's secondary names represent constants, which follows from their binding (aliasing) to primary names, which are constants.
+\item
+For safety, an enumeration instance is restricted to hold only its type's secondary names.
+\item
+There is a mechanism for \emph{enumerating} over the secondary names, where the ordering can be implicit from the type, explicitly listed, or generated arithmetically.
+\end{enumerate}
 \section{Terminology}
+The term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name.
+\label{s:Terminology}
+The term \Newterm{enumeration} defines a type with a set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name \see{\VRef{s:CEnumeration}}.
 As well, an enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}.
 \begin{cquote}
 …
 \section{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}
+In both cases, it is possible to compare the secondary names, \eg @Size < Pi@, if that is meaningful;
+however, without an enumeration type-name, it is impossible to create an iterator cursor.
+Secondary renaming can similate an enumeration, but with extra effort.
+Some programming languages only provide direct secondary renaming.
+\begin{cfa}
+const Size = 20, Pi = 3.14159, Name = "Jane";
+\end{cfa}
+Here, it is possible to compare the secondary names, \eg @Size < Pi@, if that is meaningful.
+Secondary renaming can simulate 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.
+Any reordering of the enumerators requires manual renumbering.
 \begin{cfa}
 const Sun = 1, Mon = 2, Tue = 3, Wed = 4, Thu = 5, Fri = 6, Sat = 7;
 \end{cfa}
 Finally, there is no common type to create a type-checked instance or iterator cursor.
 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}
+Finally, there is no type to create a type-checked instance or iterator cursor.
+Hence, there is only a weak equivalence between secondary naming and enumerations, justifying a seperate enumeration type in a programming language.
+A variant (algebraic) type is often promoted as a kind of enumeration, \ie a variant type can simulate an enumeration.
+Fundamentally, a variant type is a tagged-union, where the tag is normally opaque and the types are usually heterogeneous.
+\begin{cfa}[morekeywords={variant}]
 @variant@ Variant {
         @int tag;@  // optional/implicit: 0 => int, 1 => double, 2 => 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 a tag and runtime checking is unnecessary;
+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.
+The tag can be implicitly set by the compiler on assignment, or explicitly set by the program\-mer.
+Type pattern-matching is then used to dynamically test the tag and branch to a section of code to safely manipulate the value, \eg:
+Crucially, the union implies instance storage is shared by all the variant types, and therefore, before a variant type can be used in a statically-typed expression, it must be dynamically discriminated to its current contained type.
+Hence, 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 a tag and runtime checking is unnecessary.
+Otherwise, a tag is required to denote the particular type in the variant, and the tag is discriminated at runtime using some form of type pattern-matching, after which the value can be used in a statically-typed expression.
+A less frequent variant case is multiple variants with the same type, which normally requires explicit naming of the tag to disambiguate among the common types.
+\begin{cquote}
+\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
+\begin{cfa}[morekeywords={variant}]
+variant VariantCT {
+        case @car@: int i;  // explicitly typed
+        case @boat@: int i;
+        case @bridge@: int i;
+};
+\end{cfa}
+&
+\begin{cfa}[morekeywords={variant}]
+variant VariantCU {
+        case @car@: ;  // empty or unit type
+        case @boat@: ;
+        case @bridge@: ;
+};
+\end{cfa}
+\end{tabular}
+\end{cquote}
+Here, the explicit tag name is used to give different meaning to the values in the common @int@ type, \eg the value 3 has different interpretations depending on the tag name.
+It is even possible to remove the type or use the empty @unit@ type (@struct unit {}@).
+It is this tag naming that is used to simulate an enumeration.
+Normally, the variant tag is implicitly set by the compiler based on type, but with common types, a tag name is required to resolve type ambiguity.
+\begin{cfa}
+Variant v = 3;                                                  $\C{// implicitly set tag to 0 based on type of 3}$
+VariantCT ve = boats.3;                                 $\C{// explicitly set tag to 1 using tag name}$
+\end{cfa}
+Type pattern-matching is then used to dynamically test the tag and branch to a section of statically-typed code to safely manipulate the value, \eg:
+\begin{cquote}
+\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
 \begin{cfa}[morekeywords={match}]
+Variant v = 3;  // implicitly set tag to 0
+@match@( 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 */ }
+@match@( v ) { // know type implicitly or test tag
+        case int { /* only access i field */ }
+        case double { /* only access d field */ }
+        case S { /* only access s field */ }
+}
 \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 \emph{re-purposed} for either ordering or value and the variant types are omitted.
+\begin{cfa}
+variant Weekday {
+        int tag; // implicit 0 => Mon, ..., 6 => Sun
+        @case Mon;@ // no type
+&
+\begin{cfa}[morekeywords={match}]
+@match@( ve ) {
+        case car: int { /* car interpretation */ }
+        case boat: int { /* boat interpretation */ }
+        case bridge: int { /* bridge interpretation */ }
+}
+\end{cfa}
+\end{tabular}
+\end{cquote}
+For safety, some languages require all variant types to be listed or a @default@ case with no field accesses.
+To further strengthen the simulate for an enumeration with different values, each variant type can be a @const@ type or the tag becomes non-opaque, possibly taking advantage of the opaque auto-numbering.
+\begin{cquote}
+\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
+\begin{cfa}
+variant Week {
+        case Mon: const int = 0;
         ...
+        @case Sun;@
+};
+\end{cfa}
+The type system ensures tag setting and testing are correctly done.
+However, the enumeration operations are limited to the available tag operations, \eg pattern matching.
+\begin{cfa}
+Week week = Mon;
+if ( @dynamic_cast(Mon)@week ) ... // test tag == Mon
+\end{cfa}
+        case Sat: const int = 5;
+        case Sun: const int = 10;
+};
+\end{cfa}
+&
+\begin{cfa}
+variant Week {
+        case Mon: ;  // tag auto-numbering
+        ...
+        case Sat: ;
+        case @Sun = 10@: ; // directly set tag value
+};
+\end{cfa}
+\end{tabular}
+\end{cquote}
+Directly setting the tag implies restrictions, like unique values.
+In both cases, instances of @Week@ are @const@ (immutable).
+However, usage between these two types becomes complex.
+\begin{cfa}
+Week day = Week.Mon;  // sets value or tag depending on type
+if ( day == Week.Mon )   // dereference value or tag ?
+\end{cfa}
+Here, the dereference of @day@ should return the value of the type stored in the variant, never the tag.
+If it does return the tag, some special meaning must be given to the empty/unit type, especially if a variant contains both regular and unit types.
+In general, the enumeration simulation and the variant extensions to support it, are deviating from the normal use of a variant (union) type.
+As well, the enumeration operations are limited to the available tag operations, \eg pattern matching.
 While enumerating among tag names is possible:
 \begin{cfa}[morekeywords={in}]
+for ( cursor in 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, also requires pattern matching.
+\begin{cfa}[morekeywords={match}]
+for ( cursor = Mon; cursor <= Fri; cursor = succ( cursor) ) {
+        match( cursor ) {
+                case Mon { /* access special type for Mon */ }
+                ...
+                case Fri { /* access special type for Fri */ }
+                default
+        }
+}
+\end{cfa}
+If the variant type is changed by adding/removing types or the loop range changes, the pattern matching must be adjusted.
+As well, if the start/stop values are dynamic, it may be impossible to statically determine if all variant types are listed.
+Re-purposing the notion of enumerating into variant types is ill formed and confusing.
+Hence, there is only a weak equivalence between an enumeration and variant type, justifying the enumeration type in a programming language.
+for ( cursor in Week.Mon, Week.Wed, Week.Fri, Week.Sun ) ...
+\end{cfa}
+what is the type of @cursor@?
+If it the tag type (@int@), how is this value used?
+If it is the variant type, where is the instance variable, which only contains one value.
+Hence, either enumerating with a variant enumeration is disallowed or some unusual typing rule must be invented to make it work but only in restricted contexts.
+While functional programming systems regularly re-purposing variant types into enumeration types, this process seems contrived and confusing.
+A variant tag is not an enumeration, it is a discriminant among a restricted set of types stored in a storage block.
+Hence, there is only a weak equivalence between an enumeration and variant type, justifying a seperate enumeration type in a programming language.

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

Context Navigation

Changeset 4da9142 for doc/theses/jiada_liang_MMath/intro.tex

Legend:

doc/theses/jiada_liang_MMath/intro.tex

Download in other formats: