Index: c/theses/jiada_liang_MMath/CEnum.tex =================================================================== --- doc/theses/jiada_liang_MMath/CEnum.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ (revision ) @@ -1,130 +1,0 @@ -\chapter{C Enumeration in \CFA} - -\CFA supports legacy C enumeration using the same syntax for backwards compatibility. -A C-style enumeration in \CFA is called a \newterm{C Enum}. -The semantics of the C Enum is mostly consistent with C with some restrictions. -The following sections detail all of my new contributions to enumerations in C. - - -\section{Enumerator Visibility} -\label{s:EnumeratorVisibility} - -In C, unscoped enumerators present a \newterm{naming problem} when multiple enumeration types appear in the same scope with duplicate enumerator names. -\begin{cfa} -enum E1 { First, Second, Third, Fourth }; -enum E2 { @Fourth@, @Third@, @Second@, @First@ }; $\C{// same enumerator names}$ -\end{cfa} -There is no mechanism in C to resolve these naming conflicts other than renaming one of the duplicates, which may be impossible if the conflict comes from system include files. - -The \CFA type-system allows extensive overloading, including enumerators. -Hence, most ambiguities among C enumerators are implicitly resolved by the \CFA type system, possibly without any programmer knowledge of the conflict. -In addition, C Enum qualification is added, exactly like aggregate field-qualification, to disambiguate. -\VRef[Figure]{f:EnumeratorVisibility} shows how resolution, qualification, and casting are used to disambiguate situations for enumerations @E1@ and @E2@. - -\begin{figure} -\begin{cfa} -E1 f() { return Third; } $\C{// overload functions with different return types}$ -E2 f() { return Fourth; } -void g( E1 e ); -void h( E2 e ); -void foo() { $\C{// different resolutions and dealing with ambiguities}$ - E1 e1 = First; E2 e2 = First; $\C{// initialization}$ - e1 = Second; e2 = Second; $\C{// assignment}$ - e1 = f(); e2 = f(); $\C{// function return}$ - g( First ); h( First ); $\C{// function argument}$ - int i = @E1.@First + @E2.@First; $\C{// disambiguate with qualification}$ - int j = @(E1)@First + @(E2)@First; $\C{// disambiguate with cast}$ -} -\end{cfa} -\caption{Enumerator Visibility and Disambiguating} -\label{f:EnumeratorVisibility} -\end{figure} - - -\section{Enumerator Scoping} - -A C Enum can be scoped, using @'!'@, so the enumerator constants are not projected into the enclosing scope. -\begin{cfa} -enum Week @!@ { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun }; -enum RGB @!@ { Red, Green, Blue }; -\end{cfa} -Now the enumerators \emph{must} be qualified with the associated enumeration type. -\begin{cfa} -Week week = @Week.@Mon; -week = @Week.@Sat; -RGB rgb = @RGB.@Red; -rgb = @RGB.@Blue; -\end{cfa} -% with feature unimplemented -It is possible to toggle back to unscoped using the \CFA @with@ auto-qualification clause/statement (see also \CC \lstinline[language=c++]{using enum} in Section~\ref{s:C++RelatedWork}). -\begin{cfa} -with ( @Week@, @RGB@ ) { $\C{// type names}$ - week = @Sun@; $\C{// no qualification}$ - rgb = @Green@; -} -\end{cfa} -As in Section~\ref{s:EnumeratorVisibility}, opening multiple scoped enumerations in a @with@ can result in duplicate enumeration names, but \CFA implicit type resolution and explicit qualification/casting handle this localized scenario. - -A partially implemented extension to enumerator scoping is providing a combination of scoped and unscoped enumerators, using individual denotations, where @'^'@ means unscoped. -\begin{cfa} -enum E1 { @!@A, @^@B, C }; -enum E2 @!@ { @!@A, @^@B, C }; -\end{cfa} -For @E1@, @A@ is scoped; @B@ and @C@ are unscoped. -For @E2@, @A@ and @C@ are scoped; @B@ is unscoped. -Finding a use case is important to justify completing this extension. - - -\section{Type Safety} - -As in Section~\ref{s:Usage}, C's implicit bidirectional conversion between enumeration and integral type raises a safety concern. -In \CFA, the conversion is changed to unidirectional: an enumeration can be implicitly converted into an integral type, with an associated @safe@ conversion cost. -But an integral type cannot be implicitly converted into a C enumeration because the conversion cost is set to @infinity@. -\begin{cfa} -enum Bird { Penguin, Robin, Eagle }; -enum Fish { Shark, Salmon, Whale }; - -int i = Robin; $\C{// allow, implicitly converts to 1}$ -enum Bird @bird = 1;@ $\C{// disallow }$ -enum Bird @bird = Shark;@ $\C{// disallow }$ -\end{cfa} -It is now up to the programmer to insert an explicit cast to force the assignment. -\begin{cfa} -enum Bird bird = @(Bird)@1; -enum Bird bird = @(Bird)@Shark -\end{cfa} - -Note, \CC has the same safe restriction~\cite[C.1.5.7.2]{C++} and provides the same workaround cast. -\begin{description}[parsep=0pt] -\item[Change:] \CC objects of enumeration type can only be assigned values of the same enumeration type. -In C, objects of enumeration type can be assigned values of any integral type. -Example: -\begin{cfa} -enum color { red, blue, green }; -color c = 1; $\C{// valid C, invalid \CC}$ -\end{cfa} -\item[Rationale:] The type-safe nature of \CC. -\item[Effect on original feature:] Deletion of semantically well-defined feature. -\item[Difficulty of converting:] Syntactic transformation. (The type error produced by the assignment can be -automatically corrected by applying an explicit cast.) -\item[How widely used:] Common. -\end{description} - -\begin{comment} -\begin{description}[parsep=0pt] -\item[Change:] In \CC, the type of an enumerator is its enumeration. -In C, the type of an enumerator is @int@. -Example: -\begin{cfa} -enum e { A }; -sizeof(A) == sizeof(int) $\C{// in C}$ -sizeof(A) == sizeof(e) $\C{// in \CC}$ -/* and sizeof(int) is not necessary equal to sizeof(e) */ -\end{cfa} -\item[Rationale:] In \CC, an enumeration is a distinct type. -\item[Effect on original feature:] Change to semantics of well-defined feature. -\item[Difficulty of converting:] Semantic transformation. -\item[How widely used:] Seldom. The only time this affects existing C code is when the size of an enumerator is -taken. Taking the size of an enumerator is not a common C coding practice. -\end{description} -\end{comment} Index: doc/theses/jiada_liang_MMath/CFAenum.tex =================================================================== --- doc/theses/jiada_liang_MMath/CFAenum.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/CFAenum.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -1,12 +1,12 @@ -\chapter{\CFA Enumeration} - -\CFA extends C-Style enumeration by adding a number of new features that bring enumerations inline with other modern programming languages. -Any enumeration extensions must be intuitive to C programmers both in syntax and semantics. -The following sections detail all of my new contributions to enumerations in \CFA. - - -\section{Enumeration Syntax} - -\CFA extends the C enumeration declaration \see{\VRef{s:CEnumeration}} by parameterizing with a type (like a generic type), and adding Plan-9 inheritance \see{\VRef{s:EnumerationInheritance}} using an @inline@ to another enumeration type. +\chapter{\texorpdfstring{\CFA}{Cforall} Enumeration} + +\CFA extends C-Style enumeration by adding a number of new features that bring enumerations in line with other modern programming languages. +Any enumeration extensions must be intuitive to C programmers in syntax and semantics. +The following sections detail my new contributions to enumerations in \CFA. + + +\section{Syntax} + +\CFA extends the C enumeration declaration \see{\VRef{s:CEnumeration}} by parameterizing with a type (like a generic type) and adding Plan-9 inheritance \see{\VRef{s:CFAInheritance}} using an @inline@ to another enumeration type. \begin{cfa}[identifierstyle=\linespread{0.9}\it] $\it enum$-specifier: @@ -24,5 +24,5 @@ -\section{Enumeration Operations} +\section{Operations} \CFA enumerations have access to the three enumerations properties \see{\VRef{s:Terminology}}: label, order (position), and value via three overloaded functions @label@, @posn@, and @value@ \see{\VRef{c:trait} for details}. @@ -43,10 +43,11 @@ A A @0@ 3 \end{cfa} -Finally, there is an additional enumeration routine @countof@ (like @sizeof@, @typeof@) that returns the number of enumerators in an enumeration. -\begin{cfa} -enum(int) E { A, B, C, D }; -countof( E ); // 4 -\end{cfa} -This auto-generated function replaces the C idiom for automatically computing the number of enumerators \see{\VRef{s:Usage}}. +Finally, \CFA introduces an additional enumeration pseudo-function @countof@ (like @sizeof@, @typeof@) that returns the number of enumerators in an enumeration. +\begin{cfa} +enum(int) E { A, B, C, D } e; +countof( E ); // 4, type argument +countof( e ); // 4, variable argument +\end{cfa} +This built-in function replaces the C idiom for automatically computing the number of enumerators \see{\VRef{s:Usage}}. \begin{cfa} enum E { A, B, C, D, @N@ }; // N == 4 @@ -55,27 +56,28 @@ The underlying representation of \CFA enumeration object is its position, saved as an integral type. Therefore, the size of a \CFA enumeration is consistent with a C enumeration. -Attribute function @posn@ performs type substitution on an expression from \CFA type to integral type. -The label and value of an enumerator is stored in a global data structure for each enumeration, where attribute functions @label@/@value@ map an \CFA enumeration object to the corresponding data. -These operations do not apply to C Enums because backwards compatibility means the necessary backing data structures cannot be supplied. +Attribute function @posn@ performs type substitution on an expression from \CFA type to an integral type. +The label and value of an enumerator are stored in a global data structure for each enumeration, where attribute functions @label@/@value@ map an \CFA enumeration object to the corresponding data. +These operations do not apply to C Enums because backward compatibility means the necessary backing data structures cannot be supplied. + \section{Opaque Enumeration} \label{s:OpaqueEnum} -When an enumeration type is empty is it an \newterm{opaque} enumeration. +When an enumeration type is empty. it is an \newterm{opaque} enumeration. \begin{cfa} enum@()@ Mode { O_RDONLY, O_WRONLY, O_CREAT, O_TRUNC, O_APPEND }; \end{cfa} -Here, the internal representation is chosen by the compiler and hidden, so the enumerators cannot be initialized. -Compared to the C enum, opaque enums are more restrictive in terms of typing and cannot be implicitly converted to integers. +Here, the compiler chooses the internal representation, which is hidden, so the enumerators cannot be initialized. +Compared to the C enum, opaque enums are more restrictive regarding typing and cannot be implicitly converted to integers. \begin{cfa} Mode mode = O_RDONLY; int www @=@ mode; $\C{// disallowed}$ \end{cfa} -Opaque enumerations have only two attribute properties @label@ and @posn@. +Opaque enumerations have only two attribute properties, @label@ and @posn@. \begin{cfa} char * s = label( O_TRUNC ); $\C{// "O\_TRUNC"}$ int open = posn( O_WRONLY ); $\C{// 1}$ \end{cfa} -The equality and relational operations are available. +Equality and relational operations are available. \begin{cfa} if ( mode @==@ O_CREAT ) ... @@ -87,7 +89,7 @@ \label{s:EnumeratorTyping} -When an enumeration type is specified, all enumerators have that type and can be initialized with constants of that type or compile-time convertable to that type. -Figure~\ref{f:EumeratorTyping} shows a series of examples illustrating that all \CFA types can be use with an enumeration and each type's values used to set the enumerator constants. -Note, the use of the synonyms @Liz@ and @Beth@ in the last declaration. +When an enumeration type is specified, all enumerators have that type and can be initialized with constants of that type or compile-time convertible to that type. +Figure~\ref{f:EumeratorTyping} shows a series of examples illustrating that all \CFA types can be used with an enumeration, and each type's values are used to set the enumerator constants. +Note the use of the synonyms @Liz@ and @Beth@ in the last declaration. Because enumerators are constants, the enumeration type is implicitly @const@, so all the enumerator types in Figure~\ref{f:EumeratorTyping} are logically rewritten with @const@. @@ -130,5 +132,5 @@ }; \end{cfa} -Note, the enumeration type can be a structure (see @Person@ in Figure~\ref{f:EumeratorTyping}), so it is possible to have the equivalent of multiple arrays of companion data using an array of structures. +Note that the enumeration type can be a structure (see @Person@ in Figure~\ref{f:EumeratorTyping}), so it is possible to have the equivalent of multiple arrays of companion data using an array of structures. While the enumeration type can be any C aggregate, the aggregate's \CFA constructors are \emph{not} used to evaluate an enumerator's value. @@ -162,5 +164,6 @@ bar( x ); $\C{// costs (1, 0, 0, 0, 0, 0, 0, 0) or (0, 1, 0, 0, 0, 0, 0, 0)}$ \end{cfa} -Here, candidate (1) has a value conversion cost to convert to the base type, while candidate (2) has an unsafe conversion from @double@ to @int@. +Here, the candidate (1) has a @value@ conversion cost to convert to the base type, while the candidate (2) has an @unsafe@ conversion from @double@ to @int@, +which is a more expensive conversion. Hence, @bar( x )@ resolves @x@ as type @Math@. @@ -176,32 +179,47 @@ \section{Auto Initialization} - -A partially implemented feature is auto-initialization, which works for the C integral type with constant expressions. -\begin{cfa} -enum Week { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun }; // 0-2, 10-13 -\end{cfa} -The complexity of the constant expression depends on the level of computation the compiler implements, \eg \CC \lstinline[language={[GNU]C++}]{constexpr} provides complex compile-time computation across multiple types, which blurs the compilation/runtime boundary. - -If \CFA had powerful compilation expression evaluation, auto initialization would be implemented as follows. -\begin{cfa} -enum E(T) { A, B, C }; -\end{cfa} +\CFA extends C's auto-initialization scheme to \CFA enumeration. For an enumeration type with base type T, the initialization scheme is the following: \begin{enumerate} -\item the first enumerator, @A@, is initialized with @T@'s @zero_t@. -\item otherwise, the next enumerator is initialized with the previous enumerator's value using operator @?++@, where @?++( T )@ can be overloaded for any type @T@. +\item the first enumerator is initialized with @T@'s @zero_t@. +\item Every other enumerator is initialized with its previous enumerator's value "+1", where "+1" is defined in terms of overloaded operator @?+?(T, one_t)@. \end{enumerate} -Unfortunately, constant expressions in C are not powerful and \CFA is only a transpiler, relying on generated C code to perform the detail work. -It is currently beyond the scope of the \CFA project to implement a complex runtime interpreter in the transpiler to evaluate complex expressions across multiple builtin and user-defined type. -Nevertheless, the necessary language concepts exist to support this feature. - - -\section{Enumeration Inheritance} -\label{s:EnumerationInheritance} +\begin{cfa} +struct S { int i; }; +S ?+?( S & s, one_t ) { return s.i++; } +void ?{}( S & s, zero_t ) { s.i = 0; } +enum(S) E { A, B, C, D }; +\end{cfa} + +\section{Subset} + +An enumeration's type can be another enumeration. +\begin{cfa} +enum( char ) Letter { A = 'A', ..., Z = 'Z' }; +enum( @Letter@ ) Greek { Alph = @A@, Beta = @B@, Gamma = @G@, ..., Zeta = @Z@ }; // alphabet intersection +\end{cfa} +Enumeration @Greek@ may have more or less enumerators than @Letter@, but its enumerator values \emph{must} be from @Letter@. +Therefore, the set of @Greek@ enumerator values in a subset of the @Letter@ enumerator values. +@Letter@ is type compatible with enumeration @Letter@ because value conversions are inserted whenever @Letter@ is used in place of @Greek@. +\begin{cfa} +Letter l = A; $\C{// allowed}$ +Greek g = Alph; $\C{// allowed}$ +l = Alph; $\C{// allowed, conversion to base type}$ +g = A; $\C{// {\color{red}disallowed}}$ +void foo( Letter ); +foo( Beta ); $\C{// allowed, conversion to base type}$ +void bar( Greek ); +bar( A ); $\C{// {\color{red}disallowed}}$ +\end{cfa} +Hence, @Letter@ enumerators are not type-compatible with the @Greek@ enumeration, but the reverse is true. + + +\section{Inheritance} +\label{s:CFAInheritance} \CFA Plan-9 inheritance may be used with \CFA enumerations, where Plan-9 inheritance is containment inheritance with implicit unscoping (like a nested unnamed @struct@/@union@ in C). Containment is nominative: an enumeration inherits all enumerators from another enumeration by declaring an @inline statement@ in its enumerator lists. \begin{cfa} -enum( char * ) Names { /* $\see{\VRef[Figure]{s:EnumerationInheritance}}$ */ }; +enum( char * ) Names { /* $\see{\VRef[Figure]{f:EumeratorTyping}}$ */ }; enum( char * ) Names2 { @inline Names@, Jack = "JACK", Jill = "JILL" }; enum( char * ) Names3 { @inline Names2@, Sue = "SUE", Tom = "TOM" }; @@ -216,68 +234,36 @@ Inheritance can be nested, and a \CFA enumeration can inline enumerators from more than one \CFA enumeration, forming a tree-like hierarchy. -However, the uniqueness of enumeration name applies to enumerators, including those from supertypes, meaning an enumeration cannot name enumerator with the same label as its subtype's members, or inherits -from multiple enumeration that has overlapping enumerator label. As a consequence, a new type cannot inherits from both an enumeration and its supertype, or two enumerations with a -common supertype (the diamond problem), since such would unavoidably introduce duplicate enumerator labels. +However, the uniqueness of the enumeration name applies to enumerators, including those from supertypes, meaning an enumeration cannot name an enumerator with the same label as its subtype's members or inherits +from multiple enumeration that has overlapping enumerator labels. Consequently, a new type cannot inherit from an enumeration and its supertype or two enumerations with a +common supertype (the diamond problem) since such would unavoidably introduce duplicate enumerator labels. The base type must be consistent between subtype and supertype. -When an enumeration inherits enumerators from another enumeration, it copies the enumerators' @value@ and @label@, even if the @value@ is auto initialized. +When an enumeration inherits enumerators from another enumeration, it copies the enumerators' @value@ and @label@, even if the @value@ is auto-initialized. However, the position of the underlying representation is the order of the enumerator in the new enumeration. \begin{cfa} -enum() E1 { A }; -enum() E2 { B, C }; -enum() E3 { inline E1, inline E2, D }; -\end{cfa} -Here, @A@ has position 0 in @E1@ and @E3@. -@B@ has position 0 in @E2@ and 1 in @E3@. -@C@ has position 1 in @E2@ and position 2 in @E3@. -@D@ has position 3 in @E3@. - -A subtype enumeration can be casted, or implicitly converted into its supertype, with a @safe@ cost. +enum() E1 { B }; $\C{// B}$ +enum() E2 { C, D }; $\C{// C D}$ +enum() E3 { inline E1, inline E2, E }; $\C{// {\color{red}[\(_{E1}\)} B {\color{red}]} {\color{red}[\(_{E2}\)} C D {\color{red}]} E}$ +enum() E4 { A, inline E3, F}; $\C{// A {\color{blue}[\(_{E3}\)} {\color{red}[\(_{E1}\)} B {\color{red}]} {\color{red}[\(_{E2}\)} C D {\color{red}]} E {\color{blue}]} F}$ +\end{cfa} +In the example, @B@ is at position 0 in @E1@ and @E3@, but position 1 in @E4@ as @A@ takes position 0 in @E4@. +@C@ is at position 0 in @E2@, 1 in @E3@, and 2 in @E4@. +@D@ is at position 1 in @E2@, 2 in @E3@, and 3 in @E4@. + +A subtype enumeration can be casted, or implicitly converted into its supertype, with a @safe@ cost, called \newterm{enumeration conversion}. \begin{cfa} enum E2 e2 = C; -posn( e2 ); $\C[1.75in]{// 1}$ -enum E3 e3 = e2; -posn( e2 ); $\C{// 2}$ +posn( e2 ); $\C[1.75in]{// 0}$ +enum E3 e3 = e2; $\C{// Assignment with enumeration conversion E2 to E3}$ +posn( e2 ); $\C{// 1 cost}$ void foo( E3 e ); -foo( e2 ); -posn( (E3)e2 ); $\C{// 2}$ -E3 e31 = B; -posn( e31 ); $\C{// 1}\CRT$ +foo( e2 ); $\C{// Type compatible with enumeration conversion E2 to E3}$ +posn( (E3)e2 ); $\C{// Explicit cast with enumeration conversion E2 to E3}$ +E3 e31 = B; $\C{// No conversion: E3.B}$ +posn( e31 ); $\C{// 0 cost}\CRT$ \end{cfa} The last expression is unambiguous. -While both @E2.B@ and @E3.B@ are valid candidate, @E2.B@ has an associated safe cost and \CFA selects the zero cost candidate @E3.B@. -Hence, as discussed in \VRef{s:OpaqueEnum}, \CFA chooses position as a representation of the \CFA enum. -Therefore, conversion involves both a change of type and possibly position. - -When converting a subtype to a supertype, its position can only be a larger value. -The difference between the position in the subtype and in the supertype is its \newterm{offset}. -\VRef[Figure]{s:OffsetSubtypeSuperType} show the algorithm to determine the offset for an subtype enumerator to its super type. -\PAB{You need to explain the algorithm.} - -\begin{figure} -\begin{cfa} -struct Enumerator; -struct CFAEnum { - vector> members; -}; -pair calculateEnumOffset( CFAEnum dst, Enumerator e ) { - int offset = 0; - for ( auto v: dst.members ) { - if ( v.holds_alternative() ) { - auto m = v.get(); - if ( m == e ) return make_pair( true, 0 ); - offset++; - } else { - auto p = calculateEnumOffset( v, e ); - if ( p.first ) return make_pair( true, offset + p.second ); - offset += p.second; - } - } - return make_pair( false, offset ); -} -\end{cfa} -\caption{Compute Offset from Subtype Enumerator to Super Type} -\label{s:OffsetSubtypeSuperType} -\end{figure} +While both @E2.B@ and @E3.B@ are valid candidates, @E2.B@ has an associated safe cost and @E3.B@ needs no conversion (@zero@ cost). +\CFA selects the lowest cost candidate @E3.B@. For the given function prototypes, the following calls are valid. @@ -302,5 +288,53 @@ -\section{Enumerator Control Structures} +\subsection{Offset Calculation} + +As discussed in \VRef{s:OpaqueEnum}, \CFA chooses position as a representation of a \CFA enumeration variable. +When a cast or implicit conversion moves an enumeration from subtype to supertype, the position can be unchanged or increase. +\CFA determines the position offset with an \newterm{offset calculation} function. + +\begin{figure} +\begin{cfa} +struct Enumerator; +struct CFAEnum { vector> members; string name; }; +inline static bool operator==(CFAEnum& lhs, CFAEnum& rhs) { return lhs.name == rhs.name; } +pair calculateEnumOffset(CFAEnum src, CFAEnum dst) { + int offset = 0; + if ( src == dst ) return make_pair(true, 0); + for ( auto v : dst.members ) { + if ( holds_alternative(v) ) { + offset++; + } else { + auto m = get(v); + if ( m == src ) @return@ make_pair( true, offset ); + auto dist = calculateEnumOffset( src, m ); + if ( dist.first ) { + @return@ make_pair( true, offset + dist.second ); + } else { + offset += dist.second; + } + } + } + @return@ make_pair( false, offset ); +} +\end{cfa} +\caption{Compute Offset from Subtype Enumeration to a Supertype} +\label{s:OffsetSubtypeSuperType} +\end{figure} + +Figure~\ref{s:OffsetSubtypeSuperType} shows an outline of the offset calculation in \CC. +Structure @CFAEnum@ represents the \CFA enumeration with a vector of variants of @CFAEnum@ or @Enumerator@. +The algorithm takes two @CFAEnums@ parameters, @src@ and @dst@, with @src@ being the type of expression the conversion applies to, and @dst@ being the type the expression is cast to. +The algorithm iterates over the members in @dst@ to find @src@. +If a member is an enumerator of @dst@, the positions of all subsequent members are incremented by one. +If the current member is @dst@, the function returns true indicating \emph{found} and the accumulated offset. +Otherwise, the algorithm recurses into the current @CFAEnum@ @m@ to check if its @src@ is convertible to @m@. +If @src@ is convertible to the current member @m@, this means @src@ is a subtype-of-subtype of @dst@. +The offset between @src@ and @dst@ is the sum of the offset of @m@ in @dst@ and the offset of @src@ in @m@. +If @src@ is not a subtype of @m@, the loop continues but with the offset shifted by the size of @m@. +If the loop ends, than @src@ is not convertible to @dst@, and false is returned. + + +\section{Control Structures} Enumerators can be used in multiple contexts. @@ -392,5 +426,5 @@ -\section{Enumeration Dimension} +\section{Dimension} \VRef{s:EnumeratorTyping} introduces the harmonizing problem between an enumeration and secondary information. @@ -409,5 +443,4 @@ \footnotetext{C uses symbol \lstinline{'='} for designator initialization, but \CFA changes it to \lstinline{':'} because of problems with tuple syntax.} This approach is also necessary for a predefined typed enumeration (unchangeable), when additional secondary-information need to be added. - The array subscript operator, namely @?[?]@, is overloaded so that when a \CFA enumerator is used as an array index, it implicitly converts to its position over value to sustain data harmonization. This behaviour can be reverted by explicit overloading: @@ -415,17 +448,17 @@ float ?[?]( float * arr, E2 index ) { return arr[ value( index ) ]; } \end{cfa} -When an enumeration type is being used as an array dimension, \CFA adds the enumeration type to the initializer's context. -As a result, @H2@'s array destinators @A@, @B@ and @C@ are resolved unambiguously to type @E2@. -(@H1@'s destinators are also resolved unambiguously to @E1@ because @E2@ has a @value@ cost.) - - -\section{Enumeration I/O} - -As seen in multiple examples, enumerations can be printed and the default property printed is the enumerator's label, which is similar in other programming languages. +While enumerator labels @A@, @B@ and @C@ are being defined twice in different enumerations, they are unambiguous within the context. +Designators in @H1@ are unambiguous becasue @E2@ has a @value@ cost to @int@, which is more expensive than @safe@ cost from C-Enum @E1@ to @int@. +Designators in @H2@ are resolved as @E2@ because when a \CFA enumeration type is being used as an array dimension, \CFA adds the enumeration type to the initializer's resolution context. + + +\section{I/O} + +As seen in multiple examples, \CFA enumerations can be printed and the default property printed is the enumerator's label, which is similar in other programming languages. However, very few programming languages provide a mechanism to read in enumerator values. Even the @boolean@ type in many languages does not have a mechanism for input using the enumerators @true@ or @false@. \VRef[Figure]{f:EnumerationI/O} show \CFA enumeration input based on the enumerator labels. When the enumerator labels are packed together in the input stream, the input algorithm scans for the longest matching string. -For basic types in \CFA, the rule is that the same constants used to initialize a variable in a program are available to initialize a variable using input, where strings constants can be quoted or unquoted. +For basic types in \CFA, the rule is that the same constants used to initialize a variable in a program are available to initialize a variable using input, where string constants can be quoted or unquoted. \begin{figure} @@ -473,5 +506,4 @@ \label{f:EnumerationI/O} \end{figure} - Index: doc/theses/jiada_liang_MMath/Cenum.tex =================================================================== --- doc/theses/jiada_liang_MMath/Cenum.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) +++ doc/theses/jiada_liang_MMath/Cenum.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -0,0 +1,103 @@ +\chapter{C Enumeration in \texorpdfstring{\CFA}{Cforall}} + +\CFA supports legacy C enumeration using the same syntax for backward compatibility. +A C-style enumeration in \CFA is called a \newterm{C Enum}. +The semantics of the C Enum is mostly consistent with C with some restrictions. +The following sections detail all of my new contributions to enumerations in C. + + +\section{Visibility} +\label{s:CVisibility} + +In C, unscoped enumerators present a \newterm{naming problem} when multiple enumeration types appear in the same scope with duplicate enumerator names. +\begin{cfa} +enum E1 { First, Second, Third, Fourth }; +enum E2 { @Fourth@, @Third@, @Second@, @First@ }; $\C{// same enumerator names}$ +\end{cfa} +There is no mechanism in C to resolve these naming conflicts other than renaming one of the duplicates, which may be impossible if the conflict comes from system include-files. + +The \CFA type-system allows extensive overloading, including enumerators. +Hence, most ambiguities among C enumerators are implicitly resolved by the \CFA type system, possibly without any programmer knowledge of the conflict. +In addition, C Enum qualification is added, exactly like aggregate field-qualification, to disambiguate. +\VRef[Figure]{f:EnumeratorVisibility} shows how resolution, qualification, and casting are used to disambiguate situations for enumerations @E1@ and @E2@. + +\begin{figure} +\begin{cfa} +E1 f() { return Third; } $\C{// overload functions with different return types}$ +E2 f() { return Fourth; } +void g( E1 e ); +void h( E2 e ); +void foo() { $\C{// different resolutions and dealing with ambiguities}$ + E1 e1 = First; E2 e2 = First; $\C{// initialization}$ + e1 = Second; e2 = Second; $\C{// assignment}$ + e1 = f(); e2 = f(); $\C{// function return}$ + g( First ); h( First ); $\C{// function argument}$ + int i = @E1.@First + @E2.@First; $\C{// disambiguate with qualification}$ + int j = @(E1)@First + @(E2)@First; $\C{// disambiguate with cast}$ +} +\end{cfa} +\caption{Enumerator Visibility and Disambiguating} +\label{f:EnumeratorVisibility} +\end{figure} + + +\section{Scoping} + +A C Enum can be scoped, using @'!'@, so the enumerator constants are not projected into the enclosing scope. +\begin{cfa} +enum Week @!@ { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun }; +enum RGB @!@ { Red, Green, Blue }; +\end{cfa} +Now the enumerators \emph{must} be qualified with the associated enumeration type. +\begin{cfa} +Week week = @Week.@Mon; +week = @Week.@Sat; +RGB rgb = @RGB.@Red; +rgb = @RGB.@Blue; +\end{cfa} +% with feature unimplemented +It is possible to toggle back to unscoped using the \CFA @with@ auto-qualification clause/statement (see also \CC \lstinline[language=c++]{using enum} in Section~\ref{s:C++RelatedWork}). +\begin{cfa} +with ( @Week@, @RGB@ ) { $\C{// type names}$ + week = @Sun@; $\C{// no qualification}$ + rgb = @Green@; +} +\end{cfa} +As in Section~\ref{s:CVisibility}, opening multiple scoped enumerations in a @with@ can result in duplicate enumeration names, but \CFA implicit type resolution and explicit qualification/casting handle this localized scenario. + + +\section{Type Safety} +\label{s:TypeSafety} + +As in Section~\ref{s:Usage}, C's implicit bidirectional conversion between enumeration and integral type raises a safety concern. +In \CFA, the conversion is changed to unidirectional: an enumeration can be implicitly converted into an integral type, with an associated @safe@ conversion cost. +However, an integral type cannot be implicitly converted into a C enumeration because the conversion cost is set to @infinity@. +\begin{cfa} +enum Bird { Penguin, Robin, Eagle }; +enum Fish { Shark, Salmon, Whale }; + +int i = Robin; $\C{// allow, implicitly converts to 1}$ +enum Bird @bird = 1;@ $\C{// disallow }$ +enum Bird @bird = Shark;@ $\C{// disallow }$ +\end{cfa} +It is now up to the programmer to insert an explicit cast to force the assignment. +\begin{cfa} +enum Bird bird = @(Bird)@1; +enum Bird bird = @(Bird)@Shark +\end{cfa} + +Note, \CC has the same safe restriction~\cite[C.1.5.7.2]{C++} and provides the same workaround cast. +\begin{description}[parsep=0pt] +\item[Change:] \CC objects of enumeration type can only be assigned values of the same enumeration type. +In C, objects of enumeration type can be assigned values of any integral type. +Example: +\begin{cfa} +enum color { red, blue, green }; +color c = 1; $\C{// valid C, invalid \CC}$ +\end{cfa} +\item[Rationale:] The type-safe nature of \CC. +\item[Effect on original feature:] Deletion of semantically well-defined feature. +\item[Difficulty of converting:] Syntactic transformation. (The type error produced by the assignment can be +automatically corrected by applying an explicit cast.) +\item[How widely used:] Common. +\end{description} Index: doc/theses/jiada_liang_MMath/background.tex =================================================================== --- doc/theses/jiada_liang_MMath/background.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/background.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -1,5 +1,5 @@ \chapter{Background} -This chapter covers background material for C enumerations and \CFA features used in later discussion. +This chapter covers background material for C enumerations and \CFA features used in later discussions. @@ -14,9 +14,9 @@ \begin{enumerate}[leftmargin=*] \item -For @#define@, the programmer has to explicitly manage the constant name and value. -Furthermore, these C preprocessor macro names are outside of the C type-system and can incorrectly change random text in a program. +For @#define@, the programmer must explicitly manage the constant name and value. +Furthermore, these C preprocessor macro names are outside the C type system and can incorrectly change random text in a program. \item The same explicit management is true for the @const@ declaration, and the @const@ variable cannot appear in constant-expression locations, like @case@ labels, array dimensions,\footnote{ -C allows variable-length array-declarations (VLA), so this case does work, but it fails in \CC, which does not support VLAs, unless it is \lstinline{g++}.} immediate oper\-ands of assembler instructions, and occupies storage. +C allows variable-length array declarations (VLA), so this case does work. Still, it fails in \CC, which does not support VLAs, unless it is \lstinline{g++}.} immediate oper\-ands of assembler instructions and occupies storage. \begin{clang} $\$$ nm test.o @@ -28,5 +28,5 @@ -\subsection{C \lstinline{const}} +\subsection{C \texorpdfstring{\lstinline{const}}{const}} \label{s:Cconst} @@ -87,13 +87,13 @@ enum { Size = 20, Max = 10, MaxPlus10 = Max + 10, @Max10Plus1@, Fred = -7 }; \end{clang} -Here, the aliased constants are: 20, 10, 20, 21, and -7. -Direct initialization is by a compile-time expression generating a constant value. -Indirect initialization (without initializer, @Max10Plus1@) is called \newterm{auto-initialization}, where enumerators are assigned values from left to right, starting at zero or the next explicitly initialized constant, incrementing by @1@. +Here, the aliased constants are 20, 10, 20, 21, and -7. +Direct initialization is achieved by a compile-time expression that generates a constant value. +Indirect initialization (without an initializer, @Max10Plus1@) is called \newterm{auto-initialization}, where enumerators are assigned values from left to right, starting at zero or the next explicitly initialized constant, incrementing by @1@. Because multiple independent enumerators can be combined, enumerators with the same values can occur. -The enumerators are rvalues, so assignment is disallowed. +The enumerators are @rvalues@, so the assignment is disallowed. Finally, enumerators are \newterm{unscoped}, \ie enumerators declared inside of an @enum@ are visible (projected) outside into the enclosing scope of the @enum@ type. -For unnamed enumerations, this semantic is required because there is no type name for scoped qualification. - -As noted, this kind of aliasing declaration is not an enumeration, even though it is declared using an @enum@ in C. +This semantic is required for unnamed enumerations because there is no type name for scoped qualification. + +As noted, this aliasing declaration is not an enumeration, even though it is declared using an @enum@ in C. While the semantics is misleading, this enumeration form matches with aggregate types: \begin{cfa} @@ -112,5 +112,5 @@ enum @Week@ { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun }; \end{clang} -and adopts the same semantics with respect to direct and auto intialization. +and adopts the same semantics as direct and auto initialization. For example, @Mon@ to @Wed@ are implicitly assigned with constants @0@--@2@, @Thu@ is explicitly set to constant @10@, and @Fri@ to @Sun@ are implicitly assigned with constants @11@--@13@. As well, initialization may occur in any order. @@ -121,7 +121,7 @@ }; \end{clang} -Note, the comma in the enumerator list can be a terminator or a separator, allowing the list to end with a dangling comma.\footnote{ +Note the comma in the enumerator list can be a terminator or a separator, allowing the list to end with a dangling comma.\footnote{ A terminating comma appears in other C syntax, \eg the initializer list.} -This feature allow enumerator lines to be interchanged without moving a comma. +This feature allows enumerator lines to be interchanged without moving a comma. Named enumerators are also unscoped. @@ -130,5 +130,5 @@ \label{s:CenumImplementation} -In theory, a C enumeration \emph{variable} is an implementation-defined integral type large enough to hold all enumerator values. +Theoretically, a C enumeration \emph{variable} is an implementation-defined integral type large enough to hold all enumerator values. In practice, C defines @int@~\cite[\S~6.4.4.3]{C11} as the underlying type for enumeration variables, restricting initialization to integral constants, which have type @int@ (unless qualified with a size suffix). However, type @int@ is defined as: @@ -136,8 +136,8 @@ A ``plain'' @int@ object has the natural size suggested by the architecture of the execution environment (large enough to contain any value in the range @INT_MIN@ to @INT_MAX@ as defined in the header @@).~\cite[\S~6.2.5(5)]{C11} \end{quote} -However, @int@ means a 4 bytes on both 32/64-bit architectures, which does not seem like the ``natural'' size for a 64-bit architecture. -Whereas, @long int@ means 4 bytes on a 32-bit and 8 bytes on 64-bit architectures, and @long long int@ means 8 bytes on both 32/64-bit architectures, where 64-bit operations are simulated on 32-bit architectures. -\VRef[Figure]{f:gccEnumerationStorageSize} shows both @gcc@ and @clang@ partially ignore this specification and type the integral size of an enumerator based its initialization. -Hence, initialization in the range @INT_MIN@..@INT_MAX@ results in a 4-byte enumerator, and outside this range the enumerator is 8 bytes. +However, @int@ means 4 bytes on both 32/64-bit architectures, which does not seem like the ``natural'' size for a 64-bit architecture. +Whereas @long int@ means 4 bytes on a 32-bit and 8 bytes on 64-bit architectures, and @long long int@ means 8 bytes on both 32/64-bit architectures, where 64-bit operations are simulated on 32-bit architectures. +\VRef[Figure]{f:gccEnumerationStorageSize} shows both @gcc@ and @clang@ partially ignore this specification and type the integral size of an enumerator based on its initialization. +Hence, initialization in the range @INT_MIN@..@INT_MAX@ results in a 4-byte enumerator, and outside this range, the enumerator is 8 bytes. Note that @sizeof( typeof( IMin ) ) != sizeof( E )@, making the size of an enumerator different than is containing enumeration type, which seems inconsistent, \eg @sizeof( typeof( 3 ) ) == sizeof( int )@. @@ -168,5 +168,5 @@ \label{s:Usage} -C proves an implicit \emph{bidirectional} conversion between an enumeration and its integral type, and between two different enumerations. +C proves an implicit \emph{bidirectional} conversion between an enumeration and its integral type and between two different enumerations. \begin{clang} enum Week week = Mon; $\C{// week == 0}$ @@ -178,5 +178,5 @@ @week = Winter;@ $\C{// UNDEFINED! implicit conversion to Week}$ \end{clang} -While converting an enumerator to its underlying type is useful, the implicit conversion from the base or another enumeration type to an enumeration is a common source of error. +While converting an enumerator to its underlying type is sound, the implicit conversion from the base or another enumeration type to an enumeration is a common source of error. Enumerators can appear in @switch@ and looping statements. @@ -194,15 +194,15 @@ \end{cfa} For iterating using arithmetic to make sense, the enumerator values \emph{must} have a consecutive ordering with a fixed step between values. -For example, a previous gap introduced by @Thu = 10@, results in iterating over the values 0--13, where values 3--9 are not @Week@ values. -Note, it is the bidirectional conversion that allows incrementing @day@: @day@ is converted to @int@, integer @1@ is added, and the result is converted back to @Week@ for the assignment to @day@. +For example, a previous gap introduced by @Thu = 10@ results in iterating over the values 0--13, where values 3--9 are not @Week@ values. +Note that the bidirectional conversion allows incrementing @day@: @day@ is converted to @int@, integer @1@ is added, and the result is converted back to @Week@ for the assignment to @day@. For safety, \CC does not support the bidirectional conversion, and hence, an unsafe cast is necessary to increment @day@: @day = (Week)(day + 1)@. -There is a C idiom to automatically compute the number of enumerators in an enumeration. +There is a C idiom that computes the number of enumerators in an enumeration automatically. \begin{cfa} enum E { A, B, C, D, @N@ }; // N == 4 for ( enum E e = A; e < @N@; e += 1 ) ... \end{cfa} -Here, serendipitously the auto-incrementing counts the number of enumerators and puts the total into the last enumerator @N@. -This @N@ is often used as the dimension for an array assocated with the enumeration. +Serendipitously, the auto-incrementing counts the number of enumerators and puts the total into the last enumerator @N@. +This @N@ is often used as the dimension for an array associated with the enumeration. \begin{cfa} E array[@N@]; @@ -226,26 +226,21 @@ \end{cfa} However, the companion idiom results in the \emph{harmonizing} problem because an update to the enumeration @Integral_Type@ often requires a corresponding update to the companion array \snake{Integral_Name}. -The requirement to harmonize is at best indicated by a comment before the enumeration. +The requirement to harmonize is, at best, indicated by a comment before the enumeration. This issue is exacerbated if enumeration and companion array are in different translation units. \bigskip -While C provides a true enumeration, it is restricted, has unsafe semantics, and does not provide useful/advanced enumeration features found in other programming languages. - -\section{\CFA Polymorphism} - -\subsection{Function Overloading} -Function overloading is programming languages feature wherein functions may share the same name, but with different function signatures. In both C++ and \CFA, function names can be overloaded -with different entities as long as they are different in terms of the number and type of parameters. - -\section{\CFA} - -\CFA in \emph{not} an object-oriented programming-language, \ie functions cannot be nested in aggregate types, and hence, there is no \newterm{receiver} notation for calling functions, \eg @obj.method(...)@, where the first argument proceeds the call and becomes an implicit first (\lstinline[language=C++]{this}) parameter. +While C provides a true enumeration, it is restricted, has unsafe semantics, and does not provide helpful/advanced enumeration features in other programming languages. + + +\section{\texorpdfstring{\CFA}{Cforall}} + +\CFA in \emph{not} an object-oriented programming language, \ie functions cannot be nested in aggregate types, and hence, there is no \newterm{receiver} notation for calling functions, \eg @obj.method(...)@, where the first argument proceeds the call and becomes an implicit first (\lstinline[language=C++]{this}) parameter. The following sections provide short descriptions of \CFA features needed further in the thesis. -Other \CFA features are presented in-situ with short explanations, or no explanation because the feature is obvious to C programmers. +Other \CFA features are presented in situ with short or no explanation because the feature is obvious to C programmers. \subsection{Overloading} -Overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources, like include files. +Overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources like included files. \begin{quote} There are only two hard things in Computer Science: cache invalidation and naming things. --- Phil Karlton @@ -253,5 +248,5 @@ Experience from \CC and \CFA developers is that the type system implicitly and correctly disambiguates the majority of overloaded names, \ie it is rare to get an incorrect selection or ambiguity, even among hundreds of overloaded (variables and) functions. In many cases, a programmer has no idea there are name clashes, as they are silently resolved, simplifying the development process. -Depending on the language, ambiguous cases are resolved using some form of qualification or casting. +Depending on the language, ambiguous cases are resolved using some form of qualification and/or casting. @@ -268,11 +263,11 @@ s1 = @?+?@( s1, s2 ); $\C{// direct call}\CRT$ \end{cfa} -The type system examines each call size and selects the best matching overloaded function based on the number and types of the arguments. -If there are intermixed operands, @2 + 3.5@, the type system attempts (safe) conversions changing the arguments to one or more of the parameter type(s). +The type system examines each call size and selects the best matching overloaded function based on the number and types of arguments. +If there are mixed-mode operands, @2 + 3.5@, the type system, like in C/\CC, attempts (safe) conversions, converting the argument type(s) to the parameter type(s). \subsection{Function Overloading} -Both \CFA and \CC allow function names to be overloaded, as long as their prototypes differ in the number and type of parameters and returns. +Both \CFA and \CC allow function names to be overloaded as long as their prototypes differ in the number and type of parameters and returns. \begin{cfa} void f( void ); $\C[1.75in]{// (1): no parameter}$ @@ -282,8 +277,8 @@ \end{cfa} In this case, the name @f@ is overloaded depending on the number and parameter types. -The type system examines each call size and selects the best matching based on the number and types of the arguments. -Here, there is a perfect match for the call, @f( 'A' )@ with the number and parameter type of function (2). - -Ada, Scala, and \CFA type-systems also use the return type in resolving a call, to pinpoint the best overloaded name. +The type system examines each call size and selects the best match based on the number and types of arguments. +Here, the call @f( 'A' )@ is a perfect match for the number and parameter type of function (2). + +Ada, Scala, and \CFA type-systems also use the return type to pinpoint the best-overloaded name in resolving a call. \begin{cfa} int f( void ); $\C[1.75in]{// (4); overloaded on return type}$ @@ -307,5 +302,5 @@ } \end{cfa} -The \CFA type system simply treats overloaded variables as an overloaded function returning a value with no parameters. +The \CFA type system treats overloaded variables as an overloaded function returning a value with no parameters. Hence, no significant effort is required to support this feature. @@ -313,13 +308,13 @@ \subsection{Constructor and Destructor} -While \CFA in not object oriented, it adopts many language features commonly used in object-oriented languages; -these features are independent from object-oriented programming. +While \CFA is not object-oriented, it adopts many language features commonly used in object-oriented languages; +these features are independent of object-oriented programming. All objects in \CFA are initialized by @constructors@ \emph{after} allocation and de-initialized \emph{before} deallocation. -\CC cannot have constructors for basic-types because they have no aggregate type \lstinline[language=C++]{struct/class} in which to insert a constructor definition. +\CC cannot have constructors for basic types because they have no aggregate type \lstinline[language=C++]{struct/class} in which to insert a constructor definition. Like \CC, \CFA has multiple auto-generated constructors for every type. The prototype for the constructor/destructor are @void ?{}( T &, ... )@ and @void ^?{}( T &, ... )@, respectively. -The first parameter is logically, the \lstinline[language=C++]{this} or \lstinline[language=Python]{self} in other object-oriented languages, and implicitly passed. +The first parameter is logically the \lstinline[language=C++]{this} or \lstinline[language=Python]{self} in other object-oriented languages and implicitly passed. \VRef[Figure]{f:CFAConstructorDestructor} shows an example of creating and using a constructor and destructor. Both constructor and destructor can be explicitly called to reuse a variable. @@ -355,5 +350,5 @@ The C constants @0@ and @1@ have special meaning. -@0@ is the null pointer and used in conditional expressions, where @if ( p )@ is rewritten @if ( p != 0 )@; +@0@ is the null pointer and is used in conditional expressions, where @if ( p )@ is rewritten @if ( p != 0 )@; @1@ is an additive identity in unary operators @++@ and @--@. Aware of their significance, \CFA provides a special type @zero_t@ and @one_t@ for custom types. @@ -383,5 +378,5 @@ At the call size, the type parameter @T@ is bounded to @int@ from the argument @42@. -For polymorphic functions to be useful, the @forall@ clause needs \newterm{type assertion}s that restricts the polymorphic types it accepts. +For polymorphic functions to be useful, the @forall@ clause needs \newterm{type assertion}s that restrict the polymorphic types it accepts. \begin{cfa} forall( T @| { void foo( T ); }@ ) void bar( T t ) { @foo( t );@ } @@ -390,14 +385,12 @@ bar( s ); \end{cfa} -The assertion on @T@ restricts the range of types that can be manipulated by @bar@ to only those that have an implementation of @foo@ with the matching signature, allowing @bar@'s call to @foo@ in its body. +The assertion on @T@ restricts the range of types that can be manipulated by @bar@ to only those that implement @foo@ with the matching signature, allowing @bar@'s call to @foo@ in its body. +Unlike templates in \CC, which are macro expansions at the call site, \CFA polymorphic functions are compiled, passing the call-site assertion functions as hidden parameters. + \subsection{Trait} -A @forall@ clause can asserts on multiple types and with multiple asserting functions. A common practice in \CFA is to group -the asserting functions in to a named \newterm{trait}. - -\subsection{Trait} A @forall@ clause can assert many restrictions on multiple types. -A common practice is to refactor the assertions into a named \newterm{trait}. +A common practice is refactoring the assertions into a named \newterm{trait}, similar to other languages like Go and Rust. \begin{cfa} forall(T) trait @Bird@ { @@ -414,5 +407,5 @@ bird_fly( 23, robin ); \end{cfa} -Grouping type assertions into a named trait effectively creates a reusable interface for parametric-polymorphic types. +Grouping type assertions into a named trait effectively creates a reusable interface for parametric polymorphic types. @@ -423,6 +416,6 @@ When multiple best matches exist, the resolution is ambiguous. -The \CFA resolver attempts to identity a best candidate based on: first, the number of parameters and types, and second, when no exact match exists, the fewest implicit conversions and polymorphic variables. -Finding an exact match is not discussed here, because the mechanism is fairly straightforward, even when the search space is large; +The \CFA resolver attempts to identify the best candidate based on: first, the number of parameters and types, and second, when no exact match exists, the fewest implicit conversions and polymorphic variables. +Finding an exact match is not discussed here, because the mechanism is fairly straightforward, even when the search space is ample; only finding a non-exact match is discussed in detail. @@ -432,8 +425,8 @@ Most programming languages perform some implicit conversions among basic types to facilitate mixed-mode arithmetic; -otherwise, the program becomes littered with many explicit casts, which is not match programmer expectation. -C is an aggressive language as it provides conversions among almost all of the basic types, even when the conversion is potentially unsafe or not meaningful, \ie @float@ to @bool@. +otherwise, the program becomes littered with many explicit casts which do not match the programmer's expectations. +C is an aggressive language, providing conversions among almost all basic types, even when the conversion is potentially unsafe or not meaningful, \ie @float@ to @bool@. C defines the resolution pattern as ``usual arithmetic conversion''~\cite[\S~6.3.1.8]{C11}, in which C looks for a \newterm{common type} between operands, and converts one or both operands to the common type. -Loosely defined, a common type is a the smallest type in terms of size of representation that both operands can be converted into without losing their precision, called a \newterm{widening} or \newterm{safe conversion}. +A common type is the smallest type in terms of the size of representation that both operands can be converted into without losing their precision, called a \newterm{widening} or \newterm{safe conversion}. \CFA generalizes ``usual arithmetic conversion'' to \newterm{conversion cost}. @@ -445,16 +438,16 @@ @poly@ is the number of polymorphic function parameters, and \item -@safe@ is sum of the degree of safe (widening) conversions. +@safe@ is the sum of the degree of safe (widening) conversions. \end{enumerate} Sum of degree is a method to quantify C's integer and floating-point rank. -Every pair of widening conversion types is assigned a \newterm{distance}, and distance between the two same type is 0. -For example, the distance from @char@ to @int@ is 2, distance from @int@ to @long@ is 1, and distance from @int@ to @long long int@ is 2. +Every pair of widening conversion types is assigned a \newterm{distance}, and the distance between the two same types is 0. +For example, the distance from @char@ to @int@ is 2, from @int@ to @long@ is 1, and from @int@ to @long long int@ is 2. This distance does not mirror C's rank system. -For example, the rank of @char@ and @signed char@ are the same in C, but the distance from @char@ to @signed char@ is assigned 1. -@safe@ cost is summing all pairs of argument to parameter safe conversion distances. -Among the three costs in Bilson's model, @unsafe@ is the most significant cost and @safe@ is the least significant, with an implication that \CFA always choose a candidate with the lowest @unsafe@, if possible. - -For example, assume the overloaded function @foo@ is called with two @int@ parameter. -The cost for every overloaded @foo@ has been list along: +For example, the @char@ and @signed char@ ranks are the same in C, but the distance from @char@ to @signed char@ is assigned 1. +@safe@ cost is summing all pairs of arguments to parameter safe conversion distances. +Among the three costs in Bilson's model, @unsafe@ is the most significant cost, and @safe@ is the least significant, implying that \CFA always chooses a candidate with the lowest @unsafe@, if possible. + +For example, assume the overloaded function @foo@ is called with two @int@ parameters. +The cost for every overloaded @foo@ has been listed along with the following: \begin{cfa} void foo( char, char ); $\C[2.5in]{// (1) (2, 0, 0)}$ @@ -469,5 +462,5 @@ foo( i, j ); $\C{// convert j to long and call (8)}\CRT$ \end{cfa} -The overloaded instances are ordered from the highest to the lowest cost, and \CFA select the last candidate (8). +The overloaded instances are ordered from the highest to the lowest cost, and \CFA selects the last candidate (8). In the next iteration of \CFA, Schluntz and Aaron~\cite{Moss18} expanded conversion cost to a 7-tuple with 4 additional categories, @(unsafe, poly, safe, sign, vars, specialization, reference)@, with the following interpretations: @@ -476,22 +469,23 @@ \item \textit{Poly} \item \textit{Safe} -\item \textit{Sign} is the number of sign/unsign variable conversion. -\item \textit{Vars} is the number of polymorphics type variable. -\item \textit{Specialization} is negative value of the number of type assertion. +\item \textit{Sign} is the number of sign/unsign variable conversions. +\item \textit{Vars} is the number of polymorphic type variables. +\item \textit{Specialization} is the negative value of the number of type assertions. \item \textit{Reference} is number of reference-to-rvalue conversion. \end{itemize} The extended conversion-cost model looks for candidates that are more specific and less generic. @vars@ disambiguates @forall( T, V ) foo( T, V )@ and @forall( T ) void foo( T, T )@, where the extra type parameter @V@ makes is more generic. -A more generic type means less constraints on its parameter types. +A more generic type means fewer constraints on its parameter types. \CFA favours candidates with more restrictions on polymorphism, so @forall( T ) void foo( T, T )@ has lower cost. @specialization@ is an arbitrary count-down value starting at zero. -For every type assertion in @forall@ clause (no assertions in the above example), \CFA subtracts one from @specialization@. -More type assertions means more constraints on argument types, making the function less generic. +For every type assertion in the @forall@ clause (no assertions in the above example), \CFA subtracts one from @specialization@. +More type assertions mean more constraints on argument types, making the function less generic. \CFA defines two special cost values: @zero@ and @infinite@. -A conversion cost is @zero@ when argument and parameter has an exact match, and a conversion cost is @infinite@ when there is no defined conversion between two types. +A conversion cost is @zero@ when the argument and parameter have an exact match, and a conversion cost is @infinite@ when there is no defined conversion between the two types. For example, the conversion cost from @int@ to a @struct S@ is @infinite@. -In \CFA, the meaning of a C style cast is determined by its @Cast Cost@. For most cast expression resolution, a cast cost is equal to a conversion cost. -Cast cost exists as an independent matrix for conversion that cannot happen implcitly, while being possible with an explicit cast. These conversions are often defined to have -infinite conversion cost and non-infinite cast cost. +In \CFA, the meaning of a C-style cast is determined by its @Cast Cost@. +For most cast-expression resolutions, a cast cost equals a conversion cost. +Cast cost exists as an independent matrix for conversion that cannot happen implicitly while being possible with an explicit cast. +These conversions are often defined as having an infinite conversion cost and a non-infinite cast cost. Index: c/theses/jiada_liang_MMath/benchmarks.tex =================================================================== --- doc/theses/jiada_liang_MMath/benchmarks.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ (revision ) @@ -1,2 +1,0 @@ -\chapter{Benchmarks} -\label{s:Benchmarks} Index: doc/theses/jiada_liang_MMath/conclusion.tex =================================================================== --- doc/theses/jiada_liang_MMath/conclusion.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/conclusion.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -2,24 +2,69 @@ \label{c:conclusion} -The goal of this thesis is to adapt enumeration in \CFA to be aligned with the analogous features in -other languages while being backward-compatiable to C. -The presented features are based off on tools and techniques that widely used in -other languages but they were adapted to better fix \CFA's feature set. Additionally, the thesis provides -an improvement on safety and productivity of C enumeration, including enumerator overloading, -name scoping and type checking. +The goal of this work is to extend the simple and unsafe enumeration type in the C programming language into a complex and safe enumeration type in the \CFA programming language while maintaining backward compatibility with C. +Within this goal, the new \CFA enumeration should align with the analogous enumeration features in other languages to match modern programming expectations. +Hence, the \CFA enumeration features are borrowed from a number of programming languages, but engineered to work and play with \CFA's type system and feature set. -To further explores the potential of enumerated types, this thesis presents a new \CFA enumeration -that is independent on C enumeration. The \CFA enumeration aims to solve the data harmonization problem -and have natural support to \CFA generic type, along with some new features that fit with \CFA's -programming pattern, such as enumerator conctrol structures. +Strong type-checking of enumeration initialization and assignment provides additional safety, ensuring an enumeration only contains its enumerators. +Overloading and scoping of enumerators significantly reduces the naming problem, providing a better software-engineering environment, with fewer name clashes and the ability to disambiguate those that cannot be implicitly resolved. +Typed enumerations solve the data-harmonization problem increasing safety through better software engineering. +Moreover, integrating enumerations with existing control structures provides a consistent upgrade for programmers and a succinct and secure mechanism to enumerate with the new loop-range feature. +Generalization and reuse are supported by incorporating the new enumeration type using the \CFA trait system. +Enumeration traits define the meaning of an enumeration, allowing functions to be written that work on any enumeration, such as the reading and printing an enumeration. +Using advanced duck typing, existing C enumerations can be extended so they work with all of the enumeration features, providing for legacy C code to be moved forward into the modern \CFA programming domain. +Finally, I expanded the \CFA project's test-suite with multiple enumeration features tests with respect to implicit conversions, control structures, inheritance, interaction with the polymorphic types, and the features built on top of enumeration traits. +These tests ensure future \CFA work does not accidentally break the new enumeration system. -The \CFA project's test suite has been expanded to test the enumerations with respect to its -implicit conversions, inheritance, interaction with the polymorphic types, and the features -built on top of enumeration traits. +The conclusion is that the new \CFA enumeration mechanisms achieve the initial goals, providing C programmers with an intuitive enumeration mechanism for handling modern programming requirements. -The enumerated type is an attempt to adapt classic data types into \CFA unique type system. It brings -valuable new feature to \CFA in its own right, but also serve as a motivation to adapt other data types -in \CFA. -% \section{Future Work} +\section{Future Work} +The following are ideas to improve and extend the work in this thesis. +\begin{enumerate} +\item +There are still corner cases being found in the current \CFA enumeration implementation. +Fixing some of these corner cases requires changes to the \CFA resolver or extensions to \CFA. %, like compile-time constant-expression evaluation. +When these changes are made, it should be straightforward to update the \CFA enumeration implementation to work with them. +\item +Currently, some aspects of the enumeration trait system require explicitly including the file @enum.hfa@, which can lead to problems. +It should be possible to have this file included implicitly by updating the \CFA prelude. +\item +There are multiple \CFA features being developed in parallel with enumerations. +Two closely related features are iterator and namespace. +Enumerations may have to be modified to dovetail with these features. +For example, enumerating with range loops does not align with the current iterator design, so some changes will be necessary. +\item +C already provides @const@-style aliasing using the \emph{unnamed} enumerator \see{\VRef{s:TypeName}}, even if the name @enum@ is misleading (@const@ would be better). +Given the existence of this form, it is conceivable to extend it with types other than @int@. +\begin{cfa} +enum { Size = 20u, PI = 3.14159L, Jack = L"John" }; +\end{cfa} +which matches with @const@ aliasing in other programming languages. +Here, the type of the enumerator is the type of the initialization constant, \eg @typeof( 20u )@ for @Size@ implies @unsigned int@. +Auto-initialization is restricted to the case where all constants are @int@, matching with C. +As seen in \VRef{s:EnumeratorTyping}, this feature is just a shorthand for multiple typed-enumeration declarations. +\begin{cfa} +enum( unsigned int ) { Size = 20u }; +enum( long double ) { PI = 3.14159L }; +enum( wchar_t * ) { Jack = L"John" }; +\end{cfa} +\item +Currently enumeration scoping is all or nothing. In some cases, it might be useful to +increase the scoping granularity to individual enumerators. +\begin{cfa} +enum E1 { @!@A, @^@B, C }; +enum E2 @!@ { @!@A, @^@B, C }; +\end{cfa} +Here, @'!'@ means the enumerator is scoped, and @'^'@ means the enumerator is unscoped. +For @E1@, @A@ is scoped; @B@ and @C@ are unscoped. +For @E2@, @A@, and @C@ are scoped; @B@ is unscoped. +Finding a use case is important to justify this extension. +\item +An extension mentioned in \VRef{s:Ada} is using @typedef@ to create an enumerator alias. +\begin{cfa} +enum(int) RGB { @Red@, @Green@, Blue }; +enum(int) Traffic_Light { @Red@, Yellow, @Green@ }; +typedef RGB.Red OtherRed; // alias +\end{cfa} +\end{enumerate} Index: c/theses/jiada_liang_MMath/glossary.tex =================================================================== --- doc/theses/jiada_liang_MMath/glossary.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ (revision ) @@ -1,47 +1,0 @@ -% % Main glossary entries -- definitions of relevant terminology -% \newglossaryentry{computer} -% { -% name=computer, -% description={A programmable machine that receives input data, -% stores and manipulates the data, and provides -% formatted output} -% } - -% % Nomenclature glossary entries -- New definitions, or unusual terminology -% \newglossary*{nomenclature}{Nomenclature} -% \newglossaryentry{dingledorf} -% { -% type=nomenclature, -% name=dingledorf, -% description={A person of supposed average intelligence who makes incredibly brainless misjudgments} -% } - -% % List of Abbreviations (abbreviations type is built in to the glossaries-extra package) -% \newabbreviation{aaaaz}{AAAAZ}{American Association of Amateur Astronomers and Zoologists} - -% % List of Symbols -% \newglossary*{symbols}{List of Symbols} -% \newglossaryentry{rvec} -% { -% name={$\mathbf{v}$}, -% sort={label}, -% type=symbols, -% description={Random vector: a location in n-dimensional Cartesian space, where each dimensional component is determined by a random process} -% } - -% Examples from template above - -\newabbreviation{foo}{FOO}{\Newterm{Fred Orders Oysters}} -\newabbreviation{bar}{BAR}{\Newterm{Boys Are Rushed}} - -\newglossaryentry{git}{ -name=git, -first={\Newterm{git}}, -description={is a system that can count the change in your pocket.} -} - -\newglossaryentry{gulp}{ -name={gulp}, -first={\Newterm{gulp}}, -description={a motion made with the mouth.} -} Index: doc/theses/jiada_liang_MMath/intro.tex =================================================================== --- doc/theses/jiada_liang_MMath/intro.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/intro.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -1,5 +1,5 @@ \chapter{Introduction} -All basic types in a programming language have a set of constants (symbols), and these constants represent computable values, \eg integer types have constants @-1@, @17@, @0xff@ representing whole numbers, floating-point types have constants @5.3@, @2.3E-5@, @0xff.ffp0@ representing real numbers, character types have constants @'a'@, @"abc\n"@, \mbox{\lstinline{u8"}\texttt{\guillemotleft{na\"{i}ve}\guillemotright}\lstinline{"}} representing (human readable) text, \etc. +All basic types in a programming language have a set of constants (symbols), and these constants represent computable values, \eg integer types have constants @-1@, @17@, @0xff@ representing whole numbers, floating-point types have constants @5.3@, @2.3E-5@, @0xff.ffp0@ representing real numbers, character types have constants @'a'@, @"abc\n"@, \mbox{\lstinline{u8"}\texttt{\guillemotleft{na\"{i}ve}\guillemotright}\lstinline{"}} representing (human readable) text, \etc. Constants can be overloaded among types, \eg @0@ is a null pointer for all pointer types, and the value zero for integer and floating-point types. (In \CFA, the constants @0@ and @1@ can be overloaded for any type.) @@ -12,5 +12,5 @@ A constant's symbolic name is dictated by language syntax related to types, \eg @5.@ (double), @5.0f@ (float), @5l@ (long double). In general, the representation of a constant's value is \newterm{opaque}, so the internal representation can be chosen arbitrarily, \eg two's complement, IEEE floating-point. -In theory, there are an infinite set of constant names per type representing an infinite set of values. +In theory, there is an infinite set of constant names per type representing an infinite set of values. It is common in mathematics, engineering, and computer science to alias new constants to existing constants so they have the same value, \eg $\pi$, $\tau$ (2$\pi$), $\phi$ (golden ratio), K(k), M, G, T for powers of 2\footnote{Overloaded with SI powers of 10.} often prefixing bits (b) or bytes (B), \eg Gb, MB, and in general situations, \eg specific times (noon, New Years), cities (Big Apple), flowers (Lily), \etc. @@ -23,5 +23,5 @@ Because an aliased name is a constant, it cannot appear in a mutable context, \eg \mbox{$\pi$ \lstinline{= 42}} is meaningless, and a constant has no address, \ie it is an \newterm{rvalue}\footnote{ The term rvalue defines an expression that can only appear on the right-hand side of an assignment expression.}. -In theory, there are an infinite set of possible aliasing, in practice, the number of aliasing per program is finite and small. +In theory, there is an infinite set of possible aliasing; in practice, the number of aliasing per program is finite and small. Aliased constants can form an (ordered) set, \eg days of a week, months of a year, floors of a building (basement, ground, 1st), colours in a rainbow, \etc. @@ -59,5 +59,5 @@ \end{sloppypar} \item -The alias names are constants, which follows transitively from their binding to other constants. +The alias names are constants, which follow transitively from their binding to other constants. \item Defines a type for generating instants (variables). @@ -140,5 +140,5 @@ \end{cfa} For these reasons, aliasing is sometimes called an enumeration. -However, there is no type to create a type-checked instance or iterator cursor, so there is no ability for enumerating. +However, there is no type to create a type-checked instance or iterator cursor, so there is no ability to enumerate. Hence, there are multiple enumeration aspects not provided by aliasing, justifying a separate enumeration type in a programming language. @@ -158,5 +158,5 @@ the ADT has three variants (constructors), @A@, @B@, @C@, with associated types @Int@, @Double@, and @S@. The constructors create an initialized value of the specific type that is bound to the immutable variables @foo@, @bar@, and @baz@. -Hence, the ADT @Foo@ is like a union containing values of the associated types, and a constructor name is used to intialize and access the value using dynamic pattern-matching. +Hence, the ADT @Foo@ is like a union containing values of the associated types, and a constructor name is used to initialize and access the value using dynamic pattern-matching. \begin{cquote} \setlength{\tabcolsep}{20pt} @@ -194,9 +194,9 @@ baz = Z 5; \end{haskell} -Here, the constructor name gives different meaning to the values in the common \lstinline[language=Haskell]{Int} type, \eg the value @3@ has different interpretations depending on the constructor name in the pattern matching. +Here, the constructor name gives different meanings to the values in the common \lstinline[language=Haskell]{Int} type, \eg the value @3@ has different interpretations depending on the constructor name in the pattern matching. Note, the term \newterm{variant} is often associated with ADTs. However, there are multiple languages with a @variant@ type that is not an ADT \see{Algol68~\cite{Algol68} or \CC \lstinline{variant}}. -Here, the type (and possibly the position for equivalent types) is used to discriminant the specific \emph{variant} within the variant instance. +Here, the type (and possibly the position for equivalent types) is used to discriminate the specific \emph{variant} within the variant instance. For example, \VRef[Figure]{f:C++variant} shows the \CC equivalent of the two Haskell ADT types using variant types. In these languages, the variant cannot be used to simulate an enumeration. @@ -246,6 +246,6 @@ data Week = Mon | Tue | Wed | Thu | Fri | Sat | Sun deriving(Enum, Eq, Show) \end{haskell} -the default type for each constructor is the unit type, and deriving from @Enum@ enforces no other associated types, @Eq@ allows equality comparison, and @Show@ is for printing. -The nullary constructors for the unit types are numbered left-to-right from $0$ to @maxBound@$- 1$, and provides enumerating operations @succ@, @pred@, @enumFrom@, @enumFromTo@. +the default type for each constructor is the unit type, and deriving from @Enum@ enforces no other associated types. The @Eq@ allows equality comparison, and @Show@ is for printing. +The nullary constructors for the unit types are numbered left-to-right from $0$ to @maxBound@$- 1$, and provide enumerating operations @succ@, @pred@, @enumFrom@, @enumFromTo@. \VRef[Figure]{f:HaskellEnumeration} shows enumeration comparison and iterating (enumerating). @@ -296,16 +296,20 @@ However, when extended with advanced features, enumerations become complex for both the type system and the runtime implementation. -The contribution of this work are: +The contributions of this work are: \begin{enumerate} \item -overloading: provides a pattern to overload functions, literal, and variable for polymorphic enumerations. -\item -scoping: adds name space for enumerations. -\item -safety: defines a safe enumeration conversion scheme. -\item -harmonization: allows enumeration to be mapped with data. -\item -inheritance: implements containment inheritance for enumerations. +safety: Define a safe enumeration conversion scheme, both for C and \CFA, and replace ad-hoc C idioms with safer software-engineering approaches. +\item +overloading: Provide a pattern to overload functions, literals, and variables for polymorphic enumerations using the \CFA type system. +\item +scoping: Add a namespace for enumerations and qualified access into the namespace to deal with the naming problem. +\item +generalization: Support all language types for enumerators with associated values providing enumeration constants for any type. +\item +reuse: Implement subset and containment inheritance for enumerations. +\item +control flow: Extend control-flow structures making it safer and easier to enumerate over an enumeration. +\item +I/O: Provide input and output of enumerations based on enumerator names. \end{enumerate} Index: doc/theses/jiada_liang_MMath/offsetAlgorithm.cc =================================================================== --- doc/theses/jiada_liang_MMath/offsetAlgorithm.cc (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) +++ doc/theses/jiada_liang_MMath/offsetAlgorithm.cc (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -0,0 +1,135 @@ +#include +#include +#include +#include + +using namespace std; +struct Enumerator { + string label; + + Enumerator(string label) : label(label) {} +}; + +inline static bool operator==(const Enumerator& lhs, const Enumerator& rhs) { + return lhs.label == rhs.label; +} + +struct CFAEnum { + vector> members; + string name; + + CFAEnum& addMember(CFAEnum inlineMember) { + members.push_back(inlineMember); + return *this; + } + + CFAEnum& addMember(Enumerator enumerator) { + members.push_back(enumerator); + return *this; + } + + CFAEnum(string name) : name(name) {} +}; + +inline static bool operator==(CFAEnum& lhs, CFAEnum& rhs) { + return lhs.name == rhs.name; +} + +// pair calculateEnumOffset(CFAEnum dst, Enumerator e) { +// int offset = 0; +// // std::cout << dst.name << " : " << e.label << std::endl; +// for (auto v : dst.members) { +// // std::cout << " offset: " << offset << std::endl; +// if (holds_alternative(v)) { +// auto m = get(v); +// // std::cout << " Enumerator: " << ":" << m.label << std::endl; +// if (m == e) return make_pair(true, offset); +// offset++; + +// } else { +// auto m = get(v); +// // std::cout << " CFAEnum: " << ":" << m.name << std::endl; +// auto p = calculateEnumOffset(m, e); +// if (p.first) return make_pair(true, offset + p.second); +// offset += p.second; +// } +// } +// // std::cout << "End " << dst.name << " offset " << offset << std::endl; +// return make_pair(false, offset); +// } + +pair calculateEnumOffset(CFAEnum src, CFAEnum dst) { + int offset = 0; + // std::cout << dst.name << " : " << e.label << std::endl; + if (src == dst) return make_pair(true, 0); + for (auto v : dst.members) { + // std::cout << " offset: " << offset << std::endl; + if (holds_alternative(v)) { + offset++; + } else { + auto m = get(v); + // std::cout << " CFAEnum: " << ":" << m.name << std::endl; + if (m == src) return make_pair(true, offset); + auto dist = calculateEnumOffset(src, m); + if (dist.first) { + return make_pair(true, offset + dist.second); + } else { + offset += dist.second; + } + } + } + // std::cout << "End " << dst.name << " offset " << offset << std::endl; + return make_pair(false, offset); +} + +std::ostream& operator<<(std::ostream& os, const CFAEnum& e) { + os << e.name; + return os; +} + +void printEnumOffset(CFAEnum src, CFAEnum dst) { + auto offset = calculateEnumOffset(src, dst); + if (offset.first) { + std::cout << src << " To " << dst << ":" + << " " << calculateEnumOffset(src, dst).second << std::endl; + } else { + std::cout << src << " Cannot convert to " << dst << std::endl; + } + +} + +int main() { + /** + enum() E1 { A }; // A + enum() E2 { B, C }; // B C + enum() E3 { D, inline E1, inline E2, E }; // D {A}_{E1} {B C}_{E2} E + enum() E4 { F, inline E3, G }; // F { D {A}_{E1} {B C}_{E2} E }_{E3} G + * + */ + struct Enumerator A("A"), B("B"), C("C"), D("D"), E("E"), F("F"), G("G"); + struct CFAEnum E1("E1"), E2("E2"), E3("E3"), E4("E4"); + E1.addMember(A); + E2.addMember(B).addMember(C); + E3.addMember(D).addMember(E1).addMember(E2).addMember(E); + E4.addMember(F).addMember(E3).addMember(G); + // std::cout << calculateEnumOffset(E3, B).first << " " + // << calculateEnumOffset(E3, B).second << std::endl; + // std::cout << calculateEnumOffset(E4, B).first << " " + // << calculateEnumOffset(E4, B).second << std::endl; + // std::cout << calculateEnumOffset(E3, E).first << " " + // << calculateEnumOffset(E3, E).second << std::endl; + // std::cout << calculateEnumOffset(E4, E).first << " " + // << calculateEnumOffset(E4, E).second << std::endl; + // std::cout << calculateEnumOffset(E3, G).first << " " + // << calculateEnumOffset(E3, G).second << std::endl; + + printEnumOffset(E1, E3); + printEnumOffset(E1, E4); + printEnumOffset(E2, E3); + printEnumOffset(E2, E4); + printEnumOffset(E3, E4); + printEnumOffset(E4, E4); + printEnumOffset(E4, E1); +} + +// Compile g++ -std=c++17 offsetAlgorithm.cc Index: c/theses/jiada_liang_MMath/performance.tex =================================================================== --- doc/theses/jiada_liang_MMath/performance.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ (revision ) @@ -1,3 +1,0 @@ -\chapter{Performance} - -If there are any performance experiments. Index: doc/theses/jiada_liang_MMath/relatedwork.tex =================================================================== --- doc/theses/jiada_liang_MMath/relatedwork.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/relatedwork.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -18,6 +18,6 @@ \end{comment} -Enumeration-like features exist in many popular programming languages, both past and present, \eg Pascal~\cite{Pascal}, Ada~\cite{Ada}, \Csharp~\cite{Csharp}, OCaml~\cite{OCaml} \CC, Go~\cite{Go}, Haskell~\cite{Haskell}, Java~\cite{Java}, Rust~\cite{Rust}, Swift~\cite{Swift}, Python~\cite{Python}. -Among theses languages, there are a large set of overlapping features, but each language has its own unique extensions and restrictions. +Enumeration-like features exist in many popular programming languages, both past and present, \eg Pascal~\cite{Pascal}, Ada~\cite{Ada}, \Csharp~\cite{Csharp}, OCaml~\cite{OCaml} \CC, Go~\cite{Go}, Haskell~\cite{Haskell} \see{discussion in \VRef{s:AlgebraicDataType}}, Java~\cite{Java}, Rust~\cite{Rust}, Swift~\cite{Swift}, Python~\cite{Python}. +Among these languages, there is a large set of overlapping features, but each language has its own unique extensions and restrictions. @@ -39,5 +39,5 @@ \end{pascal} Object initialization and assignment are restricted to the enumerators of this type. -Enumerators are auto-initialized from left to right, starting at zero, incrementing by 1. +Enumerators are auto-initialized from left to right, starting at zero and incrementing by 1. Enumerators \emph{cannot} be explicitly initialized. Pascal provides a predefined type \lstinline[language=Pascal]{Boolean} defined as: @@ -56,15 +56,15 @@ \end{cquote} -Pascal provides \emph{consecutive} subtyping of an enumeration using subrange type. +Pascal provides \emph{consecutive} subsetting of an enumeration using a subrange type. \begin{pascal} type Week = ( Mon, Tue, Wed, Thu, Fri, Sat, Sun ); - Weekday = @Mon..Fri@; - Weekend = @Sat..Sun@; + Weekday = @Mon..Fri@; { subtype } + Weekend = @Sat..Sun@; var day : Week; - wday : Weekday; - wend : Weekend; + wday : Weekday; + wend : Weekend; \end{pascal} Hence, the ordering of the enumerators is crucial to provide the necessary ranges. -There is bidirectional assignment between the enumeration and its subranges. +There is a bidirectional assignment between the enumeration and its subranges. \begin{pascal} day := Sat; @@ -77,5 +77,5 @@ day := wend; $\C{\{ no check \}}\CRT$ \end{pascal} -There should be a static/dynamic range check to verify values assigned to subtypes. +A static/dynamic range check should be performed to verify the values assigned to subtypes. (Free Pascal does not check and aborts in certain situations, like writing an invalid enumerator.) @@ -85,13 +85,15 @@ \begin{tabular}{@{}ll@{}} \begin{pascal} +day := Mon; if @day@ = wday then Writeln( day ); if @day@ <= Fri then Writeln( 'weekday'); - - +Mon +weekday \end{pascal} & \begin{pascal} + case @day@ of Mon..Fri : @@ -100,4 +102,5 @@ Writeln( 'weekend') end; +weekday \end{pascal} \end{tabular} @@ -107,23 +110,21 @@ \begin{tabular}{@{}ll@{}} \begin{pascal} -day := Mon; -while day <= Sat do begin +while day <= Sun do begin Write( day, ' ' ); day := succ( day ); end; -Mon Tue Wed Thu Fri Sat +Mon Tue Wed Thu Fri Sat Sun \end{pascal} & \begin{pascal} - -for day := Mon to Sat do begin +for day := Mon to Sun do begin Write( day, ' ' ); end; -Mon Tue Wed Thu Fri Sat +Mon Tue Wed Thu Fri Sat Sun \end{pascal} \end{tabular} \end{cquote} -Note, subtype @Weekday@ and @Weekend@ cannot be used to define a case or loop range. +Note that subtypes @Weekday@ and @Weekend@ cannot be used to define a case or loop range. An enumeration type can be used as an array dimension and subscript. @@ -149,5 +150,5 @@ \end{pascal} -The underlying type is an implementation-defined integral-type large enough to hold all enumerated values; it does not have to be the smallest possible type. +The underlying type is an implementation-defined integral type large enough to hold all enumerated values; it does not have to be the smallest possible type. The integral size can be explicitly specified using compiler directive @$PACKENUM@~$N$, where $N$ is the number of bytes, \eg: \begin{pascal} @@ -160,4 +161,5 @@ \section{Ada} +\label{s:Ada} An Ada enumeration type is a set of ordered, unscoped identifiers (enumerators) bound to \emph{unique} \newterm{literals}.\footnote{% @@ -172,6 +174,6 @@ type Traffic_Light is ( @Red@, Yellow, @Green@ ); \end{ada} -Like \CFA, Ada uses a type-resolution algorithm including the left-hand side of assignmente to disambiguate among overloaded identifiers. -\VRef[Figure]{f:AdaEnumeration} shows how ambiguity is handled using a cast, \ie \lstinline[language=ada]{RGB'(Red)}. +Like \CFA, Ada uses a type-resolution algorithm, including the left-hand side of the assignment, to disambiguate among overloaded identifiers. +\VRef[Figure]{f:AdaEnumeration} shows how ambiguity is handled using a cast, \eg \lstinline[language=ada]{RGB'(Red)}. \begin{figure} @@ -194,5 +196,5 @@ \end{ada} \caption{Ada Enumeration Overload Resolution} -\label{f:AdaEnumeration} +\label{f:AdaEnumeration} \end{figure} @@ -201,7 +203,7 @@ \begin{ada} type Week is ( Mon, Tue, Wed, Thu, Fri, Sat, Sun ); -for Week use ( Mon => 0, Tue => 1, Wed => 2, Thu => @10@, Fri => 11, Sat => 14, Sun => 15 ); -\end{ada} -The enumeration operators are the equality and relational operators, @=@, @/=@, @<@, @<=@, @=@, @/=@, @>=@, @>@, where the ordering relationship is given implicitly by the sequence of acsending enumerators. + for Week use ( Mon => 0, Tue => 1, Wed => 2, Thu => @10@, Fri => 11, Sat => 14, Sun => 15 ); +\end{ada} +The enumeration operators are the equality and relational operators, @=@, @/=@, @<@, @<=@, @=@, @/=@, @>=@, @>@, where the ordering relationship is given implicitly by the sequence of ascending enumerators. Ada provides an alias mechanism, \lstinline[language=ada]{renames}, for aliasing types, which is useful to shorten package identifiers. @@ -259,7 +261,7 @@ if @Flag@ then ... -- conditional \end{ada} -Since only types derived from @Boolean@ can be a conditional, @Boolean@ is essentially a builtin type. - -Ada provides \emph{consecutive} subtyping of an enumeration using \lstinline[language=ada]{range}. +Since only types derived from @Boolean@ can be conditional, @Boolean@ is essentially a builtin type. + +Ada provides \emph{consecutive} subsetting of an enumeration using \lstinline[language=ada]{range}. \begin{ada} type Week is ( Mon, Tue, Wed, Thu, Fri, Sat, Sun ); @@ -325,5 +327,5 @@ \label{s:C++RelatedWork} -\CC enumeration is largely backwards compatible with C, so it inherited C's enumerations with some modifications and additions. +\CC enumeration is largely backward compatible with C, so it inherited C's enumerations with some modifications and additions. \CC has aliasing using @const@ declarations, like C \see{\VRef{s:Cconst}}, with type inferencing, plus static/dynamic initialization. @@ -351,36 +353,23 @@ whereas C @const@ declarations without @static@ are marked @R@. -The following \CC non-backwards compatible changes are made \see{\cite[\S~7.2]{ANSI98:c++}}. -\begin{cquote} -Change: \CC objects of enumeration type can only be assigned values of the same enumeration type. -In C, objects of enumeration type can be assigned values of any integral type. \\ -Example: -\begin{c++} -enum color { red, blue, green }; -color c = 1; $\C{// valid C, invalid c++}$ -\end{c++} -\textbf{Rationale}: The type-safe nature of \CC. \\ -\textbf{Effect on original feature}: Deletion of semantically well-defined feature. \\ -\textbf{Difficulty of converting}: Syntactic transformation. (The type error produced by the assignment can be automatically corrected by applying an explicit cast.) \\ -\textbf{How widely used}: Common. -\end{cquote} - -\begin{cquote} -Change: In \CC, the type of an enumerator is its enumeration. -In C, the type of an enumerator is @int@. \\ +The following \CC non-backward compatible change is made~\cite[C.1.5.7.2]{C++}, plus the safe-assignment change shown in~\VRef{s:TypeSafety}. +\begin{description}[parsep=0pt] +\item[Change:] In \CC, the type of an enumerator is its enumeration. +In C, the type of an enumerator is @int@. Example: \begin{c++} enum e { A }; sizeof(A) == sizeof(int) $\C{// in C}$ -sizeof(A) == sizeof(e) $\C{// in c++}$ +sizeof(A) == sizeof(e) $\C{// in \CC}$ /* and sizeof(int) is not necessary equal to sizeof(e) */ \end{c++} -\textbf{Rationale}: In \CC, an enumeration is a distinct type. \\ -\textbf{Effect on original feature}: Change to semantics of well-defined feature. \\ -\textbf{Difficulty of converting}: Semantic transformation. \\ -\textbf{How widely used}: Seldom. The only time this affects existing C code is when the size of an enumerator is taken. +\item[Rationale:] In \CC, an enumeration is a distinct type. +\item[Effect on original feature:] Change to semantics of well-defined feature. +\item[Difficulty of converting:] Semantic transformation. +\item[How widely used:] Seldom. The only time this affects existing C code is when the size of an enumerator is taken. Taking the size of an enumerator is not a common C coding practice. -\end{cquote} +\end{description} Hence, the values in a \CC enumeration can only be its enumerators (without a cast). + While the storage size of an enumerator is up to the compiler, there is still an implicit cast to @int@. \begin{c++} @@ -444,9 +433,11 @@ 0 1 2 @3 4 5 6 7 8 9@ 10 11 12 13 \end{c++} +As a consequence, there is no meaningful enumerating mechanism. + An enumeration type cannot declare an array dimension but an enumerator can be used as a subscript. -There is no mechanism to subtype or inherit from an enumeration. - - -\section{C\raisebox{-0.7ex}{\LARGE$^\sharp$}\xspace} % latex bug: cannot use \relsize{2} so use \LARGE +There is no mechanism to subset or inherit from an enumeration. + + +\section{C\texorpdfstring{\raisebox{-0.7ex}{\LARGE$^\sharp$}\xspace}{Csharp}} % latex bug: cannot use \relsize{2} so use \LARGE \label{s:Csharp} @@ -455,10 +446,10 @@ % https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/language-specification/enums -\Csharp is a dynamically-typed programming-language with a scoped, integral enumeration similar to \CC \lstinline[language=C++]{enum class}. +\Csharp is a dynamically-typed programming language with a scoped, integral enumeration similar to \CC \lstinline[language=C++]{enum class}. \begin{csharp} -enum Week : @long@ { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun@,@ } // terminating comma +enum Week : @long@ { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun } enum RGB { Red, Green, Blue } \end{csharp} -The default underlying integral type is @int@ (no @char@), with auto-incrementing, implicit/explicit initialization, and terminating comma. +The default underlying integral type is @int@, with auto-incrementing and implicit/explicit initialization. A method cannot be defined in an enumeration type (extension methods are possible). There is an explicit bidirectional conversion between an enumeration and its integral type, and an implicit conversion to the enumerator label in display contexts. @@ -471,9 +462,20 @@ Console.WriteLine( Week.Fri ); $\C{// print label Fri}$ \end{csharp} -The majority of the integral operators (relational and arithmetic) work with enumerations, except @*@ and @/@. +% The majority of the integral operators (relational and arithmetic) work with enumerations, except @*@ and @/@. +% Relational and arithmetic operators are defined in terms of its numeric value only. +% Therefore, enumerators are not ordered and not enumerable like \CC. +Like \CC, \Csharp defines enumeration relational and arithmetic operators in terms of value. +Enumerators have no defined positional meaning. \begin{csharp} -day = day++ - 5; $\C{// unsafe}$ +day = day++ - 5; $\C{// value manipulation}$ day = day & day; \end{csharp} +\begin{csharp} +for ( Week d = Mon; d <= Sun; @d += 1@ ) { + Console.Write( d + " " ); +} +Mon Tue Wed @3 4 5 6 7 8 9@ Thu Fri Sat Sun +\end{csharp} +As a consequence, there is no direct meaningful enumerating mechanism. An enumeration can be used in the @if@ and @switch@ statements. @@ -502,12 +504,6 @@ \end{tabular} \end{cquote} -However, there is no mechanism to iterate through an enumeration without an unsafe cast to increment and positions versus values is not handled. -\begin{csharp} -for ( Week d = Mon; d <= Sun; @d += 1@ ) { - Console.Write( d + " " ); -} -Mon Tue Wed @3 4 5 6 7 8 9@ Thu Fri Sat Sun -\end{csharp} -The @Enum.GetValues@ pseudo-method retrieves an array of the enumeration constants for looping over an enumeration type or variable (expensive operation). + +To indirectly enumerate, \Csharp's Enum library has @Enum.GetValues@, a pseudo-method that retrieves an array of the enumeration constants for looping over an enumeration type or variable (expensive operation). \begin{csharp} foreach ( Week d in @Enum.GetValues@( typeof(Week) ) ) { @@ -516,8 +512,8 @@ Mon 0, Tue 1, Wed 2, Thu 10, Fri 11, Sat 12, Sun 13, \end{csharp} -Hence, enumerating is not supplied directly by the enumeration, but indirectly through another enumerable type, array. +Hence, enumerating is not supplied directly by the enumeration, but indirectly through the enumerable array type. An enumeration type cannot declare an array dimension but an enumerator can be used as a subscript. -There is no mechanism to subtype or inherit from an enumeration. +There is no mechanism to subset or inherit from an enumeration. The @Flags@ attribute creates a bit-flags enumeration, making bitwise operators @&@, @|@, @~@ (complement), @^@ (xor) sensible. @@ -533,8 +529,8 @@ -\section{Golang} -\label{s:Golang} - -Golang has a no enumeration. +\section{Go} +\label{s:Go} + +Go has a no enumeration. It has @const@ aliasing declarations, similar to \CC \see{\VRef{s:C++RelatedWork}}, for basic types with type inferencing and static initialization (constant expression). \begin{Go} @@ -545,7 +541,7 @@ const V = 3.1; const W = 3.1; \end{Go} -Since these declarations are unmutable variables, they are unscoped and Golang has no overloading. - -Golang provides an enumeration-like feature to group together @const@ declaration into a block and introduces a form of auto-initialization. +Since these declarations are immutable variables, they are unscoped and Go has no overloading. + +Go provides an enumeration-like feature to group together @const@ declaration into a block and introduces a form of auto-initialization. \begin{Go} const ( R = 0; G; B ) $\C{// implicit initialization: 0 0 0}$ @@ -574,13 +570,13 @@ \begin{Go} const ( Mon = iota; Tue; Wed; // 0, 1, 2 - @Thu = 10@; Fri; Sat; Sun = itoa ) // 10, 10, 10, 6 + @Thu = 10@; Fri; Sat; @Sun = itoa@ ) $\C{// 10, 10, 10, {\color{red}6}}$ \end{Go} -Auto-initialization from \lstinline[language=Go]{iota} is restarted and \lstinline[language=Go]{iota} reinitialized with an expression containing as most \emph{one} \lstinline[language=Go]{iota}. +Auto-initialization from \lstinline[language=Go]{iota} is restarted and \lstinline[language=Go]{iota} reinitialized with an expression containing at most \emph{one} \lstinline[language=Go]{iota}. \begin{Go} const ( V1 = iota; V2; @V3 = 7;@ V4 = @iota@ + 1; V5 ) // 0 1 7 4 5 const ( Mon = iota; Tue; Wed; // 0, 1, 2 - @Thu = 10;@ Fri = @iota - Wed + Thu - 1@; Sat; Sun ) // 10, 11, 12, 13 + @Thu = 10;@ Fri = @iota@ - Wed + Thu - 1; Sat; Sun ) // 10, 11, 12, 13 \end{Go} -Here, @V4@ and @Fri@ restart auto-incrementing from \lstinline[language=Go]{iota} and reset \lstinline[language=Go]{iota} to 4 and 11, respectively, because of the intialization expressions containing \lstinline[language=Go]{iota}. +Here, @V4@ and @Fri@ restart auto-incrementing from \lstinline[language=Go]{iota} and reset \lstinline[language=Go]{iota} to 4 and 11, respectively, because of the initialization expressions containing \lstinline[language=Go]{iota}. Note, because \lstinline[language=Go]{iota} is incremented for an explicitly initialized identifier or @_@, at @Fri@ \lstinline[language=Go]{iota} is 4 requiring the minus one to compute the value for @Fri@. @@ -625,13 +621,11 @@ A basic Java enumeration is an opaque enumeration, where the enumerators are constants. \begin{Java} -enum Week { - Mon, Tue, Wed, Thu, Fri, Sat, Sun; -} +enum Week { Mon, Tue, Wed, Thu, Fri, Sat, Sun; } Week day = Week.Sat; \end{Java} -The enumerators members are scoped and cannot be made \lstinline[language=java]{public}, hence require qualification. +The enumerator's members are scoped and cannot be made \lstinline[language=java]{public}, hence requiring qualification. The value of an enumeration instance is restricted to its enumerators. -The position (ordinal) and label are accessible but there is no value. +The position (ordinal) and label (name) are accessible but there is no value property. \begin{Java} System.out.println( day.!ordinal()! + " " + !day! + " " + day.!name()! ); @@ -639,5 +633,5 @@ \end{Java} Since @day@ has no value, it prints its label (name). -The member @valueOf@ is the inverse of @name@ converting a string to enumerator. +The member @valueOf@ is the inverse of @name@ converting a string to an enumerator. \begin{Java} day = Week.valueOf( "Wed" ); @@ -693,5 +687,5 @@ Notice enumerators in the @switch@ statement do not require qualification. -There are no arithemtic operations on enumerations, so there is no arithmetic way to iterate through an enumeration without making the implementation type \lstinline[language=Java]{public}. +There are no arithmetic operations on enumerations, so there is no arithmetic way to iterate through an enumeration without making the implementation type \lstinline[language=Java]{public}. Like \Csharp, looping over an enumeration is done using method @values@, which returns an array of enumerator values (expensive operation). \begin{Java} @@ -782,5 +776,5 @@ #[repr(u8)] enum ADT { - I(isize) @= 5@, // ??? + I(isize) @= 5@, F(f64) @= 10@, S(S) @= 0@, @@ -791,8 +785,8 @@ Through this integral tag, it is possible to enumerate, and when all tags represent the unit type, it behaves like \CC \lstinline[language=C++]{enum class}. When tags represent non-unit types, Rust largely precludes accessing the tag because the semantics become meaningless. -Hence, the two mechanisms are largely disjoint, and ony the enumeration component is discussed. - -In detail, the @enum@ type has an implicit integer tag (discriminant), with a unique value for each variant type. -Direct initialization is by a compile-time expression generating a constant value. +Hence, the two mechanisms are largely disjoint, and only the enumeration component is discussed. + +In detail, the @enum@ type has an implicit integer tag (discriminant) with a unique value for each variant type. +Direct initialization is achieved by a compile-time expression that generates a constant value. Indirect initialization (without initialization, @Fri@/@Sun@) is auto-initialized: from left to right, starting at zero or the next explicitly initialized constant, incrementing by @1@. There is an explicit cast from the tag to integer. @@ -829,5 +823,5 @@ \end{c++} An enumeration type cannot declare an array dimension nor as a subscript. -There is no mechanism to subtype or inherit from an enumeration. +There is no mechanism to subset or inherit from an enumeration. @@ -878,11 +872,9 @@ \end{tabular} \end{cquote} -(Note, after an @adt@'s type is know, the enumerator is inferred without qualification, \eg @.I(3)@.) +Note, after an @adt@'s type is know, the enumerator is inferred without qualification, \eg @.I(3)@. An enumeration is created when \emph{all} the enumerators are unit-type, which is like a scoped, opaque enumeration. \begin{swift} -enum Week { - case Mon, Tue, Wed, Thu, Fri, Sat, Sun // unit-type -}; +enum Week { case Mon, Tue, Wed, Thu, Fri, Sat, Sun }; // unit-type var week : Week = @Week.Mon@; \end{swift} @@ -911,8 +903,8 @@ An enumeration can have methods. \begin{swift} -enum Week: Comparable { +enum Week: @Comparable@ { case Mon, Tue, Wed, Thu, Fri, Sat, Sun // unit-type - func @isWeekday() -> Bool@ { return self <= .Fri } // method - func @isWeekend() -> Bool@ { return .Sat <= self } // method + func @isWeekday() -> Bool@ { return self <= .Fri } // methods + func @isWeekend() -> Bool@ { return .Sat <= self } }; \end{swift} @@ -938,5 +930,4 @@ \end{tabular} \end{cquote} - Enumerating is accomplished by inheriting from @CaseIterable@ without any associated values. \begin{swift} @@ -944,18 +935,13 @@ case Mon, Tue, Wed, Thu, Fri, Sat, Sun // unit-type }; -var weeki : Week = Week.Mon; -if weeki <= .Fri { - print( "weekday" ); -} for day in Week@.allCases@ { print( day, terminator:" " ) } -weekday Mon Tue Wed Thu Fri Sat Sun \end{swift} The @enum.allCases@ property returns a collection of all the cases for looping over an enumeration type or variable (expensive operation). -A typed enumeration is accomplished by inheriting from any Swift type, and accessing the underlying enumerator value is done with attribute @rawValue@. -Type @Int@ has auto-incrementing from previous enumerator; +A typed enumeration is accomplished by inheriting from any Swift type, and accessing the underlying enumerator value is done with the attribute @rawValue@. +Type @Int@ has auto-incrementing from the previous enumerator; type @String@ has auto-incrementing of the enumerator label. \begin{cquote} @@ -986,5 +972,5 @@ \end{cquote} -There is a bidirectional conversion from typed enumerator to @rawValue@ and vise versa. +There is a bidirectional conversion from typed enumerator to @rawValue@ and vice versa. \begin{swift} var weekInt : WeekInt = WeekInt.Mon; @@ -1002,11 +988,11 @@ Python is a dynamically-typed reflexive programming language with multiple incompatible versions. -The generality of the language makes it is possible to extend existing or build new language features. -As a result, discussing Python enumerations is a moving target, because if a features does not exist, it can often be created with varying levels of complexity within the language. +The generality of the language makes it possible to extend existing or build new language features. +As a result, discussing Python enumerations is a moving target, because if a feature does not exist, it can often be created with varying levels of complexity within the language. Therefore, the following discussion is (mostly) restricted to the core enumeration features in Python 3.13. A Python enumeration is not a basic type; it is a @class@ inheriting from the @Enum@ class. -The @Enum@ class presents a set of scoped enumerators, where each enumerator is a pair object with a \emph{constant} string name and arbitrary value. +The @Enum@ class presents a set of scoped enumerators, where each enumerator is a pair object with a \emph{constant} string name and an arbitrary value. Hence, an enumeration instance is a fixed type (enumeration pair), and its value is the type of one of the enumerator pairs. @@ -1015,10 +1001,10 @@ class Week(!Enum!): Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 7 \end{python} -and/or explicitly auto initialized, \eg: +and/or explicitly auto-initialized, \eg: \begin{python} class Week(Enum): Mon = 1; Tue = 2; Wed = 3; Thu = 10; Fri = !auto()!; Sat = 4; Sun = !auto()! Mon : 1 Tue : 2 Wed : 3 Thu : 10 Fri : !11! Sat : 4 Sun : !12! \end{python} -where @auto@ increments by 1 from the previous @auto@ value \see{Golang \lstinline[language=Go]{iota}, \VRef{s:Golang}}. +where @auto@ increments by 1 from the previous @auto@ value \see{Go \lstinline[language=Go]{iota}, \VRef{s:Go}}. @auto@ is controlled by member @_generate_next_value_()@, which can be overridden: \begin{python} @@ -1028,5 +1014,5 @@ \end{python} -There is no direct concept of restricting the enumerators in an enumeration \emph{instance} because the dynamic typing changes the type. +There is no direct concept of restricting the enumerators in an enumeration \emph{instance} because dynamic typing changes the type. \begin{python} class RGB(Enum): Red = 1; Green = 2; Blue = 3 @@ -1086,7 +1072,7 @@ class Week(!OrderedEnum!): Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 7 - def !isWeekday(self)!: # method + def !isWeekday(self)!: # methods return Week(self.value) !<=! Week.Fri - def !isWeekend(self)!: # method + def !isWeekend(self)!: return Week.Sat !<=! Week(self.value) \end{python} @@ -1137,5 +1123,5 @@ class WeekEnd(WeekE): Sat = 6; Sun = 7 \end{python} -Here, type @WeekE@ is an abstract type because the dynamic typing never uses it. +Here, type @WeekE@ is an abstract type because dynamic typing never uses it. \begin{cquote} \setlength{\tabcolsep}{25pt} @@ -1165,5 +1151,5 @@ @Flag@ is the same as @IntFlag@ but cannot be combined with, nor compared against, any other @Flag@ enumeration, nor @int@. Auto increment for @IntFlag@ and @Flag@ is by powers of 2. -Enumerators that are a combinations of single bit enumerators are aliases, and hence, invisible. +Enumerators that are combinations of single-bit enumerators are aliases and, hence, invisible. The following is an example for @Flag@. \begin{python} @@ -1248,5 +1234,5 @@ \end{cquote} (Note, after an @adtv@'s type is know, the enumerator is inferred without qualification, \eg @I(3)@.) -The type names are independent from the type value, and mapped to an opaque, ascending, integral tag, starting from 0, supporting relational operators @<@, @<=@, @>@, and @>=@. +The type names are independent of the type value and mapped to an opaque, ascending, integral tag, starting from 0, supporting relational operators @<@, @<=@, @>@, and @>=@. \begin{cquote} \setlength{\tabcolsep}{10pt} @@ -1288,7 +1274,10 @@ As seen, a type tag can be used in the @if@ and \lstinline[language=ocaml]{match} statements, where \lstinline[language=ocaml]{match} must be exhaustive or have a default case. -Enumerating is accomplished by deriving from @enumerate@. - -Enumeration subtyping is allowed but inheritance is restricted to classes not types. +While OCaml enumerators have an ordering following the definition order, they are not enumerable. +To iterate over all enumerators, an OCaml type needs to derive from the @enumerate@ preprocessor, which appends a list of all enumerators to the program abstract syntax tree (AST). +However, the list of values may not persist in the defined ordering. +As a consequence, there is no meaningful enumerating mechanism. + +Enumeration subsetting is allowed but inheritance is restricted to classes not types. \begin{ocaml} type weekday = Mon | Tue | Wed | Thu | Fri @@ -1518,7 +1507,6 @@ \section{Comparison} -\VRef[Table]{t:FeatureLanguageComparison} shows a comparison of enumeration features and programming languages. -The features are high level and may not capture nuances within a particular language -The @const@ feature is simple macros substitution and not a typed enumeration. +\VRef[Table]{t:FeatureLanguageComparison} shows a comparison of enumeration features and programming languages with the explaination of categories below. +The features are high-level and may not capture nuances within a particular language. \begin{table} @@ -1529,36 +1517,50 @@ \newcommand{\CM}{\checkmark} \begin{tabular}{r|c|c|c|c|c|c|c|c|c|c|c|c|c} - &Pascal & Ada &\Csharp& OCaml & Java &Modula-3&Golang& Rust & Swift & Python& C & \CC & \CFA \\ + &Pascal & Ada &\Csharp & OCaml & Java &Golang & Rust & Swift & Python& C & \CC & \CFA \\ \hline -@const@ & \CM & & & & & & \CM & & & & & \CM & \\ +enum &Dialect& \CM & \CM & ADT & \CM & @const@ &ADT/\CM &ADT/\CM & \CM &\CM &\CM &\CM\\ \hline \hline -opaque & & & & & & & & & & & & & \CM \\ +opaque & \CM & & & \CM & \CM & & \CM & \CM & & & & \CM \\ \hline -typed & & & & & & & & & & & @int@ & integral & @T@ \\ +typed & Int & Int & Integral & H & U & H & U/H & U/H & H & Int & Integral& U \\ \hline -safe & & & & & & & & & & & & \CM & \CM \\ +safety & \CM & \CM & & \CM & \CM & & \CM & \CM & & & \CM & \CM \\ \hline -ordered & & & & & & & & & & & \CM & \CM & \CM \\ +posn ordered & Implied & Implied & & \CM & & & & & & & & \CM \\ \hline -dup. values & & & & & & & & & & alias & \CM & \CM & \CM \\ +unique values & \CM & \CM & & & & & & \CM & & & & \\ \hline -setable & & & & & & & & & & & \CM & \CM & \CM \\ +auto-init & \CM & all or none & \CM & & & \CM & \CM & \CM & \CM & \CM & \CM & \CM \\ \hline -auto-init & & & & & & & & & & & \CM & \CM & \CM \\ +(Un)Scoped & U & U & S & S & S & U & S & S & S & U & U/S & U/S \\ \hline -(Un)Scoped & & & & & & & & & & & U & U/S & U/S \\ +overload & & \CM & & & & & & & & & & \CM \\ \hline -overload & & \CM & & & & & & & & & & \CM & \CM \\ +loop & \CM & \CM & & & & & & & \CM & & & \CM \\ \hline -switch & & & & & & & & & & & \CM & \CM & \CM \\ +arr. dim. & \CM & \CM & & & & & & & & & & \CM \\ \hline -loop & & & & & & & & & & & & & \CM \\ +subset & \CM & \CM & & \CM & & & & & & & & \CM \\ \hline -array/subscript & & & & & & & & & & & \CM & & \CM \\ -\hline -subtype & & & & & & & & & & & & & \CM \\ -\hline -inheritance & & & & & & & & & & & & & \CM \\ +superset & & & & & & & & & & & & \CM \\ \end{tabular} \end{table} + +\begin{enumerate} +\item opaque: an enumerator cannot be used as its underlying representation or implemented in terms of an ADT. +\item typed: H $\Rightarrow$ heterogeneous, \ie enumerator values may be different types. \\ +U $\Rightarrow$ homogenous, \ie enumerator values have the same type. +\item safety: An enumeration variable can only hold a value from its defined enumerators. +\item posn ordered: enumerators have defined ordering based on enumerator declaration order. +Position ordered is implied if the enumerator values must be strictly increasingly. +\item unique value: enumerators must have a unique value. +\item auto-init: Values are auto-initializable by language specification, often being "+1" of the predecessor. +\item (Un)Scoped: U $\Rightarrow$ enumerators are projected into the containing scope. +S $\Rightarrow$ enumerators are contained in the enumeration scope and require qualification. +\item overload: An enumerator label can be used without type qualification in a context where multiple enumerations have defined the label. +\item loop: Enumerate without the need to convert an enumeration to another data structure. +\item arr. dim: An enumeration can be used directly as an array dimension, and enumerators can be mapped to an array element (not a conversion to integer type). +\item subset: Name a subset of enumerators as a new type. +\item superset: Create a new enumeration that contains all enumerators from pre-defined enumerations. +\end{enumerate} Index: doc/theses/jiada_liang_MMath/test.adb =================================================================== --- doc/theses/jiada_liang_MMath/test.adb (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test.adb (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -2,6 +2,7 @@ -- with Ada.Standard; use Ada.Standard; procedure test is + type GBR is ( Green, Blue, Red ); type RGB is ( Red, Green, Blue ); - for RGB use ( Red => 10, Green => 20, Blue => 30 ); + for RGB use ( Red => 10, Green => 20, Blue => 21 ); Colour : RGB := Red; @@ -95,4 +96,10 @@ if B then null; end if; + + B := False; + Colour := Green; + + Put_Line ( Boolean'Image( B ) & " " ); + Put_Line ( RGB'Image( RGB'Enum_Val( 10 ) ) & " " ); end test; Index: doc/theses/jiada_liang_MMath/test.cc =================================================================== --- doc/theses/jiada_liang_MMath/test.cc (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test.cc (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -61,5 +61,7 @@ eca[A] = EC::A; - enum Week { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun }; + enum Week { Mon, Tue, Wed, Thu = 10, Fri, Sat = 8, Sun }; + if ( Fri < Sat ) cout << "hmm" << endl; + else cout << "ahh" << std::endl; Week day = Mon; if ( day <= Fri ) cout << "weekday" << endl; Index: doc/theses/jiada_liang_MMath/test.go =================================================================== --- doc/theses/jiada_liang_MMath/test.go (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test.go (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -20,10 +20,10 @@ -const ( R = 0; G = 3; B ) // implicit: 0 0 0 +const ( R = 0; G = 3; B = 3; TT = 3 ) // implicit: 0 3 3 const ( Fred = "Fred"; Mary = "Mary"; Jane = "Jane" ) // Fred Mary Jane const ( H = 0; Jack = "Jack"; J; K = 0; I ) // type change, implicit: 0 Jack Jack const ( C = iota + G; M = iota; Y ) const ( Mon = iota; Tue; Wed; // 0, 1, 2 - Thu = 10; Fri = iota - Wed + Thu - 1; Sat; Sun = iota ) // 10, 11, 12, 13 + Thu = 10; Fri = iota - Wed + Thu - 1; Sat; Sun = 0 ) // 10, 11, 12, 13 const ( O1 = iota + 1; _; O3; _; O5 ) // 1, 3, 5 const ( V1 = iota; V2; V3 = 7; V4 = iota + 1; V5 ) @@ -34,4 +34,5 @@ func main() { + fmt.Println( "Go:") if 3 == R {}; fmt.Println( R, G, B ) @@ -45,8 +46,10 @@ day := Mon; + day = Sun; + switch day { case Mon, Tue, Wed, Thu, Fri: fmt.Println( "weekday" ); - case Sat, Sun: + case Sat: fmt.Println( "weekend" ); } @@ -54,6 +57,6 @@ fmt.Println( i ) } + fmt.Println(B < TT); +} // main - var ar[Sun] int - ar[Mon] = 3 -} // main +// go build test.go Index: doc/theses/jiada_liang_MMath/test.pas =================================================================== --- doc/theses/jiada_liang_MMath/test.pas (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test.pas (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -4,5 +4,7 @@ Weekday = Mon..Fri; Weekend = Sat..Sun; -type Count = ( Zero, One, Two, Ten = 10, Eleven ); +type Count = ( Zero, One, Two, Ten = 10, Eleven=10 ); +type RR = ( A, B, C ); + var day : Week; wday : Weekday; @@ -10,4 +12,16 @@ lunch : array[Week] of Integer; cnt : Count; +// procedure P1(v:Week); +// begin +// Writeln('Week'); +// end; +procedure P1(v:Weekday); +begin + Writeln('Weekday'); +end; +procedure P1(v:RR); +begin + Writeln('RR'); +end; begin day := Sat; @@ -40,4 +54,6 @@ Writeln(); for day := Mon to Sat do + lunch[day] := ord(day) * 10; + for day := Mon to Sun do Write( lunch[day], ' ' ); Writeln(); @@ -45,5 +61,12 @@ Write( ord( cnt ), ' ' ); end; + day := Tue; + P1( day ); Writeln(); + + case (day) of + Mon: writeln('Excellent!' ); + Tue: writeln('Well done' ); + end; end. Index: doc/theses/jiada_liang_MMath/test.py =================================================================== --- doc/theses/jiada_liang_MMath/test.py (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test.py (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -25,5 +25,5 @@ # Mon = 1; Tue = 2; Wed = 3; Thu = 10; Fri = 10; Sat = 16; Sun = 17 class Week(OrderedEnum): - Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 7 + Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; Sat = 6; Sun = 0 def isWeekday(self): return Week(self.value) <= Week.Fri @@ -34,21 +34,21 @@ return cls(date.isoweekday()) -day : Week = Week.Tue; +day : Week = Week.Tue print( "weekday:", day.isWeekday() ) print( "weekend:", day.isWeekend() ) print( "today:", Week.today(date.today())) -print( Week.Thu.value == 4 ); -print( Week.Thu.name == "Thu" ); -print( Week( 4 ) == Week.Thu ); -print( Week["Thu"].value == 4 ); +print( Week.Thu.value == 4 ) +print( Week.Thu.name == "Thu" ) +print( Week( 4 ) == Week.Thu ) +print( Week["Thu"].value == 4 ) if day <= Week.Fri : - print( "weekday" ); + print( "weekday" ) match day: case Week.Mon | Week.Tue | Week.Wed | Week.Thu | Week.Fri: - print( "weekday" ); + print( "weekday" ) case Week.Sat | Week.Sun: - print( "weekend" ); + print( "weekend" ) for day in Week: @@ -80,5 +80,5 @@ print( isinstance(Week.Fri, Week) ) -class WeekE(OrderedEnum): pass; +class WeekE(OrderedEnum): pass class WeekDay(WeekE): Mon = 1; Tue = 2; Wed = 3; Thu = 4; Fri = 5; class WeekEnd(WeekE): Sat = 6; Sun = 7 @@ -121,5 +121,5 @@ Weekend = Sat | Sun print( f"0x{repr(WeekF.Weekday.value)} 0x{repr(WeekF.Weekend.value)}" ) -day : WeekF = WeekF.Mon | WeekF.Tue; +day : WeekF = WeekF.Mon | WeekF.Tue print( type(day) ) for day in WeekF: @@ -164,9 +164,9 @@ match diffval: case Diff.Int: - print( "diffval", diffval.value ); + print( "diffval", diffval.value ) case Diff.Float: - print( "diffval", diffval.value ); + print( "diffval", diffval.value ) case Diff.Str: - print( "diffval", diffval.value ); + print( "diffval", diffval.value ) for i in Diff: print( f"Diff type {type(i)}, {i}, {i.name}, {i.value} : " ) @@ -197,8 +197,12 @@ return G * self.mass / (self.radius * self.radius) def surfaceWeight(self, otherMass): - return otherMass * self.surfaceGravity(); + return otherMass * self.surfaceGravity() + +class Cats(Enum): + pass + earthWeight : float = 100 -earthMass : float = earthWeight / ( Planet.EARTH.surfaceGravity() ); +earthMass : float = earthWeight / ( Planet.EARTH.surfaceGravity() ) p = by_position( Planet, random.randrange(8) ) # select a random orbiting body Index: doc/theses/jiada_liang_MMath/test.swift =================================================================== --- doc/theses/jiada_liang_MMath/test.swift (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test.swift (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -59,5 +59,5 @@ enum WeekInt: Int, CaseIterable { - case Mon, Tue, Wed, Thu = 10, Fri, + case Mon, Tue, Wed, Thu = 10, Fri = 14, Sat = 4, Sun // auto-incrementing }; Index: doc/theses/jiada_liang_MMath/test1.cfa =================================================================== --- doc/theses/jiada_liang_MMath/test1.cfa (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test1.cfa (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -1,4 +1,5 @@ #include // sout #include // ato +#include // integral @@ -9,4 +10,5 @@ enum( Letter ) Greek { Alph = A, Beta = B, Gamma = G, /* more enums */ Zeta = Z }; // alphabet intersection +// integral enum( char ) Currency { Dollar = '$', Cent = '¢', Yen = '¥', Pound = '£', Euro = 'E' }; // iso-latin-1 enum( Currency ) Europe { Euro = Currency.Euro, Pound = Currency.Pound }; @@ -33,9 +35,14 @@ enum() Mode { O_RDONLY, O_WRONLY, O_CREAT, O_TRUNC, O_APPEND }; -Mode iomode = O_RDONLY; -//bool b = iomode == O_RDONLY || iomode < O_APPEND; // disallowed -//int www = iomode; // disallowed +Mode mode = O_RDONLY; +void opaque() { +bool b = mode == O_RDONLY || mode < O_APPEND; // disallowed +//int www = mode; // disallowed +} enum( char * ) Colour { Red = "red", Green = "green", Blue = "blue" }; + +enum E1 { A1, B1, C1 = A1, D1 = B1 }; +enum(float) E2 { A2 = 3.5, B2 = 4.5, C2 = A, D2 = B }; void fred() { @@ -45,17 +52,23 @@ //greek = A; // disallowed - for ( Greek l = Alph; posn(l) <= posn(Gamma); l = succ( l ) ) { + for ( Greek l = Alph; posn(l) < posn(Gamma); l = succ( l ) ) { printf( "%s %c %d\n", label( l ), value( l ), posn( l ) ); } - for ( Currency c = Dollar; posn(c) <= posn(Currency.Euro); c = succ( c ) ) { + for ( Currency c = Dollar; posn(c) < posn(Currency.Euro); c = succ( c ) ) { printf( "%s %c %d\n", label( c ), value( c ), posn( c ) ); } } - -enum( char * ) Names { Fred = "FRED", Mary = "MARY", Jane = "JANE" }; -enum( char * ) Names2 { inline Names, Jack = "JACK", Jill = "JILL" }; -enum( char * ) Names3 { inline Names2, Sue = "SUE", Tom = "TOM" }; - +enum( const char * ) Names { Fred = "FRED", Mary = "MARY", Jane = "JANE" }; +enum( const char * ) Names2 { inline Names, Jack = "JACK", Jill = "JILL" }; +enum( const char * ) Names3 { inline Names2, Sue = "SUE", Tom = "TOM" }; +void bar() { + Names fred = Names.Fred; + (Names2)fred; (Names3)fred; (Names3)Names2.Jack; // cast to super type + Names2 fred2 = fred; Names3 fred3 = fred2; // assign to super type + const char * name = fred; + Names name = Fred; + sout | name | label( name ) | posn( name ) | value( name ); +} void f( Names n ) { sout | "Name" | posn( n ); } void g( Names2 ); @@ -63,9 +76,17 @@ void j( char * ); -enum color { red, blue, green }; -//color c = 0; -//color c = 1; -color c = 2; -int w = red; +enum CColour { Red, Blue, Green }; +CColour c0 = 0; +CColour c1 = 1; +CColour c = 2; +int w = Red; + +void coo() { + enum(int) Color { Red, Blue, Green }; + Colour c = Red; + sout | countof( Colour ) | Countof( c ); +// sout | Countof( Colour ); + sout | countof( c ); +} // enum(int) Week ! { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun }; @@ -79,12 +100,57 @@ // } +void baz() { + enum(int) Count { First, Second, Third/* = First*/, Fourth/* = Second*/ }; + enum CCount { First, Second, Third/* = First*/, Fourth/* = Second*/ }; + Count cnt = Second; + CCount ccnt = Second; + if ( cnt < Third ) sout | "less than Third"; + if ( cnt ) sout | "XXX"; + if ( ccnt ) sout | "YYY"; + enum(float) F {WWW = 0.0}; + F f; + if ( f ) sout | "FFF"; + bool ?!=?( Name n, zero_t ) { sout | "DDD"; return n != Fred; } + Name n = Mary; + if ( n ) sout | "NAME"; + choose( cnt ) { + case First: sout | "First"; + case Second: sout | "Second"; + case Third: sout | "Third"; + case Fourth: sout | "Fourth"; + } +// for (d; Week) { sout | d; } +// for (p; +~=Planet) { sout | p; } + for ( cx; Count ) { sout | cx | nonl; } sout | nl; + for ( cx; +~= Count ) { sout | cx | nonl; } sout | nl; + for ( cx; -~= Count ) { sout | cx | nonl; } sout | nl; + for ( Count cx = lowerBound();; ) { + sout | cx | nonl; + if ( cx == upperBound() ) break; + cx = succ( cx ); + } + sout | nl; +} + int main() { fred(); - Names name = Fred; + Names name = Names.Fred; // f( name ); int jane_pos = posn( Names.Jane ); - char * jane_value = value( Names.Jane ); - char * jane_label = label( Names.Jane ); + const char * jane_value = value( Names.Jane ); + const char * jane_label = label( Names.Jane ); sout | Names.Jane | posn( Names.Jane) | label( Names.Jane ) | value( Names.Jane ); + + bar(); + baz(); + coo(); + + enum Ex { Ax, Bx, Cx, Nx }; + float H1[Nx] = { [Ax] : 3.4, [Bx] : 7.1, [Cx] : 0.01 }; // C +// float H2[Ex] = { [Ax] : 3.4, [Bx] : 7.1, [Cx] : 0.01 }; // CFA + + enum(int) E { A = 3 } e = A; + sout | A | label( A ) | posn( A ) | value( A ); + sout | e | label( e ) | posn( e ) | value( e ); } Index: doc/theses/jiada_liang_MMath/test1.java =================================================================== --- doc/theses/jiada_liang_MMath/test1.java (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/test1.java (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -3,5 +3,5 @@ public class test1 { enum Weekday { - Mon(7), Tue(6), Wed(5), Thu(3), Fri(3), Sat(3), Sun(1); // must appear first + Mon(7), Tue(6), Wed(5), Thu(3), Fri(4), Sat(3), Sun(7); // must appear first private long day; private Weekday( long d ) { day = d; } @@ -27,7 +27,11 @@ } for ( Weekday icday : Weekday.values() ) { // position - System.out.print( icday + " " + icday.ordinal() + " " + icday.day + " " + icday.name() + ", " ); // label + System.out.println( icday + " " + icday.ordinal() + " " + icday.day + " " + icday.name() + ", " ); // label } System.out.println(); + + if (Weekday.Fri == Weekday.Sat) { + System.out.println( "Alias "); + } } } Index: c/theses/jiada_liang_MMath/test2.cc =================================================================== --- doc/theses/jiada_liang_MMath/test2.cc (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ (revision ) @@ -1,8 +1,0 @@ -struct unit {}; -void foo( void ); -unit bar( unit ); -int main() { - unit u; - foo( foo() ); - bar( bar( u ) ); -} Index: c/theses/jiada_liang_MMath/test20.cfa =================================================================== --- doc/theses/jiada_liang_MMath/test20.cfa (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ (revision ) @@ -1,10 +1,0 @@ -int main() { -// enum { X = 3, Y = 3.5 }; -// enum(char *) { Z = "abc" }; - enum { X = 3, Y = 3.5, Z = "abc" }; - - int i = X; - double d = Y; - printf( "%g\n", d ); - const char * str = Z; -} Index: c/theses/jiada_liang_MMath/test3.cfa =================================================================== --- doc/theses/jiada_liang_MMath/test3.cfa (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ (revision ) @@ -1,8 +1,0 @@ -enum Week ! { Mon, Tue, Wed, Thu = 10, Fri, Sat, Sun }; -enum RGB ! { Red, Green, Blue }; -void foo() { - Week week = Week.Mon; - week = Week.Sat; - RGB rgb = RGB.Red; - rgb = RGB.Blue; -} Index: doc/theses/jiada_liang_MMath/trait.tex =================================================================== --- doc/theses/jiada_liang_MMath/trait.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/trait.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -2,31 +2,38 @@ \label{c:trait} -% Despite parametric polymorphism being a pivotal feature of \CFA, for a long time, there was not -% a technique to write functions being polymorphic over enumerated types. -\CC introduced @std::is_enum@ trait on \CC{11} and @concepts@ on \CC{20}; with the combination, users can -write function polymorphic over enumerated type in \CC: -\begin{cfa} +\CC introduced the @std::is_enum@ trait in \CC{11} and concept feature in \CC{20}. +With this combination, it is possible to write a polymorphic function over an enumerated type. +\begin{c++} #include - -template -@concept Enumerable = std::is_enum::value;@ - -template<@Enumerable@ T> -void f(T) {} -\end{cfa} -The @std::is_enum@ and other \CC @traits@ are a compile-time interfaces to query type information. -While named the same as @trait@, it is orthogonal to \CFA trait, as the latter being defined as -a collection of assertion to be satisfied by a polymorphic type. - -\CFA provides @CfaEnum@ and @TypedEnum@ traits to supports polymorphic functions for \CFA enumeration: -\begin{cfa} -forall(T | @CfaEnum(T)@) -void f(T) {} -\end{cfa} - -\section{CfaEnum and TypedEnum} -\CFA defines attribute functions @label()@ and @posn()@ for all \CFA enumerations, -and therefore \CFA enumerations fulfills the type assertions with the combination. -With the observation, we define trait @CfaEnum@: +template @concept Enumerable@ = std::is_enum::value; +template<@Enumerable@ E> E f( E e ) { $\C{// constrainted type}$ + E w = e; $\C{// alloction and copy}$ + cout << e << ' ' << w << endl; $\C{// value}$ + return w; $\C{// copy}$ +} +int main() { + enum E { A = 42, B, C } e = C; + e = f( e ); +} +44 44 +\end{c++} +The @std::is_enum@ and other \CC @traits@ are a compile-time interfaces to query type information. +While named the same as @trait@ in other programming languages, it is orthogonal to the \CFA trait, with the latter being defined as a collection of assertion to be satisfied by a polymorphic type. + +The following sections cover the underlying implementation features I created to generalize and restrict enumerations in the \CFA type-system using the @trait@ mechanism. + + +\section{Traits \texorpdfstring{\lstinline{CfaEnum}{CfaEnum}} and \texorpdfstring{\lstinline{TypedEnum}}{TypedEnum}} + +Traits @CfaEnum@ and @TypedEnum@ define the enumeration attributes: @label@, @posn@, @value@, and @Countof@. +These traits support polymorphic functions for \CFA enumeration, \eg: +\begin{cfa} +forall( E ) | @CfaEnum( E )@ ) +void f( E e ) { + // access enumeration properties for e +} +\end{cfa} + +Trait @CfaEnum@ defines attribute functions @label@ and @posn@ for all \CFA enumerations, and internally \CFA enumerations fulfills this assertion. \begin{cfa} forall( E ) trait CfaEnum { @@ -35,9 +42,7 @@ }; \end{cfa} - -% The trait @TypedEnum@ extends @CfaEnum@ with an additional value() assertion: -Typed enumerations are \CFA enumeration with an additional @value@ attribute. Extending -CfaEnum traits, TypedEnum is a subset of CFAEnum that implements attribute function @value()@, -which includes all typed enumerations. +This trait covers opaque enumerations that do not have an explicit @value@. + +The trait @TypedEnum@ extends @CfaEnum@ with the @value@ assertion for typed enumerations. \begin{cfa} forall( E, V | CfaEnum( E ) ) trait TypedEnum { @@ -45,89 +50,85 @@ }; \end{cfa} -Type parameter V of TypedEnum trait binds to return type of @value()@, which is also the base -type for typed enumerations. CfaEnum and TypedEnum triats constitues a CfaEnum function interfaces, as well a way to define functions -over all CfaEnum enumerations. -\begin{cfa} -// for all type E that implements value() to return type T, where T is a type that convertible to string -forall( E, T | TypedEnum( E, T ) | { ?{}(string &, T ); } ) -string format_enum( E e ) { return label(E) + "(" + string(value(e)) + ")"; } - -// int is convertible to string; implemented in the standard library -enum(int) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF }; - -struct color_code { int R; int G; int B }; -// Implement color_code to string conversion -?{}(string & this, struct color_code p ) { - this = string(p.R) + ',' + string(p.G) + ',' + string(p.B); -} +Here, the associate type-parameter @V@ is the base type of the typed enumeration, and hence, the return type of @value@. +These two traits provide a way to define functions over all \CFA enumerations. + +For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows a generalized enumeration formatter for any enumeration type. +The formatter prints an enumerator name and its value in the form @"label( value )"@. +The trait for @format_enum@ requires a function named @str@ for printing the value (payload) of the enumerator. +Hence, enumeration defines how its value appear and @format_enum@ displays this value within the label name. + +\begin{figure} +\begin{cfa} +forall( @E, V | TypedEnum( E, V )@ | { string str( V ); } ) $\C{// format any enumeration}$ +string format_enum( E e ) { + return label( e ) + '(' + str( value( e ) ) + ')'; $\C{// "label( value )"}$ +} +enum(size_t) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF }; +// string library has conversion function str from size_t to string + +struct color_code { int R, G, B; }; enum(color_code) Rainbow { - Red = {255, 0, 0}, Orange = {255, 127, 0}, Yellow = {255, 255, 0}, Green = {0, 255, 0}, - Blue = {0, 0, 255}, Indigo = {75, 0, 130}, Purple = {148, 0, 211} -}; - -format_enum(RGB.Green); // "Green(65280)" -format_enum(Rainbow.Green); // "Green(0,255,0)" -\end{cfa} - - -% Not only CFA enumerations can be used with CfaEnum trait, other types that satisfy -% CfaEnum assertions are all valid. -Types does not need be defined as \CFA enumerations to work with CfaEnum traits. CfaEnum applies to any type -with @label()@ and @value()@ being properly defined. -Here is an example on how to extend a C enumeration to comply CfaEnum traits: -\begin{cfa} -enum Fruit { Apple, Banana, Cherry }; $\C{// C enum}$ -const char * label( Fruit f ) { - choose( f ) { - case Apple: return "Apple"; - case Banana: return "Banana"; - case Cherry: return "Cherry"; - } -} -unsigned posn( Fruit f ) { return f; } -char value( Fruit f ) { - choose(f) { - case Apple: return 'a'; - case Banana: return 'b'; - case Cherry: return 'c'; - } -} - -format_enum(Cherry); // "Cherry(c)" -\end{cfa} - -\section{Discussion: Static Type Information} -@CfaEnum@ and @TypedEnum@ are approximations to \CFA Enumerations and Typed Enumerations: they are not -assertions on a type being an enumerated type, -but rather types being shared an interfaces with \CFA enumerations. -\CC's @type_traits@ is fundamentally different than \CFA's traits: \CC's @type_traits@ are descriptions -of compile time type information -\footnote{Concepts can check if a \CC class implement a certain method, -but it is to probe a static type information of a class having a such member.} -, while \CFA's trait describe how a type can be used, -which is a closer paradigm to a trait system in languages such as Scala and Rust. -However, Scala and Rust's traits are nominative: -a type explicitly declare a named traits to be of its type; while in \CFA, -type implements all functions declares in a trait to implicitly be of the trait type. - -If to support static type information, \CFA needs new piece of syntax to distinguish static type -query from function calls, for example: -\begin{cfa} -forall(T | { T::is_enum; }); -\end{cfa} -When to call a polymorphic function @foo(T)@ with assertions set @S@ and function call argument @a@, \CFA -determines if there is an overloaded name @a@ that has non-zero conversion cost to all assertions in @S@. -As a consequence, @is_enum@ can be a \CFA directive that immediately trim down the search space of @a@ to -be some enumerated types. In fact, because \CFA stores symbols maps to enumeration in a standalone data structure. -Limiting search space to enumeration improve on \CFA resolution speed. - -While assertion on static type information seems improvement on expressivity, it is a challenge to -extend its capability without a fully functional pre-processsor that evaluate constant expression as \CC -compilers does. The described @is_enum@ manipulate compiler behaviour, which cannot be easily extended to -other usage cases. Therefore, \CFA currently does not support @is_enum@ and utalizes traits as a workaround. + Red = {255, 0, 0}, Orange = {255, 127, 0}, Yellow = {255, 255, 0}, Green = {0, 255, 0}, // ... +}; +string str( color_code cc ) with( cc ) { $\C{// format payload, "ddd,ddd,ddd"}$ + return str( R ) + ',' + str( G ) + ',' + str( B ); $\C{// "R,G,B"}$ +} +int main() { + sout | format_enum( RGB.Green ); $\C{// "Green(65280)"}$ + sout | format_enum( Rainbow.Green ); $\C{// "Green(0,255,0)"}$ +} +\end{cfa} +\caption{Generalized Enumeration Formatter} +\label{f:GeneralizedEnumerationFormatter} +\end{figure} + +Other types may work with traits @CfaEnum@ and @TypedEnum@, by supplying appropriate @label@, @posn@, and @value@ functions. +For example, \VRef[Figure]{f:ExtendCEnumeration} extends a (possibly predefined) C enumeration to work with all the \CFA extensions. + +\begin{figure} +\begin{cfa} +enum Fruit { Apple, Banana, Cherry }; $\C{// C enum}$ +const char * @label@( Fruit f ) { + static const char * labels[] = { "Apple", "Banana", "Cherry" }; + return labels[f]; +} +int @posn@( Fruit f ) { return f; } +int @value@( Fruit f ) { + static const char values[] = { 'a', 'b', 'c' }; + return values[f]; +} +sout | format_enum( Cherry ); $\C{// "Cherry(c)"}$ +\end{cfa} +\caption{Extend C Enumeration to \CFA Enumeration} +\label{f:ExtendCEnumeration} +\end{figure} + + +\section{Discussion: Genericity} + +At the start of this chapter, the \CC concept is introduced to constraint template types, \eg: +\begin{c++} +concept Enumerable = std::is_enum::value; +\end{c++} +Here, @concept@ is referring directly to types with kind @enum@; +other @concept@s can refer to all types with kind @int@ with @long@ or @long long@ qualifiers, \etc. +Hence, the @concept@ is a first level of restriction allowing only the specified kinds of types and rejecting others. +The template expansion is the second level of restriction verifying if the type passing the @concept@ test provides the necessary functionality. +Hence, a @concept@ is querying precise aspects of the programming language set of types. + +Alternatively, languages using traits, like \CFA, Scala, Go, and Rust, are defining a restriction based on a set of operations, variables, or structure fields that must exist to match with usages in a function or aggregate type. +Hence, the \CFA enumeration traits never connected with the specific @enum@ kind. +Instead, anything that can look like the @enum@ kind is considered an enumeration (duck typing). +However, Scala, Go, and Rust traits are nominative: a type explicitly declares a named traits to be of its type, while in \CFA, any type implementing all requirements declared in a trait implicitly satisfy its restrictions. + +One of the key differences between concepts and traits, which is leveraged heavily by \CFA, is the ability to apply new \CFA features to C legacy code. +For example, \VRef[Figure]{f:GeneralizedEnumerationFormatter} shows that pre-existing C enumerations can be upgraded to work and play with new \CFA enumeration facilities. +Another example is adding constructors and destructors to pre-existing C types by simply declaring them for the old C type. +\CC fails at certain levels of legacy extension because many of the new \CC features must appear \emph{within} an aggregate definition due to the object-oriented nature of he type system, where it is impossible to change legacy library types. \section{Bounded and Serial} -A bounded type defines a lower bound and a upper bound. + +A bounded trait defines a lower and upper bound for a type. \begin{cfa} forall( E ) trait Bounded { @@ -135,145 +136,143 @@ E lowerBound(); }; - -\end{cfa} -Both Bounded functions are implement for \CFA enumerations, with @lowerBound()@ returning the first enumerator and @upperBound()@ returning -the last enumerator. -\begin{cfa} -Workday day = lowerBound(); $\C{// Mon}$ -Planet outermost = upperBound(); $\C{// NEPTUNE}$ -\end{cfa} - -The lowerBound() and upperBound() are functions overloaded on return type only, means their type resolution solely depend on the outer context, -including expected type as a function argument, or the left hand size of an assignment expression. -Calling either function without a context results in a type ambiguity, except in the rare case where the type environment has only one -type overloads the functions, including \CFA enumerations, which has Bounded functions automatic defined. -\begin{cfa} -@lowerBound();@ $\C{// ambiguous as both Workday and Planet implement Bounded}$ -sout | @lowerBound()@; -Workday day = first(); $\C{// day provides type Workday}$ -void foo( Planet p ); -foo( last() ); $\C{// argument provides type Planet}$ -\end{cfa} - -@Serial@ is a subset of @Bounded@, with functions maps elements against integers, as well implements a sequential order between members. +\end{cfa} +Both functions are necessary for the implementation of \CFA enumeration, with @lowerBound@ returning the first enumerator and @upperBound@ returning the last enumerator. +\begin{cfa} +enum(int) Week { Mon, Tue, Wed, Thu, Fri, Sat, Sun }; +enum(int) Fruit { Apple, Banana, Cherry }; +Week first_day = lowerBound(); $\C{// Mon}$ +Fruit last_fruit = upperBound(); $\C{// Cherry}$ +\end{cfa} +The @lowerBound@ and @upperBound@ are functions overloaded on return type only, meaning their type resolution depends solely on the call-site context, such as the parameter type for a function argument or the left hand size of an assignment expression. +Calling either function without a context results in a type ambiguity, unless the type environment has only one type overloading the functions. +\begin{cfa} +sout | @lowerBound()@; $\C[2.5in]{// ambiguous as Week and Fruit implement Bounded}$ +void foo( Fruit ); +foo( lowerBound() ); $\C{// parameter provides type Fruit}$ +Week day = upperBound(); $\C{// day provides type Week}\CRT$ +\end{cfa} + +Trait @Serial@ is a subset of @Bounded@, with functions mapping enumerators to integers, and implementing a sequential order between enumerators. \begin{cfa} forall( E | Bounded( E ) ) trait Serial { - unsigned fromInstance( E e ); + int fromInstance( E e ); E fromInt( unsigned int i ); + E pred( E e ); E succ( E e ); - E pred( E e ); - unsigned Countof( E e ); -}; -\end{cfa} - -% A Serail type can project to an unsigned @int@ type, \ie an instance of type T has a corresponding integer value. -Function @fromInstance()@ projects a @Bounded@ member to a number and @fromInt@ is the inverser. Function @succ()@ take an element, returns the "next" -member in sequential order and @pred()@ returns the "last" member. - -A Serial type E may not be having a one-to-one mapping to integer because of bound. An integer that cannot be mapping to a member of E is called the member \newterm{out of bound}. -Calling @succ()@ on @upperBound@ or @pred()@ on @lowerBound()@ results in out of bound. - -\CFA implements Serial interface for CFA enumerations with \newterm{bound check} on @fromInt()@, @succ()@ and @pred()@, and abort the program if the function call results in out of bound. -Unlike a cast, conversion between \CFA enumeration and integer with @Serial@ interface is type safe. -Specifically for @fromInt@, \CFA abort if input i smaller than @fromInstance(lowerBound())@ or greater than @fromInstance(upperBound())@ - -Function @Countof@ takes an object as a parameter and returns the number of elements in the Serial type, which is @fromInstance( upper ) - fromInstance( lower ) + 1@. -@Countof@ does not use its arugment as procedural input; it needs -an argument to anchor its polymorphic type T. - -\CFA has an expression @countof@ (lower case) that returns the number of enumerators defined for enumerations. -\begin{cfa} -enum RGB {Red, Green, Blue}; -countof( RGB ); -countof( Red ); -\end{cfa} -Both expressions from the previous example are converted to constant expression @3@ with no function call at runtime. -@countof@ also works for any type T that defines @Countof@ and @lowerBound@, for which it turns into -a function call @Countof( T )@. The resolution step on expression @countof(e)@ works as the following with priority ordered: + unsigned Countof( E ); +}; +\end{cfa} +Function @fromInstance@ projects a @Bounded@ member to a number and @fromInt@ is the inverse. +Function @pred@ and @succ@ are advancement functions: +@pred@ takes an enumerator and returns the previous enumerator, if there is one, in sequential order, and @succ@ returns the next enumerator. +\begin{cfa} +sout | fromInstance( Wed ) | fromInt( 2 ) | succ( Wed ) | pred( Wed ); +2 Wed Thu Tue +\end{cfa} +Bound checking is provided for @fromInt@, @pred@, and @succ@, and the program is terminated if the lower or upper bound is exceeded, \eg: +\begin{cfa} +fromInt( 100 ); +Cforall Runtime error: call to fromInt has index 100 outside of enumeration range 0-6. +\end{cfa} +Function @fromInstance@ or a position cast using @(int)@ is always safe, \ie within the enumeration range. + +Function @Countof@ is the generic counterpart to the builtin pseudo-function @countof@. +@countof@ only works on enumeration types and instances, so it is locked into the language type system; +as such, @countof( enum-type)@ becomes a compile-time constant. +@Countof@ works on an any type that matches the @Serial@ trait. +Hence, @Countof@ does not use its argument; +only the parameter type is needed to compute the range size. +\begin{cfa} +int Countof( E ) { + E upper = upperBound(); + E lower = lowerBound(); + return fromInstance( upper ) + fromInstance( lower ) + 1; +} +\end{cfa} + +@countof@ also works for any type @E@ that defines @Countof@ and @lowerBound@, becoming a call to @Countof( E )@. +The resolution step on expression @countof( E )@ are: \begin{enumerate} -\item Looks for an enumeration named e, such as @enum e {... }@. -If such an enumeration e exists, \CFA replace @countof(e)@ with constant expression with number of enumerator of e. -\item Looks for a non-enumeration type named e that defines @Countof@ and @lowerBound@, including e being a polymorphic type, such as @forall(e)@. -If type e exists, \CFA replaces it with @Countof(lowerBound())@, where lowerBound() is bounded to type e. -\item Looks for an enumerator e that defined in enumeration E. If such an enumeration e exists, \CFA replace @countof(e)@ with constant expression with number of enumerator of E. -\item Looks for a name e in the context with expression type E. If such name e exists, \CFA replace @countof(e)@ with function call @Countof(e)@. -\item If 1-4 fail, \CFA reports a type error on expression @countof(e)@. +\item Look for an enumeration named @E@, such as @enum E {... }@. +If such an enumeration @E@ exists, replace @countof( E )@ with the number of enumerators. +\item Look for a non-enumeration type named @E@ that defines @Countof@ and @lowerBound@, including @E@ being a polymorphic type, such as @forall( E )@. +If type @E@ exists, replaces it with @Countof(lowerBound())@, where @lowerBound@ is defined for type @E@. +\item Look for an enumerator @A@ defined in enumeration @E@. +If such an enumerator @A@ exists, replace @countof( A )@ with the number of enumerators in @E@. +\item Look for a name @A@ in the lexical context with type @E@. +If such name @A@ exists, replace @countof( A )@ with function call @Countof( E )@. +\item If 1-4 fail, report a type error on expression @countof( E )@. \end{enumerate} -\section{Iterating Over An Enumeration} -An fundamental aspect of an enumerated type is to be able to enumerate over its enumerators. \CFA supports \newterm{for} loops, -\newterm{while} loop, and \newterm{range} loop. This section covers @for@ loops and @range@ loops for -enumeration, but the concept transition to @while@ loop. + +\section{Enumerating} + +The fundamental aspect of an enumeration type is the ability to enumerate over its enumerators. +\CFA supports \newterm{for} loops, \newterm{while} loop, and \newterm{range} loop. This section covers @for@ loops and @range@ loops for enumeration, but the concept transition to @while@ loop. + \subsection{For Loop} -A for loop is constitued by a loop control and a loop body. -A loop control is often a 3-tuple, separated by semicolons: initializers, condition, and an expression. It is a common practice to declare -a variable, often in initializers, that be used in the condition and updated in the expression or loop body. Such variable is called \newterm{index}. - -% With implemented @Bounded@ and @Serial@ interface for \CFA enumeration, a @for@ loop that iterates over \CFA enumeration can be implemented as the following: -A @for@ loop iterates an enumeration can be written with functions from @Bounded@ and @Serial@ interfaces: -\begin{cfa} -enum() Chars { A, B, C, D }; -for( unsigned i = 0; i < countof(E); i++ ) { sout | label(e); } $\C{// (1) A B C D}$ -for( Chars e = lowerBound(); ; e = succ(e) ) { $\C{// (2)}$ - sout |label((Chars)fromInt(i)) |' '; - if (e == upperBound()) break; -} -\end{cfa} - -A caveat in writing loop using finite number as index is that the number can unintentionally be out the range: -\begin{cfa} -for( unsigned i = countof(Chars) - 1; i >= 0; i-- ) {} $\C{// 3}$ -for( Chars e = lowerBound(); e <= upperBound(); e = succ(e) ) {} $\C{// 4}$ -for( Chars e = upperBound(); e >= lowerBound(); e = pred(e) ) {} $\C{// 5}$ -\end{cfa} -Loop (3) is a value underflow: when @i@ reaches to @0@, decrement statement will still execute and cause -the @unsigned int@ value @i@ wraps to @UINT_MAX@, which fails to loop test and the loop cannot terminate. - -In loop (4) and (5), when @e@ is at the @Bound@ (@upperBound@/@lowerBound@) and @succ@/@pred@ will result in @out of bounded@, \CFA -aborts its execution. Therefore, it is necessary to implement the condtional break within the loop body. + +A for-loop consists of loop control and body. +The loop control is often a 3-tuple: initializers, stopping condition, and advancement. +It is a common practice to declare one or more loop-index variables in initializers, checked these variables for stopping iteration, and updated the variables in advancement. +Such a variable is called an \newterm{index} and is available for reading and writing within the loop body. +(Some languages make the index read-only in the loop body.) +This style of iteration can be written for an enumeration using functions from the @Bounded@ and @Serial@ traits: +\begin{cfa} +enum() E { A, B, C, D }; +for ( unsigned int i = 0; i < countof(E); i += 1 ) $\C{// (1)}$ + sout | label( fromInt( i ) ) | nonl; +sout | nl; +for ( E e = lowerBound(); ; e = succ(e) ) { $\C{// (2)}$ + sout | label(e) | nonl; + if (e == upperBound()) break; +} +sout | nl; +A B C D +A B C D +\end{cfa} + +A caveat in writing loop control using @pred@ and @succ@ is unintentionally exceeding the range. +\begin{cfa} +for ( E e = upperBound(); e >= lowerBound(); e = pred( e ) ) {} +for ( E e = lowerBound(); e <= upperBound(); e = succ( e ) ) {} +\end{cfa} +Both of these loops look correct but fail because these is an additional bound check within the advancement \emph{before} the conditional test to stop the loop, resulting in a failure at the endpoints of the iteration. +These loops must be restructured by moving the loop test to the end of the loop (@do-while@), as in loop (2) above, which is safe because an enumeration always at least one enumerator. \subsection{Range Loop} -Instead of specifying condition, \CFA supports @range loops@, for which a user specifies a range of values. -\begin{cfa}[label=lst:range_functions_2] -for ( Chars e; A ~= D ) { sout | label(e); } $\C{// (6)}$ -for ( e; A ~= D ) { sout | label(e); } $\C{// (7)}$ -for ( Chars e; A -~= D ) { sout | label(e); } $\C{// (8) D C B A}$ -for ( e; A -~=D ~ 2 ) { sout | label(e); } $\C{// (9) D B }$ -\end{cfa} -Every range loop above has an index declaration, and a @range@ bounded by \newterm{left bound} @A@ and \newterm{right bound} @D@. -An index declaration can have an optional type declaration, without which \CFA -implicitly declares index variable to be the type of the bounds (@typeof(A)@). -If a range is joined by @~=@ (range up equal) operator, the index variable will be initialized by -the @left bound@, and change incrementally until its position exceeds @right bound@. -On the other hand, if a range is defined with @-~=@ (range down equal) operation, the index variable will -have the value of the @right bound@. It change decrementally until its position is less than the @left bound@. -A range can be suffixed by an positive integal \newterm{step}, joined by @~@. The loop @(9)@ declares a step size of 2 so that -e updates @pred(pred(e))@ in every iteration. - -\CFA manipulates the position of the index variable and breaks the loop if an index update can result in @out of range@. - -\CFA provides a shorthand for range loop over a \CFA enumeration or a @Serial@: -\begin{cfa}[label=lst:range_functions_2] -for ( e; Chars ) { sout | label(e); } $\C{// (10) A B C D}$ -for ( e; E ) { $\C{// forall(E | CfaEnum(E) | Serial(E)) }$ - sout | label(e); -} -\end{cfa} -The shorthand syntax has a type name expression (@Char@ and @E@) as its range. If the range expression does not name -a \CFA enumeration or a @Serial@, \CFA reports a compile time error. When type name as range is a \CFA enumeration, -it turns into a loop that iterates all enumerators of the type. If the type name is a @Serial@, the index variable -will be initialized as the @lowerBound@. The loop control checks the index's position against the position of @upperBound@, -and terminate the loop when the index has a position greater than the @upperBound@. \CFA does not update the index with -@succ@ but manipulate its position directly to avoid @out of bound@. + +Instead of writing the traditional 3-tuple loop control, \CFA supports a \newterm{range loop}. +\begin{cfa} +for ( @E e; A ~= D@ ) { sout | label( e ) | nonl; } sout | nl; +for ( @e; A ~= D@ ) { sout | label( e ) | nonl; } sout | nl; +for ( @E e; A -~= D@ ) { sout | label( e ) | nonl; } sout | nl; +for ( @e; A -~= D ~ 2@ ) { sout | label( e ) | nonl; } sout | nl; +\end{cfa} +Every range loop above has an index declaration and a @range@ bounded by \newterm{left bound} @A@ and \newterm{right bound} @D@. +If the index declaration-type is omitted, the index type is the type of the lower bound (@typeof( A )@). +If a range is joined by @~=@ (range up equal) operator, the index variable is initialized by the left bound and advanced by 1 until it is greater than the right bound. +If a range is joined by @-~=@ (range down equal) operator, the index variable is initialized by the right bound and advanced by -1 until it is less than the left bound. +(Note, functions @pred@ and @succ@ are not used for advancement, so the advancement problem does not occur.) +A range can be suffixed by a positive \newterm{step}, \eg @~ 2@, so advancement is incremented/decremented by step. + +Finally, a shorthand for enumerating over the entire set of enumerators (the most common case) is using the enumeration type for the range. +\begin{cfa} +for ( e; @E@ ) sout | label( e ) | nonl; sout | nl; $\C{// A B C D}$ +for ( e; @-~= E@ ) sout | label( e ) | nonl; sout | nl; $\C{// D C B A}$ +\end{cfa} +For a \CFA enumeration, the loop enumerates over all enumerators of the enumeration. +For a type matching the @Serial@ trait: the index variable is initialized to @lowerBound@ and loop control checks the index's value for greater than the @upperBound@. +If the range type is not a \CFA enumeration or does not match trait @Serial@, it is compile-time error. + \section{Overload Operators} -% Finally, there is an associated trait defining comparison operators among enumerators. -\CFA preemptively overloads comparison operators for \CFA enumeration with @Serial@ and @CfaEnum@. -They defines that two enumerators are equal only if the are the same enumerator, and compartors are -define for order comparison. -\begin{cfa} -forall( E | CfaEnum( E ) | Serial( E ) ) { + +\CFA overloads the comparison operators for \CFA enumeration satisfying traits @Serial@ and @CfaEnum@. +These definitions require the operand types be the same and the appropriate comparison is made using the the positions of the operands. +\begin{cfa} +forall( E | CfaEnum( E ) | Serial( E ) ) @{@ $\C{// distribution block}$ // comparison int ?==?( E l, E r ); $\C{// true if l and r are same enumerators}$ @@ -283,12 +282,13 @@ int ?>?( E l, E r ); $\C{// true if l is an enumerator after r}$ int ?>=?( E l, E r ); $\C{// true if l after or the same as r}$ -} -\end{cfa} - -\CFA implements few arithmetic operators for @CfaEnum@. Unlike update functions in @Serial@, these -operator does not have bound checks, which rely on @upperBound@ and @lowerBound@. These operators directly manipulate -position, the underlying representation of a \CFA enumeration. -\begin{cfa} -forall( E | CfaEnum( E ) | Serial( E ) ) { +@}@ +\end{cfa} +(Note, all the function prototypes are wrapped in a distribution block, where all qualifiers preceding the block are distributed to each declaration with the block, which eliminated tedious repeated qualification. +Distribution blocks can be nested.) + +\CFA implements a few arithmetic operators for @CfaEnum@. +Unlike advancement functions in @Serial@, these operators perform direct arithmetic, so there is no implicit bound checks. +\begin{cfa} +forall( E | CfaEnum( E ) | Serial( E ) ) { $\C{// distribution block}$ // comparison E ++?( E & l ); @@ -303,105 +303,11 @@ \end{cfa} -Lastly, \CFA does not define @zero_t@ for \CFA enumeration. Users can define the boolean false for -\CFA enumerations on their own. Here is an example: -\begin{cfa} -forall(E | CfaEnum(E)) -bool ?!=?(E lhs, zero_t) { - return posn(lhs) != 0; -} -\end{cfa} -which effectively turns the first enumeration as a logical false and true for others. - -% \begin{cfa} -% Count variable_a = First, variable_b = Second, variable_c = Third, variable_d = Fourth; -% p(variable_a); // 0 -% p(variable_b); // 1 -% p(variable_c); // "Third" -% p(variable_d); // 3 -% \end{cfa} - - -% \section{Iteration and Range} - - - -% % It is convenient to iterate over a \CFA enumeration value, \eg: -% \CFA implements \newterm{range loop} for \CFA enumeration using the enumerated traits. The most basic form of @range loop@ is the follows: -% \begin{cfa}[label=lst:range_functions] -% for ( Alphabet alph; Alphabet ) { sout | alph; } -% >>> A B C ... D -% \end{cfa} -% % The @range loops@ iterates through all enumerators in the order defined in the enumeration. -% % @alph@ is the iterating enumeration object, which returns the value of an @Alphabet@ in this context according to the precedence rule. -% Enumerated @range loop@ extends the \CFA grammar as it allows a type name @Alphabet@ - -% \textbullet\ \CFA offers a shorthand for iterating all enumeration constants: -% \begin{cfa}[label=lst:range_functions] -% for ( Alphabet alph ) { sout | alph; } -% >>> A B C ... D -% \end{cfa} - -% The 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. - -% \textbullet\ H is implicit up-to exclusive range [0, H). -% \begin{cfa}[label=lst:range_function_1] -% for ( alph; Alphabet.D ) { sout | alph; } -% >>> A B C -% \end{cfa} - -% \textbullet\ ~= H is implicit up-to inclusive range [0,H]. -% \begin{cfa}[label=lst:range_function_2] -% for ( alph; ~= Alphabet.D ) { sout | alph; } -% >>> A B C D -% \end{cfa} - -% \textbullet\ L ~ H is explicit up-to exclusive range [L,H). -% \begin{cfa}[label=lst:range_function_3] -% for ( alph; Alphabet.B ~ Alphabet.D ) { sout | alph; } -% // for ( Alphabet alph = Alphabet.B; alph < Alphabet.D; alph += 1 ); 1 is one_t -% >>> B C -% \end{cfa} - -% \textbullet\ L ~= H is explicit up-to inclusive range [L,H]. -% \begin{cfa}[label=lst:range_function_4] -% for ( alph; Alphabet.B ~= Alphabet.D ) { sout | alph; } -% >>> B C D -% \end{cfa} - -% \textbullet\ L -~ H is explicit down-to exclusive range [H,L), where L and H are implicitly interchanged to make the range down-to. -% \begin{cfa}[label=lst:range_function_5] -% for ( alph; Alphabet.D -~ Alphabet.B ) { sout | alph; } -% >>> D C -% \end{cfa} - -% \textbullet\ L -~= H is explicit down-to exclusive range [H,L], where L and H are implicitly interchanged to make the range down-to. -% \begin{cfa}[label=lst:range_function_6] -% for ( alph; Alphabet.D -~= Alphabet.B ) { sout | alph; } -% >>> D C B -% \end{cfa} - -% A user can specify the ``step size'' of an iteration. There are two different stepping schemes of enumeration for-loop. -% \begin{cfa}[label=lst:range_function_stepping] -% enum(int) Sequence { A = 10, B = 12, C = 14, D = 16, D = 18 }; -% for ( s; Sequence.A ~= Sequence.D ~ 1 ) { sout | alph; } -% >>> 10 12 14 16 18 -% for ( s; Sequence.A ~= Sequence.D; s+=1 ) { sout | alph; } -% >>> 10 11 12 13 14 15 16 17 18 -% \end{cfa} -% The 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 -% \begin{cfa}[label=lst:range_function_stepping_converted] -% for ( typeof( value(Sequence.A) ) s=value( Sequence.A ); s <= Sequence.D; s+=1 ) { sout | alph; } -% >>> 10 11 12 13 14 15 16 17 18 -% \end{cfa} - -% % \PAB{Explain what each loop does.} - -% It is also possible to iterate over an enumeration's labels, implicitly or explicitly: -% \begin{cfa}[label=lst:range_functions_label_implicit] -% for ( char * alph; Alphabet ) -% \end{cfa} -% This for-loop implicitly iterates every label of the enumeration, because a label is the only valid resolution to @ch@ with type @char *@ in this case. -% If the value can also be resolved as the @char *@, you might iterate the labels explicitly with the array iteration. -% \begin{cfa}[label=lst:range_functions_label_implicit] -% for ( char * ch; labels( Alphabet ) ) -% \end{cfa} +Lastly, \CFA does not define @zero_t@ for \CFA enumeration. +Users can define the boolean @false@ for \CFA enumerations on their own, \eg: +\begin{cfa} +forall( E | CfaEnum( E ) ) +int ?!=?( E lhs, zero_t ) { + return posn( lhs ) != 0; +} +\end{cfa} +which effectively turns the first enumeration to a logical @false@ and @true@ for the others. Index: doc/theses/jiada_liang_MMath/user_define_enum.cfa =================================================================== --- doc/theses/jiada_liang_MMath/user_define_enum.cfa (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) +++ doc/theses/jiada_liang_MMath/user_define_enum.cfa (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -0,0 +1,38 @@ +#include +#include +#include + +forall( E, V | TypedEnum( E, V ) | { string str( V ); } ) // routine to format value}$ +string format_enum( E e ) { + return label( e ) + '(' + str( value( e ) ) + ')'; // "label( value )" +} +enum(size_t) RGB { Red = 0xFF0000, Green = 0x00FF00, Blue = 0x0000FF }; +// string library has conversion from size_t to string + +struct color_code { int R, G, B; }; +enum(color_code) Rainbow { + Red = {255, 0, 0}, Orange = {255, 127, 0}, Yellow = {255, 255, 0}, Green = {0, 255, 0}, // ... +}; +string str( color_code cc ) with( cc ) { + return str( R ) + ',' + str( G ) + ',' + str( B ); // "R,G,B" +} + +enum Fruit { Apple, Banana, Cherry }; // C enum +const char * label( Fruit f ) { + static const char * labels[] = { "Apple", "Banana", "Cherry" }; + return labels[f]; +} +int posn( Fruit f ) { return f; } +int value( Fruit f ) { + static const char values[] = { 'a', 'b', 'c' }; + return values[f]; +} +string str( int f ) { + string s = (char)f; + return s; +} +int main() { + sout | format_enum( RGB.Green ); // "Green(65280)"}$ + sout | format_enum( Rainbow.Green ); // "Green(0,255,0)"}$ + sout | format_enum( Cherry ); // "Cherry(c)" +} Index: doc/theses/jiada_liang_MMath/uw-ethesis-frontpgs.tex =================================================================== --- doc/theses/jiada_liang_MMath/uw-ethesis-frontpgs.tex (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ doc/theses/jiada_liang_MMath/uw-ethesis-frontpgs.tex (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -141,13 +141,13 @@ One of the key properties of an enumeration is the ability to enumerate (iterate) through the constants, and hence, access their values, if present. C restricts an enumeration to the integral type @signed int@, while \CC extends enumerations to all integral types, meaning enumeration names must bind to integer constants. -Other modern programming languages provide bindings to any type and additional features to extend enumeration capabilities for better software-engineering practices. - -The \CFA (C-for-all) programming language is an evolutionary refinement of the C programing language. -One of its distinctive feature is a parametric-polymorphic generic type. -However, legacy data types from C, such as enumerations, do not adapt well into the \CFA generic type-system. +Other modern programming languages provide bindings to any type and additional features to extend enumeration capabilities for better software engineering practices. + +The \CFA (C-for-all) programming language is an evolutionary refinement of the C programming language. +One of its distinctive features is a parametric-polymorphic generic type. +However, legacy data types from C, such as enumerations, do not adapt well to the \CFA generic type-system. This thesis extends the simple and unsafe enumeration type in the C programming language into a complex and safe enumeration type in the \CFA programming-language, while maintaining backwards compatibility with C. The major contribution is an adaptation of enumerated types with the \CFA type-system in a way that integrates naturally with the generic types. -This thesis also presents a number of smaller refinement to the \CFA overload resolution rules for enumerated types, each of which improves the intuitive nature of enumeration name resolution by the compiler. +This thesis also presents several smaller refinements to the \CFA overload resolution rules for enumerated types, each of which improves the intuitive nature of enumeration name resolution by the compiler. Finally, this work adds other useful features to enumerations that better support software-engineering practices and simplify program development. @@ -166,8 +166,8 @@ Thanks to Gregor Richards and Yzihou Zhang for reading my thesis. -Special thanks to Andrew James Beach for your insight on the theory development on the thesis. +Special thanks to Andrew James Beach for your insight on the theory development of the thesis. Thanks to Michael Brooks, Fangran Yu, Colby Parsons, Thierry Delisle, Mubeen Zulifiqar, -and the entire \CFA team for development of the \CFA language, making it the best language it can be. +and the entire \CFA team for the development of the \CFA language, making it the best language it can be. Finally, a special thank you to Huawei Canada for funding this work. Index: libcfa/src/collections/string.hfa =================================================================== --- libcfa/src/collections/string.hfa (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ libcfa/src/collections/string.hfa (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -10,6 +10,6 @@ // Created On : Fri Sep 03 11:00:00 2021 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Aug 5 23:06:14 2024 -// Update Count : 128 +// Last Modified On : Tue Aug 6 07:49:52 2024 +// Update Count : 130 // @@ -161,9 +161,9 @@ string ?+?( char c, const string & s ); // add a character to a copy of the string string ?+?( const string & s, const string & s2 ); // copy and concatenate both strings -string ?+?( const char * s, char c ); // copy and concatenate both strings -string ?+?( char c, const char * s ); // copy and concatenate both strings -string ?+?( const char * s1, const char * s2 ); // copy and concatenate both strings -string ?+?( const char * s1, string & s2 ); // copy and concatenate both strings -string ?+?( const string & s, const char * c ); // copy and concatenate with NULL-terminated string +string ?+?( const char * s, char c ); // add a character to a copy of the string +string ?+?( char c, const char * s ); // add a character to a copy of the string +string ?+?( const char * c, const char * s ); // copy and add with two NULL-terminated string +string ?+?( const char * c, string & s ); // copy and add with NULL-terminated string +string ?+?( const string & s, const char * c ); // copy and add with NULL-terminated string static inline string & strcat( string & s, const string & s2 ) { s += s2; return s; } @@ -184,27 +184,27 @@ // Comparisons -int strcmp ( const string &, const string &); -bool ?==?( const string &, const string &); -bool ?!=?( const string &, const string &); -bool ?>? ( const string &, const string &); -bool ?>=?( const string &, const string &); -bool ?<=?( const string &, const string &); -bool ?? ( const string &, const char *); -bool ?>=?( const string &, const char *); -bool ?<=?( const string &, const char *); -bool ?? ( const char *, const string &); -bool ?>=?( const char *, const string &); -bool ?<=?( const char *, const string &); -bool ?? ( const string &, const string & ); +bool ?>=?( const string &, const string & ); +bool ?<=?( const string &, const string & ); +bool ?? ( const string &, const char * ); +bool ?>=?( const string &, const char * ); +bool ?<=?( const string &, const char * ); +bool ?? ( const char *, const string & ); +bool ?>=?( const char *, const string & ); +bool ?<=?( const char *, const string & ); +bool ? fromInstance( upper ) ) - abort( "call to fromInt has index %d outside enumeration range %d-%d", + abort( "call to fromInt has index %d outside of enumeration range %d-%d.", i, fromInstance( lower ), fromInstance( upper ) ); return fromInt_unsafe( i ); @@ -19,5 +19,5 @@ E upper = upperBound(); if ( fromInstance( e ) >= fromInstance( upper ) ) - abort( "call to succ() exceeds enumeration upper bound of %d", fromInstance( upper ) ); + abort( "call to succ() exceeds enumeration upper bound of %d.", fromInstance( upper ) ); return succ_unsafe(e); } @@ -26,9 +26,9 @@ E lower = lowerBound(); if ( fromInstance( e ) <= fromInstance(lower ) ) - abort( "call to pred() exceeds enumeration lower bound of %d", fromInstance( lower ) ); + abort( "call to pred() exceeds enumeration lower bound of %d.", fromInstance( lower ) ); return pred_unsafe( e ); } - int Countof( __attribute__((unused)) E e ) { + int Countof( E ) { E upper = upperBound(); E lower = lowerBound(); Index: libcfa/src/enum.hfa =================================================================== --- libcfa/src/enum.hfa (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ libcfa/src/enum.hfa (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -19,5 +19,5 @@ E succ( E e ); E pred( E e ); - int Countof( E e ); + int Countof( E ); } Index: libcfa/src/heap.cfa =================================================================== --- libcfa/src/heap.cfa (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ libcfa/src/heap.cfa (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -10,6 +10,6 @@ // Created On : Tue Dec 19 21:58:35 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Apr 7 21:54:29 2024 -// Update Count : 1644 +// Last Modified On : Wed Aug 7 10:14:47 2024 +// Update Count : 1646 // @@ -582,5 +582,5 @@ __cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText), "CFA warning (UNIX pid:%ld) : program terminating with %td(%#tx) bytes of storage allocated but not freed.\n" - "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n", + "Possible cause is mismatched allocation/deallocation calls (malloc/free), direct constructor call without a direct destructor call, or system/library routines not freeing storage.\n", (long int)getpid(), allocUnfreed, allocUnfreed ); // always print the UNIX pid } // if Index: src/Validate/ImplementEnumFunc.cpp =================================================================== --- src/Validate/ImplementEnumFunc.cpp (revision 2ca7fc29c8c37ba927ee8d0ee98416000df83e36) +++ src/Validate/ImplementEnumFunc.cpp (revision 6abb6dc94b1ba4f2beffaa34eb7f3bea3eebb309) @@ -210,8 +210,5 @@ "value", {new ast::ObjectDecl(getLocation(), "_i", new ast::EnumInstType(decl))}, - {new ast::ObjectDecl(getLocation(), "_ret", - ast::deepCopy(decl->base))}); - // else - // return genQuasiValueProto(); + {new ast::ObjectDecl(getLocation(), "_ret", decl->base)}); }