source: doc/theses/jiada_liang_MMath/intro.tex @ 48b76d03

\chapter{Introduction}

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 for all pointer types, and the value 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.

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.}.

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.
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 week, the weekdays, the weekend, and every second day of the week.
\begin{cfa}[morekeywords={in}]
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 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.
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
\begin{cfa}
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.


\section{Terminology}

The term \Newterm{enumeration} defines the set of secondary names, and the term \Newterm{enumerator} represents an arbitrary secondary name.
As well, an enumerated type has three fundamental properties, \Newterm{label}, \Newterm{order}, and \Newterm{value}.
\begin{cquote}
\sf\setlength{\tabcolsep}{3pt}
\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 = 42      & \};   \\
\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             & 42            &
\end{tabular}
\end{cquote}
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.
The value is the constant represented by the secondary name, which can be implicitly or explicitly set.

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.


\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.
\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}
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}
@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 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:
\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 */ }
}
\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 variant 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}[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}
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 adds/removes types or the loop range changes, the pattern matching must be adjusted.
As well, 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 an enumeration 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.

\begin{enumerate}
\item
overloading
\item
scoping
\item
typing
\item
subset
\item
inheritance
\end{enumerate}