source: doc/proposals/enum.tex @ 2d373440

Last change on this file since 2d373440 was 2d373440, checked in by JiadaL <j82liang@…>, 6 months ago

Update enum.tex

  • Property mode set to 100644
File size: 34.3 KB
Line 
1\documentclass[12pt]{article}
2\usepackage{fullpage,times}
3\usepackage{pslatex}                    % reduce size of san serif font
4\usepackage{xcolor}
5\usepackage{listings}
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
17% Denote newterms in particular font and index them without particular font and in lowercase, e.g., \newterm{abc}.
18% The option parameter provides an index term different from the new term, e.g., \newterm[\texttt{abc}]{abc}
19% The star version does not lowercase the index information, e.g., \newterm*{IBM}.
20\newcommand{\newtermFontInline}{\emph}
21\newcommand{\newterm}{\protect\@ifstar\@snewterm\@newterm}
22\newcommand{\@newterm}[2][\@empty]{\lowercase{\def\temp{#2}}{\newtermFontInline{#2}}\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi}
23\newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}
24\makeatother
25
26\usepackage[ignoredisplayed]{enumitem}  % do not affect trivlist
27\setlist{labelsep=1ex}% global
28\setlist[itemize]{topsep=0.5ex,parsep=0.25ex,itemsep=0.25ex,listparindent=\parindent,leftmargin=\parindent}% global
29\setlist[itemize,1]{label=\textbullet}% local
30%\renewcommand{\labelitemi}{{\raisebox{0.25ex}{\footnotesize$\bullet$}}}
31\setlist[enumerate]{topsep=0.5ex,parsep=0.25ex,itemsep=0.25ex,listparindent=\parindent}% global
32\setlist[enumerate,2]{leftmargin=\parindent,labelsep=*,align=parleft,label=\alph*.}% local
33\setlist[description]{topsep=0.5ex,itemsep=0pt,listparindent=\parindent,leftmargin=\parindent,labelsep=1.5ex}
34
35\newenvironment{cquote}{%
36        \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=4pt\parsep=0pt\leftmargin=\parindent\rightmargin\leftmargin}%
37        \item\relax
38}{%
39        \endlist
40}% cquote
41
42\setlength{\topmargin}{-0.45in}                                                 % move running title into header
43\setlength{\headsep}{0.25in}
44\setlength{\textheight}{9.0in}
45
46\newcommand{\CFAIcon}{\textsf{C\raisebox{\depth}{\rotatebox{180}A}}} % Cforall icon
47\newcommand{\CFA}{\protect\CFAIcon\xspace}                              % CFA symbolic name
48\newcommand{\CCIcon}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ icon
49\newcommand{\CC}[1][]{\protect\CCIcon{#1}\xspace}               % C++ symbolic name
50\newcommand{\PAB}[1]{{\color{red}PAB: #1}}
51
52% \definecolor{mGreen}{rgb}{0,0.6,0}
53% \definecolor{mGray}{rgb}{0.5,0.5,0.5}
54% \definecolor{mPurple}{rgb}{0.58,0,0.82}
55% \definecolor{backgroundColour}{rgb}{0.95,0.95,0.92}
56
57\lstdefinestyle{CStyle}{
58%    backgroundcolor=\color{backgroundColour},   
59%    commentstyle=\color{mGreen},
60%    keywordstyle=\color{magenta},
61        stringstyle=\small\tt,                                  % use typewriter font
62%    stringstyle=\color{mPurple},
63    columns=fullflexible,
64    basicstyle=\small\linespread{0.9}\sf,       % reduce line spacing and use sanserif font
65%   basicstyle=\footnotesize,
66    breakatwhitespace=false,         
67%    breaklines=true,                 
68    captionpos=b,                   
69    keepspaces=true,                 
70        escapechar=\$,                                                  % LaTeX escape in CFA code
71%    numbers=left,                   
72%    numbersep=5pt,                 
73%    numberstyle=\tiny\color{mGray},
74%    showspaces=false,               
75    showstringspaces=false,
76%    showtabs=false,                 
77        showlines=true,                                                 % show blank lines at end of code
78    tabsize=5,
79    language=C,
80        aboveskip=4pt,                                                  % spacing above/below code block
81        belowskip=2pt,
82        xleftmargin=\parindent,                 % indent code to paragraph indentation
83}
84\lstset{style=CStyle,moredelim=**[is][\color{red}]{@}{@}}
85\lstMakeShortInline@                            % single-character for \lstinline
86
87\begin{document}
88
89\title{\vspace*{-0.5in}Enumeration in \CFA}
90\author{Jiada Liang}
91
92\maketitle
93
94\begin{abstract}
95An enumeration is a type that defines a list of named constant values in C (and other languages).
96C and \CC use an integral type as the underlying representation of an enumeration.
97\CFA extends C enumerations to allow all basic and custom types for the inner representation.
98\end{abstract}
99
100\section{C-Style Enum}
101
102\CFA supports the C-Style enumeration using the same syntax and semantics.
103\begin{lstlisting}[label=lst:weekday]
104enum Weekday { Monday, Tuesday, Wednesday, Thursday=10, Friday, Saturday, Sunday };
105                $\(\uparrow\)$                                                                      $\(\uparrow\)$
106    ${\rm \newterm{enumeration name}}$                                        ${\rm \newterm{enumerator names}}
107\end{lstlisting}
108The example defines an enumeration type @Weekday@ with ordered enumerators @Monday@, @Tuesday@, @Wednesday@, @Thursday@, @Friday@, @Saturday@ and @Sunday@.
109The successor of @Tuesday@ is @Monday@ and the predecessor of @Tuesday@ is @Wednesday@.
110A C enumeration is an integral type, with consecutive enumerator values assigned by the compiler starting at zero or the next explicitly initialized value by the programmer.
111For example, @Monday@ to @Wednesday@ have values 0--2 implicitly set by the compiler, @Thursday@ is explicitly set to @10@ by the programmer, and @Friday@ to @Sunday@ have values 11--13 implicitly set by the compiler.
112
113There are 3 attributes for an enumeration: \newterm{position}, \newterm{label}, and \newterm{value}:
114\begin{cquote}
115\small\sf\setlength{\tabcolsep}{3pt}
116\begin{tabular}{rccccccccccc}
117@enum@ Weekday \{       & Monday,       & Tuesday,      & Wednesday,    & Thursday=10,  & Friday,       & Saturday,     & Sunday \}; \\
118\it position            & 0                     & 1                     & 2                             & 3                             & 4                     & 5                     & 6                     \\
119\it label                       & Monday        & Tuesday       & Wednesday             & Thursday              & Friday        & Saturday      & Sunday        \\
120\it value                       & 0                     & 1                     & 2                             & 10                    & 11            & 12            & 13
121\end{tabular}
122\end{cquote}
123
124The enumerators of an enumeration are unscoped, i.e., enumerators declared inside of an @enum@ are visible in the enclosing scope of the @enum@ type.
125\begin{lstlisting}[label=lst:enum_scope]
126{
127        enum Weekday { ... };   // enumerators implicitly projected into local scope
128        Weekday weekday = Monday;
129        weekday = Friday;
130        int i = Sunday  // i == 13
131}
132int j = Wednesday; // ERROR! Wednesday is not declared in this scope
133\end{lstlisting}
134
135\section{\CFA-Style Enum}
136
137A \CFA enumeration is parameterized by a type, which specifies the type for each enumerator.
138\CFA allows any object type for the enumerators, and values assigned to enumerators must be from the declared type.
139\begin{lstlisting}[label=lst:color]
140enum Colour( @char *@ ) { Red = "R", Green = "G", Blue = "B"  };
141\end{lstlisting}
142The type of @Colour@ is @char *@ and each enumerator is initialized with a C string.
143Only types with a defined ordering can be automatically initialized (see Section~\ref{s:AutoInitializable}).
144
145% An instance of \CFA-enum (denoted as @<enum_instance>@) is a label for the defined enum name.
146% The label can be retrieved by calling the function @label( <enum_instance> )@.
147% Similarly, the @value()@ function returns the value used to initialize the \CFA-enum.
148
149\subsection{Enumerator Scoping}
150
151A \CFA-enum can be scoped, meaning the enumerator constants are not projected into the enclosing scope.
152\begin{lstlisting}
153enum Colour( char * ) @!@ { ... };
154\end{lstlisting}
155where the @'!'@ implies the enumerators are \emph{not} projected.
156The enumerators of a scoped enumeration are accessed using qualification, like the fields of an aggregate.
157% The syntax of $qualified\_expression$ for \CFA-enum is the following:
158% $$<qualified\_expression> := <enum\_type>.<enumerator>$$
159\begin{lstlisting}
160Colour colour = @Colour.@Red;   // qualification
161colour = @Colour.@Blue;
162\end{lstlisting}
163
164\subsection{Enumerator Attributes}
165
166The attributes of an enumerator are accessed by pseudo-functions @position@, @value@, and @label@, i.e., like @sizeof@.
167\begin{lstlisting}
168int green_pos = @position@( Colour.Green );     // 1
169char * green_value = @value@( Colour.Green );   // "G"
170char * green_label = @label@( Colour.Green );   // "Green"
171\end{lstlisting}
172There are implicit conversions from an enumerator to its attributes.
173\begin{lstlisting}[label=lst:enum_inst_assign_int]
174int green_pos = Colour.Green;  // 1
175char * green_value = Colour.Green;  // ambiguous
176char * green_label = Colour.Green;  // ambiguous
177\end{lstlisting}
178where a conversion is ambiguous, if the enumerator's type is same as an attribute's type.
179For example, @value( Colour.Green )@ and @label( Colour.Green )@ both have type @char *@.
180Further examples are:
181\begin{cquote}
182\begin{tabular}{ll}
183\begin{lstlisting}
184int monday_pos = Monday;  // ambiguous
185int monday_value = Monday;  // ambiguous
186char * monday_label = Monday;  // "Monday"
187
188\end{lstlisting}
189&
190\begin{lstlisting}
191enum(double) Math { PI = 3.14159, E = 2.718 };
192int pi_pos = PI;  // 0
193double pi_value = PI;  // 3.14159
194char * pi_label = PI;  // "PI"
195\end{lstlisting}
196\end{tabular}
197\end{cquote}
198Here, @position( Monday )@ and @value( Monday )@ both have type @int@, while all attribute types are unique for enumerator @PI@.
199
200When a resolution is ambiguous, a \textit{resolution precedence} applies: $$value > position > label$$
201\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.
202\begin{lstlisting}[label=lst:enum_inst_precedence]
203enum(double) Foo { Bar };
204int tee = Foo.Bar; // value( Bar );
205\end{lstlisting}
206In 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.
207
208\PAB{Not sure this is going to work.}
209
210\subsection{Enumerator Storage}
211
212Although \CFA enumeration captures three different attributes, an enumeration instance does not store all this information.
213The @sizeof@ a \CFA enumeration instance is always 4 bytes, the same size as a C enumeration instance (@sizeof( int )@).
214It comes from the fact that:
215\begin{enumerate}
216\item
217a \CFA enumeration is always statically typed;
218\item
219it is always resolved as one of its attributes in terms of real usage.
220\end{enumerate}
221When creating an enumeration instance @colour@ and assigning it with the enumerator @Color.Green@, the compiler allocates an integer variable and stores the position 1.
222The invocations of $positions()$, $value()$, and $label()$ turn into calls to special functions defined in the prelude:
223\begin{lstlisting}[label=lst:companion_call]
224position( green );
225>>> position( Colour, 1 ) -> int
226value( green );
227>>> value( Colour, 1 ) -> T
228label( green );
229>>> label( Colour, 1) -> char *
230\end{lstlisting}
231@T@ represents the type declared in the \CFA enumeration defined and @char *@ in the example.
232These generated functions are $Companion Functions$, they take an $companion$ object and the position as parameters.
233
234\subsection{Companion Object and Companion Function}
235
236\begin{lstlisting}[caption={Enum Type Functions}, label=lst:cforall_enum_functions]
237forall( T )
238struct Companion {
239        const T * const values;
240        const char ** const labels;
241        int length;
242};
243\end{lstlisting}
244\CFA creates a @Companion@ object for every \CFA enumeration.
245A companion object has the same name as the enumeration is defined for.
246A companion object stores values and labels of enumeration constants, in the order of the constants defined in the enumeration.
247
248\CFA generates the definition of companion functions.
249Because \CFA implicitly stores enumeration instance as its position, the companion function @position@ does nothing but return the position it is passed.
250Companions function @value@ and @label@ return the array item at the given position of @values@ and @labels@, respectively.
251\begin{lstlisting}[label=lst:companion_definition]
252int position( Companion o, int pos ) { return pos; }
253T value( Companion o, int pos ) { return o.values[ pos ]; }
254char * label( Companion o, int pos ) { return o.labels[ pos ]; }
255\end{lstlisting}
256Notably, the @Companion@ structure definition, and all companion objects, are visible to users.
257A 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@
258\begin{lstlisting}[label=lst:companion_definition_values_labels]
259Colour.values; // read the Companion's values
260values( Colour ); // same as Colour.values
261\end{lstlisting}
262
263\subsection{User Define Enumeration Functions}
264
265Companion objects make extending features for \CFA enumeration easy.
266\begin{lstlisting}[label=lst:companion_user_definition]
267char * charastic_string( Companion o, int position ) { 
268        return sprintf( "Label: %s; Value: %s", label( o, position ), value( o, position) );
269}
270printf( charactic_string ( Color, 1 ) );
271>>> Label: Green; Value: G
272\end{lstlisting}
273Defining a function takes a Companion object effectively defines functions for all \CFA enumeration.
274
275The \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.
276Therefore, a user can use the syntax with a user-defined enumeration function call:
277\begin{lstlisting}[label=lst:companion_user_definition]
278charactic_string( Color.Green ); // equivalent to charactic_string( Color, 1 )
279>>> Label: Green; Value: G
280\end{lstlisting}
281Similarly, the user can work with the enumeration type itself: (see section ref...)
282\begin{lstlisting}[ label=lst:companion_user_definition]
283void print_enumerators ( Companion o ) { 
284        for ( c : Companion o ) {
285                sout | label (c) | value( c ) ;
286        } 
287}
288print_enumerators( Colour );
289\end{lstlisting}
290
291% \subsection{Runtime Enumeration}
292
293% The companion structure definition is visible to users, and users can create an instance of companion object themselves, which effectively constructs a \textit{Runtime Enumeration}.
294% \begin{lstlisting}[ label=lst:runtime_enum ]
295% const char values[$\,$] = { "Hello", "World" };
296% const char labels[$\,$] = { "First", "Second" };
297% Companion(char *) MyEnum = { .values: values, .labels: labels, .length: 2 };
298% \end{lstlisting}
299% A runtime enumeration can be used to call enumeration functions.
300% \begin{lstlisting}[ label=lst:runtime_enum_usage ]
301% sout | charatstic_string( MyEnum, 1 );
302% >>> Label: Second; Value: World
303% \end{lstlisting}
304% However, a runtime enumeration cannot create an enumeration instance, and it does not support enum-qualified syntax.
305% \begin{lstlisting}[ label=lst:runtime_enum_usage ]
306% MyEnum e = MyEnum.First; // Does not work: cannot create an enumeration instance e,
307%                                   // and MyEnum.First is not recognizable
308% \end{lstlisting}
309% During the compilation, \CFA adds enumeration declarations to an enumeration symbol table and creates specialized function definitions for \CFA enumeration.
310% \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.
311
312% \PAB{Not sure how useful this feature is.}
313
314% \section{Enumeration Features}
315
316A trait is a collection of constraints in \CFA that can be used to describe types.
317The \CFA standard library defines traits to categorize types with related enumeration features.
318
319\section{Enumerator Initialization}
320An enumerator must have a deterministic immutable value, either be explicitly initialized in the enumeration definition, or implicitly initialized by rules.
321
322\subsection{C Enumeration Rule}
323A 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$.
324
325\subsection{Auto Initializable}
326\label{s:AutoInitializable}
327
328
329\CFA enumerations have the same rule in enumeration constant initialization.
330However, only \CFA types that have defined traits for @zero_t@, @one_t@, and an addition operator can be automatically initialized by \CFA.
331
332Specifically, a type is auto-initializable only if it satisfies the trait @AutoInitializable@:
333\begin{lstlisting}
334forall(T)
335trait AutoInitializable {
336        void ?()( T & t, zero_t );
337        void ?()( T & t, one_t );
338        S ?+?( T & t, one_t );
339};
340\end{lstlisting}
341An example of a user-defined @AutoInitializable@ is:
342\begin{lstlisting}[label=lst:sample_auto_Initializable]
343struct Odd { int i; };
344void ?()( Odd & t, zero_t ) { t.i = 1; };
345void ?()( Odd & t, one_t ) { t.i = 2; };
346Odd ?+?( Odd t1, Odd t2 ) { return Odd( t1.i + t2.i); };
347\end{lstlisting}
348When the type of an enumeration is @AutoInitializable@, implicit initialization is available.
349\begin{lstlisting}[label=lst:sample_auto_Initializable_usage]
350enum AutoInitUsage(Odd) {
351        A, B, C = 7, D
352};
353\end{lstlisting}
354In the example, there is no initializer specified for the first enumeration constant @A@, so \CFA initializes it with the value of @zero_t@, which is 1.
355@B@ and @D@ have the values of their $predecessor + one_t$, where @one_t@ has the value 2.
356Therefore, the enumeration is initialized as follows:
357\begin{lstlisting}[label=lst:sample_auto_Initializable_usage_gen]
358enum AutoInitUsage(Odd) {
359        A = 1, B = 3, C = 7, D = 9
360};
361\end{lstlisting}
362Note that there is no mechanism to prevent an even value for the direct initialization, such as @C = 6@.
363
364In \CFA, character, integral, float, and imaginary types are all @AutoInitialiable@.
365\begin{lstlisting}[label=lst:letter]
366enum Alphabet( int ) {
367        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,
368        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
369};
370print( "%c, %c, %c", Alphabet.F, Alphabet.o, Alphabet.z );
371>>> F, o, z
372\end{lstlisting}
373\section{Enumeration Features}
374\subsection{Iteration and Range}
375
376It is convenient to iterate over a \CFA enumeration value, e.g.:
377\begin{lstlisting}[label=lst:range_functions]
378for ( Alphabet alph; Alphabet ) { sout | alph; }
379>>> A B C ... D
380\end{lstlisting}
381The for-loop uses the enumeration type @Alphabet@ its range, and iterates through all enumerators in the order defined in the enumeration.
382@alph@ is the iterating enumeration object, which returns the value of an @Alphabet@ in this context according to the precedence rule.
383
384\textbullet\ \CFA offers a shorthand for iterating all enumeration constants:
385\begin{lstlisting}[label=lst:range_functions]
386for ( Alphabet alph ) { sout | alph; }
387>>> A B C ... D
388\end{lstlisting}
389
390The 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.
391
392\textbullet\ H is implicit up-to exclusive range [0, H).
393\begin{lstlisting}[label=lst:range_function_1]
394for ( alph; Alphabet.D ) { sout | alph; }
395>>> A B C
396\end{lstlisting}
397
398\textbullet\ ~= H is implicit up-to inclusive range [0,H].
399\begin{lstlisting}[label=lst:range_function_2]
400for ( alph; ~= Alphabet.D ) { sout | alph; }
401>>> A B C D
402\end{lstlisting}
403
404\textbullet\ L ~ H is explicit up-to exclusive range [L,H).
405\begin{lstlisting}[label=lst:range_function_3]
406for ( alph; Alphabet.B ~ Alphabet.D  ) { sout | alph; }
407// for ( Alphabet alph = Alphabet.B; alph < Alphabet.D; alph += 1  ); 1 is one_t
408>>> B C
409\end{lstlisting}
410
411\textbullet\ L ~= H is explicit up-to inclusive range [L,H].
412\begin{lstlisting}[label=lst:range_function_4]
413for ( alph; Alphabet.B ~= Alphabet.D  ) { sout | alph; }
414>>> B C D
415\end{lstlisting}
416
417\textbullet\ L -~ H is explicit down-to exclusive range [H,L), where L and H are implicitly interchanged to make the range down-to.
418\begin{lstlisting}[label=lst:range_function_5]
419for ( alph; Alphabet.D -~ Alphabet.B  ) { sout | alph; }
420>>> D C
421\end{lstlisting}
422
423\textbullet\ L -~= H is explicit down-to exclusive range [H,L], where L and H are implicitly interchanged to make the range down-to.
424\begin{lstlisting}[label=lst:range_function_6]
425for ( alph; Alphabet.D -~= Alphabet.B  ) { sout | alph; }
426>>> D C B
427\end{lstlisting}
428
429A user can specify the ``step size'' of an iteration. There are two different stepping schemes of enumeration for-loop.
430\begin{lstlisting}[label=lst:range_function_stepping]
431enum(int) Sequence { A = 10, B = 12, C = 14, D = 16, D  = 18 };
432for ( s; Sequence.A ~= Sequence.D ~ 1  ) { sout | alph; }
433>>> 10 12 14 16 18
434for ( s; Sequence.A ~= Sequence.D; s+=1  ) { sout | alph; }
435>>> 10 11 12 13 14 15 16 17 18
436\end{lstlisting}
437The 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
438\begin{lstlisting}[label=lst:range_function_stepping_converted]
439for ( typeof( value(Sequence.A) ) s=value( Sequence.A ); s <= Sequence.D; s+=1  ) { sout | alph; }
440>>> 10 11 12 13 14 15 16 17 18
441\end{lstlisting}
442
443% \PAB{Explain what each loop does.}
444
445It is also possible to iterate over an enumeration's labels, implicitly or explicitly:
446\begin{lstlisting}[label=lst:range_functions_label_implicit]
447for ( char * alph; Alphabet )
448\end{lstlisting}
449This 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.
450If the value can also be resolved as the @char *@, you might iterate the labels explicitly with the array iteration.
451\begin{lstlisting}[label=lst:range_functions_label_implicit]
452for ( char * ch; labels( Alphabet ) )
453\end{lstlisting}
454
455
456% \subsection{Non-uniform Type}
457% TODO: Working in Progress, might need to change other sections. Conflict with the resolution right now.
458
459% \begin{lstlisting}
460% enum T( int, char * ) {
461%     a=42, b="Hello World"
462% };
463% \end{lstlisting}
464% The enum T declares two different types: int and char *. The enumerators of T hold values of one of the declared types.
465
466\subsection{Enumeration Inheritance}
467
468\begin{lstlisting}[label=lst:EnumInline]
469enum( char * ) Name { Jack = "Jack", Jill = "Jill" };
470enum /* inferred */ Name2 { inline Name, Sue = "Sue", Tom = "Tom" };
471\end{lstlisting}
472\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.
473\begin{lstlisting}[label=lst:EnumInline]
474Name Fred;
475void f( Name2 );
476f( Fred );
477\end{lstlisting}
478If enumeration A declares @inline B@ in its enumeration body, enumeration A is the "inlining enum" and enumeration B is the "inlined enum".
479
480An 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.
481\begin{lstlisting}[label=lst:EnumInline]
482enum /* inferred */ Name2 { inline Name, Sue = "Sue", Tom = "Tom" };
483// is equivalent to enum Name2 { Jack = "Jack", Jill="Jill", Sue = "Sue", Tom = "Tom" };
484\end{lstlisting}
485Name.Jack is equivalent to Name2.Jack. Their attributes are all identical. Opening both Name and Name2 in the same scope will not introduce ambiguity.
486\begin{lstlisting}[label=lst:EnumInline]
487with( Name, Name2 ) { Jack; } // Name.Jack and Name2.Jack are equivalent. No ambiguity
488\end{lstlisting}
489
490\section{Implementation}
491
492\subsection{Compiler Representation}
493The 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:
494\begin{lstlisting}[label=lst:EnumDecl]
495forall(T)
496class EnumDecl {
497    T* values;
498    char** label;
499};
500\end{lstlisting}
501
502The internal representation of an enumeration constant is @EnumInstType@.
503An @EnumInstType@ has a reference to the \CFA-enumeration declaration and the position of the enumeration constant.
504\begin{lstlisting}[label=lst:EnumInstType]
505class EnumInstType {
506    EnumDecl enumDecl;
507    int position;
508};
509\end{lstlisting}
510In 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>@.
511
512% \subsection{Preluede}
513% \CFA places the definition of Companion structure and non-parameterized Companion functions in the prelude, visible globally.
514
515\subsection{Declaration}
516
517The qualified enumeration syntax is dedicated to \CFA enumeration.
518\begin{lstlisting}[label=lst:range_functions]
519enum (type_declaration) name { enumerator = const_expr, enumerator = const_expr, ... }
520\end{lstlisting}
521A compiler stores the name, the underlying type, and all enumerators in an @enumeration table@.
522During the $Validation$ pass, the compiler links the type declaration to the type's definition.
523It 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.
524If the declared type is not @AutoInitializable@, \CFA rejects the enumeration definition.
525Otherwise, it attempts to initialize enumerators with the enumeration initialization pattern. (a reference to a future initialization pattern section)
526
527\begin{lstlisting}[label=lst:init]
528struct T { ... };
529void ?{}( T & t, zero_t ) { ... };
530void ?{}( T & t, one_t ) { ... };
531T ?+?( T & lhs, T & rhs ) { ... };
532
533enum (T) Sample { 
534        Zero: 0 /* zero_t */,
535        One: Zero + 1 /* ?+?( Zero, one_t ) */ , ...
536};
537\end{lstlisting}
538Challenge: \\
539The value of an enumerator, or the initializer, requires @const_expr@.
540While 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.
541Might not be able to implement a \emph{correct} static check.
542
543\CFA $autogens$ a Companion object for the declared enumeration.
544\begin{lstlisting}[label=lst:companion]
545Companion( T ) Sample {
546        .values: { 0, 0+1, 0+1+1, 0+1+1+1, ... }, /* 0: zero_t, 1: one_t, +: ?+?{} */
547        .labels: { "Zero", "One", "Two", "Three", ...},
548        .length: /* number of enumerators */
549};
550\end{lstlisting}
551\CFA stores values as intermediate expressions because the result of the function call to the function @?+?{}(T&, T&)@ is statically unknown to \CFA.
552But the result is computed at run time, and the compiler ensures the @values@ are not changed.
553
554\subsection{Qualified Expression}
555
556\CFA uses qualified expression to address the scoping of \CFA-enumeration.
557\begin{lstlisting}[label=lst:qualified_expression]
558aggregation_name.field;
559\end{lstlisting}
560The qualified expression is not dedicated to \CFA enumeration.
561It is a feature that is supported by other aggregation in \CFA as well, including a C enumeration.
562When C enumerations are unscoped, the qualified expression syntax still helps to disambiguate names in the context.
563\CFA recognizes if the expression references a \CFA aggregation by searching the presence of @aggregation_name@ in the \CFA enumeration table.
564If the @aggregation_name@ is identified as a \CFA enumeration, the compiler checks if @field@ presents in the declared \CFA enumeration.
565
566\subsection{\lstinline{with} Clause/Statement}
567Instead of qualifying an enumeration expression every time, the @with@ can be used to expose enumerators to the current scope, making them directly accessible.
568\begin{lstlisting}[label=lst:declaration]
569enum Color( char * ) { Red="R", Green="G", Blue="B" };
570enum Animal( int ) { Cat=10, Dog=20 };
571with ( Color, Animal ) {
572    char * red_string = Red; // value( Color.Red )
573    int cat = Cat; // value( Animal.Cat )
574}
575\end{lstlisting}
576The \lstinline{with} might introduce ambiguity to a scope. Consider the example:
577\begin{lstlisting}[label=lst:declaration]
578enum Color( char * ) { Red="R", Green="G", Blue="B" };
579enum RGB( int ) { Red=0, Green=1, Blue=2 };
580with ( Color, RGB ) {
581    // int red = Red;
582}
583\end{lstlisting}
584\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.
585
586\subsection{Instance Declaration}
587
588
589\begin{lstlisting}[label=lst:var_declaration]
590enum Sample s1;
591\end{lstlisting}
592
593The declaration \CFA-enumeration variable has the same syntax as the C-enumeration. Internally, such a variable will be represented as an EnumInstType.
594\begin{lstlisting}[label=lst:declaration_code]
595int s1;
596\end{lstlisting}
597The 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, with respect to the @Unification@ rule
598
599\subsection{Unification and Resolution }
600
601
602\begin{lstlisting}
603enum Colour( char * ) { Red = "R", Green = "G", Blue = "B"  };
604\end{lstlisting}
605The @EnumInstType@ is convertible to other types.
606A \CFA enumeration expression is implicitly \emph{overloaded} with its three different attributes: value, position, and label.
607The \CFA compilers need to resolve an @EnumInstType@ as one of its attributes based on the current context.
608
609\begin{lstlisting}[caption={Null Context}, label=lst:null_context]
610{
611        Colour.Green;
612}
613\end{lstlisting}
614In example~\ref{lst:null_context}, the environment gives no information to help with the resolution of @Colour.Green@.
615In this case, any of the attributes is resolvable.
616According to the \textit{precedence rule}, the expression with @EnumInstType@ resolves as @value( Colour.Green )@.
617The @EnumInstType@ is converted to the type of the value, which is statically known to the compiler as @char *@.
618When the compilation reaches the code generation, the compiler outputs code for type @char *@ with the value @"G"@.
619\begin{lstlisting}[caption={Null Context Generated Code}, label=lst:null_context]
620{
621        "G";
622}
623\end{lstlisting}
624\begin{lstlisting}[caption={int Context}, label=lst:int_context]
625{
626        int g = Colour.Green;
627}
628\end{lstlisting}
629The assignment expression gives a context for the EnumInstType resolution.
630The EnumInstType is used as an @int@, and \CFA needs to determine which of the attributes can be resolved as an @int@ type.
631The functions $Unify( T1, T2 ): bool$ take two types as parameters and determine if one type can be used as another.
632In example~\ref{lst:int_context}, the compiler is trying to unify @int@ and @EnumInstType@ of @Colour@.
633$$Unification( int, EnumInstType<Colour> )$$ which turns into three Unification call
634\begin{lstlisting}[label=lst:attr_resolution_1]
635{
636        Unify( int, char * ); // unify with the type of value
637        Unify( int, int ); // unify with the type of position
638        Unify( int, char * ); // unify with the type of label
639}
640\end{lstlisting}
641\begin{lstlisting}[label=lst:attr_resolution_precedence]
642{
643        Unification( T1, EnumInstType<T2> ) {
644                if ( Unify( T1, T2 ) ) return T2;
645                if ( Unify( T1, int ) ) return int;
646                if ( Unify( T1, char * ) ) return char *;
647                Error: Cannot Unify T1 with EnumInstType<T2>;
648        }
649}
650\end{lstlisting}
651After the unification, @EnumInstType@ is replaced by its attributes.
652
653\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
654{
655        T2 foo ( T1 ); // function take variable with T1 as a parameter
656        foo( EnumInstType<T3> ); // Call foo with a variable has type EnumInstType<T3>
657        >>>> Unification( T1, EnumInstType<T3> )
658}
659\end{lstlisting}
660% The conversion can work backward: in restrictive cases, attributes of can be implicitly converted back to the EnumInstType.
661Backward conversion:
662\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
663{
664        enum Colour colour = 1;
665}
666\end{lstlisting}
667
668\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
669{
670   Unification( EnumInstType<Colour>, int ) >>> label
671}
672\end{lstlisting}
673@int@ can be unified with the label of Colour.
674@5@ is a constant expression $\Rightarrow$ Compiler knows the value during the compilation $\Rightarrow$ turns it into
675\begin{lstlisting}
676{
677   enum Colour colour = Colour.Green;
678}
679\end{lstlisting}
680Steps:
681\begin{enumerate}
682\item
683identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
684\item
685@unification( EnumInstType<Colour>, int )@: @position( EnumInstType< Colour > )@
686\item
687return the enumeration constant at position 1
688\end{enumerate}
689\begin{lstlisting}
690{
691        enum T (int) { ... } // Declaration
692        enum T t = 1;
693}
694\end{lstlisting}
695Steps:
696\begin{enumerate}
697\item
698identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
699\item
700@unification( EnumInstType<Colour>, int )@: @value( EnumInstType< Colour > )@
701\item
702return the FIRST enumeration constant that has the value 1, by searching through the values array
703\end{enumerate}
704The 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
705
706\subsection{Casting}
707Casting an EnumInstType to some other type T works similarly to unify the EnumInstType with T. For example:
708\begin{lstlisting}
709enum( int ) Foo { A = 10, B = 100, C = 1000 };
710(int) Foo.A;
711\end{lstlisting}
712The \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.
713
714\subsection{Value Conversion}
715As 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.
716
717\begin{lstlisting}
718Foo a; // int a;
719int j = a;
720char * s = a;
721\end{lstlisting}
722Assume 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
723\begin{lstlisting}
724int j = value( Foo, a )
725\end{lstlisting}
726Similarly, the generated code for the third line is
727\begin{lstlisting}
728char * j = label( Foo, a )
729\end{lstlisting}
730
731\end{document}
732
733% Local Variables: %
734% tab-width: 4 %
735% compile-command: "pdflatex enum.tex" %
736% End: %
Note: See TracBrowser for help on using the repository browser.