source: doc/theses/jiada_liang_MMath/trait.tex @ 43ab5fb

\chapter{Enumeration Traits}
\label{c:trait}

\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 <type_traits>
template<typename T>  @concept Enumerable@  =  std::is_enum<T>::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 \lstinline{CfaEnum} and \lstinline{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 {
        const char * @label@( E e );
        unsigned int @posn@( E e );
};
\end{cfa}
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 {
        V @value@( E e );
};
\end{cfa}
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}, // ...
};
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:GeneralizedEnumerationFormatter} 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{Generalized Enumeration Formatter}
\label{f:GeneralizedEnumerationFormatter}
\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<T>::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 trait defines a lower and upper bound for a type.
\begin{cfa}
forall( E ) trait Bounded {
        E lowerBound();
        E lowerBound();
};
\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 {
        int fromInstance( E e );
        E fromInt( unsigned int i );
        E pred( E e );
        E succ( E e );
        unsigned Countof( E );
};
\end{cfa}
Function @fromInstance@ projects a @Bounded@ member to a number and @fromInt@ is the inverse.
Function @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 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{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 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 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}

\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}$
        int ?!=?( E l, E r );           $\C{// true if l and r are different enumerators}$
        int ?<?( E l, E r );            $\C{// true if l is an enumerator before r}$
        int ?<=?( E l, E r );           $\C{// true if l before or the same as r}$
        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}
(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 );
        E --?( E & l );
        E ?+=? ( E & l, one_t );
        E ?-=? ( E & l, one_t );
        E ?+=? ( E & l, int i );
        E ?-=? ( E & l, int i );
        E ?++( E & l );
        E ?--( E & l );
}
\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.