source: doc/theses/jiada_liang_MMath/intro.tex@ bf4fe05

\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@, @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 constant names per type.

\newterm{Secondary naming} is a common practice in mathematics, engineering and computer science, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), MB (megabyte, 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.
Its purpose is for readability and to eliminate duplication of the primary constant throughout a program.
For example, a meaningful secondary name replaces a primary name throughout a program;
thereafter, changing the binding of the secondary to primary name automatically distributes the rebinding, preventing errors.
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.}.

Secondary names can form an (ordered) set, \eg days of a 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;
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 \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.
\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 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 (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:
\begin{cfa}
for ( cursor = Monday; cursor @<=@ Friday; cursor = @succ@( cursor ) ) ...
\end{cfa}
Here the internal representation 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
\begin{sloppypar}
It provides a finite set of secondary names, which become its primary constants.
This differentiates an enumeration from general types with an infinite set
of primary constants.
\end{sloppypar}
\item
The secondary names are constants, which follows transitively from their binding (aliasing) to primary names, which are constants.
\item
Defines a type for generating instants (variables).
\item
For safety, an enumeration instance should be 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}
\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} for the name derivation}.
As well, an enumerated type can have 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*{15pt}      & \multicolumn{8}{c}{$\downarrow$}                              \\
@enum@ Week \{                          & Mon,  & Tue,  & Wed,  & Thu,  & Fri,  & Sat,  & Sun {\color{red}= 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             & {\color{red}42}               &
\end{tabular}
\end{cquote}
Here, the enumeration @Week@ 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}

Many programming languages provide an enumeration-like mechanism, which may or may not cover the previous five fundamental enumeration aspects.
Hence, the term \emph{enumeration} can be confusing and misunderstood.
Furthermore, some languages conjoin the enumeration with other type features, making it difficult to tease apart which featuring is being used.
This section discusses some language features that are sometimes called an enumeration but do not provide all enumeration aspects.


\subsection{Aliasing}
\label{s:Aliasing}

Some languages provide simple secondary aliasing (renaming), \eg:
\begin{cfa}
const Size = 20, Pi = 3.14159, Name = "Jane";
\end{cfa}
The secondary name is logically replaced in the program text by its corresponding primary name.
Therefore, it is possible to compare the secondary names, \eg @Size < Pi@, only because the primary constants allow it, whereas \eg @Pi < Name@ might be disallowed depending on the language.

Aliasing is not macro substitution, \eg @#define Size 20@, where a name is replaced by its value \emph{before} compilation, so the name is invisible to the programming language.
With aliasing, each secondary name is part of the language, and hence, participates fully, such as name overloading in the type system.
Aliasing is not an immutable variable, \eg:
\begin{cfa}
extern @const@ int Size = 20;
extern void foo( @const@ int @&@ size );
foo( Size ); // take the address of (reference) Size
\end{cfa}
Taking the address of an immutable variable makes it an \newterm{lvalue}, which implies it has storage.
With separate compilation, it is necessary to choose one translation unit to perform the initialization.
If aliasing does require storage, its address and initialization are opaque (compiler only), similar to \CC rvalue reference @&&@.

Aliasing does provide readability and automatic resubstitution.
It also provides simple enumeration properties, but with extra effort.
\begin{cfa}
const Mon = 1, Tue = 2, Wed = 3, Thu = 4, Fri = 5, Sat = 6, Sun = 7;
\end{cfa}
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}
For these reasons, aliasing is sometimes called an enumeration.
However, there is no type to create a type-checked instance or iterator cursor, so there is no ability for enumerating.
Hence, there are multiple enumeration aspects not provided by aliasing, justifying a separate enumeration type in a programming language.


\subsection{Algebraic Data Type}
\label{s:AlgebraicDataType}

