source: doc/theses/jiada_liang_MMath/intro.tex @ 2325b57

\chapter{Introduction}

All basic types in a programming language have a set of constants (symbols), and these constants represent computable values, \eg integer types have constants @-1@, @17@, @0xff@ representing whole numbers, floating-point types have constants @5.3@, @2.3E-5@, @0xff.ffp0@ representing real numbers, character types have constants @'a'@, @"abc\n"@, \mbox{\lstinline{u8"}\texttt{\guillemotleft{na\"{i}ve}\guillemotright}\lstinline{"}} representing (human readable) text, \etc.
Constants can be overloaded among types, \eg @0@ is a null pointer for all pointer types, and the value zero for integer and floating-point types.
(In \CFA, the constants @0@ and @1@ can be overloaded for any type.)
Higher-level types compose constants from the basic constants.
\begin{cfa}
struct S { int i, j, k; } s;
s = (S){ 1, 2, 3 };                             $\C[2in]{// structure constant}$
int x[5] = { 1, 2, 3, 4, 5 };   $\C{// array constant}\CRT$
\end{cfa}
A constant's symbolic name is dictated by language syntax related to types, \eg @5.@ (double), @5.0f@ (float), @5l@ (long double).
In general, the representation of a constant's value is \newterm{opaque}, so the internal representation can be chosen arbitrarily, \eg two's complement, IEEE floating-point.
In theory, there is an infinite set of constant names per type representing an infinite set of values.

It is common in mathematics, engineering, and computer science to alias new constants to existing constants so they have the same value, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), K(k), M, G, T for powers of 2\footnote{Overloaded with SI powers of 10.} often prefixing bits (b) or bytes (B), \eg Gb, MB, and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc.
An alias can bind to another alias, which transitively binds it to the specified constant.
Multiple aliases can represent the same value, \eg eighth note and quaver, giving synonyms.

Many programming languages capture this important software-engineering capability through a mechanism called \newterm{constant} or \newterm{literal} naming, where a new constant is aliased to an existing constant.
Its purpose is for readability: replacing constant values in a program with symbolic names that are more meaningful to programmers in the context of the application.
Thereafter, associating a name to a different value automatically distributes this rebinding, preventing errors.
Because an aliased 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.}.
In theory, there is an infinite set of possible aliasing; in practice, the number of aliasing per program is finite and small.

Aliased constants 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.
In this case, the binding between a constant name and value can be implicit, where the values are chosen to support any set operations.
Many programming languages capture the aliasing and ordering 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 (aliases) must be unique, and instances of an enumerated type are \emph{often} restricted to hold only these names.

It is possible to enumerate among set names without having an ordering among the set values.
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}
A set can have a partial or total ordering, making it possible to compare set elements, \eg Monday is before Tuesday and Tuesday 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 ) ) ... // weekdays
\end{cfa}
Here the values for the set 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 new constants, which are implicitly or explicitly assigned values that must be appropriate for any set operations, \eg increasing order.
This aspect differentiates an enumeration from general types with an infinite set of constants.
\end{sloppypar}
\item
The alias names are constants, which follow transitively from their binding to other constants.
\item
Defines a type for generating instances (variables).
\item
For safety, an enumeration instance should be restricted to hold only its constant names.
\item
There is a mechanism for \emph{enumerating} over the enumeration 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 new constants, and the term \newterm{enumerator} represents an arbitrary alias name \see{\VRef{s:CEnumeration} for the name derivations}.
An enumerated type can have the following properties: \newterm{label} (name), \newterm{order} (position), and \newterm{value} (payload).
\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 constants @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 implicitly/explicitly assigned constant to support any enumeration operations;
the value may be hidden (opaque) or visible.

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 feature 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 aliasing (renaming).
\begin{cfa}
const Size = 20, Pi = 3.14159, Name = "Jane";
\end{cfa}
The alias name is logically replaced in the program text by its matching constant.
It is possible to compare aliases, if the constants allow it, \eg @Size < Pi@, whereas @Pi < Name@ might be disallowed depending on the language.

