Changes in / [69ab896:5546eee4]

File:

• doc/proposals/enum.tex (modified) (5 diffs)

doc/proposals/enum.tex

@@ -205 +205 @@
 \end{lstlisting}
 
-\section{Enumeration Characteristic}
-
-\subsection{Enumerator Storage}
+\section{Enumeration Storage}
+
+\subsection{Enumeration Variable}
 
 Although \CFA enumeration captures three different attributes, an enumeration instance does not store all this information.
@@ -231 +231 @@
 These generated functions are $Companion Functions$, they take an $companion$ object and the position as parameters.
 
+\subsection{Enumeration Data}
+\begin{lstlisting}[label=lst:enumeration_backing_data]
+enum(T) E { ... };
+// backing data
+T* E_values;
+char** E_labels;
+\end{lstlisting}
+Storing values and labels as arrays can sometimes help support enumeration features. However, the data structures are the overhead for the programs. We want to reduce the memory usage for enumeration support by:
+\begin{itemize}
+    \item Only generates the data array if necessary
+    \item The compilation units share the data structures. No extra overhead if the data structures are requested multiple times.
+\end{itemize}
+
+
+\subsection{Aggressive Inline}
+To avoid allocating memory for enumeration data structures, \CFA inline the result of enumeration attribute pseudo-function whenever it is possible. 
+\begin{lstlisting}[label=lst:enumeration_inline]
+enum(int) OddNumber { A=1, B=3 };
+sout | "A: " | OddNumber.A | "B: " | OddNumber.B | "A+B: " | OddNumber.A + OddNumber.B
+\end{lstlisting}
+Instead of calling pseudo-function @value@ on expression $OddNumber.A$ and $OddNumber.B$, because the result is known statistically, \CFA will inline the constant expression 1 and 3, respectively. Because no runtime lookup for enumeration value is necessary, \CFA will not generate data structure for enumeration OddNumber.
+
+\subsection{Weak Reference}
+\begin{lstlisting}[label=lst:week_ref]
+enum(int) OddNumber { A=1, B=3 };
+enum OddNumber i = ...;
+...
+sout | OddNumber;
+\end{lstlisting}
+In this example, \CFA cannot determine the static value of the enum variable i, and Runtime lookup is necessary. The OddNumber can be referenced in multiple compilations, and allocating the arrays in all compilation units is not desirable. \CFA addresses this by declaring the value array as a weak reference. All compilation units reference OddNumber have weak references to the same enumeration data structure. No extra memory is allocated if more compilation units reference OddNumber, and the OddNumber is initialized once.
+
+\section{Unification}
+
 \subsection{Enumeration as Value}
-An \CFA enumeration with base type T can be used seamlessly as T. 
+\label{section:enumeration_as_value}
+An \CFA enumeration with base type T can be used seamlessly as T, without explicitly calling the pseudo-function value. 
 \begin{lstlisting}[label=lst:implicit_conversion]
 char * green_value = Colour.Green; // "G"
 // Is equivalent to 
