source: doc/theses/jiada_liang_MMath/background.tex @ a03ed29

\chapter{Background}

\vspace*{-8pt}

\CFA is a backwards-compatible extension of the C programming language, therefore, it must support C-style enumerations.
The following discussion covers C enumerations.

As mentioned in \VRef{s:Aliasing}, it is common for C programmers to ``believe'' there are three equivalent forms of named constants.
\begin{clang}
#define Mon 0
static const int Mon = 0;
enum { Mon };
\end{clang}
\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.
\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 occupy storage.
\begin{clang}
$\$$ nm test.o
0000000000000018 r Mon
\end{clang}
\item
Only the @enum@ form is managed by the compiler, is part of the language type-system, works in all C constant-expression locations, and normally does not occupy storage.
\end{enumerate}


\section{C \lstinline{const}}
\label{s:Cconst}

C can simulate the aliasing @const@ declarations \see{\VRef{s:Aliasing}}, with static and dynamic initialization.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{@{}c}{\textbf{static initialization}} &  \multicolumn{1}{c@{}}{\textbf{dynamic intialization}} \\
\begin{clang}
static const int one = 0 + 1;
static const void * NIL = NULL;
static const double PI = 3.14159;
static const char Plus = '+';
static const char * Fred = "Fred";
static const int Mon = 0, Tue = Mon + 1, Wed = Tue + 1,
        Thu = Wed + 1, Fri = Thu + 1, Sat = Fri + 1, Sun = Sat + 1;
\end{clang}
&
\begin{clang}
void foo() {
        // auto scope only
        const int r = random() % 100;
        int va[r];
}
\end{clang}
\end{tabular}
\end{cquote}
However, statically initialized identifiers cannot appear in constant-expression contexts, \eg @case@.
Dynamically initialized identifiers may appear in initialization and array dimensions in @g++@, which allows variable-sized arrays on the stack.
Again, this form of aliasing is not an enumeration.

\section{C Enumeration}
\label{s:CEnumeration}

The C enumeration has the following syntax~\cite[\S~6.7.2.2]{C11}.
\begin{clang}[identifierstyle=\linespread{0.9}\it]
$\it enum$-specifier:
        enum identifier$\(_{opt}\)$ { enumerator-list }
        enum identifier$\(_{opt}\)$ { enumerator-list , }
        enum identifier
enumerator-list:
        enumerator
        enumerator-list , enumerator
enumerator:
        enumeration-constant
        enumeration-constant = constant-expression
\end{clang}
The terms \emph{enumeration} and \emph{enumerator} used in this work \see{\VRef{s:Terminology}} come from the grammar.
The C enumeration semantics are discussed using examples.


\subsection{Type Name}
\label{s:TypeName}

