Changeset 8d182b1 for doc


Ignore:
Timestamp:
Nov 14, 2023, 12:19:09 PM (23 months ago)
Author:
caparson <caparson@…>
Branches:
master
Children:
1ccae59, 89a8bab
Parents:
df8ba61a (diff), 5625427 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc
Files:
1 deleted
2 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/pl.bib

    rdf8ba61a r8d182b1  
    41084108}
    41094109
    4110 @article{Buhr22,
     4110@article{Buhr23,
    41114111    contributer = {pabuhr@plg},
    41124112    author      = {Peter A. Buhr and Colby A. Parsons and Thierry Delisle and He Nan Li},
    … …  
    41144114    journal     = spe,
    41154115    year        = 2023,
    4116     month       = sep,
    4117     note        = {\url{https://onlinelibrary.wiley.com/doi/pdf/10.1002/spe.3262}}
     4116    month       = dec,
     4117    volume      = 53,
     4118    number      = 12,
     4119    pages       = {2463-2500},
     4120    note        = {\url{https://onlinelibrary.wiley.com/doi/10.1002/spe.3262},
    41184121}
    41194122
    … …  
    41334136    journal     = spe,
    41344137    year        = 1983,
     4138    month       = jul,
    41354139    volume      = 13,
    41364140    number      = 7,
    41374141    pages       = {577-596},
    4138     month       = jul
    41394142}
    41404143

  • doc/proposals/enum.tex

    rdf8ba61a r8d182b1  
    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}
     1\documentclass[12pt]{article}
     2\usepackage{fullpage,times}
     3\usepackage{pslatex}                    % reduce size of san serif font
    384\usepackage{xcolor}
    395\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}
     6%\usepackage{array}
     7\usepackage{graphics}
     8\usepackage{xspace}
     9
     10\makeatletter
     11\renewcommand\section{\@startsection{section}{1}{\z@}{-3.0ex \@plus -1ex \@minus -.2ex}{1.5ex \@plus .2ex}{\normalfont\large\bfseries}}
     12\renewcommand\subsection{\@startsection{subsection}{2}{\z@}{-2.75ex \@plus -1ex \@minus -.2ex}{1.25ex \@plus .2ex}{\normalfont\normalsize\bfseries}}
     13\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}{-2.5ex \@plus -1ex \@minus -.2ex}{1.0ex \@plus .2ex}{\normalfont\normalsize\bfseries}}
     14\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}{-2.0ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries}}
     15\renewcommand\subparagraph{\@startsection{subparagraph}{4}{\z@}{-1.5ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries\itshape}}
     16\makeatother
     17
     18\usepackage[ignoredisplayed]{enumitem}  % do not affect trivlist
     19\setlist{labelsep=1ex}% global
     20\setlist[itemize]{topsep=0.5ex,parsep=0.25ex,itemsep=0.25ex,listparindent=\parindent,leftmargin=\parindent}% global
     21\setlist[itemize,1]{label=\textbullet}% local
     22%\renewcommand{\labelitemi}{{\raisebox{0.25ex}{\footnotesize$\bullet$}}}
     23\setlist[enumerate]{topsep=0.5ex,parsep=0.25ex,itemsep=0.25ex,listparindent=\parindent}% global
     24\setlist[enumerate,2]{leftmargin=\parindent,labelsep=*,align=parleft,label=\alph*.}% local
     25\setlist[description]{topsep=0.5ex,itemsep=0pt,listparindent=\parindent,leftmargin=\parindent,labelsep=1.5ex}
     26
     27\newenvironment{cquote}{%
     28        \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=4pt\parsep=0pt\leftmargin=\parindent\rightmargin\leftmargin}%
     29        \item\relax
     30}{%
     31        \endlist
     32}% cquote
     33
     34\setlength{\topmargin}{-0.45in}                                                 % move running title into header
     35\setlength{\headsep}{0.25in}
     36\setlength{\textheight}{9.0in}
     37
     38\newcommand{\CFAIcon}{\textsf{C\raisebox{\depth}{\rotatebox{180}A}}} % Cforall icon
     39\newcommand{\CFA}{\protect\CFAIcon\xspace}                              % CFA symbolic name
     40\newcommand{\PAB}[1]{{\color{red}PAB: #1}}
     41
     42% \definecolor{mGreen}{rgb}{0,0.6,0}
     43% \definecolor{mGray}{rgb}{0.5,0.5,0.5}
     44% \definecolor{mPurple}{rgb}{0.58,0,0.82}
     45% \definecolor{backgroundColour}{rgb}{0.95,0.95,0.92}
    4746
    4847\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,
     48%    backgroundcolor=\color{backgroundColour},   
     49%    commentstyle=\color{mGreen},
     50%    keywordstyle=\color{magenta},
     51        stringstyle=\small\tt,                                  % use typewriter font
     52%    stringstyle=\color{mPurple},
     53    columns=fullflexible,
     54    basicstyle=\small\linespread{0.9}\sf,       % reduce line spacing and use sanserif font
     55%   basicstyle=\footnotesize,
    5556    breakatwhitespace=false,         
    56     breaklines=true,                 
     57%    breaklines=true,                 
    5758    captionpos=b,                   
    5859    keepspaces=true,                 
    59     numbers=left,                   
    60     numbersep=5pt,                 
    61     showspaces=false,               
     60%    numbers=left,                   
     61%    numbersep=5pt,                 
     62%    numberstyle=\tiny\color{mGray},
     63%    showspaces=false,               
    6264    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.
     65%    showtabs=false,                 
     66        showlines=true,                                                 % show blank lines at end of code
     67    tabsize=5,
     68    language=C,
     69        aboveskip=4pt,                                                  % spacing above/below code block
     70        belowskip=2pt,
     71        xleftmargin=\parindent,                 % indent code to paragraph indentation
     72}
     73\lstset{style=CStyle,moredelim=**[is][\color{red}]{@}{@}}
     74\lstMakeShortInline@                            % single-character for \lstinline
     75
    7776\begin{document}
    7877
    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.
     78\title{\vspace*{-0.5in}Enumeration in \CFA}
    9079\author{Jiada Liang}
    9180
    92 
    93 %%
    94 %% The abstract is a short summary of the work to be presented in the
    95 %% article.
     81\maketitle
     82
    9683\begin{abstract}
    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.
     84An enumeration is a type that defines a list of named constant values in C (and other languages).
     85C uses an integral type as the underlying representation of an enumeration.
     86\CFA extends C enumerations to allow all basic and custom types for the inner representation.
    9887\end{abstract}
    9988
    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 
    11189\section{C-Style Enum}
    112 \begin{lstlisting}[style=CStyle, label{lst:weekday}]
     90
     91\CFA supports the C-Style enumeration using the same syntax and semantics.
     92\begin{lstlisting}[label=lst:weekday]
    11393enum Weekday { Monday, Tuesday, Wednesday, Thursday=10, Friday, Saturday, Sunday };
    11494\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.
    138 \begin{lstlisting}[style=CStyle]
    139 forall(T)
    140 trait Enumerable {
    141     T value( *class_name* , int );
    142 };
    143 \end{lstlisting}
    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]
     95The example defines an @enum@ type @Weekday@ with ordered enumerators @Monday@, @Tuesday@, @Wednesday@, @Thursday@, @Friday@, @Saturday@ and @Sunday@.
     96The successor of @Tuesday@ is @Monday@ and the predecessor of @Tuesday@ is @Wednesday@.
     97A C enumeration has an integral type, with consecutive enumerator values assigned by the compiler starting at zero or explicitly initialized by the programmer.
     98For example, @Monday@ to @Wednesday@ have values 0--2, @Thursday@ is set to @10@, and after it, @Friday@ to @Sunday@ have values 11--13.
     99
     100There are 3 attributes for an enumeration: position, label, and value:
     101\begin{cquote}
     102\small\sf
     103\begin{tabular}{rccccccccccc}
     104enum Weekday \{ & Monday,       & Tuesday,      & Wednesday,    & Thursday=10,  & Friday,       & Saturday,     & Sunday \}; \\
     105position                & 0                     & 1                     & 2                             & 3                             & 4                     & 5                     & 6                     \\
     106label                   & Monday        & Tuesday       & Wednesday             & Thursday              & Friday        & Saturday      & Sunday        \\
     107value                   & 0                     & 1                     & 2                             & 10                    & 11            & 12            & 13
     108\end{tabular}
     109\end{cquote}
     110
     111The enumerators of an enum are unscoped, i.e., enumerators declared inside of an enum are visible in the enclosing scope of the enum class.
     112\begin{lstlisting}[label=lst:enum_scope]
     113{
     114        enum RGB { R, G, B };
     115        int i = R  // i == 0
     116}
     117int j = G; // ERROR! G is not declared in this scope
     118\end{lstlisting}
     119
     120\section{\CFA-Style Enum}
     121
     122A \CFA enumeration is parameterized by a type, which specifies the type for each enumerator.
     123\CFA allows any object type for the enumerators, and values assigned to enumerators must be in the declared type.
     124\begin{lstlisting}[label=lst:color]
     125enum Colour( @char *@ ) { Red = "R", Green = "G", Blue = "B"  };
     126\end{lstlisting}
     127The type of @Colour@ is @char *@ and each enumerator is initialized with a C string.
     128Only types have define an ordering can be automatically initialized (see Section~\ref{s:AutoInitializable}).
     129
     130
     131% An instance of \CFA-enum (denoted as @<enum_instance>@) is a label for the defined enum name.
     132% The label can be retrieved by calling the function @label( <enum_instance> )@.
     133% Similarly, the @value()@ function returns the value used to initialize the \CFA-enum.
     134
     135A \CFA-enum is scoped: enumeration constants are not automatically exposed to the global scope.
     136Enumeration constant can be referenced using qualified expressions like an aggregate that supports qualified references to its fields. The syntax of $qualified\_expression$ for \CFA-enum is the following:
     137$$<qualified\_expression> := <enum\_type>.<enumerator>$$
     138
     139
     140\subsection{enumeration instance}
     141\begin{lstlisting}[label=lst:sample_cforall_enum_usage]
     142Colour green = Colour.Green;
     143\end{lstlisting}
     144The ~\ref{lst:sample_cforall_enum_usage} example declares a $enumeration\ instance$ named @red@ and initializes it with $enumeration\ constant$ @Color.Red@.
     145An enumeration instance is a data structure that captures attributes of an enumeration constant, which can be retrieved by functions $position( enumeration\ instance )$, $value( enumeration\ instance )$, and $label( enumeration\ instance )$.
     146\begin{lstlisting}
     147int green_pos = position( green ); // 1
     148char * green_value = value( green ); // "G"
     149char * green_label = label( green ); // "Green"
     150\end{lstlisting}
     151An enumeration instance can be assigned to a variable or used as its position with type integer, its value with declared type T, or its label with type char *, and the compiler will resolve the usage as a type fits the context.
     152\begin{lstlisting}[label=lst:enum_inst_assign_int]
     153int green_pos = green; // equivalent to position( green );
     154\end{lstlisting}
     155A resolution of an enumeration constant is $unambigious$ if only one of the attributes has the resolvable type.
     156In example~\ref{lst:enum_inst_assign_int}, the right-hand side of the assignment expression expects integer type.
     157The position of an enumeration is @int@, while the other two cannot be resolved as integers.
     158The expression unambiguously returns the position of @green@.
     159\begin{lstlisting}[label=lst:enum_inst_assign_string]
     160char * green_value = green; // equivalent to value( green );
     161\end{lstlisting}
     162On the other hand, the resolution of an enumeration constant is $ambigious$ if multiple attributes have the expected type.
     163In example~\ref{lst:enum_inst_assign_string}, both value and label have the expected type @char *@.
     164When a resolution is ambiguous, a \textit{resolution precedence} applies: $$value > position > label$$
     165\CFA uses resolution distance to describe if one type can be used as another. While \CFA calculates the resolution distance between the expected type and types of all three attributes, it would not choose the attribute with the closest distance. Instead, when resolving an enumeration constant, \CFA always chooses value whenever it is a possible resolution (resolution distance is not infinite), followed by position, then label.
     166\begin{lstlisting}[label=lst:enum_inst_precedence]
     167enum(double) Foo { Bar };
     168int tee = Foo.Bar; // value( Bar );
     169\end{lstlisting}
     170In the example~\ref{lst:enum_inst_precedence}, while $position( Bar )$ has the closest resolution among the three attributes, $Foo.Bar$ is resolved as $value( Bar )$ because of the resolution precedence.
     171
     172Although \CFA enumeration captures three different attributes, an instance of enumeration does not occupy extra memory.
     173The @sizeof@ \CFA enumeration instance is always 4 bytes, the same amount of memory to store a C enumeration instance.
     174It comes from the fact that:
     175\begin{enumerate}
     176\item
     177a \CFA enumeration is always statically typed;
     178\item
     179it is always resolved as one of its attributes in terms of real usage.
     180\end{enumerate}
     181When creating the enumeration instance green and assigns it with the enumeration constant @Color.Green@, the compilers essentially allocate an integer variables and store the position 1.
     182The invocations of $positions()$, $value()$, and $label()$ turn into calls to special functions defined in the prelude:
     183\begin{lstlisting}[label=lst:companion_call]
     184position( green );
     185>>> position( Colour, 1 ) -> int
     186value( green );
     187>>> value( Colour, 1 ) -> T
     188label( green );
     189>>> label( Colour, 1) -> char *
     190\end{lstlisting}
     191@T@ represents the type declared in the \CFA enumeration defined and @char *@ in the example.
     192These generated functions are $Companion Functions$, they take an $companion$ object and the position as parameters.
     193
     194\subsection{Companion Object and Companion Function}
     195
     196\begin{lstlisting}[caption={Enum Type Functions}, label=lst:cforall_enum_functions]
     197forall( T )  {
     198        struct Companion {
     199                const T * const values;
     200                const char** const labels;
     201                        int length;
     202        };
     203}
     204\end{lstlisting}
     205\CFA creates an object of Companion for every \CFA-enumeration. A companion object has the same name as the enumeration is defined for.
     206A companion object stores values and labels of enumeration constants, in the order of the constants defined in the enumeration.
     207
     208\CFA generates the definition of companion functions. Because \CFA implicitly stores enumeration instance as its position, the companion function $position$ does nothing but returns the position it passes it.
     209Companions function $value$ and $label$ return the array item at the given position of $values$ and $labels$, respectively.
     210\begin{lstlisting}[label=lst:companion_definition]
     211int position( Companion o, int pos ) { return pos; }
     212T value( Companion o, int pos ) { return o.values[ pos ]; }
     213char * label( Companion o, int pos ) { return o.labels[ pos ]; }
     214\end{lstlisting}
     215Notably, the Companion structure definition, and all companion objects, are visible to the users.
     216A 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$
     217\begin{lstlisting}[label=lst:companion_definition_values_labels]
     218Colour.values; // read the Companion's values
     219values( Colour ); // Same as Colour.values
     220\end{lstlisting}
     221
     222\subsection{User Define Enumeration Functions}
     223
     224The Companion objects make extending features for \CFA enumeration easy.
     225
     226\begin{lstlisting}[label=lst:companion_user_definition]
     227char * charastic_string( Companion o, int position ) {
     228        return sprintf("Label: %s; Value: %s", label( o, position ), value( o, position) );
     229}
     230printf( charactic_string ( Color, 1 ) );
     231>>> Label: G; Value: G
     232\end{lstlisting}
     233Defining a function takes a Companion object effectively defines functions for all \CFA enumeration.
     234
     235The \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.
     236Therefore, a user can use the syntax with a user-defined enumeration function call:
     237\begin{lstlisting}[label=lst:companion_user_definition]
     238charactic_string ( Color.Green ); // equivalent to charactic_string ( Color, 1 )
     239>>> Label: G; Value: G
     240\end{lstlisting}
     241Similarly, the user can work with the enumeration type itself: (see section ref...)
     242\begin{lstlisting}[ label=lst:companion_user_definition]
     243void print_enumerators ( Companion o ) {
     244        for ( c : Companion o ) {
     245                sout | label (c) | value( c ) ;
     246        }
     247}
     248print_enumerators( Colour );
     249\end{lstlisting}
     250
     251\subsection{Runtime Enumeration}
     252
     253The Companion structure definition is visible to users, and users can create an instance of Companion object themselves, which effectively constructs a \textit{Runtime Enumeration}.
     254\begin{lstlisting}[ label=lst:runtime_enum ]
     255const char values[] = { "Hello", "World" };
     256const char labels[] = { "First", "Second" };
     257Companion (char *) MyEnum = { .values: values, .labels: labels, .length: 2 };
     258\end{lstlisting}
     259A runtime enumeration can be used to call enumeration functions.
     260\begin{lstlisting}[ label=lst:runtime_enum_usage ]
     261sout | charatstic_string( MyEnum, 1 );
     262>>> Label: Second; Value: World
     263\end{lstlisting}
     264However, a runtime enumeration cannot create an enumeration instance, and it does not support enum-qualified syntax.
     265\begin{lstlisting}[ label=lst:runtime_enum_usage ]
     266MyEnum e = MyEnum.First; // Does not work: cannot create an enumeration instance e,
     267                                    // and MyEnum.First is not recognizable
     268\end{lstlisting}
     269During the compilation, \CFA adds enumeration declarations to an enumeration symbol table and creates specialized function definitions for \CFA enumeration. \CFA does not recognize runtime enumeration during compilation and would not add them to the enumeration symbol table, resulting in a lack of supports for runtime enumeration.
     270
     271\section{Enumeration Features}
     272
     273A trait is a collection of constraints in \CFA, which can be used to describe types.
     274The \CFA standard library defines traits to categorize types with related enumeration features.
     275
     276\subsection{Auto Initializable}
     277\label{s:AutoInitializable}
     278
     279TODO: make the initialization rule a separate section.
     280
     281If no explicit initializer is given to an enumeration constant, C initializes the first enumeration constant with value 0, and the other enumeration constant has a value equal to its $predecessor+1$.
     282\CFA enumerations have the same rule in enumeration constant initialization.
     283However, not all types can be automatically initialized by \CFA because the meaning of $zero$, $one$, and addition operator may not be well-defined.
     284
     285A type is auto-Initializable if it has defined @zero_t@, @one_t@, and an addition operator.
     286\begin{lstlisting}
    148287forall(T)
    149288trait 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.
    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}
    182 
    183 
    184 
    185 
    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.
     289        void ?()( T & t, zero_t );
     290        void ?()( T & t, one_t );
     291        S ?+?( T & t, one_t );
     292};
     293\end{lstlisting}
     294An example of user-defined @AutoInitializable@ would look like the following:
     295\begin{lstlisting}[label=lst:sample_auto_Initializable]
     296struct Odd { int i; };
     297void ?()( Odd & t, zero_t ) { t.i = 1; };
     298void ?()( Odd & t, one_t ) { t.i = 2; };
     299Odd ?+?( Odd t1, Odd t2 )
     300        { return Odd( t1.i + t2.i); };
     301\end{lstlisting}
     302When an enumeration declares an AutoInitializable as its type, no explicit initialization is necessary.
     303\begin{lstlisting}[label=lst:sample_auto_Initializable_usage]
     304enum AutoInitUsage(Odd) {
     305        A, B, C = 6, D
     306};
     307\end{lstlisting}
     308
     309In the example~\ref{lst:sample_auto_Initializable_usage_gen}, because no initializer is specified for the first enumeration constant @A@, \CFA initializes it with the value of @zero_t@, which is 1.
     310@B@ and @D@ have the values of their $predecessor + one_t$, while @one_t@ has the value 2.
     311Therefore, the enumeration is initialized as the following:
     312\begin{lstlisting}[label=lst:sample_auto_Initializable_usage_gen]
     313enum AutoInitUsage(Odd) {
     314        A=1, B=3, C = 6, D=8
     315};
     316\end{lstlisting}
     317In \CFA, integral types, float types, and imaginary numbers are example types that are AutoInitialiable.
     318\begin{lstlisting}[label=lst:letter]
     319enum Alphabet(int) {
     320        A='A', B, C, D, E, F, G, H, I, J, K, L, M,
     321        N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
     322        a='a', b, c, d, e, f, g, h, i, j, k, l, m,
     323        n, o, p, q, r, s, t, u, v, w, x, y, z
     324};
     325print( "%c, %c, %c", Alphabet.F, Alphabet.o, Alphabet.o );
     326>>> F, o, o
     327\end{lstlisting}
    248328
    249329\subsection{Iteration and Range}
    250 A Cforall enum is iterable and supports range function.
    251 \begin{lstlisting}[caption={Range Functions}, label{lst:range_functions}, style=CStyle]
    252 struct string;
    253 enum(string) Weekday(
    254     Monday = "M", Tuesday = "Tu", ...
    255 };
    256 for ( i; Weekday ) { sout | i; }
    257 >> M Tu W Th F Sat Sun
    258 for ( Monday ~= Tuesday )
    259 >> M Tu
     330
     331It is convenient to iterate over a \CFA enumeration.
     332Here is the basic usage:
     333\begin{lstlisting}[label=lst:range_functions]
     334for ( Alphabet ah; Alphabet; ) {
     335        printf( "%d ", ah );
     336}
     337>>> A B C (...omit the rest)
     338\end{lstlisting}
     339The for-loop uses the enumeration type @Alphabet@ as range.
     340When that happens, \CFA iterates all enumerators in the order they defined in the enumeration.
     341@'ch'@ is the iterating enumerator, and it returns the value of an Alphabet in this context according to the precedence rule.
     342
     343\CFA offers a shorthand for iterating all enumeration constants:
     344\begin{lstlisting}[label=lst:range_functions]
     345for ( Alphabet ch ) {
     346        printf( "%d ", ch );
     347}
     348>>> A B C (...omit the rest)
     349\end{lstlisting}
     350
     351Enumeration supports the \CFA loop control syntax for for-loop.
     352\begin{lstlisting}[label=lst:range_functions]
     353for ( Alphabet.D )
     354for ( ch; Alphabet.g ~ Alphabet.z )
     355for ( Alphabet ch; Alphabet.R ~ Alphabet.X ~ 2 )
     356\end{lstlisting}
     357Notably, the meaning of "step" of iteration has changed for enumeration.
     358Consider the following example:
     359\begin{lstlisting}[label=lst:range_functions]
     360enum(int) Sequence {
     361        A = 10, B = 12, C = 14; 
     362}
     363for ( s; Sequence.A ~ Sequence.C ) {
     364        printf( "%d ", s );
     365}
     366
     367>>> 10 12 14
     368
     369for ( s; Sequence.A ~ Sequence.A ~ 2 ) {
     370        printf( "%d ", s );
     371}
     372>>> 10 14
     373\end{lstlisting}
     374The range iteration of enumeration does not return the @current_value++@ until it reaches the upper bound.
     375The semantics is to return the next enumeration constant.
     376If a stepping is specified, 2 for example, it returns the 2 enumeration constant after the current one, rather than the @current+2@.
     377
     378It is also possible to iterate over an enumeration's labels, implicitly or explicitly:
     379\begin{lstlisting}[label=lst:range_functions_label_implicit]
     380for ( char * ch; Alphabet )
     381\end{lstlisting}
     382This for-loop implicitly iterates every label of the enumeration, because a label is the only valid resolution to the ch with type @char *@ in this case.
     383If the value can also be resolved as the @char *@, you might iterate the labels explicitly with the array iteration.
     384\begin{lstlisting}[label=lst:range_functions_label_implicit]
     385for ( char * ch; labels( Alphabet ) )
    260386\end{lstlisting}
    261387
    262388\section{Implementation}
    263389
    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 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    280 enum Color.Label;
    281 Companion( string ) Color = {
    282     .values = [ "Red", "Green", "Blue" ],
    283     .labels = [ "R", "G", "B" ]
    284 };
    285 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
    286 forall( T | enumerable(T) )
    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 
    292 \end{lstlisting}
    293 
    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}
    305 %%
    306 %% If your work has an appendix, this is the place to put it.
    307 \appendix
    308 
     390\CFA places the definition of Companion structure and non-parameterized Companion functions in the prelude, visible globally.
     391
     392\subsection{Declaration}
     393
     394The qualified enumeration syntax is dedicated to \CFA enumeration.
     395\begin{lstlisting}[label=lst:range_functions]
     396enum (type_declaration) name { enumerator = const_expr, enumerator = const_expr, ... }
     397\end{lstlisting}
     398A compiler stores the name, the underlying type, and all enumerators in an @enumeration table@.
     399During the $Validation$ pass, the compiler links the type declaration to the type's definition.
     400It 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.
     401If the declared type is not @Auto Initializable@, \CFA rejects the enumeration definition.
     402Otherwise, it attempts to initialize enumerators with the enumeration initialization pattern. (a reference to a future initialization pattern section)
     403
     404\begin{lstlisting}[label=lst:init]
     405struct T { ... };
     406void ?{}( T & t, zero_t ) { ... };
     407void ?{}( T & t, one_t ) { ... };
     408T ?+?( T & lhs, T & rhs ) { ... };
     409
     410enum (T) Sample {
     411        Zero: 0 /* zero_t */,
     412        One: Zero + 1 /* ?+?( Zero, one_t ) */ , ...
     413};
     414\end{lstlisting}
     415Challenge: \\
     416The value of an enumerator, or the initializer, requires @const_expr@.
     417While 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.
     418Might not be able to implement a \emph{correct} static check.
     419
     420\CFA $autogens$ a Companion object for the declared enumeration.
     421\begin{lstlisting}[label=lst:companion]
     422Companion( T ) Sample {
     423        .values: { 0, 0+1, 0+1+1, 0+1+1+1, ... }, /* 0: zero_t, 1: one_t, +: ?+?{} */
     424        .labels: { "Zero", "One", "Two", "Three", ...},
     425        .length: /* number of enumerators */
     426};
     427\end{lstlisting}
     428\CFA stores values as intermediate expressions because the result of the function call to the function @?+?{}(T&, T&)@ is statically unknown to \CFA.
     429But the result is computed at run time, and the compiler ensures the @values@ are not changed.
     430
     431\subsection{qualified expression}
     432
     433\CFA uses qualified expression to address the scoping of \CFA-enumeration.
     434\begin{lstlisting}[label=lst:qualified_expression]
     435aggregation_name.field;
     436\end{lstlisting}
     437The qualified expression is not dedicated to \CFA enumeration.
     438It is a feature that is supported by other aggregation in \CFA as well, including a C enumeration.
     439When C enumerations are unscoped, the qualified expression syntax still helps to disambiguate names in the context.
     440\CFA recognizes if the expression references a \CFA aggregation by searching the presence of @aggregation_name@ in the \CFA enumeration table.
     441If the @aggregation_name@ is identified as a \CFA enumeration, the compiler checks if @field@ presents in the declared \CFA enumeration.
     442
     443\subsection{\lstinline{with} statement/statement}
     444
     445\emph{Work in Progress}
     446
     447Instead of qualifying an enumeration expression every time, one can use the @with@ to expose enumerators to the current scope so that they are directly accessible.
     448
     449\subsection{Instance Declaration}
     450
     451\emph{Work in Progress}
     452
     453\begin{lstlisting}[label=lst:declaration]
     454enum Sample s1;
     455Sample s2;
     456\end{lstlisting}
     457A declaration of \CFA enumeration instance that has no difference than a C enumeration or other \CFA aggregation.
     458The compiler recognizes the type of a variable declaration by searching the name in all possible types.
     459The @enum@ keyword is not necessary but helps to disambiguate types (questionable).
     460The generated code for a \CFA enumeration declaration is utterly an integer, which is meant to store the position.
     461\begin{lstlisting}[label=lst:declaration]
     462int s1;
     463int s2;
     464\end{lstlisting}
     465
     466\subsection{Compiler Representation}
     467
     468\emph{Work in Progress}
     469
     470The internal representation of an enumeration constant is @EnumInstType@.
     471The minimum information an @EnumInstType@ stores is a reference to the \CFA-enumeration declaration and the position of the enumeration constant.
     472\begin{lstlisting}[label=lst:EnumInstType]
     473class EnumInstType {
     474        EnumDecl enumDecl;
     475        int position;
     476};
     477\end{lstlisting}
     478
     479\subsection{Unification and Resolution }
     480
     481\emph{Work in Progress}
     482
     483\begin{lstlisting}
     484enum Colour( char * ) { Red = "R", Green = "G", Blue = "B"  };
     485\end{lstlisting}
     486The @EnumInstType@ is convertible to other types.
     487A \CFA enumeration expression is implicitly \emph{overloaded} with its three different attributes: value, position, and label.
     488The \CFA compilers need to resolve an @EnumInstType@ as one of its attributes based on the current context.
     489
     490\begin{lstlisting}[caption={Null Context}, label=lst:null_context]
     491{
     492        Colour.Green;
     493}
     494\end{lstlisting}
     495In example~\ref{lst:null_context}, the environment gives no information to help with the resolution of @Colour.Green@.
     496In this case, any of the attributes is resolvable.
     497According to the \textit{precedence rule}, the expression with @EnumInstType@ resolves as @value( Colour.Green )@.
     498The @EnumInstType@ is converted to the type of the value, which is statically known to the compiler as @char *@.
     499When the compilation reaches the code generation, the compiler outputs code for type @char *@ with the value @"G"@.
     500\begin{lstlisting}[caption={Null Context Generated Code}, label=lst:null_context]
     501{
     502        "G";
     503}
     504\end{lstlisting}
     505\begin{lstlisting}[caption={int Context}, label=lst:int_context]
     506{
     507        int g = Colour.Green;
     508}
     509\end{lstlisting}
     510The assignment expression gives a context for the EnumInstType resolution.
     511The EnumInstType is used as an @int@, and \CFA needs to determine which of the attributes can be resolved as an @int@ type.
     512The functions $Unify( T1, T2 ): bool$ take two types as parameters and determine if one type can be used as another.
     513In example~\ref{lst:int_context}, the compiler is trying to unify @int@ and @EnumInstType@ of @Colour@.
     514$$Unification( int, EnumInstType<Colour> )$$ which turns into three Unification call
     515\begin{lstlisting}[label=lst:attr_resolution_1]
     516{
     517        Unify( int, char * ); // unify with the type of value
     518        Unify( int, int ); // unify with the type of position
     519        Unify( int, char * ); // unify with the type of label
     520}
     521\end{lstlisting}
     522\begin{lstlisting}[label=lst:attr_resolution_precedence]
     523{
     524        Unification( T1, EnumInstType<T2> ) {
     525                if ( Unify( T1, T2 ) ) return T2;
     526                if ( Unify( T1, int ) ) return int;
     527                if ( Unify( T1, char * ) ) return char *;
     528                Error: Cannot Unify T1 with EnumInstType<T2>;
     529        }
     530}
     531\end{lstlisting}
     532After the unification, @EnumInstType@ is replaced by its attributes.
     533
     534\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
     535{
     536        T2 foo ( T1 ); // function take variable with T1 as a parameter
     537        foo( EnumInstType<T3> ); // Call foo with a variable has type EnumInstType<T3>
     538        >>>> Unification( T1, EnumInstType<T3> )
     539}
     540\end{lstlisting}
     541% The conversion can work backward: in restrictive cases, attributes of can be implicitly converted back to the EnumInstType.
     542Backward conversion:
     543\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
     544{
     545        enum Colour colour = 1;
     546}
     547\end{lstlisting}
     548
     549\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
     550{
     551   Unification( EnumInstType<Colour>, int ) >>> label
     552}
     553\end{lstlisting}
     554@int@ can be unified with the label of Colour.
     555@5@ is a constant expression $\Rightarrow$ Compiler knows the value during the compilation $\Rightarrow$ turns it into
     556\begin{lstlisting}
     557{
     558   enum Colour colour = Colour.Green;
     559}
     560\end{lstlisting}
     561Steps:
     562\begin{enumerate}
     563\item
     564identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
     565\item
     566@unification( EnumInstType<Colour>, int )@: @position( EnumInstType< Colour > )@
     567\item
     568return the enumeration constant at the position 1
     569\end{enumerate}
     570\begin{lstlisting}
     571{
     572        enum T (int) { ... } // Declaration
     573        enum T t = 1;
     574}
     575\end{lstlisting}
     576Steps:
     577\begin{enumerate}
     578\item
     579identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
     580\item
     581@unification( EnumInstType<Colour>, int )@: @value( EnumInstType< Colour > )@
     582\item
     583return the FIRST enumeration constant that has the value 1, by searching through the values array
     584\end{enumerate}
     585The 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
    309586
    310587\end{document}
    311 \endinput
    312 %%
    313 %% End of file `sample-manuscript.tex'.
     588
     589% Local Variables: %
     590% tab-width: 4 %
     591% compile-command: "pdflatex enum.tex" %
     592% End: %
Note: See TracChangeset for help on using the changeset viewer.