-char * green_value = value( Color.Green ); "G"
-\end{lstlisting}
-\CFA recognizes @Colour.Green@ as an Expression with enumeration type. [reference to resolution distance] An enumeration type can be safely converted into its value type T, @char *@ in the example. When assigning @Colour.Green@ to a reference @green_value@, which has type @char *@, the compiler adds the distance between an enumeration and type T, and the distance between type T and @char *@. If the distance is safe, \CFA will replace the expression @Colour.Green@ with @value( Colour.Green )@.
-
-\subsection{Variable Overloading}
+// char * green_value = value( Color.Green ); "G"
+\end{lstlisting}
+
+\subsection{Unification Distance}
+\begin{lstlisting}[label=lst:unification_distance_example]
+T_2 Foo(T1);
+\end{lstlisting}
+The @Foo@ function expects a parameter with type @T1@. In C, only a value with the exact type T1 can be used as a parameter for @Foo@. In \CFA, @Foo@ accepts value with some type @T3@ as long as @distance(T1, T3)@ is not @Infinite@.
+
+@path(A, B)@ is a compiler concept that returns one of the following:
+\begin{itemize}
+    \item Zero or 0, if and only if $A == B$.
+    \item Safe, if B can be used as A without losing its precision, or B is a subtype of A. 
+    \item Unsafe, if B loses its precision when used as A, or A is a subtype of B.
+    \item Infinite, if B cannot be used as A. A is not a subtype of B and B is not a subtype of A.
+\end{itemize}
+
+For example, @path(int, int)==Zero@, @path(int, char)==Safe@, @path(int, double)==Unsafe@, @path(int, struct S)@ is @Infinite@ for @struct S{}@.
+@distance(A, C)@ is the minimum sum of paths from A to C. For example, if @path(A, B)==i@, @path(B, C)==j@, and @path(A, C)=k@, then $$distance(A,C)==min(path(A,B), path(B,C))==i+j$$.
+
+(Skip over the distance matrix here because it is mostly irrelevant for enumeration discussion. In the actual implementation, distance( E, T ) is 1.)
+
+The arithmetic of distance is the following:
+\begin{itemize}
+    \item $Zero + v= v$, for some value v.
+    \item $Safe * k <  Unsafe$, for finite k. 
+    \item $Unsafe * k < Infinite$, for finite k.
+    \item $Infinite + v = Infinite$, for some value v.
+\end{itemize}
+
+For @enum(T) E@, @path(T, E)==Safe@ and @path(E,T)==Infinite@. In other words, enumeration type E can be @safely@ used as type T, but type T cannot be used when the resolution context expects a variable with enumeration type @E@.
+
+
+\subsection{Variable Overloading and Parameter Unification}
+\CFA allows variable names to be overloaded. It is possible to overload a variable that has type T and an enumeration with type T.
 \begin{lstlisting}[label=lst:variable_overload]
+char * green = "Green";
+Colour green = Colour.Green; // "G"
+
+void bar(char * s) { return s; }
 void foo(Colour c) { return value( c ); }
-void bar(char * s) { return s; }
-Colour green = Colour.Green; // "G"
-char * green = "Green";
+
 foo( green ); // "G"
 bar( green ); // "Green"
 \end{lstlisting}
+\CFA's conversion distance helps disambiguation in this overloading. For the function @bar@ which expects the parameter s to have type @char *@, $distance(char *,char *) == Zero$ while $distance(char *, Colour) == Safe$, the path from @char *@ to the enumeration with based type @char *@, \CFA chooses the @green@ with type @char *@ unambiguously. On the other hand, for the function @foo@, @distance(Colour, char *)@ is @Infinite@, @foo@ picks the @green@ with type @char *@.
 
 \subsection{Function Overloading}
+Similarly, functions can be overloaded with different signatures. \CFA picks the correct function entity based on the distance between parameter types and the arguments.
 \begin{lstlisting}[label=lst:function_overload]
-void foo(Colour c) { return "It is an enum"; }
-void foo(char * s) { return "It is a string"; }
+Colour green = Colour.Green; 
+void foo(Colour c) { sout | "It is an enum"; } // First foo
+void foo(char * s) { sout | "It is a string"; } // Second foo
 foo( green ); // "It is an enum"
 \end{lstlisting}
