Index: doc/proposals/enum.tex =================================================================== --- doc/proposals/enum.tex (revision 81da3da480e889a2c890e4b9dc274a74be5c2037) +++ doc/proposals/enum.tex (revision 21ce2c70fd9046a9729e56a718e82628931c9b2c) @@ -231,37 +231,208 @@ These generated functions are $Companion Functions$, they take an $companion$ object and the position as parameters. +\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 )$$ 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 ) { +% if ( Unify( T1, T2 ) ) return T2; +% if ( Unify( T1, int ) ) return int; +% if ( Unify( T1, char * ) ) return char *; +% Error: Cannot Unify T1 with EnumInstType; +% } +% } +% \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 ); // Call foo with a variable has type EnumInstType +% >>>> Unification( T1, EnumInstType ) +% } +% \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, 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, 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, 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@ 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@ 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,5 +607,5 @@ \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,5 +635,4 @@ 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. - \subsection{(Rework) Companion Object and Companion Function} @@ -636,140 +806,4 @@ 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 )$$ 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 ) { - if ( Unify( T1, T2 ) ) return T2; - if ( Unify( T1, int ) ) return int; - if ( Unify( T1, char * ) ) return char *; - Error: Cannot Unify T1 with EnumInstType; - } -} -\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 ); // Call foo with a variable has type EnumInstType - >>>> Unification( T1, EnumInstType ) -} -\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, 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, 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, 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@ 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@ 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}