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

\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 );
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:
\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}

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

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


\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@.

\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 ) ) {
        // 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}

\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 ) ) {
        // 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. 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}