source: doc/theses/jiada_liang_MMath/trait.tex @ b797fe36

\chapter{Enumeration Traits}
\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}
#include <type_traits>

template<typename T>
@concept Enumerable = std::is_enum<T>::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@:
\begin{cfa}
forall( E ) trait CfaEnum {
        const char * @label@( E e );
        unsigned int @posn@( E e );
};
\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. 
\begin{cfa}
forall( E, V | CfaEnum( E ) ) trait TypedEnum {
        V @value@( E e );
};
\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);
}
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.


\section{Bounded and Serial}
A bounded type defines a lower bound and a upper bound.
\begin{cfa}
forall( E ) trait Bounded {
        E lowerBound();
        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.
\begin{cfa}
forall( E | Bounded( E ) ) trait Serial {
        unsigned fromInstance( E e );
        E fromInt( unsigned int i );
        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 ); // (1)
countof( Red ); // (2)
\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:
\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)@.
\end{enumerate}

With the @Bounded@ and @Serial@, a loop over enumeration can be implemented in the following ways:
\begin{cfa}
enum() E { ... }
for( unsigned i = 0; i < countof(E); i++ ) { ... }
for( E e = lowerBound(); ; e = succ(e) ) { ...; if (e == upperBound()) break; }

forall( T ) {
        for( unsigned i = 0; i < countof(T); i++ ) { ... }
        for( T e = lowerBound(); ; e = succ(e) ) { ...; if (e == upperBound()) break; }
}
\end{cfa}

Finally, there is an associated trait defining comparison operators among enumerators. 
\begin{cfa}
forall( E, T | CfaEnum( E, T ) ) {
        // 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, zero_t );        $\C{// true if l is not the first enumerator}$
        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}

As an alternative, users can define the boolean conversion for CfaEnum:

\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 zero and non-zero 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:
\begin{cfa}[label=lst:range_functions]
for ( Alphabet alph; Alphabet ) { sout | alph; }
>>> A B C ... D
\end{cfa}
The for-loop uses the enumeration type @Alphabet@ its range, and 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.

\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}