source: doc/theses/fangren_yu_MMath/future.tex@ 4740281

\chapter{Future Work}

\vspace*{-18pt}
The following are feature requests related to type-system enhancements that have surfaced during the development of the \CFA language and library, but have not been implemented yet.
Currently, developers must work around these missing features, sometimes resulting in inefficiency.


\section{Closed trait types}

Currently, \CFA does not have any closed types, as open type are the basis of its unique type-system, allowing new functions to be added at any time to override existing ones for trait satisfaction.
Locally-declared nested-functions,\footnote{
Nested functions are not a feature in C but supported by \lstinline{gcc} for multiple decades and are used heavily in \CFA.}
or a function-pointer variable can be used to make a type satisfy a certain trait temporarily in a limited lexical scope.
However, the lack of closed types in such a \emph{duck typing} scheme presents two problems.
\begin{enumerate}[leftmargin=*]
\item
Library implementers normally do not want users to override certain operations and cause the behaviour of polymorphic invocations to change.
\item
Caching and reusing resolution results in the compiler is effected, as newly introduced declarations can participate in assertion resolution;
as a result, previously invalid subexpressions suddenly become valid, or alternatively cause ambiguity in assertions.
\end{enumerate}
Sometimes those interfaces are fairly complicated, \eg the \CFA I/O library traits @istream@ and @ostream@ each have over 20 operations.
Without the ability to store and reuse assertion resolution results, each time the compiler encounters an I/O operation (denoted by the pipe operator @?|?@ like the @<<@, @>>@ stream operators in \CC) it has to resolve the same set of assertions again, causing a lot of repetitive work.
Previous experiments have shown that the I/O assertions often account for over half of the number of assertions resolved in a \CFA translation unit.
Hence, eliminating repetitive assertion resolution, which are very unlikely to change by new overloads, can provide a significant performance benefit.

\VRef[Figure]{f:basicOstreamTrait} shows the basic output-stream trait in \CFA and the overloaded I/O operator is declared as:
\begin{cfa}
forall( ostype & | basic_ostream( ostype ) ) ostype & ?|?( ostype &, int ); // one for each basic type
\end{cfa}
The \CFA polymorphic calling convention means all of these trait functions are repeatedly resolved at each output-operator call-site and then become implicit arguments of the call.
This creates both compile-time and run-time overheads.
As stated, resolving assertions takes the most amount of time during compilation, and it is common to see in the current codebase and test suite that the majority of compilation time is spent in I/O statements.
With closed types, the I/O assertions can be resolved once and this information reused everywhere.
Furthermore, closed types can have a different calling convention of pushing a virtual-table pointer rather than individual arguments onto the stack.
Although for I/O, this benefit might not be significant, since these operations involve system calls that are inherently slow.

