source: doc/generic_types/generic_types.tex@ 1ca52db

% take of review (for line numbers) and anonymous (for anonymization) on submission
\documentclass[format=acmlarge, anonymous, review]{acmart}

\usepackage{listings}   % For code listings

% Useful macros
\newcommand{\CFA}{C$\mathbf\forall$} % Cforall symbolic name
\newcommand{\CC}{\rm C\kern-.1em\hbox{+\kern-.25em+}} % C++ symbolic name
\newcommand{\CCeleven}{\rm C\kern-.1em\hbox{+\kern-.25em+}11} % C++11 symbolic name
\newcommand{\CCfourteen}{\rm C\kern-.1em\hbox{+\kern-.25em+}14} % C++14 symbolic name
\newcommand{\CCseventeen}{\rm C\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name

\newcommand{\TODO}{\textbf{TODO}}
\newcommand{\eg}{\textit{e}.\textit{g}.}
\newcommand{\ie}{\textit{i}.\textit{e}.}
\newcommand{\etc}{\textit{etc}.}

% CFA programming language, based on ANSI C (with some gcc additions)
\lstdefinelanguage{CFA}[ANSI]{C}{
        morekeywords={_Alignas,_Alignof,__alignof,__alignof__,asm,__asm,__asm__,_At,_Atomic,__attribute,__attribute__,auto,
                _Bool,catch,catchResume,choose,_Complex,__complex,__complex__,__const,__const__,disable,dtype,enable,__extension__,
                fallthrough,fallthru,finally,forall,ftype,_Generic,_Imaginary,inline,__label__,lvalue,_Noreturn,one_t,otype,restrict,sized,_Static_assert,
                _Thread_local,throw,throwResume,trait,try,typeof,__typeof,__typeof__,zero_t},
}%

\lstset{
language=CFA,
columns=fullflexible,
basicstyle=\linespread{0.9}\sf,                                                 % reduce line spacing and use sanserif font
stringstyle=\tt,                                                                                % use typewriter font
tabsize=4,                                                                                              % 4 space tabbing
xleftmargin=\parindent,                                                                 % indent code to paragraph indentation
% extendedchars=true,                                                                   % allow ASCII characters in the range 128-255
% escapechar=§,                                                                                 % LaTeX escape in CFA code §...§ (section symbol), emacs: C-q M-'
mathescape=true,                                                                                % LaTeX math escape in CFA code $...$
keepspaces=true,                                                                                %
showstringspaces=false,                                                                 % do not show spaces with cup
showlines=true,                                                                                 % show blank lines at end of code
aboveskip=4pt,                                                                                  % spacing above/below code block
belowskip=3pt,
% replace/adjust listing characters that look bad in sanserif
literate={-}{\raisebox{-0.15ex}{\texttt{-}}}1 {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {_}{\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{$\rightarrow$}2,
% moredelim=**[is][\color{red}]{®}{®},                                  % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
% moredelim=**[is][\color{blue}]{ß}{ß},                                 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
% moredelim=**[is][\color{OliveGreen}]{¢}{¢},                   % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
% moredelim=[is][\lstset{keywords={}}]{¶}{¶},                   % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
}% lstset

% inline code @...@
\lstMakeShortInline@

% ACM Information
\citestyle{acmauthoryear}

\acmJournal{PACMPL}

\title{Generic and Tuple Types with Efficient Dynamic Layout in \CFA{}}

\author{Aaron Moss}
\affiliation{%
        \institution{University of Waterloo}
        \department{David R. Cheriton School of Computer Science}
        \streetaddress{Davis Centre, University of Waterloo}
        \city{Waterloo}
        \state{ON}
        \postcode{N2L 3G1}
        \country{Canada}
}
\email{a3moss@uwaterloo.ca}

\author{Robert Schluntz}
\affiliation{%
        \institution{University of Waterloo}
        \department{David R. Cheriton School of Computer Science}
        \streetaddress{Davis Centre, University of Waterloo}
        \city{Waterloo}
        \state{ON}
        \postcode{N2L 3G1}
        \country{Canada}
}
\email{rschlunt@uwaterloo.ca}

\author{Peter Buhr}
\affiliation{%
        \institution{University of Waterloo}
        \department{David R. Cheriton School of Computer Science}
        \streetaddress{Davis Centre, University of Waterloo}
        \city{Waterloo}
        \state{ON}
        \postcode{N2L 3G1}
        \country{Canada}
}
\email{pabuhr@uwaterloo.ca}

\terms{generic, tuple, types}
\keywords{generic types, tuple types, polymorphic functions, C, Cforall}

\begin{CCSXML}
<ccs2012>
<concept>
<concept_id>10011007.10011006.10011008.10011024.10011025</concept_id>
<concept_desc>Software and its engineering~Polymorphism</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10011007.10011006.10011008.10011024.10011028</concept_id>
<concept_desc>Software and its engineering~Data types and structures</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10011007.10011006.10011041.10011047</concept_id>
<concept_desc>Software and its engineering~Source code generation</concept_desc>
<concept_significance>300</concept_significance>
</concept>
</ccs2012>
\end{CCSXML}

\ccsdesc[500]{Software and its engineering~Polymorphism}
\ccsdesc[500]{Software and its engineering~Data types and structures}
\ccsdesc[300]{Software and its engineering~Source code generation}

\begin{abstract}
\TODO{} Write abstract.
\end{abstract}

\begin{document}

\maketitle

\section{Introduction \& Background}

\CFA{}\footnote{Pronounced ``C-for-all'', and written \CFA{} or Cforall.} is an evolutionary extension of the C programming language which aims to add modern language features to C while maintaining both source compatibility with C and a familiar mental model for programmers. Four key design goals were set out in the original design of \CFA{} \citep{Bilson03}:
\begin{enumerate}
\item The behaviour of standard C code must remain the same when translated by a \CFA{} compiler as when translated by a C compiler.
\item Standard C code must be as fast and as small when translated by a \CFA{} compiler as when translated by a C compiler.
\item \CFA{} code must be at least as portable as standard C code.
\item Extensions introduced by \CFA{} must be translated in the most efficient way possible.
\end{enumerate}
The purpose of these goals is to ensure that existing C codebases can be converted to \CFA{} incrementally and with minimal effort, and that programmers who already know C can productively produce \CFA{} code without extensive training beyond the extension features they wish to employ.

\CFA{} has been previously extended with polymorphic functions and name overloading (including operator overloading) \citep{Bilson03}, and deterministically-executed constructors and destructors \citep{Schluntz17}. This paper describes how generic and tuple types are designed and implemented in \CFA{} in accordance with both the backward compatibility goals and existing features described above.

\subsection{Polymorphic Functions}
\label{sec:poly-fns}

\CFA{}'s polymorphism was originally formalized by \citet{Ditchfield92}, and first implemented by \citet{Bilson03}. The signature feature of \CFA{} is parametric-polymorphic functions; such functions are written using a @forall@ clause (which gives the language its name): 
\begin{lstlisting}
forall(otype T)
T identity(T x) {
    return x;
}

int forty_two = identity(42); // T is bound to int, forty_two == 42
\end{lstlisting}
The @identity@ function above can be applied to any complete object type (or ``@otype@''). The type variable @T@ is transformed into a set of additional implicit parameters to @identity@, which encode sufficient information about @T@ to create and return a variable of that type. The \CFA{} implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor and destructor. If this extra information is not needed, the type parameter can be declared as @dtype T@, where @dtype@ is short for ``data type''.

Here, the runtime cost of polymorphism is spread over each polymorphic call, due to passing more arguments to polymorphic functions; preliminary experiments have shown this overhead to be similar to \CC{} virtual function calls. An advantage of this design is that, unlike \CC{} template functions, \CFA{} @forall@ functions are compatible with separate compilation.

Since bare polymorphic types do not provide a great range of available operations, \CFA{} provides a \emph{type assertion} mechanism to provide further information about a type:
\begin{lstlisting}
forall(otype T | { T twice(T); })
T four_times(T x) {
    return twice( twice(x) );
}

double twice(double d) { return d * 2.0; } // (1)

double magic = four_times(10.5); // T is bound to double, uses (1) to satisfy type assertion
\end{lstlisting}
These type assertions may be either variable or function declarations that depend on a polymorphic type variable. @four_times@ can only be called with an argument for which there exists a function named @twice@ that can take that argument and return another value of the same type; a pointer to the appropriate @twice@ function is passed as an additional implicit parameter to the call of @four_times@.

Monomorphic specializations of polymorphic functions can themselves be used to satisfy type assertions. For instance, @twice@ could have been defined using the \CFA{} syntax for operator overloading as:
\begin{lstlisting}
forall(otype S | { S ?+?(S, S); })
S twice(S x) { return x + x; }  // (2)
\end{lstlisting} 
This version of @twice@ works for any type @S@ that has an addition operator defined for it, and it could have been used to satisfy the type assertion on @four_times@. 
The compiler accomplishes this by creating a wrapper function calling @twice // (2)@ with @S@ bound to @double@, then providing this wrapper function to @four_times@\footnote{\lstinline@twice // (2)@ could also have had a type parameter named \lstinline@T@; \CFA{} specifies renaming of the type parameters, which would avoid the name conflict with the type variable \lstinline@T@ of \lstinline@four_times@.}.

\subsection{Traits}

\CFA{} provides \emph{traits} as a means to name a group of type assertions, as in the example below:
\begin{lstlisting}
trait has_magnitude(otype T) {
    bool ?<?(T, T);  // comparison operator for T
    T -?(T);  // negation operator for T
    void ?{}(T*, zero_t);  // constructor from 0 literal
};

forall(otype M | has_magnitude(M))
M abs( M m ) {
    M zero = { 0 };  // uses zero_t constructor from trait
    return m < zero ? -m : m;
}

forall(otype M | has_magnitude(M))
M max_magnitude( M a, M b ) {
    return abs(a) < abs(b) ? b : a; 
}
\end{lstlisting}
This capability allows specifying the same set of assertions in multiple locations, without the repetition and likelihood of mistakes that come with manually writing them out for each function declaration.

@otype@ is essentially syntactic sugar for the following trait:
\begin{lstlisting}
trait otype(dtype T | sized(T)) {
        // sized is a compiler-provided pseudo-trait for types with known size & alignment
        void ?{}(T*);  // default constructor
        void ?{}(T*, T);  // copy constructor
        void ?=?(T*, T);  // assignment operator
        void ^?{}(T*);  // destructor
};
\end{lstlisting}
Given this information, variables of polymorphic type can be treated as if they were a complete struct type -- they can be stack-allocated using the @alloca@ compiler builtin, default or copy-initialized, assigned, and deleted. As an example, the @abs@ function above would produce generated code something like the following (simplified for clarity and brevity):
\begin{lstlisting}
void abs( size_t _sizeof_M, size_t _alignof_M, 
                void (*_ctor_M)(void*), void (*_copy_M)(void*, void*), 
                void (*_assign_M)(void*, void*), void (*_dtor_M)(void*), 
                bool (*_lt_M)(void*, void*), void (*_neg_M)(void*, void*), 
        void (*_ctor_M_zero)(void*, int), 
                void* m, void* _rtn ) {  // polymorphic parameter and return passed as void*
        // M zero = { 0 };
        void* zero = alloca(_sizeof_M);  // stack allocate 0 temporary
        _ctor_M_zero(zero, 0);  // initialize using zero_t constructor
        // return m < zero ? -m : m;
        void *_tmp = alloca(_sizeof_M)
        _copy_M( _rtn,  // copy-initialize return value
                _lt_M( m, zero ) ?  // check condition
                 (_neg_M(m, _tmp), _tmp) :  // negate m
                 m);
        _dtor_M(_tmp); _dtor_M(zero);  // destroy temporaries
}
\end{lstlisting}

Semantically, traits are simply a named lists of type assertions, but they may be used for many of the same purposes that interfaces in Java or abstract base classes in \CC{} are used for. Unlike Java interfaces or \CC{} base classes, \CFA{} types do not explicitly state any inheritance relationship to traits they satisfy; this can be considered a form of structural inheritance, similar to implementation of an interface in Go, as opposed to the nominal inheritance model of Java and \CC{}. Nominal inheritance can be simulated with traits using marker variables or functions:
\begin{lstlisting}
trait nominal(otype T) {
    T is_nominal;
};

int is_nominal;  // int now satisfies the nominal trait
{
    char is_nominal; // char satisfies the nominal trait
}
// char no longer satisfies the nominal trait here  
\end{lstlisting}

Traits, however, are significantly more powerful than nominal-inheritance interfaces; firstly, due to the scoping rules of the declarations that satisfy a trait's type assertions, a type may not satisfy a trait everywhere that the type is declared, as with @char@ and the @nominal@ trait above. Secondly, traits may be used to declare a relationship among multiple types, a property that may be difficult or impossible to represent in nominal-inheritance type systems:
\begin{lstlisting}
trait pointer_like(otype Ptr, otype El) {
    lvalue El *?(Ptr); // Ptr can be dereferenced into a modifiable value of type El
}

struct list {
    int value;
    list *next;  // may omit "struct" on type names
};

typedef list *list_iterator;

lvalue int *?( list_iterator it ) {
    return it->value;
}
\end{lstlisting}

In the example above, @(list_iterator, int)@ satisfies @pointer_like@ by the user-defined dereference function, and @(list_iterator, list)@ also satisfies @pointer_like@ by the built-in dereference operator for pointers. Given a declaration @list_iterator it@, @*it@ can be either an @int@ or a @list@, with the meaning disambiguated by context (\eg, @int x = *it;@ interprets @*it@ as an @int@, while @(*it).value = 42;@ interprets @*it@ as a @list@).
While a nominal-inheritance system with associated types could model one of those two relationships by making @El@ an associated type of @Ptr@ in the @pointer_like@ implementation, few such systems could model both relationships simultaneously.

\section{Generic Types}

The generic types design for \CFA{} must integrate efficiently and naturally with the existing polymorphic functions in \CFA{}, while retaining backwards compatibility with C; maintaining separate compilation is a particularly important constraint on the design. However, where the concrete parameters of the generic type are known, there should not be extra overhead for the use of a generic type.

A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration, and instantiated using a parenthesized list of types after the type name:
\begin{lstlisting}
forall(otype R, otype S) struct pair {
    R first;
    S second;
};

forall(otype T)
T value( pair(const char*, T) *p ) { return p->second; }

forall(dtype F, otype T)
T value_p( pair(F*, T*) p ) { return *p.second; }

pair(const char*, int) p = { "magic", 42 };
int magic = value( &p );

pair(void*, int*) q = { 0, &p.second };
magic = value_p( q );
double d = 1.0;
pair(double*, double*) r = { &d, &d };
d = value_p( r );
\end{lstlisting}

\CFA{} classifies generic types as either \emph{concrete} or \emph{dynamic}. Dynamic generic types vary in their in-memory layout depending on their type parameters, while concrete generic types have a fixed memory layout regardless of type parameters. A type may have polymorphic parameters but still be concrete; \CFA{} refers to such types as \emph{dtype-static}. Polymorphic pointers are an example of dtype-static types -- @forall(dtype T) T*@ is a polymorphic type, but for any @T@ chosen, @T*@ will have exactly the same in-memory representation as a @void*@, and can therefore be represented by a @void*@ in code generation.

The \CFA{} compiler instantiates concrete generic types by template-expanding them to fresh struct types; concrete generic types can therefore be used with zero runtime overhead. To enable interoperation between equivalent instantiations of a generic type, the compiler saves the set of instantiations currently in scope and re-uses the generated struct declarations where appropriate. As an example, the concrete instantiation for @pair(const char*, int)@ would look something like this:
\begin{lstlisting}
struct _pair_conc1 {
        const char* first;
        int second;
};
\end{lstlisting}

A concrete generic type with dtype-static parameters is also expanded to a struct type, but this struct type is used for all matching instantiations. In the example above, the @pair(F*, T*)@ parameter to @value_p@ is such a type; its expansion would look something like this, and be used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate:
\begin{lstlisting}
struct _pair_conc0 {
        void* first;
        void* second;
};
\end{lstlisting}

Though \CFA{} implements concrete generic types efficiently, it also has a fully-general system for computing with dynamic generic types. As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. Dynamic generic structs also come with an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0.}. Access to members\footnote{The \lstinline@offsetof@ macro is implmented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where neccessary.

\TODO{} Discuss caller-provided versus callee-provided offset arrays, layout functions.

Whether a type is concrete, dtype-static, or dynamic is decided based solely on the type parameters and @forall@ clause on the struct declaration. This allows opaque forward declarations of generic types like @forall(otype T) struct Box;@ -- like in C, all uses of @Box(T)@ can be in a separately compiled translation unit, and callers from other translation units will know the proper calling conventions to use. If the definition of a struct type was included in the determination of dynamic or concrete, some further types may be recognized as dtype-static (\eg, @forall(otype T) struct unique_ptr { T* p };@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in this way is judged to be an appropriate trade-off.

The re-use of dtype-static struct instantiations enables some useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T*@ as a type-checked replacement for @void*@, as in this example, which takes a @qsort@ or @bsearch@-compatible comparison routine and creates a similar lexicographic comparison for pairs of pointers:
\begin{lstlisting}
forall(dtype T)
int lexcmp( pair(T*, T*)* a, pair(T*, T*)* b, int (*cmp)(T*, T*) ) {
        int c = cmp(a->first, b->first);
        if ( c == 0 ) c = cmp(a->second, b->second);
        return c;
}
\end{lstlisting}
Since @pair(T*, T*)@ is a concrete type, there are no added implicit parameters to @lexcmp@, so the code generated by \CFA{} will be effectively identical to a version of this written in standard C using @void*@, yet the \CFA{} version will be type-checked to ensure that the fields of both pairs and the arguments to the comparison function match in type.

Another useful pattern enabled by re-used dtype-static type instantiations is zero-cost ``tag'' structs. Sometimes a particular bit of information is only useful for type-checking, and can be omitted at runtime. Tag structs can be used to provide this information to the compiler without further runtime overhead, as in the following example:
\begin{lstlisting}
forall(dtype Unit) struct scalar { unsigned long value; };

struct metres {};
struct litres {};

forall(dtype U)
scalar(U) ?+?(scalar(U) a, scalar(U) b) {
        return (scalar(U)){ a.value + b.value };
}

scalar(metres) half_marathon = { 21093 };
scalar(litres) swimming_pool = { 2500000 };

scalar(metres) marathon = half_marathon + half_marathon;
scalar(litres) two_pools = swimming_pool + swimming_pool;
marathon + swimming_pool; // ERROR -- caught by compiler
\end{lstlisting}
@scalar@ is a dtype-static type, so all uses of it will use a single struct definition, containing only a single @unsigned long@, and can share the same implementations of common routines like @?+?@ -- these implementations may even be separately compiled, unlike \CC{} template functions. However, the \CFA{} type-checker will ensure that matching types are used by all calls to @?+?@, preventing nonsensical computations like adding the length of a marathon to the volume of an olympic pool.

\section{Tuples}

\TODO{} Integrate Rob's work

\TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).

\section{Related Work}

\TODO{} Talk about \CC{}, Cyclone, maybe D, Rust, \etc{}

A major difference between the approaches of \CC{} and \CFA{} to polymorphism is that the set of assumed properties for a type is \emph{explicit} in \CFA{}. One of the major limiting factors of \CC{}'s approach is that templates cannot be separately compiled. In contrast, the explicit nature of assertions allows \CFA{}'s polymorphic functions to be separately compiled.

\section{Conclusion \& Future Work}

\TODO{} Among future work, talk about ideas for selectively template-expanding code (on decls for specific types, or on calls for accessible decls).

\bibliographystyle{ACM-Reference-Format}
\bibliography{generic_types}

\end{document}