source: doc/proposals/enum.tex@ fe293bf

%%
%% This is file `sample-manuscript.tex',
%% generated with the docstrip utility.
%%
%% The original source files were:
%%
%% samples.dtx  (with options: `manuscript')
%% 
%% IMPORTANT NOTICE:
%% 
%% For the copyright see the source file.
%% 
%% Any modified versions of this file must be renamed
%% with new filenames distinct from sample-manuscript.tex.
%% 
%% For distribution of the original source see the terms
%% for copying and modification in the file samples.dtx.
%% 
%% This generated file may be distributed as long as the
%% original source files, as listed above, are part of the
%% same distribution. (The sources need not necessarily be
%% in the same archive or directory.)
%%
%% Commands for TeXCount
%TC:macro \cite [option:text,text]
%TC:macro \citep [option:text,text]
%TC:macro \citet [option:text,text]
%TC:envir table 0 1
%TC:envir table* 0 1
%TC:envir tabular [ignore] word
%TC:envir displaymath 0 word
%TC:envir math 0 word
%TC:envir comment 0 0
%%
%%
%% The first command in your LaTeX source must be the \documentclass command.
\documentclass[manuscript,screen,review]{acmart}
\usepackage{xcolor}
\usepackage{listings}
\usepackage[ligature, inference]{semantic}
\usepackage{array}

\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},
    numberstyle=\tiny\color{mGray},
    stringstyle=\color{mPurple},
    basicstyle=\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2,
    language=C
}

%%
%% \BibTeX command to typeset BibTeX logo in the docs
\AtBeginDocument{%
  \providecommand\BibTeX{{%
    \normalfont B\kern-0.5em{\scshape i\kern-0.25em b}\kern-0.8em\TeX}}}


%%
%% end of the preamble, start of the body of the document source.
\begin{document}

%%
%% The "title" command has an optional parameter,
%% allowing the author to define a "short title" to be used in page headers.
\title{Enumeration in Cforall}

%%
%% The "author" command and its associated commands are used to define
%% the authors and their affiliations.
%% Of note is the shared affiliation of the first two authors, and the
%% "authornote" and "authornotemark" commands
%% used to denote shared contribution to the research.
\author{Jiada Liang}


%%
%% The abstract is a short summary of the work to be presented in the
%% article.
\begin{abstract}
    An enumeration, or enum in short, is a type that defines a list of named constant values in C. C uses integral type as the underlying representation of enum. Cforall extends C enum to allow more types, including custom types, to be used as enumeration inner representation.
\end{abstract}

%%
%% The code below is generated by the tool at http://dl.acm.org/ccs.cfm.
%% Please copy and paste the code instead of the example below.
%%


%%
%% This command processes the author and affiliation and title
%% information and builds the first part of the formatted document.
\maketitle

\section{C-Style Enum}
\begin{lstlisting}[style=CStyle, label{lst:weekday}]
enum Weekday { Monday, Tuesday, Wednesday, Thursday=10, Friday, Saturday, Sunday };
\end{lstlisting}
Cforall supports the C-Style enumeration (C-enum for short). It has the same syntax as C and resembles the same language semantics. In code~\ref{lst:weekday} example, the syntax defines an enum class $Weekday$ with enumerators $Monday$, $Tuesday$, $Wednesday$, $Thursday$, $Friday$, $Saturday$ and $Sunday$ in order. The successor of $Tuesday$ is $Monday$ and the predecessor of $Tuesday$ is $Wednesday$. Enumerators have an integral type, either being explicitly initialized by an initializer or being assigned a value by the compiler. For example, $Thursday$ has been assigned with value $10$. If not explicitly initialized, the first value of an enum, $Monday$ in the $Weekday$ example, has the integer value 0. Other uninitialized enum value has a value that is equal to their successor $+ 1$. The enum value $Tuesday$, $Wednesday$, $Friday$, $Saturday$, and $Sunday$ have value 1, 2, 11, 12, and 13 respectively. 