\begin{figure}
\begin{cfa}[escapechar={\#}]
forall( ostype & ) @trait@ basic_ostream {
        // private
        bool sepPrt$( ostype & );                                       #\C[3.35in]{// get separator state (on/off)}#
        void sepReset$( ostype & );                                     #\C{// set separator state to default state}#
        void sepReset$( ostype &, bool );                       #\C{// set separator and default state}#
        const char * sepGetCur$( ostype & );            #\C{// get current separator string}#
        void sepSetCur$( ostype &, const char [] );     #\C{// set current separator string}#
        bool getNL$( ostype & );                                        #\C{// get newline}#
        bool setNL$( ostype &, bool );                          #\C{// set newline}#
        bool getANL$( ostype & );                                       #\C{// get auto newline (on/off)}#
        bool setANL$( ostype &, bool );                         #\C{// set auto newline (on/off)}#
        bool getPrt$( ostype & );                                       #\C{// get fmt called in output cascade}#
        bool setPrt$( ostype &, bool );                         #\C{// set fmt called in output cascade}#
        // public
        void nlOn( ostype & );                                          #\C{// turn auto-newline state on}#
        void nlOff( ostype & );                                         #\C{// turn auto-newline state off}#
        void sep( ostype & );                                           #\C{// turn separator state on}#
        void nosep( ostype & );                                         #\C{// turn separator state off}#
        bool sepOn( ostype & );                                         #\C{// set default state to on}#
        bool sepOff( ostype & );                                        #\C{// set default state to off}#
        const char * sepGet( ostype & );                        #\C{// get separator string}#
        void sepSet( ostype &, const char [] );         #\C{// set separator to string (15 maximum)}#
        const char * sepGetTuple( ostype & );           #\C{// get tuple separator string}#
        void sepSetTuple( ostype &, const char [] );#\C{// set tuple separator to string (15 maximum)}#
        void ends( ostype & );                                          #\C{// end of output statement}\CRT#
        int fmt( ostype &, const char format[], ... ) __attribute__(( format(printf, 2, 3) ));
};
\end{cfa}
\caption{\lstinline{basic_ostream} trait}
\label{f:basicOstreamTrait}
\end{figure}

A \CFA closed trait type is similar to a Haskell type class requiring an explicit instance declaration.
The syntax for the closed trait might look like:
\begin{cfa}
forall( ostype & ) @closed@ trait basic_ostream { /* above declarations */ };
@trait@ basic_ostream struct ofstream { ... }; // bind trait to type, implement basic_ostream
\end{cfa}
At the trait declaration, all the required trait functions must be inferred and specialized in the usual way.
The list of inferred and specialized functions is then saved as an array of function pointers (vtable), and polymorphic functions using the closed type are passed the vtable, instead of a list of implicit parameters.
\begin{cfa}
ostype ?|?( ostype &, int, @basic_ostream_vtable *@ ); // parametric vtable
sout | 42;   /* becomes */   ?|?( sout, 42, @ofstream_trait@ );  // generated for closed type ofstream
\end{cfa}

Closed types can provide additional encapsulation.
In \VRef[Figure]{f:basicOstreamTrait}, the functions ending with dollar sign @$@ are meant to be private (internal to the library) so client code should not be able to see or call these functions directly.
This kind of information hiding is impossible with the current trait and assertion system, because the trait information must be visible at the call site for the polymorphic call to resolve.
With closed traits and types, it is possible to forward declare a closed trait (which does not make sense otherwise) and its vtable without exposing any details to the client.
That is, all the information necessary to call trait functions is now captured in a single vtable pointer built at compile time and the type of the vtable pointer is opaque.


\section{Associated Types}

The analysis presented in \VRef{s:AssertionSatisfaction} shows if all type parameters have to be bound before assertion resolution, the complexity of resolving assertions become much lower as every assertion parameter can be resolved independently.
That is, by utilizing information from higher up the expression tree for return value overloading, most of the type bindings can be resolved.
However, there are scenarios where some intermediate types need to be involved in certain operations, which are neither input nor output types.

\CFA standard library provides a few polymorphic container types similar to those found in the \CC standard library.
Like \CC, \CFA would like to have a harmonized iterator interface for different container types.
While this feature is still under development, the following trait outline is used to present the problem.
\begin{cfa}
forall( Container, Elem, Iter ) trait iterable {
        @Iter@ begin( Container );
        @Iter@ end( Container );
        @Elem@ & *?( Iter );
        Iter ++?( Iter );
        bool ?==?( Iter, Iter );
};
\end{cfa}
These are the \CC operators required for for-loop comprehension, \eg @for (Elem & e : container)@.
Note, the iterable trait is meant to describe a property for a container type, but involves two additional types, one for the element type and one for the iterator type.
However, @Iter@ is intended to be deduced from the @begin@ and @end@ operations on the container type;
the same can be said for the element type @Elem@.
The alternative is to make @Elem@ and @Iter@ unbound type-parameters by removing them from the @forall@.
As mentioned, unbound type-parameters cause problems, but that is the only way to describe the iterable property.

To solve this problem, I propose adding associate-type declarations in addition to the existing unbounded @forall@ type parameter.
In the body of a trait declaration, new types can be introduced as the return type of an expression involving type parameters.
\begin{cfa}
forall( Container ) trait iterable {
        @type@ Iter begin( Container );
        Iter end( Container );
        @type@ Elem & *?( Iter );
        Iter ++?( Iter );
        bool ?==?( Iter, Iter );
};
\end{cfa}
This matches conceptually with the iterable trait having only the container type, rather than three types.
The iterator type and element type are now viewed as properties of the container type not independent type parameters.

There remains one design decision to be made: whether the expression that defines an associated type needs to be uniquely resolved.
If the associated type does not appear in the parameter or return types, this requirement seems reasonable.
The reason is that the expression cost does not consider any conversions that occur in assertion parameter matching, which essentially means having multiple ways to resolve an associated type always results in ambiguity.
The interesting case is when the associated type also appears in the return type, where both resolving the return type overload based on context and resolving the assertion that defines the associate type can help;
for the whole expression to resolve, they must agree on a common result.

Moss gave the following example to illustrate \CFA assertion system's expressiveness.
\begin{cfa}
forall( Ptr, Elem ) trait pointer_like {
        Elem & *?( Ptr ); // Ptr can be dereferenced to Elem
};
struct list {
        int value;
        list * next;
};
typedef list * list_iterator;
int & *?( list_iterator it ) {
        return it->value;
}
\end{cfa}
This can be viewed as having an associated type, @Elem@, as return, which can potentially vary based on context.
Note that the type @list *@ satisfies both @pointer_like( list *, int )@ and @pointer_like( list *,@ @list )@ (the latter by the built-in pointer dereference operator) and the expression @*it@ can be either a @struct list@ or an @int@.
Requiring associated types to be unique makes the @pointer_like@ trait not applicable to @list *@, which is undesirable.
I have not attempted to implement associated types in \CFA compiler, but based on the above discussions, one option is to make associated type resolution and return type overloading coexist:
when the associated type appears in returns, it is deduced from the context and then verify the trait with ordinary assertion resolution;
when it does not appear in the returns, the type is required to be uniquely determined by the expression that defines the associated type.


\section{User-defined conversions}

Missing type-system feature is a scheme for user-defined conversions.
Conversion means one type goes through an arbitrary complex process of changing its value to some meaningful value in another type.
Because the conversion process can be arbitrarily complex, it requires the power of a function.
Arbitrary conversions are already possible through standalone named functions.
\begin{cfa}
S convert( T );  $\C[2in]{// change T to S}$
S s;   T t;
s = convert( t );
\end{cfa}
C has implicit/explicit conversions for the builtin types.
\begin{cfa}
int i = 3.5;  $\C{// implicit, change the floating-point bits to integral bits}$
int i = (int)3.5 + 17;  $\C{// explicit, change the floating-point bits to integral bits}$
\end{cfa}
When the conversion occurs in expression evaluation can significantly affect the result, where function call has higher precedence than cast.
Overloading the cast operator would allow user-defined conversions to look and feel, like regular C casts, as is provided in \CC.
\begin{cfa}[escapechar={}]
S ?@$@( T ) { /* change T to S */ }
s = t;
\end{cfa}
% $ stop formatting
Similarly, constructors can be used for implicit conversion, as in \CC.
\begin{cfa}
void ?{}( S s, T t ) { ... } $\C{// convert T to S}$
s = t;  $\C{// rewritten as s = ?{}( s, t )}\CRT$
\end{cfa}
To integrate properly with the \CFA conversion model, there would need to distinguish between safe and unsafe conversion, and possibly a way to denote conversions as explicit-only or non-chainable, otherwise conversion cycles are possible.