source: doc/user/user.tex @ 8a63547

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -*- Mode: Latex -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 
%% Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
%%
%% The contents of this file are covered under the licence agreement in the
%% file "LICENCE" distributed with Cforall.
%% 
%% user.tex -- 
%% 
%% Author           : Peter A. Buhr
%% Created On       : Wed Apr  6 14:53:29 2016
%% Last Modified By : Peter A. Buhr
%% Last Modified On : Tue May  3 08:05:33 2016
%% Update Count     : 246
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% requires tex packages: texlive-base texlive-latex-base tex-common texlive-humanities texlive-latex-extra texlive-fonts-recommended

% inline code ©...© (copyright symbol) emacs: C-q M-)
% red highlighting ®...® (registered trademark sumbol) emacs: C-q M-.
% latex escape §...§ (section symbol) emacs: C-q M-'
% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
% math escape $...$ (dollar symbol)

\documentclass[openright,twoside]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Latex packages used in the document.
\usepackage[T1]{fontenc}                                % allow Latin1 (extended ASCII) characters
\usepackage{textcomp}
\usepackage[latin1]{inputenc}
\usepackage{upquote}
\usepackage{fullpage,times}
\usepackage{epic,eepic}
\usepackage{xspace}
\usepackage{varioref}
\usepackage{listings}
\usepackage{footmisc}
\usepackage{comment}
\usepackage{latexsym}                                   % \Box
\usepackage{mathptmx}                                   % better math font with "times"
\usepackage[pagewise]{lineno}
\renewcommand{\linenumberfont}{\scriptsize\sffamily}
\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
\usepackage{breakurl}
\renewcommand{\UrlFont}{\small\sf}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Bespoke macros used in the document.
\input{common}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Names used in the document.

\newcommand{\Version}{1.0.0}
\newcommand{\CS}{C\raisebox{-0.9ex}{\large$^\sharp$}\xspace}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\setcounter{secnumdepth}{3}                             % number subsubsections
\setcounter{tocdepth}{3}                                % subsubsections in table of contents
\makeindex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\pagestyle{headings}
\linenumbers                                            % comment out to turn off line numbering

\title{\Huge
\vspace*{1in}
\CFA (\CFL) User Manual                         \\
Version 1.0                                                     \\
\vspace*{0.25in}
\huge``describe not prescribe''         \\
\vspace*{1in}
}% title
\author{\huge
Peter A. Buhr and ...                           \\
}% author
\date{
DRAFT \\
\today
}% date

\pagenumbering{roman}
\pagestyle{plain}

\maketitle

\vspace*{\fill}
\thispagestyle{empty}
\noindent
\copyright\,2016 \CFA Project \\ \\
\noindent
This work is licensed under the Creative Commons Attribution 4.0 International License.
To view a copy of this license, visit {\small\url{http://creativecommons.org/licenses/by/4.0}}.
\vspace*{1in}

\clearpage
\pdfbookmark[1]{Contents}{section}
\tableofcontents

\clearpage
\pagenumbering{arabic}


\section{Introduction}

\CFA\footnote{Pronounced ``C-for-all'', and written \CFA, CFA, or \CFL.} is a modern general-purpose programming-language, designed an as evolutionary step forward from the C programming language.
The syntax of the \CFA language builds from C, and should look immediately familiar to C programmers.
% Any language feature that is not described here can be assumed to be using the standard C11 syntax.
\CFA adds many modern programming-language features, which directly leads to increased safety and productivity, while maintaining interoperability with existing C programs and achieving C performance.
Like C, \CFA is a statically typed, procedural language with a low-overhead runtime, meaning there is no global garbage-collection.
The primary new features include parametric-polymorphism routines and types, exceptions, concurrency, and modules.

One of the main design philosophies of \CFA is to ``describe not prescribe'', which means \CFA tries to provide a pathway from low-level C programming to high-level \CFA programming, but it does not force programmers to ``do the right thing''.
Programmers can cautiously add \CFA extensions to their C programs in any order and at any time to incrementally move towards safer, higher-level programming features.
A programmer is always free to reach back to C from \CFA for any reason, and in many cases, new \CFA features have a fallback to a C mechanism.
There is no notion or requirement for rewriting a legacy C program in \CFA;
instead, a programmer evolves an existing C program into \CFA by incrementally incorporating \CFA features.
New programs can be written in \CFA using a combination of C and \CFA features.
\CC had a similar goal 30 years ago, but has struggled over the intervening time to incorporate modern programming-language features because of early design choices.
\CFA has 30 years of hindsight and clean starting point.

Like \CC, there may be both an old and new ways to achieve the same effect.
For example, the following programs compare the \CFA and C I/O mechanisms.
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c}{\textbf{C}}        \\
\begin{lstlisting}
#include <fstream>
int main( void ) {
        int x = 0, y = 1, z = 2;
        sout | x | y | z | endl;
}
\end{lstlisting}
&
\begin{lstlisting}
#include <stdio.h>
int main( void ) {
        int x = 0, y = 1, z = 2;
        printf( "%d %d %d\n", x, y, z );
}
\end{lstlisting}
\end{tabular}
\end{quote2}
Both programs output the same result.
While the \CFA I/O looks similar to the \CC output style, there are several important differences, such as automatic spacing between variables as in Python (see also~\VRef{s:IOLibrary}).

This document is a reference manual for the \CFA programming language, targeted at \CFA programmers.
Implementers may refer to the \CFA Programming Language Specification for details about the language syntax and semantics.
In its current state, this document covers the intended core features of the language.
Changes to the syntax and additional features are expected to be included in later revisions.
% For additional information, see \url{http://wiki.do-lang.org}.


\section{History}

The \CFA project started with K-W C~\cite{Till89,Buhr94a}, which extended C with new declaration syntax, multiple return values from routines, and extended assignment capabilities using the notion of tuples.
(See~\cite{Werther96} for some similar work, but for \CC.)
The original \CFA project~\cite{Ditchfield92} extended the C type system with parametric polymorphism and overloading, as opposed to the \CC approach of object-oriented extensions to the C type-system.
A first implementation of the core Cforall language was created~\cite{Bilson03,Esteves04}, but at the time there was little interesting in extending C, so work did not continue.
As the saying goes, ``What goes around, comes around'', and there is now renewed interest in the C programming language because of legacy code-bases, so the \CFA project has been restarted.


\section{Why fix C?}

Even with all its problems, C is a very popular programming language because it allows writing software at virtually any level in a computer system without restriction.
For systems programming, where direct access to hardware and dealing with real-time issues is a requirement, C is usually the language of choice.
As well, there are millions of lines of C legacy code, forming the base for many software development projects (especially on UNIX systems).
The TIOBE index (\url{http://www.tiobe.com/tiobe_index}) for March 2016 shows programming-language popularity, with Java 20.5\%, C 14.5\%, \CC 6.7\%, \CS 4.3\%, Python 4.3\%, and all other programming languages below 3\%.
Hence, C is still an extremely important programming language, with double the usage of \CC, where \CC itself is largely C code.
Finally, love it or hate it, C has been an important and influential part of computer science for 40 years and it appears it will continue to be for many more years.
Unfortunately, C has too many problems and omissions to make it an acceptable programming language for modern needs.

The goal of this project is to engineer modern language features into C in an evolutionary rather than revolutionary way.
\CC~\cite{c++,ANSI14:C++} is an example of a similar project;
however, it largely extended the language, and did not address existing problems.\footnote{%
Two important existing problems addressed were changing the type of character literals from ©int© to ©char© and enumerator from ©int© to the type of its enumerators.}
Fortran~\cite{Fortran08}, Ada~\cite{Ada12}, and Cobol~\cite{Cobol14} are examples of programming languages that took an evolutionary approach, where modern language features are added and problems fixed within the framework of the existing language.
Java~\cite{Java8}, Go~\cite{Go}, Rust~\cite{Rust} and D~\cite{D} are examples of the revolutionary approach for modernizing C/\CC, resulting in a new language rather than an extension of the descendent.
These languages have different syntax and semantics from C, and do not interoperate directly with C, largely because of garbage collection.
As a result, there is a significant learning curve to move to these languages, and C legacy-code must be rewritten.
These costs can be prohibitive for many companies with a large software base in C/\CC, and many programmers that require retraining to a new programming language.

The result of this project is a language that is largely backwards compatible with C11~\cite{C11}, but containing many modern language features and fixing some of the well known C problems.
Without significant extension to the C programming language, C will be unable to cope with the needs of modern programming problems and programmers;
as a result, it will fade into disuse.
Considering the large body of existing C code and programmers, there is significant impetus to ensure C is transformed into a modern programming language.
While C11 made a few simple extensions to the language, nothing was added to address existing problems in the language or to augment the language with modern language features.
While some may argue that modern language features may make C complex and inefficient, it is clear a language without modern capabilities is insufficient for the advanced programming problems existing today.


\section{Interoperability}

\CFA is designed to integrate well with existing C programs and libraries.
The most important feature of interoperability is to use the same calling conventions, so there is no overhead to call existing C routines.
This feature allows users of \CFA to take advantage of the existing panoply of C libraries from inside their \CFA code.
In fact, one of the biggest issues for any new programming language is establishing a minimum level of library code to support a large body of activities.
Programming-language developers often state that adequate library support takes more work than designing and implementing the language itself.
Like \CC, \CFA starts with immediate access to all exiting C libraries, and in many cases, can easily wrap library routines with simpler and safer interfaces, at very low cost.

However, it is necessary to differentiate between C and \CFA code because of name overloading, as for \CC.
For example, the C math-library provides the following routines for computing the absolute value of the basic type: ©abs©, ©labs©, ©llabs©, ©fabs©, ©fabsf©, ©fabsl©, ©cabsf©, ©cabs©, and ©cabsl©.
Whereas, \CFA wraps each of these routines into one with the common name ©abs©.
\begin{lstlisting}
char abs( char );
extern "C" {
int abs( int );                         // use default C routine for int
} // extern "C"
long int abs( long int );
long long int abs( long long int );
float abs( float );
double abs( double );
long double abs( long double );
float _Complex abs( float _Complex );
double _Complex abs( double _Complex );
long double _Complex abs( long double _Complex );
\end{lstlisting}
The problem is the name clash between the library routine ©abs© and the \CFA names ©abs©.
Hence, names appearing in an ©extern "C"© block have \newterm{C linkage}.
Then overloading polymorphism uses a mechanism called \newterm{name mangling} to create unique names that are different from C names, which are not mangled.
Hence, there is the same need as in \CC, to know if a name is a C or \CFA name, so it can be correctly formed.
There is no way around this problem, other than C's approach of creating unique names for each pairing of operation and type.
This example strongly illustrates a core idea in \CFA: \emph{the power of a name}.
The name ``©abs©'' evokes the notion of absolute value, and many mathematical types provide the notion of absolute value.
Hence, knowing the name ©abs© should be sufficient to apply it to any type where it is applicable.
The time savings and safety of using one name uniformly versus $N$ unique names should not be underestimated.


\section[Compiling CFA Program]{Compiling \CFA Program}

The command ©cfa© is used to compile \CFA program(s).
This command works like the GNU ©gcc©\index{gcc} command, e.g.:
\begin{lstlisting}
cfa§\indexc{cfa}\index{compilation!cfa@©cfa©}§ [ gcc-options ] C/§\CFA§-files [ assembler/loader-files ]
\end{lstlisting}
By default, \CFA programs having the following ©gcc© flags turned on:
\begin{description}
\item\hspace*{-4pt}\Indexc{-std=gnu99}\index{compilation option!-std=gnu99@{©-std=gnu99©}}
The 1999 C standard plus GNU extensions.
\item\hspace*{-4pt}\Indexc{-fgnu89-¶inline¶}\index{compilation option!-fgnu89-inline@{©-fgnu89-¶inline¶©}}
Use the traditional GNU semantics for inline routines in C99 mode.
\end{description}
The following new \CFA option is available:
\begin{description}
\item\hspace*{-4pt}\Indexc{-CFA}\index{compilation option!-CFA@{©-CFA©}}
Only the C preprocessor and the \CFA translator steps are performed and the transformed program is written to standard output, which makes it possible to examine the code generated by the \CFA translator.
\end{description}

The following preprocessor variables are available:
\begin{description}
\item\hspace*{-4pt}\Indexc{__CFA__}\index{preprocessor variables!__CFA__@{©__CFA__©}}
is always available during preprocessing and its value is the current major \Index{version number} of \CFA.\footnote{
The C preprocessor allows only integer values in a preprocessor variable so a value like ``\Version'' is not allowed.
Hence, the need to have three variables for the major, minor and patch version number.}

\item\hspace*{-4pt}\Indexc{__CFA_MINOR__}\index{preprocessor variables!__CFA_MINOR__@{©__CFA_MINOR__©}}
is always available during preprocessing and its value is the current minor \Index{version number} of \CFA.

\item\hspace*{-4pt}\Indexc{__CFA_PATCH__}\index{preprocessor variables!__CFA_PATCH__@©__CFA_PATCH__©}
is always available during preprocessing and its value is the current patch \Index{version number} of \CFA.

\item\hspace*{-4pt}\Indexc{__CFORALL__}\index{preprocessor variables!__CFORALL__@©__CFORALL__©}
is always available during preprocessing and it has no value.
\end{description}

These preprocessor variables allow conditional compilation of programs that must work differently in these situations.
For example, to toggle between C and \CFA extensions, using the following:
\begin{lstlisting}
#ifndef __CFORALL__
#include <stdio.h>                      // C header file
#else
#include <fstream>                      // §\CFA{}§ header file
#endif
\end{lstlisting}
which conditionally includes the correct header file, if the program is compiled using ©gcc© or ©cfa©. 


\section{Underscores in Constants}

Numeric constants are extended to allow \Index{underscore}s within constants\index{constant!underscore}, e.g.:
\begin{lstlisting}
2®_®147®_®483®_®648;                            // decimal constant
56_ul;                                          // decimal unsigned long constant
0_377;                                          // octal constant
0x_ff_ff;                                       // hexadecimal constant
0x_ef3d_aa5c;                           // hexadecimal constant
3.141_592_654;                          // floating point constant
10_e_+1_00;                                     // floating point constant
0x_ff_ff_p_3;                           // hexadecimal floating point
0x_1.ffff_ffff_p_128_l;         // hexadecimal floating point long constant
L_"\x_ff_ee";                           // wide character constant
\end{lstlisting}
The rules for placement of underscores is as follows:
\begin{enumerate}
\item
A sequence of underscores is disallowed, e.g., ©12__34© is invalid.
\item
Underscores may only appear within a sequence of digits (regardless of the digit radix).
In other words, an underscore cannot start or end a sequence of digits, e.g., ©_1©, ©1_© and ©_1_© are invalid (actually, the 1st and 3rd examples are identifier names).
\item
A numeric prefix may end with an underscore;
a numeric infix may begin and/or end with an underscore;
a numeric suffix may begin with an underscore.
For example, the octal ©0© or hexadecimal ©0x© prefix may end with an underscore ©0_377© or ©0x_ff©;
the exponent infix ©E© may start or end with an underscore ©1.0_E10©, ©1.0E_10© or ©1.0_E_10©;
the type suffixes ©U©, ©L©, etc. may start with an underscore ©1_U©, ©1_ll© or ©1.0E10_f©.
\end{enumerate}
It is significantly easier to read and enter long constants when they are broken up into smaller groupings (most cultures use comma or period among digits for the same purpose).
This extension is backwards compatible, matches with the use of underscore in variable names, and appears in Ada and Java.


\section{Declarations}
\label{s:Declarations}

C declaration syntax is notoriously confusing and error prone.
For example, many C programmers are confused by a declaration as simple as:
\begin{quote2}
\begin{tabular}{@{}ll@{}}
\begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
int *x[ 5 ]
\end{lstlisting}
&
\raisebox{-0.75\totalheight}{\input{Cdecl}}
\end{tabular}
\end{quote2}
Is this an array of 5 pointers to integers or a pointer to an array of 5 integers?
Another example of confusion results from the fact that a routine name and its parameters are embedded within the return type, mimicking the way the return value is used at the routine's call site.
For example, a routine returning a pointer to an array of integers is defined and used in the following way:
\begin{lstlisting}
int (*f())[ 5 ] {...};  // definition mimics usage
... (*f())[ 3 ] += 1;
\end{lstlisting}
Essentially, the return type is wrapped around the routine name in successive layers (like an onion).
While attempting to make the two contexts consistent was a laudable goal, it has not worked out in practice.

\CFA provides its own type, variable and routine declarations, using a slightly different syntax.
The new declarations place modifiers to the left of the base type, while C declarations place modifiers to the right of the base type.
The only exception is bit field specification, which always appear to the right of the base type.
C and the new \CFA declarations may appear together in the same program block, but cannot be mixed within a specific declaration.

In \CFA declarations, the same tokens are used as in C: the character ©*© is used to indicate a pointer, square brackets ©[©\,©]© are used to represent an array, and parentheses ©()© are used to indicate a routine parameter.
However, unlike C, \CFA type declaration tokens are specified from left to right and the entire type specification is distributed across all variables in the declaration list.
For instance, variables ©x© and ©y© of type pointer to integer are defined in \CFA as follows:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c}{\textbf{C}}        \\
\begin{lstlisting}
®* int x, y;®
\end{lstlisting}
&
\begin{lstlisting}
int *x, *y;
\end{lstlisting}
\end{tabular}
\end{quote2}
Other examples are:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{\hspace{20pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c@{\hspace{20pt}}}{\textbf{C}}        \\
\begin{lstlisting}
[ 5 ] int z;
[ 5 ] * char w;
* [ 5 ] double v;
struct s {
        int f0:3;
        * int f1;
        [ 5 ] * int f2;
};
\end{lstlisting}
&
\begin{lstlisting}
int z[ 5 ];
char *w[ 5 ];
double (*v)[ 5 ];
struct s {
        int f0:3;
        int *f1;
        int *f2[ 5 ]
};
\end{lstlisting}
&
\begin{lstlisting}
// array of 5 integers
// array of 5 pointers to char
// pointer to array of 5 doubles

// common bit field syntax



\end{lstlisting}
\end{tabular}
\end{quote2}

All type qualifiers, i.e., ©const© and ©volatile©, are used in the normal way with the new declarations but appear left to right, e.g.:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{\hspace{20pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c@{\hspace{20pt}}}{\textbf{C}}        \\
\begin{lstlisting}
const * const int x;
const * [ 5 ] const int y;
\end{lstlisting}
&
\begin{lstlisting}
int const * const x;
const int (* const y)[ 5 ]
\end{lstlisting}
&
\begin{lstlisting}
// const pointer to const integer
// const pointer to array of 5 const integers
\end{lstlisting}
\end{tabular}
\end{quote2}
All declaration qualifiers, i.e., ©extern©, ©static©, etc., are used in the normal way with the new declarations but can only appear at the start of a \CFA routine declaration,\footnote{\label{StorageClassSpecifier}
The placement of a storage-class specifier other than at the beginning of the declaration specifiers in a declaration is an obsolescent feature.~\cite[\S~6.11.5(1)]{C11}} e.g.:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{\hspace{20pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c@{\hspace{20pt}}}{\textbf{C}}        \\
\begin{lstlisting}
extern [ 5 ] int x;
static * const int y;
\end{lstlisting}
&
\begin{lstlisting}
int extern x[ 5 ];
const int static *y;
\end{lstlisting}
&
\begin{lstlisting}
// externally visible array of 5 integers
// internally visible pointer to constant int
\end{lstlisting}
\end{tabular}
\end{quote2}

Unsupported are K\&R C declarations where the base type defaults to ©int©, if no type is specified\footnote{
At least one type specifier shall be given in the declaration specifiers in each declaration, and in the specifier-qualifier list in each structure declaration and type name~\cite[\S~6.7.2(2)]{C11}},
e.g.:
\begin{lstlisting}
x;                                              // int x
*y;                                             // int *y
f( p1, p2 );                    // int f( int p1, int p2 );
f( p1, p2 ) {}                  // int f( int p1, int p2 ) {}
\end{lstlisting}

As stated above, the two styles of declaration may appear together in the same block.
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 systems.


\section{Type Operators}

The new declaration syntax can be used in other contexts where types are required, e.g., casts and the pseudo-routine ©sizeof©:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c}{\textbf{C}}        \\
\begin{lstlisting}
y = (* int)x;
i = sizeof([ 5 ] * int);
\end{lstlisting}
&
\begin{lstlisting}
y = (int *)x;
i = sizeof(int *[ 5 ]);
\end{lstlisting}
\end{tabular}
\end{quote2}


\section{Routine Definition}

\CFA also supports a new syntax for routine definition, as well as ISO C and K\&R routine syntax.
The point of the new syntax is to allow returning multiple values from a routine~\cite{CLU,Galletly96}, e.g.:
\begin{lstlisting}
®[ int o1, int o2, char o3 ]® f( int i1, char i2, char i3 ) {
        §\emph{routine body}§
}
\end{lstlisting}
where routine ©f© has three output (return values) and three input parameters.
Existing C syntax cannot be extended with multiple return types because it is impossible to embed a single routine name within multiple return type specifications.

In detail, the brackets, ©[]©, enclose the result type, where each return value is named and that name is a local variable of the particular return type.\footnote{
Michael Tiemann, with help from Doug Lea, provided named return values in g++, circa 1989.}
The value of each local return variable is automatically returned at routine termination.
Declaration qualifiers can only appear at the start of a routine definition, e.g.:
\begin{lstlisting}
extern [ int x ] g( int y ) {§\,§}
\end{lstlisting}
Lastly, if there are no output parameters or input parameters, the brackets and/or parentheses must still be specified;
in both cases the type is assumed to be void as opposed to old style C defaults of int return type and unknown parameter types, respectively, as in:
\begin{lstlisting}
[§\,§] g();                                             // no input or output parameters
[ void ] g( void );                     // no input or output parameters
\end{lstlisting}

Routine f is called as follows:
\begin{lstlisting}
[ i, j, ch ] = f( 3, 'a', ch );
\end{lstlisting}
The list of return values from f and the grouping on the left-hand side of the assignment is called a tuple and discussed in Section 12.

\CFA style declarations cannot be used to declare parameters for K\&R style routine definitions because of the following ambiguity:
\begin{lstlisting}
int (*f(x))[ 5 ] int x; {}
\end{lstlisting}
The string ``©int (*f(x))[ 5 ]©'' declares a K\&R style routine of type returning a pointer to an array of 5 integers, while the string ``©[ 5 ] int x©'' declares a \CFA style parameter x of type array of 5 integers.
Since the strings overlap starting with the open bracket, ©[©, there is an ambiguous interpretation for the string.
As well, \CFA-style declarations cannot be used to declare parameters for C-style routine-definitions because of the following ambiguity:
\begin{lstlisting}
typedef int foo;
int f( int (* foo) );           // foo is redefined as a parameter name
\end{lstlisting}
The string ``©int (* foo)©'' declares a C-style named-parameter of type pointer to an integer (the parenthesis are superfluous), while the same string declares a \CFA style unnamed parameter of type routine returning integer with unnamed parameter of type pointer to foo.
The redefinition of a type name in a parameter list is the only context in C where the character ©*© can appear to the left of a type name, and \CFA relies on all type modifier characters appearing to the right of the type name.
The inability to use \CFA declarations in these two contexts is probably a blessing because it precludes programmers from arbitrarily switching between declarations forms within a declaration contexts.

C-style declarations can be used to declare parameters for \CFA style routine definitions, e.g.:
\begin{lstlisting}
[ int ] f( * int, int * );      // returns an integer, accepts 2 pointers to integers
[ * int, int * ] f( int );      // returns 2 pointers to integers, accepts an integer
\end{lstlisting}
The reason for allowing both declaration styles in the new context is for backwards compatibility with existing preprocessor macros that generate C-style declaration-syntax, as in:
\begin{lstlisting}
#define ptoa( n, d ) int (*n)[ d ]
int f( ptoa(p,5) ) ...          // expands to int f( int (*p)[ 5 ] )
[ int ] f( ptoa(p,5) ) ...      // expands to [ int ] f( int (*p)[ 5 ] )
\end{lstlisting}
Again, programmers are highly encouraged to use one declaration form or the other, rather than mixing the forms.


\subsection{Returning Values}

Named return values handle the case where it is necessary to define a local variable whose value is then returned in a ©return© statement, as in:
\begin{lstlisting}
int f() {
        int x;
        ... x = 0; ... x = y; ...
        return x;
}
\end{lstlisting}
Because the value in the return variable is automatically returned when a \CFA routine terminates, the ©return© statement \emph{does not} contain an expression, as in:
\begin{lstlisting}
®[ int x ]® f() {
        ... x = 0; ... x = y; ...
        ®return;® // implicitly return x
}
\end{lstlisting}
When the return is encountered, the current value of ©x© is returned to the calling routine.
As well, ``falling off the end'' of a routine without a ©return© statement is permitted, as in:
\begin{lstlisting}
[ int x ] f() {
        ... x = 0; ... x = y; ...
} // implicitly return x
\end{lstlisting}
In this case, the current value of ©x© is returned to the calling routine just as if a ©return© had been encountered.


\subsection{Routine Prototype}

The syntax of the new routine prototype declaration follows directly from the new routine definition syntax;
as well, parameter names are optional, e.g.:
\begin{lstlisting}
[ int x ] f ();                         // returning int with no parameters
[ * int ] g (int y);            // returning pointer to int with int parameter
[ ] h (int,char);                       // returning no result with int and char parameters
[ * int,int ] j (int);          // returning pointer to int and int, with int parameter
\end{lstlisting}
This syntax allows a prototype declaration to be created by cutting and pasting source text from the routine definition header (or vice versa).
It is possible to declare multiple routine-prototypes in a single declaration, but the entire type specification is distributed across \emph{all} routine names in the declaration list (see~\VRef{s:Declarations}), e.g.:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c}{\textbf{C}}        \\
\begin{lstlisting}
[ int ] f(int), g;
\end{lstlisting}
&
\begin{lstlisting}
int f(int), g(int);
\end{lstlisting}
\end{tabular}
\end{quote2}
Declaration qualifiers can only appear at the start of a \CFA routine declaration,\footref{StorageClassSpecifier} e.g.:
\begin{lstlisting}
extern [ int ] f (int);
static [ int ] g (int);
\end{lstlisting}


\section{Routine Pointers}

The syntax for pointers to \CFA routines specifies the pointer name on the right, e.g.:
\begin{lstlisting}
* [ int x ] () fp;                      // pointer to routine returning int with no parameters
* [ * int ] (int y) gp;         // pointer to routine returning pointer to int with int parameter
* [ ] (int,char) hp;            // pointer to routine returning no result with int and char parameters
* [ * int,int ] (int) jp;       // pointer to routine returning pointer to int and int, with int parameter
\end{lstlisting}
While parameter names are optional, \emph{a routine name cannot be specified};
for example, the following is incorrect:
\begin{lstlisting}
* [ int x ] f () fp;            // routine name "f" is not allowed
\end{lstlisting}


\section{Named and Default Arguments}

Named and default arguments~\cite{Hardgrave76}\footnote{
Francez~\cite{Francez77} proposed a further extension to the named-parameter passing style, which specifies what type of communication (by value, by reference, by name) the argument is passed to the routine.}
are two mechanisms to simplify routine call.
Both mechanisms are discussed with respect to \CFA.
\begin{description}
\item[Named (or Keyword) Arguments:]
provide the ability to specify an argument to a routine call using the parameter name rather than the position of the parameter.
For example, given the routine:
\begin{lstlisting}
void p( int x, int y, int z ) {...}
\end{lstlisting}
a positional call is:
\begin{lstlisting}
p( 4, 7, 3 );
\end{lstlisting}
whereas a named (keyword) call may be:
\begin{lstlisting}
p( z : 3, x : 4, y : 7 ); // rewrite $\Rightarrow$ p( 4, 7, 3 )
\end{lstlisting}
Here the order of the arguments is unimportant, and the names of the parameters are used to associate argument values with the corresponding parameters.
The compiler rewrites a named call into a positional call.
The advantages of named parameters are:
\begin{itemize}
\item
Remembering the names of the parameters may be easier than the order in the routine definition.
\item
Parameter names provide documentation at the call site (assuming the names are descriptive).
\item
Changes can be made to the order or number of parameters without affecting the call (although the call must still be recompiled).
\end{itemize}

Unfortunately, named arguments do not work in C-style programming-languages because a routine prototype is not required to specify parameter names, nor do the names in the prototype have to match with the actual definition.
For example, the following routine prototypes and definition are all valid.
\begin{lstlisting}
void p( int, int, int );                        // equivalent prototypes
void p( int x, int y, int z );
void p( int y, int x, int z );
void p( int z, int y, int x );
void p( int q, int r, int s ) {}        // match with this definition
\end{lstlisting}
Forcing matching parameter names in routine prototypes with corresponding routine definitions is possible, but goes against a strong tradition in C programming.
Alternatively, prototype definitions can be eliminated by using a two-pass compilation, and implicitly creating header files for exports.
The former is easy to do, while the latter is more complex.
Currently, \CFA does \emph{not} attempt to support named arguments.

\item[Default Arguments]
provide the ability to associate a default value with a parameter so it can be optionally specified in the argument list.
For example, given the routine:
\begin{lstlisting}
void p( int x = 1, int y = 2, int z = 3 ) {...}
\end{lstlisting}
the allowable positional calls are:
\begin{lstlisting}
p();                            // rewrite $\Rightarrow$ p( 1, 2, 3 )
p( 4 );                         // rewrite $\Rightarrow$ p( 4, 2, 3 )
p( 4, 4 );                      // rewrite $\Rightarrow$ p( 4, 4, 3 )
p( 4, 4, 4 );           // rewrite $\Rightarrow$ p( 4, 4, 4 )
// empty arguments
p(  , 4, 4 );           // rewrite $\Rightarrow$ p( 1, 4, 4 )
p( 4,  , 4 );           // rewrite $\Rightarrow$ p( 4, 2, 4 )
p( 4, 4,   );           // rewrite $\Rightarrow$ p( 4, 4, 3 )
p( 4,  ,   );           // rewrite $\Rightarrow$ p( 4, 2, 3 )
p(  , 4,   );           // rewrite $\Rightarrow$ p( 1, 4, 3 )
p(  ,  , 4 );           // rewrite $\Rightarrow$ p( 1, 2, 4 )
p(  ,  ,   );           // rewrite $\Rightarrow$ p( 1, 2, 3 )
\end{lstlisting}
Here the missing arguments are inserted from the default values in the parameter list.
The compiler rewrites missing default values into explicit positional arguments.
The advantages of default values are:
\begin{itemize}
\item
Routines with a large number of parameters are often very generalized, giving a programmer a number of different options on how a computation is performed.
For many of these kinds of routines, there are standard or default settings that work for the majority of computations.
Without default values for parameters, a programmer is forced to specify these common values all the time, resulting in long argument lists that are error prone.
\item
When a routine's interface is augmented with new parameters, it extends the interface providing generalizability\footnote{
``It should be possible for the implementor of an abstraction to increase its generality.
So long as the modified abstraction is a generalization of the original, existing uses of the abstraction will not require change.
It might be possible to modify an abstraction in a manner which is not a generalization without affecting existing uses, but, without inspecting the modules in which the uses occur, this possibility cannot be determined.
This criterion precludes the addition of parameters, unless these parameters have default or inferred values that are valid for all possible existing applications.''~\cite[p.~128]{Cormack90}}
(somewhat like the generalization provided by inheritance for classes).
That is, all existing calls are still valid, although the call must still be recompiled.
\end{itemize}
The only disadvantage of default arguments is that unintentional omission of an argument may not result in a compiler-time error.
Instead, a default value is used, which may not be the programmer's intent.

Default values may only appear in a prototype versus definition context:
\begin{lstlisting}
void p( int x, int y = 2, int z = 3 );          // prototype: allowed
void p( int, int = 2, int = 3 );                        // prototype: allowed
void p( int x, int y = 2, int z = 3 ) {}        // definition: not allowed
\end{lstlisting}
The reason for this restriction is to allow separate compilation.
Multiple prototypes with different default values is an error.
\end{description}

Ellipse (``...'') arguments present problems when used with default arguments.
The conflict occurs because both named and ellipse arguments must appear after positional arguments, giving two possibilities:
\begin{lstlisting}
p( /* positional */, . . ., /* named */ );
p( /* positional */, /* named */, . . . );
\end{lstlisting}
While it is possible to implement both approaches, the first possibly is more complex than the second, e.g.:
\begin{lstlisting}
p( int x, int y, int z, . . . );
p( 1, 4, 5, 6, z : 3, y : 2 ); // assume p( /* positional */, . . ., /* named */ );
p( 1, z : 3, y : 2, 4, 5, 6 ); // assume p( /* positional */, /* named */, . . . );
\end{lstlisting}
In the first call, it is necessary for the programmer to conceptually rewrite the call, changing named arguments into positional, before knowing where the ellipse arguments begin.
Hence, this approach seems significantly more difficult, and hence, confusing and error prone.
In the second call, the named arguments separate the positional and ellipse arguments, making it trivial to read the call.

The problem is exacerbated with default arguments, e.g.:
\begin{lstlisting}
void p( int x, int y = 2, int z = 3. . . );
p( 1, 4, 5, 6, z : 3 );         // assume p( /* positional */, . . ., /* named */ );
p( 1, z : 3, 4, 5, 6 );         // assume p( /* positional */, /* named */, . . . );
\end{lstlisting}
The first call is an error because arguments 4 and 5 are actually positional not ellipse arguments;
therefore, argument 5 subsequently conflicts with the named argument z : 3.
In the second call, the default value for y is implicitly inserted after argument 1 and the named arguments separate the positional and ellipse arguments, making it trivial to read the call.
For these reasons, \CFA requires named arguments before ellipse arguments.
Finally, while ellipse arguments are needed for a small set of existing C routines, like printf, the extended \CFA type system largely eliminates the need for ellipse arguments (see Section 24), making much of this discussion moot.

Default arguments and overloading (see Section 24) are complementary.
While in theory default arguments can be simulated with overloading, as in:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{default arguments}}  & \multicolumn{1}{c}{\textbf{overloading}}      \\
\begin{lstlisting}
void p( int x, int y = 2, int z = 3 ) {...}


\end{lstlisting}
&
\begin{lstlisting}
void p( int x, int y, int z ) {...}
void p( int x ) { p( x, 2, 3 ); }
void p( int x, int y ) { p( x, y, 3 ); }
\end{lstlisting}
\end{tabular}
\end{quote2}
the number of required overloaded routines is linear in the number of default values, which is unacceptable growth.
In general, overloading should only be used over default arguments if the body of the routine is significantly different.
Furthermore, overloading cannot handle accessing default arguments in the middle of a positional list, via a missing argument, such as:
\begin{lstlisting}
p( 1, /* default */, 5 );               // rewrite $\Rightarrow$ p( 1, 2, 5 )
\end{lstlisting}

Given the \CFA restrictions above, both named and default arguments are backwards compatible.
\CC only supports default arguments;
Ada supports both named and default arguments.


\section{Type/Routine Nesting}

Nesting of types and routines is useful for controlling name visibility (\newterm{name hiding}).


\subsection{Type Nesting}

\CFA allows \Index{type nesting}, and type qualification of the nested types, where as C hoists\index{type hoisting} (refactors) nested types into the enclosing scope and has no type qualification.
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l|l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{C Type Nesting}}     & \multicolumn{1}{c}{\textbf{C Implicit Hoisting}}      & \multicolumn{1}{|c}{\textbf{\CFA}}    \\
\hline
\begin{lstlisting}
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 fred() {
        s.t.c = R;
        struct T t = { R, 1, 2 };
        enum C c;
        union U u;
}
\end{lstlisting}
&
\begin{lstlisting}
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{lstlisting}
&
\begin{lstlisting}
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 fred() {
        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{lstlisting}
\end{tabular}
\end{quote2}
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{Routine Nesting}

While \CFA does not provide object programming by putting routines into structures, it does rely heavily on locally nested routines to redefine operations at or close to a call site.
For example, the C quick-sort is wrapped into the following polymorphic \CFA routine:
\begin{lstlisting}
forall( otype T | { int ?<?( T, T ); } )
void qsort( const T * arr, size_t dimension );
\end{lstlisting}
which can be used to sort in ascending and descending order by locally redefining the less-than operator into greater-than.
\begin{lstlisting}
const unsigned int size = 5;
int ia[size];
...                                             // assign values to array ia
qsort( ia, size );              // sort ascending order using builtin ?<?
{
        ®int ?<?( int x, int y ) { return x > y; }® // nested routine
        qsort( ia, size );      // sort descending order by local redefinition
}
\end{lstlisting}

Nested routines are not first-class, meaning a nested routine cannot be returned if it has references to variables in its enclosing blocks;
the only exception is references to the external block of the translation unit, as these variables persist for the duration of the program.
The following program in undefined in \CFA (and ©gcc©\index{gcc})
\begin{lstlisting}
[* [int]( int )] foo() {                // int (*foo())( int )
        int ®i® = 7;
        int bar( int p ) {
                ®i® += 1;                                       // dependent on local variable
                sout | ®i® | endl;
        }
        return bar;                                     // undefined because of local dependence
}
int main() {
        * [int](int) fp = foo();        // int (*fp)(int)
    sout | fp( 3 ) | endl;
}
\end{lstlisting}
because 

Currently, there are no \Index{lambda} expressions, i.e., unnamed routines because routine names are very important to properly select the correct routine.


\section{Tuples}

In C and \CFA, lists of elements appear in several contexts, such as the parameter list for a routine call.
(More contexts are added shortly.)
A list of such elements is called a tuple.
The general syntax of a tuple is:
\begin{lstlisting}
[ §\emph{exprlist}§ ]
\end{lstlisting}
where ©$\emph{exprlist}$© is a list of one or more expressions separated by commas.
The brackets, ©[]©, allow differentiating between tuples and expressions containing the C comma operator.
The following are examples of tuples:
\begin{lstlisting}
[ x, y, z ]
[ 2 ]
[ v+w, x*y, 3.14159, f() ]
\end{lstlisting}
Tuples are permitted to contain sub-tuples (i.e., nesting), such as ©[ [ 14, 21 ], 9 ]©, which is a 2-element tuple whose first element is itself a tuple.
Note, a tuple is not a record (structure);
a record denotes a single value with substructure, whereas a tuple is multiple values with no substructure (see flattening coercion in Section 12.1).
In essence, tuples are largely a compile time phenomenon, having little or no runtime presence.

Tuples can be organized into compile-time tuple variables;
these variables are of \newterm{tuple type}.
Tuple variables and types can be used anywhere lists of conventional variables and types can be used.
The general syntax of a tuple type is:
\begin{lstlisting}
[ §\emph{typelist}§ ]
\end{lstlisting}
where ©$\emph{typelist}$© is a list of one or more legal \CFA or C type specifications separated by commas, which may include other tuple type specifications.
Examples of tuple types include:
\begin{lstlisting}
[ unsigned int, char ]
[ double, double, double ]
[ * int, int * ]                // mix of CFA and ANSI
[ * [ 5 ] int, * * char, * [ [ int, int ] ] (int, int) ]
\end{lstlisting}
Like tuples, tuple types may be nested, such as ©[ [ int, int ], int ]©, which is a 2-element tuple type whose first element is itself a tuple type.

Examples of declarations using tuple types are:
\begin{lstlisting}
[ int, int ] x;                 // 2 element tuple, each element of type int
* [ char, char ] y;             // pointer to a 2 element tuple
[ [ int, int ] ] z ([ int, int ]);
\end{lstlisting}
The last example declares an external routine that expects a 2 element tuple as an input parameter and returns a 2 element tuple as its result.

As mentioned, tuples can appear in contexts requiring a list of value, such as an argument list of a routine call.
In unambiguous situations, the tuple brackets may be omitted, e.g., a tuple that appears as an argument may have its
square brackets omitted for convenience; therefore, the following routine invocations are equivalent:
\begin{lstlisting}
f( [ 1, x+2, fred() ] );
f( 1, x+2, fred() );
\end{lstlisting}
Also, a tuple or a tuple variable may be used to supply all or part of an argument list for a routine expecting multiple input parameters or for a routine expecting a tuple as an input parameter.
For example, the following are all legal:
\begin{lstlisting}
[ int, int ] w1;
[ int, int, int ] w2;
[ void ] f (int, int, int); /* three input parameters of type int */
[ void ] g ([ int, int, int ]); /* 3 element tuple as input */
f( [ 1, 2, 3 ] );
f( w1, 3 );
f( 1, w1 );
f( w2 );
g( [ 1, 2, 3 ] );
g( w1, 3 );
g( 1, w1 );
g( w2 );
\end{lstlisting}
Note, in all cases 3 arguments are supplied even though the syntax may appear to supply less than 3. As mentioned, a
tuple does not have structure like a record; a tuple is simply converted into a list of components.
\begin{rationale}
The present implementation of \CFA does not support nested routine calls when the inner routine returns multiple values; i.e., a statement such as ©g( f() )© is not supported.
Using a temporary variable to store the  results of the inner routine and then passing this variable to the outer routine works, however.
\end{rationale}

A tuple can contain a C comma expression, provided the expression containing the comma operator is enclosed in parentheses.
For instance, the following tuples are equivalent:
\begin{lstlisting}
[ 1, 3, 5 ]
[ 1, (2, 3), 5 ]
\end{lstlisting}
The second element of the second tuple is the expression (2, 3), which yields the result 3.
This requirement is the same as for comma expressions in argument lists.

Type qualifiers, i.e., const and volatile, may modify a tuple type.
The meaning is the same as for a type qualifier modifying an aggregate type [Int99, x 6.5.2.3(7),x 6.7.3(11)], i.e., the qualifier is distributed across all of the types in the tuple, e.g.:
\begin{lstlisting}
const volatile [ int, float, const int ] x;
\end{lstlisting}
is equivalent to:
\begin{lstlisting}
[ const volatile int, const volatile float, const volatile int ] x;
\end{lstlisting}
Declaration qualifiers can only appear at the start of a \CFA tuple declaration4, e.g.:
\begin{lstlisting}
extern [ int, int ] w1;
static [ int, int, int ] w2;
\end{lstlisting}
\begin{rationale}
Unfortunately, C's syntax for subscripts precluded treating them as tuples.
The C subscript list has the form ©[i][j]...© and not ©[i, j, ...]©.
Therefore, there is no syntactic way for a routine returning multiple values to specify the different subscript values, e.g., ©f[g()]© always means a single subscript value because there is only one set of brackets.
Fixing this requires a major change to C because the syntactic form ©M[i, j, k]© already has a particular meaning: ©i, j, k© is a comma expression.
\end{rationale}


\subsection{Tuple Coercions}

There are four coercions that can be performed on tuples and tuple variables: closing, opening, flattening and structuring.
In addition, the coercion of dereferencing can be performed on a tuple variable to yield its value(s), as for other variables.
A \newterm{closing coercion} takes a set of values and converts it into a tuple value, which is a contiguous set of values, as in:
\begin{lstlisting}
[ int, int, int, int ] w;
w = [ 1, 2, 3, 4 ];
\end{lstlisting}
First the right-hand tuple is closed into a tuple value and then the tuple value is assigned.

An \newterm{opening coercion} is the opposite of closing; a tuple value is converted into a tuple of values, as in:
\begin{lstlisting}
[ a, b, c, d ] = w
\end{lstlisting}
©w© is implicitly opened to yield a tuple of four values, which are then assigned individually.

A \newterm{flattening coercion} coerces a nested tuple, i.e., a tuple with one or more components, which are themselves tuples, into a flattened tuple, which is a tuple whose components are not tuples, as in:
\begin{lstlisting}
[ a, b, c, d ] = [ 1, [ 2, 3 ], 4 ];
\end{lstlisting}
First the right-hand tuple is flattened and then the values are assigned individually.
Flattening is also performed on tuple types.
For example, the type ©[ int, [ int, int ], int ]© can be coerced, using flattening, into the type ©[ int, int, int, int ]©.

A \newterm{structuring coercion} is the opposite of flattening;
a tuple is structured into a more complex nested tuple.
For example, structuring the tuple ©[ 1, 2, 3, 4 ]© into the tuple ©[ 1, [ 2, 3 ], 4 ]© or the tuple type ©[ int, int, int, int ]© into the tuple type ©[ int, [ int, int ], int ]©.
In the following example, the last assignment illustrates all the tuple coercions:
\begin{lstlisting}
[ int, int, int, int ] w = [ 1, 2, 3, 4 ];
int x = 5;
[ x, w ] = [ w, x ];            // all four tuple coercions
\end{lstlisting}
Starting on the right-hand tuple in the last assignment statement, w is opened, producing a tuple of four values;
therefore, the right-hand tuple is now the tuple ©[ [ 1, 2, 3, 4 ], 5 ]©.
This tuple is then flattened, yielding ©[ 1, 2, 3, 4, 5 ]©, which is structured into ©[ 1, [ 2, 3, 4, 5 ] ]© to match the tuple type of the left-hand side.
The tuple ©[ 2, 3, 4, 5 ]© is then closed to create a tuple value.
Finally, ©x© is assigned ©1© and ©w© is assigned the tuple value using multiple assignment (see Section 14).
\begin{rationale}
A possible additional language extension is to use the structuring coercion for tuples to initialize a complex record with a tuple.
\end{rationale}


\section{Mass Assignment}

\CFA permits assignment to several variables at once using mass assignment~\cite{CLU}.
Mass assignment has the following form:
\begin{lstlisting}
[ §\emph{lvalue}§, ..., §\emph{lvalue}§ ] = §\emph{expr}§;
\end{lstlisting}
The left-hand side is a tuple of \emph{lvalues}, which is a list of expressions each yielding an address, i.e., any data object that can appear on the left-hand side of a conventional assignment statement.
©$\emph{expr}$© is any standard arithmetic expression.
Clearly, the types of the entities being assigned must be type compatible with the value of the expression.

Mass assignment has parallel semantics, e.g., the statement:
\begin{lstlisting}
[ x, y, z ] = 1.5;
\end{lstlisting}
is equivalent to:
\begin{lstlisting}
x = 1.5; y = 1.5; z = 1.5;
\end{lstlisting}
This semantics is not the same as the following in C:
\begin{lstlisting}
x = y = z = 1.5;
\end{lstlisting}
as conversions between intermediate assignments may lose information.
A more complex example is:
\begin{lstlisting}
[ i, y[i], z ] = a + b;
\end{lstlisting}
which is equivalent to:
\begin{lstlisting}
t = a + b;
a1 = &i; a2 = &y[i]; a3 = &z;
*a1 = t; *a2 = t; *a3 = t;
\end{lstlisting}
The temporary ©t© is necessary to store the value of the expression to eliminate conversion issues.
The temporaries for the addresses are needed so that locations on the left-hand side do not change as the values are assigned.
In this case, ©y[i]© uses the previous value of ©i© and not the new value set at the beginning of the mass assignment.


\section{Multiple Assignment}

\CFA also supports the assignment of several values at once, known as multiple assignment~\cite{CLU,Galletly96}.
Multiple assignment has the following form:
\begin{lstlisting}
[ §\emph{lvalue}§, . . ., §\emph{lvalue}§ ] = [ §\emph{expr}§, . . ., §\emph{expr}§ ];
\end{lstlisting}
The left-hand side is a tuple of \emph{lvalues}, and the right-hand side is a tuple of \emph{expr}s.
Each \emph{expr} appearing on the righthand side of a multiple assignment statement is assigned to the corresponding \emph{lvalues} on the left-hand side of the statement using parallel semantics for each assignment.
An example of multiple assignment is:
\begin{lstlisting}
[ x, y, z ] = [ 1, 2, 3 ];
\end{lstlisting}
Here, the values ©1©, ©2© and ©3© are assigned, respectively, to the variables ©x©, ©y© and ©z©.
 A more complex example is:
\begin{lstlisting}
[ i, y[ i ], z ] = [ 1, i, a + b ];
\end{lstlisting}
Here, the values ©1©, ©i© and ©a + b© are assigned to the variables ©i©, ©y[i]© and ©z©, respectively.
 Note, the parallel semantics of
multiple assignment ensures:
\begin{lstlisting}
[ x, y ] = [ y, x ];
\end{lstlisting}
correctly interchanges (swaps) the values stored in ©x© and ©y©.
The following cases are errors:
\begin{lstlisting}
[ a, b, c ] = [ 1, 2, 3, 4 ];
[ a, b, c ] = [ 1, 2 ];
\end{lstlisting}
because the number of entities in the left-hand tuple is unequal with the right-hand tuple.

As for all tuple contexts in C, side effects should not be used because C does not define an ordering for the evaluation of the elements of a tuple;
both these examples produce indeterminate results:
\begin{lstlisting}
f( x++, x++ );                          // C routine call with side effects in arguments
[ v1, v2 ] = [ x++, x++ ];      // side effects in righthand side of multiple assignment
\end{lstlisting}


\section{Cascade Assignment}

As in C, \CFA mass and multiple assignments can be cascaded, producing cascade assignment.
Cascade assignment has the following form:
\begin{lstlisting}
§\emph{tuple}§ = §\emph{tuple}§ = ... = §\emph{tuple}§;
\end{lstlisting}
and it has the same parallel semantics as for mass and multiple assignment.
Some examples of cascade assignment are:
\begin{lstlisting}
x1 = y1 = x2 = y2 = 0;
[ x1, y1 ] = [ x2, y2 ] = [ x3, y3 ];
[ x1, y1 ] = [ x2, y2 ] = 0;
[ x1, y1 ] = z = 0;
\end{lstlisting}
As in C, the rightmost assignment is performed first, i.e., assignment parses right to left.


\section{Field Tuples}

Tuples may be used to select multiple fields of a record by field name.
Its general form is:
\begin{lstlisting}
§\emph{expr}§ . [ §\emph{fieldlist}§ ]
§\emph{expr}§ -> [ §\emph{fieldlist}§ ]
\end{lstlisting}
\emph{expr} is any expression yielding a value of type record, e.g., ©struct©, ©union©.
Each element of \emph{ fieldlist} is an element of the record specified by \emph{expr}.
A record-field tuple may be used anywhere a tuple can be used. An example of the use of a record-field tuple is
the following:
\begin{lstlisting}
struct s {
        int f1, f2;
        char f3;
        double f4;
} v;
v.[ f3, f1, f2 ] = ['x', 11, 17 ];      // equivalent to v.f3 = 'x', v.f1 = 11, v.f2 = 17
f( v.[ f3, f1, f2 ] );                          // equivalent to f( v.f3, v.f1, v.f2 )
\end{lstlisting}
Note, the fields appearing in a record-field tuple may be specified in any order;
also, it is unnecessary to specify all the fields of a struct in a multiple record-field tuple.

If a field of a ©struct© is itself another ©struct©, multiple fields of this subrecord can be specified using a nested record-field tuple, as in the following example:
\begin{lstlisting}
struct inner {
        int f2, f3;
};
struct outer {
        int f1;
        struct inner i;
        double f4;
} o;

o.[ f1, i.[ f2, f3 ], f4 ] = [ 11, 12, 13, 3.14159 ];
\end{lstlisting}


\section{Labelled Break/Continue}

While C provides ©break© and ©continue© statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
Unfortunately, this restriction forces programmers to use ©goto© to achieve the equivalent for more than one level of nesting.
To prevent having to make this switch, the ©break© and ©continue© are extended with a target label to support static multi-level exit~\cite{Buhr85,Java}.
For the labelled ©break©, it is possible to specify which control structure is the target for exit, as in:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c}{\textbf{C}}        \\
\begin{lstlisting}
®L1:® for ( ... ) {
        ®L2:® for ( ... ) {
                ®L3:® for ( ... ) {
                        ... break ®L1®; ...
                        ... break ®L2®; ...
                        ... break ®L3®; // or break
                }
        }
}
\end{lstlisting}
&
\begin{lstlisting}
for ( ... ) {
        for ( ... ) {
                for ( ... ) {
                        ... goto L1; ...
                        ... goto L2; ...
                        ... goto L3; // or break
                } L3: ;
        } L2: ;
} L1: ;
\end{lstlisting}
\end{tabular}
\end{quote2}
The inner most loop has three exit points, which cause termination of one or more of the three nested loops, respectively.
For the labelled ©continue©, it is possible to specify which control structure is the target for the next loop iteration, as in:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c}{\textbf{C}}        \\
\begin{lstlisting}
®L1®: for ( ... ) {
        ®L2®: for ( ... ) {
                ®L3®: for ( ... ) {
                        ... continue ®L1®; ...
                        ... continue ®L2®; ...
                        ... continue ®L3®; ...

                }

        }

}
\end{lstlisting}
&
\begin{lstlisting}
for ( ... ) {
        for ( ... ) {
                for ( ... ) {
                        ... goto L1; ...
                        ... goto L2; ...
                        ... goto L3; ...
                  L3: ;
                }
          L2: ;
        }
  L1: ;
}
\end{lstlisting}
\end{tabular}
\end{quote2}
The inner most loop has three restart points, which cause the next loop iteration to begin, respectively.
For both ©break© and ©continue©, the target label must be directly associated with a ©for©, ©while© or ©do© statement;
for ©break©, the target label can also be associated with a ©switch© statement.
Both ©break© and ©continue© with target labels are simply a ©goto© restricted in the following ways:
\begin{itemize}
\item
They cannot be used to create a loop.
This means that only the looping construct can be used to create a loop.
This restriction is important since all situations that can result in repeated execution of statements in a program are clearly delineated.
\item
Since they always transfers out of containing control structures, they cannot be used to branch into a control structure.
\end{itemize}
The advantage of the labelled ©break©/©continue© is that it allows static multi-level exits without having to use the ©goto© statement and ties control flow to the target control structure rather than an arbitrary point in a program.
Furthermore, the location of the label at the beginning of the target control structure informs the reader that complex control-flow is occurring in the body of the control structure.
With ©goto©, the label at the end of the control structure fails to convey this important clue early enough to the reader.
Finally, using an explicit target for the transfer instead of an implicit target allows new nested loop or switch constructs to be added or removed without affecting other constructs.
The implicit targets of the current ©break© and ©continue©, i.e., the closest enclosing loop or ©switch©, change as certain constructs are added or removed.


\section{Switch Statement}

C allows a number of questionable forms for the ©switch© statement:
\begin{enumerate}
\item
By default, the end of a ©case© clause\footnote{
In this section, the term \emph{case clause} refers to either a ©case© or ©default© clause.}
\emph{falls through} to the next ©case© clause in the ©switch© statement;
to exit a ©switch© statement from a ©case© clause requires explicitly terminating the clause with a transfer statement, most commonly ©break©, as in:
\begin{lstlisting}
switch ( i ) {
  case 1:
        ...
        // fall-through
  case 2:
        ...
        break;  // exit switch statement
}
\end{lstlisting}
The ability to fall-through to the next clause is a useful form of control flow, specifically when a sequence of case actions compound, as in:
\begin{lstlisting}
switch ( argc ) {
  case 3:
        // open output file
        // fall-through
  case 2:
        // open input file
        break;  // exit switch statement
  default:
        // usage message
}
\end{lstlisting}
In this example, case 2 is always done if case 3 is done.
This control flow is difficult to simulate with if statements or a ©switch© statement without fall-through as code must be duplicated or placed in a separate routine.
C also uses fall-through to handle multiple case-values resulting in the same action, as in:
\begin{lstlisting}
switch ( i ) {
  case 1: case 3: case 5:       // odd values
        // same action
        break;
  case 2: case 4: case 6:       // even values
        // same action
        break;
}
\end{lstlisting}
However, this situation is handled in other languages without fall-through by allowing a list of case values.
While fall-through itself is not a problem, the problem occurs when fall-through is the ©default©, as this semantics is not intuitive to most programmers and is different from virtually all other programming languages with a ©switch© statement.
Hence, ©default© fall-through semantics results in a large number of programming errors as programmers often forget the ©break© statement at the end of a ©case© clause, resulting in inadvertent fall-through.

\item
It is possible to place ©case© clauses on statements nested \emph{within} the body of the ©switch© statement, as in:
\begin{lstlisting}
switch ( i ) {
  case 0:
        if ( j < k ) {
                ...
          case 1:               // transfer into "if" statement
                if ( j < m ) {
                        ...
                  case 2:       // transfer into "if" statement
                        ...
                }
        }
  case 3:
        while ( j < 5 ) {
                ...
          case 4:               // transfer into "while" statement
                ...
        }
}
\end{lstlisting}
The problem with this usage is branching into control structures, which is known to cause both comprehension and technical difficulties.
The comprehension problem occurs from the inability to determine how control reaches a particular point due to the number of branches leading to it.
The technical problem results from the inability to ensure allocation and initialization of variables when blocks are not entered at the beginning.
Often transferring into a block can bypass variable declaration and/or its initialization, which results in subsequent errors.
There are virtually no positive arguments for this kind of control flow, and therefore, there is a strong impetus to eliminate it.
Nevertheless, C does have an idiom where this capability is used, known as ``Duff's device''~\cite{Duff83}:
\begin{lstlisting}
register int n = (count + 7) / 8;
switch ( count % 8 ) {
case 0: do{ *to = *from++;
case 7:         *to = *from++;
case 6:         *to = *from++;
case 5:         *to = *from++;
case 4:         *to = *from++;
case 3:         *to = *from++;
case 2:         *to = *from++;
case 1:         *to = *from++;
                } while ( --n > 0 );
}
\end{lstlisting}
which unrolls a loop N times (N = 8 above) and uses the ©switch© statement to deal with any iterations not a multiple of N.
While efficient, this sort of special purpose usage is questionable:
\begin{quote}
Disgusting, no? But it compiles and runs just fine. I feel a combination of pride and revulsion at this
discovery.~\cite{Duff83}
\end{quote}
\item
It is possible to place the ©default© clause anywhere in the list of labelled clauses for a ©switch© statement, rather than only at the end.
Virtually all programming languages with a ©switch© statement require the ©default© clause to appear last in the case-clause list.
The logic for this semantics is that after checking all the ©case© clauses without success, the ©default© clause is selected;
hence, physically placing the ©default© clause at the end of the ©case© clause list matches with this semantics.
This physical placement can be compared to the physical placement of an ©else© clause at the end of a series of connected ©if©/©else© statements.

\item
It is possible to place unreachable code at the start of a ©switch© statement, as in:
\begin{lstlisting}
switch ( x ) {
        int y = 1;                      // unreachable initialization
        x = 7;                          // unreachable code
  case 3: ...
        y = 3;
        ...
}
\end{lstlisting}
While the declaration of the local variable ©y© is useful and its scope is across all ©case© clauses, the initialization for such a variable is defined to never be executed because control always transfers over it.
Furthermore, any statements before the first ©case© clause can only be executed if labelled and transfered to using a ©goto©, either from outside or inside of the ©switch©.
As mentioned, transfer into control structures should be forbidden.
Transfers from within the ©switch© body using a ©goto© are equally unpalatable.
\end{enumerate}
Before discussing potential language changes to deal with these problems, it is worth observing that in a typical C program:
\begin{itemize}
\item
the number of ©switch© statements is small,
\item
most ©switch© statements are well formed (i.e., no Duff's device),
\item
the ©default© clause is usually written as the last case-clause,
\item
and there is only a medium amount of fall-through from one ©case© clause to the next, and most of these result from a list of case values executing common code, rather than a sequence of case actions that compound.
\end{itemize}
These observations should help to put the effects of suggested changes into perspective.
% Figure 1 shows the grammar change that attempts to minimize the effect on existing C programs.
\begin{enumerate}
\item
Eliminating the ©default© fall-through problem has the greatest potential for affecting existing code.
However, even if fall-through is removed, most ©switch© statements would continue to work because of the explicit transfers already present at the end of each ©case© clause, and the common placement of the ©default© clause at the end of the case list.
In addition, the above grammar provides for the most common use of fall-through, i.e., a list of ©case© clauses executing common code, e.g.:
\begin{lstlisting}
case 1:  case 2:  case 3: ...
\end{lstlisting}
Nevertheless, reversing the default action would have a non-trivial effect on case actions that compound, such as the above example of processing shell arguments.
Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called ©choose©, with no fall-through semantics.
The ©choose© statement is identical to the new ©switch© statement, except there is no implicit fall-through between case-clauses and the ©break© statement applies to the enclosing loop construct (as for the continue statement in a ©switch© statement).
It is still possible to fall-through if a case-clause ends with the new keyword fallthru, e.g.:
\begin{lstlisting}
choose ( i ) {
        int i;
  case 3, 4:
        i = 3;
        fallthru;
  case 8, 10:
  default:
        j = 3;
}
\end{lstlisting}
The ability to fall-through is retained because it is a sufficient C-idiom that most C programmers simply expect it, and its absence might discourage these programmers from using the choose statement.
\item
Eliminating Duff's device is straightforward and only invalidates a small amount of very questionable code.
The solution is to allow ©case© clauses to only appear at the same nesting level as the ©switch© body, as is done in most other programming languages with ©switch© statements.
\item
The issue of ©default© at locations other than at the end of the cause clause can be solved by using good programming style, and there are a few reasonable situations involving fall-through where the ©default© clause may appear is locations other than at the end.
Therefore, no language change is made for this issue.
\item
Dealing with unreachable code at the start of a ©switch© statement is solved by defining the declaration-list, including any associated initialization, at the start of a ©switch© statement body to be executed before the transfer to the appropriate ©case© clause.
This semantics is the same as for declarations at the start of a loop body, which are executed before each iteration of the loop body.
As well, this grammar does not allow statements to appear before the first ©case© clause.
The change is compatible for declarations with initialization in this context because existing code cannot assume the initialization has occurred.
The change is incompatible for statements, but any existing code using it is highly questionable, as in:
\begin{lstlisting}
switch ( i ) {
        L: x = 5;               // questionable code
  case 0:
        ...
}
\end{lstlisting}
The statement after the ©switch© can never be executed unless it is labelled.
If it is labelled, it must be transfered to from outside or inside the ©switch© statement, neither of which is acceptable control flow.
\end{enumerate}


\section{Case Clause}

C restricts the ©case© clause of a ©switch© statement to a single value.
For multiple ©case© clauses associated with the same statement, it is necessary to have multiple ©case© clauses rather than multiple values.
Requiring a ©case© clause for each value does not seem to be in the spirit of brevity normally associated with C.
Therefore, the ©case© clause is extended with a list of values, as in:
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{\hspace{20pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c@{\hspace{20pt}}}{\textbf{C}}        \\
\begin{lstlisting}
switch ( i ) {
  ®case 1, 3, 5®:
        ...
  ®case 2, 4, 6®:
        ...
}
\end{lstlisting}
&
\begin{lstlisting}
switch ( i ) {
  case 1: case 3 : case 5:
        ...
  case 2: case 4 : case 6:
        ...
}
\end{lstlisting}
&
\begin{lstlisting}

// odd values

// even values


\end{lstlisting}
\end{tabular}
\end{quote2}
In addition, two forms of subranges are allowed to specify case values: the GNU C form and a new \CFA form.
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{\hspace{20pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c@{\hspace{20pt}}}{\textbf{GNU C}}    \\
\begin{lstlisting}
switch ( i ) {
  ®case 1~5:®
        ...
  ®case 10~15:®
        ...
}
\end{lstlisting}
&
\begin{lstlisting}
switch ( i )
  case 1 ... 5:
        ...
  case 10 ... 15:
        ...
}
\end{lstlisting}
&
\begin{lstlisting}

// 1, 2, 3, 4, 5

// 10, 11, 12, 13, 14, 15


\end{lstlisting}
\end{tabular}
\end{quote2}


\section{Unnamed Structure Fields}

C requires each field of a structure to have a name, except for a bit field associated with a basic type, e.g.:
\begin{lstlisting}
struct {
        int f1;                 // named field
        int f2 : 4;             // named field with bit field size
        int : 3;                // unnamed field for basic type with bit field size
        int ;                   // disallowed, unnamed field
        int *;                  // disallowed, unnamed field
        int (*)(int);   // disallowed, unnamed field
};
\end{lstlisting}
This requirement is relaxed by making the field name optional for all field declarations; therefore, all the field declarations in the example are allowed.
As for unnamed bit fields, an unnamed field is used for padding a structure to a particular size.
A list of unnamed fields is also supported, e.g.:
\begin{lstlisting}
struct {
        int , , ;               // 3 unnamed fields
}
\end{lstlisting}


\section{Exception Handling}

Exception handling provides two mechanim: change of control flow from a raise to a handler, and commumication from the riase to the handler.
\begin{lstlisting}
exception void h( int i );
exception int h( int i, double d );

void f(...) {
        ... throw h( 3 );
        ... i = resume h( 3, 5.1 );
}

try {
        f(...);
} catch h( int w ) {
        // reset
} resume h( int p, double x ) {
        return 17;  // recover
} finally {
}
\end{lstlisting}
So the type raised would be the mangled name of the exception prototype and that name would be matched at the handler clauses by comparing the strings.
The arguments for the call would have to be packed in a message and unpacked at handler clause and then a call made to the handler.


\section{Types}

\subsection{Type Definitions}

\CFA allows users to define new types using the keyword type.

\begin{lstlisting}
// SensorValue is a distinct type and represented as an int
type SensorValue = int;
\end{lstlisting}

A type definition is different from a typedef in C because a typedef just creates an alias for a type,  while Do.s type definition creates a distinct type.
This means that users can define distinct function overloads for the new type (see Overloading for more information).
For example:

\begin{lstlisting}
type SensorValue = int;
void printValue(int v) {...}
void printValue(SensorValue v) {...}
void process(int v) {...}

SensorValue s = ...;

printValue(s); // calls version with SensorValue argument

printValue((int) s); // calls version with int argument

process(s); // implicit conversion to int
\end{lstlisting}

If SensorValue was defined with a typedef, then these two print functions would not have unique signatures.
This can be very useful to create a distinct type that has the same representation as another type.

The compiler will assume it can safely convert from the old type to the new type, implicitly.
Users may override this and define a function that must be called to convert from one type to another.

\begin{lstlisting}
type SensorValue = int;
// ()? is the overloaded conversion operator identifier
// This function converts an int to a SensorValue
SensorValue ()?(int val) {
        ...
}
void process(int v) {...}

SensorValue s = ...;
process(s); // implicit call to conversion operator
\end{lstlisting}

In many cases, it is not desired for the compiler to do this implicit conversion.
To avoid that, the user can use the explicit modifier on the conversion operator.
Any places where the conversion is needed but not explicit (with a cast), will result in a compile-time error.

\begin{lstlisting}
type SensorValue = int;

// conversion from int to SensorValue; must be explicit
explicit SensorValue ()?(int val) {
        ...
}

void process(int v) {...}

SensorValue s = ...;
process(s); // implicit cast to int: compile-time error
process((int) s); // explicit cast to int: calls conversion func
\end{lstlisting}

The conversion may not require any code, but still need to be explicit; in that case, the syntax can be simplified to:
\begin{lstlisting}
type SensorValue = int;
explicit SensorValue ()?(int);
void process(int v) {...}

SensorValue s = ...;
process(s); // compile-time error
process((int) s); // type is converted, no function is called
\end{lstlisting}


\subsection{Structures}

Structures in \CFA are basically the same as structures in C.
A structure is defined with the same syntax as in C.
When referring to a structure in \CFA, users may omit the struct keyword.
\begin{lstlisting}
struct Point {
        double x;
        double y;
};

Point p = {0.0, 0.0};
\end{lstlisting}

\CFA does not support inheritance among types, but instead uses composition to enable reuse of structure fields.
Composition is achieved by embedding one type into another.
When type A is embedded in type B, an object with type B may be used as an object of type A, and the fields of type A are directly accessible.
Embedding types is achieved using anonymous members.
For example, using Point from above:
\begin{lstlisting}
void foo(Point p);

struct ColoredPoint {
        Point; // anonymous member (no identifier)
        int Color;
};
...
        ColoredPoint cp = ...;
        cp.x = 10.3; // x from Point is accessed directly
        cp.color = 0x33aaff; // color is accessed normally
        foo(cp); // cp can be used directly as a Point
\end{lstlisting}


\subsection{Constructors and Destructors}

\CFA supports C initialization of structures, but it also adds constructors for more advanced initialization.
Additionally, \CFA adds destructors that are called when a variable is de-allocated (variable goes out of scope or object is deleted).
These functions take a reference to the structure as a parameter (see
References for more information).

\begin{figure}
\begin{lstlisting}
struct Widget {
        int id;
        float size;
        Parts *optionalParts;
};

// ?{} is the constructor operator identifier
// The first argument is a reference to the type to initialize
// Subsequent arguments can be specified for initialization

void ?{}(Widget &w) { // default constructor
        w.id = -1;
        w.size = 0.0;
        w.optionalParts = 0;
}

// constructor with values (does not need to include all fields)
void ?{}(Widget &w, int id, float size) {
        w.id = id;
        w.size = size;
        w.optionalParts = 0;
}

// ^? is the destructor operator identifier
void ^?(Widget &w) { // destructor
        w.id = 0;
        w.size = 0.0;
        if (w.optionalParts != 0) {
        // This is the only pointer to optionalParts, free it
        free(w.optionalParts);
        w.optionalParts = 0;
        }
}

Widget baz; // reserve space only
Widget foo{}; // calls default constructor
Widget bar{23, 2.45}; // calls constructor with values
baz{24, 0.91}; // calls constructor with values
?{}(baz, 24, 0.91}; // explicit call to constructor
^bar; // explicit call to destructor
^?(bar); // explicit call to destructor
\end{lstlisting}
\caption{Constructors and Destructors}
\end{figure}


\begin{comment}
\section{References}

\CFA supports reference types similar to rvalue references in \CC.
A reference is essentially an alias for a variable, allowing multiple names to refer to the same object.
A reference can be used as a safer alternative to a pointer, because it can be used to pass a variable by reference, but it must always reference an object.
It cannot be NULL, it must be assigned a value at initialization, and the object it references cannot change once it is set.
By introducing references in parameter types, users are given an easy way to pass a value by reference, without the need for NULL pointer checks.
In structures, a reference can replace a pointer to an object that should always have a valid value.
When a structure contains a reference, all of its constructors must initialize the reference and all instances of this structure must initialize it upon definition.

The syntax for using references in \CFA is the same as \CC with the exception of reference initialization.
Use ©&© to specify a reference, and access references just like regular objects, not like pointers (use dot notation to access fields).
When initializing a reference, \CFA uses a different syntax which differentiates reference initialization from assignment to a reference.
The ©&© is used on both sides of the expression to clarify that the address of the reference is being set to the address of the variable to which it refers.

\begin{figure}
\begin{lstlisting}
// parameter p is a reference to a Point
void movePointUp(Point &p) {
        p.y += 1.0; // Uses dot-notation to access fields
}

Point p1 = ...;
ColoredPoint cp1 = ...;
movePoint(p1); // reference to p1 passed to movePoint
movePoint(cp1); // reference to cp1 passed to movePoint

// a ListElement cannot be created without a valid list

struct ListElement {
        int element;
        List &list; // a list element has a reference to the list
}

// The constructor must initialize the reference
void ?{}(ListElement &le, int e, List &l) {
        le.element = e;
        &le.list = &l; // initialize the reference
}

ListElement e1{88, numberList}; // uses constructor
ListElement e2; // compiler error: uninitialized reference
Listing 10: References
\end{lstlisting}
\end{figure}
\end{comment}


\section{Overloading}

Overloading refers to the capability of a programmer to define and use multiple objects in a program with the same name.
In \CFA, a declaration may overload declarations from outer scopes with the same name, instead of hiding them as is the case in C.
This may cause identical C and \CFA programs to behave differently.
The compiler selects the appropriate object (overload resolution) based on context information at the place where it is used.
Overloading allows programmers to give functions with different signatures but similar semantics the same name, simplifying the interface to users.
Disadvantages of overloading are that it can be used to give functions with different semantics the same name, causing confusion, or that the compiler may resolve to a different function from what the programmer expected.
\CFA allows overloading of functions, operators, variables, and even the constants 0 and 1.

The compiler follows some overload resolution rules to determine the best interpretation of all of these overloads.
The best valid interpretations are the valid interpretations that use the fewest unsafe conversions.
Of these, the best are those where the functions and objects involved are the least polymorphic.
Of these, the best have the lowest total conversion cost, including all implicit conversions in the argument expressions.
Of these, the best have the highest total conversion cost for the implicit conversions (if any) applied to the argument expressions.
If there is no single best valid interpretation, or if the best valid interpretation is ambiguous, then the resulting interpretation is ambiguous.
For details about type inference and overload resolution, please see the \CFA Language Specification.
\begin{lstlisting}
int foo(int a, int b) {
        float sum = 0.0;
        float special = 1.0;
        {
                int sum = 0;
                // both the float and int versions of sum are available
                float special = 4.0;
                // this inner special hides the outer version
                ...
        }
        ...
}
\end{lstlisting}


\subsection{Overloaded Constant}

The constants 0 and 1 have special meaning.
In \CFA, as in C, all scalar types can be incremented and
decremented, which is defined in terms of adding or subtracting 1.
The operations ©&&©, ©||©, and ©!© can be applied to any scalar arguments and are defined in terms of comparison against 0 (ex. ©(a && b)© becomes ©(a != 0 && b != 0)©).

In C, the integer constants 0 and 1 suffice because the integer promotion rules can convert them to any
arithmetic type, and the rules for pointer expressions treat constant expressions evaluating to 0 as a
special case.
However, user-defined arithmetic types often need the equivalent of a 1 or 0 for their
functions or operators, polymorphic functions often need 0 and 1 constants of a type matching their
polymorphic parameters, and user-defined pointer-like types may need a null value.
Defining special
constants for a user-defined type is more efficient than defining a conversion to the type from ©_Bool©.

Why just 0 and 1? Why not other integers? No other integers have special status in C.
A facility that let programmers declare specific constants..const Rational 12., for instance. would not be much of an improvement.
Some facility for defining the creation of values of programmer-defined types from arbitrary integer tokens would be needed.
The complexity of such a feature doesn.t seem worth the gain.

For example, to define the constants for a complex type, the programmer would define the following:

\begin{lstlisting}
struct Complex {
        double real;
        double imaginary;
}

const Complex 0 = {0, 0};
const Complex 1 = {1, 0};
...

        Complex a = 0;
...

        a++;
...
        if (a) { // same as if (a == 0)
...
}
\end{lstlisting}


\subsection{Variable Overloading}

The overload rules of \CFA allow a programmer to define multiple variables with the same name, but different types.
Allowing overloading of variable names enables programmers to use the same name across multiple types, simplifying naming conventions and is compatible with the other overloading that is allowed.
For example, a developer may want to do the following:
\begin{lstlisting}
int pi = 3;
float pi = 3.14;
char pi = .p.;
\end{lstlisting}


\subsection{Function Overloading}

Overloaded functions in \CFA are resolved based on the number and type of arguments, type of return value, and the level of specialization required (specialized functions are preferred over generic).

The examples below give some basic intuition about how the resolution works.
\begin{lstlisting}
// Choose the one with less conversions
int doSomething(int value) {...} // option 1
int doSomething(short value) {...} // option 2

int a, b = 4;
short c = 2;

a = doSomething(b); // chooses option 1
a = doSomething(c); // chooses option 2

// Choose the specialized version over the generic

generic(type T)
T bar(T rhs, T lhs) {...} // option 3
float bar(float rhs, float lhs){...} // option 4
float a, b, c;
double d, e, f;
c = bar(a, b); // chooses option 4

// specialization is preferred over unsafe conversions

f = bar(d, e); // chooses option 5
\end{lstlisting}


\subsection{Operator Overloading}

\CFA also allows operators to be overloaded, to simplify the use of user-defined types.
Overloading the operators allows the users to use the same syntax for their custom types that they use for built-in types, increasing readability and improving productivity.
\CFA uses the following special identifiers to name overloaded operators:

\begin{table}[hbt]
\hfil
\begin{tabular}[t]{ll}
%identifier & operation \\ \hline
©?[?]© & subscripting \impl{?[?]}\\
©?()© & function call \impl{?()}\\
©?++© & postfix increment \impl{?++}\\
©?--© & postfix decrement \impl{?--}\\
©++?© & prefix increment \impl{++?}\\
©--?© & prefix decrement \impl{--?}\\
©*?© & dereference \impl{*?}\\
©+?© & unary plus \impl{+?}\\
©-?© & arithmetic negation \impl{-?}\\
©~?© & bitwise negation \impl{~?}\\
©!?© & logical complement \impl{"!?}\\
©?*?© & multiplication \impl{?*?}\\
©?/?© & division \impl{?/?}\\
\end{tabular}\hfil
\begin{tabular}[t]{ll}
%identifier & operation \\ \hline
©?%?© & remainder \impl{?%?}\\
©?+?© & addition \impl{?+?}\\
©?-?© & subtraction \impl{?-?}\\
©?<<?© & left shift \impl{?<<?}\\
©?>>?© & right shift \impl{?>>?}\\
©?<?© & less than \impl{?<?}\\
©?<=?© & less than or equal \impl{?<=?}\\
©?>=?© & greater than or equal \impl{?>=?}\\
©?>?© & greater than \impl{?>?}\\
©?==?© & equality \impl{?==?}\\
©?!=?© & inequality \impl{?"!=?}\\
©?&?© & bitwise AND \impl{?&?}\\
\end{tabular}\hfil
\begin{tabular}[t]{ll}
%identifier & operation \\ \hline
©?^?© & exclusive OR \impl{?^?}\\
©?|?© & inclusive OR \impl{?"|?}\\
©?=?© & simple assignment \impl{?=?}\\
©?*=?© & multiplication assignment \impl{?*=?}\\
©?/=?© & division assignment \impl{?/=?}\\
©?%=?© & remainder assignment \impl{?%=?}\\
©?+=?© & addition assignment \impl{?+=?}\\
©?-=?© & subtraction assignment \impl{?-=?}\\
©?<<=?© & left-shift assignment \impl{?<<=?}\\
©?>>=?© & right-shift assignment \impl{?>>=?}\\
©?&=?© & bitwise AND assignment \impl{?&=?}\\
©?^=?© & exclusive OR assignment \impl{?^=?}\\
©?|=?© & inclusive OR assignment \impl{?"|=?}\\
\end{tabular}
\hfil
\caption{Operator Identifiers}
\label{opids}
\end{table}

These identifiers are defined such that the question marks in the name identify the location of the operands.
These operands represent the parameters to the functions, and define how the operands are mapped to the function call.
For example, ©a + b© becomes ©?+?(a, b)©.

In the example below, a new type, myComplex, is defined with an overloaded constructor, + operator, and string operator.
These operators are called using the normal C syntax.

\begin{lstlisting}
type Complex = struct { // define a Complex type
        double real;
        double imag;
}

// Constructor with default values

void ?{}(Complex &c, double real = 0.0, double imag = 0.0) {
        c.real = real;
        c.imag = imag;
}

Complex ?+?(Complex lhs, Complex rhs) {
        Complex sum;
        sum.real = lhs.real + rhs.real;
        sum.imag = lhs.imag + rhs.imag;
        return sum;
}

String ()?(const Complex c) {
        // use the string conversions for the structure members
        return (String)c.real + . + . + (String)c.imag + .i.;
}
...

Complex a, b, c = {1.0}; // constructor for c w/ default imag
...
c = a + b;
print(.sum = . + c);
\end{lstlisting}


\section{Auto Type-Inferencing}

Auto type-inferencing occurs in a declaration where a variable's type is inferred from its initialization expression type.
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}ll@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CC}}        & \multicolumn{1}{c}{©gcc©}\index{gcc} \\
\begin{lstlisting}

auto j = 3.0 * 4;
int i;
auto k = i;
\end{lstlisting}
&
\begin{lstlisting}
#define expr 3.0 * i
typeof(expr) j = expr;
int i;
typeof(i) k = i;
\end{lstlisting}
&
\begin{lstlisting}

// use type of initialization expression

// use type of primary variable
\end{lstlisting}
\end{tabular}
\end{quote2}
The two important capabilities are:
\begin{itemize}
\item
preventing having to determine or write out long generic types,
\item
ensure secondary variables, related to a primary variable, always have the same type.
\end{itemize}

In \CFA, ©typedef© provides a mechanism to alias long type names with short ones, both globally and locally, but not eliminate the use of the short name.
©gcc© provides ©typeof© to declare a secondary variable from a primary variable.
\CFA also relies heavily on the specification of the left-hand side of assignment for type inferencing, so in many cases it is crucial to specify the type of the left-hand side to select the correct type of the right-hand expression.
Only for overloaded routines with the same return type is variable type-inferencing possible.
Finally, ©auto© presents the programming problem of tracking down a type when the type is actually needed.
For example, given
\begin{lstlisting}
auto j = ®...®
\end{lstlisting}
and the need to write a routine to compute using ©j©
\begin{lstlisting}
void rtn( ®...® parm );
rtn( j );
\end{lstlisting}
A programmer must work backwards to determine the type of ©j©'s initialization expression, reconstructing the possibly long generic type-name.
In this situation, having the type name or a short alias is very useful.

There is also the conundrum in type inferencing of when to \emph{\Index{brand}} a type.
That is, when is the type of the variable more important than the type of its initialization expression.
For example, if a change is made in an initialization expression, it can cause hundreds or thousands of cascading type changes and/or errors.
At some point, a programmer wants the type of the variable to remain constant and the expression to be in error when it changes.

Given ©typedef© and ©typeof© in \CFA, and the strong need to use the type of left-hand side in inferencing, auto type-inferencing is not supported at this time.
Should a significant need arise, this feature can be revisited.


\section{Generics}

\CFA supports parametric polymorphism to allow users to define generic functions and types.
Generics allow programmers to use type variables in place of concrete types so that the code can be reused with multiple types.
The type parameters can be restricted to satisfy a set of constraints.
This enables \CFA to build fully compiled generic functions and types, unlike other languages like \CC where templates are expanded or must be explicitly instantiated.


\subsection{Generic Functions}

Generic functions in \CFA are similar to template functions in \CC, and will sometimes be expanded into specialized versions, just like in \CC.
The difference, however, is that generic functions in \CFA can also be separately compiled, using function pointers for callers to pass in all needed functionality for the given type.
This means that compiled libraries can contain generic functions that can be used by programs linked with them (statically or dynamically).
Another advantage over \CC templates is unlike templates, generic functions are statically checked, even without being instantiated.

A simple example of using Do.s parametric polymorphism to create a generic swap function would look like this:

\begin{lstlisting}
generic(type T)
void swap(T &a, T &b) {
        T tmp = a;
        a = b;
        b = a;
}

int a, b;
swap(a, b);

Point p1, p2;
swap(p1, p2);
\end{lstlisting}

Here, instead of specifying types for the parameters a and b, the function has a generic type parameter, type T.
This function can be called with any type, and the compiler will handle generating the proper code for that type, using call site inference to determine the appropriate value for T.


\subsection{Bounded Quantification}

Some generic functions only work (or make sense) for any type that satisfies a given property.
For example, here is a function to pick the minimum of two values of some type.
\begin{lstlisting}
generic (type T | bool ?<?(T, T) )

T min(T a, T b) {
        return a < b ? a : b;
}
\end{lstlisting}

It only makes sense to call min with values of a type that has an ordering: a way to decide whether one value is less than another.
The ordering function used here is the less than operator, <.
The syntax used to reference the operator is discussed in further detail in Operator Overloading.
In \CFA, this assertion on the type of a generic is written as the bound, (type T | bool ?<?(T, T)).
The \CFA compiler enforces that minis only called with types for which the less than operator is defined, and reports a compile-time error otherwise.

Bounds can also involve multiple types, and multiple requirements, as shown below:
\begin{lstlisting}
generic (type T, type U | { T foo(T, U); U bar(U); })

T baz(T t, U u) {
        return foo(t, bar(u));
}
\end{lstlisting}


\subsection{Interfaces}

Type bounds as shown above are not very informative, merely requiring that a function exists with the right name and type.
Suppose you try to call a polymorphic function and \CFA gives you an error that int combine(int, int) is not defined.
Can you define it? What is it supposed to do? Perhaps it should compute the sum, or the bitwise and, or the maximum, or the least common multiple; or perhaps it's an operation that can't be defined for integers.
The function signature doesn't say.

Interfaces gather together a set of function signatures under a common name, which solves two problems.
First, an interface name can be used in type bounds instead of function signatures.
This avoids repetition when a bound is used in many functions.
Second, interfaces explicitly document the existence of a commonly used set of functionality, making programs easier to understand.
\begin{lstlisting}
generic (type T)
interface Orderable {
        bool ?<?(T, T);
};

generic (type T | Orderable(T))
T min(T a, T b) {
        return a < b ? a : b;
}
\end{lstlisting}

This definition of the interface Orderable makes the generic function min easier to read and understand.
Orderable can also be reused for other generic functions, max for example.
Interfaces can also build on top of other interfaces.
For example:
\begin{lstlisting}
generic (type T | Orderable(T)
interface FooBarable {
        int foo(T, T);
        int Bar(T, T);
};
\end{lstlisting}

The FooBarable interface specifies all of the bounds of the Orderable interface, plus the additional bounds specified in its definition.
A type does not need to specify that it satisfies any interface, the compiler can figure this out at compile time.
For example, there is no need to add some special syntax to show that a type implements the Orderable interface, just define a ?<? operator and it is satisfied.


\subsection{Generic Typedefs}

Type synonyms can be defined generically using the typedef keyword together with a generic type annotation.
These can be used to abbreviate complicated type expressions, especially in generic code.
\begin{lstlisting}
// typedef the generic function pointers for later use

generic(type T)
typedef int (*predicate)(T);
generic(type Captured, type T)
typedef void (*callback)(Captured, T);

generic(type T)
void find(int length, T *array,
        predicate(T) p, callback(void *, T)f) {
        int i;
        for (i = 0; i < length; i++)
        if (p(array[i])) f(NULL, array[i]);
}
\end{lstlisting}


\subsection{Generic Types}

Generic types are defined using the same mechanisms as those described above for generic functions.
This feature allows users to create types that have one or more fields that use generic parameters as types, similar to a template classes in \CC.
For example, to make a generic linked list, a placeholder is created for the type of the elements, so that the specific type of the elements in the list need not be specified when defining the list.
In C, something like this would have to be done using void pointers and unsafe casting.
As in generic functions, Do.s generic types are different from \CC templates in that they can be fully compiled, while \CC templates are more like macro expansions.
This means that a \CFA generic type from a compiled library can be used with any type that satisfies the bounds.

The syntax for defining a generic type looks very similar to that of a generic function.
Generic types support bounds and interfaces, using the same syntax as generic functions.
\begin{lstlisting}
generic (type T)
struct LinkedListElem {
        T elem;
        LinkedListElem(T) *next;
};

LinkedListElem *++?(LinkedListElem **elem) {
        return *elem = elem->next;
}

generic (type T)
struct LinkedList {
        LinkedListElem(T) *head;
        unsigned int size;
}

generic (type T | bool ?==?(T, T))
bool contains(LinkedList(T) *list, T elem) {
        for(LinkedListElem *iter = list->head; iter != 0; ++iter) {
        if (iter->elem == elem) return true;
        }
        return false;
}
\end{lstlisting}


\section{Safety}

Safety, along with productivity, is a key goal of Do.
This section discusses the safety features that have been included in \CFA to help programmers create more stable, reliable, and secure code.


\subsection{Exceptions}

\CFA introduces support for exceptions as an easier way to recover from exceptional conditions that may be detected within a block of code.
In C, developers can use error codes and special return values to report to a caller that an error occurred in a function.
The major problem with error codes is that they can be easily ignored by the caller.
Failure to properly check for errors can result in the caller making incorrect assumptions about the current state or about the return value that are very likely to result in errors later on in the program, making the source of the problem more difficult to find when debugging.
An unhandled exception on the other hand will cause a crash, revealing the original source of the erroneous state.

Exceptions in \CFA allow a different type of control flow.
Throwing an exception terminates execution of the current block, invokes the destructors of variables that are local to the block, and propagates the exception to the parent block.
The exception is immediately re-thrown from the parent block unless it is caught as described below.
\CFA uses keywords similar to \CC for exception handling.
An exception is thrown using a throw statement, which accepts one argument.

\begin{lstlisting}
        ...

        throw 13;

        ...
\end{lstlisting}

An exception can be caught using a catch statement, which specifies the type of the exception it can catch.
A catch is specified immediately after a guarded block to signify that it can catch an exception from that block.
A guarded block is specified using the try keyword, followed by a block of code inside of curly braces.

\begin{lstlisting}
        ...

        try {
                throw 13;
        }
        catch(int e) {
                printf(.caught an exception: %d\n., e);
        }
\end{lstlisting}


\subsection{Memory Management}


\subsubsection{Manual Memory Management}

Using malloc and free to dynamically allocate memory exposes several potential, and common, errors.
First, malloc breaks type safety because it returns a pointer to void.
There is no relationship between the type that the returned pointer is cast to, and the amount of memory allocated.
This problem is solved with a type-safe malloc.
Do.s type-safe malloc does not take any arguments for size.
Instead, it infers the type based on the return value, and then allocates space for the inferred type.

\begin{lstlisting}
float *f = malloc(); // allocates the size of a float

struct S {
        int i, j, k;
};

struct S *s = malloc(); // allocates the size of a struct S
\end{lstlisting}

In addition to the improved malloc, \CFA also provides a technique for combining allocation and initialization into one step, using the new function.
For all constructors defined for a given type (see Operator Overloading), a corresponding call to new can be used to allocate and construct that type.

\begin{lstlisting}
type Complex = struct {
        float real;
        float imag;
};

// default constructor

void ?{}(Complex &c) {
        c.real = 0.0;
        c.imag = 0.0;
}



// 2 parameter constructor

void ?{}(Complex &c, float real, float imag) {
        c.real = real;
        c.imag = imag;
}


int main() {
        Complex c1; // No constructor is called
        Complex c2{}; // Default constructor called
        Complex c3{1.0, -1.0}; // 2 parameter constructor is called

        Complex *p1 = malloc(); // allocate
        Complex *p2 = new(); // allocate + default constructor
        Complex *p3 = new(0.5, 1.0); // allocate + 2 param constructor
}

\end{lstlisting}


\subsubsection{Automatic Memory Management}

\CFA may also support automatic memory management to further improve safety.
If the compiler can insert all of the code needed to manage dynamically allocated memory (automatic reference counting), then developers can avoid problems with dangling pointers, double frees, memory leaks, etc.
This feature requires further investigation.
\CFA will not have a garbage collector, but might use some kind of region-based memory management.


\subsection{Unsafe C Constructs}

C programmers are able to access all of the low-level tricks that are sometimes needed for close-to-the-hardware programming.
Some of these practices however are often error-prone and difficult to read and maintain.
Since \CFA is designed to be safer than C, such constructs are disallowed in \CFA code.
If a programmer wants to use one of these unsafe C constructs, the unsafe code must be contained in a C linkage block (see Interoperability), which will be compiled like C code.
This block means that the user is telling the tools, .I know this is unsafe, but I.m going to do it anyway..

The exact set of unsafe C constructs that will be disallowed in \CFA has not yet been decided, but is sure to include pointer arithmetic, pointer casting, etc.
Once the full set is decided, the rules will be listed here.


\section{Syntactic Anomalies}

The number 0 and 1 are treated specially in \CFA, and can be redefined as variables.
One syntactic anomaly is when a field in an structure is names 0 or 1:
\begin{lstlisting}
struct S {
        int 0, 1;
} s;
\end{lstlisting}
The problem occurs in accesing these fields using the selection operation ``©.©'':
\begin{lstlisting}
s.0 = 0;        // ambiguity with floating constant .0
s.1 = 1;        // ambiguity with floating constant .1
\end{lstlisting}
To make this work, a space is required after the field selection:
\begin{lstlisting}
®s.§\textvisiblespace§0® = 0;
®s.§\textvisiblespace§1® = 1;
\end{lstlisting}
While this sytact is awkward, it is unlikely many programers will name fields of a structure 0 or 1.
Like the \CC lexical problem with closing template-syntax, e.g, ©Foo<Bar<int®>>®©, this issue can be solved with a more powerful lexer/parser.

There are several ambiguous cases with operator identifiers, e.g., ©int *?*?()©, where the string ©*?*?© can be lexed as ©*©/©?*?© or ©*?©/©*?©.
Since it is common practise to put a unary operator juxtaposed to an identifier, e.g., ©*i©, users will be annoyed if they cannot do this with respect to operator identifiers.
Even with this special hack, there are 5 general cases that cannot be handled.
The first case is for the function-call identifier ©?()©:
\begin{lstlisting}
int *§\textvisiblespace§?()();  // declaration: space required after '*'
*§\textvisiblespace§?()();              // expression: space required after '*'
\end{lstlisting}
Without the space, the string ©*?()© is ambiguous without N character look ahead;
it requires scanning ahead to determine if there is a ©'('©, which is the start of an argument/parameter list.

The 4 remaining cases occur in expressions:
\begin{lstlisting}
i++§\textvisiblespace§?i:0;             // space required before '?'
i--§\textvisiblespace§?i:0;             // space required before '?'
i§\textvisiblespace§?++i:0;             // space required after '?'
i§\textvisiblespace§?--i:0;             // space required after '?'
\end{lstlisting}
In the first two cases, the string ©i++?© is ambiguous, where this string can be lexed as ©i© / ©++?© or ©i++© / ©?©;
it requires scanning ahead to determine if there is a ©'('©, which is the start of an argument list.
In the second two cases, the string ©?++x© is ambiguous, where this string can be lexed as ©?++© / ©x© or ©?© / y©++x©;
it requires scanning ahead to determine if there is a ©'('©, which is the start of an argument list.


\section{Concurrency}

Today's processors for nearly all use cases, ranging from embedded systems to large cloud computing servers, are composed of multiple cores, often heterogeneous.
As machines grow in complexity, it becomes more difficult for a program to make the most use of the hardware available.
\CFA includes built-in concurrency features to enable high performance and improve programmer productivity on these multi-/many-core machines.

Concurrency support in \CFA is implemented on top of a highly efficient runtime system of light-weight, M:N, user level threads.
The model integrates concurrency features into the language by making the structure type the core unit of concurrency.
All communication occurs through method calls, where data is sent via method arguments, and received via the return value.
This enables a very familiar interface to all programmers, even those with no parallel programming experience.
It also allows the compiler to do static type checking of all communication, a very important safety feature.
This controlled communication with type safety has some similarities with channels in Go, and can actually implement
channels exactly, as well as create additional communication patterns that channels cannot.
Mutex objects, monitors, are used to contain mutual exclusion within an object and synchronization across concurrent threads.

Three new keywords are added to support these features:

monitor creates a structure with implicit locking when accessing fields

mutex implies use of a monitor requiring the implicit locking

task creates a type with implicit locking, separate stack, and a thread


\subsection{Monitors}

A monitor is a structure in \CFA which includes implicit locking of its fields.
Users of a monitor interact with it just like any structure, but the compiler handles code as needed to ensure mutual exclusion.
An example of the definition of a monitor is shown here:
\begin{lstlisting}
type Account = monitor {
        const unsigned long number; // account number
        float balance; // account balance
};
\end{lstlisting}

Since a monitor structure includes an implicit locking mechanism, it does not make sense to copy a monitor;
it is always passed by reference.
Users can specify to the compiler whether or not a function will require mutual exclusion of the monitor using the mutex modifier on the parameter.
When mutex is specified, the compiler inserts locking before executing the body of the function, and unlocking after the body.
This means that a function requiring mutual exclusion could block if the lock is already held by another thread.
Blocking on a monitor lock does not block the kernel thread, it simply blocks the user thread, which yields its kernel thread while waiting to obtain the lock.
If multiple mutex parameters are specified, they will be locked in parameter order (i.e. first parameter is locked first) and unlocked in the
reverse order.
\begin{lstlisting}
// This function accesses a constant field, it does not require
// mutual exclusion

export unsigned long getAccountNumber(Account &a) {
        return a.number;
}

// This function accesses and modifies a shared field; it
// requires mutual exclusion

export float withdrawal(mutex Account &a, float amount) {
        a.balance -= amount;
        return a.balance;
}
\end{lstlisting}

Often, one function using a monitor will call another function using that same monitor.
If both require mutual exclusion, then the thread would be waiting for itself to release the lock when it calls the inner function.
This situation is resolved by allowing recursive entry (reentrant locks), meaning that if the lock is already held by the caller, it can be locked again.
It will still be unlocked the same number of times.
An example of this situation is shown below:

\begin{lstlisting}
// deleting a job from a worker requires mutual exclusion

void deleteJob(mutex Worker &w, Job &j) {
        ...
}

// transferring requires mutual exclusion and calls deleteJob

void transferJob(mutex Worker &from, Worker &to) {
        ...
        deleteJob(j);
        ...
}
\end{lstlisting}


\subsection{Tasks}

\CFA also provides a simple mechanism for creating and utilizing user level threads.
A task provides mutual exclusion like a monitor, and also has its own execution state and a thread of control.
Similar to a monitor, a task is defined like a structure:
\begin{lstlisting}
type Adder = task {
        int *row;
        int size;
        int &subtotal;
}
\end{lstlisting}

A task may define a constructor, which will be called upon allocation and run on the caller.s thread.
A destructor may also be defined, which is called at de-allocation (when a dynamic object is deleted or when a local object goes out of scope).
After a task is allocated and initialized, its thread is spawned implicitly and begins executing in its function call method.
All tasks must define this function call method, with a void return value and no additional parameters, or the compiler will report an error.
Below are example functions for the above Adder task, and its usage to sum up a matrix on multiple threads.
(Note that this example is designed to display the syntax and functionality, not the best method to solve this problem)
\begin{lstlisting}
void ?{}(Adder &a, int r[], int s, int &st) { // constructor
        a.row = r;
        a.size = s;
        a.subtotal = st;
}

// implicitly spawn thread and begin execution here

void ?()(Adder &a) {
        int c;
        subtotal = 0;
        for (c=0; c<a.size; ++c) {
        subtotal += row[c];
        }
}

int main() {
        const int rows = 100, cols = 1000000;
        int matrix[rows][cols];
        int subtotals[rows];
        int total = 0;
        int r;

        { // create a new scope here for our adders
        Adder adders[rows];
        // read in the matrix
        ...
        for (r=0; r<rows; ++r) {
        // tasks are initialized on this thread
        Adders[r] = {matrix[r], cols, subtotals[r]};
        Adders[r](); // spawn thread and begin execution
        }
        } // adders go out of scope; block here until they all finish
        total += subtotals[r];
        printf(.total is %d\n., total);
}
\end{lstlisting}


\subsection{Cooperative Scheduling}

Tasks in \CFA are cooperatively scheduled, meaning that a task will not be interrupted by another task, except at specific yield points.
In Listing 31, there are no yield points, so each task runs to completion with no interruptions.
Places where a task could yield include waiting for a lock (explicitly or implicitly), waiting for I/O, or waiting for a specific function (or one of a set of functions) to be called.
This last option is introduced with the yield function. yield is used to indicate that this task should yield its thread until the specified function is called.
For example, the code below defines a monitor that maintains a generic list.
When a task tries to pop from the list, but it is empty, the task should yield until another task puts something into the list, with the push function.
Similarly, when a task tries to push something onto the list, but it is full, it will yield until another task frees some space with the pop function.

\begin{lstlisting}
// type T is used as a generic type for all definitions inside
// the curly brackets

generic(type T) {
        type Channel = monitor {
        List(T) list; // list is a simple generic list type
        };

        T pop(mutex &Channel(T) ch) {
        if (ch.list.empty()) {
        // yield until push is called for this channel
        yield(push);
        }
        return ch.list.pop();
        }

        void push(mutex &Channel(T)ch, T val) {
        if (ch.list.full()) {
        // yield until pop is called for this channel
        yield(pop);
        }
        ch.list.push(val);
        }
}
\end{lstlisting}

A task can also yield indefinitely by calling yield with no arguments.
This will tell the scheduler to yield this task until it is resumed by some other task.
A task can resume another task by using its functional call operator.
The code below shows a simple ping-pong example, where two tasks yield back and forth to each other using these methods.

\begin{lstlisting}
type Ping = task {
        Pong *partner;
};

void ?{}(Ping &p, Pong *partner = 0) {
        p.partner = partner;
}

void ?()(Ping &p) {
        for(;;) { // loop forever
        printf(.ping\n.);
        partner(); // resumes the partner task
        yield(); // yields this task
        }
}

type Pong = task {
        Ping *partner;
};

void ?{}(Pong &p, Ping *partner = 0) {
        p.partner = partner;
}

void ?()(Pong &p) {
        for(;;) { // loop forever
        yield(); // yields this task
        printf(.pong/n.);
        partner(); // resumes the partner task
        }
}

void main() {
        Ping ping; // allocate ping
        Pong pong{ping}; // allocate, initialize, and start pong
        Ping{pong}; // initialize and start ping
}
\end{lstlisting}

The same functionality can be accomplished by providing functions to be called by the partner task.
\begin{lstlisting}
type Pingpong = task {
        String msg;
        Pingpong *partner;
};

void ?{}(Pingpong &p, String msg, Pingpong *partner = 0) {
        p.msg = msg;
        p.partner = partner;
}

void ?()(Pingpong &p) {
        for(;;) {
        yield(go);
        }
}

void go(Pingpong &p) {
        print(.%(p.msg)\n.);
        go(p.partner);
}

void main() {
        Pingpong ping = {.ping.};
        Pingpong pong = {.pong., ping};
        ping.partner = pong;
        go(ping);
}
\end{lstlisting}


\section{Modules and Packages }

\begin{comment}
High-level encapsulation is useful for organizing code into reusable units, and accelerating compilation speed.
\CFA provides a convenient mechanism for creating, building and sharing groups of functionality that enhances productivity and improves compile time.

There are two levels of encapsulation in \CFA, module and package.
A module is a logical grouping of functionality that can be easily pulled into another project, much like a module in Python or a package in Go.
A module forms a namespace to limit the visibility and prevent naming conflicts of variables.
Furthermore, a module is an independent translation unit, which can be compiled separately to accelerate the compilation speed.

A package is a physical grouping of one or more modules that is used for code distribution and version management.
Package is also the level of granularity at which dependences are managed.
A package is similar to the Crate in Rust.


\subsection{No Declarations, No Header Files}

In C and \CC, it is necessary to declare or define every global variable, global function, and type before it is used in each file.
Header files and a preprocessor are normally used to avoid repeating code.
Thus, many variables, functions, and types are described twice, which exposes an opportunity for errors and causes additional maintenance work.
Instead of following this model, the \CFA tools can extract all of the same information from the code automatically.
This information is then stored in the object files for each module, in a format that can quickly be read by the compiler, and stored at the top of the file, for quick access.
In addition to the user productivity improvements, this simple change also improves compile time, by saving the information in a simple machine readable format, instead of making the compiler parse the same information over and over from a header file.
This seems like a minor change, but according to (Pike, Go at Google: Language Design in the Service of Software Engineering), this simple change can cause massive reductions in compile time.

In \CFA, multiple definitions are not necessary.
Within a module, all of the module's global definitions are visible throughout the module.
For example, the following code compiles, even though isOdd was not declared before being called:
\begin{lstlisting}
bool isEven(unsigned int x) {
        if (x == 0) return true;
        else return !isOdd(x);
}

bool isOdd(unsigned int x) {
        if (x == 1) return true;
        else return !isEven(x - 2);
}
\end{lstlisting}

Header files in C are used to expose the declarations from a library, so that they can be used externally.
With \CFA, this functionality is replaced with module exports, discussed below.
When building a \CFA module which needs to be callable from C code, users can use the tools to generate a header file suitable for including in these C files with all of the needed declarations.

In order to interoperate with existing C code, \CFA files can still include header files, the contents of which will be enclosed in a C linkage section to indicate C calling conventions (see Interoperability for more information).


\subsection{Modules}

A module typically contains a set of related types and methods, with some objects accessible from outside the package, and some limited to use inside the module.
These modules can then be easily shared and reused in multiple projects.
As modules are intended to be distributed for reuse, they should generally have stable, well-defined interfaces.

\CFA adds the following keywords to express the module systems: module, export, import, as.


\subsubsection{Module Declaration}

The syntax to declare a module is module moduleName;.

The module declaration must be at the beginning of a file, and each file can only belong to one module.
If there is no module declaration at the beginning of a file, the file belongs to the global module.
A module can span several files.
By convention, a module and the files belonging to the module have additional mapping relationship which is described in the Do-Lang Tooling documentation.

The moduleName follows the same rules of a variable name, except that it can use slash "/" to indicate the module/sub-module relationship.
For example, container/vector is a valid module name, where container is the parent module name, and vector is the sub-module under container.

Only the interfaces of a module are visible from outside, when the module is imported. export is a type decorator to declare a module interface.
A method, a global variable or a type can be declared as a module interface.
Types defined in a module and referenced by an exported function or a variable must be exported, too.

The following code is a simple module declaration example.
\begin{lstlisting}
module M;

//visible outside module M

export int f(int i) { return i + 1; }
export double aCounter;

//not visible outside module M

int g(int i) { return i - 1; }

double bCounter;
\end{lstlisting}

export module moduleName; can be use to re-export all the visible (exported) names in moduleName from the current module.


\subsubsection{Module Import}

The syntax to import a module is import moduleName; or import moduleName as anotherName;.
One package cannot be imported with both of the two types of syntax in one file.
A package imported in one file will only be visible in this file.
For example, two files, A and B belong to the same module.
If file A imports another module, M, the exported names in M are not visible in file B.

All of the exported names are visible in the file that imports the module.
The exported names can be accessed within a namespace based on the module name in the first syntax (ex moduleName.foo).
If moduleName has several elements separated by '/' to describe a sub-module (ex. import container/vector;), the last element in the moduleName is used as the namespace to access the visible names in that module (ex vector.add(...);).
The as keyword is used to confine the imported names in a unique namespace (ex. anotherName.foo). anotherName must be a valid identifier (same rules as a variable name) which means it cannot have '/' in it.
Conflicts in namespaces will be reported by the compiler.
The second method can be used to solve conflicting name problems.
The following code snippets show the two situations.

\begin{lstlisting}
module util/counter;
export int f(int i) { return i+1; }

import util/counter;

int main() {
        return counter.f(200); // f() from the package counter
}

import util/counter as ct;
int main() {
        return ct.f(200); // f() from the package counter
}
\end{lstlisting}


Additionally, using the .as. syntax, a user can force the compiler to add the imported names into the current namespace using .as ..With these module rules, the following module definitions and imports can be achieved without any problem.

\begin{lstlisting}
module M1;
export int f(int i) { return i+1;} // visible outside

int g(int i) { return i-1;} // not visible outside

module M2;
int f(int i) { return i * 2; } // not visible outside
export int g(int g) { return i / 2; } // visible outside

import M1 as .;

import M2 as .;


int main() {
        return f(3) + g(4); //f() from M1 and g() from M2;
}
\end{lstlisting}


\subsubsection{Sub-Module and Module Aggregation}

Several modules can be organized in a parent module and sub-modules relationship.
The sub-module names are based on hierarchical naming, and use slash, "/", to indicate the relationship.
For example, std/vector and std/io are sub-modules of module std.
The exported names in a sub-module are NOT visible if the parent module is imported, which means the exported names in the sub-module are
not implicitly exported in the parent module.

Aggregation is a mechanism to support components and simplified importing.
The mechanism is not based on naming but based on manual declaration.
For example, the following is the aggregated sequence module.
The export {...} is syntactic sugar for many lines of export module aModule;.
If an aggregated module is imported, all the included modules in the aggregation are imported.

\begin{lstlisting}
module std/sequence;

export {
        module std/vector;
        module std/list;
        module std/array;
        module std/deque;
        module std/forward_list;
        module std/queue;
        module std/stack;
};
\end{lstlisting}

After importing the aggregated module, each individual name is still contained in the original name space.
For example, vector.add() and list.add() should be used to reference the add methods if there are add methods in both the vector module and the list module.


\subsubsection{Import from Repository}

When a module is imported, the tools locate the module in the one of the accessible package paths (defined by command line flag or environment variable).
The tools also support retrieving modules of a package from external repositories.
See Listing 40: Package directory structure


\subsubsection{Package Import}

Because packages are the places where the building tool looks for modules, there is no code required in the \CFA source file to import a package.
In order to use modules in a package, the programmer needs to guide the building tool to locate the right package by 1) Adding the package's parent path into \$DOPATH;
or 2) Adding the package dependence into the current project's Do.prj.
More details about locating a module in a package are explained in the next section.


\subsubsection{Package Versioning}

A package must have a version number.
The version number is a string.
For example "1.0", "1.a", "A1", and "1ec5fab753eb979d3886a491845b8ae152d58c8f" are all valid version numbers.
By convention, a package is stored in a directory named packageName-packageVersion.
For example, the util package with version 1.1 is stored in a directory named util-1.1.

The project description file can optionally specify the version of the package used in the current project.
If not defined, because the version number is a string, and all the different versions for the same package will be sorted in increasing order, the package with the largest version number will be used in the compilation.
The builder tool will record the specific package version used in the build in the project's "Do.lock" file to enable fully repeatable builds.


\subsection{Module and Package Organization}

\CFA has two level of encapsulations, module and package.
This section explains the object model of modules, packages and other language concepts.
It also explains how programmers should organize their code, and the method used by the build tools to locate packages, and import modules for compilation.


\subsubsection{Object Model}

There are several concepts in Do.
\begin{itemize}
\item
File: a \CFA source file
\item
Module: a container to organize a set of related types and methods; It has a module name, and several interfaces visible from outside
\item
Package: a container to organize modules for distribution; It has attributes like name, author,
version, dependences, etc.
\item
Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, etc.
\end{itemize}

The following rules summarize the object model of all the above concepts:
\begin{itemize}
\item
A module contains one or more files
\begin{itemize}
\item
One file can only belong to one module
\item
A module has its name and interfaces exported
\item
A file without a module declaration at the beginning belongs to the global module
\item
\end{itemize}

\item
A package contains one or more modules
\begin{itemize}
\item
A package has additional meta info described in Do.prj file
\item
A package may be dependent on other packages.
\end{itemize}

\item
A project contains one or more modules in its source code
\begin{itemize}
\item
A project has additional meta info described in Do.prj file
\item
A project may be dependent on other packages
\item
A project can be transformed into a package for distribution
\item
A project can generate one or more executable binaries
\end{itemize}
\end{itemize}


\subsubsection{Module File Organization}

The rules of this section are the conventions to organize module files in one package.

The file location of a module in a package must match the module/submodule naming hierarchy.
The names separated by slash "/" must match the directory levels.
If only one file is used to implement one module, there is no need to put the module implementation file inside a sub-directory.
The file can be put inside its parent module's sub-directory with the sub module's name as the file name.

Here is an example of a package, util.
\begin{lstlisting}
+ util
Do.prj #package description file
        heap.do #Case 1: module heap;
        list.do #Case 1: mdoule list;
        ring.do #Case 1: module ring;
        + string #Case 2
        impl1.do #module string;
        + std
        vector.do
        list.do
        + array #Case 3
        array1.do #module std/array;
        array2.do #module std/array;
        sequence.do #Case 4, module std/sequence;
        test.do #Case 5
\end{lstlisting}

\begin{itemize}
\item
Case 1: Each individual file implements a module
\item
Case 2: Put the implementation of a module under the sub-directory, but there is only one file
\item
Case 3: Put the implementation of a module under the sub-directory; There are several files to
implement one module
\item
Case 4: One file to express one aggregation
\item
Case 5: The file does not belong to any module; It is used for testing purpose
\end{itemize}

The example only uses source code, ".do" files, to show the module file organization.
Other module packaging formats, like binary, must also follow the same rules.


\subsection{Module File Format}

\CFA supports different types of module file formats.

\begin{itemize}
\item
Pure source code format: The files should be organized following the previous section's definition.
\item
IR format (TBD): The \CFA compiler IR format, similar to the source code format
\item
Binary format, including ".a" static library or ".so" dynamic linkage library
\begin{itemize}
\item
The file's name must match the right level's module name defined in the previous section
\item
E.g. "util.so" includes all modules for the package util.
\item
E.g. "string.so" under the package directory to include files belonging to "module string;"
\end{itemize}
\item.
Archive format
\begin{itemize}
\item
The archive is named as ".dar", and is a zip archive of the source code or the binary for a package
\item
E.g. "util.dar" is the whole package for util package including the package direction file
\end{itemize}
\item
Hybrid format
\begin{itemize}
\item
A package can be distributed partly in source code, partly in binary format, and/or packaged in the archive format
\item
The only limitation is that the names of the files must match the module location names defined in previous section
\end{itemize}
\end{itemize}
Package and Module Locating and the \CFA Language Tooling documentation for more details.


\subsection{Packages}

A package is synonymous with a library in other languages.
The intent of the package level encapsulation is to facilitate code distribution, version control, and dependence management.
A package is a physical grouping of one or more modules in a directory (an archive file for a directory).
The concept of a package is the convention for grouping code, and the contract between the language and the building tool to search for imported modules.


\subsubsection{Package Definition}

A package is defined by putting a project description file, Do.prj, with one or more modules into a directory.
This project description file contains the package's meta data, including package name, author, version, dependences, etc.
It should be in the root of the package directory.

The modules in the package could be either source code, or compiled binary format.
The location of the module files should follow the module name's path.

Here is a simple example of the directory structure of a package, core.
It contains a module std and several sub-modules under std.
\begin{lstlisting}
+ core
        Do.prj
        + std
        + io
        file.do # module std/io/file;
        network.do #module std/io/network;
        + container
        vector.do #module std/container/vector;
        list.do #module std/container/list;
\end{lstlisting}


\subsubsection{Package Import}

Because packages are the places where the building tool looks for modules, there is no code required in the \CFA source file to import a package.
In order to use modules in a package, the programmer needs to guide the building tool to locate the right package by 1) Adding the package's parent path into \$DOPATH; or 2) Adding the package dependence into the current project's Do.prj.
More details about locating a module in a package are explained in the next section.


\subsubsection{Package Versioning}

A package must have a version number.
The version number is a string.
For example "1.0", "1.a", "A1", and "1ec5fab753eb979d3886a491845b8ae152d58c8f" are all valid version numbers.
By convention, a package is stored in a directory named packageName-packageVersion.
For example, the util package with version 1.1 is stored in a directory named util-1.1.

The project description file can optionally specify the version of the package used in the current project.
If not defined, because the version number is a string, and all the different versions for the same package will be sorted in increasing order, the package with the largest version number will be used in the compilation.
The builder tool will record the specific package version used in the build in the project's "Do.lock" file to enable fully repeatable builds.


\subsection{Module and Package Organization}

\CFA has two level of encapsulations, module and package.
This section explains the object model of modules, packages and other language concepts.
It also explains how programmers should organize their code, and the method used by the build tools to locate packages, and import modules for compilation.


\subsubsection{Object Model}

There are several concepts in Do.
\begin{itemize}
\item
File: a \CFA source file
\item
Module: a container to organize a set of related types and methods; It has a module name, and several interfaces visible from outside
\item
Package: a container to organize modules for distribution; It has attributes like name, author, version, dependences, etc.
\item
Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, etc.
\end{itemize}

The following rules summarize the object model of all the above concepts:
\begin{itemize}
\item
A module contains one or more files
\begin{itemize}
\item
One file can only belong to one module
\item
A module has its name and interfaces exported
\item
A file without a module declaration at the beginning belongs to the global module
\end{itemize}
\item
A package contains one or more modules
\begin{itemize}
\item
A package has additional meta info described in Do.prj file
\item
A package may be dependent on other packages.
\end{itemize}
\item
A project contains one or more modules in its source code
\begin{itemize}
\item
A project has additional meta info described in Do.prj file
\item
A project may be dependent on other packages
\item
A project can be transformed into a package for distribution
\item
A project can generate one or more executable binaries
\end{itemize}
\end{itemize}


\subsubsection{Module File Organization}

The rules of this section are the conventions to organize module files in one package.

The file location of a module in a package must match the module/submodule naming hierarchy.
The names separated by slash "/" must match the directory levels.
If only one file is used to implement one module, there is no need to put the module implementation file inside a sub-directory.
The file can be put inside its parent module's sub-directory with the sub module's name as the file name.

Here is an example of a package, util.
\begin{lstlisting}
+ util
        Do.prj #package description file
        heap.do #Case 1: module heap;
        list.do #Case 1: mdoule list;
        ring.do #Case 1: module ring;
        + string #Case 2
        impl1.do #module string;
        + std
        vector.do
        list.do
        + array #Case 3
        array1.do #module std/array;
        array2.do #module std/array;
        sequence.do #Case 4, module std/sequence;
        test.do #Case 5
\end{lstlisting}


\begin{itemize}
\item
Case 1: Each individual file implements a module
\item
Case 2: Put the implementation of a module under the sub-directory, but there is only one file
\item
Case 3: Put the implementation of a module under the sub-directory; There are several files to implement one module
\item
Case 4: One file to express one aggregation
\item
Case 5: The file does not belong to any module; It is used for testing purpose
\end{itemize}

The example only uses source code, ".do" files, to show the module file organization.
Other module packaging formats, like binary, must also follow the same rules.


\subsubsection{Module File Format}

\CFA supports different types of module file formats.

\begin{itemize}
\item
Pure source code format: The files should be organized following the previous section's definition.
\item
IR format (TBD): The \CFA compiler IR format, similar to the source code format
\item
Binary format, including ".a" static library or ".so" dynamic linkage library
\begin{itemize}
\item
The file's name must match the right level's module name defined in the previous section
\item
E.g. "util.so" includes all modules for the package util.
\item
E.g. "string.so" under the package directory to include files belonging to "module string;"
\end{itemize}
\item
Archive format
\begin{itemize}
\item
The archive is named as ".dar", and is a zip archive of the source code or the binary for a package
\item
E.g. "util.dar" is the whole package for util package including the package direction file
\end{itemize}
\item
Hybrid format
\begin{itemize}
\item
A package can be distributed partly in source code, partly in binary format, and/or packaged in the archive format
\item
The only limitation is that the names of the files must match the module location names defined in previous section
\end{itemize}
\end{itemize}


\subsection{Package and Module Locating}

The high-level build tools provided by \CFA will handle finding a package in your local filesystem or retrieving it from a repository if necessary, building it if necessary, and linking with it.
If a programmer prefers, one can directly call the compiler, docc to build the source files and create and link to static libraries.

When a source file imports a module, the \CFA build tool and docc compiler will locate the module according to the following order:

\begin{enumerate}
\item
This source file's directory tree, which is typically the project's src directory
\item
All of the dependent packages (in a directory or in an archive file) under the current \CFA project's pkg directory
\item
The dependent packages (in a directory or in an archive file) inside the paths defined in the DOPATH environment variable
\item
The dependent packages (in a directory or in an archive file) inside the global \CFA SDK installation's pkg directory
\item
If one dependent package is still not found, the builder tool will automatically retrieve it from the repository defined in the SDK installation's configuration, and store it in the SDK's pkg directory
\end{enumerate}

The module found first in a package will shadow the modules with the same name in the later packages in the search sequence.


\subsubsection{Dependent Package}

Dependent packages are those packages containing modules that the current project's source code will import from.
Dependent packages are defined implicitly or explicitly in one \CFA project.
All of the packages under the current project's pkg directory are implicitly dependent packages.
For others, the dependent packages must be defined in the project's Do.prj file.


\subsubsection{Package and Module Locating Example}

\begin{lstlisting}
# A project's source code tree

--------------------------------------

+ testProject
        Do.prj
        + src
        main.do
        + pkg
        + security-1.1
        Do.prj
        security.do #module security

--------------------------------------

# Do.prj

--------------------------------------

[dependences]
std
util = "0.2"

--------------------------------------

# main.do

---------------------------------------

import security;
import std/vector;
import container;

----------------------------------------
\end{lstlisting}


\begin{lstlisting}
# pkg directory's source code tree

-----------------------------------------

+ pkg
        + std-1.0
        Do.prj
        vector.do #module std/vector;
        queue.do #module std/queue;
        + std-1.1
        Do.prj
        vector.do #module std/vector;
        queue.do #module std/queue;
        list.do #module std/list;
        + util-0.1
        Do.prj
        container.do #module container;
        + security-1.0
        security.do #module security;
------------------------------------------
\end{lstlisting}


During the compiling of main.do file import security;
The security module appears in both the local security-1.1 package, and the global security-1.0 package.
According to the locating sequence, the local security module in security-1.1 will be used.
And because the security-1.1 package is under local's pkg directory.
No dependence description is required in the project Do.prj file.

import std/vector;

The std/vector package appears in two different versions' packages in the global path and the project dependence doesn't specify the version. std-1.1 is used in this case.

import container;

The Do.prj specifies the version 0.2 should be used to locate container module from util package but only version 0.1 is available in the local file system.
The builder tool then will try to retrieve it from the web and store it in the global pkg directory.
After that, the container module from the newly downloaded package will be used in the compilation.
\end{comment}


\section{Comparison with Other Languages}

\CFA is one of many languages that attempts to improve upon C.
In developing \CFA, many other languages were consulted for ideas, constructs, and syntax.
Therefore, it is important to show how these languages each compare with Do.
In this section, \CFA is compared with what the writers of this document consider to be the closest competitors of Do: \CC, Go, Rust, and D.


\subsection[Comparing Key Features of CFA]{Comparing Key Features of \CFA}


\subsubsection{Constructors and Destructors}

\lstset{basicstyle=\sf\relsize{-2}}

\begin{flushleft}
\begin{tabular}{@{}l|l|l|l@{}}
\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
\hline
\begin{lstlisting}
struct Line {
        float length;
}
// default constructor
void ?{}( Line * l ) {
        sout | "default" | endl;
        l.length = 0.0;
}


// constructor with length
void ?{}( Line * l, float length ) {
        sout | "length" | length | endl;

        l.length = length;
}

// destructor
void ^?(Line &l) {
        sout | "destroyed" | endl;
        l.length = 0.0;
}

// usage
Line line1;
Line line2{ 3.4 };
\end{lstlisting}
&
\begin{lstlisting}[language=C++]
class Line {
        float length;

        // default constructor
        Line() {
                cout << "default" << endl;
                length = 0.0;
        }


        // constructor with length
        Line( float l ) {
                cout << "length " << length
                         << endl;
                length = l;
        }

        // destructor
        ~Line() {
                cout << "destroyed" << endl;
                length = 0.0;
        }
}
// usage
Line line1;
Line line2( 3.4 );
\end{lstlisting}
&
\begin{lstlisting}[language=Golang]
type Line struct {
        length float32
}
// default constructor
func makeLine() Line {
        fmt.PrintLn( "default" )
        return Line{0.0}
}


// constructor with length
func makeLine( length float32 ) Line {
        fmt.Printf( "length %v", length )

        return Line{length}
}

// no destructor





// usage
line1 := makeLine()
line2 := makeLine( 3.4 )
\end{lstlisting}
&
\begin{lstlisting}
struct Line {
        length: f32
}
// default constructor
impl Default for Line {
        fn default () -> Line {
                println!( "default" );
                Line{ length: 0.0 }
        }
}
// constructor with length
impl Line {
        fn make( len: f32 ) -> Line {
                println!( "length: {}", len );
                Line{ length: len }
        }
}
// destructor
impl Drop for Line {
        fn drop( &mut self ) {
                self.length = 0.0
        }
}
// usage
let line1:Line = Default::default();
Line line2( 3.4 );
\end{lstlisting}
\end{tabular}
\end{flushleft}


\subsubsection{Operator Overloading}

\begin{flushleft}
\begin{tabular}{@{}l|l|l|l@{}}
\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
\hline
\begin{lstlisting}
struct Cpx {
        double re, im;
};
// overload addition operator
Cpx ?+?( Cpx l, const Cpx r ) {
        return (Cpx){l.re+l.im, l.im+r.im};
}
Cpx a, b, c;
c = a + b;
\end{lstlisting}
&
\begin{lstlisting}
struct Cpx {
        double re, im;
};
// overload addition operator
Cpx operator+( Cpx l, const Cpx r ) {
        return (Cpx){l.re+l.im, l.im+r.im};
}
Cpx a, b, c;
c = a + b;
\end{lstlisting}
&
\begin{lstlisting}
// no operator overloading







\end{lstlisting}
&
\begin{lstlisting}
struct Cpx {
        re: f32,
        im: f32
}
// overload addition operator
impl Add for Cpx {
        type Output = Cpx
        fn add(self, r: Cpx) -> Cpx {
                let mut res = Cpx{re: 0.0, im: 0.0};
                res.re = self.re + r.re;
                res.im = self.im + r.im;
                return res
        }
}
let (a, b, mut c) = ...;
c = a + b
\end{lstlisting}
\end{tabular}
\end{flushleft}


\subsubsection{Calling C Functions}

\begin{flushleft}
\begin{tabular}{@{}l|l|l@{}}
\multicolumn{1}{c|}{\textbf{\CFA/\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}   \\
\hline
\begin{lstlisting}[boxpos=t]
extern "C" {
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
}
size_t fileSize( const char *path ) {
        struct stat s;
        stat(path, &s);
        return s.st_size;
}
\end{lstlisting}
&
\begin{lstlisting}[boxpos=t]
/*
#cgo
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
*/
import "C"
import "unsafe"

func fileSize(path string) C.size_t {
        var buf C.struct_stat
        c_string := C.CString(path)
        C.stat(p, &buf)
        C.free(unsafe.Pointer(c_string))
        return buf._st_size
}
\end{lstlisting}
&
\begin{lstlisting}[boxpos=t]
use libc::{c_int, size_t};
// translated from sys/stat.h
#[repr(C)]
struct stat_t {
        ...
        st_size: size_t,
        ...
}
#[link(name = "libc")]
extern {
        fn stat(path: *const u8,
        buf: *mut stat_t) -> c_int;
}
fn fileSize(path: *const u8) -> size_t
{
        unsafe {
                let mut buf: stat_t = uninit();
                stat(path, &mut buf);
                buf.st_size
        }
}
\end{lstlisting}
\end{tabular}
\end{flushleft}


\subsubsection{Generic Functions}

\begin{flushleft}
\begin{tabular}{@{}l|l|l|l@{}}
\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
\hline
\begin{lstlisting}
generic(type T, type N |
        { int ?<?(N, N); })
T *maximize(N (*f)(const T&),
        int n, T *a) {
        T *bestX = NULL;
        N bestN;
        for (int i = 0; i < n; i++) {
        N curN = f(a[i]);
        if (bestX == NULL ||
        curN > bestN) {
        bestX = &a[i]; bestN = curN;
        }
        }
        return bestX;
}

string *longest(int n, string *p)
{
        return maximize(length, n, p);
}
\end{lstlisting}
&
\begin{lstlisting}
template<typename T, typename F>
T *maximize(const F &f,
        int n, T *a) {
        typedef decltype(f(a[0])) N;
        T *bestX = NULL;
        N bestN;
        for (int i = 0; i < n; i++) {
        N curN = f(a[i]);
        if (bestX == NULL || curN > bestN)
        {
        bestX = &a[i]; bestN = curN;
        }
        }
        return bestX;
}

string *longest(int n, string *p) {
        return maximize(
        [](const string &s) {
        return s.length();
        }, n, p);
}
\end{lstlisting}
&
\begin{lstlisting}
// Go does not support generics!
func maximize(
        gt func(interface{}, interface{}) bool,
        f func(interface{}) interface{},
        a []interface{}) interface{} {
        var bestX interface{} = nil
        var bestN interface{} = nil
        for _, x := range a {
        curN := f(x)
        if bestX == nil || gt(curN, bestN)
        {
        bestN = curN
        bestX = x
        }
        }
        return bestX
}

func longest(
        a []interface{}) interface{} {
        return maximize(
        func(a, b interface{}) bool {
        return a.(int) > b.(int) },
        func(s interface{}) interface{} {
        return len(s.(string)) },
        a).(string)
}
\end{lstlisting}
&
\begin{lstlisting}
use std::cmp::Ordering;

fn maximize<N: Ord + Copy, T, F:
Fn(&T) -> N>(f: F, a: &Vec<T>) ->
Option<&T> {
        let mut best_x: Option<&T> = None;
        let mut best_n: Option<N> = None;
        for x in a {
        let n = f(x);
        if (match best_n { None => true,
        Some(bn) =>
        n.cmp(&bn) == Ordering::Greater })
        {
        best_x = Some(x);
        best_n = Some(n);
        }
        }
        return best_x
}

fn longest(a: &Vec<String>) ->
        Option<&String> {
        return
        maximize(|x: &String| x.len(), a)
}
\end{lstlisting}
\end{tabular}
\end{flushleft}


\begin{comment}
\subsubsection{Modules / Packages}

\begin{lstlisting}
\CFA
\CC


module example/M;

export int inc(int val) {
        return val + 1;
}




--------------------------------------
//Use the module in another file
import example/M;
int main() {
        print(M.inc(100));
        return 0;
}
// Using \CC17 module proposal

module example.M;

export {
        int inc(int val);
}

int inc(inv val) {
        return val + 1;
}
--------------------------------------
// Use the module in another file
import example.M;
int main() {
        cout << inc(100) << endl;
        return 0;
}

Go
Rust
package example/M;

func Inc(val int32) int32 {
        // Capitalization indicates exported
        return val + 100
}


--------------------------------------
//Use the package in another file
package main
import .fmt.
import "example/M"

func main() int32 {
        fmt.Printf(.%v., M.Inc(100))
}
pub mod example {
        pub mod M {
        pub inc(val i32) -> i32 {
        return val + 100;
        }
        }
}

--------------------------------------
//Use the module in another file
use example::M;



fn main() {
        println!(.{}., M::inc(100));
}
\end{lstlisting}
\end{comment}


\subsubsection{Parallel Tasks}

\begin{flushleft}
\begin{tabular}{@{}l|l|l|l@{}}
\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
\hline
\begin{lstlisting}
task Nonzero {
        int *data;
        int start;
        int end;
        int* res;
};

void ?{}(Nonzero &a, int d[], int s,
        int e, int* subres) {
        // constructor
        a.data = d;
        a.start = s;
        a.end = e;
        a.res = subres;
}

// implicitly spawn thread here
void ?()(NonzeroCounter &a) {
        int i;
        int nonzero = 0;
        for (i=start; c<end; ++i) {
        if(a.data[i]!=0){ nonzero++;}
        }
        *a.res = nonzero;
}

int main() {
        int sz = ...
        int data[sz] = ...;
        int r1 = 0, r2=0;
        int res;
        { // create a scope for Nonzero
        Nonzero n1{data, 0, sz/2, &n1};
        Nonzero n2{data, sz/2, sz, &n2};
        n1();//spawn
        n2();//spawn
        }
        res = r1+r2;
        return res;
}
\end{lstlisting}
&
\begin{lstlisting}
#include <thread>
#include <mutex>

std::mutex m;












void task(const vector<int>&v,
        int* res, size_t s,
        size_t e) {
        int non_zero = 0;
        for(size_t i = s; i < e; ++i){
        if(v[i]!=0) { non_zero++;}
        }
        std::unique_lock<mutex> lck {m};
        *res += non_zero;
}

int main() {
        vector<int> data = ...; //data
        int res = 0;
        std::thread t1 {task, ref(data),
        &res, 0,
        data.size()/2};
        std::thread t2 {task, ref(data),
        &res, data.size()/2,
        data.size()};
        t1.join();
        t2.join();
        return res;
}
\end{lstlisting}
&
\begin{lstlisting}
package main

import "fmt"

func nonzero(data []int, c chan int) {
        nz := 0
        for _, v:=range data {
        if(v!=0) { nz := nz+1 }
        }
        c <- nz
}

func main() {
        sz := ...
        data := make([]int, sz)
        ... // data init
        go nonzero(data[:len(data)/2], c)
        go nonzero(data[len(data)/2:], c)
        n1, n2 := <-c, <-c
        res := n1 + n2
        fmt.Println(res)
}
\end{lstlisting}
&
\begin{lstlisting}
use std::thread;
use std::sync:mpsc::channel;

fn main() {
        let sz = ...;
        let mut data:Vec<i32> =
        Vec::with_capacity(sz as usize);
        ... //init data
        let (tx, rx) = channel();
        for i in 0..1 {
        let tx = tx.clone();
        let data = data.clone()
        thread::spawn(move|| {
        let mut nz := 0;
        let mut s = 0;
        let mut e = sz / 2;
        if i == 1 {
        s = sz/2;
        e = data.len();
        }
        for i in s..(e - 1) {
        if data[i] != 0 (
        nz = nz + 1
        }
        }
        tx.send(nz).unwrap();
        });
        }
        let res = rx.recv().unwrap() +
        rx.recv().unwrap();
        println!(.{}., res);
}
\end{lstlisting}
\end{tabular}
\end{flushleft}

\lstset{basicstyle=\sf\relsize{-1}}


\subsection{Summary of Language Comparison}


\subsubsection[C++]{\CC}

\CC is a general-purpose programming language.
It has imperative, object-oriented and generic programming features, while also providing facilities for low-level memory manipulation. (Wikipedia)

The primary focus of \CC seems to be adding object-oriented programming to C, and this is the primary difference between \CC and Do.
\CC uses classes to encapsulate data and the functions that operate on that data, and to hide the internal representation of the data.
\CFA uses modules instead to perform these same tasks.
Classes in \CC also enable inheritance among types.
Instead of inheritance, \CFA embraces composition and interfaces to achieve the same goals with more flexibility.
There are many studies and articles comparing inheritance and composition (or is-a versus has-a relationships), so we will not go into more detail here (Venners, 1998) (Pike, Go at Google: Language Design in the Service of Software Engineering , 2012).

Overloading in \CFA is very similar to overloading in \CC, with the exception of the additional use, in \CFA, of the return type to differentiate between overloaded functions.
References and exceptions in \CFA are heavily based on the same features from \CC.
The mechanism for interoperating with C code in \CFA is also borrowed from \CC.

Both \CFA and \CC provide generics, and the syntax is quite similar.
The key difference between the two, is that in \CC templates are expanded at compile time for each type for which the template is instantiated, while in \CFA, function pointers are used to make the generic fully compilable.
This means that a generic function can be defined in a compiled library, and still be used as expected from source.


\subsubsection{Go}

Go, also commonly referred to as golang, is a programming language developed at Google in 2007 [.].
It is a statically typed language with syntax loosely derived from that of C, adding garbage collection, type
safety, some structural typing capabilities, additional built-in types such as variable-length arrays and key-value maps, and a large standard library. (Wikipedia)

Go and \CFA differ significantly in syntax and implementation, but the underlying core concepts of the two languages are aligned.
Both Go and \CFA use composition and interfaces as opposed to inheritance to enable encapsulation and abstraction.
Both languages (along with their tooling ecosystem) provide a simple packaging mechanism for building units of code for easy sharing and reuse.
Both languages also include built-in light weight, user level threading concurrency features that attempt to simplify the effort and thought process required for writing parallel programs while maintaining high performance.

Go has a significant runtime which handles the scheduling of its light weight threads, and performs garbage collection, among other tasks.
\CFA uses a cooperative scheduling algorithm for its tasks, and uses automatic reference counting to enable advanced memory management without garbage collection.
This results in Go requiring significant overhead to interface with C libraries while \CFA has no overhead.


\subsubsection{Rust}

Rust is a general-purpose, multi-paradigm, compiled programming language developed by Mozilla Research.
It is designed to be a "safe, concurrent, practical language", supporting pure-functional, concurrent-actor[dubious . discuss][citation needed], imperative-procedural, and object-oriented styles.

The primary focus of Rust is in safety, especially in concurrent programs.
To enforce a high level of safety, Rust has added ownership as a core feature of the language to guarantee memory safety.
This safety comes at the cost of a difficult learning curve, a change in the thought model of the program, and often some runtime overhead.

Aside from those key differences, Rust and \CFA also have several similarities.
Both languages support no overhead interoperability with C and have minimal runtimes.
Both languages support inheritance and polymorphism through the use of interfaces (traits).


\subsubsection{D}

The D programming language is an object-oriented, imperative, multi-paradigm system programming
language created by Walter Bright of Digital Mars and released in 2001. [.]
Though it originated as a re-engineering of \CC, D is a distinct language, having redesigned some core \CC features while also taking inspiration from other languages, notably Java, Python, Ruby, C\#, and Eiffel.

D and \CFA both start with C and add productivity features.
The obvious difference is that D uses classes and inheritance while \CFA uses composition and interfaces.
D is closer to \CFA than \CC since it is limited to single inheritance and also supports interfaces.
Like \CC, and unlike \CFA, D uses garbage collection and has compile-time expanded templates.
D does not have any built-in concurrency constructs in the
language, though it does have a standard library for concurrency which includes the low-level primitives for concurrency.


\appendix


\section{Incompatible}

The following incompatibles exist between C and \CFA, and are similar to Annex C for \CC~\cite{ANSI14:C++}.

\begin{enumerate}
\item
Change type of character literal ©int© to ©char©.
This change allows overloading differentiation argument type matching, e.g.:
\begin{lstlisting}
int function( int i );
int function( char c );
function( 'x' );
\end{lstlisting}
It is preferable that this call match the second version of function rather than the first. \\
Effect on original feature: Change to semantics of well-defined feature. ISO C programs which depend on
\begin{lstlisting}
sizeof('x') == sizeof(int)
\end{lstlisting}
will not work the same as C++ programs. \\
Difficulty of converting: Simple. \\
How widely used: Programs which depend upon sizeof('x') are probably rare.

\item
Change: String literals made ©const© \\
The type of a string literal is changed from ©array of char© to ©array of const char©.
The type of a wide string literal is changed from ©array of wchar_t© to ©array of const wchar_t©. \\
Rationale: This avoids calling an inappropriate overloaded function, which might expect to be able to modify its argument.
Effect on original feature: Change to semantics of well-defined feature. \\
Difficulty of converting: Simple syntactic transformation, because string literals can be converted to ©char*;© (4.2).
The most common cases are handled by a new but deprecated standard conversion:
\begin{lstlisting}
char* p = "abc"; // valid in C, deprecated in C++
char* q = expr ? "abc" : "de"; // valid in C, invalid in C++
\end{lstlisting}
How widely used: Programs that have a legitimate reason to treat string literals as pointers to potentially modifiable memory are probably rare.

\item
Change: C++ does not have \emph{tentative definitions} as in C.
E.g., at file scope,
\begin{lstlisting}
int i;
int i;
\end{lstlisting}
is valid in C, invalid in C++.
This makes it impossible to define mutually referential file-local static
objects, if initializers are restricted to the syntactic forms of C. For example,
\begin{lstlisting}
struct X { int i; struct X *next; };
static struct X a;
static struct X b = { 0, &a };
static struct X a = { 1, &b };
\end{lstlisting}
Rationale: This avoids having different initialization rules for builtin types and userdefined types.
Effect on original feature: Deletion of semantically welldefined feature. \\
Difficulty of converting: Semantic transformation.
In C++, the initializer for one of a set of mutuallyreferential filelocal static objects must invoke a function call to achieve the initialization.
How widely used: Seldom.

\item
Change: A struct is a scope in C++, not in C \\
Rationale: Class scope is crucial to C++, and a struct is a class. \\
Effect on original feature: Change to semantics of well-defined feature. \\
Difficulty of converting: Semantic transformation. \\
How widely used: C programs use struct extremely frequently, but the change is only noticeable when struct, enumeration, or enumerator names are referred to outside the struct.
The latter is probably rare.

\CFA is C \emph{incompatible} on this issue, and provides semantics similar to \CC.
Nested types are not hoisted and can be referenced using the field selection operator ``©.©'', unlike the \CC scope-resolution operator ``©::©''.
Given that nested types in C are equivalent to not using them, i.e., they are essentially useless, it is unlikely there are any realistic usages that break because of this incompatibility.

\item
Change: In C++, the name of a nested class is local to its enclosing class.
In C the name of the nested class belongs to the same scope as the name of the outermost enclosing class
Example:
\begin{lstlisting}
struct X {
struct Y { /* ... */ } y;
};
struct Y yy; // valid C, invalid C++
\end{lstlisting}
Rationale: C++ classes have member functions which require that classes establish scopes.
The C rule would leave classes as an incomplete scope mechanism which would prevent C++ programmers from maintaining locality within a class. A coherent set of scope rules for C++ based on the C rule would be very complicated and C++ programmers would be unable to predict reliably the meanings of nontrivial examples involving nested or local functions.
Effect on original feature: Change of semantics of welldefined feature.
Difficulty of converting: Semantic transformation. To make the struct type name visible in the scope of the enclosing struct, the struct tag could be declared in the scope of the enclosing struct, before the enclosing struct is defined. Example:
\begin{lstlisting}
struct Y; // struct Y and struct X are at the same scope
struct X {
struct Y { /* ... */ } y;
};
\end{lstlisting}
All the definitions of C struct types enclosed in other struct definitions and accessed outside the scope of the enclosing struct could be exported to the scope of the enclosing struct.
Note: this is a consequence of the difference in scope rules, which is documented in 3.3.
How widely used: Seldom.
\end{enumerate}


\section{I/O Library}
\label{s:IOLibrary}
\index{input/output library}

The goal for \CFA I/O is to make I/O as simple as possible for the general case, while fully supporting polmorphism and user defined types in a consistent way.
The general case is printing out a sequence of variables separated by whitespace.
\begin{quote2}
\begin{tabular}{@{}l@{\hspace{30pt}}l@{}}
\multicolumn{1}{c@{\hspace{30pt}}}{\textbf{\CFA}}       & \multicolumn{1}{c}{\textbf{\CC}}      \\
\begin{lstlisting}
int x = 0, y = 1, z = 2;
®sout® ®|® x ®|® y ®|® z ®| endl®;
\end{lstlisting}
&
\begin{lstlisting}

cout << x << " " << y << " " << z << endl;
\end{lstlisting}
\end{tabular}
\end{quote2}
The \CFA form is half as many characters, and is similar to \Index{Python} I/O with respect to implicit separators.

The logical-or operator is used because it is the lowest-priority overloadable operator, other than assignment.
Therefore, fewer output expressions require parenthesis.
\begin{quote2}
\begin{tabular}{@{}ll@{}}
\textbf{\CFA:}
&
\begin{lstlisting}
sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
\end{lstlisting}
\\
\textbf{\CC:}
&
\begin{lstlisting}
cout << x * 3 << y + 1 << (z << 2) << (x == y) << (x | y) << (x || y) << (x > z ? 1 : 2) << endl;
\end{lstlisting}
\end{tabular}
\end{quote2}
Finally, the logical-or operator has a link with the Shell pipe-operator for moving data, although data flows in the opposite direction.

The implicit seperator\index{I/O separator} character (space/blank) is a separator not a terminator.
The rules for implicitly adding the separator are:
\begin{enumerate}
\item
A seperator does not appear at the start or end of a line.
\begin{lstlisting}[belowskip=0pt]
sout | 1 | 2 | 3 | endl;
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
1 2 3
\end{lstlisting}
\item
A seperator does not appear before or after a character literal or variable.
\begin{lstlisting}
sout | '1' | '2' | '3' | endl;
123
\end{lstlisting}
\item
A seperator does not appear before or after a null (empty) C string
\begin{lstlisting}
sout | 1 | "" | 2 | "" | 3 | endl;
123
\end{lstlisting}
which is a local mechanism to disable insertion of the separator character.
\item
A seperator does not appear before a C string starting with the (extended) \Index{ASCII}\index{ASCII!extended} characters: \lstinline[mathescape=off]@([{$£¥¡¿«@
%$
\begin{lstlisting}[mathescape=off]
sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x $" | 4 | "x £" | 5 | "x ¥" | 6 | "x ¡" | 7 | "x ¿" | 8 | "x «" | 9 | endl;
\end{lstlisting}
%$
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
x (1 x [2 x {3 x $4 x £5 x ¥6 x ¡7 x ¿8 x «9
\end{lstlisting}
%$
\item
A seperator does not appear after a C string ending with the (extended) \Index{ASCII}\index{ASCII!extended} characters: ©,.:;!?)]}%¢»©
\begin{lstlisting}[belowskip=0pt]
sout | 1 | ", x" | 2 | ". x" | 3 | ": x" | 4 | "; x" | 5 | "! x" | 6 | "? x" | 7 | ") x" | 8 | "] x" | 9 | "} x"
         | 10 | "% x" | 11 | "¢ x" | 12 | "» x" | endl;
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
1, x 2. x 3: x 4; x 5! x 6? x 7) x 8] x 9} x 10% x 11¢ 12»
\end{lstlisting}
\item
A seperator does not appear before or after a C string begining/ending with the \Index{ASCII} quote or whitespace characters: \lstinline[showspaces=true]@`'" \t\v\f\r\n@
\begin{lstlisting}[belowskip=0pt]
sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x" | "x " | 4 | " x" | "x\t" | 1 | "\tx" | endl;
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,showtabs=true,aboveskip=0pt,belowskip=0pt]
x`1`x'2'x"3"x x 4 x x   1       x
\end{lstlisting}
\end{enumerate}
The following \CC-style \Index{manipulator}s allow further control over implicit seperation.
\begin{lstlisting}[mathescape=off,belowskip=0pt]
sout | sepOn | 1 | 2 | 3 | sepOn | endl;        // separator at start of line
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
 1 2 3
\end{lstlisting}
\begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt]
sout | 1 | sepOff | 2 | 3 | endl;                       // turn off implicit separator temporarily
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
12 3
\end{lstlisting}
\begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt]
sout | sepDisable | 1 | 2 | 3 | endl;           // turn off implicit separation, affects all subsequent prints
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
123
\end{lstlisting}
\begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt]
sout | 1 | sepOn | 2 | 3 | endl;                        // turn on implicit separator temporarily
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
1 23
\end{lstlisting}
\begin{lstlisting}[mathescape=off,aboveskip=0pt,belowskip=0pt]
sout | sepEnable | 1 | 2 | 3 | endl;            // turn on implicit separation, affects all subsequent prints
\end{lstlisting}
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
 1 2 3
\end{lstlisting}
\begin{lstlisting}[mathescape=off,aboveskip=0pt,aboveskip=0pt,belowskip=0pt]
sepSet( sout, ", $" );                                          // change separator from " " to ", $"
sout | 1 | 2 | 3 | endl;
\end{lstlisting}
%$
\begin{lstlisting}[mathescape=off,showspaces=true,aboveskip=0pt]
1, $2, $3
\end{lstlisting}
%$
\begin{comment}
#include <fstream>

int main() {
        int x = 3, y = 5, z = 7;
        sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
        sout | 1 | 2 | 3 | endl;
        sout | '1' | '2' | '3' | endl;
        sout | 1 | "" | 2 | "" | 3 | endl;
        sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x $" | 4 | "x £" | 5 | "x ¥" | 6 | "x ¡" | 7 | "x ¿" | 8 | "x «" | 9 | endl;
        sout | 1 | ", x" | 2 | ". x" | 3 | ": x" | 4 | "; x" | 5 | "! x" | 6 | "? x" | 7 | ") x" | 8 | "] x" | 9 | "} x"
                 | 10 | "% x" | 11 | "¢ x" | 12 | "» x" | endl;
        sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x" | "x " | 4 | " x" | "x\t" | 1 | "\tx" | endl;
        sout | sepOn | 1 | 2 | 3 | sepOn | endl;        // separator at start of line
        sout | 1 | sepOff | 2 | 3 | endl;                       // turn off implicit separator temporarily
        sout | sepDisable | 1 | 2 | 3 | endl;           // turn off implicit separation, affects all subsequent prints
        sout | 1 | sepOn | 2 | 3 | endl;                        // turn on implicit separator temporarily
        sout | sepEnable | 1 | 2 | 3 | endl;            // turn on implicit separation, affects all subsequent prints
        sepSet( sout, ", $" );                                          // change separator from " " to ", $"
        sout | 1 | 2 | 3 | endl;

}

// Local Variables: //
// tab-width: 4 //
// End: //
\end{comment}
%$


\section{Standard Library}
\label{s:StandardLibrary}

The goal of the \CFA standard-library is to wrap many of the existing C library-routines that are explicitly polymorphic into implicitly polymorphic versions.


\subsection{malloc}

\begin{lstlisting}
forall( otype T ) T * malloc( void );§\indexc{malloc}§
forall( otype T ) T * malloc( char fill );
forall( otype T ) T * malloc( T * ptr, size_t size );
forall( otype T ) T * malloc( T * ptr, size_t size, unsigned char fill );
forall( otype T ) T * calloc( size_t nmemb );§\indexc{calloc}§
forall( otype T ) T * realloc( T * ptr, size_t size );§\indexc{ato}§
forall( otype T ) T * realloc( T * ptr, size_t size, unsigned char fill );

forall( otype T ) T * aligned_alloc( size_t alignment );§\indexc{ato}§
forall( otype T ) T * memalign( size_t alignment );             // deprecated
forall( otype T ) int posix_memalign( T ** ptr, size_t alignment );

forall( otype T ) T * memset( T * ptr, unsigned char fill ); // use default value '\0' for fill
forall( otype T ) T * memset( T * ptr );                                // remove when default value available
\end{lstlisting}


\subsection{ato / strto}

\begin{lstlisting}
int ato( const char * ptr );§\indexc{ato}§
unsigned int ato( const char * ptr );
long int ato( const char * ptr );
unsigned long int ato( const char * ptr );
long long int ato( const char * ptr );
unsigned long long int ato( const char * ptr );
float ato( const char * ptr );
double ato( const char * ptr );
long double ato( const char * ptr );
float _Complex ato( const char * ptr );
double _Complex ato( const char * ptr );
long double _Complex ato( const char * ptr );

int strto( const char * sptr, char ** eptr, int base );
unsigned int strto( const char * sptr, char ** eptr, int base );
long int strto( const char * sptr, char ** eptr, int base );
unsigned long int strto( const char * sptr, char ** eptr, int base );
long long int strto( const char * sptr, char ** eptr, int base );
unsigned long long int strto( const char * sptr, char ** eptr, int base );
float strto( const char * sptr, char ** eptr );
double strto( const char * sptr, char ** eptr );
long double strto( const char * sptr, char ** eptr );
float _Complex strto( const char * sptr, char ** eptr );
double _Complex strto( const char * sptr, char ** eptr );
long double _Complex strto( const char * sptr, char ** eptr );
\end{lstlisting}


\subsection{bsearch / qsort}

\begin{lstlisting}
forall( otype T | { int ?<?( T, T ); } )
T * bsearch( const T key, const T * arr, size_t dimension );§\indexc{bsearch}§

forall( otype T | { int ?<?( T, T ); } )
void qsort( const T * arr, size_t dimension );§\indexc{qsort}§
\end{lstlisting}


\subsection{abs}

\begin{lstlisting}
char abs( char );§\indexc{abs}§
int abs( int );
long int abs( long int );
long long int abs( long long int );
float abs( float );
double abs( double );
long double abs( long double );
float abs( float _Complex );
double abs( double _Complex );
long double abs( long double _Complex );
\end{lstlisting}


\subsection{random}

\begin{lstlisting}
void rand48seed( long int s );§\indexc{rand48seed}§
char rand48();§\indexc{rand48}§
int rand48();
unsigned int rand48();
long int rand48();
unsigned long int rand48();
float rand48();
double rand48();
float _Complex rand48();
double _Complex rand48();
long double _Complex rand48();
\end{lstlisting}


\subsection{min / max / swap}

\begin{lstlisting}
forall( otype T | { int ?<?( T, T ); } )
T min( const T t1, const T t2 );§\indexc{min}§

forall( otype T | { int ?>?( T, T ); } )
T max( const T t1, const T t2 );§\indexc{max}§

forall( otype T )
void swap( T * t1, T * t2 );§\indexc{swap}§
\end{lstlisting}


\section{Math Library}
\label{s:Math Library}

The goal of the \CFA math-library is to wrap many of the existing C math library-routines that are explicitly polymorphic into implicitly polymorphic versions.


\subsection{General}

\begin{lstlisting}
float fabs( float );§\indexc{fabs}§
double fabs( double );
long double fabs( long double );
float cabs( float _Complex );
double cabs( double _Complex );
long double cabs( long double _Complex );

float ?%?( float, float );§\indexc{fmod}§
float fmod( float, float );
double ?%?( double, double );
double fmod( double, double );
long double ?%?( long double, long double );
long double fmod( long double, long double );

float remainder( float, float );§\indexc{remainder}§
double remainder( double, double );
long double remainder( long double, long double );

[ int, float ] remquo( float, float );§\indexc{remquo}§
float remquo( float, float, int * );
[ int, double ] remquo( double, double );
double remquo( double, double, int * );
[ int, long double ] remquo( long double, long double );
long double remquo( long double, long double, int * );

[ int, float ] div( float, float );                                             // alternative name for remquo
float div( float, float, int * );§\indexc{div}§
[ int, double ] div( double, double );
double div( double, double, int * );
[ int, long double ] div( long double, long double );
long double div( long double, long double, int * );

float fma( float, float, float );§\indexc{fma}§
double fma( double, double, double );
long double fma( long double, long double, long double );

float fdim( float, float );§\indexc{fdim}§
double fdim( double, double );
long double fdim( long double, long double );

float nan( const char * );§\indexc{nan}§
double nan( const char * );
long double nan( const char * );
\end{lstlisting}


\subsection{Exponential}

\begin{lstlisting}
float exp( float );§\indexc{exp}§
double exp( double );
long double exp( long double );
float _Complex exp( float _Complex );
double _Complex exp( double _Complex );
long double _Complex exp( long double _Complex );

float exp2( float );§\indexc{exp2}§
double exp2( double );
long double exp2( long double );
float _Complex exp2( float _Complex );
double _Complex exp2( double _Complex );
long double _Complex exp2( long double _Complex );

float expm1( float );§\indexc{expm1}§
double expm1( double );
long double expm1( long double );

float log( float );§\indexc{log}§
double log( double );
long double log( long double );
float _Complex log( float _Complex );
double _Complex log( double _Complex );
long double _Complex log( long double _Complex );

float log2( float );§\indexc{log2}§
double log2( double );
long double log2( long double );
float _Complex log2( float _Complex );
double _Complex log2( double _Complex );
long double _Complex log2( long double _Complex );

float log10( float );§\indexc{log10}§
double log10( double );
long double log10( long double );
float _Complex log10( float _Complex );
double _Complex log10( double _Complex );
long double _Complex log10( long double _Complex );

float log1p( float );§\indexc{log1p}§
double log1p( double );
long double log1p( long double );

int ilogb( float );§\indexc{ilogb}§
int ilogb( double );
int ilogb( long double );

float logb( float );§\indexc{logb}§
double logb( double );
long double logb( long double );
\end{lstlisting}


\subsection{Power}

\begin{lstlisting}
float sqrt( float );§\indexc{sqrt}§
double sqrt( double );
long double sqrt( long double );
float _Complex sqrt( float _Complex );
double _Complex sqrt( double _Complex );
long double _Complex sqrt( long double _Complex );

float cbrt( float );§\indexc{cbrt}§
double cbrt( double );
long double cbrt( long double );

float hypot( float, float );§\indexc{hypot}§
double hypot( double, double );
long double hypot( long double, long double );

float pow( float, float );§\indexc{pow}§
double pow( double, double );
long double pow( long double, long double );
float _Complex pow( float _Complex, float _Complex );
double _Complex pow( double _Complex, double _Complex );
long double _Complex pow( long double _Complex, long double _Complex );
\end{lstlisting}


\subsection{Trigonometric}

\begin{lstlisting}
float sin( float );§\indexc{sin}§
double sin( double );
long double sin( long double );
float _Complex sin( float _Complex );
double _Complex sin( double _Complex );
long double _Complex sin( long double _Complex );

float cos( float );§\indexc{cos}§
double cos( double );
long double cos( long double );
float _Complex cos( float _Complex );
double _Complex cos( double _Complex );
long double _Complex cos( long double _Complex );

float tan( float );§\indexc{tan}§
double tan( double );
long double tan( long double );
float _Complex tan( float _Complex );
double _Complex tan( double _Complex );
long double _Complex tan( long double _Complex );

float asin( float );§\indexc{asin}§
double asin( double );
long double asin( long double );
float _Complex asin( float _Complex );
double _Complex asin( double _Complex );
long double _Complex asin( long double _Complex );

float acos( float );§\indexc{acos}§
double acos( double );
long double acos( long double );
float _Complex acos( float _Complex );
double _Complex acos( double _Complex );
long double _Complex acos( long double _Complex );

float atan( float );§\indexc{atan}§
double atan( double );
long double atan( long double );
float _Complex atan( float _Complex );
double _Complex atan( double _Complex );
long double _Complex atan( long double _Complex );

float atan2( float, float );§\indexc{atan2}§
double atan2( double, double );
long double atan2( long double, long double );

float atan( float, float );                                                             // alternative name for atan2
double atan( double, double );§\indexc{atan}§
long double atan( long double, long double );
\end{lstlisting}


\subsection{Hyperbolic}

\begin{lstlisting}
float sinh( float );§\indexc{sinh}§
double sinh( double );
long double sinh( long double );
float _Complex sinh( float _Complex );
double _Complex sinh( double _Complex );
long double _Complex sinh( long double _Complex );

float cosh( float );§\indexc{cosh}§
double cosh( double );
long double cosh( long double );
float _Complex cosh( float _Complex );
double _Complex cosh( double _Complex );
long double _Complex cosh( long double _Complex );

float tanh( float );§\indexc{tanh}§
double tanh( double );
long double tanh( long double );
float _Complex tanh( float _Complex );
double _Complex tanh( double _Complex );
long double _Complex tanh( long double _Complex );

float asinh( float );§\indexc{asinh}§
double asinh( double );
long double asinh( long double );
float _Complex asinh( float _Complex );
double _Complex asinh( double _Complex );
long double _Complex asinh( long double _Complex );

float acosh( float );§\indexc{acosh}§
double acosh( double );
long double acosh( long double );
float _Complex acosh( float _Complex );
double _Complex acosh( double _Complex );
long double _Complex acosh( long double _Complex );

float atanh( float );§\indexc{atanh}§
double atanh( double );
long double atanh( long double );
float _Complex atanh( float _Complex );
double _Complex atanh( double _Complex );
long double _Complex atanh( long double _Complex );
\end{lstlisting}


\subsection{Error / Gamma}

\begin{lstlisting}
float erf( float );§\indexc{erf}§
double erf( double );
long double erf( long double );
float _Complex erf( float _Complex );
double _Complex erf( double _Complex );
long double _Complex erf( long double _Complex );

float erfc( float );§\indexc{erfc}§
double erfc( double );
long double erfc( long double );
float _Complex erfc( float _Complex );
double _Complex erfc( double _Complex );
long double _Complex erfc( long double _Complex );

float lgamma( float );§\indexc{lgamma}§
double lgamma( double );
long double lgamma( long double );
float lgamma( float, int * );
double lgamma( double, int * );
long double lgamma( long double, int * );

float tgamma( float );§\indexc{tgamma}§
double tgamma( double );
long double tgamma( long double );
\end{lstlisting}


\subsection{Nearest Integer}

\begin{lstlisting}
float floor( float );§\indexc{floor}§
double floor( double );
long double floor( long double );

float ceil( float );§\indexc{ceil}§
double ceil( double );
long double ceil( long double );

float trunc( float );§\indexc{trunc}§
double trunc( double );
long double trunc( long double );

float rint( float );§\indexc{rint}§
long double rint( long double );
long int rint( float );
long int rint( double );
long int rint( long double );
long long int rint( float );
long long int rint( double );
long long int rint( long double );

long int lrint( float );§\indexc{lrint}§
long int lrint( double );
long int lrint( long double );
long long int llrint( float );
long long int llrint( double );
long long int llrint( long double );

float nearbyint( float );§\indexc{nearbyint}§
double nearbyint( double );
long double nearbyint( long double );

float round( float );§\indexc{round}§
long double round( long double );
long int round( float );
long int round( double );
long int round( long double );
long long int round( float );
long long int round( double );
long long int round( long double );

long int lround( float );§\indexc{lround}§
long int lround( double );
long int lround( long double );
long long int llround( float );
long long int llround( double );
long long int llround( long double );
\end{lstlisting}


\subsection{Manipulation}

\begin{lstlisting}
float copysign( float, float );§\indexc{copysign}§
double copysign( double, double );
long double copysign( long double, long double );

float frexp( float, int * );§\indexc{frexp}§
double frexp( double, int * );
long double frexp( long double, int * );

float ldexp( float, int );§\indexc{ldexp}§
double ldexp( double, int );
long double ldexp( long double, int );

[ float, float ] modf( float );§\indexc{modf}§
float modf( float, float * );
[ double, double ] modf( double );
double modf( double, double * );
[ long double, long double ] modf( long double );
long double modf( long double, long double * );

float nextafter( float, float );§\indexc{nextafter}§
double nextafter( double, double );
long double nextafter( long double, long double );

float nexttoward( float, long double );§\indexc{nexttoward}§
double nexttoward( double, long double );
long double nexttoward( long double, long double );

float scalbn( float, int );§\indexc{scalbn}§
double scalbn( double, int );
long double scalbn( long double, int );

float scalbln( float, long int );§\indexc{scalbln}§
double scalbln( double, long int );
long double scalbln( long double, long int );
\end{lstlisting}


\section{Rational Numbers}
\label{s:RationalNumbers}

Rational numbers are numbers written as a ratio, i.e., as a fraction, where the numerator (top number) and the denominator (bottom number) are whole numbers.
When creating and computing with rational numbers, results are constantly reduced to keep the numerator and denominator as small as possible.

\begin{lstlisting}
// implementation
struct Rational {§\indexc{Rational}§
        long int numerator, denominator;                                        // invariant: denominator > 0
}; // Rational

// constants
extern struct Rational 0;
extern struct Rational 1;

// constructors
Rational rational();
Rational rational( long int n );
Rational rational( long int n, long int d );

// getter/setter for numerator/denominator
long int numerator( Rational r );
long int numerator( Rational r, long int n );
long int denominator( Rational r );
long int denominator( Rational r, long int d );

// comparison
int ?==?( Rational l, Rational r );
int ?!=?( Rational l, Rational r );
int ?<?( Rational l, Rational r );
int ?<=?( Rational l, Rational r );
int ?>?( Rational l, Rational r );
int ?>=?( Rational l, Rational r );

// arithmetic
Rational -?( Rational r );
Rational ?+?( Rational l, Rational r );
Rational ?-?( Rational l, Rational r );
Rational ?*?( Rational l, Rational r );
Rational ?/?( Rational l, Rational r );

// conversion
double widen( Rational r );
Rational narrow( double f, long int md );

// I/O
forall( dtype istype | istream( istype ) ) istype * ?|?( istype *, Rational * );
forall( dtype ostype | ostream( ostype ) ) ostype * ?|?( ostype *, Rational );
\end{lstlisting}


\bibliographystyle{plain}
\bibliography{cfa}


\addcontentsline{toc}{section}{\indexname} % add index name to table of contents
\begin{theindex}
Italic page numbers give the location of the main entry for the referenced term.
Plain page numbers denote uses of the indexed term.
Entries for grammar non-terminals are italicized.
A typewriter font is used for grammar terminals and program identifiers.
\indexspace
\input{user.ind}
\end{theindex}


\end{document}

% Local Variables: %
% tab-width: 4 %
% fill-column: 100 %
% compile-command: "make" %
% End: %