\begin{lstlisting}[label{lst:enum_scope}, style=CStyle]
{
    {
        enum RGB {R, G, B};
        int i = R  // i == 0
    }
    int j = G; // ERROR! G is not declared in this scope
}
\end{lstlisting}
C-enums are unscoped: enumerators declared inside of an enum are visible in the enclosing scope of the enum class.

\section{Cforall-Style Enum}
\begin{lstlisting}[style=CStyle, label{lst:color}]
enum Color(char *) { Red="R", Green="G", Blue="B"  };
\end{lstlisting}
A Cforall enumeration is parameterized by a type declared. Cforall allows any oType in the enum declaration, and values assigned to enumerators must be in the declared type.

\section{Enumerable Type Traits}
A trait is a collection of constraints in Cforall, which can be used to describe types. Cforall standard library defines traits to categorize types that are related enumeration features.
\subsection{Enumerable}
A type is enumerable if it can map an integer to a value. 
\begin{lstlisting}[style=CStyle]
forall(T)
trait Enumerable {
    T value( *class_name* , int );
};
\end{lstlisting}
The parameter class name stands for the name of an enumeration class, Weekday, for example.

\subsection{AutoInitializable}
\begin{lstlisting}[style=CStyle]
forall(T)
trait AutoInitializable {
  void ?()( T & t, zero_t );
  void ?()( T & t, one_t );
  S& ?+=?( T & t, one_t );
  void ?{}( T &, T ); 
  T ?{}( T &, T ); 
};
\end{lstlisting}

\subsection{AutoInitializable}
\begin{lstlisting}[style=CStyle]
forall(T)
trait AutoInitializable {
  void ?()( T & t, zero_t );
  void ?()( T & t, one_t );
  S& ?+=?( T & t, one_t );
  void ?{}( T &, T ); 
  T ?{}( T &, T ); 
};
\end{lstlisting}
A type is AutoInitializable if it has defined a zero\_t constructor, a one\_t constructor, an addition assignment operator, a copy constructor, and a copy assignment operator.

\subsection{Enumerable Type}
\begin{lstlisting}[style=CStyle]
forall(T)
trait enumerable {
  void ?()( T & t, zero_t );
  void ?()( T & t, one_t );
  S& ?+=?( T & t, one_t );
  void ?{}( T &, T ); 
  T ?{}( T &, T ); 
};
\end{lstlisting}





(Should change the definition of enumerable to something else. Maybe auto-constructible. If a type is not auto-constructible, all enumeration must be explicitly initialized)
\begin{lstlisting}[caption={An example enumerable type}, label{lst:sample_enumerable}, style=CStyle]
struct Type { int i; };
void ?()( Type & t, zero_t ) { t.i = 0; };
void ?()( Type & t, one_t ) { t.i = 1; };
int ?!=?( Type t, zero_t ) { return t.i != 0; };
S& ?+=?( Type & t, one_t ) { t.i += 1; return t; };
void ?()( Type & t, Type rhs ) { t.i = rhs.i; };
Type ?()( Type & t, Type rhs ) { t.i = rhs.i; return t; };
\end{lstlisting}

A Cforall-enum is a C-enum parameterized by an enumerable type. For example,  $enum(int)$ turns a C-enum into a Cforall-enum.
\begin{lstlisting}[caption={An example Cforall enum}, label{lst:sample_cforall_enum}, style=CStyle]
enum Color(Type) { Red, Green, Blue };

> Type Color.values[] = { 0, values[0]++, values[1]++ }; 
> enum Color.Label { Red_Label, Green_Label, Blue_Label };
\end{lstlisting}
Declaring a Cforall-enum, the compiler defines a C-enum names every element in the Cforall-enum, and an array that stores Cforall enumeration values. 

\subsection{Cforall Enumerations Behaviour}
An instance of Cforall-enum (denoted as $<enum\_instance>$) has a label, the defined enum name. The label can be retrieved by calling the function $label()$ on a $<enum\_instance>$. The $value()$ function on the other hand returns the value used to initialize the Cforall-enum.

Cforall-enum supports a qualified expression. The syntax of the qualified expression for Cforall-enum is $$<enum\_type\_name>.<enum\_instance\_name>$$. In the $Color$ example, $Color$ is a $<enum\_type\_name>$ and $Red$, $Green$, $Blue$ are $<enum\_instance\_name>$. 

