Index: doc/theses/jiada_liang_MMath/main.tex =================================================================== --- doc/theses/jiada_liang_MMath/main.tex (revision bab2917ddf427236b02c457fe13904bbca581868) +++ (revision ) @@ -1,313 +1,0 @@ -%% -%% 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 $$) has a label, the defined enum name. The label can be retrieved by calling the function $label()$ on a $$. 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 $$.$$. In the $Color$ example, $Color$ is a $$ and $Red$, $Green$, $Blue$ are $$. - -\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'.