An \emph{unnamed} enumeration is used to provide aliasing \see{\VRef{s:Aliasing}} exactly like a @const@ declaration in other languages.
However, it is restricted to integral values.
\begin{clang}
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 initialization, @Max10Plus1@) is \newterm{auto-initialized}: 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.
Finally, enumerators are \newterm{unscoped}, \ie enumerators declared inside of an @enum@ are visible (projected) 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.
While the semantics is misleading, this enumeration form matches with aggregate types:
\begin{cfa}
typedef struct @/* unnamed */@  { ... } S;
struct @/* unnamed */@  { ... } x, y, z;        $\C{// questionable}$
struct S {
        union @/* unnamed */@ {                                 $\C{// unscoped fields}$
                int i;  double d ;  char ch;
        };
};
\end{cfa}
Hence, C programmers would expect this enumeration form to exist in harmony with the aggregate form.

A \emph{named} enumeration is an enumeration:
\begin{clang}
enum @Week@ { Mon, Tue, Wed, Thu@ = 10@, Fri, Sat, Sun };
\end{clang}
and adopts the same semantics with respect to direct and auto intialization.
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.
\begin{clang}
enum Week {
        Thu@ = 10@, Fri, Sat, Sun,
        Mon@ = 0@, Tue, Wed@,@                  $\C{// terminating comma}$
};
\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{
A terminating comma appears in other C syntax, \eg the initializer list.}
This feature allow enumerator lines to be interchanged without moving a comma.
Named enumerators are also unscoped.


\subsection{Implementation}
\label{s:CenumImplementation}

In theory, 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:
\begin{quote}
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 @<limits.h>@).~\cite[\S~6.2.5(5)]{C11}
\end{quote}
Howeveer, @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.
In reality, both @gcc@ and @clang@ partially ignore this specification and type the integral size of an enumerator based its initialization.
\begin{cfa}
enum E { IMin = INT_MIN, IMax = INT_MAX,
                         ILMin = LONG_MIN, ILMax = LONG_MAX,
                         ILLMin = LLONG_MIN, ILLMax = LLONG_MAX };
int main() {
        printf( "%zd %d %d\n%zd %ld %ld\n%zd %ld %ld\n",
                         sizeof(IMin), IMin, IMax,
                         sizeof(ILMin), ILMin, ILMax,
                         sizeof(ILLMin), ILLMin, ILLMax );
}
4 -2147483648 2147483647
8 -9223372036854775808 9223372036854775807
8 -9223372036854775808 9223372036854775807
\end{cfa}
Hence, initialization in the range @INT_MIN@..@INT_MAX@ is 4 bytes, and outside this range is 8 bytes.

\subsection{Usage}
\label{s:Usage}

C proves an implicit \emph{bidirectional} conversion between an enumeration and its integral type.
\begin{clang}
enum Week week = Mon;                           $\C{// week == 0}$
week = Fri;                                                     $\C{// week == 11}$
int i = Sun;                                            $\C{// implicit conversion to int, i == 13}$
@week = 10000;@                                         $\C{// UNDEFINED! implicit conversion to Week}$
\end{clang}
While converting an enumerator to its underlying type is useful, the implicit conversion from the base type to an enumeration type is a common source of error.

Enumerators can appear in @switch@ and looping statements.
\begin{cfa}
enum Week { Mon, Tue, Wed, Thu, Fri, Sat, Sun };
switch ( week ) {
        case Mon ... Fri:                               $\C{// gcc case range}$
                printf( "weekday\n" );
        case Sat: case Sun:
                printf( "weekend\n" );
}
for ( enum Week day = Mon; day <= Sun; day += 1 ) { $\C{// step of 1}$
        printf( "day %d\n", day ); // 0-6
}
\end{cfa}
For iterating to make sense, the enumerator values \emph{must} have a consecutive ordering with a fixed step between values.
For example, a 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 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.
\begin{cfa}
enum E { A, B, C, D, @N@ };  // N == 4
for ( enum E e = A; e < @N@; e += 1 ) ...
\end{cfa}
Here, the auto-incrementing counts the number of enumerators and puts the total into the last enumerator @N@.
@N@ is often used as the dimension for an array assocated with the enumeration.
\begin{cfa}
E array[@N@];
for ( enum E e = A; e < N; e += 1 ) {
        array[e] = e;
}
\end{cfa}
However, for non-integral typed enumerations, \see{\VRef{f:EumeratorTyping}}, this idiom fails.

This idiom is used in another C idiom for matching companion information.
For example, an enumeration is linked with a companion array of printable strings.
\begin{cfa}
enum Integral_Type { chr, schar, uschar, sshort, ushort, sint, usint, ..., NO_OF_ITYPES };
char * Integral_Name[@NO_OF_ITYPES@] = {
        "char", "signed char", "unsigned char",
        "signed short int", "unsigned short int",
        "signed int", "unsigned int", ...
};
enum Integral_Type integral_type = ...
printf( "%s\n", Integral_Name[@integral_type@] ); // human readable type name
\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 need 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 enumeration features 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.

\begin{cfa}
void f(); // (1)
void f(int); // (2); Overloaded on the number of parameters
void f(char); // (3); Overloaded on parameter type

f('A');
\end{cfa}
In this case, the name f is overloaded with a nullity function and two arity functions with different parameters types. Exactly which precedures being executed
is determined based on the passing arguments. The last expression of the preceding example calls f with one arguments, narrowing the possible candidates down to (2) and (3).
Between those, function argument 'A' is an exact match to the parameter expected by (3), while needing an @implicit conversion@ to call (2). The compiler determines (3) is the better candidates among
and procedure (3) is being executed.

\begin{cfa}
int f(int); // (4); Overloaded on return type
[int, int] f(int); // (5) Overloaded on the number of return value
\end{cfa}
The function declarations (4) and (5) show the ability of \CFA functions overloaded with different return value, a feature that is not shared by C++.


\subsection{Operator Overloading}
Operators in \CFA are specialized function and are overloadable by with specially-named functions represents the syntax used to call the operator.
% For example, @bool ?==?T(T lhs, T rhs)@ overloads equality operator for type T, where @?@ is the placeholders for operands for the operator.
\begin{cfa}
enum Weekday { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday };
bool ?<?(const Weekday a, const Weekday b) {
        return ((int)a + 1);
}
Monday < Sunday; // False
?<?( Monday, Sunday ); // Equivalent syntax
\end{cfa}
Unary operators are functions that takes one argument and have name @operator?@ or @?operator@, where @?@ is the placeholders for operands.
Binary operators are function with two parameters. They are overloadable with function name @?operator?@.

\subsection{Constructor and Destructor}
In \CFA, all objects are initialized by @constructors@ during its allocation, including basic types, 
which are initialized by auto-generated basic type constructors.

Constructors are overloadable functions with name @?{}@, return @void@, and have at least one parameter, which is a reference
to the object being constructored (Colloquially referred to "this" or "self" in other language).

\begin{cfa}
struct Employee {
        const char * name;
        double salary;
};

void ?{}( Employee& this, const char * name, double salary ) {
    this.name = name;
    this.salary = salary;
}

Employee Sara { "Sara Schmidt", 20.5 };
\end{cfa}
Like Python, the "self" reference is implicitly passed to a constructor. The Employee constructors takes two additional arugments used in its
field initialization.

A destructor in \CFA is a function that has name @^?{}@. It returns void, and take only one arugment as its "self".
\begin{cfa}
void ^?{}( Employee& this ) {
    free(this.name);
    this.name = 0p;
    this.salary = 0;
}
\end{cfa}
Destructor can be explicitly evoked as a function call, or implicitly called at the end of the block in which the object is delcared.
\begin{cfa}
{
^Sara{};
Sara{ "Sara Craft", 20 };
} // ^Sara{}
\end{cfa}

\subsection{Variable Overloading}
C and C++ disallow more than one variable declared in the same scope with the same name. When a variable declare in a inner scope has the same name as 
a variable in an outer scope, the outer scope variable is "shadowed" by the inner scope variable and cannot be accessed directly. 

\CFA has variable overloading: multiple variables can share the same name in the same scope, as long as they have different type. Name shadowing only 
happens when the inner scope variable and the outer scope ones have the same type.
\begin{cfa}
double i = 6.0;
int i = 5;
void foo( double i ) { sout | i; } // 6.0
\end{cfa}

\subsection{Special Literals}
Literal 0 has special meanings within different contexts: it can means "nothing" or "empty", an additive identity in arithmetic, a default value as in C (null pointer), 
or an initial state.
Awaring of its significance, \CFA provides a special type for the 0 literal, @zero_t@, to define the logical @zero@ for custom types.
\begin{cfa}
struct S { int i, j; };
void ?{}( S & this, @zero_t@ ) { this.i = 0; this.j = 0; } // zero_t, no parameter name allowed
S s0 = @0@;
\end{cfa}
Overloading @zero_t@ for S provides new definition for @zero@ of type S.

According to the C standard, @0@ is the @only@ false value. Any values compares equals to @0@ is false, and not euqals @0@ is true. As a consequence, control structure 
such as @if()@ and @while()@ only runs it true clause when its predicate @not equals@ to @0@. 

\CFA generalizes this concept and allows to logically overloads the boolean value for any type by overloading @not equal@ comparison against @zero_t@.
\begin{cfa}
int ?@!=@?( S this, @zero_t@ ) { return this.i != 0 && this.j != 0; }
\end{cfa}

% In C, the literal 0 represents the Boolean value false. The expression such as @if (x)@ is equivalent to @if (x != 0)@ .
% \CFA allows user to define the logical zero for a custom type by overloading the @!=@ operation against a special type, @zero_t@, 
% so that an expression with the custom type can be used as a predicate without the need of conversion to the literal 0.
% \begin{cfa}
% struct S s;
% int ?!=?(S, zero_t);
% if (s) {}
% \end{cfa}
Literal 1 is also special. Particularly in C, the pre-increment operator and post-increment operator can be interpreted in terms of @+= 1@.
The logical @1@ in \CFA is represented by special type @one_t@.
\begin{cfa}
void ?{}( S & this, one_t ) { this.i = 1; this.j = 1; } // one_t, no parameter name allowed
S & ?+=?( S & this, one_t ) { this.i += 1; this.j += 1; return op; }
\end{cfa}
Without explictly overloaded by a user, \CFA uses the user-defined @+=(S&, one_t)@ to interpret @?++@ and @++?@, as both are polymorphic functions in \CFA.

\subsection{Polymorphics Functions}
Parametric-Polymorphics functions are the functions that applied to all types. \CFA functions are parametric-polymorphics when 
they are written with the @forall@ clause.

\begin{cfa}
forall(T)
T identity(T x) { return x; }
identity(42);
\end{cfa}
The identity function accepts a value from any type as an arugment, and the type parameter @T@ is bounded to @int@ when the function
is called with 42. 

The forall clause can takes @type assertions@ that restricts the polymorphics type. 
\begin{cfa}
forall( T | { void foo(T); } )
void bar(T t) { foo(t); }

struct S {} s;
void foo(struct S);

bar(s);
\end{cfa}
The assertion on @T@ restricts the range of types for bar to only those implements foo with the matching a signature, so that bar() 
can call @foo@ in its body with type safe.
Calling on type with no mathcing @foo()@ implemented, such as int, causes a compile time type assertion error. 

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

\begin{cfa}
trait Bird(T) {
        int days_can_fly(T i);
        void fly(T t);
};

forall(B | Bird(B)) {
        void bird_fly(int days_since_born, B bird) {
                if (days_since_born > days_can_fly(bird)) {
                        fly(bird);
                }
        }
}

struct Robin {} r;
int days_can_fly(Robin r) { return 23; }
void fly(Robin r) {}

bird_fly( r );
\end{cfa}

Grouping type assertions into named trait effectively create a reusable interface for parametrics polymorphics types.

\section{Expression Resolution}

The overloading feature poses a challenge in \CFA expression resolution. Overloadeded identifiers can refer multiple 
candidates, with multiples being simultaneously valid. The main task of \CFA resolver is to identity a best candidate that
involes less implicit conversion and polymorphism.

\subsection{Conversion Cost}
In C, functions argument and parameter type does not need to be exact match, and the compiler performs an @implicit conversion@ on argument.
\begin{cfa}
void foo(double i);
foo(42);
\end{cfa}
The implicit conversion in C is relatively simple because of the abscence of overloading, with the exception of binary operators, for which the 
compiler needs to find a common type of both operands and the result. The pattern is known as "usual arithmetic conversions".

\CFA generalizes C implicit conversion to function overloading as a concept of @conversion cost@.
Initially designed by Bilson, conversion cost is a 3-tuple, @(unsafe, poly, safe)@, where unsafe is the number of narrowing conversion,
poly is the count of polymorphics type binding, and safe is the sum of the degree of widening conversion. Every 
basic type in \CFA has been assigned with a @distance to Byte@, or @distance@, and the degree of widening conversion is the difference between two distances.

Aaron extends conversion cost to a 7-tuple, 
@@(unsafe, poly, safe, sign, vars, specialization, reference)@@. The summary of Aaron's cost model is the following:
\begin{itemize}
\item Unsafe is the number of argument that implicitly convert to a type with high rank.
\item Poly accounts for number of polymorphics binding in the function declaration.
\item Safe is sum of distance (add reference/appendix later).
\item Sign is the number of sign/unsign variable conversion.
\item Vars is the number of polymorphics type declared in @forall@.
\item Specialization is opposite number of function declared in @forall@. More function declared implies more constraint on polymorphics type, and therefore has the lower cost.
\item Reference is number of lvalue-to-rvalue conversion.
\end{itemize}