Aliasing is \emph{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 new name is part of the language, and hence, participates fully, such as name overloading in the type system.
Aliasing is not an immutable variable.
\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 requires 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 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 to enumerate.
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 initialize and access the value using dynamic pattern-matching.
\begin{cquote}
\setlength{\tabcolsep}{20pt}
\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 associated 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 meanings 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}}.
Here, the type (and possibly the position for equivalent types) is used to discriminate the specific \emph{variant} within the variant instance.
For example, \VRef[Figure]{f:C++variant} shows the \CC equivalent of the two Haskell ADT types using variant types.
In these languages, the variant cannot be used to simulate an enumeration.
Hence, in this work the term variant is not a synonym for ADT.

\begin{figure}
\begin{c++}
struct S { char s[32]; };
variant< int, double, S > vd;
variant< int, int, int > vs;

// discrimination based on type
vd = 3;
if ( holds_alternative<int>(vd) ) cout << "int " << get<int>(vd ) << endl;
vd = 3.5;
if ( holds_alternative<double>(vd) ) cout << "double " << get<double>(vd) << endl;
vd = (S){ "abc" };
if ( holds_alternative<S>(vd) ) cout << "S.s " << get<S>(vd).s << endl;

// discrimination based on type and position within type
vs = (variant<int,int,int>){ in_place_index<0>, 12 };
if ( vs.index() == 0 ) cout << "posn 0 " << get<0>(vs) << endl;
vs = (variant<int,int,int>){ in_place_index<1>, 4 };
if ( vs.index() == 1 ) cout << "posn 1 " << get<1>(vs) << endl;
vs = (variant<int,int,int>){ in_place_index<2>, 5 };
if ( vs.index() == 2 ) cout << "posn 2 " << get<2>(vs) << endl;
\end{c++}
\caption{\CC \lstinline[language=C++]{variant} Discrimination Using RTTI/Position}
\label{f:C++variant}
\end{figure}

% 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}.
In terms of functional programming linguistics, enumerations often refer to a @unit type@ ADT, which is a set with the @nil@ value carrying no information.
The unit type is different from type @void@ in C, because @void@ has no value, which is an empty set.
Hence, @void@ is a C annotation that nothing is expected in this place.
For example, a function that takes a @void@ parameter and returns a @void@ is a function that expects no parameters and returns nothing.
\begin{cfa}
void foo( void );
foo(); $\C{// no arguments and no result}$
\end{cfa}
Because of this distinction, it is impossible to have a variable of type @void@, to assign a @void@ value, or have a function taking and returning multiple @void@s.
\begin{cfa}
void v;                 $\C{// disallowed}$
v = void;
[ void, void ] bar( void, void );
\end{cfa}
Programming languages often use an empty parameter list to imply no value and no return type for empty return.
\begin{cfa}
[] bar(); $\C{// \CFA empty/empty prototype}$
\end{cfa}
However, C is saddled with an empty parameter list meaning a list of unknown type parameters, \ie @var_arg@, which is changed to @void@ in \CC/\CFA.
As a result, a function that returns @void@ cannot be used as a parameter of a function that expects no parameter.
\begin{cfa}
void foo( void );
foo( @foo()@ );         $\C{// void argument does not match with void parameter}$
\end{cfa}

This issue arose when simulating an ADT using a \CC @variant@: @void@ cannot be used as an empty variant.
To solve this problem, \CC introduced @std::monstate@~\cite{C++monstate}, a type that can be instantiated as a value but holds no information.
A similar approximation in C is to define a @struct@ type with no fields.
\begin{cfa}
struct Unit {} e;               $\C{// empty type}$
Unit bar( Unit );
bar( @bar( e )@ );
\end{cfa}
Because @std::monostate@ and @Unit@ are user-defined types versus part of the type system, they are only an approximation to @unit@ because other @unit@ types can be defined.

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 associated types. The @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 provide enumerating operations @succ@, @pred@, @enumFrom@, @enumFromTo@.
\VRef[Figure]{f:HaskellEnumeration} shows enumeration comparison and iterating (enumerating).

\begin{figure}
\begin{cquote}
\setlength{\tabcolsep}{40pt}
\begin{tabular}{@{}ll@{}}
\begin{haskell}
day = Tue
main = do
        if day == Tue then
                print day
        else
                putStr "not Tue"
        print (enumFrom Mon)            $\C[2.25in]{-- week}$
        print (enumFromTo Mon Fri)      $\C{-- weekday}$
        print (enumFromTo Sat Sun)      $\C{-- weekend}\CRT$
\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.
In contrast, an enumeration may be constructed using the ADT mechanism, but it is so restricted it is not 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 contributions of this work are:
\begin{enumerate}
\item
safety: Define a safe enumeration conversion scheme, both for C and \CFA, and replace ad-hoc C idioms with safer software-engineering approaches.
\item
overloading: Provide a pattern to overload functions, literals, and variables for polymorphic enumerations using the \CFA type system.
\item
scoping: Add a namespace for enumerations and qualified access into the namespace to deal with the naming problem.
\item
generalization: Support all language types for enumerators with associated values providing enumeration constants for any type.
\item
reuse: Implement subset and containment inheritance for enumerations.
\item
control flow: Extend control-flow structures making it safer and easier to enumerate over an enumeration.
\item
I/O: Provide input and output of enumerations based on enumerator names.
\end{enumerate}


\begin{comment}
Date: Wed, 1 May 2024 13:41:58 -0400
Subject: Re: Enumeration
To: "Peter A. Buhr" <pabuhr@uwaterloo.ca>
From: Gregor Richards <gregor.richards@uwaterloo.ca>

I think I have only one comment and one philosophical quibble to make:

Comment: I really can't agree with putting MB in the same category as the
others. MB is both a quantity and a unit, and the suggestion that MB *is* one
million evokes the rather disgusting comparison 1MB = 1000km.  Unit types are
not in the scope of this work.

Philosophical quibble: Pi *is* 3.14159...etc. Monday is not 0; associating
Monday with 0 is just a consequence of the language. The way this is written
suggests that the intentional part is subordinate to the implementation detail,
which seems backwards to me. Calling the number "primary" and the name
"secondary" feels like you're looking out from inside of the compiler, instead
of looking at the language from the outside. And, calling secondary values
without visible primary values "opaque"-which yes, I realize is my own term
;)-suggests that you insist that the primary value is a part of the design, or
at least mental model, of the program. Although as a practical matter there is
some system value associated with the constructor/tag of an ADT, that value is
not part of the mental model, and so calling it "primary" and calling the name
"secondary" and "opaque" seems either (a) very odd or (b) very C-biased. Or
both.

With valediction,
  - Gregor Richards


Date: Thu, 30 May 2024 23:15:23 -0400
Subject: Re: Meaning?
To: "Peter A. Buhr" <pabuhr@uwaterloo.ca>
CC: <ajbeach@uwaterloo.ca>, <j82liang@uwaterloo.ca>
From: Gregor Richards <gregor.richards@uwaterloo.ca>

I have to disagree with this being agreeing to disagree, since we agree
here. My core point was that it doesn't matter whether you enumerate over the
names or the values. This is a distinction without a difference in any case
that matters. If any of the various ways of looking at it are actually
different from each other, then that's because the enumeration has failed to be
an enumeration in some other way, not because of the actual process of
enumeration. Your flag enum is a 1-to-1 map of names and values, so whether you
walk through names or walk through values is not an actual distinction. It
could be distinct in the *order* that it walks through, but that doesn't
actually matter, it's just a choice that has to be made. Walking through entire
range of machine values, including ones that aren't part of the enumeration,
would be bizarre in any case.

Writing these out has crystallized some thoughts, albeit perhaps not in a way
that's any help to y'all. An enumeration is a set of names; ideally an ordered
set of names. The state of enumerations in programming languages muddies things
because they often expose the machine value underlying those names, resulting
in a possibly ordered set of names and a definitely ordered set of values. And,
muddying things further, because those underlying values are exposed, enums are
used in ways that *depend* on the underlying values being exposed, making that
a part of the definition. But, an enumeration is conceptually just *one* set,
not both. So much of the difficulty is that you're trying to find a way to make
a concept that should be a single set agree with an implementation that's two
sets. If those sets have a 1-to-1 mapping, then who cares, they're just
aliases. It's the possibility of the map being surjective (having multiple
names for the same underlying values) that breaks everything. Personally, I
think that an enum with aliases isn't an enumeration anyway, so who cares about
the rest; if you're not wearing the gourd as a shoe, then it's not an
enumeration.

With valediction,
  - Gregor Richards
\end{comment}