An algebraic data type (ADT)\footnote{ADT is overloaded with abstract data type.} is another language feature often linked with enumeration, where an ADT conjoins an arbitrary type, possibly a \lstinline[language=C++]{class} or @union@, and a named constructor.
For example, in Haskell:
\begin{haskell}
data S = S { i::Int, d::Double }                $\C{// structure}$
data @Foo@ = A Int | B Double | C S             $\C{// ADT, composed of three types}$
foo = A 3;                                                              $\C{// type Foo is inferred}$
bar = B 3.5
baz = C S{ i = 7, d = 7.5 }
\end{haskell}
the ADT has three variants (constructors), @A@, @B@, @C@ with associated types @Int@, @Double@, and @S@.
The constructors create an initialized value of the specific type that is bound to the immutable variables @foo@, @bar@, and @baz@.
Hence, the ADT @Foo@ is like a union containing values of the associated types, and a constructor name is used to access the value using dynamic pattern-matching.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}ll@{}}
\begin{haskell}
prtfoo val = -- function
    -- pattern match on constructor
    case val of
      @A@ a -> print a
      @B@ b -> print b
      @C@ (S i d) -> do
          print i
          print d
\end{haskell}
&
\begin{haskell}
main = do
    prtfoo foo
    prtfoo bar
    prtfoo baz
3
3.5
7
7.5
\end{haskell}
\end{tabular}
\end{cquote}
For safety, most languages require all assocaited types to be listed or a default case with no field accesses.

A less frequent case is multiple constructors with the same type.
\begin{haskell}
data Bar = X Int | Y Int | Z Int;
foo = X 3;
bar = Y 3;
baz = Z 5;
\end{haskell}
Here, the constructor name gives different meaning to the values in the common \lstinline[language=Haskell]{Int} type, \eg the value @3@ has different interpretations depending on the constructor name in the pattern matching.

Note, the term \newterm{variant} is often associated with ADTs.
However, there are multiple languages with a @variant@ type that is not an ADT \see{Algol68~\cite{Algol68} or \CC \lstinline{variant}}.
In these languages, the variant is often a union using RTTI tags, which cannot be used to simulate an enumeration.
Hence, in this work the term variant is not a synonym for ADT.

% https://downloads.haskell.org/ghc/latest/docs/libraries/base-4.19.1.0-179c/GHC-Enum.html
% https://hackage.haskell.org/package/base-4.19.1.0/docs/GHC-Enum.html

The association between ADT and enumeration occurs if all the constructors have a unit (empty) type, \eg @struct unit {}@.
Note, the unit type is not the same as \lstinline{void}, \eg:
\begin{cfa}
void foo( void );
struct unit {} u;  // empty type
unit bar( unit );
foo( foo() );        // void argument does not match with void parameter
bar( bar( u ) );   // unit argument does match with unit parameter
\end{cfa}

For example, in the Haskell ADT:
\begin{haskell}
data Week = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving(Enum, Eq, Show)
\end{haskell}
the default type for each constructor is the unit type, and deriving from @Enum@ enforces no other type, @Eq@ allows equality comparison, and @Show@ is for printing.
The nullary constructors for the unit types are numbered left-to-right from $0$ to @maxBound@$- 1$, and provides enumerating operations @succ@, @pred@, @enumFrom@ @enumFromTo@.
\VRef[Figure]{f:HaskellEnumeration} shows enumeration comparison and iterating (enumerating).

\begin{figure}
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}ll@{}}
\begin{haskell}
day = Tue
main = do
    if day == Tue then
        print day
    else
        putStr "not Tue"
    print (enumFrom Mon)            -- week
    print (enumFromTo Mon Fri)   -- weekday
    print (enumFromTo Sat Sun)  -- weekend
\end{haskell}
&
\begin{haskell}
Tue
[Mon,Tue,Wed,Thu,Fri,Sat,Sun]
[Mon,Tue,Wed,Thu,Fri]
[Sat,Sun]





\end{haskell}
\end{tabular}
\end{cquote}
\caption{Haskell Enumeration}
\label{f:HaskellEnumeration}
\end{figure}

The key observation is the dichotomy between an ADT and enumeration: the ADT uses the associated type resulting in a union-like data structure, and the enumeration does not use the associated type, and hence, is not a union.
While the enumeration is constructed using the ADT mechanism, it is so restricted it is not really an ADT.
Furthermore, a general ADT cannot be an enumeration because the constructors generate different values making enumerating meaningless.
While functional programming languages regularly repurpose the ADT type into an enumeration type, this process seems contrived and confusing.
Hence, there is only a weak equivalence between an enumeration and ADT, justifying a separate 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 complex and safe enumeration type in the \CFA programming-language, while maintaining 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 runtime implementation.

The contribution of this work are:
\begin{enumerate}
\item
overloading
\item
scoping
\item
typing
\item
subseting
\item
inheritance
\end{enumerate}