source: doc/proposals/enum.tex@ a55ebcc

\documentclass[12pt]{article}
\usepackage{fullpage,times}
\usepackage{pslatex}                    % reduce size of san serif font
\usepackage{xcolor}
\usepackage{listings}
%\usepackage{array}
\usepackage{graphics}
\usepackage{xspace}
\usepackage{relsize}                                                                    % must be after change to small or selects old size
\usepackage{calc}                                                                               % latex arithmetic

\makeatletter
\renewcommand\section{\@startsection{section}{1}{\z@}{-3.0ex \@plus -1ex \@minus -.2ex}{1.5ex \@plus .2ex}{\normalfont\large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}{-2.75ex \@plus -1ex \@minus -.2ex}{1.25ex \@plus .2ex}{\normalfont\normalsize\bfseries}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}{-2.5ex \@plus -1ex \@minus -.2ex}{1.0ex \@plus .2ex}{\normalfont\normalsize\bfseries}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}{-2.0ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries}}
\renewcommand\subparagraph{\@startsection{subparagraph}{4}{\z@}{-1.5ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries\itshape}}

% Denote newterms in particular font and index them without particular font and in lowercase, e.g., \newterm{abc}.
% The option parameter provides an index term different from the new term, e.g., \newterm[\texttt{abc}]{abc}
% The star version does not lowercase the index information, e.g., \newterm*{IBM}.
\newcommand{\newtermFontInline}{\emph}
\newcommand{\newterm}{\protect\@ifstar\@snewterm\@newterm}
\newcommand{\@newterm}[2][\@empty]{\lowercase{\def\temp{#2}}{\newtermFontInline{#2}}\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi}
\newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}

\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{#1}}}
\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
\newcommand{\LstStringStyle}[1]{{\lst@basicstyle{\lst@stringstyle{#1}}}}
\newcommand{\LstNumberStyle}[1]{{\lst@basicstyle{\lst@numberstyle{#1}}}}

\newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
\newlength{\columnposn}
\setlength{\gcolumnposn}{3in}
\setlength{\columnposn}{\gcolumnposn}
\newcommand{\setgcolumn}[1]{\global\gcolumnposn=#1\global\columnposn=\gcolumnposn}
\newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\LstCommentStyle{#2}}}
\newcommand{\CD}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\LstBasicStyle{#2}}}
\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
\makeatother

\usepackage[ignoredisplayed]{enumitem}  % do not affect trivlist
\setlist{labelsep=1ex}% global
\setlist[itemize]{topsep=0.5ex,parsep=0.25ex,itemsep=0.25ex,listparindent=\parindent,leftmargin=\parindent}% global
\setlist[itemize,1]{label=\textbullet}% local
%\renewcommand{\labelitemi}{{\raisebox{0.25ex}{\footnotesize$\bullet$}}}
\setlist[enumerate]{topsep=0.5ex,parsep=0.25ex,itemsep=0.25ex,listparindent=\parindent}% global
\setlist[enumerate,2]{leftmargin=\parindent,labelsep=*,align=parleft,label=\alph*.}% local
\setlist[description]{topsep=0.5ex,itemsep=0pt,listparindent=\parindent,leftmargin=\parindent,labelsep=1.5ex}

\newenvironment{cquote}{%
        \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=4pt\parsep=0pt\leftmargin=\parindent\rightmargin\leftmargin}%
        \item\relax
}{%
        \endlist
}% cquote

\setlength{\topmargin}{-0.45in}                                                 % move running title into header
\setlength{\headsep}{0.25in}
\setlength{\textheight}{9.0in}

\newcommand{\CFAIcon}{\textsf{C\raisebox{\depth}{\rotatebox{180}A}}} % Cforall icon
\newcommand{\CFA}{\protect\CFAIcon\xspace}                              % CFA symbolic name
\newcommand{\CCIcon}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ icon
\newcommand{\CC}[1][]{\protect\CCIcon{#1}\xspace}               % C++ symbolic name
\newcommand{\Csharp}{C\raisebox{-0.7ex}{\relsize{2}$^\sharp$}\xspace} % C# symbolic name
\newcommand{\PAB}[1]{{\color{red}PAB: #1}}

% \definecolor{mGreen}{rgb}{0,0.6,0}
% \definecolor{mGray}{rgb}{0.5,0.5,0.5}
% \definecolor{mPurple}{rgb}{0.58,0,0.82}
% \definecolor{backgroundColour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{CStyle}{
%    backgroundcolor=\color{backgroundColour},
%    commentstyle=\color{mGreen},
%    keywordstyle=\color{magenta},
        stringstyle=\small\tt,                                  % use typewriter font
%    stringstyle=\color{mPurple},
    columns=fullflexible,
    basicstyle=\small\linespread{0.9}\sf,       % reduce line spacing and use sanserif font
%   basicstyle=\footnotesize,
    breakatwhitespace=false,
%    breaklines=true,
    captionpos=b,
    keepspaces=true,
        escapechar=\$,                                                  % LaTeX escape in CFA code
%    numbers=left,
%    numbersep=5pt,
%    numberstyle=\tiny\color{mGray},
%    showspaces=false,
    showstringspaces=false,
%    showtabs=false,
        showlines=true,                                                 % show blank lines at end of code
    tabsize=5,
    language=C,
        aboveskip=4pt,                                                  % spacing above/below code block
        belowskip=2pt,
        xleftmargin=\parindent,                 % indent code to paragraph indentation
}
\lstset{style=CStyle,moredelim=**[is][\color{red}]{@}{@}}
\lstMakeShortInline@                            % single-character for \lstinline

\begin{document}

\title{\vspace*{-0.5in}Enumeration in \CFA}
\author{Jiada Liang}

\maketitle

\begin{abstract}
An enumeration is a type defining an ordered set of named constant values, where a name abstracts a value, e.g., @PI@ versus @3.145159@.
C restrict an enumeration type to the integral type @signed int@, which \CC support , meaning enumeration names bind to integer constants.
\CFA extends C enumerations to allow all basic and custom types for the enumeration type, like other modern programming languages.
Furthermore, \CFA adds other useful features for enumerations to support better software-engineering practices and simplify program development.
\end{abstract}

\section{Background}

Naming values is a common practice in mathematics and engineering, e.g., $\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), time (noon, New Years).
Many programming languages capture this important 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 its set.
Note, all enumeration names must be unique but different names can represent the same value (eight note, quaver), which are synonyms.

Specifically, an enumerated type is a type whose values are restricted to a fixed set of named constants.
Fundamentally, 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, e.g., @3@, @3.5@, @3.5+2.1i@, @'c'@, @"abc"@, etc.
However, the values for basic types are not named, other than the programming-language supplied constants.


\section{C-Style Enum}

The C-Style enumeration has the following syntax and semantics.
\begin{lstlisting}[label=lst:weekday]
enum Weekday { Monday, Tuesday, Wednesday, Thursday@ = 10@, Friday, Saturday, Sunday };
                $\(\uparrow\)$                                                                        $\(\uparrow\)$
    ${\rm \newterm{enumeration name}}$                                          ${\rm \newterm{enumerator names}}
\end{lstlisting}
Here, the enumeration type @Weekday@ defines the ordered \newterm{enumerator}s @Monday@, @Tuesday@, @Wednesday@, @Thursday@, @Friday@, @Saturday@ and @Sunday@.
The successor of @Tuesday@ is @Monday@ and the predecessor of @Tuesday@ is @Wednesday@.
A C enumeration is implemented by an integral type, with consecutive enumerator values assigned by the compiler starting at zero or the next explicitly initialized value.
For example, @Monday@ to @Wednesday@ have values 0--2 implicitly set by the compiler, @Thursday@ is explicitly set to @10@, and @Friday@ to @Sunday@ have values 11--13 implicitly set by the compiler.

There are 3 attributes for an enumeration: \newterm{position}, \newterm{label}, and \newterm{value}:
\begin{cquote}
\small\sf\setlength{\tabcolsep}{3pt}
\begin{tabular}{rccccccccccc}
@enum@ Weekday \{       & Monday,       & Tuesday,      & Wednesday,    & Thursday=10,  & Friday,       & Saturday,     & Sunday \}; \\
\it position            & 0                     & 1                     & 2                             & 3                             & 4                     & 5                     & 6                     \\
\it label                       & Monday        & Tuesday       & Wednesday             & Thursday              & Friday        & Saturday      & Sunday        \\
\it value                       & 0                     & 1                     & 2                             & {\color{red}10}& 11           & 12            & 13
\end{tabular}
\end{cquote}

The enumerators of an enumeration are unscoped, i.e., enumerators declared inside of an @enum@ are visible in the enclosing scope of the @enum@ type.
Furthermore, there is an implicit bidirectional conversion between an enumeration and integral types.
\begin{lstlisting}[label=lst:enum_scope]
{
        enum Weekday { ... };                           $\C{// enumerators implicitly projected into local scope}$
        Weekday weekday = Monday;
        weekday = Friday;                                       $\C{// weekday == 11}$
        int i = Sunday                                          $\C{// i == 13}$
        weekday = 10000;                                        $\C{// undefined behaviour}$
}
int j = Wednesday;                                              $\C{// ERROR! Wednesday is not declared in this scope}$
\end{lstlisting}

\section{\CFA-Style Enum}

\CFA supports C-Style enumeration using the same syntax and semantics for backwards compatibility.
\CFA also extends C-Style enumeration by adding a number of new features that bring enumerations inline with other modern programming languages.

\subsection{Enumerator Typing}

\CFA extends the enumeration by parameterizing the enumeration with a type for the enumerators, allowing enumerators to be assigned any values from the declared type.
\begin{lstlisting}[label=lst:color]
enum( @char@ ) Currency { Dollar = '$\textdollar$', Euro = '$\texteuro$', Pound = '$\textsterling$'  };
enum( @double@ ) Planet { Venus = 4.87, Earth = 5.97, Mars = 0.642  }; // mass
enum( @char *@ ) Colour { Red = "red", Green = "green", Blue = "blue"  };
enum( @Currency@ ) Europe { Euro = '$\texteuro$', Pound = '$\textsterling$' }; // intersection
\end{lstlisting}
The types of the enumerators are @char@, @double@, and @char *@ and each enumerator is initialized with corresponding type values.
% Only types with a defined ordering can be automatically initialized (see Section~\ref{s:AutoInitializable}).

% An instance of \CFA-enum (denoted as @<enum_instance>@) is a label for the defined enum name.
% The label can be retrieved by calling the function @label( <enum_instance> )@.
% Similarly, the @value()@ function returns the value used to initialize the \CFA-enum.

\subsection{Enumerator Scoping}

A \CFA-enum can be scoped, meaning the enumerator constants are not projected into the enclosing scope.
\begin{lstlisting}
enum Weekday @!@ { /* as above */ };
enum Colour( char * ) @!@ { /* as above */ };
\end{lstlisting}
where the @'!'@ implies the enumerators are \emph{not} projected.
The enumerators of a scoped enumeration are accessed using qualifications, like the fields of an aggregate.
% The syntax of $qualified\_expression$ for \CFA-enum is the following:
% $$<qualified\_expression> := <enum\_type>.<enumerator>$$
\begin{lstlisting}
Weekday weekday = @Weekday.Monday@;             $\C{// qualification}$
Colour colour = @Colour.@Red;
colour = @Colour.@Blue;
\end{lstlisting}

\subsection{Enumeration Pseudo-functions}

Pseudo-functions are function-like operators that do not result in any run-time computations, i.e., like @sizeof@.
Often a call to a pseudo-function is substituted with information extracted from the symbol table at compilation time, like storage size or alignment associated with the underlying architecture..

\subsubsection{Enumerator Attributes}
The attributes of an enumerator are accessed by pseudo-functions @position@, @value@, and @label@.
\begin{lstlisting}
int green_pos = @position@( Colour.Green );     $\C{// 1}$
char * green_value = @value@( Colour.Green ); $\C{// "G"}$
char * green_label = @label@( Colour.Green ); $\C{// "Green"}$
\end{lstlisting}

Enumeration Greek may have more or less enumerators than Letter, but the enumerator values must be from Letter.
Therefore, Greek enumerators are a subset of type Letter and are type compatible with enumeration Letter, but Letter enumerators are not type compatible with enumeration Greek. 

\subsubsection{\lstinline{enumerate()}}

\begin{lstlisting}[label=lst:c_switch]
enum(int) C_ENUM { First, Second, Third = First, Fourth };
int v( C_ENUM e ) {
        switch( e ) {
                case First: return 0; break;
                case Second: return 1; break;
                // case Third: return 2; break;
                // case Fourth: return 3; break;
        };
};
\end{lstlisting}
In the @C_ENUM@ example, @Third@ is an alias of @First@ and @Fourth@ is an alias of @Second@.
Programmers cannot make case branches for @Third@ and @Fourth@ because the switch statement matches cases by the enumerator's value.
Case @First@ and @Third@, or @Second@ and @Fourth@, has duplicate case values.

@enumerate()@ is a pseudo-function that makes the switch statement match by an enumerator instead.
\begin{lstlisting}[label=lst:c_switch_enumerate]
enum(double) C_ENUM { First, Second, Third = First, Fourth };
C_ENUM variable_a = First, variable_b = Second, variable_c = Third, variable_d = Fourth;
int v(C_ENUM e) {
        switch( enumeratate( e ) ) {
                case First: return e; break;
                case Second: return value( e ); break;
                case Third: return label( e ); break;
                case Fourth: return position( e ); break;
        };
};
p(variable_a); // 0
p(variable_b); // 1
p(variable_c); // "Third"
p(variable_d); // 3
\end{lstlisting}


\section{Enumeration Storage}


\subsection{Enumeration Variable}

Although \CFA enumeration captures three different attributes, an enumeration instance does not store all this information.
The @sizeof@ a \CFA enumeration instance is always 4 bytes, the same size as a C enumeration instance (@sizeof( int )@).
It comes from the fact that:
\begin{enumerate}
\item
a \CFA enumeration is always statically typed;
\item
it is always resolved as one of its attributes regarding real usage.
\end{enumerate}
When creating an enumeration instance @colour@ and assigning it with the enumerator @Color.Green@, the compiler allocates an integer variable and stores the position 1.
The invocations of $positions()$, $value()$, and $label()$ turn into calls to special functions defined in the prelude:
\begin{lstlisting}[label=lst:companion_call]
position( green );
>>> position( Colour, 1 ) -> int
value( green );
>>> value( Colour, 1 ) -> T
label( green );
>>> label( Colour, 1) -> char *
\end{lstlisting}
@T@ represents the type declared in the \CFA enumeration defined and @char *@ in the example.
These generated functions are $Companion Functions$, they take an $companion$ object and the position as parameters.


\subsection{Enumeration Data}

\begin{lstlisting}[label=lst:enumeration_backing_data]
enum(T) E { ... };
// backing data
T * E_values;
char ** E_labels;
\end{lstlisting}
Storing values and labels as arrays can sometimes help support enumeration features.
However, the data structures are the overhead for the programs. We want to reduce the memory usage for enumeration support by:
\begin{itemize}
        \item Only generates the data array if necessary
        \item The compilation units share the data structures.
        No extra overhead if the data structures are requested multiple times.
\end{itemize}


\section{Unification}

\subsection{Enumeration as Value}
\label{section:enumeration_as_value}
An \CFA enumeration with base type T can be used seamlessly as T, without explicitly calling the pseudo-function value.
\begin{lstlisting}[label=lst:implicit_conversion]
char * green_value = Colour.Green; // "G"
// Is equivalent to
// char * green_value = value( Color.Green ); "G"
\end{lstlisting}


\subsection{Unification Distance}

\begin{lstlisting}[label=lst:unification_distance_example]
T_2 Foo(T1);
\end{lstlisting}
The @Foo@ function expects a parameter with type @T1@. In C, only a value with the exact type T1 can be used as a parameter for @Foo@. In \CFA, @Foo@ accepts value with some type @T3@ as long as @distance(T1, T3)@ is not @Infinite@.

@path(A, B)@ is a compiler concept that returns one of the following:
\begin{itemize}
        \item Zero or 0, if and only if $A == B$.
        \item Safe, if B can be used as A without losing its precision, or B is a subtype of A.
        \item Unsafe, if B loses its precision when used as A, or A is a subtype of B.
        \item Infinite, if B cannot be used as A. A is not a subtype of B and B is not a subtype of A.
\end{itemize}

For example, @path(int, int)==Zero@, @path(int, char)==Safe@, @path(int, double)==Unsafe@, @path(int, struct S)@ is @Infinite@ for @struct S{}@.
@distance(A, C)@ is the minimum sum of paths from A to C. For example, if @path(A, B)==i@, @path(B, C)==j@, and @path(A, C)=k@, then $$distance(A,C)==min(path(A,B), path(B,C))==i+j$$.

(Skip over the distance matrix here because it is mostly irrelevant for enumeration discussion. In the actual implementation, distance( E, T ) is 1.)

The arithmetic of distance is the following:
\begin{itemize}
        \item $Zero + v= v$, for some value v.
        \item $Safe * k <  Unsafe$, for finite k.
        \item $Unsafe * k < Infinite$, for finite k.
        \item $Infinite + v = Infinite$, for some value v.
\end{itemize}

For @enum(T) E@, @path(T, E)==Safe@ and @path(E,T)==Infinite@. In other words, enumeration type E can be @safely@ used as type T, but type T cannot be used when the resolution context expects a variable with enumeration type @E@.


\subsection{Variable Overloading and Parameter Unification}

\CFA allows variable names to be overloaded. It is possible to overload a variable that has type T and an enumeration with type T.
\begin{lstlisting}[label=lst:variable_overload]
char * green = "Green";
Colour green = Colour.Green; // "G"

void bar(char * s) { return s; }
void foo(Colour c) { return value( c ); }

foo( green ); // "G"
bar( green ); // "Green"
\end{lstlisting}
\CFA's conversion distance helps disambiguation in this overloading. For the function @bar@ which expects the parameter s to have type @char *@, $distance(char *,char *) == Zero$ while $distance(char *, Colour) == Safe$, the path from @char *@ to the enumeration with based type @char *@, \CFA chooses the @green@ with type @char *@ unambiguously. On the other hand, for the function @foo@, @distance(Colour, char *)@ is @Infinite@, @foo@ picks the @green@ with type @char *@.

\subsection{Function Overloading}
Similarly, functions can be overloaded with different signatures. \CFA picks the correct function entity based on the distance between parameter types and the arguments.
\begin{lstlisting}[label=lst:function_overload]
Colour green = Colour.Green;
void foo(Colour c) { sout | "It is an enum"; } // First foo
void foo(char * s) { sout | "It is a string"; } // Second foo
foo( green ); // "It is an enum"
\end{lstlisting}
Because @distance(Colour, Colour)@ is @Zero@ and @distance(char *, Colour)@ is @Safe@, \CFA determines the @foo( green )@ is a call to the first foo.

\subsection{Attributes Functions}
The pseudo-function @value()@ "unboxes" the enumeration and the type of the expression is the underlying type. Therefore, in the section~\ref{section:enumeration_as_value} when assigning @Colour.Green@ to variable typed @char *@, the resolution distance is @Safe@, while assigning @value(Color.Green) to @char *) has resolution distance @Zero@.

\begin{lstlisting}[label=lst:declaration_code]
int s1;
\end{lstlisting}
The generated code for an enumeration instance is simply an int. It is to hold the position of an enumeration. And usage of variable @s1@ will be converted to return one of its attributes: label, value, or position, concerning the @Unification@ rule

% \subsection{Unification and Resolution (this implementation will probably not be used, safe as reference for now)}

% \begin{lstlisting}
% enum Colour( char * ) { Red = "R", Green = "G", Blue = "B"  };
% \end{lstlisting}
% The @EnumInstType@ is convertible to other types.
% A \CFA enumeration expression is implicitly \emph{overloaded} with its three different attributes: value, position, and label.
% The \CFA compilers need to resolve an @EnumInstType@ as one of its attributes based on the current context.

% \begin{lstlisting}[caption={Null Context}, label=lst:null_context]
% {
%       Colour.Green;
% }
% \end{lstlisting}
% In example~\ref{lst:null_context}, the environment gives no information to help with the resolution of @Colour.Green@.
% In this case, any of the attributes is resolvable.
% According to the \textit{precedence rule}, the expression with @EnumInstType@ resolves as @value( Colour.Green )@.
% The @EnumInstType@ is converted to the type of the value, which is statically known to the compiler as @char *@.
% When the compilation reaches the code generation, the compiler outputs code for type @char *@ with the value @"G"@.
% \begin{lstlisting}[caption={Null Context Generated Code}, label=lst:null_context]
% {
%       "G";
% }
% \end{lstlisting}
% \begin{lstlisting}[caption={int Context}, label=lst:int_context]
% {
%       int g = Colour.Green;
% }
% \end{lstlisting}
% The assignment expression gives a context for the EnumInstType resolution.
% The EnumInstType is used as an @int@, and \CFA needs to determine which of the attributes can be resolved as an @int@ type.
% The functions $Unify( T1, T2 ): bool$ take two types as parameters and determine if one type can be used as another.
% In example~\ref{lst:int_context}, the compiler is trying to unify @int@ and @EnumInstType@ of @Colour@.
% $$Unification( int, EnumInstType<Colour> )$$ which turns into three Unification call
% \begin{lstlisting}[label=lst:attr_resolution_1]
% {
%       Unify( int, char * ); // unify with the type of value
%       Unify( int, int ); // unify with the type of position
%       Unify( int, char * ); // unify with the type of label
% }
% \end{lstlisting}
% \begin{lstlisting}[label=lst:attr_resolution_precedence]
% {
%       Unification( T1, EnumInstType<T2> ) {
%               if ( Unify( T1, T2 ) ) return T2;
%               if ( Unify( T1, int ) ) return int;
%               if ( Unify( T1, char * ) ) return char *;
%               Error: Cannot Unify T1 with EnumInstType<T2>;
%       }
% }
% \end{lstlisting}
% After the unification, @EnumInstType@ is replaced by its attributes.

% \begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
% {
%       T2 foo ( T1 ); // function take variable with T1 as a parameter
%       foo( EnumInstType<T3> ); // Call foo with a variable has type EnumInstType<T3>
%       >>>> Unification( T1, EnumInstType<T3> )
% }
% \end{lstlisting}
% % The conversion can work backward: in restrictive cases, attributes of can be implicitly converted back to the EnumInstType.
% Backward conversion:
% \begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
% {
%       enum Colour colour = 1;
% }
% \end{lstlisting}

% \begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
% {
%       Unification( EnumInstType<Colour>, int ) >>> label
% }
% \end{lstlisting}
% @int@ can be unified with the label of Colour.
% @5@ is a constant expression $\Rightarrow$ Compiler knows the value during the compilation $\Rightarrow$ turns it into
% \begin{lstlisting}
% {
%       enum Colour colour = Colour.Green;
% }
% \end{lstlisting}
% Steps:
% \begin{enumerate}
% \item
% identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
% \item
% @unification( EnumInstType<Colour>, int )@: @position( EnumInstType< Colour > )@
% \item
% return the enumeration constant at position 1
% \end{enumerate}
% \begin{lstlisting}
% {
%       enum T (int) { ... } // Declaration
%       enum T t = 1;
% }
% \end{lstlisting}
% Steps:
% \begin{enumerate}
% \item
% identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
% \item
% @unification( EnumInstType<Colour>, int )@: @value( EnumInstType< Colour > )@
% \item
% return the FIRST enumeration constant that has the value 1, by searching through the values array
% \end{enumerate}
% The downside of the precedence rule: @EnumInstType@ $\Rightarrow$ @int ( value )@ $\Rightarrow$ @EnumInstType@ may return a different @EnumInstType@ because the value can be repeated and there is no way to know which one is expected $\Rightarrow$ want uniqueness

% \subsection{Casting}
% Casting an EnumInstType to some other type T works similarly to unify the EnumInstType with T. For example:
% \begin{lstlisting}
% enum( int ) Foo { A = 10, B = 100, C = 1000 };
% (int) Foo.A;
% \end{lstlisting}
% The \CFA-compiler unifies @EnumInstType<int>@ with int, with returns @value( Foo.A )@, which has statically known value 10. In other words, \CFA-compiler is aware of a cast expression, and it forms the context for EnumInstType resolution. The expression with type @EnumInstType<int>@ can be replaced by the compile with a constant expression 10, and optionally discard the cast expression.

% \subsection{Value Conversion}
% As discussed in section~\ref{lst:var_declaration}, \CFA only saves @position@ as the necessary information. It is necessary for \CFA to generate intermediate code to retrieve other attributes.

% \begin{lstlisting}
% Foo a; // int a;
% int j = a;
% char * s = a;
% \end{lstlisting}
% Assume stores a value x, which cannot be statically determined. When assigning a to j in line 2, the compiler @Unify@ j with a, and returns @value( a )@. The generated code for the second line will be
% \begin{lstlisting}
% int j = value( Foo, a )
% \end{lstlisting}
% Similarly, the generated code for the third line is
% \begin{lstlisting}
% char * j = label( Foo, a )
% \end{lstlisting}


\section{Enumerator Initialization}
An enumerator must have a deterministic immutable value, either be explicitly initialized in the enumeration definition, or implicitly initialized by rules.

\subsection{C Enumeration Rule}
A C enumeration has an integral type. If not initialized, the first enumerator implicitly has the integral value 0, and other enumerators have a value equal to its $predecessor + 1$.

\subsection{Auto Initializable}
\label{s:AutoInitializable}


\CFA enumerations have the same rule in enumeration constant initialization.
However, only \CFA types that have defined traits for @zero_t@, @one_t@, and an addition operator can be automatically initialized by \CFA.

Specifically, a type is auto-initializable only if it satisfies the trait @AutoInitializable@:
\begin{lstlisting}
forall(T)
trait AutoInitializable {
        void ?()( T & t, zero_t );
        S ?++( T & t);
};
\end{lstlisting}
An example of a user-defined @AutoInitializable@ is:
\begin{lstlisting}[label=lst:sample_auto_Initializable]
struct Odd { int i; };
void ?()( Odd & t, zero_t ) { t.i = 1; };
Odd ?++( Odd t1 ) { return Odd( t1.i + 2); };
\end{lstlisting}
When the type of an enumeration is @AutoInitializable@, implicit initialization is available.
\begin{lstlisting}[label=lst:sample_auto_Initializable_usage]
enum AutoInitUsage(Odd) {
        A, B, C = 7, D
};
\end{lstlisting}
In the example, no initializer is specified for the first enumeration constant @A@, so \CFA initializes it with the value of @zero_t@, which is 1.
@B@ and @D@ have the values of their $predecessor++$, where @one_t@ has the value 2.
Therefore, the enumeration is initialized as follows:
\begin{lstlisting}[label=lst:sample_auto_Initializable_usage_gen]
enum AutoInitUsage(Odd) {
        A = 1, B = 3, C = 7, D = 9
};
\end{lstlisting}
Note that there is no mechanism to prevent an even value for the direct initialization, such as @C = 6@.

In \CFA, character, integral, float, and imaginary types are all @AutoInitialiable@.
\begin{lstlisting}[label=lst:letter]
enum Alphabet( int ) {
        A = 'A', B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
        a = 'a', b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
};
print( "%c, %c, %c", Alphabet.F, Alphabet.o, Alphabet.z );
>>> F, o, z
\end{lstlisting}
\section{Enumeration Features}
\subsection{Iteration and Range}

It is convenient to iterate over a \CFA enumeration value, e.g.:
\begin{lstlisting}[label=lst:range_functions]
for ( Alphabet alph; Alphabet ) { sout | alph; }
>>> A B C ... D
\end{lstlisting}
The for-loop uses the enumeration type @Alphabet@ its range, and iterates through all enumerators in the order defined in the enumeration.
@alph@ is the iterating enumeration object, which returns the value of an @Alphabet@ in this context according to the precedence rule.

\textbullet\ \CFA offers a shorthand for iterating all enumeration constants:
\begin{lstlisting}[label=lst:range_functions]
for ( Alphabet alph ) { sout | alph; }
>>> A B C ... D
\end{lstlisting}

The following are examples for constructing for-control using an enumeration. Note that the type declaration of the iterating variable is optional, because \CFA can infer the type as EnumInstType based on the range expression, and possibly convert it to one of its attribute types.

\textbullet\ H is implicit up-to exclusive range [0, H).
\begin{lstlisting}[label=lst:range_function_1]
for ( alph; Alphabet.D ) { sout | alph; }
>>> A B C
\end{lstlisting}

\textbullet\ ~= H is implicit up-to inclusive range [0,H].
\begin{lstlisting}[label=lst:range_function_2]
for ( alph; ~= Alphabet.D ) { sout | alph; }
>>> A B C D
\end{lstlisting}

\textbullet\ L ~ H is explicit up-to exclusive range [L,H).
\begin{lstlisting}[label=lst:range_function_3]
for ( alph; Alphabet.B ~ Alphabet.D  ) { sout | alph; }
// for ( Alphabet alph = Alphabet.B; alph < Alphabet.D; alph += 1  ); 1 is one_t
>>> B C
\end{lstlisting}

\textbullet\ L ~= H is explicit up-to inclusive range [L,H].
\begin{lstlisting}[label=lst:range_function_4]
for ( alph; Alphabet.B ~= Alphabet.D  ) { sout | alph; }
>>> B C D
\end{lstlisting}

\textbullet\ L -~ H is explicit down-to exclusive range [H,L), where L and H are implicitly interchanged to make the range down-to.
\begin{lstlisting}[label=lst:range_function_5]
for ( alph; Alphabet.D -~ Alphabet.B  ) { sout | alph; }
>>> D C
\end{lstlisting}

\textbullet\ L -~= H is explicit down-to exclusive range [H,L], where L and H are implicitly interchanged to make the range down-to.
\begin{lstlisting}[label=lst:range_function_6]
for ( alph; Alphabet.D -~= Alphabet.B  ) { sout | alph; }
>>> D C B
\end{lstlisting}

A user can specify the ``step size'' of an iteration. There are two different stepping schemes of enumeration for-loop.
\begin{lstlisting}[label=lst:range_function_stepping]
enum(int) Sequence { A = 10, B = 12, C = 14, D = 16, D  = 18 };
for ( s; Sequence.A ~= Sequence.D ~ 1  ) { sout | alph; }
>>> 10 12 14 16 18
for ( s; Sequence.A ~= Sequence.D; s+=1  ) { sout | alph; }
>>> 10 11 12 13 14 15 16 17 18
\end{lstlisting}
The first syntax is stepping to the next enumeration constant, which is the default stepping scheme if not explicitly specified. The second syntax, on the other hand, is to call @operator+=@ @one_type@ on the @value( s )@. Therefore, the second syntax is equivalent to
\begin{lstlisting}[label=lst:range_function_stepping_converted]
for ( typeof( value(Sequence.A) ) s=value( Sequence.A ); s <= Sequence.D; s+=1  ) { sout | alph; }
>>> 10 11 12 13 14 15 16 17 18
\end{lstlisting}

% \PAB{Explain what each loop does.}

It is also possible to iterate over an enumeration's labels, implicitly or explicitly:
\begin{lstlisting}[label=lst:range_functions_label_implicit]
for ( char * alph; Alphabet )
\end{lstlisting}
This for-loop implicitly iterates every label of the enumeration, because a label is the only valid resolution to @ch@ with type @char *@ in this case.
If the value can also be resolved as the @char *@, you might iterate the labels explicitly with the array iteration.
\begin{lstlisting}[label=lst:range_functions_label_implicit]
for ( char * ch; labels( Alphabet ) )
\end{lstlisting}


% \subsection{Non-uniform Type}
% TODO: Working in Progress, might need to change other sections. Conflict with the resolution right now.

% \begin{lstlisting}
% enum T( int, char * ) {
%        a=42, b="Hello World"
% };
% \end{lstlisting}
% The enum T declares two different types: int and char *. The enumerators of T hold values of one of the declared types.

\subsection{Enumeration Inheritance}

\begin{lstlisting}[label=lst:EnumInline]
enum( char * ) Name { Jack = "Jack", Jill = "Jill" };
enum /* inferred */ Name2 { inline Name, Sue = "Sue", Tom = "Tom" };
\end{lstlisting}
\lstinline{Inline} allows Enumeration Name2 to inherit enumerators from Name1 by containment, and a Name enumeration is a subtype of enumeration Name2. An enumeration instance of type Name can be used where an instance of Name2 is expected.
\begin{lstlisting}[label=lst:EnumInline]
Name Fred;
void f( Name2 );
f( Fred );
\end{lstlisting}
If enumeration A declares @inline B@ in its enumeration body, enumeration A is the "inlining enum" and enumeration B is the "inlined enum".

An enumeration can inline at most one other enumeration. The inline declaration must be placed before the first enumerator of the inlining enum. The inlining enum has all the enumerators from the inlined enum, with the same labels, values, and position.
\begin{lstlisting}[label=lst:EnumInline]
enum /* inferred */ Name2 { inline Name, Sue = "Sue", Tom = "Tom" };
// is equivalent to enum Name2 { Jack = "Jack", Jill="Jill", Sue = "Sue", Tom = "Tom" };
\end{lstlisting}
Name.Jack is equivalent to Name2.Jack. Their attributes are all identical. Opening both Name and Name2 in the same scope will not introduce ambiguity.
\begin{lstlisting}[label=lst:EnumInline]
with( Name, Name2 ) { Jack; } // Name.Jack and Name2.Jack are equivalent. No ambiguity
\end{lstlisting}

\section{Implementation}

\subsection{Static Attribute Expression}
\begin{lstlisting}[label=lst:static_attr]
enum( char * ) Colour {
        Red = "red", Blue = "blue", Green = "green"
};
\end{lstlisting}
An enumerator expression returns its enumerator value as a constant expression with no runtime cost. For example, @Colour.Red@ is equivalent to the constant expression "red", and \CFA finishes the expression evaluation before generating the corresponding C code. Applying a pseudo-function to a constant enumerator expression results in a constant expression as well. @value( Colour.Red )@, @position( Colour. Red )@, and @label( Colour.Red )@ are equivalent to constant expression with char * value "red", int value 0, and char * value "Red", respectively.

\subsection{Runtime Attribute Expression and Weak Referenced Data}
\begin{lstlisting}[label=lst:dynamic_attr]
Colour c;
...
value( c ); // or c
\end{lstlisting}
An enumeration variable c is equivalent to an integer variable with the value of @position( c )@ In Example~\ref{lst:dynamic_attr}, the value of enumeration variable c is unknown at compile time. In this case, the pseudo-function calls are reduced to expression that returns the enumerator values at runtime.

\CFA stores the variables and labels in @const@ arrays to provide runtime lookup for enumeration information.

\begin{lstlisting}[label=lst:attr_array]
const char * Colour_labels [3] = { "Red", "Blue", "Green" };
const char * Colour_values [3] = { "red", "blue", "green" };
\end{lstlisting}
The \CFA compiles transforms the attribute expressions into array access.
\begin{lstlisting}[label=lst:attr_array_access]
position( c ) // c; an integer
value( c ); // Colour_values[c]
label( c ); // Colour_labels[c]
\end{lstlisting}

To avoid unnecessary memory usage, the labels and values array are only generated as needed, and only generate once across all compilation units. By default, \CFA defers the declaration of the label and value arrays until an call to attribute function with a dynamic value. If an attribute function is never called on a dynamic value of an enumerator, the array will never be allocated. Once the arrays are created, all compilation units share a weak reference to the allocation array.

\subsection{Enum Prelude}

\begin{lstlisting}[label=lst:enum_func_dec]
forall( T ) {
        unsigned position( unsigned );
        T value( unsigned );
        char * label( unsigned );
}
\end{lstlisting}
\CFA loads the declaration of enumeration function from the enum.hfa.

\subsection{Internal Representation}

The definition of an enumeration is represented by an internal type called @EnumDecl@. At the minimum, it stores all the information needed to construct the companion object. Therefore, an @EnumDecl@ can be represented as the following:
\begin{lstlisting}[label=lst:EnumDecl]
forall(T)
class EnumDecl {
        T* values;
        char** label;
};
\end{lstlisting}

The internal representation of an enumeration constant is @EnumInstType@.
An @EnumInstType@ has a reference to the \CFA-enumeration declaration and the position of the enumeration constant.
\begin{lstlisting}[label=lst:EnumInstType]
class EnumInstType {
        EnumDecl enumDecl;
        int position;
};
\end{lstlisting}
In the later discussion, we will use @EnumDecl<T>@ to symbolize a @EnumDecl@ parameterized by type T, and @EnumInstType<T>@ is a declared instance of @EnumDecl<T>@.

\begin{lstlisting}[caption={Enum Type Functions}, label=lst:cforall_enum_data]
const T * const values;
const char * label;
int length;
\end{lstlisting}
Companion data are necessary information to represent an enumeration. They are stored as standalone pieces, rather than a structure. Those data will be loaded "on demand".
Companion data are needed only if the according pseudo-functions are called. For example, the value of the enumeration Workday is loaded only if there is at least one compilation that has call $value(Workday)$. Once the values are loaded, all compilations share these values array to reduce memory usage.


% \subsection{(Rework) Companion Object and Companion Function}

% \begin{lstlisting}[caption={Enum Type Functions}, label=lst:cforall_enum_functions]
% forall( T )
% struct Companion {
%       const T * const values;
%                const char * label;
%       int length;
% };
% \end{lstlisting}
% \CFA generates companion objects, an instance of structure that encloses @necessary@ data to represent an enumeration. The size of the companion is unknown at the compilation time, and it "grows" in size to compensate for the @usage@.

% The companion object is singleton across the compilation (investigation).

% \CFA generates the definition of companion functions.
% Because \CFA implicitly stores an enumeration instance as its position, the companion function @position@ does nothing but return the position it is passed.
% Companions function @value@ and @label@ return the array item at the given position of @values@ and @labels@, respectively.
% \begin{lstlisting}[label=lst:companion_definition]
% int position( Companion o, int pos ) { return pos; }
% T value( Companion o, int pos ) { return o.values[ pos ]; }
% char * label( Companion o, int pos ) { return o.labels[ pos ]; }
% \end{lstlisting}
% Notably, the @Companion@ structure definition, and all companion objects, are visible to users.
% A user can retrieve values and labels defined in an enumeration by accessing the values and labels directly, or indirectly by calling @Companion@ functions @values@ and @labels@
% \begin{lstlisting}[label=lst:companion_definition_values_labels]
% Colour.values; // read the Companion's values
% values( Colour ); // same as Colour.values
% \end{lstlisting}

\subsection{Companion Traits (experimental)}
Not sure its semantics yet, and it might replace a companion object.
\begin{lstlisting}[label=lst:companion_trait]
forall(T1) {
        trait Companion(otype T2<otype T1>) {
                T1 value((otype T2<otype T1> const &);
                int position(otype T2<otype T1> const &);
                char * label(otype T2<otype T1> const &);
        }
}
\end{lstlisting}
All enumerations implicitly implement the Companion trait, an interface to access attributes. The Companion can be a data type because it fulfills to requirements to have concrete instances, which are:

\begin{enumerate}
  \item The instance of enumeration has a single polymorphic type.
  \item Each assertion should use the type once as a parameter.
\end{enumerate}

\begin{lstlisting}
enum(int) Weekday {
        Monday=10, Tuesday, ...
};

T value( enum Weekday<T> & this);
int position( enum Weekday<T> & this )
char * label( enum Weekday<T> & this )

trait Companion obj = (enum(int)) Workday.Weekday;
value(obj); // 10
\end{lstlisting}
The enumeration comes with default implementation to the Companion traits functions. The usage of Companion functions would make \CFA allocates and initializes the necessary companion arrays, and return the data at the position represented by the enumeration.
(...)

\subsection{User Define Enumeration Functions}

Companion objects make extending features for \CFA enumeration easy.
\begin{lstlisting}[label=lst:companion_user_definition]
char * charastic_string( Companion o, int position ) {
        return sprintf( "Label: %s; Value: %s", label( o, position ), value( o, position) );
}
printf( charactic_string ( Color, 1 ) );
>>> Label: Green; Value: G
\end{lstlisting}
Defining a function takes a Companion object effectively defines functions for all \CFA enumeration.

The \CFA compiler turns a function call that takes an enumeration instance as a parameter into a function call with a companion object plus a position.
Therefore, a user can use the syntax with a user-defined enumeration function call:
\begin{lstlisting}[label=lst:companion_user_definition]
charactic_string( Color.Green ); // equivalent to charactic_string( Color, 1 )
>>> Label: Green; Value: G
\end{lstlisting}
Similarly, the user can work with the enumeration type itself: (see section ref...)
\begin{lstlisting}[ label=lst:companion_user_definition]
void print_enumerators ( Companion o ) {
        for ( c : Companion o ) {
                sout | label (c) | value( c ) ;
        }
}
print_enumerators( Colour );
\end{lstlisting}


\subsection{Declaration}

The qualified enumeration syntax is dedicated to \CFA enumeration.
\begin{lstlisting}[label=lst:range_functions]
enum (type_declaration) name { enumerator = const_expr, enumerator = const_expr, ... }
\end{lstlisting}
A compiler stores the name, the underlying type, and all enumerators in an @enumeration table@.
During the $Validation$ pass, the compiler links the type declaration to the type's definition.
It ensures that the name of an enumerator is unique within the enumeration body, and checks if all values of the enumerator have the declaration type.
If the declared type is not @AutoInitializable@, \CFA rejects the enumeration definition.
Otherwise, it attempts to initialize enumerators with the enumeration initialization pattern. (a reference to a future initialization pattern section)

\begin{lstlisting}[label=lst:init]
struct T { ... };
void ?{}( T & t, zero_t ) { ... };
void ?{}( T & t, one_t ) { ... };
T ?+?( T & lhs, T & rhs ) { ... };

enum (T) Sample {
        Zero: 0 /* zero_t */,
        One: Zero + 1 /* ?+?( Zero, one_t ) */ , ...
};
\end{lstlisting}
Challenge: \\
The value of an enumerator, or the initializer, requires @const_expr@.
While previously getting around the issue by pushing it to the C compiler, it might not work anymore because of the user-defined types, user-defined @zero_t@, @one_t@, and addition operation.
Might not be able to implement a \emph{correct} static check.

\CFA $autogens$ a Companion object for the declared enumeration.
\begin{lstlisting}[label=lst:companion]
Companion( T ) Sample {
        .values: { 0, 0+1, 0+1+1, 0+1+1+1, ... }, /* 0: zero_t, 1: one_t, +: ?+?{} */
        .labels: { "Zero", "One", "Two", "Three", ...},
        .length: /* number of enumerators */
};
\end{lstlisting}
\CFA stores values as intermediate expressions because the result of the function call to the function @?+?{}(T&, T&)@ is statically unknown to \CFA.
But the result is computed at run time, and the compiler ensures the @values@ are not changed.

\subsection{Qualified Expression}

\CFA uses qualified expression to address the scoping of \CFA-enumeration.
\begin{lstlisting}[label=lst:qualified_expression]
aggregation_name.field;
\end{lstlisting}
The qualified expression is not dedicated to \CFA enumeration.
It is a feature that is supported by other aggregation in \CFA as well, including a C enumeration.
When C enumerations are unscoped, the qualified expression syntax still helps to disambiguate names in the context.
\CFA recognizes if the expression references a \CFA aggregation by searching the presence of @aggregation_name@ in the \CFA enumeration table.
If the @aggregation_name@ is identified as a \CFA enumeration, the compiler checks if @field@ presents in the declared \CFA enumeration.

\subsection{\lstinline{with} Clause/Statement}

Instead of qualifying an enumeration expression every time, the @with@ can be used to expose enumerators to the current scope, making them directly accessible.
\begin{lstlisting}[label=lst:declaration]
enum Color( char * ) { Red="R", Green="G", Blue="B" };
enum Animal( int ) { Cat=10, Dog=20 };
with ( Color, Animal ) {
        char * red_string = Red; // value( Color.Red )
        int cat = Cat; // value( Animal.Cat )
}
\end{lstlisting}
The \lstinline{with} might introduce ambiguity to a scope. Consider the example:
\begin{lstlisting}[label=lst:declaration]
enum Color( char * ) { Red="R", Green="G", Blue="B" };
enum RGB( int ) { Red=0, Green=1, Blue=2 };
with ( Color, RGB ) {
        // int red = Red;
}
\end{lstlisting}
\CFA will not try to resolve the expression with ambiguity. It would report an error. In this case, it is necessary to qualify @Red@ even inside of the \lstinline{with} clause.

\subsection{Instance Declaration}


\begin{lstlisting}[label=lst:var_declaration]
enum Sample s1;
\end{lstlisting}

The declaration \CFA-enumeration variable has the same syntax as the C-enumeration. Internally, such a variable will be represented as an EnumInstType.

\section{Related Work}

Enumerations exist in many popular programming languages, e.g., Pascal, Ada, \Csharp, \CC, Go, Java, Modula-3, Rust, Swift, Python, and Algebraic data type in functional programming.
There are a large set of overlapping features for all the languages, but each language has its own unique restrictions and extensions.

\subsection{Pascal}

\subsection{Ada}

\subsection{\Csharp}

\subsection{\CC}

Because \CC is backwards compatible with C, it inherited C's enumerations, except there is no implicit conversion from an integral value to an enumeration;
hence, the values in a \CC enumeration can only be its enumerators.

\CC{11} extended enumeration with a scoped enumeration, \lstinline[language=c++]{enum class} (or \lstinline[language=c++]{enum struct}), where the enumerators are local to the enumeration and are accessed using type qualification, e.g., @Weekday::Monday@.
\CC{20} supports unscoped access with a \lstinline[language=c++]{using enum} declaration.

For both unscoped and scoped enumerations, the underlying type is an implementation-defined integral type that is large enough to hold all enumerated values; it does not have to be the smallest possible type.
The underlying integral type can be explicitly specified:
\begin{lstlisting}[language=c++,{moredelim=**[is][\color{red}]{@}{@}}]
enum class RGB : @long@ { Red, Green, Blue };
enum class rgb : @char@ { Red = 'r', Green = 'g', Blue = 'b' };
enum class srgb : @signed char@ { Red = -1, Green = 0, Blue = 1 };
\end{lstlisting}

\subsection{Go}

\subsection{Java}

\subsection{Modula-3}

\subsection{Rust}

\subsection{Swift}

\subsection{Python}

\subsection{Algebraic Data Type}

\end{document}

% Local Variables: %
% tab-width: 4 %
% compile-command: "pdflatex enum.tex" %
% End: %