Context Navigation

← Previous Change
Next Change →

Paper.tex

Timestamp:

Feb 16, 2018, 4:22:25 PM (8 years ago)

Author:

Rob Schluntz <rschlunt@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

5964127

Parents:

c71b256 (diff), 62cd621 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:/u/cforall/software/cfa/cfa-cc

File:

: 1 edited

doc/papers/general/Paper.tex (modified) (31 diffs)

Legend:

: Unmodified
: Added
: Removed

doc/papers/general/Paper.tex

-              rc71b256
+              r7c782af
 \usepackage{epic,eepic}
 \usepackage{xspace,calc,comment}
+\usepackage{upquote}                                                                    % switch curled `'" to straight
+\usepackage{listings}                                                                   % format program code
+\usepackage{upquote}                                            % switch curled `'" to straight
+\usepackage{listings}                                           % format program code
+\usepackage{enumitem}
+\usepackage[flushmargin]{footmisc}                      % support label/reference in footnote
 \usepackage{rotating}
 \usepackage[usenames]{color}
 \usepackage{pslatex}                                    % reduce size of san serif font
+\usepackage{pslatex}                                            % reduce size of san serif font
 \usepackage[plainpages=false,pdfpagelabels,pdfpagemode=UseNone,pagebackref=true,breaklinks=true,colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
 \setlength{\textheight}{9in}
 %\oddsidemargin 0.0in
 \renewcommand{\topfraction}{0.8}                % float must be greater than X of the page before it is forced onto its own page
 \renewcommand{\bottomfraction}{0.8}             % float must be greater than X of the page before it is forced onto its own page
 \renewcommand{\floatpagefraction}{0.8}  % float must be greater than X of the page before it is forced onto its own page
 \renewcommand{\textfraction}{0.0}               % the entire page maybe devoted to floats with no text on the page at all
 \lefthyphenmin=4                                                % hyphen only after 4 characters
+\renewcommand{\topfraction}{0.8}                        % float must be greater than X of the page before it is forced onto its own page
+\renewcommand{\bottomfraction}{0.8}                     % float must be greater than X of the page before it is forced onto its own page
+\renewcommand{\floatpagefraction}{0.8}          % float must be greater than X of the page before it is forced onto its own page
+\renewcommand{\textfraction}{0.0}                       % the entire page maybe devoted to floats with no text on the page at all
+\lefthyphenmin=4                                                        % hyphen only after 4 characters
 \righthyphenmin=4
 …
 \newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}\xspace} % Cforall symbolic name
 \newcommand{\CFA}{\protect\CFAIcon} % safe for section/caption
 \newcommand{\CFL}{\textrm{Cforall}\xspace} % Cforall symbolic name
 \newcommand{\Celeven}{\textrm{C11}\xspace} % C11 symbolic name
+\newcommand{\CFA}{\protect\CFAIcon}             % safe for section/caption
+\newcommand{\CFL}{\textrm{Cforall}\xspace}      % Cforall symbolic name
+\newcommand{\Celeven}{\textrm{C11}\xspace}      % C11 symbolic name
 \newcommand{\CC}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}\xspace} % C++ symbolic name
 \newcommand{\CCeleven}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}11\xspace} % C++11 symbolic name
 …
 \newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
 \newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
+\newlength{\gcolumnposn}                                        % temporary hack because lstlisting does not handle tabs correctly
 \newlength{\columnposn}
 \setlength{\gcolumnposn}{2.75in}
 …
 % Latin abbreviation
 \newcommand{\abbrevFont}{\textit}       % set empty for no italics