-
-As a consequence, the semantics of using \CFA enumeration as a flag for selection is identical to C enumeration.
-
-
-% \section{Enumeration Features}
-
-A trait is a collection of constraints in \CFA that can be used to describe types.
-The \CFA standard library defines traits to categorize types with related enumeration features.
+Because @distance(Colour, Colour)@ is @Zero@ and @distance(char *, Colour)@ is @Safe@, \CFA determines the @foo( green )@ is a call to the first foo.
+
+\subsection{Attributes Functions}
+The pseudo-function @value()@ "unboxes" the enumeration and the type of the expression is the underlying type. Therefore, in the section~\ref{section:enumeration_as_value} when assigning @Colour.Green@ to variable typed @char *@, the resolution distance is @Safe@, while assigning @value(Color.Green) to @char *) has resolution distance @Zero@.
+
+\begin{lstlisting}[label=lst:declaration_code]
+int s1;
+\end{lstlisting}
+The 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, concerning the @Unification@ rule
+
+% \subsection{Unification and Resolution (this implementation will probably not be used, safe as reference for now)}
+
+% \begin{lstlisting}
+% enum Colour( char * ) { Red = "R", Green = "G", Blue = "B"  };
+% \end{lstlisting}
+% The @EnumInstType@ is convertible to other types.
+% A \CFA enumeration expression is implicitly \emph{overloaded} with its three different attributes: value, position, and label.
+% The \CFA compilers need to resolve an @EnumInstType@ as one of its attributes based on the current context. 
+
+% \begin{lstlisting}[caption={Null Context}, label=lst:null_context]
+% {
+%       Colour.Green;
+% }
+% \end{lstlisting}
+% In example~\ref{lst:null_context}, the environment gives no information to help with the resolution of @Colour.Green@.
+% In this case, any of the attributes is resolvable.
+% According to the \textit{precedence rule}, the expression with @EnumInstType@ resolves as @value( Colour.Green )@.
+% The @EnumInstType@ is converted to the type of the value, which is statically known to the compiler as @char *@.
+% When the compilation reaches the code generation, the compiler outputs code for type @char *@ with the value @"G"@.
+% \begin{lstlisting}[caption={Null Context Generated Code}, label=lst:null_context]
+% {
+%       "G";
+% }
+% \end{lstlisting}
+% \begin{lstlisting}[caption={int Context}, label=lst:int_context]
+% {
+%       int g = Colour.Green;
+% }
+% \end{lstlisting}
+% The assignment expression gives a context for the EnumInstType resolution.
+% The EnumInstType is used as an @int@, and \CFA needs to determine which of the attributes can be resolved as an @int@ type.
+% The functions $Unify( T1, T2 ): bool$ take two types as parameters and determine if one type can be used as another.
+% In example~\ref{lst:int_context}, the compiler is trying to unify @int@ and @EnumInstType@ of @Colour@.
+% $$Unification( int, EnumInstType<Colour> )$$ which turns into three Unification call
+% \begin{lstlisting}[label=lst:attr_resolution_1]
+% {
+%       Unify( int, char * ); // unify with the type of value
+%       Unify( int, int ); // unify with the type of position
+%       Unify( int, char * ); // unify with the type of label
+% }
+% \end{lstlisting}
+% \begin{lstlisting}[label=lst:attr_resolution_precedence]
+% {
+%       Unification( T1, EnumInstType<T2> ) {
+%               if ( Unify( T1, T2 ) ) return T2;
+%               if ( Unify( T1, int ) ) return int;
+%               if ( Unify( T1, char * ) ) return char *;
+%               Error: Cannot Unify T1 with EnumInstType<T2>;
+%       }
+% }
+% \end{lstlisting}
+% After the unification, @EnumInstType@ is replaced by its attributes.
+
+% \begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
+% {
+%       T2 foo ( T1 ); // function take variable with T1 as a parameter
+%       foo( EnumInstType<T3> ); // Call foo with a variable has type EnumInstType<T3>
+%       >>>> Unification( T1, EnumInstType<T3> )
+% }
+% \end{lstlisting}
+% % The conversion can work backward: in restrictive cases, attributes of can be implicitly converted back to the EnumInstType. 
+% Backward conversion:
+% \begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
+% {
+%       enum Colour colour = 1;
+% }
+% \end{lstlisting}
+
+% \begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
+% {
+%    Unification( EnumInstType<Colour>, int ) >>> label
+% }
+% \end{lstlisting}
+% @int@ can be unified with the label of Colour.
+% @5@ is a constant expression $\Rightarrow$ Compiler knows the value during the compilation $\Rightarrow$ turns it into 
+% \begin{lstlisting}
+% {
+%    enum Colour colour = Colour.Green; 
+% }
+% \end{lstlisting}
+% Steps:
+% \begin{enumerate}
+% \item
+% identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
+% \item
+% @unification( EnumInstType<Colour>, int )@: @position( EnumInstType< Colour > )@
+% \item
+% return the enumeration constant at position 1
+% \end{enumerate}
+% \begin{lstlisting}
+% {
+%       enum T (int) { ... } // Declaration
+%       enum T t = 1; 
+% }
+% \end{lstlisting}
+% Steps:
+% \begin{enumerate}
+% \item
+% identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
+% \item
+% @unification( EnumInstType<Colour>, int )@: @value( EnumInstType< Colour > )@
+% \item
+% return the FIRST enumeration constant that has the value 1, by searching through the values array
+% \end{enumerate}
+% The 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 
+
+% \subsection{Casting}
+% Casting an EnumInstType to some other type T works similarly to unify the EnumInstType with T. For example:
+% \begin{lstlisting}
+% enum( int ) Foo { A = 10, B = 100, C = 1000 };
+% (int) Foo.A;
+% \end{lstlisting}
+% The \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. 
+
+% \subsection{Value Conversion}
+% As 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.
+
+% \begin{lstlisting}
+% Foo a; // int a;
+% int j = a;
+% char * s = a;
+% \end{lstlisting}
+% Assume 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
+% \begin{lstlisting}
+% int j = value( Foo, a )
+% \end{lstlisting}
+% Similarly, the generated code for the third line is 
+% \begin{lstlisting}
+% char * j = label( Foo, a )
+% \end{lstlisting}
+
 
 \section{Enumerator Initialization}
@@ -436 +638 @@
 \section{Implementation}
 
-\subsection{Compiler Representation}
+\subsection{Compiler Representation (Reworking)}
 The 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:
 \begin{lstlisting}[label=lst:EnumDecl]
@@ -464 +666 @@
 Companion data are needed only if the according pseudo-functions are called. For example, the value of the enumeration Workday is loaded only if there is at least one compilation that has call $value(Workday)$. Once the values are loaded, all compilations share these values array to reduce memory usage.
 
-<Investiage: how to implement this is huge>
 
 \subsection{(Rework) Companion Object and Companion Function}
@@ -636 +837 @@
 
 The declaration \CFA-enumeration variable has the same syntax as the C-enumeration. Internally, such a variable will be represented as an EnumInstType.
-\begin{lstlisting}[label=lst:declaration_code]
-int s1;
-\end{lstlisting}
-The 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
-
-\subsection{Unification and Resolution }
-
-
-\begin{lstlisting}
-enum Colour( char * ) { Red = "R", Green = "G", Blue = "B"  };
-\end{lstlisting}
-The @EnumInstType@ is convertible to other types.
-A \CFA enumeration expression is implicitly \emph{overloaded} with its three different attributes: value, position, and label.
-The \CFA compilers need to resolve an @EnumInstType@ as one of its attributes based on the current context. 
-
-\begin{lstlisting}[caption={Null Context}, label=lst:null_context]
-{
-        Colour.Green;
-}
-\end{lstlisting}
-In example~\ref{lst:null_context}, the environment gives no information to help with the resolution of @Colour.Green@.
-In this case, any of the attributes is resolvable.
-According to the \textit{precedence rule}, the expression with @EnumInstType@ resolves as @value( Colour.Green )@.
-The @EnumInstType@ is converted to the type of the value, which is statically known to the compiler as @char *@.
-When the compilation reaches the code generation, the compiler outputs code for type @char *@ with the value @"G"@.
-\begin{lstlisting}[caption={Null Context Generated Code}, label=lst:null_context]
-{
-        "G";
-}
-\end{lstlisting}
-\begin{lstlisting}[caption={int Context}, label=lst:int_context]
-{
-        int g = Colour.Green;
-}
-\end{lstlisting}
-The assignment expression gives a context for the EnumInstType resolution.
-The EnumInstType is used as an @int@, and \CFA needs to determine which of the attributes can be resolved as an @int@ type.
-The functions $Unify( T1, T2 ): bool$ take two types as parameters and determine if one type can be used as another.
-In example~\ref{lst:int_context}, the compiler is trying to unify @int@ and @EnumInstType@ of @Colour@.
-$$Unification( int, EnumInstType<Colour> )$$ which turns into three Unification call
-\begin{lstlisting}[label=lst:attr_resolution_1]
-{
-        Unify( int, char * ); // unify with the type of value
-        Unify( int, int ); // unify with the type of position
-        Unify( int, char * ); // unify with the type of label
-}
-\end{lstlisting}
-\begin{lstlisting}[label=lst:attr_resolution_precedence]
-{
-        Unification( T1, EnumInstType<T2> ) {
-                if ( Unify( T1, T2 ) ) return T2;
-                if ( Unify( T1, int ) ) return int;
-                if ( Unify( T1, char * ) ) return char *;
-                Error: Cannot Unify T1 with EnumInstType<T2>;
-        }
-}
-\end{lstlisting}
-After the unification, @EnumInstType@ is replaced by its attributes.
-
-\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
-{
-        T2 foo ( T1 ); // function take variable with T1 as a parameter
-        foo( EnumInstType<T3> ); // Call foo with a variable has type EnumInstType<T3>
-        >>>> Unification( T1, EnumInstType<T3> )
-}
-\end{lstlisting}
-% The conversion can work backward: in restrictive cases, attributes of can be implicitly converted back to the EnumInstType. 
-Backward conversion:
-\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
-{
-        enum Colour colour = 1;
-}
-\end{lstlisting}
-
-\begin{lstlisting}[caption={Unification Functions}, label=lst:unification_func_call]
-{
-   Unification( EnumInstType<Colour>, int ) >>> label
-}
-\end{lstlisting}
-@int@ can be unified with the label of Colour.
-@5@ is a constant expression $\Rightarrow$ Compiler knows the value during the compilation $\Rightarrow$ turns it into 
-\begin{lstlisting}
-{
-   enum Colour colour = Colour.Green; 
-}
-\end{lstlisting}
-Steps:
-\begin{enumerate}
-\item
-identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
-\item
-@unification( EnumInstType<Colour>, int )@: @position( EnumInstType< Colour > )@
-\item
-return the enumeration constant at position 1
-\end{enumerate}
-\begin{lstlisting}
-{
-        enum T (int) { ... } // Declaration
-        enum T t = 1; 
-}
-\end{lstlisting}
-Steps:
-\begin{enumerate}
-\item
-identify @1@ as a constant expression with type @int@, and the value is statically known as @1@
-\item
-@unification( EnumInstType<Colour>, int )@: @value( EnumInstType< Colour > )@
-\item
-return the FIRST enumeration constant that has the value 1, by searching through the values array
-\end{enumerate}
-The 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 
-
-\subsection{Casting}
-Casting an EnumInstType to some other type T works similarly to unify the EnumInstType with T. For example:
-\begin{lstlisting}
-enum( int ) Foo { A = 10, B = 100, C = 1000 };
-(int) Foo.A;
-\end{lstlisting}
-The \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. 
-
-\subsection{Value Conversion}
-As 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.
-
-\begin{lstlisting}
-Foo a; // int a;
-int j = a;
-char * s = a;
-\end{lstlisting}
-Assume 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
-\begin{lstlisting}
-int j = value( Foo, a )
-\end{lstlisting}
-Similarly, the generated code for the third line is 
-\begin{lstlisting}
-char * j = label( Foo, a )
-\end{lstlisting}