\begin{lstlisting}[caption={An example Cforall enum}, label{lst:sample_cforall_enum_usage}, style=CStyle]
enum Color red = Color.Red;
> enum Color.Label red = = Color.Label.Red_Label; 
Type instance = Color.Red;
> Type instance = Color.values[ Color.Label.Red_Label ];
\end{lstlisting}

The expression $Color.Red$ is overloaded to represent both $value(Color.Red)$ and $label(Color.Red)$. The expression returns the $label(Color.Red)$ by default but returns $value()$ whenever the $value()$ is a closer candidate in the context. [more explanation] In \ref{lst:sample_cforall_enum_usage}, when assigned to an enum variable, $Color.Red$ returns the label. This is to reduce the memory to store a Cforall-enum variable. In an assignment expression when the left-hand-side expects a $Type$, the resolution finds $value(Color.Red)$ is a better candidate than $label(Color.Red)$, and returns the value instead.

\subsection{Enum Type Functions}
\begin{lstlisting}[caption={Enum Type Functions}, label{lst:cforall_enum_functions}, style=CStyle]
enum Color(string) { // assume String has been defined as an enumerable type
    R = "Red", G = "Green", B = "Blue"
};
values( Color );
> [ String("Red"), String("Green"), String("Blue") ];
label_strings( Color );
> [ "R", "G", "B" ];
enum Color green = Color.G;

label_string( Color, green );
> "G"
label( Color, green );
> 1
value( Color, green ) ;
> "Green"
value( Color, "G" );
> "Green"
label( Color, "G" );
> 1
value( Color, "DNE" );
> (null)
value( Color, 1 ); // "1" is the label "G"
> "Green"
\end{lstlisting}
Names of labels are distinct in an enum declaration. Cforall therefore allows indexing an enum value with its string representation of a label.

\subsection{Iteration and Range}
A Cforall enum is iterable and supports range function.
\begin{lstlisting}[caption={Range Functions}, label{lst:range_functions}, style=CStyle]
struct string;
enum(string) Weekday( 
    Monday = "M", Tuesday = "Tu", ...
};
for ( i; Weekday ) { sout | i; }
>> M Tu W Th F Sat Sun
for ( Monday ~= Tuesday )
>> M Tu
\end{lstlisting}

\section{Implementation}

\subsection{Companion Object}
The intuition to create a companion object is that functions that support enumeration features need static information of an enumeration class. For example, values() returns an array of values defined for the enumeration. $label( Color, "G" )$ needs information about enum names defined for the enum class $Color$. Theoretically, enum-type functions can be defined as functions that take $TypeName$ expression as the first parameter. An alternative approach is to define that "companion object".

\begin{lstlisting}[caption={Enum Type Functions}, label{lst:cforall_enum_functions}, style=CStyle]
struct string;
enum Color( string ) { 
    R = "Red", G = "Green", B = "Blue"
};

forall( T | enumerable(T) )  {
    struct Companion {
        T* values;
        char** labels;
    };
}
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
enum Color.Label;
Companion( string ) Color = { 
    .values = [ "Red", "Green", "Blue" ],
    .labels = [ "R", "G", "B" ]
};
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
forall( T | enumerable(T) )
T value( Companion companion, int index ) { return companion.values[ index ]; } 
T value( Companion, enum Color.Label );
char* label( Companion companion, int index ) { return companion.values[ index ]; }
char* label( Companion, enum Color.Label );

\end{lstlisting}


\subsection{Companion Trait}
Users can define the companion object themselves. A companion object should define an array of any type called values and an array of strings representing a label. Defining a companion object effectively creates a new enumerable type. 

\subsection{Companion Mapping}



\begin{lstlisting}[caption={Enum Type Functions}, label{lst:cforall_enum_functions}, style=CStyle]

\end{lstlisting}
%%
%% If your work has an appendix, this is the place to put it.
\appendix


\end{document}
\endinput
%%
%% End of file `sample-manuscript.tex'.