+\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
 \newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
 \newcommand*{\eg}{%
 …
 \newenvironment{cquote}{%
         \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=4pt\parsep=0pt\leftmargin=\parindent\rightmargin\leftmargin}%
+        \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=4pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%
         \item\relax
 }{%
 …
 \section{Introduction and Background}
+\section{Introduction}
 The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems to hobby projects.
 …
 The TIOBE~\cite{TIOBE} ranks the top 5 most popular programming languages as: Java 16\%, \Textbf{C 7\%}, \Textbf{\CC 5\%}, \Csharp 4\%, Python 4\% = 36\%, where the next 50 languages are less than 3\% each with a long tail.
 The top 3 rankings over the past 30 years are:
-\lstDeleteShortInline@%
 \begin{center}
 \setlength{\tabcolsep}{10pt}
+\lstDeleteShortInline@%
 \begin{tabular}{@{}rccccccc@{}}
                 & 2017  & 2012  & 2007  & 2002  & 1997  & 1992  & 1987          \\ \hline
 …
 \CC             & 3             & 3             & 3             & 3             & 2             & 2             & 4                     \\
 \end{tabular}
+\lstMakeShortInline@%
 \end{center}
-\lstMakeShortInline@%
 Love it or hate it, C is extremely popular, highly used, and one of the few systems languages.
 In many cases, \CC is often used solely as a better C.
 …
 The new constructs are empirically compared with both standard C and \CC; the results show the new design is comparable in performance.
+\subsection{Polymorphic Functions}
+\section{Polymorphic Functions}
+\CFA introduces both ad-hoc and parametric polymorphism to C, with a design originally formalized by Ditchfield~\cite{Ditchfield92}, and first implemented by Bilson~\cite{Bilson03}.
+\subsection{Name Overloading}
+C already has a limited form of ad-hoc polymorphism in the form of its basic arithmetic operators, which apply to a variety of different types using identical syntax.
+\CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable; Section~\ref{sec:libraries} includes a number of examples of how this overloading simplifies \CFA programming relative to C.
+Code generation for these overloaded functions and variables is implemented by the usual approach of mangling the identifier names to include a representation of their type, while \CFA decides which overload to apply based on the same ``usual arithmetic conversions'' used in C to disambiguate operator overloads.
+As an example:
+\begin{cfa}
+int max(int a, int b) { return a < b ? b : a; }  // (1)
+double max(double a, double b) { return a < b ? b : a; }  // (2)
+int max = INT_MAX;     // (3)
+double max = DBL_MAX;  // (4)
+max(7, -max);   $\C{// uses (1) and (3), by matching int from constant 7}$
+max(max, 3.14); $\C{// uses (2) and (4), by matching double from constant 3.14}$
+//max(max, -max);  $\C{// ERROR: ambiguous}$
+int m = max(max, -max); $\C{// uses (1) once and (3) twice, by matching return type}$
+\end{cfa}
+\Celeven did add @_Generic@ expressions, which can be used in preprocessor macros to provide a form of ad-hoc polymorphism; however, this polymorphism is both functionally and ergonomically inferior to \CFA name overloading.
+The macro wrapping the generic expression imposes some limitations; as an example, it could not implement the example above, because the variables @max@ would collide with the functions @max@.
+Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the functions dispatched to, which must all have distinct names.
+\subsection{\texorpdfstring{\LstKeywordStyle{forall} Functions}{forall Functions}}
 \label{sec:poly-fns}
-\CFA{}\hspace{1pt}'s polymorphism was originally formalized by Ditchfield~\cite{Ditchfield92}, and first implemented by Bilson~\cite{Bilson03}.
 The signature feature of \CFA is parametric-polymorphic functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a @forall@ clause (giving the language its name):
 \begin{lstlisting}
 …
 Crucial to the design of a new programming language are the libraries to access thousands of external software features.
 Like \CC, \CFA inherits a massive compatible library-base, where other programming languages must rewrite or provide fragile inter-language communication with C.
 A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted floating-point array:
+A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array:
 \begin{lstlisting}
 void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
 …
 int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
                                 *(double *)t2 < *(double *)t1 ? 1 : 0; }
 double key = 5.0, vals[10] = { /* 10 sorted floating-point values */ };
+double key = 5.0, vals[10] = { /* 10 sorted float values */ };
 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
 \end{lstlisting}
 …
 Hence, programmers can easily form local environments, adding and modifying appropriate functions, to maximize reuse of other existing functions and types.
+Finally, \CFA allows variable overloading:
+\begin{lstlisting}
+short int MAX = ...;   int MAX = ...;  double MAX = ...;
+short int s = MAX;    int i = MAX;    double d = MAX;   $\C{// select correct MAX}$
+\end{lstlisting}
+Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
+%% Redundant with Section~\ref{sec:libraries} %%
+% Finally, \CFA allows variable overloading:
+% \begin{lstlisting}
+% short int MAX = ...;   int MAX = ...;  double MAX = ...;
+% short int s = MAX;    int i = MAX;    double d = MAX;   $\C{// select correct MAX}$
+% \end{lstlisting}
+% Here, the single name @MAX@ replaces all the C type-specific names: @SHRT_MAX@, @INT_MAX@, @DBL_MAX@.
 \subsection{Traits}
 …
 In many languages, functions can return at most one value;
 however, many operations have multiple outcomes, some exceptional.
 Consider C's @div@ and @remquo@ functions, which return the quotient and remainder for a division of integer and floating-point values, respectively.
+Consider C's @div@ and @remquo@ functions, which return the quotient and remainder for a division of integer and float values, respectively.
 \begin{lstlisting}
 typedef struct { int quo, rem; } div_t;         $\C{// from include stdlib.h}$
 …
 \section{Control Structures}
+\CFA identifies missing and problematic control structures in C, and extends and modifies these control structures to increase functionality and safety.
 …
 The implicit targets of the current @continue@ and @break@, \ie the closest enclosing loop or @switch@, change as certain constructs are added or removed.
 \subsection{\texorpdfstring{Enhanced \LstKeywordStyle{switch} Statement}{Enhanced switch Statement}}
+\CFA also fixes a number of ergonomic defecits in the @switch@ statements of standard C.
+C can specify a number of equivalent cases by using the default ``fall-through'' semantics of @case@ clauses, \eg @case 1: case 2: case 3:@ -- this syntax is cluttered, however, so \CFA includes a more concise list syntax, @case 1, 2, 3:@.
+For contiguous ranges, \CFA provides an even more concise range syntax as well, @case 1~3:@; lists of ranges are also allowed in case selectors.
+There are a number of deficiencies with the C @switch@ statements: enumerating @case@ lists, placement of @case@ clauses, scope of the switch body, and fall through between case clauses.
+C has no shorthand for specifying a list of case values, whether the list is non-contiguous or contiguous\footnote{C provides this mechanism via fall through.}.
+\CFA provides a shorthand for a non-contiguous list:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+case 2, 10, 34, 42:
+\end{cfa}
+&
+\begin{cfa}
+case 2: case 10: case 34: case 42:
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+for a contiguous list:\footnote{gcc provides the same mechanism with awkward syntax, \lstinline@2 ... 42@, where spaces are required around the ellipse.}
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+case 2~42:
+\end{cfa}
+&
+\begin{cfa}
+case 2: case 3: ... case 41: case 42:
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+and a combination:
+\begin{cfa}
+case -12~-4, -1~5, 14~21, 34~42:
+\end{cfa}
+C allows placement of @case@ clauses \emph{within} statements nested in the @switch@ body (see Duff's device~\cite{Duff83});
+\begin{cfa}
+switch ( i ) {
+  case 0:
+        for ( int i = 0; i < 10; i += 1 ) {
+                ...
+  `case 1:`             // no initialization of loop index
+                ...
+        }
+}
+\end{cfa}
+\CFA precludes this form of transfer into a control structure because it causes undefined behaviour, especially with respect to missed initialization, and provides very limited functionality.
+C allows placement of declaration within the @switch@ body and unreachable code at the start, resulting in undefined behaviour:
+\begin{cfa}
+switch ( x ) {
+        `int y = 1;`                            $\C{// unreachable initialization}$
+        `x = 7;`                                        $\C{// unreachable code without label/branch}$
+  case 0:
+        ...
+        `int z = 0;`                            $\C{// unreachable initialization, cannot appear after case}$
+        z = 2;
+  case 1:
+        `x = z;`                                        $\C{// without fall through, z is undefined}$
+}
+\end{cfa}
+\CFA allows the declaration of local variables, \eg @y@, at the start of the @switch@ with scope across the entire @switch@ body, \ie all @case@ clauses, but no statements.
+\CFA disallows the declaration of local variable, \eg @z@, directly within the @switch@ body, because a declaration cannot occur immediately after a @case@ since a label can only be attached to a statement, and the use of @z@ is undefined in @case 1@ as neither storage allocation nor initialization may have occurred.
+C @switch@ provides multiple entry points into the statement body, but once an entry point is selected, control continues across \emph{all} @case@ clauses until the end of the @switch@ body, called \newterm{fall through};
+@case@ clauses are made disjoint by the @break@ statement.
+While the ability to fall through \emph{is} a useful form of control flow, it does not match well with programmer intuition, resulting in many errors from missing @break@ statements.
+\CFA provides a new control structure, @choose@, which mimics @switch@, but reverses the meaning of fall through:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+`choose` ( day ) {
+  case Mon~Thu:
+        // program
+  case Fri:
+        // program
+        wallet += pay;
+        `fallthrough;`
+  case Sat:
+        // party
+        wallet -= party;
+  case Sun:
+        // rest
+  default:
+        // error
+}
+\end{cfa}
+&
+\begin{cfa}
+switch ( day ) {
+  case Mon: case Tue: case Wed: case Thu:
+        // program
+        `break;`
+  case Fri:
+        // program
+        wallet += pay;
+  case Sat:
+        // party
+        wallet -= party;
+        `break;`
+  case Sun:
+        // rest
+        `break;`
+  default:
+        // error
+}
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+Collectively, these enhancements reduce programmer burden and increase readability and safety.
+\begin{comment}
 Forgotten @break@ statements at the end of @switch@ cases are a persistent sort of programmer error in C, and the @break@ statements themselves introduce visual clutter and an un-C-like keyword-based block delimiter.
 \CFA addresses this error by introducing a @choose@ statement, which works identically to a @switch@ except that its default end-of-case behaviour is to break rather than to fall through for all non-empty cases.
 …
+}
 \end{cfa}
+\end{comment}
 \subsection{\texorpdfstring{\LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}}
 …
 \end{cfa}
+\subsection{Exception Handling ???}
+% \subsection{Exception Handling ???}
 \section{Declarations}
 …
 \lstDeleteShortInline@%
 \lstset{moredelim=**[is][\color{blue}]{+}{+}}
 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
 \begin{cfa}
 +[5] *+ `int` x1;
 +* [5]+ `int` x2;
 +[* [5] int]+ f`( int p )`;
+`[* [5] int]` f+( int p )+;
 \end{cfa}
+&
 …
 `int` +*+ x1 +[5]+;
 `int` +(*+x2+)[5]+;
 +int (*+f`( int p )`+)[5]+;
+`int (*`f+( int p )+`)[5]`;
 \end{cfa}
 \end{tabular}
 …
 \begin{cquote}
 \lstDeleteShortInline@%
 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
 \begin{cfa}
 `*` int x, y;
 …
 \begin{cquote}
 \lstDeleteShortInline@%
 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
 \begin{cfa}
 `*` int x;
 …
 \begin{cquote}
 \lstDeleteShortInline@%
 \begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{C}} \\
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{C}}      \\
 \begin{cfa}
 [ 5 ] int z;
 …
 \begin{cquote}
 \lstDeleteShortInline@%
 \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}}
 \multicolumn{1}{c@{\hspace{1em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{1em}}}{\textbf{C}} \\
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{C}}      \\
 \begin{cfa}
 const * const int x;
 …
 \begin{cquote}
 \lstDeleteShortInline@%
 \begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{C}} \\
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{C}}      \\
 \begin{cfa}
 extern [ 5 ] int x;
 …
 \begin{cquote}
 \lstDeleteShortInline@%
 \begin{tabular}{@{}l@{\hspace{3em}}l@{}}
 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
 \begin{cfa}
 y = (* int)x;
 …
 Therefore, a programmer has the option of either continuing to use traditional C declarations or take advantage of the new style.
 Clearly, both styles need to be supported for some time due to existing C-style header-files, particularly for UNIX-like systems.
+The syntax of the new routine prototype declaration follows directly from the new routine definition syntax;
+as well, parameter names are optional, \eg:
+\begin{cfa}
+[ int x ] f ();                                                 $\C{// returning int with no parameters}$
+[ * int ] g (int y);                                    $\C{// returning pointer to int with int parameter}$
+[ ] h ( int, char );                                    $\C{// returning no result with int and char parameters}$
+[ * int, int ] j ( int );                               $\C{// returning pointer to int and int, with int parameter}$
+\end{cfa}
+This syntax allows a prototype declaration to be created by cutting and pasting source text from the routine definition header (or vice versa).
+Like C, it is possible to declare multiple routine-prototypes in a single declaration, where the return type is distributed across \emph{all} routine names in the declaration list, \eg:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+[double] foo(), foo( int ), foo( double ) {...}
+\end{cfa}
+&
+\begin{cfa}
+double foo1(), foo2( int ), foo3( double );
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+\CFA allows the last routine in the list to define its body.
+Declaration qualifiers can only appear at the start of a \CFA routine declaration,\footref{StorageClassSpecifier} \eg:
+\begin{cfa}
+extern [ int ] f ( int );
+static [ int ] g ( int );
+\end{cfa}
+The syntax for pointers to \CFA routines specifies the pointer name on the right, \eg:
+\begin{cfa}
+* [ int x ] () fp;                                              $\C{// pointer to routine returning int with no parameters}$
+* [ * int ] (int y) gp;                                 $\C{// pointer to routine returning pointer to int with int parameter}$
+* [ ] (int,char) hp;                                    $\C{// pointer to routine returning no result with int and char parameters}$
+* [ * int,int ] ( int ) jp;                             $\C{// pointer to routine returning pointer to int and int, with int parameter}$
+\end{cfa}
+While parameter names are optional, \emph{a routine name cannot be specified};
+for example, the following is incorrect:
+\begin{cfa}
+* [ int x ] f () fp;                                    $\C{// routine name "f" is not allowed}$
+\end{cfa}
 …
 In addition to the expressive power, \lstinline|@=| provides a simple path for migrating legacy C code to \CFA, by providing a mechanism to incrementally convert initializers; the \CFA design team decided to introduce a new syntax for this escape hatch because we believe that our RAII implementation will handle the vast majority of code in a desirable way, and we wished to maintain familiar syntax for this common case.
+\subsection{Type Nesting}
+\CFA allows \newterm{type nesting}, and type qualification of the nested types (see Figure~\ref{f:TypeNestingQualification}), where as C hoists (refactors) nested types into the enclosing scope and has no type qualification.
+\begin{figure}
+\centering
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{3em}}l|l@{}}
+\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C Type Nesting}}      & \multicolumn{1}{c}{\textbf{C Implicit Hoisting}}      & \multicolumn{1}{|c}{\textbf{\CFA}}    \\
+\hline
+\begin{cfa}
+struct S {
+        enum C { R, G, B };
+        struct T {
+                union U { int i, j; };
+                enum C c;
+                short int i, j;
+        };
+        struct T t;
+} s;
+int rtn() {
+        s.t.c = R;
+        struct T t = { R, 1, 2 };
+        enum C c;
+        union U u;
+}
+\end{cfa}
+&
+\begin{cfa}
+enum C { R, G, B };
+union U { int i, j; };
+struct T {
+        enum C c;
+        short int i, j;
+};
+struct S {
+        struct T t;
+} s;
+\end{cfa}
+&
+\begin{cfa}
+struct S {
+        enum C { R, G, B };
+        struct T {
+                union U { int i, j; };
+                enum C c;
+                short int i, j;
+        };
+        struct T t;
+} s;
+int rtn() {
+        s.t.c = `S.`R;  // type qualification
+        struct `S.`T t = { `S.`R, 1, 2 };
+        enum `S.`C c;
+        union `S.T.`U u;
+}
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\caption{Type Nesting / Qualification}
+\label{f:TypeNestingQualification}
+\end{figure}
+In the left example in C, types @C@, @U@ and @T@ are implicitly hoisted outside of type @S@ into the containing block scope.
+In the right example in \CFA, the types are not hoisted and accessed using the field-selection operator ``@.@'' for type qualification, as does Java, rather than the \CC type-selection operator ``@::@''.
 \subsection{Default Parameters}
 …
 \section{Literals}
 C already includes limited polymorphism for literals -- @0@ can be either an integer or a pointer literal, depending on context, while the syntactic forms of literals of the various integer and floating-point types are very similar, differing from each other only in suffix.
+C already includes limited polymorphism for literals -- @0@ can be either an integer or a pointer literal, depending on context, while the syntactic forms of literals of the various integer and float types are very similar, differing from each other only in suffix.
 In keeping with the general \CFA approach of adding features while respecting ``the C way'' of doing things, we have extended both C's polymorphic zero and typed literal syntax to interoperate with user-defined types, while maintaining a backwards-compatible semantics.
 …
 struct Weight { double stones; };
 void ?{}( Weight & w ) { w.stones = 0; } $\C{// operations}$
+void ?{}( Weight & w ) { w.stones = 0; }        $\C{// operations}$
 void ?{}( Weight & w, double w ) { w.stones = w; }
 Weight ?+?( Weight l, Weight r ) { return (Weight){ l.stones + r.stones }; }
 …
 int main() {
         Weight w, hw = { 14 };                  $\C{// 14 stone}$
+        Weight w, hw = { 14 };                                  $\C{// 14 stone}$
         w = 11@`st@ + 1@`lb@;
         w = 70.3@`kg@;
         w = 155@`lb@;
         w = 0x_9b_u@`lb@;                               $\C{// hexadecimal unsigned weight (155)}$
         w = 0_233@`lb@;                                 $\C{// octal weight (155)}$
+        w = 0x_9b_u@`lb@;                                               $\C{// hexadecimal unsigned weight (155)}$
+        w = 0_233@`lb@;                                                 $\C{// octal weight (155)}$
         w = 5@`st@ + 8@`kg@ + 25@`lb@ + hw;
+}
 \end{cfa}
 }%
+\section{Libraries}
+\label{sec:libraries}
+As stated in Section~\ref{sec:poly-fns}, \CFA inherits a large corpus of library code, where other programming languages must rewrite or provide fragile inter-language communication with C.
+\CFA has replacement libraries condensing hundreds of existing C names into tens of \CFA overloaded names, all without rewriting the actual computations.
+In many cases, the interface is an inline wrapper providing overloading during compilation but zero cost at runtime.
+The following sections give a glimpse of the interface reduction to many C libraries.
+In many cases, @signed@/@unsigned@ @char@ and @short@ routines are available (but not shown) to ensure expression computations remain in a single type, as conversions can distort results.
+\subsection{Limits}
+C library @limits.h@ provides lower and upper bound constants for the basic types.
+\CFA name overloading is used to condense these typed constants, \eg:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{Definition}}       & \multicolumn{1}{c}{\textbf{Usage}}    \\
+\begin{cfa}
+const short int `MIN` = -32768;
+const int `MIN` = -2147483648;
+const long int `MIN` = -9223372036854775808L;
+\end{cfa}
+&
+\begin{cfa}
+short int si = `MIN`;
+int i = `MIN`;
+long int li = `MIN`;
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+The result is a significant reduction in names to access typed constants, \eg:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+MIN
+MAX
+M_PI
+M_E
+\end{cfa}
+&
+\begin{cfa}
+SCHAR_MIN, CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN,
+SCHAR_MAX, UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX,
+M_PI, M_PIl, M_CPI, M_CPIl,
+M_E, M_El, M_CE, M_CEl
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+\subsection{Math}
+C library @math.h@ provides many mathematical routines.
+\CFA routine overloading is used to condense these mathematical routines, \eg:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{Definition}}       & \multicolumn{1}{c}{\textbf{Usage}}    \\
+\begin{cfa}
+float `log`( float x );
+double `log`( double );
+double _Complex `log`( double _Complex x );
+\end{cfa}
+&
+\begin{cfa}
+float f = `log`( 3.5 );
+double d = `log`( 3.5 );
+double _Complex dc = `log`( 3.5+0.5I );
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+The result is a significant reduction in names to access math routines, \eg:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+log
+sqrt
+sin
+\end{cfa}
+&
+\begin{cfa}
+logf, log, logl, clogf, clog, clogl
+sqrtf, sqrt, sqrtl, csqrtf, csqrt, csqrtl
+sinf, sin, sinl, csinf, csin, csinl
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+While \Celeven has type-generic math~\cite[\S~7.25]{C11} in @tgmath.h@ to provide a similar mechanism, these macros are limited, matching a routine name with a single set of floating type(s).
+For example, it is not possible to overload @atan@ for both one and two arguments;
+instead the names @atan@ and @atan2@ are required.
+The key observation is that only a restricted set of type-generic macros are provided for a limited set of routine names, which do not generalize across the type system, as in \CFA.
+\subsection{Standard}
+C library @stdlib.h@ provides many general routines.
+\CFA routine overloading is used to condense these utility routines, \eg:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{Definition}}       & \multicolumn{1}{c}{\textbf{Usage}}    \\
+\begin{cfa}
+unsigned int `abs`( int );
+double `abs`( double );
+double abs( double _Complex );
+\end{cfa}
+&
+\begin{cfa}
+unsigned int i = `abs`( -1 );
+double d = `abs`( -1.5 );
+double d = `abs`( -1.5+0.5I );
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+The result is a significant reduction in names to access utility routines, \eg:
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+abs
+strto
+random
+\end{cfa}
+&
+\begin{cfa}
+abs, labs, llabs, fabsf, fabs, fabsl, cabsf, cabs, cabsl
+strtol, strtoul, strtoll, strtoull, strtof, strtod, strtold
+srand48, mrand48, lrand48, drand48
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+In additon, there are polymorphic routines, like @min@ and @max@, which work on any type with operators @?<?@ or @?>?@.
+The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety.
+C/\Celeven provide a number of complex and overlapping storage-management operation to support the following capabilities:
+\begin{description}[itemsep=2pt,parsep=0pt]
+\item[fill]
+after allocation the storage is filled with a specified character.
+\item[resize]
+an existing allocation is decreased or increased in size.
+In either case, new storage may or may not be allocated and, if there is a new allocation, as much data from the existing allocation is copied.
+For an increase in storage size, new storage after the copied data may be filled.
+\item[alignment]
+an allocation starts on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes.
+\item[array]
+the allocation size is scaled to the specified number of array elements.
+An array may be filled, resized, or aligned.
+\end{description}
+Table~\ref{t:StorageManagementOperations} shows the capabilities provided by C/\Celeven allocation-routines and how all the capabilities can be combined into two \CFA routines.
+\CFA storage-management routines extend the C equivalents by overloading, providing shallow type-safety, and removing the need to specify the base allocation-size.
+The following example contrasts \CFA and C storage-allocation operation performing the same operations with the same type safety:
+\begin{cquote}
+\begin{cfa}[aboveskip=0pt]
+size_t  dim = 10;                                                       $\C{// array dimension}$
+char fill = '\xff';                                                     $\C{// initialization fill value}$
+int * ip;
+\end{cfa}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{C}}        \\
+\begin{cfa}
+ip = alloc();
+ip = alloc( fill );
+ip = alloc( dim );
+ip = alloc( dim, fill );
+ip = alloc( ip, 2 * dim );
+ip = alloc( ip, 4 * dim, fill );
+ip = align_alloc( 16 );
+ip = align_alloc( 16, fill );
+ip = align_alloc( 16, dim );
+ip = align_alloc( 16, dim, fill );
+\end{cfa}
+&
+\begin{cfa}
+ip = (int *)malloc( sizeof( int ) );
+ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, sizeof( int ) );
+ip = (int *)malloc( dim * sizeof( int ) );
+ip = (int *)malloc( sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
+ip = (int *)realloc( ip, 2 * dim * sizeof( int ) );
+ip = (int *)realloc( ip, 4 * dim * sizeof( int ) ); memset( ip, fill, 4 * dim * sizeof( int ) );
+ip = memalign( 16, sizeof( int ) );
+ip = memalign( 16, sizeof( int ) ); memset( ip, fill, sizeof( int ) );
+ip = memalign( 16, dim * sizeof( int ) );
+ip = memalign( 16, dim * sizeof( int ) ); memset( ip, fill, dim * sizeof( int ) );
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+Variadic @new@ (see Section~\ref{sec:variadic-tuples}) cannot support the same overloading because extra parameters are for initialization.
+Hence, there are @new@ and @anew@ routines for single and array variables, and the fill value is the arguments to the constructor, \eg:
+\begin{cfa}
+struct S { int i, j; };
+void ?{}( S & s, int i, int j ) { s.i = i; s.j = j; }
+S * s = new( 2, 3 );                                            $\C{// allocate storage and run constructor}$
+S * as = anew( dim, 2, 3 );                                     $\C{// each array element initialized to 2, 3}$
+\end{cfa}
+Note, \CC can only initialization array elements via the default constructor.
+Finally, the \CFA memory-allocator has \newterm{sticky properties} for dynamic storage: fill and alignment are remembered with an object's storage in the heap.
+When a @realloc@ is performed, the sticky properties are respected, so that new storage is correctly aligned and initialized with the fill character.
+\begin{table}
+\centering
+\lstDeleteShortInline@%
+\lstMakeShortInline~%
+\begin{tabular}{@{}r|r|l|l|l|l@{}}
+\multicolumn{1}{c}{}&           & \multicolumn{1}{c|}{fill}     & resize        & alignment     & array \\
+\hline
+C               & ~malloc~                      & no                    & no            & no            & no    \\
+                & ~calloc~                      & yes (0 only)  & no            & no            & yes   \\
+                & ~realloc~                     & no/copy               & yes           & no            & no    \\
+                & ~memalign~            & no                    & no            & yes           & no    \\
+                & ~posix_memalign~      & no                    & no            & yes           & no    \\
+\hline
+C11             & ~aligned_alloc~       & no                    & no            & yes           & no    \\
+\hline
+\CFA    & ~alloc~                       & yes/copy              & no/yes        & no            & yes   \\
+                & ~align_alloc~         & yes                   & no            & yes           & yes   \\
+\end{tabular}
+\lstDeleteShortInline~%
+\lstMakeShortInline@%
+\caption{Storage-Management Operations}
+\label{t:StorageManagementOperations}
+\end{table}
+\subsection{I/O}
+\label{s:IOLibrary}
+The goal of \CFA I/O is to simplify the common cases, while fully supporting polymorphism and user defined types in a consistent way.
+The approach combines ideas from \CC and Python.
+The \CFA header file for the I/O library is @fstream@.
+The common case is printing out a sequence of variables separated by whitespace.
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{\CC}}      \\
+\begin{cfa}
+int x = 1, y = 2, z = 3;
+sout | x `|` y `|` z | endl;
+\end{cfa}
+&
+\begin{cfa}
+cout << x `<< " "` << y `<< " "` << z << endl;
+\end{cfa}
+\\
+\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
+` `2` `3
+\end{cfa}
+&
+\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
+2 3
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+The \CFA form has half the characters of the \CC form, and is similar to Python I/O with respect to implicit separators.
+Similar simplification occurs for tuple I/O, which prints all tuple values separated by ``\lstinline[showspaces=true]@, @''.
+\begin{cfa}
+[int, [ int, int ] ] t1 = [ 1, [ 2, 3 ] ], t2 = [ 4, [ 5, 6 ] ];
+sout | t1 | t2 | endl;                                  $\C{// print tuples}$
+\end{cfa}
+\begin{cfa}[showspaces=true,aboveskip=0pt]
+`, `2`, `3 4`, `5`, `6
+\end{cfa}
+Finally, \CFA uses the logical-or operator for I/O as it is the lowest-priority overloadable operator, other than assignment.
+Therefore, fewer output expressions require parenthesis.
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}ll@{}}
+\textbf{\CFA:}
+&
+\begin{cfa}
+sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
+\end{cfa}
+\\
+\textbf{\CC:}
+&
+\begin{cfa}
+cout << x * 3 << y + 1 << `(`z << 2`)` << `(`x == y`)` << (x | y) << (x || y) << (x > z ? 1 : 2) << endl;
+\end{cfa}
+\\
+\textbf{output:}
+&
+\begin{cfa}[showspaces=true,aboveskip=0pt]
+3 12 0 3 1 2
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
+There is a weak similarity between the \CFA logical-or operator and the Shell pipe-operator for moving data, where data flows in the correct direction for input but the opposite direction for output.
+The implicit separator character (space/blank) is a separator not a terminator.
+The rules for implicitly adding the separator are:
+\begin{itemize}[itemsep=2pt,parsep=0pt]
+\item
+A separator does not appear at the start or end of a line.
+\item
+A separator does not appear before or after a character literal or variable.
+\item
+A separator does not appear before or after a null (empty) C string, which is a local mechanism to disable insertion of the separator character.
+\item
+A separator does not appear before a C string starting with the characters: \lstinline[mathescape=off,basicstyle=\tt]@([{=$@
+\item
+A seperator does not appear after a C string ending with the characters: \lstinline[basicstyle=\tt]@,.;!?)]}%@
+\item
+{\lstset{language=CFA,deletedelim=**[is][]{`}{`}}
+A seperator does not appear before or after a C string begining/ending with the quote or whitespace characters: \lstinline[basicstyle=\tt,showspaces=true]@`'": \t\v\f\r\n@
+}%
+\item
+There are routines to set and get the separator string, and manipulators to toggle separation on and off in the middle of output.
+\end{itemize}
+\subsection{Multi-precision Integers}
+\label{s:MultiPrecisionIntegers}
+\CFA has an interface to the GMP multi-precision signed-integers~\cite{GMP}, similar to the \CC interface provided by GMP.
+The \CFA interface wraps GMP routines into operator routines to make programming with multi-precision integers identical to using fixed-sized integers.
+The \CFA type name for multi-precision signed-integers is @Int@ and the header file is @gmp@.
+The following multi-precision factorial programs contrast using GMP with the \CFA and C interfaces.
+\begin{cquote}
+\lstDeleteShortInline@%
+\begin{tabular}{@{}l@{\hspace{\parindentlnth}}@{\hspace{\parindentlnth}}l@{}}
+\multicolumn{1}{c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}     & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}}      \\
+\begin{cfa}
+#include <gmp>
+int main( void ) {
+        sout | "Factorial Numbers" | endl;
+        Int fact = 1;
+        sout | 0 | fact | endl;
+        for ( unsigned int i = 1; i <= 40; i += 1 ) {
+                fact *= i;
+                sout | i | fact | endl;
+        }
+}
+\end{cfa}
+&
+\begin{cfa}
+#include <gmp.h>
+int main( void ) {
+        `gmp_printf`( "Factorial Numbers\n" );
+        `mpz_t` fact;
+        `mpz_init_set_ui`( fact, 1 );
+        `gmp_printf`( "%d %Zd\n", 0, fact );
+        for ( unsigned int i = 1; i <= 40; i += 1 ) {
+                `mpz_mul_ui`( fact, fact, i );
+                `gmp_printf`( "%d %Zd\n", i, fact );
+        }
+}
+\end{cfa}
+\end{tabular}
+\lstMakeShortInline@%
+\end{cquote}
 \section{Evaluation}
 …
 \begin{table}
+\centering
 \caption{Properties of benchmark code}
 \label{tab:eval}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 7c782af for doc/papers/general/Paper.tex

Legend:

doc/papers/general/Paper.tex

Download in other formats: