[85034ed] | 1 | %% |
---|
| 2 | %% This is file `sample-manuscript.tex', |
---|
| 3 | %% generated with the docstrip utility. |
---|
| 4 | %% |
---|
| 5 | %% The original source files were: |
---|
| 6 | %% |
---|
| 7 | %% samples.dtx (with options: `manuscript') |
---|
| 8 | %% |
---|
| 9 | %% IMPORTANT NOTICE: |
---|
| 10 | %% |
---|
| 11 | %% For the copyright see the source file. |
---|
| 12 | %% |
---|
| 13 | %% Any modified versions of this file must be renamed |
---|
| 14 | %% with new filenames distinct from sample-manuscript.tex. |
---|
| 15 | %% |
---|
| 16 | %% For distribution of the original source see the terms |
---|
| 17 | %% for copying and modification in the file samples.dtx. |
---|
| 18 | %% |
---|
| 19 | %% This generated file may be distributed as long as the |
---|
| 20 | %% original source files, as listed above, are part of the |
---|
| 21 | %% same distribution. (The sources need not necessarily be |
---|
| 22 | %% in the same archive or directory.) |
---|
| 23 | %% |
---|
| 24 | %% Commands for TeXCount |
---|
| 25 | %TC:macro \cite [option:text,text] |
---|
| 26 | %TC:macro \citep [option:text,text] |
---|
| 27 | %TC:macro \citet [option:text,text] |
---|
| 28 | %TC:envir table 0 1 |
---|
| 29 | %TC:envir table* 0 1 |
---|
| 30 | %TC:envir tabular [ignore] word |
---|
| 31 | %TC:envir displaymath 0 word |
---|
| 32 | %TC:envir math 0 word |
---|
| 33 | %TC:envir comment 0 0 |
---|
| 34 | %% |
---|
| 35 | %% |
---|
| 36 | %% The first command in your LaTeX source must be the \documentclass command. |
---|
| 37 | \documentclass[manuscript,screen,review]{acmart} |
---|
| 38 | \usepackage{xcolor} |
---|
| 39 | \usepackage{listings} |
---|
| 40 | \usepackage[ligature, inference]{semantic} |
---|
| 41 | \usepackage{array} |
---|
| 42 | |
---|
| 43 | \definecolor{mGreen}{rgb}{0,0.6,0} |
---|
| 44 | \definecolor{mGray}{rgb}{0.5,0.5,0.5} |
---|
| 45 | \definecolor{mPurple}{rgb}{0.58,0,0.82} |
---|
| 46 | \definecolor{backgroundColour}{rgb}{0.95,0.95,0.92} |
---|
| 47 | |
---|
| 48 | \lstdefinestyle{CStyle}{ |
---|
| 49 | backgroundcolor=\color{backgroundColour}, |
---|
| 50 | commentstyle=\color{mGreen}, |
---|
| 51 | keywordstyle=\color{magenta}, |
---|
| 52 | numberstyle=\tiny\color{mGray}, |
---|
| 53 | stringstyle=\color{mPurple}, |
---|
| 54 | basicstyle=\footnotesize, |
---|
| 55 | breakatwhitespace=false, |
---|
| 56 | breaklines=true, |
---|
| 57 | captionpos=b, |
---|
| 58 | keepspaces=true, |
---|
| 59 | numbers=left, |
---|
| 60 | numbersep=5pt, |
---|
| 61 | showspaces=false, |
---|
| 62 | showstringspaces=false, |
---|
| 63 | showtabs=false, |
---|
| 64 | tabsize=2, |
---|
| 65 | language=C |
---|
| 66 | } |
---|
| 67 | |
---|
| 68 | %% |
---|
| 69 | %% \BibTeX command to typeset BibTeX logo in the docs |
---|
| 70 | \AtBeginDocument{% |
---|
| 71 | \providecommand\BibTeX{{% |
---|
| 72 | \normalfont B\kern-0.5em{\scshape i\kern-0.25em b}\kern-0.8em\TeX}}} |
---|
| 73 | |
---|
| 74 | |
---|
| 75 | %% |
---|
| 76 | %% end of the preamble, start of the body of the document source. |
---|
| 77 | \begin{document} |
---|
| 78 | |
---|
| 79 | %% |
---|
| 80 | %% The "title" command has an optional parameter, |
---|
| 81 | %% allowing the author to define a "short title" to be used in page headers. |
---|
| 82 | \title{Enumeration in Cforall} |
---|
| 83 | |
---|
| 84 | %% |
---|
| 85 | %% The "author" command and its associated commands are used to define |
---|
| 86 | %% the authors and their affiliations. |
---|
| 87 | %% Of note is the shared affiliation of the first two authors, and the |
---|
| 88 | %% "authornote" and "authornotemark" commands |
---|
| 89 | %% used to denote shared contribution to the research. |
---|
| 90 | \author{Jiada Liang} |
---|
| 91 | |
---|
| 92 | |
---|
| 93 | %% |
---|
| 94 | %% The abstract is a short summary of the work to be presented in the |
---|
| 95 | %% article. |
---|
| 96 | \begin{abstract} |
---|
[bab2917] | 97 | 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. |
---|
[85034ed] | 98 | \end{abstract} |
---|
| 99 | |
---|
| 100 | %% |
---|
| 101 | %% The code below is generated by the tool at http://dl.acm.org/ccs.cfm. |
---|
| 102 | %% Please copy and paste the code instead of the example below. |
---|
| 103 | %% |
---|
| 104 | |
---|
| 105 | |
---|
| 106 | %% |
---|
| 107 | %% This command processes the author and affiliation and title |
---|
| 108 | %% information and builds the first part of the formatted document. |
---|
| 109 | \maketitle |
---|
| 110 | |
---|
| 111 | \section{C-Style Enum} |
---|
[bab2917] | 112 | \begin{lstlisting}[style=CStyle, label{lst:weekday}] |
---|
| 113 | enum Weekday { Monday, Tuesday, Wednesday, Thursday=10, Friday, Saturday, Sunday }; |
---|
| 114 | \end{lstlisting} |
---|
| 115 | 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. |
---|
| 116 | |
---|
| 117 | \begin{lstlisting}[label{lst:enum_scope}, style=CStyle] |
---|
| 118 | { |
---|
| 119 | { |
---|
| 120 | enum RGB {R, G, B}; |
---|
| 121 | int i = R // i == 0 |
---|
| 122 | } |
---|
| 123 | int j = G; // ERROR! G is not declared in this scope |
---|
| 124 | } |
---|
| 125 | \end{lstlisting} |
---|
| 126 | C-enums are unscoped: enumerators declared inside of an enum are visible in the enclosing scope of the enum class. |
---|
| 127 | |
---|
| 128 | \section{Cforall-Style Enum} |
---|
| 129 | \begin{lstlisting}[style=CStyle, label{lst:color}] |
---|
| 130 | enum Color(char *) { Red="R", Green="G", Blue="B" }; |
---|
| 131 | \end{lstlisting} |
---|
| 132 | 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. |
---|
| 133 | |
---|
| 134 | \section{Enumerable Type Traits} |
---|
| 135 | 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. |
---|
| 136 | \subsection{Enumerable} |
---|
| 137 | A type is enumerable if it can map an integer to a value. |
---|
[85034ed] | 138 | \begin{lstlisting}[style=CStyle] |
---|
[bab2917] | 139 | forall(T) |
---|
| 140 | trait Enumerable { |
---|
| 141 | T value( *class_name* , int ); |
---|
| 142 | }; |
---|
[85034ed] | 143 | \end{lstlisting} |
---|
[bab2917] | 144 | The parameter class name stands for the name of an enumeration class, Weekday, for example. |
---|
| 145 | |
---|
| 146 | \subsection{AutoInitializable} |
---|
| 147 | \begin{lstlisting}[style=CStyle] |
---|
| 148 | forall(T) |
---|
| 149 | trait AutoInitializable { |
---|
| 150 | void ?()( T & t, zero_t ); |
---|
| 151 | void ?()( T & t, one_t ); |
---|
| 152 | S& ?+=?( T & t, one_t ); |
---|
| 153 | void ?{}( T &, T ); |
---|
| 154 | T ?{}( T &, T ); |
---|
| 155 | }; |
---|
| 156 | \end{lstlisting} |
---|
| 157 | |
---|
| 158 | \subsection{AutoInitializable} |
---|
| 159 | \begin{lstlisting}[style=CStyle] |
---|
| 160 | forall(T) |
---|
| 161 | trait AutoInitializable { |
---|
| 162 | void ?()( T & t, zero_t ); |
---|
| 163 | void ?()( T & t, one_t ); |
---|
| 164 | S& ?+=?( T & t, one_t ); |
---|
| 165 | void ?{}( T &, T ); |
---|
| 166 | T ?{}( T &, T ); |
---|
| 167 | }; |
---|
| 168 | \end{lstlisting} |
---|
| 169 | 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. |
---|
[85034ed] | 170 | |
---|
| 171 | \subsection{Enumerable Type} |
---|
| 172 | \begin{lstlisting}[style=CStyle] |
---|
| 173 | forall(T) |
---|
| 174 | trait enumerable { |
---|
| 175 | void ?()( T & t, zero_t ); |
---|
| 176 | void ?()( T & t, one_t ); |
---|
| 177 | S& ?+=?( T & t, one_t ); |
---|
| 178 | void ?{}( T &, T ); |
---|
| 179 | T ?{}( T &, T ); |
---|
| 180 | }; |
---|
| 181 | \end{lstlisting} |
---|
[bab2917] | 182 | |
---|
| 183 | |
---|
| 184 | |
---|
| 185 | |
---|
[85034ed] | 186 | |
---|
| 187 | (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) |
---|
| 188 | \begin{lstlisting}[caption={An example enumerable type}, label{lst:sample_enumerable}, style=CStyle] |
---|
| 189 | struct Type { int i; }; |
---|
| 190 | void ?()( Type & t, zero_t ) { t.i = 0; }; |
---|
| 191 | void ?()( Type & t, one_t ) { t.i = 1; }; |
---|
| 192 | int ?!=?( Type t, zero_t ) { return t.i != 0; }; |
---|
| 193 | S& ?+=?( Type & t, one_t ) { t.i += 1; return t; }; |
---|
| 194 | void ?()( Type & t, Type rhs ) { t.i = rhs.i; }; |
---|
| 195 | Type ?()( Type & t, Type rhs ) { t.i = rhs.i; return t; }; |
---|
| 196 | \end{lstlisting} |
---|
| 197 | |
---|
| 198 | A Cforall-enum is a C-enum parameterized by an enumerable type. For example, $enum(int)$ turns a C-enum into a Cforall-enum. |
---|
| 199 | \begin{lstlisting}[caption={An example Cforall enum}, label{lst:sample_cforall_enum}, style=CStyle] |
---|
| 200 | enum Color(Type) { Red, Green, Blue }; |
---|
| 201 | |
---|
| 202 | > Type Color.values[] = { 0, values[0]++, values[1]++ }; |
---|
| 203 | > enum Color.Label { Red_Label, Green_Label, Blue_Label }; |
---|
| 204 | \end{lstlisting} |
---|
| 205 | 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. |
---|
| 206 | |
---|
| 207 | \subsection{Cforall Enumerations Behaviour} |
---|
| 208 | 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. |
---|
| 209 | |
---|
| 210 | 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>$. |
---|
| 211 | |
---|
| 212 | \begin{lstlisting}[caption={An example Cforall enum}, label{lst:sample_cforall_enum_usage}, style=CStyle] |
---|
| 213 | enum Color red = Color.Red; |
---|
| 214 | > enum Color.Label red = = Color.Label.Red_Label; |
---|
| 215 | Type instance = Color.Red; |
---|
| 216 | > Type instance = Color.values[ Color.Label.Red_Label ]; |
---|
| 217 | \end{lstlisting} |
---|
| 218 | |
---|
| 219 | 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. |
---|
| 220 | |
---|
| 221 | \subsection{Enum Type Functions} |
---|
| 222 | \begin{lstlisting}[caption={Enum Type Functions}, label{lst:cforall_enum_functions}, style=CStyle] |
---|
| 223 | enum Color(string) { // assume String has been defined as an enumerable type |
---|
| 224 | R = "Red", G = "Green", B = "Blue" |
---|
| 225 | }; |
---|
| 226 | values( Color ); |
---|
| 227 | > [ String("Red"), String("Green"), String("Blue") ]; |
---|
| 228 | label_strings( Color ); |
---|
| 229 | > [ "R", "G", "B" ]; |
---|
| 230 | enum Color green = Color.G; |
---|
| 231 | |
---|
| 232 | label_string( Color, green ); |
---|
| 233 | > "G" |
---|
| 234 | label( Color, green ); |
---|
| 235 | > 1 |
---|
| 236 | value( Color, green ) ; |
---|
| 237 | > "Green" |
---|
| 238 | value( Color, "G" ); |
---|
| 239 | > "Green" |
---|
| 240 | label( Color, "G" ); |
---|
| 241 | > 1 |
---|
| 242 | value( Color, "DNE" ); |
---|
| 243 | > (null) |
---|
| 244 | value( Color, 1 ); // "1" is the label "G" |
---|
| 245 | > "Green" |
---|
| 246 | \end{lstlisting} |
---|
| 247 | Names of labels are distinct in an enum declaration. Cforall therefore allows indexing an enum value with its string representation of a label. |
---|
| 248 | |
---|
[bab2917] | 249 | \subsection{Iteration and Range} |
---|
| 250 | A Cforall enum is iterable and supports range function. |
---|
[85034ed] | 251 | \begin{lstlisting}[caption={Range Functions}, label{lst:range_functions}, style=CStyle] |
---|
[bab2917] | 252 | struct string; |
---|
| 253 | enum(string) Weekday( |
---|
| 254 | Monday = "M", Tuesday = "Tu", ... |
---|
[85034ed] | 255 | }; |
---|
[bab2917] | 256 | for ( i; Weekday ) { sout | i; } |
---|
| 257 | >> M Tu W Th F Sat Sun |
---|
| 258 | for ( Monday ~= Tuesday ) |
---|
| 259 | >> M Tu |
---|
[85034ed] | 260 | \end{lstlisting} |
---|
| 261 | |
---|
| 262 | \section{Implementation} |
---|
| 263 | |
---|
| 264 | \subsection{Companion Object} |
---|
| 265 | 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". |
---|
| 266 | |
---|
| 267 | \begin{lstlisting}[caption={Enum Type Functions}, label{lst:cforall_enum_functions}, style=CStyle] |
---|
| 268 | struct string; |
---|
| 269 | enum Color( string ) { |
---|
| 270 | R = "Red", G = "Green", B = "Blue" |
---|
| 271 | }; |
---|
| 272 | |
---|
| 273 | forall( T | enumerable(T) ) { |
---|
| 274 | struct Companion { |
---|
| 275 | T* values; |
---|
| 276 | char** labels; |
---|
| 277 | }; |
---|
| 278 | } |
---|
| 279 | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> |
---|
[bab2917] | 280 | enum Color.Label; |
---|
[85034ed] | 281 | Companion( string ) Color = { |
---|
| 282 | .values = [ "Red", "Green", "Blue" ], |
---|
| 283 | .labels = [ "R", "G", "B" ] |
---|
| 284 | }; |
---|
| 285 | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> |
---|
| 286 | forall( T | enumerable(T) ) |
---|
[bab2917] | 287 | T value( Companion companion, int index ) { return companion.values[ index ]; } |
---|
| 288 | T value( Companion, enum Color.Label ); |
---|
| 289 | char* label( Companion companion, int index ) { return companion.values[ index ]; } |
---|
| 290 | char* label( Companion, enum Color.Label ); |
---|
| 291 | |
---|
[85034ed] | 292 | \end{lstlisting} |
---|
| 293 | |
---|
[bab2917] | 294 | |
---|
| 295 | \subsection{Companion Trait} |
---|
| 296 | 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. |
---|
| 297 | |
---|
| 298 | \subsection{Companion Mapping} |
---|
| 299 | |
---|
| 300 | |
---|
| 301 | |
---|
| 302 | \begin{lstlisting}[caption={Enum Type Functions}, label{lst:cforall_enum_functions}, style=CStyle] |
---|
| 303 | |
---|
| 304 | \end{lstlisting} |
---|
[85034ed] | 305 | %% |
---|
| 306 | %% If your work has an appendix, this is the place to put it. |
---|
| 307 | \appendix |
---|
| 308 | |
---|
| 309 | |
---|
| 310 | \end{document} |
---|
| 311 | \endinput |
---|
| 312 | %% |
---|
| 313 | %% End of file `sample-manuscript.tex'. |
---|