source: doc/user/user.tex @ 816d61c

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 816d61c was 816d61c, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago

more updates

  • Property mode set to 100644
File size: 243.4 KB
Line 
1%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -*- Mode: Latex -*- %%%%%%%%%%%%%%%%%%%%%%%%%%%%
2%%
3%% Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
4%%
5%% The contents of this file are covered under the licence agreement in the
6%% file "LICENCE" distributed with Cforall.
7%%
8%% user.tex --
9%%
10%% Author           : Peter A. Buhr
11%% Created On       : Wed Apr  6 14:53:29 2016
12%% Last Modified By : Peter A. Buhr
13%% Last Modified On : Fri Jun 16 12:00:01 2017
14%% Update Count     : 2433
15%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16
17% requires tex packages: texlive-base texlive-latex-base tex-common texlive-humanities texlive-latex-extra texlive-fonts-recommended
18
19\documentclass[twoside,11pt]{article}
20
21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
22
23% Latex packages used in the document.
24\usepackage[T1]{fontenc}                                % allow Latin1 (extended ASCII) characters
25\usepackage{textcomp}
26\usepackage[latin1]{inputenc}
27% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
28% removes it as a variable-name character so keyworks in variables are highlighted
29\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
30
31
32\usepackage{fullpage,times,comment}
33\usepackage{epic,eepic}
34\usepackage{upquote}                                                                    % switch curled `'" to straight
35\usepackage{calc}
36\usepackage{xspace}
37\usepackage{varioref}                                                                   % extended references
38\usepackage{listings}                                                                   % format program code
39\usepackage[flushmargin]{footmisc}                                              % support label/reference in footnote
40\usepackage{latexsym}                                   % \Box glyph
41\usepackage{mathptmx}                                   % better math font with "times"
42\usepackage[usenames]{color}
43\usepackage[pagewise]{lineno}
44\renewcommand{\linenumberfont}{\scriptsize\sffamily}
45\input{common}                                          % common CFA document macros
46\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
47\usepackage{breakurl}
48\renewcommand{\UrlFont}{\small\sf}
49
50\setlength{\topmargin}{-0.45in}                                                 % move running title into header
51\setlength{\headsep}{0.25in}
52
53%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54
55\CFAStyle                                                                                               % use default CFA format-style
56
57% inline code ©...© (copyright symbol) emacs: C-q M-)
58% red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
59% blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
60% green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
61% LaTex escape §...§ (section symbol) emacs: C-q M-'
62% keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
63% math escape $...$ (dollar symbol)
64
65%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
66
67% Names used in the document.
68\newcommand{\Version}{\input{../../version}}
69\newcommand{\Textbf}[2][red]{{\color{#1}{\textbf{#2}}}}
70\newcommand{\Emph}[2][red]{{\color{#1}\textbf{\emph{#2}}}}
71\newcommand{\R}[1]{\Textbf{#1}}
72\newcommand{\B}[1]{{\Textbf[blue]{#1}}}
73\newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}}
74
75\newsavebox{\LstBox}
76
77%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
78
79\setcounter{secnumdepth}{3}                             % number subsubsections
80\setcounter{tocdepth}{3}                                % subsubsections in table of contents
81\makeindex
82
83%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
84
85\title{\Huge
86\vspace*{1in}
87\CFA (\CFL) User Manual                         \\
88Version 1.0                                                     \\
89\vspace*{0.25in}
90\huge``describe not prescribe''
91\vspace*{1in}
92}% title
93
94\author{
95\huge \CFA Team \medskip \\
96\Large Andrew Beach, Richard Bilson, Peter A. Buhr, Thierry Delisle, \smallskip \\
97\Large Glen Ditchfield, Rodolfo G. Esteves, Aaron Moss, Rob Schluntz
98}% author
99
100\date{
101DRAFT \\ \today
102}% date
103
104%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
105
106\begin{document}
107\pagestyle{headings}
108% changed after setting pagestyle
109\renewcommand{\sectionmark}[1]{\markboth{\thesection\quad #1}{\thesection\quad #1}}
110\renewcommand{\subsectionmark}[1]{\markboth{\thesubsection\quad #1}{\thesubsection\quad #1}}
111\pagenumbering{roman}
112%\linenumbers                                            % comment out to turn off line numbering
113
114\maketitle
115\thispagestyle{empty}
116\vspace*{\fill}
117\noindent
118\copyright\,2016 \CFA Project \\ \\
119\noindent
120This work is licensed under the Creative Commons Attribution 4.0 International License.
121To view a copy of this license, visit {\small\url{http://creativecommons.org/licenses/by/4.0}}.
122\vspace*{1in}
123
124\clearpage
125\thispagestyle{plain}
126\pdfbookmark[1]{Contents}{section}
127\tableofcontents
128
129\clearpage
130\thispagestyle{plain}
131\pagenumbering{arabic}
132
133
134\section{Introduction}
135
136\CFA{}\index{cforall@\CFA}\footnote{Pronounced ``\Index*{C-for-all}'', and written \CFA, CFA, or \CFL.} is a modern general-purpose programming-language, designed as an evolutionary step forward for the C programming language.
137The syntax of the \CFA language builds from C, and should look immediately familiar to C/\Index*[C++]{\CC{}} programmers.
138% Any language feature that is not described here can be assumed to be using the standard \Celeven syntax.
139\CFA adds many modern programming-language features that directly lead to increased \emph{\Index{safety}} and \emph{\Index{productivity}}, while maintaining interoperability with existing C programs and achieving C performance.
140Like C, \CFA is a statically typed, procedural language with a low-overhead runtime, meaning there is no global \Index{garbage-collection}, but \Index{regional garbage-collection}\index{garbage-collection!regional} is possible.
141The primary new features include parametric-polymorphic routines and types, exceptions, concurrency, and modules.
142
143One 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''.
144Programmers 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.
145A 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.
146There is no notion or requirement for rewriting a legacy C program in \CFA;
147instead, a programmer evolves an existing C program into \CFA by incrementally incorporating \CFA features.
148New programs can be written in \CFA using a combination of C and \CFA features.
149\Index*[C++]{\CC{}} had a similar goal 30 years ago, but currently has the disadvantages of multiple legacy design-choices that cannot be updated and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project.
150In contrast, \CFA has 30 years of hindsight and a clean starting point.
151
152Like \Index*[C++]{\CC{}}, there may be both an old and new ways to achieve the same effect.
153For example, the following programs compare the \CFA, C, and \CC I/O mechanisms, where the programs output the same result.
154\begin{quote2}
155\begin{tabular}{@{}l@{\hspace{1.5em}}l@{\hspace{1.5em}}l@{}}
156\multicolumn{1}{c@{\hspace{1.5em}}}{\textbf{\CFA}}      & \multicolumn{1}{c}{\textbf{C}}        & \multicolumn{1}{c}{\textbf{\CC}}      \\
157\begin{cfa}
158#include <fstream>§\indexc{fstream}§
159
160int main( void ) {
161        int x = 0, y = 1, z = 2;
162        ®sout | x | y | z | endl;®
163}
164\end{cfa}
165&
166\begin{lstlisting}
167#include <stdio.h>§\indexc{stdio.h}§
168
169int main( void ) {
170        int x = 0, y = 1, z = 2;
171        ®printf( "%d %d %d\n", x, y, z );®
172}
173\end{lstlisting}
174&
175\begin{lstlisting}
176#include <iostream>§\indexc{iostream}§
177using namespace std;
178int main() {
179        int x = 0, y = 1, z = 2;
180        ®cout<<x<<" "<<y<<" "<<z<<endl;®
181}
182\end{lstlisting}
183\end{tabular}
184\end{quote2}
185While the \CFA I/O looks similar to the \Index*[C++]{\CC{}} output style, there are important differences, such as automatic spacing between variables as in \Index*{Python} (see~\VRef{s:IOLibrary}).
186
187This document is a programmer reference-manual for the \CFA programming language.
188The manual covers the core features of the language and runtime-system, with simple examples illustrating syntax and semantics of each feature.
189The manual does not teach programming, i.e., how to combine the new constructs to build complex programs.
190A reader should already have an intermediate knowledge of control flow, data structures, and concurrency issues to understand the ideas presented as well as some experience programming in C/\CC.
191Implementers may refer to the \CFA Programming Language Specification for details about the language syntax and semantics.
192Changes to the syntax and additional features are expected to be included in later revisions.
193
194
195\section{Why fix C?}
196
197The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from commercial operating-systems (especially UNIX systems) to hobby projects.
198This installation base and the programmers producing it represent a massive software-engineering investment spanning decades and likely to continue for decades more.
199Even with all its problems, C continues to be popular because it allows writing software at virtually any level in a computer system without restriction.
200For system programming, where direct access to hardware and dealing with real-time issues is a requirement, C is usually the language of choice.
201The TIOBE index~\cite{TIOBE} for March 2016 showed the following programming-language popularity: \Index*{Java} 20.5\%, C 14.5\%, \Index*[C++]{\CC{}} 6.7\%, \Csharp 4.3\%, \Index*{Python} 4.3\%, where the next 50 languages are less than 3\% each with a long tail.
202As well, for 30 years, C has been the number 1 and 2 most popular programming language:
203\begin{center}
204\setlength{\tabcolsep}{1.5ex}
205\begin{tabular}{@{}r|c|c|c|c|c|c|c@{}}
206Ranking & 2016  & 2011  & 2006  & 2001  & 1996  & 1991  & 1986          \\
207\hline
208Java    & 1             & 1             & 1             & 3             & 29    & -             & -                     \\
209\hline
210\R{C}   & \R{2} & \R{2} & \R{2} & \R{1} & \R{1} & \R{1} & \R{1}         \\
211\hline
212\CC             & 3             & 3             & 3             & 2             & 2             & 2             & 7                     \\
213\end{tabular}
214\end{center}
215Hence, C is still an extremely important programming language, with double the usage of \Index*[C++]{\CC{}}; in many cases, \CC is often used solely as a better C.
216Love it or hate it, C has been an important and influential part of computer science for 40 years and sit appeal is not diminishing.
217Unfortunately, C has too many problems and omissions to make it an acceptable programming language for modern needs.
218
219As stated, the goal of the \CFA project is to engineer modern language features into C in an evolutionary rather than revolutionary way.
220\CC~\cite{C++14,C++} is an example of a similar project;
221however, it largely extended the language, and did not address many existing problems.\footnote{%
222Two 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.}
223\Index*{Fortran}~\cite{Fortran08}, \Index*{Ada}~\cite{Ada12}, and \Index*{Cobol}~\cite{Cobol14} are examples of programming languages that took an evolutionary approach, where modern language features (\eg objects, concurrency) are added and problems fixed within the framework of the existing language.
224\Index*{Java}~\cite{Java8}, \Index*{Go}~\cite{Go}, \Index*{Rust}~\cite{Rust} and \Index*{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.
225These languages have different syntax and semantics from C, and do not interoperate directly with C, largely because of garbage collection.
226As a result, there is a significant learning curve to move to these languages, and C legacy-code must be rewritten.
227These costs can be prohibitive for many companies with a large software base in C/\CC, and a significant number of programmers requiring retraining to a new programming language.
228
229The result of this project is a language that is largely backwards compatible with \Index*[C11]{\Celeven{}}~\cite{C11}, but fixing some of the well known C problems and containing many modern language features.
230Without significant extension to the C programming language, it is becoming unable to cope with the needs of modern programming problems and programmers;
231as a result, it will fade into disuse.
232Considering the large body of existing C code and programmers, there is significant impetus to ensure C is transformed into a modern programming language.
233While \Index*[C11]{\Celeven{}} 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.
234While 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.
235
236
237\section{History}
238
239The \CFA project started with \Index*{K-W C}~\cite{Buhr94a,Till89}, which extended C with new declaration syntax, multiple return values from routines, and extended assignment capabilities using the notion of tuples.
240(See~\cite{Werther96} for similar work in \Index*[C++]{\CC{}}.)
241A first \CFA implementation of these extensions was by Esteves~\cite{Esteves04}.
242The signature feature of \CFA is parametric-polymorphic functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a ©forall© clause (giving the language its name):
243\begin{lstlisting}
244®forall( otype T )® T identity( T val ) { return val; }
245int forty_two = identity( 42 );                 §\C{// T is bound to int, forty\_two == 42}§
246\end{lstlisting}
247% extending the C type system with parametric polymorphism and overloading, as opposed to the \Index*[C++]{\CC{}} approach of object-oriented extensions.
248\CFA{}\hspace{1pt}'s polymorphism was originally formalized by Ditchfiled~\cite{Ditchfield92}, and first implemented by Bilson~\cite{Bilson03}.
249However, at that time, there was little interesting in extending C, so work did not continue.
250As 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.
251
252
253\section{Interoperability}
254\label{s:Interoperability}
255
256\CFA is designed to integrate directly with existing C programs and libraries.
257The most important feature of \Index{interoperability} is using the same \Index{calling convention}s, so there is no overhead to call existing C routines.
258This feature allows \CFA programmers to take advantage of the existing panoply of C libraries to access thousands of external software features.
259Language developers often state that adequate \Index{library support} takes more work than designing and implementing the language itself.
260Fortunately, \CFA, like \Index*[C++]{\CC{}}, 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.
261Hence, \CFA begins by leveraging the large repository of C libraries with little cost.
262
263\begin{comment}
264A simple example is leveraging the existing type-unsafe (©void *©) C ©bsearch© to binary search a sorted floating-point array:
265\begin{lstlisting}
266void * bsearch( const void * key, const void * base, size_t dim, size_t size,
267                                int (* compar)( const void *, const void * ));
268
269int comp( const void * t1, const void * t2 ) { return *(double *)t1 < *(double *)t2 ? -1 :
270                                *(double *)t2 < *(double *)t1 ? 1 : 0; }
271
272double key = 5.0, vals[10] = { /* 10 sorted floating-point values */ };
273double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
274\end{lstlisting}
275which can be augmented simply with a polymorphic, type-safe, \CFA-overloaded wrappers:
276\begin{lstlisting}
277forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) {
278        int comp( const void * t1, const void * t2 ) { /* as above with double changed to T */ }
279        return (T *)bsearch( &key, arr, size, sizeof(T), comp ); }
280
281forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) {
282        T * result = bsearch( key, arr, size ); $\C{// call first version}$
283        return result ? result - arr : size; }  $\C{// pointer subtraction includes sizeof(T)}$
284
285double * val = bsearch( 5.0, vals, 10 );        $\C{// selection based on return type}$
286int posn = bsearch( 5.0, vals, 10 );
287\end{lstlisting}
288The nested function ©comp© provides the hidden interface from typed \CFA to untyped (©void *©) C, plus the cast of the result.
289Providing a hidden ©comp© function in \CC is awkward as lambdas do not use C calling-conventions and template declarations cannot appear at block scope.
290As well, an alternate kind of return is made available: position versus pointer to found element.
291\CC's type-system cannot disambiguate between the two versions of ©bsearch© because it does not use the return type in overload resolution, nor can \CC separately compile a templated ©bsearch©.
292
293\CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations.
294For example, it is possible to write a type-safe \CFA wrapper ©malloc© based on the C ©malloc©:
295\begin{lstlisting}
296forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); }
297int * ip = malloc();                                    §\C{// select type and size from left-hand side}§
298double * dp = malloc();
299struct S {...} * sp = malloc();
300\end{lstlisting}
301where the return type supplies the type/size of the allocation, which is impossible in most type systems.
302\end{comment}
303
304However, it is necessary to differentiate between C and \CFA code because of name overloading, as for \CC.
305For example, the C math-library provides the following routines for computing the absolute value of the basic types: ©abs©, ©labs©, ©llabs©, ©fabs©, ©fabsf©, ©fabsl©, ©cabsf©, ©cabs©, and ©cabsl©.
306Whereas, \CFA wraps each of these routines into ones with the common name ©abs©:
307\begin{cfa}
308char abs( char );
309®extern "C" {®
310int abs( int );                                                 §\C{// use default C routine for int}§
311®}® // extern "C"
312long int abs( long int );
313long long int abs( long long int );
314float abs( float );
315double abs( double );
316long double abs( long double );
317float _Complex abs( float _Complex );
318double _Complex abs( double _Complex );
319long double _Complex abs( long double _Complex );
320\end{cfa}
321The problem is the name clash between the library routine ©abs© and the \CFA names ©abs©.
322Hence, names appearing in an ©extern "C"© block have \newterm*{C linkage}.
323Then overloading polymorphism uses a mechanism called \newterm{name mangling}\index{mangling!name} to create unique names that are different from C names, which are not mangled.
324Hence, 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.
325There is no way around this problem, other than C's approach of creating unique names for each pairing of operation and type.
326This example strongly illustrates a core idea in \CFA: \emph{the power of a name}.
327The name ``©abs©'' evokes the notion of absolute value, and many mathematical types provide the notion of absolute value.
328Hence, knowing the name ©abs© should be sufficient to apply it to any type where it is applicable.
329The time savings and safety of using one name uniformly versus $N$ unique names should not be underestimated.
330
331
332\section[Compiling CFA Program]{Compiling \CFA Program}
333
334The command ©cfa© is used to compile \CFA program(s), and is based on the GNU \Indexc{gcc} command, \eg:
335\begin{cfa}
336cfa§\indexc{cfa}\index{compilation!cfa@©cfa©}§ [ gcc-options ] C/§\CFA§-files [ assembler/loader-files ]
337\end{cfa}
338\CFA programs having the following ©gcc© flags turned on:
339\begin{description}
340\item
341\Indexc{-std=gnu99}\index{compilation option!-std=gnu99@{©-std=gnu99©}}
342The 1999 C standard plus GNU extensions.
343\item
344{\lstset{deletekeywords={inline}}
345\Indexc{-fgnu89-inline}\index{compilation option!-fgnu89-inline@{©-fgnu89-inline©}}
346Use the traditional GNU semantics for inline routines in C99 mode, which allows inline routines in header files.
347}%
348\end{description}
349The following new \CFA options are available:
350\begin{description}
351\item
352\Indexc{-CFA}\index{compilation option!-CFA@©-CFA©}
353Only 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.
354The generated code started with the standard \CFA prelude.
355
356\item
357\Indexc{-debug}\index{compilation option!-debug@©-debug©}
358The program is linked with the debugging version of the runtime system.
359The debug version performs runtime checks to help during the debugging phase of a \CFA program, but substantially slows the execution of the program.
360The runtime checks should only be removed after the program is completely debugged.
361\textbf{This option is the default.}
362
363\item
364\Indexc{-nodebug}\index{compilation option!-nodebug@©-nodebug©}
365The program is linked with the non-debugging version of the runtime system, so the execution of the program is faster.
366\Emph{However, no runtime checks or ©assert©s are performed so errors usually result in abnormal program termination.}
367
368\item
369\Indexc{-help}\index{compilation option!-help@©-help©}
370Information about the set of \CFA compilation flags is printed.
371
372\item
373\Indexc{-nohelp}\index{compilation option!-nohelp@©-nohelp©}
374Information about the set of \CFA compilation flags is not printed.
375\textbf{This option is the default.}
376
377\item
378\Indexc{-quiet}\index{compilation option!-quiet@©-quiet©}
379The \CFA compilation message is not printed at the beginning of a compilation.
380
381\item
382\Indexc{-noquiet}\index{compilation option!-noquiet@©-noquiet©}
383The \CFA compilation message is printed at the beginning of a compilation.
384\textbf{This option is the default.}
385
386\item
387\Indexc{-no-include-stdhdr}\index{compilation option!-no-include-stdhdr@©-no-include-stdhdr©}
388Do not supply ©extern "C"© wrappers for \Celeven standard include files (see~\VRef{s:StandardHeaders}).
389\textbf{This option is \emph{not} the default.}
390\end{description}
391
392The following preprocessor variables are available:
393\begin{description}
394\item
395\Indexc{__CFA_MAJOR__}\index{preprocessor variables!__CFA__@{©__CFA__©}}
396is available during preprocessing and its value is the major \Index{version number} of \CFA.\footnote{
397The C preprocessor allows only integer values in a preprocessor variable so a value like ``\Version'' is not allowed.
398Hence, the need to have three variables for the major, minor and patch version number.}
399
400\item
401\Indexc{__CFA_MINOR__}\index{preprocessor variables!__CFA_MINOR__@{©__CFA_MINOR__©}}
402is available during preprocessing and its value is the minor \Index{version number} of \CFA.
403
404\item
405\Indexc{__CFA_PATCH__}\index{preprocessor variables!__CFA_PATCH____CFA_PATCH__©}
406is available during preprocessing and its value is the patch \Index{level number} of \CFA.
407
408\item
409\Indexc{__CFA__}\index{preprocessor variables!__CFA____CFA__©},
410\Indexc{__CFORALL__}\index{preprocessor variables!__CFORALL____CFORALL__©} and
411\Indexc{__cforall}\index{preprocessor variables!__cforall@©__cforall©}
412are always available during preprocessing and have no value.
413\end{description}
414These preprocessor variables allow conditional compilation of programs that must work differently in these situations.
415For example, to toggle between C and \CFA extensions, using the following:
416\begin{cfa}
417#ifndef __CFORALL__
418#include <stdio.h>§\indexc{stdio.h}§    §\C{// C header file}§
419#else
420#include <fstream>§\indexc{fstream}§    §\C{// \CFA header file}§
421#endif
422\end{cfa}
423which conditionally includes the correct header file, if the program is compiled using \Indexc{gcc} or \Indexc{cfa}.
424
425
426\section{Constants Underscores}
427
428Numeric constants are extended to allow \Index{underscore}s within constants\index{constant!underscore}, \eg:
429\begin{cfa}
430_®147®_®483®_®648;                                    §\C{// decimal constant}§
43156®_®ul;                                                                §\C{// decimal unsigned long constant}§
432_®377;                                                                §\C{// octal constant}§
4330x®_®ff®_®ff;                                                   §\C{// hexadecimal constant}§
4340x®_®ef3d®_®aa5c;                                               §\C{// hexadecimal constant}§
4353.141®_®592®_®654;                                              §\C{// floating point constant}§
43610®_®e®_®+1®_®00;                                               §\C{// floating point constant}§
4370x®_®ff®_®ff®_®p®_®3;                                   §\C{// hexadecimal floating point}§
4380x®_®1.ffff®_®ffff®_®p®_®128®_®l;               §\C{// hexadecimal floating point long constant}§
439_®§"\texttt{\textbackslash{x}}§®_®§\texttt{ff}§®_®§\texttt{ee}"§;     §\C{// wide character constant}§
440\end{cfa}
441The rules for placement of underscores is as follows:
442\begin{enumerate}
443\item
444A sequence of underscores is disallowed, \eg ©12__34© is invalid.
445\item
446Underscores may only appear within a sequence of digits (regardless of the digit radix).
447In other words, an underscore cannot start or end a sequence of digits, \eg ©_1©, ©1_© and ©_1_© are invalid (actually, the 1st and 3rd examples are identifier names).
448\item
449A numeric prefix may end with an underscore;
450a numeric infix may begin and/or end with an underscore;
451a numeric suffix may begin with an underscore.
452For example, the octal ©0© or hexadecimal ©0x© prefix may end with an underscore ©0_377© or ©0x_ff©;
453the exponent infix ©E© may start or end with an underscore ©1.0_E10©, ©1.0E_10© or ©1.0_E_10©;
454the type suffixes ©U©, ©L©, etc. may start with an underscore ©1_U©, ©1_ll© or ©1.0E10_f©.
455\end{enumerate}
456It is significantly easier to read and enter long constants when they are broken up into smaller groupings (many cultures use comma and/or period among digits for the same purpose).
457This extension is backwards compatible, matches with the use of underscore in variable names, and appears in \Index*{Ada} and \Index*{Java} 8.
458
459
460\section{Backquote Identifiers}
461\label{s:BackquoteIdentifiers}
462
463\CFA accommodates keyword clashes with existing C variable-names by syntactic transformations using the \CFA backquote escape-mechanism:
464\begin{cfa}
465int ®`®otype®`® = 3;                    §\C{// make keyword an identifier}§
466double ®`®forall®`® = 3.5;
467\end{cfa}
468Existing C programs with keyword clashes can be converted by enclosing keyword identifiers in backquotes, and eventually the identifier name can be changed to a non-keyword name.
469\VRef[Figure]{f:InterpositionHeaderFile} shows how clashes in C header files (see~\VRef{s:StandardHeaders}) can be handled using preprocessor \newterm{interposition}: ©#include_next© and ©-I filename©:
470
471\begin{figure}
472\begin{cfa}
473// include file uses the CFA keyword "otype".
474#if ! defined( otype )                  §\C{// nesting ?}§
475#define otype ®`®otype®`®               §\C{// make keyword an identifier}§
476#define __CFA_BFD_H__
477#endif // ! otype
478
479#include_next <bfd.h>                   §\C{// must have internal check for multiple expansion}§
480
481#if defined( otype ) && defined( __CFA_BFD_H__ )        §\C{// reset only if set}§
482#undef otype
483#undef __CFA_BFD_H__
484#endif // otype && __CFA_BFD_H__
485\end{cfa}
486\caption{Interposition of Header File}
487\label{f:InterpositionHeaderFile}
488\end{figure}
489
490
491\section{Declarations}
492\label{s:Declarations}
493
494C declaration syntax is notoriously confusing and error prone.
495For example, many C programmers are confused by a declaration as simple as:
496\begin{quote2}
497\begin{tabular}{@{}ll@{}}
498\begin{cfa}
499int * x[5]
500\end{cfa}
501&
502\raisebox{-0.75\totalheight}{\input{Cdecl}}
503\end{tabular}
504\end{quote2}
505Is this an array of 5 pointers to integers or a \Index{pointer} to an array of 5 integers?
506The fact this declaration is unclear to many C programmers means there are \Index{productivity} and \Index{safety} issues even for basic programs.
507Another 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.
508For example, a routine returning a \Index{pointer} to an array of integers is defined and used in the following way:
509\begin{cfa}
510int ®(*®f®())[®5®]® {...};                              §\C{definition}§
511 ... ®(*®f®())[®3®]® += 1;                              §\C{usage}§
512\end{cfa}
513Essentially, the return type is wrapped around the routine name in successive layers (like an \Index{onion}).
514While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice.
515
516\CFA provides its own type, variable and routine declarations, using a different syntax.
517The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
518In the following example, \R{red} is the base type and \B{blue} is qualifiers.
519The \CFA declarations move the qualifiers to the left of the base type, \ie move the blue to the left of the red, while the qualifiers have the same meaning but are ordered left to right to specify a variable's type.
520\begin{quote2}
521\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
522\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
523\begin{cfa}
524ß[5] *ß ®int® x1;
525ß* [5]ß ®int® x2;
526ß[* [5] int]ß f®( int p )®;
527\end{cfa}
528&
529\begin{cfa}
530®int® ß*ß x1 ß[5]ß;
531®int® ß(*ßx2ß)[5]ß;
532ßint (*ßf®( int p )®ß)[5]ß;
533\end{cfa}
534\end{tabular}
535\end{quote2}
536The only exception is \Index{bit field} specification, which always appear to the right of the base type.
537% Specifically, the character ©*© is used to indicate a pointer, square brackets ©[©\,©]© are used to represent an array or function return value, and parentheses ©()© are used to indicate a routine parameter.
538However, unlike C, \CFA type declaration tokens are distributed across all variables in the declaration list.
539For instance, variables ©x© and ©y© of type \Index{pointer} to integer are defined in \CFA as follows:
540\begin{quote2}
541\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
542\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
543\begin{cfa}
544®*® int x, y;
545\end{cfa}
546&
547\begin{cfa}
548int ®*®x, ®*®y;
549\end{cfa}
550\end{tabular}
551\end{quote2}
552The downside of this semantics is the need to separate regular and \Index{pointer} declarations:
553\begin{quote2}
554\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
555\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
556\begin{cfa}
557®*® int x;
558int y;
559\end{cfa}
560&
561\begin{cfa}
562int ®*®x, y;
563
564\end{cfa}
565\end{tabular}
566\end{quote2}
567which is \Index{prescribing} a safety benefit.
568Other examples are:
569\begin{quote2}
570\begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
571\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{C}} \\
572\begin{cfa}
573[ 5 ] int z;
574[ 5 ] * char w;
575* [ 5 ] double v;
576struct s {
577        int f0:3;
578        * int f1;
579        [ 5 ] * int f2;
580};
581\end{cfa}
582&
583\begin{cfa}
584int z[ 5 ];
585char * w[ 5 ];
586double (* v)[ 5 ];
587struct s {
588        int f0:3;
589        int * f1;
590        int * f2[ 5 ]
591};
592\end{cfa}
593&
594\begin{cfa}
595// array of 5 integers
596// array of 5 pointers to char
597// pointer to array of 5 doubles
598
599// common bit field syntax
600
601
602
603\end{cfa}
604\end{tabular}
605\end{quote2}
606
607All type qualifiers, \eg ©const©, ©volatile©, etc., are used in the normal way with the new declarations and also appear left to right, \eg:
608\begin{quote2}
609\begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}}
610\multicolumn{1}{c@{\hspace{1em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{1em}}}{\textbf{C}} \\
611\begin{cfa}
612const * const int x;
613const * [ 5 ] const int y;
614\end{cfa}
615&
616\begin{cfa}
617int const * const x;
618const int (* const y)[ 5 ]
619\end{cfa}
620&
621\begin{cfa}
622// const pointer to const integer
623// const pointer to array of 5 const integers
624\end{cfa}
625\end{tabular}
626\end{quote2}
627All declaration qualifiers, \eg ©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}
628The 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}} \eg:
629\begin{quote2}
630\begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
631\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{C}} \\
632\begin{cfa}
633extern [ 5 ] int x;
634static * const int y;
635\end{cfa}
636&
637\begin{cfa}
638int extern x[ 5 ];
639const int static * y;
640\end{cfa}
641&
642\begin{cfa}
643// externally visible array of 5 integers
644// internally visible pointer to constant int
645\end{cfa}
646\end{tabular}
647\end{quote2}
648
649The new declaration syntax can be used in other contexts where types are required, \eg casts and the pseudo-routine ©sizeof©:
650\begin{quote2}
651\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
652\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
653\begin{cfa}
654y = (®* int®)x;
655i = sizeof(®[ 5 ] * int®);
656\end{cfa}
657&
658\begin{cfa}
659y = (®int *®)x;
660i = sizeof(®int * [ 5 ]®);
661\end{cfa}
662\end{tabular}
663\end{quote2}
664
665Finally, new \CFA declarations may appear together with C declarations in the same program block, but cannot be mixed within a specific declaration.
666Therefore, a programmer has the option of either continuing to use traditional C declarations or take advantage of the new style.
667Clearly, both styles need to be supported for some time due to existing C-style header-files, particularly for UNIX systems.
668
669
670\section{Pointer/Reference}
671
672C provides a \newterm{pointer type};
673\CFA adds a \newterm{reference type}.
674These types may be derived from an object or routine type, called the \newterm{referenced type}.
675Objects of these types contain an \newterm{address}, which is normally a location in memory, but may also address memory-mapped registers in hardware devices.
676An integer constant expression with the value 0, or such an expression cast to type ©void *©, is called a \newterm{null-pointer constant}.\footnote{
677One way to conceptualize the null pointer is that no variable is placed at this address, so the null-pointer address can be used to denote an uninitialized pointer/reference object;
678\ie the null pointer is guaranteed to compare unequal to a pointer to any object or routine.}
679An address is \newterm{sound}, if it points to a valid memory location in scope, \ie within the program's execution-environment and has not been freed.
680Dereferencing an \newterm{unsound} address, including the null pointer, is \Index{undefined}, often resulting in a \Index{memory fault}.
681
682A program \newterm{object} is a region of data storage in the execution environment, the contents of which can represent values.
683In most cases, objects are located in memory at an address, and the variable name for an object is an implicit address to the object generated by the compiler and automatically dereferenced, as in:
684\begin{quote2}
685\begin{tabular}{@{}ll@{\hspace{2em}}l@{}}
686\begin{cfa}
687int x;
688x = 3;
689int y;
690y = x;
691\end{cfa}
692&
693\raisebox{-0.45\totalheight}{\input{pointer1}}
694&
695\begin{cfa}
696int * ®const® x = (int *)100
697*x = 3;                 // implicit dereference
698int * ®const® y = (int *)104;
699*y = *x;                // implicit dereference
700\end{cfa}
701\end{tabular}
702\end{quote2}
703where the right example is how the compiler logically interprets the variables in the left example.
704Since a variable name only points to one address during its lifetime, it is an \Index{immutable} \Index{pointer};
705hence, the implicit type of pointer variables ©x© and ©y© are constant pointers in the compiler interpretation.
706In general, variable addresses are stored in instructions instead of loaded from memory, and hence may not occupy storage.
707These approaches are contrasted in the following:
708\begin{quote2}
709\begin{tabular}{@{}l|l@{}}
710\multicolumn{1}{c|}{explicit variable address} & \multicolumn{1}{c}{implicit variable address} \\
711\hline
712\begin{cfa}
713lda             r1,100                  // load address of x
714ld               r2,(r1)                  // load value of x
715lda             r3,104                  // load address of y
716st               r2,(r3)                  // store x into y
717\end{cfa}
718&
719\begin{cfa}
720
721ld              r2,(100)                // load value of x
722
723st              r2,(104)                // store x into y
724\end{cfa}
725\end{tabular}
726\end{quote2}
727Finally, the immutable nature of a variable's address and the fact that there is no storage for the variable pointer means pointer assignment\index{pointer!assignment}\index{assignment!pointer} is impossible.
728Therefore, the expression ©x = y© has only one meaning, ©*x = *y©, \ie manipulate values, which is why explicitly writing the dereferences is unnecessary even though it occurs implicitly as part of \Index{instruction decoding}.
729
730A \Index{pointer}/\Index{reference} object is a generalization of an object variable-name, \ie a mutable address that can point to more than one memory location during its lifetime.
731(Similarly, an integer variable can contain multiple integer literals during its lifetime versus an integer constant representing a single literal during its lifetime, and like a variable name, may not occupy storage if the literal is embedded directly into instructions.)
732Hence, a pointer occupies memory to store its current address, and the pointer's value is loaded by dereferencing, \eg:
733\begin{quote2}
734\begin{tabular}{@{}l@{\hspace{2em}}l@{}}
735\begin{cfa}
736int x, y, ®*® p1, ®*® p2, ®**® p3;
737p1 = ®&®x;               // p1 points to x
738p2 = p1;                 // p2 points to x
739p1 = ®&®y;               // p1 points to y
740p3 = &p2;               // p3 points to p2
741\end{cfa}
742&
743\raisebox{-0.5\totalheight}{\input{pointer2.pstex_t}}
744\end{tabular}
745\end{quote2}
746
747Notice, an address has a \Index{duality}\index{address!duality}: a location in memory or the value at that location.
748In many cases, a compiler might be able to infer the best meaning for these two cases.
749For example, \Index*{Algol68}~\cite{Algol68} infers pointer dereferencing to select the best meaning for each pointer usage
750\begin{cfa}
751p2 = p1 + x;                                    §\C{// compiler infers *p2 = *p1 + x;}§
752\end{cfa}
753Algol68 infers the following dereferencing ©*p2 = *p1 + x©, because adding the arbitrary integer value in ©x© to the address of ©p1© and storing the resulting address into ©p2© is an unlikely operation.
754Unfortunately, automatic dereferencing does not work in all cases, and so some mechanism is necessary to fix incorrect choices.
755
756Rather than inferring dereference, most programming languages pick one implicit dereferencing semantics, and the programmer explicitly indicates the other to resolve address-duality.
757In C, objects of pointer type always manipulate the pointer object's address:
758\begin{cfa}
759p1 = p2;                                                §\C{// p1 = p2\ \ rather than\ \ *p1 = *p2}§
760p2 = p1 + x;                                    §\C{// p2 = p1 + x\ \ rather than\ \ *p2 = *p1 + x}§
761\end{cfa}
762even though the assignment to ©p2© is likely incorrect, and the programmer probably meant:
763\begin{cfa}
764p1 = p2;                                                §\C{// pointer address assignment}§
765®*®p2 = ®*®p1 + x;                              §\C{// pointed-to value assignment / operation}§
766\end{cfa}
767The C semantics work well for situations where manipulation of addresses is the primary meaning and data is rarely accessed, such as storage management (©malloc©/©free©).
768
769However, in most other situations, the pointed-to value is requested more often than the pointer address.
770\begin{cfa}
771*p2 = ((*p1 + *p2) * (**p3 - *p1)) / (**p3 - 15);
772\end{cfa}
773In this case, it is tedious to explicitly write the dereferencing, and error prone when pointer arithmetic is allowed.
774It is better to have the compiler generate the dereferencing and have no implicit pointer arithmetic:
775\begin{cfa}
776p2 = ((p1 + p2) * (p3 - p1)) / (p3 - 15);
777\end{cfa}
778
779To support this common case, a reference type is introduced in \CFA, denoted by ©&©, which is the opposite dereference semantics to a pointer type, making the value at the pointed-to location the implicit semantics for dereferencing (similar but not the same as \CC \Index{reference type}s).
780\begin{cfa}
781int x, y, ®&® r1, ®&® r2, ®&&® r3;
782®&®r1 = &x;                                             §\C{// r1 points to x}§
783®&®r2 = &r1;                                    §\C{// r2 points to x}§
784®&®r1 = &y;                                             §\C{// r1 points to y}§
785®&&®r3 = ®&®&r2;                                §\C{// r3 points to r2}§
786r2 = ((r1 + r2) * (r3 - r1)) / (r3 - 15); §\C{// implicit dereferencing}§
787\end{cfa}
788Except for auto-dereferencing by the compiler, this reference example is the same as the previous pointer example.
789Hence, a reference behaves like the variable name for the current variable it is pointing-to.
790One way to conceptualize a reference is via a rewrite rule, where the compiler inserts a dereference operator before the reference variable for each reference qualifier in a declaration, so the previous example becomes:
791\begin{cfa}
792®*®r2 = ((®*®r1 + ®*®r2) ®*® (®**®r3 - ®*®r1)) / (®**®r3 - 15);
793\end{cfa}
794When a reference operation appears beside a dereference operation, \eg ©&*©, they cancel out.
795However, in C, the cancellation always yields a value (\Index{rvalue}).\footnote{
796The unary ©&© operator yields the address of its operand.
797If the operand has type ``type'', the result has type ``pointer to type''.
798If the operand is the result of a unary ©*© operator, neither that operator nor the ©&© operator is evaluated and the result is as if both were omitted, except that the constraints on the operators still apply and the result is not an lvalue.~\cite[\S~6.5.3.2--3]{C11}}
799For a \CFA reference type, the cancellation on the left-hand side of assignment leaves the reference as an address (\Index{lvalue}):
800\begin{cfa}
801(&®*®)r1 = &x;                                  §\C{// (\&*) cancel giving address in r1 not variable pointed-to by r1}§
802\end{cfa}
803Similarly, the address of a reference can be obtained for assignment or computation (\Index{rvalue}):
804\begin{cfa}
805(&(&®*®)®*®)r3 = &(&®*®)r2;             §\C{// (\&*) cancel giving address in r2, (\&(\&*)*) cancel giving address in r3}§
806\end{cfa}
807Cancellation\index{cancellation!pointer/reference}\index{pointer!cancellation} works to arbitrary depth.
808
809Fundamentally, pointer and reference objects are functionally interchangeable because both contain addresses.
810\begin{cfa}
811int x, *p1 = &x, **p2 = &p1, ***p3 = &p2,
812                 &r1 = x,    &&r2 = r1,   &&&r3 = r2;
813***p3 = 3;                                              §\C{// change x}§
814r3 = 3;                                                 §\C{// change x, ***r3}§
815**p3 = ...;                                             §\C{// change p1}§
816&r3 = ...;                                              §\C{// change r1, (\&*)**r3, 1 cancellation}§
817*p3 = ...;                                              §\C{// change p2}§
818&&r3 = ...;                                             §\C{// change r2, (\&(\&*)*)*r3, 2 cancellations}§
819&&&r3 = p3;                                             §\C{// change r3 to p3, (\&(\&(\&*)*)*)r3, 3 cancellations}§
820\end{cfa}
821Furthermore, both types are equally performant, as the same amount of dereferencing occurs for both types.
822Therefore, the choice between them is based solely on whether the address is dereferenced frequently or infrequently, which dictates the amount of implicit dereferencing aid from the compiler.
823
824As for a pointer type, a reference type may have qualifiers:
825\begin{cfa}
826const int cx = 5;                                       §\C{// cannot change cx;}§
827const int & cr = cx;                            §\C{// cannot change what cr points to}§
828®&®cr = &cx;                                            §\C{// can change cr}§
829cr = 7;                                                         §\C{// error, cannot change cx}§
830int & const rc = x;                                     §\C{// must be initialized}§
831®&®rc = &x;                                                     §\C{// error, cannot change rc}§
832const int & const crc = cx;                     §\C{// must be initialized}§
833crc = 7;                                                        §\C{// error, cannot change cx}§
834®&®crc = &cx;                                           §\C{// error, cannot change crc}§
835\end{cfa}
836Hence, for type ©& const©, there is no pointer assignment, so ©&rc = &x© is disallowed, and \emph{the address value cannot be the null pointer unless an arbitrary pointer is coerced\index{coercion} into the reference}:
837\begin{cfa}
838int & const cr = *0;                            §\C{// where 0 is the int * zero}§
839\end{cfa}
840Note, constant reference-types do not prevent \Index{addressing errors} because of explicit storage-management:
841\begin{cfa}
842int & const cr = *malloc();
843cr = 5;
844free( &cr );
845cr = 7;                                                         §\C{// unsound pointer dereference}§
846\end{cfa}
847
848The position of the ©const© qualifier \emph{after} the pointer/reference qualifier causes confuse for C programmers.
849The ©const© qualifier cannot be moved before the pointer/reference qualifier for C style-declarations;
850\CFA-style declarations (see \VRef{s:Declarations}) attempt to address this issue:
851\begin{quote2}
852\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
853\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
854\begin{cfa}
855®const® * ®const® * const int ccp;
856®const® & ®const® & const int ccr;
857\end{cfa}
858&
859\begin{cfa}
860const int * ®const® * ®const® ccp;
861
862\end{cfa}
863\end{tabular}
864\end{quote2}
865where the \CFA declaration is read left-to-right.
866
867Finally, like pointers, references are usable and composable with other type operators and generators.
868\begin{cfa}
869int w, x, y, z, & ar[3] = { x, y, z }; §\C{// initialize array of references}§
870&ar[1] = &w;                                            §\C{// change reference array element}§
871typeof( ar[1] ) p;                                      §\C{// (gcc) is int, i.e., the type of referenced object}§
872typeof( &ar[1] ) q;                                     §\C{// (gcc) is int \&, i.e., the type of reference}§
873sizeof( ar[1] ) == sizeof( int );       §\C{// is true, i.e., the size of referenced object}§
874sizeof( &ar[1] ) == sizeof( int *)      §\C{// is true, i.e., the size of a reference}§
875\end{cfa}
876
877In contrast to \CFA reference types, \Index*[C++]{\CC{}}'s reference types are all ©const© references, preventing changes to the reference address, so only value assignment is possible, which eliminates half of the \Index{address duality}.
878Also, \CC does not allow \Index{array}s\index{array!reference} of reference\footnote{
879The reason for disallowing arrays of reference is unknown, but possibly comes from references being ethereal (like a textual macro), and hence, replaceable by the referant object.}
880\Index*{Java}'s reference types to objects (all Java objects are on the heap) are like C pointers, which always manipulate the address, and there is no (bit-wise) object assignment, so objects are explicitly cloned by shallow or deep copying, which eliminates half of the address duality.
881
882
883\subsection{Initialization}
884
885\Index{Initialization} is different than \Index{assignment} because initialization occurs on the empty (uninitialized) storage on an object, while assignment occurs on possibly initialized storage of an object.
886There are three initialization contexts in \CFA: declaration initialization, argument/parameter binding, return/temporary binding.
887Because the object being initialized has no value, there is only one meaningful semantics with respect to address duality: it must mean address as there is no pointed-to value.
888In contrast, the left-hand side of assignment has an address that has a duality.
889Therefore, for pointer/reference initialization, the initializing value must be an address not a value.
890\begin{cfa}
891int * p = &x;                                           §\C{// assign address of x}§
892®int * p = x;®                                          §\C{// assign value of x}§
893int & r = x;                                            §\C{// must have address of x}§
894\end{cfa}
895Like the previous example with C pointer-arithmetic, it is unlikely assigning the value of ©x© into a pointer is meaningful (again, a warning is usually given).
896Therefore, for safety, this context requires an address, so it is superfluous to require explicitly taking the address of the initialization object, even though the type is incorrect.
897Note, this is strictly a convenience and safety feature for a programmer.
898Hence, \CFA allows ©r© to be assigned ©x© because it infers a reference for ©x©, by implicitly inserting a address-of operator, ©&©, and it is an error to put an ©&© because the types no longer match due to the implicit dereference.
899Unfortunately, C allows ©p© to be assigned with ©&x© (address) or ©x© (value), but most compilers warn about the latter assignment as being potentially incorrect.
900Similarly, when a reference type is used for a parameter/return type, the call-site argument does not require a reference operator for the same reason.
901\begin{cfa}
902int & f( int & r );                                     §\C{// reference parameter and return}§
903z = f( x ) + f( y );                            §\C{// reference operator added, temporaries needed for call results}§
904\end{cfa}
905Within routine ©f©, it is possible to change the argument by changing the corresponding parameter, and parameter ©r© can be locally reassigned within ©f©.
906Since operator routine ©?+?© takes its arguments by value, the references returned from ©f© are used to initialize compiler generated temporaries with value semantics that copy from the references.
907\begin{cfa}
908int temp1 = f( x ), temp2 = f( y );
909z = temp1 + temp2;
910\end{cfa}
911This \Index{implicit referencing} is crucial for reducing the syntactic burden for programmers when using references;
912otherwise references have the same syntactic  burden as pointers in these contexts.
913
914When a pointer/reference parameter has a ©const© value (immutable), it is possible to pass literals and expressions.
915\begin{cfa}
916void f( ®const® int & cr );
917void g( ®const® int * cp );
918f( 3 );                   g( ®&®3 );
919f( x + y );             g( ®&®(x + y) );
920\end{cfa}
921Here, the compiler passes the address to the literal 3 or the temporary for the expression ©x + y©, knowing the argument cannot be changed through the parameter.
922The ©&© before the constant/expression for the pointer-type parameter (©g©) is a \CFA extension necessary to type match and is a common requirement before a variable in C (\eg ©scanf©).
923Importantly, ©&3© may not be equal to ©&3©, where the references occur across calls because the temporaries maybe different on each call.
924
925\CFA \emph{extends} this semantics to a mutable pointer/reference parameter, and the compiler implicitly creates the necessary temporary (copying the argument), which is subsequently pointed-to by the reference parameter and can be changed.\footnote{
926If whole program analysis is possible, and shows the parameter is not assigned, \ie it is ©const©, the temporary is unnecessary.}
927\begin{cfa}
928void f( int & r );
929void g( int * p );
930f( 3 );                   g( ®&®3 );            §\C{// compiler implicit generates temporaries}§
931f( x + y );             g( ®&®(x + y) );        §\C{// compiler implicit generates temporaries}§
932\end{cfa}
933Essentially, there is an implicit \Index{rvalue} to \Index{lvalue} conversion in this case.\footnote{
934This conversion attempts to address the \newterm{const hell} problem, when the innocent addition of a ©const© qualifier causes a cascade of type failures, requiring an unknown number of additional ©const© qualifiers, until it is discovered a ©const© qualifier cannot be added and all the ©const© qualifiers must be removed.}
935The implicit conversion allows seamless calls to any routine without having to explicitly name/copy the literal/expression to allow the call.
936
937%\CFA attempts to handle pointers and references in a uniform, symmetric manner.
938Finally, C handles \Index{routine object}s in an inconsistent way.
939A routine object is both a pointer and a reference (\Index{particle and wave}).
940\begin{cfa}
941void f( int i );
942void (*fp)( int );                                      §\C{// routine pointer}§
943fp = f;                                                         §\C{// reference initialization}§
944fp = &f;                                                        §\C{// pointer initialization}§
945fp = *f;                                                        §\C{// reference initialization}§
946fp(3);                                                          §\C{// reference invocation}§
947(*fp)(3);                                                       §\C{// pointer invocation}§
948\end{cfa}
949While C's treatment of routine objects has similarity to inferring a reference type in initialization contexts, the examples are assignment not initialization, and all possible forms of assignment are possible (©f©, ©&f©, ©*f©) without regard for type.
950Instead, a routine object should be referenced by a ©const© reference:
951\begin{cfa}
952®const® void (®&® fr)( int ) = f;       §\C{// routine reference}§
953fr = ...                                                        §\C{// error, cannot change code}§
954&fr = ...;                                                      §\C{// changing routine reference}§
955fr( 3 );                                                        §\C{// reference call to f}§
956(*fr)(3);                                                       §\C{// error, incorrect type}§
957\end{cfa}
958because the value of the routine object is a routine literal, \ie the routine code is normally immutable during execution.\footnote{
959Dynamic code rewriting is possible but only in special circumstances.}
960\CFA allows this additional use of references for routine objects in an attempt to give a more consistent meaning for them.
961
962
963\subsection{Address-of Semantics}
964
965In C, ©&E© is an rvalue for any expression ©E©.
966\CFA extends the ©&© (address-of) operator as follows:
967\begin{itemize}
968\item
969if ©R© is an \Index{rvalue} of type ©T &$_1$...&$_r$© where $r \ge 1$ references (©&© symbols) than ©&R© has type ©T ®*®&$_{\color{red}2}$...&$_{\color{red}r}$©, \ie ©T© pointer with $r-1$ references (©&© symbols).
970
971\item
972if ©L© is an \Index{lvalue} of type ©T &$_1$...&$_l$© where $l \ge 0$ references (©&© symbols) then ©&L© has type ©T ®*®&$_{\color{red}1}$...&$_{\color{red}l}$©, \ie ©T© pointer with $l$ references (©&© symbols).
973\end{itemize}
974The following example shows the first rule applied to different \Index{rvalue} contexts:
975\begin{cfa}
976int x, * px, ** ppx, *** pppx, **** ppppx;
977int & rx = x, && rrx = rx, &&& rrrx = rrx ;
978x = rrrx;               // rrrx is an lvalue with type int &&& (equivalent to x)
979px = &rrrx;             // starting from rrrx, &rrrx is an rvalue with type int *&&& (&x)
980ppx = &&rrrx;   // starting from &rrrx, &&rrrx is an rvalue with type int **&& (&rx)
981pppx = &&&rrrx; // starting from &&rrrx, &&&rrrx is an rvalue with type int ***& (&rrx)
982ppppx = &&&&rrrx; // starting from &&&rrrx, &&&&rrrx is an rvalue with type int **** (&rrrx)
983\end{cfa}
984The following example shows the second rule applied to different \Index{lvalue} contexts:
985\begin{cfa}
986int x, * px, ** ppx, *** pppx;
987int & rx = x, && rrx = rx, &&& rrrx = rrx ;
988rrrx = 2;               // rrrx is an lvalue with type int &&& (equivalent to x)
989&rrrx = px;             // starting from rrrx, &rrrx is an rvalue with type int *&&& (rx)
990&&rrrx = ppx;   // starting from &rrrx, &&rrrx is an rvalue with type int **&& (rrx)
991&&&rrrx = pppx; // starting from &&rrrx, &&&rrrx is an rvalue with type int ***& (rrrx)
992\end{cfa}
993
994
995\subsection{Conversions}
996
997C provides a basic implicit conversion to simplify variable usage:
998\begin{enumerate}
999\setcounter{enumi}{-1}
1000\item
1001lvalue to rvalue conversion: ©cv T© converts to ©T©, which allows implicit variable dereferencing.
1002\begin{cfa}
1003int x;
1004x + 1;                  // lvalue variable (int) converts to rvalue for expression
1005\end{cfa}
1006An rvalue has no type qualifiers (©cv©), so the lvalue qualifiers are dropped.
1007\end{enumerate}
1008\CFA provides three new implicit conversion for reference types to simplify reference usage.
1009\begin{enumerate}
1010\item
1011reference to rvalue conversion: ©cv T &© converts to ©T©, which allows implicit reference dereferencing.
1012\begin{cfa}
1013int x, &r = x, f( int p );
1014x = ®r® + f( ®r® );  // lvalue reference converts to rvalue
1015\end{cfa}
1016An rvalue has no type qualifiers (©cv©), so the reference qualifiers are dropped.
1017
1018\item
1019lvalue to reference conversion: \lstinline[deletekeywords={lvalue}]@lvalue-type cv1 T@ converts to ©cv2 T &©, which allows implicitly converting variables to references.
1020\begin{cfa}
1021int x, &r = ®x®, f( int & p ); // lvalue variable (int) convert to reference (int &)
1022f( ®x® );               // lvalue variable (int) convert to reference (int &)
1023\end{cfa}
1024Conversion can restrict a type, where ©cv1© $\le$ ©cv2©, \eg passing an ©int© to a ©const volatile int &©, which has low cost.
1025Conversion can expand a type, where ©cv1© $>$ ©cv2©, \eg passing a ©const volatile int© to an ©int &©, which has high cost (\Index{warning});
1026furthermore, if ©cv1© has ©const© but not ©cv2©, a temporary variable is created to preserve the immutable lvalue.
1027
1028\item
1029rvalue to reference conversion: ©T© converts to ©cv T &©, which allows binding references to temporaries.
1030\begin{cfa}
1031int x, & f( int & p );
1032f( ®x + 3® );   // rvalue parameter (int) implicitly converts to lvalue temporary reference (int &)
1033®&f®(...) = &x; // rvalue result (int &) implicitly converts to lvalue temporary reference (int &)
1034\end{cfa}
1035In both case, modifications to the temporary are inaccessible (\Index{warning}).
1036Conversion expands the temporary-type with ©cv©, which is low cost since the temporary is inaccessible.
1037\end{enumerate}
1038
1039
1040\begin{comment}
1041From: Richard Bilson <rcbilson@gmail.com>
1042Date: Wed, 13 Jul 2016 01:58:58 +0000
1043Subject: Re: pointers / references
1044To: "Peter A. Buhr" <pabuhr@plg2.cs.uwaterloo.ca>
1045
1046As a general comment I would say that I found the section confusing, as you move back and forth
1047between various real and imagined programming languages. If it were me I would rewrite into two
1048subsections, one that specifies precisely the syntax and semantics of reference variables and
1049another that provides the rationale.
1050
1051I don't see any obvious problems with the syntax or semantics so far as I understand them. It's not
1052obvious that the description you're giving is complete, but I'm sure you'll find the special cases
1053as you do the implementation.
1054
1055My big gripes are mostly that you're not being as precise as you need to be in your terminology, and
1056that you say a few things that aren't actually true even though I generally know what you mean.
1057
105820 C provides a pointer type; CFA adds a reference type. Both types contain an address, which is normally a
105921 location in memory.
1060
1061An address is not a location in memory; an address refers to a location in memory. Furthermore it
1062seems weird to me to say that a type "contains" an address; rather, objects of that type do.
1063
106421 Special addresses are used to denote certain states or access co-processor memory. By
106522 convention, no variable is placed at address 0, so addresses like 0, 1, 2, 3 are often used to denote no-value
106623 or other special states.
1067
1068This isn't standard C at all. There has to be one null pointer representation, but it doesn't have
1069to be a literal zero representation and there doesn't have to be more than one such representation.
1070
107123 Often dereferencing a special state causes a memory fault, so checking is necessary
107224 during execution.
1073
1074I don't see the connection between the two clauses here. I feel like if a bad pointer will not cause
1075a memory fault then I need to do more checking, not less.
1076
107724 If the programming language assigns addresses, a program's execution is sound, \ie all
107825 addresses are to valid memory locations.
1079
1080You haven't said what it means to "assign" an address, but if I use my intuitive understanding of
1081the term I don't see how this can be true unless you're assuming automatic storage management.
1082
10831 Program variables are implicit pointers to memory locations generated by the compiler and automatically
10842 dereferenced, as in:
1085
1086There is no reason why a variable needs to have a location in memory, and indeed in a typical
1087program many variables will not. In standard terminology an object identifier refers to data in the
1088execution environment, but not necessarily in memory.
1089
109013 A pointer/reference is a generalization of a variable name, \ie a mutable address that can point to more
109114 than one memory location during its lifetime.
1092
1093I feel like you're off the reservation here. In my world there are objects of pointer type, which
1094seem to be what you're describing here, but also pointer values, which can be stored in an object of
1095pointer type but don't necessarily have to be. For example, how would you describe the value denoted
1096by "&main" in a C program? I would call it a (function) pointer, but that doesn't satisfy your
1097definition.
1098
109916 not occupy storage as the literal is embedded directly into instructions.) Hence, a pointer occupies memory
110017 to store its current address, and the pointer's value is loaded by dereferencing, e.g.:
1101
1102As with my general objection regarding your definition of variables, there is no reason why a
1103pointer variable (object of pointer type) needs to occupy memory.
1104
110521 p2 = p1 + x; // compiler infers *p2 = *p1 + x;
1106
1107What language are we in now?
1108
110924 pointer usage. However, in C, the following cases are ambiguous, especially with pointer arithmetic:
111025 p1 = p2; // p1 = p2 or *p1 = *p2
1111
1112This isn't ambiguous. it's defined to be the first option.
1113
111426 p1 = p1 + 1; // p1 = p1 + 1 or *p1 = *p1 + 1
1115
1116Again, this statement is not ambiguous.
1117
111813 example. Hence, a reference behaves like the variable name for the current variable it is pointing-to. The
111914 simplest way to understand a reference is to imagine the compiler inserting a dereference operator before
112015 the reference variable for each reference qualifier in a declaration, e.g.:
1121
1122It's hard for me to understand who the audience for this part is. I think a practical programmer is
1123likely to be satisfied with "a reference behaves like the variable name for the current variable it
1124is pointing-to," maybe with some examples. Your "simplest way" doesn't strike me as simpler than
1125that. It feels like you're trying to provide a more precise definition for the semantics of
1126references, but it isn't actually precise enough to be a formal specification. If you want to
1127express the semantics of references using rewrite rules that's a great way to do it, but lay the
1128rules out clearly, and when you're showing an example of rewriting keep your
1129references/pointers/values separate (right now, you use \eg "r3" to mean a reference, a pointer,
1130and a value).
1131
113224 Cancellation works to arbitrary depth, and pointer and reference values are interchangeable because both
113325 contain addresses.
1134
1135Except they're not interchangeable, because they have different and incompatible types.
1136
113740 Interestingly, C++ deals with the address duality by making the pointed-to value the default, and prevent-
113841 ing changes to the reference address, which eliminates half of the duality. Java deals with the address duality
113942 by making address assignment the default and requiring field assignment (direct or indirect via methods),
114043 \ie there is no builtin bit-wise or method-wise assignment, which eliminates half of the duality.
1141
1142I can follow this but I think that's mostly because I already understand what you're trying to
1143say. I don't think I've ever heard the term "method-wise assignment" and I don't see you defining
1144it. Furthermore Java does have value assignment of basic (non-class) types, so your summary here
1145feels incomplete. (If it were me I'd drop this paragraph rather than try to save it.)
1146
114711 Hence, for type & const, there is no pointer assignment, so &rc = &x is disallowed, and the address value
114812 cannot be 0 unless an arbitrary pointer is assigned to the reference.
1149
1150Given the pains you've taken to motivate every little bit of the semantics up until now, this last
1151clause ("the address value cannot be 0") comes out of the blue. It seems like you could have
1152perfectly reasonable semantics that allowed the initialization of null references.
1153
115412 In effect, the compiler is managing the
115513 addresses for type & const not the programmer, and by a programming discipline of only using references
115614 with references, address errors can be prevented.
1157
1158Again, is this assuming automatic storage management?
1159
116018 rary binding. For reference initialization (like pointer), the initializing value must be an address (lvalue) not
116119 a value (rvalue).
1162
1163This sentence appears to suggest that an address and an lvalue are the same thing.
1164
116520 int * p = &x; // both &x and x are possible interpretations
1166
1167Are you saying that we should be considering "x" as a possible interpretation of the initializer
1168"&x"? It seems to me that this expression has only one legitimate interpretation in context.
1169
117021 int & r = x; // x unlikely interpretation, because of auto-dereferencing
1171
1172You mean, we can initialize a reference using an integer value? Surely we would need some sort of
1173cast to induce that interpretation, no?
1174
117522 Hence, the compiler implicitly inserts a reference operator, &, before the initialization expression.
1176
1177But then the expression would have pointer type, which wouldn't be compatible with the type of r.
1178
117922 Similarly,
118023 when a reference is used for a parameter/return type, the call-site argument does not require a reference
118124 operator.
1182
1183Furthermore, it would not be correct to use a reference operator.
1184
118545 The implicit conversion allows
11861 seamless calls to any routine without having to explicitly name/copy the literal/expression to allow the call.
11872 While C' attempts to handle pointers and references in a uniform, symmetric manner, C handles routine
11883 variables in an inconsistent way: a routine variable is both a pointer and a reference (particle and wave).
1189
1190After all this talk of how expressions can have both pointer and value interpretations, you're
1191disparaging C because it has expressions that have both pointer and value interpretations?
1192
1193On Sat, Jul 9, 2016 at 4:18 PM Peter A. Buhr <pabuhr@plg.uwaterloo.ca> wrote:
1194> Aaron discovered a few places where "&"s are missing and where there are too many "&", which are
1195> corrected in the attached updated. None of the text has changed, if you have started reading
1196> already.
1197\end{comment}
1198
1199
1200\section{Routine Definition}
1201
1202\CFA also supports a new syntax for routine definition, as well as \Celeven and K\&R routine syntax.
1203The point of the new syntax is to allow returning multiple values from a routine~\cite{Galletly96,CLU}, \eg:
1204\begin{cfa}
1205®[ int o1, int o2, char o3 ]® f( int i1, char i2, char i3 ) {
1206        §\emph{routine body}§
1207}
1208\end{cfa}
1209where routine ©f© has three output (return values) and three input parameters.
1210Existing C syntax cannot be extended with multiple return types because it is impossible to embed a single routine name within multiple return type specifications.
1211
1212In 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{
1213\Index*{Michael Tiemann}, with help from \Index*{Doug Lea}, provided named return values in g++, circa 1989.}
1214The value of each local return variable is automatically returned at routine termination.
1215Declaration qualifiers can only appear at the start of a routine definition, \eg:
1216\begin{cfa}
1217®extern® [ int x ] g( int y ) {§\,§}
1218\end{cfa}
1219Lastly, if there are no output parameters or input parameters, the brackets and/or parentheses must still be specified;
1220in 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:
1221\begin{cfa}
1222\,§] g();                                                     §\C{// no input or output parameters}§
1223[ void ] g( void );                                     §\C{// no input or output parameters}§
1224\end{cfa}
1225
1226Routine f is called as follows:
1227\begin{cfa}
1228[ i, j, ch ] = f( 3, 'a', ch );
1229\end{cfa}
1230The list of return values from f and the grouping on the left-hand side of the assignment is called a \newterm{return list} and discussed in Section 12.
1231
1232\CFA style declarations cannot be used to declare parameters for K\&R style routine definitions because of the following ambiguity:
1233\begin{cfa}
1234int (*f(x))[ 5 ] int x; {}
1235\end{cfa}
1236The 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.
1237Since the strings overlap starting with the open bracket, ©[©, there is an ambiguous interpretation for the string.
1238As well, \CFA-style declarations cannot be used to declare parameters for C-style routine-definitions because of the following ambiguity:
1239\begin{cfa}
1240typedef int foo;
1241int f( int (* foo) );                           §\C{// foo is redefined as a parameter name}§
1242\end{cfa}
1243The 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.
1244The 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 qualifier characters appearing to the right of the type name.
1245The 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.
1246
1247C-style declarations can be used to declare parameters for \CFA style routine definitions, \eg:
1248\begin{cfa}
1249[ int ] f( * int, int * );                      §\C{// returns an integer, accepts 2 pointers to integers}§
1250[ * int, int * ] f( int );                      §\C{// returns 2 pointers to integers, accepts an integer}§
1251\end{cfa}
1252The 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:
1253\begin{cfa}
1254#define ptoa( n, d ) int (*n)[ d ]
1255int f( ptoa( p, 5 ) ) ...                       §\C{// expands to int f( int (*p)[ 5 ] )}§
1256[ int ] f( ptoa( p, 5 ) ) ...           §\C{// expands to [ int ] f( int (*p)[ 5 ] )}§
1257\end{cfa}
1258Again, programmers are highly encouraged to use one declaration form or the other, rather than mixing the forms.
1259
1260
1261\subsection{Named Return Values}
1262
1263\Index{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:
1264\begin{cfa}
1265int f() {
1266        int x;
1267        ... x = 0; ... x = y; ...
1268        return x;
1269}
1270\end{cfa}
1271Because 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:
1272\newline
1273\begin{minipage}{\linewidth}
1274\begin{cfa}
1275®[ int x, int y ]® f() {
1276        int z;
1277        ... x = 0; ... y = z; ...
1278        ®return;®                                                       §\C{// implicitly return x, y}§
1279}
1280\end{cfa}
1281\end{minipage}
1282\newline
1283When the return is encountered, the current values of ©x© and ©y© are returned to the calling routine.
1284As well, ``falling off the end'' of a routine without a ©return© statement is permitted, as in:
1285\begin{cfa}
1286[ int x, int y ] f() {
1287        ...
1288}                                                                               §\C{// implicitly return x, y}§
1289\end{cfa}
1290In this case, the current values of ©x© and ©y© are returned to the calling routine just as if a ©return© had been encountered.
1291
1292Named return values may be used in conjunction with named parameter values;
1293specifically, a return and parameter can have the same name.
1294\begin{cfa}
1295[ int x, int y ] f( int, x, int y ) {
1296        ...
1297}                                                                               §\C{// implicitly return x, y}§
1298\end{cfa}
1299This notation allows the compiler to eliminate temporary variables in nested routine calls.
1300\begin{cfa}
1301[ int x, int y ] f( int, x, int y );    §\C{// prototype declaration}§
1302int a, b;
1303[a, b] = f( f( f( a, b ) ) );
1304\end{cfa}
1305While the compiler normally ignores parameters names in prototype declarations, here they are used to eliminate temporary return-values by inferring that the results of each call are the inputs of the next call, and ultimately, the left-hand side of the assignment.
1306Hence, even without the body of routine ©f© (separate compilation), it is possible to perform a global optimization across routine calls.
1307The compiler warns about naming inconsistencies between routine prototype and definition in this case, and behaviour is \Index{undefined} if the programmer is inconsistent.
1308
1309
1310\subsection{Routine Prototype}
1311
1312The syntax of the new routine prototype declaration follows directly from the new routine definition syntax;
1313as well, parameter names are optional, \eg:
1314\begin{cfa}
1315[ int x ] f ();                                                 §\C{// returning int with no parameters}§
1316[ * int ] g (int y);                                    §\C{// returning pointer to int with int parameter}§
1317[ ] h ( int, char );                                    §\C{// returning no result with int and char parameters}§
1318[ * int, int ] j ( int );                               §\C{// returning pointer to int and int, with int parameter}§
1319\end{cfa}
1320This syntax allows a prototype declaration to be created by cutting and pasting source text from the routine definition header (or vice versa).
1321It 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}), \eg:
1322\begin{quote2}
1323\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
1324\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{C}}        \\
1325\begin{cfa}
1326[ int ] f( int ), g;
1327\end{cfa}
1328&
1329\begin{cfa}
1330int f( int ), g( int );
1331\end{cfa}
1332\end{tabular}
1333\end{quote2}
1334Declaration qualifiers can only appear at the start of a \CFA routine declaration,\footref{StorageClassSpecifier} \eg:
1335\begin{cfa}
1336extern [ int ] f ( int );
1337static [ int ] g ( int );
1338\end{cfa}
1339
1340
1341\section{Routine Pointers}
1342
1343The syntax for pointers to \CFA routines specifies the pointer name on the right, \eg:
1344\begin{cfa}
1345* [ int x ] () fp;                                              §\C{// pointer to routine returning int with no parameters}§
1346* [ * int ] (int y) gp;                                 §\C{// pointer to routine returning pointer to int with int parameter}§
1347* [ ] (int,char) hp;                                    §\C{// pointer to routine returning no result with int and char parameters}§
1348* [ * int,int ] ( int ) jp;                             §\C{// pointer to routine returning pointer to int and int, with int parameter}§
1349\end{cfa}
1350While parameter names are optional, \emph{a routine name cannot be specified};
1351for example, the following is incorrect:
1352\begin{cfa}
1353* [ int x ] f () fp;                                    §\C{// routine name "f" is not allowed}§
1354\end{cfa}
1355
1356
1357\section{Named and Default Arguments}
1358
1359Named\index{named arguments}\index{arguments!named} and default\index{default arguments}\index{arguments!default} arguments~\cite{Hardgrave76}\footnote{
1360Francez~\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.}
1361are two mechanisms to simplify routine call.
1362Both mechanisms are discussed with respect to \CFA.
1363\begin{description}
1364\item[Named (or Keyword) Arguments:]
1365provide the ability to specify an argument to a routine call using the parameter name rather than the position of the parameter.
1366For example, given the routine:
1367\begin{cfa}
1368void p( int x, int y, int z ) {...}
1369\end{cfa}
1370a positional call is:
1371\begin{cfa}
1372p( 4, 7, 3 );
1373\end{cfa}
1374whereas a named (keyword) call may be:
1375\begin{cfa}
1376p( z : 3, x : 4, y : 7 );       §\C{// rewrite $\Rightarrow$ p( 4, 7, 3 )}§
1377\end{cfa}
1378Here the order of the arguments is unimportant, and the names of the parameters are used to associate argument values with the corresponding parameters.
1379The compiler rewrites a named call into a positional call.
1380The advantages of named parameters are:
1381\begin{itemize}
1382\item
1383Remembering the names of the parameters may be easier than the order in the routine definition.
1384\item
1385Parameter names provide documentation at the call site (assuming the names are descriptive).
1386\item
1387Changes can be made to the order or number of parameters without affecting the call (although the call must still be recompiled).
1388\end{itemize}
1389
1390Unfortunately, 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.
1391For example, the following routine prototypes and definition are all valid.
1392\begin{cfa}
1393void p( int, int, int );                        §\C{// equivalent prototypes}§
1394void p( int x, int y, int z );
1395void p( int y, int x, int z );
1396void p( int z, int y, int x );
1397void p( int q, int r, int s ) {}        §\C{// match with this definition}§
1398\end{cfa}
1399Forcing matching parameter names in routine prototypes with corresponding routine definitions is possible, but goes against a strong tradition in C programming.
1400Alternatively, prototype definitions can be eliminated by using a two-pass compilation, and implicitly creating header files for exports.
1401The former is easy to do, while the latter is more complex.
1402
1403Furthermore, named arguments do not work well in a \CFA-style programming-languages because they potentially introduces a new criteria for type matching.
1404For example, it is technically possible to disambiguate between these two overloaded definitions of ©f© based on named arguments at the call site:
1405\begin{cfa}
1406int f( int i, int j );
1407int f( int x, double y );
1408
1409f( j : 3, i : 4 );                              §\C{// 1st f}§
1410f( x : 7, y : 8.1 );                    §\C{// 2nd f}§
1411f( 4, 5 );                                              §\C{// ambiguous call}§
1412\end{cfa}
1413However, named arguments compound routine resolution in conjunction with conversions:
1414\begin{cfa}
1415f( i : 3, 5.7 );                                §\C{// ambiguous call ?}§
1416\end{cfa}
1417Depending on the cost associated with named arguments, this call could be resolvable or ambiguous.
1418Adding named argument into the routine resolution algorithm does not seem worth the complexity.
1419Therefore, \CFA does \emph{not} attempt to support named arguments.
1420
1421\item[Default Arguments]
1422provide the ability to associate a default value with a parameter so it can be optionally specified in the argument list.
1423For example, given the routine:
1424\begin{cfa}
1425void p( int x = 1, int y = 2, int z = 3 ) {...}
1426\end{cfa}
1427the allowable positional calls are:
1428\begin{cfa}
1429p();                                                    §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§
1430p( 4 );                                                 §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§
1431p( 4, 4 );                                              §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§
1432p( 4, 4, 4 );                                   §\C{// rewrite $\Rightarrow$ p( 4, 4, 4 )}§
1433// empty arguments
1434p(  , 4, 4 );                                   §\C{// rewrite $\Rightarrow$ p( 1, 4, 4 )}§
1435p( 4,  , 4 );                                   §\C{// rewrite $\Rightarrow$ p( 4, 2, 4 )}§
1436p( 4, 4,   );                                   §\C{// rewrite $\Rightarrow$ p( 4, 4, 3 )}§
1437p( 4,  ,   );                                   §\C{// rewrite $\Rightarrow$ p( 4, 2, 3 )}§
1438p(  , 4,   );                                   §\C{// rewrite $\Rightarrow$ p( 1, 4, 3 )}§
1439p(  ,  , 4 );                                   §\C{// rewrite $\Rightarrow$ p( 1, 2, 4 )}§
1440p(  ,  ,   );                                   §\C{// rewrite $\Rightarrow$ p( 1, 2, 3 )}§
1441\end{cfa}
1442Here the missing arguments are inserted from the default values in the parameter list.
1443The compiler rewrites missing default values into explicit positional arguments.
1444The advantages of default values are:
1445\begin{itemize}
1446\item
1447Routines with a large number of parameters are often very generalized, giving a programmer a number of different options on how a computation is performed.
1448For many of these kinds of routines, there are standard or default settings that work for the majority of computations.
1449Without 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.
1450\item
1451When a routine's interface is augmented with new parameters, it extends the interface providing generalizability\footnote{
1452``It should be possible for the implementor of an abstraction to increase its generality.
1453So long as the modified abstraction is a generalization of the original, existing uses of the abstraction will not require change.
1454It 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.
1455This 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}}
1456(somewhat like the generalization provided by inheritance for classes).
1457That is, all existing calls are still valid, although the call must still be recompiled.
1458\end{itemize}
1459The only disadvantage of default arguments is that unintentional omission of an argument may not result in a compiler-time error.
1460Instead, a default value is used, which may not be the programmer's intent.
1461
1462Default values may only appear in a prototype versus definition context:
1463\begin{cfa}
1464void p( int x, int y = 2, int z = 3 );          §\C{// prototype: allowed}§
1465void p( int, int = 2, int = 3 );                        §\C{// prototype: allowed}§
1466void p( int x, int y = 2, int z = 3 ) {}        §\C{// definition: not allowed}§
1467\end{cfa}
1468The reason for this restriction is to allow separate compilation.
1469Multiple prototypes with different default values is an error.
1470\end{description}
1471
1472Ellipse (``...'') arguments present problems when used with default arguments.
1473The conflict occurs because both named and ellipse arguments must appear after positional arguments, giving two possibilities:
1474\begin{cfa}
1475p( /* positional */, ... , /* named */ );
1476p( /* positional */, /* named */, ... );
1477\end{cfa}
1478While it is possible to implement both approaches, the first possibly is more complex than the second, \eg:
1479\begin{cfa}
1480p( int x, int y, int z, ... );
1481p( 1, 4, 5, 6, z : 3, y : 2 ); §\C{// assume p( /* positional */, ... , /* named */ );}§
1482p( 1, z : 3, y : 2, 4, 5, 6 ); §\C{// assume p( /* positional */, /* named */, ... );}§
1483\end{cfa}
1484In 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.
1485Hence, this approach seems significantly more difficult, and hence, confusing and error prone.
1486In the second call, the named arguments separate the positional and ellipse arguments, making it trivial to read the call.
1487
1488The problem is exacerbated with default arguments, \eg:
1489\begin{cfa}
1490void p( int x, int y = 2, int z = 3... );
1491p( 1, 4, 5, 6, z : 3 );         §\C{// assume p( /* positional */, ... , /* named */ );}§
1492p( 1, z : 3, 4, 5, 6 );         §\C{// assume p( /* positional */, /* named */, ... );}§
1493\end{cfa}
1494The first call is an error because arguments 4 and 5 are actually positional not ellipse arguments;
1495therefore, argument 5 subsequently conflicts with the named argument z : 3.
1496In 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.
1497For these reasons, \CFA requires named arguments before ellipse arguments.
1498Finally, 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.
1499
1500Default arguments and overloading (see Section 24) are complementary.
1501While in theory default arguments can be simulated with overloading, as in:
1502\begin{quote2}
1503\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
1504\multicolumn{1}{c@{\hspace{3em}}}{\textbf{default arguments}}   & \multicolumn{1}{c}{\textbf{overloading}}      \\
1505\begin{cfa}
1506void p( int x, int y = 2, int z = 3 ) {...}
1507
1508
1509\end{cfa}
1510&
1511\begin{cfa}
1512void p( int x, int y, int z ) {...}
1513void p( int x ) { p( x, 2, 3 ); }
1514void p( int x, int y ) { p( x, y, 3 ); }
1515\end{cfa}
1516\end{tabular}
1517\end{quote2}
1518the number of required overloaded routines is linear in the number of default values, which is unacceptable growth.
1519In general, overloading should only be used over default arguments if the body of the routine is significantly different.
1520Furthermore, overloading cannot handle accessing default arguments in the middle of a positional list, via a missing argument, such as:
1521\begin{cfa}
1522p( 1, /* default */, 5 );               §\C{// rewrite $\Rightarrow$ p( 1, 2, 5 )}§
1523\end{cfa}
1524
1525Given the \CFA restrictions above, both named and default arguments are backwards compatible.
1526\Index*[C++]{\CC{}} only supports default arguments;
1527\Index*{Ada} supports both named and default arguments.
1528
1529
1530\section{Unnamed Structure Fields}
1531
1532C requires each field of a structure to have a name, except for a bit field associated with a basic type, \eg:
1533\begin{cfa}
1534struct {
1535        int f1;                                 §\C{// named field}§
1536        int f2 : 4;                             §\C{// named field with bit field size}§
1537        int : 3;                                §\C{// unnamed field for basic type with bit field size}§
1538        int ;                                   §\C{// disallowed, unnamed field}§
1539        int *;                                  §\C{// disallowed, unnamed field}§
1540        int (*)( int );                 §\C{// disallowed, unnamed field}§
1541};
1542\end{cfa}
1543This requirement is relaxed by making the field name optional for all field declarations; therefore, all the field declarations in the example are allowed.
1544As for unnamed bit fields, an unnamed field is used for padding a structure to a particular size.
1545A list of unnamed fields is also supported, \eg:
1546\begin{cfa}
1547struct {
1548        int , , ;                               §\C{// 3 unnamed fields}§
1549}
1550\end{cfa}
1551
1552
1553\section{Nesting}
1554
1555Nesting of types and routines is useful for controlling name visibility (\newterm{name hiding}).
1556
1557
1558\subsection{Type Nesting}
1559
1560\CFA allows \Index{type nesting}, and type qualification of the nested types (see \VRef[Figure]{f:TypeNestingQualification}), where as C hoists\index{type hoisting} (refactors) nested types into the enclosing scope and has no type qualification.
1561\begin{figure}
1562\centering
1563\begin{tabular}{@{}l@{\hspace{3em}}l|l@{}}
1564\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C Type Nesting}}      & \multicolumn{1}{c}{\textbf{C Implicit Hoisting}}      & \multicolumn{1}{|c}{\textbf{\CFA}}    \\
1565\hline
1566\begin{cfa}
1567struct S {
1568        enum C { R, G, B };
1569        struct T {
1570                union U { int i, j; };
1571                enum C c;
1572                short int i, j;
1573        };
1574        struct T t;
1575} s;
1576
1577int fred() {
1578        s.t.c = R;
1579        struct T t = { R, 1, 2 };
1580        enum C c;
1581        union U u;
1582}
1583\end{cfa}
1584&
1585\begin{cfa}
1586enum C { R, G, B };
1587union U { int i, j; };
1588struct T {
1589        enum C c;
1590        short int i, j;
1591};
1592struct S {
1593        struct T t;
1594} s;
1595       
1596
1597
1598
1599
1600
1601
1602\end{cfa}
1603&
1604\begin{cfa}
1605struct S {
1606        enum C { R, G, B };
1607        struct T {
1608                union U { int i, j; };
1609                enum C c;
1610                short int i, j;
1611        };
1612        struct T t;
1613} s;
1614
1615int fred() {
1616        s.t.c = ®S.®R;  // type qualification
1617        struct ®S.®T t = { ®S.®R, 1, 2 };
1618        enum ®S.®C c;
1619        union ®S.T.®U u;
1620}
1621\end{cfa}
1622\end{tabular}
1623\caption{Type Nesting / Qualification}
1624\label{f:TypeNestingQualification}
1625\end{figure}
1626In the left example in C, types ©C©, ©U© and ©T© are implicitly hoisted outside of type ©S© into the containing block scope.
1627In the right example in \CFA, the types are not hoisted and accessed using the field-selection operator ``©.©'' for type qualification, as does \Index*{Java}, rather than the \CC type-selection operator ``©::©''.
1628
1629
1630\subsection{Routine Nesting}
1631
1632While \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.
1633For example, the C quick-sort is wrapped into the following polymorphic \CFA routine:
1634\begin{cfa}
1635forall( otype T | { int ?<?( T, T ); } )
1636void qsort( const T * arr, size_t dimension );
1637\end{cfa}
1638which can be used to sort in ascending and descending order by locally redefining the less-than operator into greater-than.
1639\begin{cfa}
1640const unsigned int size = 5;
1641int ia[size];
1642...                                             §\C{// assign values to array ia}§
1643qsort( ia, size );              §\C{// sort ascending order using builtin ?<?}§
1644{
1645        ®int ?<?( int x, int y ) { return x > y; }® §\C{// nested routine}§
1646        qsort( ia, size );      §\C{// sort descending order by local redefinition}§
1647}
1648\end{cfa}
1649
1650Nested routines are not first-class, meaning a nested routine cannot be returned if it has references to variables in its enclosing blocks;
1651the only exception is references to the external block of the translation unit, as these variables persist for the duration of the program.
1652The following program in undefined in \CFA (and Indexc{gcc})
1653\begin{cfa}
1654[* [int]( int )] foo() {                §\C{// int (*foo())( int )}§
1655        int ®i® = 7;
1656        int bar( int p ) {
1657                ®i® += 1;                               §\C{// dependent on local variable}§
1658                sout | ®i® | endl;
1659        }
1660        return bar;                                     §\C{// undefined because of local dependence}§
1661}
1662int main() {
1663        * [int]( int ) fp = foo();      §\C{// int (*fp)( int )}§
1664        sout | fp( 3 ) | endl;
1665}
1666\end{cfa}
1667because
1668
1669Currently, there are no \Index{lambda} expressions, \ie unnamed routines because routine names are very important to properly select the correct routine.
1670
1671
1672\section{Tuples}
1673
1674In C and \CFA, lists of elements appear in several contexts, such as the parameter list for a routine call.
1675(More contexts are added shortly.)
1676A list of such elements is called a \newterm{lexical list}.
1677The general syntax of a lexical list is:
1678\begin{cfa}
1679[ §\emph{exprlist}§ ]
1680\end{cfa}
1681where ©$\emph{exprlist}$© is a list of one or more expressions separated by commas.
1682The brackets, ©[]©, allow differentiating between lexical lists and expressions containing the C comma operator.
1683The following are examples of lexical lists:
1684\begin{cfa}
1685[ x, y, z ]
1686[ 2 ]
1687[ v+w, x*y, 3.14159, f() ]
1688\end{cfa}
1689Tuples are permitted to contain sub-tuples (\ie nesting), such as ©[ [ 14, 21 ], 9 ]©, which is a 2-element tuple whose first element is itself a tuple.
1690Note, a tuple is not a record (structure);
1691a record denotes a single value with substructure, whereas a tuple is multiple values with no substructure (see flattening coercion in Section 12.1).
1692In essence, tuples are largely a compile time phenomenon, having little or no runtime presence.
1693
1694Tuples can be organized into compile-time tuple variables;
1695these variables are of \newterm{tuple type}.
1696Tuple variables and types can be used anywhere lists of conventional variables and types can be used.
1697The general syntax of a tuple type is:
1698\begin{cfa}
1699[ §\emph{typelist}§ ]
1700\end{cfa}
1701where ©$\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.
1702Examples of tuple types include:
1703\begin{cfa}
1704[ unsigned int, char ]
1705[ double, double, double ]
1706[ * int, int * ]                §\C{// mix of CFA and ANSI}§
1707[ * [ 5 ] int, * * char, * [ [ int, int ] ] (int, int) ]
1708\end{cfa}
1709Like 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.
1710
1711Examples of declarations using tuple types are:
1712\begin{cfa}
1713[ int, int ] x;                 §\C{// 2 element tuple, each element of type int}§
1714* [ char, char ] y;             §\C{// pointer to a 2 element tuple}§
1715[ [ int, int ] ] z ([ int, int ]);
1716\end{cfa}
1717The 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.
1718
1719As mentioned, tuples can appear in contexts requiring a list of value, such as an argument list of a routine call.
1720In unambiguous situations, the tuple brackets may be omitted, \eg a tuple that appears as an argument may have its
1721square brackets omitted for convenience; therefore, the following routine invocations are equivalent:
1722\begin{cfa}
1723f( [ 1, x+2, fred() ] );
1724f( 1, x+2, fred() );
1725\end{cfa}
1726Also, 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.
1727For example, the following are all legal:
1728\begin{cfa}
1729[ int, int ] w1;
1730[ int, int, int ] w2;
1731[ void ] f (int, int, int); /* three input parameters of type int */
1732[ void ] g ([ int, int, int ]); /* 3 element tuple as input */
1733f( [ 1, 2, 3 ] );
1734f( w1, 3 );
1735f( 1, w1 );
1736f( w2 );
1737g( [ 1, 2, 3 ] );
1738g( w1, 3 );
1739g( 1, w1 );
1740g( w2 );
1741\end{cfa}
1742Note, in all cases 3 arguments are supplied even though the syntax may appear to supply less than 3. As mentioned, a
1743tuple does not have structure like a record; a tuple is simply converted into a list of components.
1744\begin{rationale}
1745The present implementation of \CFA does not support nested routine calls when the inner routine returns multiple values; \ie a statement such as ©g( f() )© is not supported.
1746Using a temporary variable to store the  results of the inner routine and then passing this variable to the outer routine works, however.
1747\end{rationale}
1748
1749A tuple can contain a C comma expression, provided the expression containing the comma operator is enclosed in parentheses.
1750For instance, the following tuples are equivalent:
1751\begin{cfa}
1752[ 1, 3, 5 ]
1753[ 1, (2, 3), 5 ]
1754\end{cfa}
1755The second element of the second tuple is the expression (2, 3), which yields the result 3.
1756This requirement is the same as for comma expressions in argument lists.
1757
1758Type qualifiers, \ie const and volatile, may modify a tuple type.
1759The 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)], \ie the qualifier is distributed across all of the types in the tuple, \eg:
1760\begin{cfa}
1761const volatile [ int, float, const int ] x;
1762\end{cfa}
1763is equivalent to:
1764\begin{cfa}
1765[ const volatile int, const volatile float, const volatile int ] x;
1766\end{cfa}
1767Declaration qualifiers can only appear at the start of a \CFA tuple declaration4, \eg:
1768\begin{cfa}
1769extern [ int, int ] w1;
1770static [ int, int, int ] w2;
1771\end{cfa}
1772\begin{rationale}
1773Unfortunately, C's syntax for subscripts precluded treating them as tuples.
1774The C subscript list has the form ©[i][j]...© and not ©[i, j, ...]©.
1775Therefore, there is no syntactic way for a routine returning multiple values to specify the different subscript values, \eg ©f[g()]© always means a single subscript value because there is only one set of brackets.
1776Fixing 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.
1777\end{rationale}
1778
1779
1780\subsection{Tuple Coercions}
1781
1782There are four coercions that can be performed on tuples and tuple variables: closing, opening, flattening and structuring.
1783In addition, the coercion of dereferencing can be performed on a tuple variable to yield its value(s), as for other variables.
1784A \newterm{closing coercion} takes a set of values and converts it into a tuple value, which is a contiguous set of values, as in:
1785\begin{cfa}
1786[ int, int, int, int ] w;
1787w = [ 1, 2, 3, 4 ];
1788\end{cfa}
1789First the right-hand tuple is closed into a tuple value and then the tuple value is assigned.
1790
1791An \newterm{opening coercion} is the opposite of closing; a tuple value is converted into a tuple of values, as in:
1792\begin{cfa}
1793[ a, b, c, d ] = w
1794\end{cfa}
1795©w© is implicitly opened to yield a tuple of four values, which are then assigned individually.
1796
1797A \newterm{flattening coercion} coerces a nested tuple, \ie 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:
1798\begin{cfa}
1799[ a, b, c, d ] = [ 1, [ 2, 3 ], 4 ];
1800\end{cfa}
1801First the right-hand tuple is flattened and then the values are assigned individually.
1802Flattening is also performed on tuple types.
1803For example, the type ©[ int, [ int, int ], int ]© can be coerced, using flattening, into the type ©[ int, int, int, int ]©.
1804
1805A \newterm{structuring coercion} is the opposite of flattening;
1806a tuple is structured into a more complex nested tuple.
1807For 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 ]©.
1808In the following example, the last assignment illustrates all the tuple coercions:
1809\begin{cfa}
1810[ int, int, int, int ] w = [ 1, 2, 3, 4 ];
1811int x = 5;
1812[ x, w ] = [ w, x ];            §\C{// all four tuple coercions}§
1813\end{cfa}
1814Starting on the right-hand tuple in the last assignment statement, w is opened, producing a tuple of four values;
1815therefore, the right-hand tuple is now the tuple ©[ [ 1, 2, 3, 4 ], 5 ]©.
1816This 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.
1817The tuple ©[ 2, 3, 4, 5 ]© is then closed to create a tuple value.
1818Finally, ©x© is assigned ©1© and ©w© is assigned the tuple value using multiple assignment (see Section 14).
1819\begin{rationale}
1820A possible additional language extension is to use the structuring coercion for tuples to initialize a complex record with a tuple.
1821\end{rationale}
1822
1823
1824\section{Mass Assignment}
1825
1826\CFA permits assignment to several variables at once using mass assignment~\cite{CLU}.
1827Mass assignment has the following form:
1828\begin{cfa}
1829[ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = §\emph{expr}§;
1830\end{cfa}
1831\index{lvalue}
1832The left-hand side is a tuple of \emph{lvalues}, which is a list of expressions each yielding an address, \ie any data object that can appear on the left-hand side of a conventional assignment statement.
1833©$\emph{expr}$© is any standard arithmetic expression.
1834Clearly, the types of the entities being assigned must be type compatible with the value of the expression.
1835
1836Mass assignment has parallel semantics, \eg the statement:
1837\begin{cfa}
1838[ x, y, z ] = 1.5;
1839\end{cfa}
1840is equivalent to:
1841\begin{cfa}
1842x = 1.5; y = 1.5; z = 1.5;
1843\end{cfa}
1844This semantics is not the same as the following in C:
1845\begin{cfa}
1846x = y = z = 1.5;
1847\end{cfa}
1848as conversions between intermediate assignments may lose information.
1849A more complex example is:
1850\begin{cfa}
1851[ i, y[i], z ] = a + b;
1852\end{cfa}
1853which is equivalent to:
1854\begin{cfa}
1855t = a + b;
1856a1 = &i; a2 = &y[i]; a3 = &z;
1857*a1 = t; *a2 = t; *a3 = t;
1858\end{cfa}
1859The temporary ©t© is necessary to store the value of the expression to eliminate conversion issues.
1860The temporaries for the addresses are needed so that locations on the left-hand side do not change as the values are assigned.
1861In this case, ©y[i]© uses the previous value of ©i© and not the new value set at the beginning of the mass assignment.
1862
1863
1864\section{Multiple Assignment}
1865
1866\CFA also supports the assignment of several values at once, known as multiple assignment~\cite{CLU,Galletly96}.
1867Multiple assignment has the following form:
1868\begin{cfa}
1869[ §\emph{lvalue}§, ... , §\emph{lvalue}§ ] = [ §\emph{expr}§, ... , §\emph{expr}§ ];
1870\end{cfa}
1871\index{lvalue}
1872The left-hand side is a tuple of \emph{lvalues}, and the right-hand side is a tuple of \emph{expr}s.
1873Each \emph{expr} appearing on the right-hand 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.
1874An example of multiple assignment is:
1875\begin{cfa}
1876[ x, y, z ] = [ 1, 2, 3 ];
1877\end{cfa}
1878Here, the values ©1©, ©2© and ©3© are assigned, respectively, to the variables ©x©, ©y© and ©z©.
1879 A more complex example is:
1880\begin{cfa}
1881[ i, y[ i ], z ] = [ 1, i, a + b ];
1882\end{cfa}
1883Here, the values ©1©, ©i© and ©a + b© are assigned to the variables ©i©, ©y[i]© and ©z©, respectively.
1884 Note, the parallel semantics of
1885multiple assignment ensures:
1886\begin{cfa}
1887[ x, y ] = [ y, x ];
1888\end{cfa}
1889correctly interchanges (swaps) the values stored in ©x© and ©y©.
1890The following cases are errors:
1891\begin{cfa}
1892[ a, b, c ] = [ 1, 2, 3, 4 ];
1893[ a, b, c ] = [ 1, 2 ];
1894\end{cfa}
1895because the number of entities in the left-hand tuple is unequal with the right-hand tuple.
1896
1897As 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;
1898both these examples produce indeterminate results:
1899\begin{cfa}
1900f( x++, x++ );                          §\C{// C routine call with side effects in arguments}§
1901[ v1, v2 ] = [ x++, x++ ];      §\C{// side effects in righthand side of multiple assignment}§
1902\end{cfa}
1903
1904
1905\section{Cascade Assignment}
1906
1907As in C, \CFA mass and multiple assignments can be cascaded, producing cascade assignment.
1908Cascade assignment has the following form:
1909\begin{cfa}
1910§\emph{tuple}§ = §\emph{tuple}§ = ... = §\emph{tuple}§;
1911\end{cfa}
1912and it has the same parallel semantics as for mass and multiple assignment.
1913Some examples of cascade assignment are:
1914\begin{cfa}
1915x1 = y1 = x2 = y2 = 0;
1916[ x1, y1 ] = [ x2, y2 ] = [ x3, y3 ];
1917[ x1, y1 ] = [ x2, y2 ] = 0;
1918[ x1, y1 ] = z = 0;
1919\end{cfa}
1920As in C, the rightmost assignment is performed first, \ie assignment parses right to left.
1921
1922
1923\section{Field Tuples}
1924
1925Tuples may be used to select multiple fields of a record by field name.
1926Its general form is:
1927\begin{cfa}
1928§\emph{expr}§ . [ §\emph{fieldlist}§ ]
1929§\emph{expr}§ -> [ §\emph{fieldlist}§ ]
1930\end{cfa}
1931\emph{expr} is any expression yielding a value of type record, \eg ©struct©, ©union©.
1932Each element of \emph{ fieldlist} is an element of the record specified by \emph{expr}.
1933A record-field tuple may be used anywhere a tuple can be used. An example of the use of a record-field tuple is
1934the following:
1935\begin{cfa}
1936struct s {
1937        int f1, f2;
1938        char f3;
1939        double f4;
1940} v;
1941v.[ f3, f1, f2 ] = ['x', 11, 17 ];      §\C{// equivalent to v.f3 = 'x', v.f1 = 11, v.f2 = 17}§
1942f( v.[ f3, f1, f2 ] );                          §\C{// equivalent to f( v.f3, v.f1, v.f2 )}§
1943\end{cfa}
1944Note, the fields appearing in a record-field tuple may be specified in any order;
1945also, it is unnecessary to specify all the fields of a struct in a multiple record-field tuple.
1946
1947If 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:
1948\begin{cfa}
1949struct inner {
1950        int f2, f3;
1951};
1952struct outer {
1953        int f1;
1954        struct inner i;
1955        double f4;
1956} o;
1957
1958o.[ f1, i.[ f2, f3 ], f4 ] = [ 11, 12, 13, 3.14159 ];
1959\end{cfa}
1960
1961
1962\section{Labelled Continue/Break}
1963
1964While C provides ©continue© and ©break© statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
1965Unfortunately, this restriction forces programmers to use \Indexc{goto} to achieve the equivalent control-flow for more than one level of nesting.
1966To prevent having to switch to the ©goto©, \CFA extends the \Indexc{continue}\index{continue@\lstinline $continue$!labelled}\index{labelled!continue@©continue©} and \Indexc{break}\index{break@\lstinline $break$!labelled}\index{labelled!break@©break©} with a target label to support static multi-level exit\index{multi-level exit}\index{static multi-level exit}~\cite{Buhr85,Java}.
1967For both ©continue© and ©break©, the target label must be directly associated with a ©for©, ©while© or ©do© statement;
1968for ©break©, the target label can also be associated with a ©switch©, ©if© or compound (©{}©) statement.
1969\VRef[Figure]{f:MultiLevelResumeTermination} shows the labelled ©continue© and ©break©, specifying which control structure is the target for exit, and the corresponding C program using only ©goto©.
1970The innermost loop has 7 exit points, which cause resumption or termination of one or more of the 7 \Index{nested control-structure}s.
1971
1972\begin{figure}
1973\begin{tabular}{@{\hspace{\parindentlnth}}l@{\hspace{1.5em}}l@{}}
1974\multicolumn{1}{c@{\hspace{1.5em}}}{\textbf{\CFA}}      & \multicolumn{1}{c}{\textbf{C}}        \\
1975\begin{cfa}
1976®LC:® {
1977        ... §declarations§ ...
1978        ®LS:® switch ( ... ) {
1979          case 3:
1980                ®LIF:® if ( ... ) {
1981                        ®LF:® for ( ... ) {
1982                                ®LW:® while ( ... ) {
1983                                        ... break ®LC®; ...                     // terminate compound
1984                                        ... break ®LS®; ...                     // terminate switch
1985                                        ... break ®LIF®; ...                    // terminate if
1986                                        ... continue ®LF;® ...   // resume loop
1987                                        ... break ®LF®; ...                     // terminate loop
1988                                        ... continue ®LW®; ...   // resume loop
1989                                        ... break ®LW®; ...               // terminate loop
1990                                } // while
1991                        } // for
1992                } else {
1993                        ... break ®LIF®; ...                                     // terminate if
1994                } // if
1995        } // switch
1996} // compound
1997\end{cfa}
1998&
1999\begin{cfa}
2000{
2001        ... §declarations§ ...
2002        switch ( ... ) {
2003          case 3:
2004                if ( ... ) {
2005                        for ( ... ) {
2006                                while ( ... ) {
2007                                        ... goto ®LC®; ...
2008                                        ... goto ®LS®; ...
2009                                        ... goto ®LIF®; ...
2010                                        ... goto ®LFC®; ...
2011                                        ... goto ®LFB®; ...
2012                                        ... goto ®LWC®; ...
2013                                        ... goto ®LWB®; ...
2014                                  ®LWC®: ; } ®LWB:® ;
2015                          ®LFC:® ; } ®LFB:® ;
2016                } else {
2017                        ... goto ®LIF®; ...
2018                } ®L3:® ;
2019        } ®LS:® ;
2020} ®LC:® ;
2021\end{cfa}
2022\end{tabular}
2023\caption{Multi-level Resume/Termination}
2024\label{f:MultiLevelResumeTermination}
2025\end{figure}
2026
2027\begin{comment}
2028int main() {
2029  LC: {
2030          LS: switch ( 1 ) {
2031                  case 3:
2032                  LIF: if ( 1 ) {
2033                          LF: for ( ;; ) {
2034                                  LW: while ( 1 ) {
2035                                                break LC;                       // terminate compound
2036                                                break LS;                       // terminate switch
2037                                                break LIF;                      // terminate if
2038                                                continue LF;     // resume loop
2039                                                break LF;                       // terminate loop
2040                                                continue LW;     // resume loop
2041                                                break LW;                 // terminate loop
2042                                        } // while
2043                                } // for
2044                        } else {
2045                                break LIF;                                       // terminate if
2046                        } // if
2047                } // switch
2048        } // compound
2049        {
2050                switch ( 1 ) {
2051                  case 3:
2052                        if ( 1 ) {
2053                                for ( ;; ) {
2054                                        while ( 1 ) {
2055                                                goto LCx;
2056                                                goto LSx;
2057                                                goto LIF;
2058                                                goto LFC;
2059                                                goto LFB;
2060                                                goto LWC;
2061                                                goto LWB;
2062                                          LWC: ; } LWB: ;
2063                                  LFC: ; } LFB: ;
2064                        } else {
2065                                goto LIF;
2066                        } L3: ;
2067                } LSx: ;
2068        } LCx: ;
2069}
2070
2071// Local Variables: //
2072// tab-width: 4 //
2073// End: //
2074\end{comment}
2075
2076
2077Both labelled ©continue© and ©break© are a ©goto©\index{goto@\lstinline $goto$!restricted} restricted in the following ways:
2078\begin{itemize}
2079\item
2080They cannot create a loop, which means only the looping constructs cause looping.
2081This restriction means all situations resulting in repeated execution are clearly delineated.
2082\item
2083They cannot branch into a control structure.
2084This restriction prevents missing initialization at the start of a control structure resulting in undefined behaviour.
2085\end{itemize}
2086The advantage of the labelled ©continue©/©break© is allowing static multi-level exits without having to use the ©goto© statement, and tying control flow to the target control structure rather than an arbitrary point in a program.
2087Furthermore, the location of the label at the \emph{beginning} of the target control structure informs the reader that complex control-flow is occurring in the body of the control structure.
2088With ©goto©, the label is at the end of the control structure, which fails to convey this important clue early enough to the reader.
2089Finally, using an explicit target for the transfer instead of an implicit target allows new constructs to be added or removed without affecting existing constructs.
2090The implicit targets of the current ©continue© and ©break©, \ie the closest enclosing loop or ©switch©, change as certain constructs are added or removed.
2091
2092
2093\section{Switch Statement}
2094
2095C allows a number of questionable forms for the ©switch© statement:
2096\begin{enumerate}
2097\item
2098By default, the end of a ©case© clause\footnote{
2099In this section, the term \emph{case clause} refers to either a ©case© or ©default© clause.}
2100\emph{falls through} to the next ©case© clause in the ©switch© statement;
2101to exit a ©switch© statement from a ©case© clause requires explicitly terminating the clause with a transfer statement, most commonly ©break©:
2102\begin{cfa}
2103switch ( i ) {
2104  case 1:
2105        ...
2106        // fall-through
2107  case 2:
2108        ...
2109        break;  // exit switch statement
2110}
2111\end{cfa}
2112The ability to fall-through to the next clause \emph{is} a useful form of control flow, specifically when a sequence of case actions compound:
2113\begin{quote2}
2114\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
2115\begin{cfa}
2116switch ( argc ) {
2117  case 3:
2118        // open output file
2119        // fall-through
2120  case 2:
2121        // open input file
2122        break;  // exit switch statement
2123  default:
2124        // usage message
2125}
2126\end{cfa}
2127&
2128\begin{cfa}
2129
2130if ( argc == 3 ) {
2131        // open output file
2132        ®// open input file
2133®} else if ( argc == 2 ) {
2134        ®// open input file
2135
2136®} else {
2137        // usage message
2138}
2139\end{cfa}
2140\end{tabular}
2141\end{quote2}
2142In this example, case 2 is always done if case 3 is done.
2143This 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.
2144C also uses fall-through to handle multiple case-values resulting in the same action:
2145\begin{cfa}
2146switch ( i ) {
2147  case 1: case 3: case 5:       // odd values
2148        // same action
2149        break;
2150  case 2: case 4: case 6:       // even values
2151        // same action
2152        break;
2153}
2154\end{cfa}
2155However, this situation is handled in other languages without fall-through by allowing a list of case values.
2156While fall-through itself is not a problem, the problem occurs when fall-through is the default, as this semantics is unintuitive to many programmers and is different from virtually all other programming languages with a ©switch© statement.
2157Hence, 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.
2158
2159\item
2160It is possible to place ©case© clauses on statements nested \emph{within} the body of the ©switch© statement:
2161\begin{cfa}
2162switch ( i ) {
2163  case 0:
2164        if ( j < k ) {
2165                ...
2166          ®case 1:®             // transfer into "if" statement
2167                ...
2168        } // if
2169  case 2:
2170        while ( j < 5 ) {
2171                ...
2172          ®case 3:®             // transfer into "while" statement
2173                ...
2174        } // while
2175} // switch
2176\end{cfa}
2177The problem with this usage is branching into control structures, which is known to cause both comprehension and technical difficulties.
2178The comprehension problem occurs from the inability to determine how control reaches a particular point due to the number of branches leading to it.
2179The technical problem results from the inability to ensure allocation and initialization of variables when blocks are not entered at the beginning.
2180Often transferring into a block can bypass variable declaration and/or its initialization, which results in subsequent errors.
2181There are virtually no positive arguments for this kind of control flow, and therefore, there is a strong impetus to eliminate it.
2182Nevertheless, C does have an idiom where this capability is used, known as ``\Index*{Duff's device}''~\cite{Duff83}:
2183\begin{cfa}
2184register int n = (count + 7) / 8;
2185switch ( count % 8 ) {
2186case 0: do{ *to = *from++;
2187case 7:         *to = *from++;
2188case 6:         *to = *from++;
2189case 5:         *to = *from++;
2190case 4:         *to = *from++;
2191case 3:         *to = *from++;
2192case 2:         *to = *from++;
2193case 1:         *to = *from++;
2194                } while ( --n > 0 );
2195}
2196\end{cfa}
2197which unrolls a loop N times (N = 8 above) and uses the ©switch© statement to deal with any iterations not a multiple of N.
2198While efficient, this sort of special purpose usage is questionable:
2199\begin{quote}
2200Disgusting, no? But it compiles and runs just fine. I feel a combination of pride and revulsion at this
2201discovery.~\cite{Duff83}
2202\end{quote}
2203\item
2204It is possible to place the ©default© clause anywhere in the list of labelled clauses for a ©switch© statement, rather than only at the end.
2205Virtually all programming languages with a ©switch© statement require the ©default© clause to appear last in the case-clause list.
2206The logic for this semantics is that after checking all the ©case© clauses without success, the ©default© clause is selected;
2207hence, physically placing the ©default© clause at the end of the ©case© clause list matches with this semantics.
2208This physical placement can be compared to the physical placement of an ©else© clause at the end of a series of connected ©if©/©else© statements.
2209
2210\item
2211It is possible to place unreachable code at the start of a ©switch© statement, as in:
2212\begin{cfa}
2213switch ( x ) {
2214        ®int y = 1;®                            §\C{// unreachable initialization}§
2215        ®x = 7;®                                        §\C{// unreachable code without label/branch}§
2216  case 3: ...
2217        ...
2218        ®int z = 0;®                            §\C{// unreachable initialization, cannot appear after case}§
2219        z = 2;
2220  case 3:
2221        ®x = z;®                                        §\C{// without fall through, z is uninitialized}§
2222}
2223\end{cfa}
2224While the declaration of the local variable ©y© is useful with a scope across all ©case© clauses, the initialization for such a variable is defined to never be executed because control always transfers over it.
2225Furthermore, any statements before the first ©case© clause can only be executed if labelled and transferred to using a ©goto©, either from outside or inside of the ©switch©, both of which are problematic.
2226As well, the declaration of ©z© cannot occur after the ©case© because a label can only be attached to a statement, and without a fall through to case 3, ©z© is uninitialized.
2227The key observation is that the ©switch© statement branches into control structure, \ie there are multiple entry points into its statement body.
2228\end{enumerate}
2229
2230Before discussing potential language changes to deal with these problems, it is worth observing that in a typical C program:
2231\begin{itemize}
2232\item
2233the number of ©switch© statements is small,
2234\item
2235most ©switch© statements are well formed (\ie no \Index*{Duff's device}),
2236\item
2237the ©default© clause is usually written as the last case-clause,
2238\item
2239and 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.
2240\end{itemize}
2241These observations help to put the \CFA changes to the ©switch© into perspective.
2242\begin{enumerate}
2243\item
2244Eliminating default fall-through has the greatest potential for affecting existing code.
2245However, 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, the common placement of the ©default© clause at the end of the case list, and the most common use of fall-through, \ie a list of ©case© clauses executing common code, \eg:
2246\begin{cfa}
2247case 1:  case 2:  case 3: ...
2248\end{cfa}
2249still works.
2250Nevertheless, reversing the default action would have a non-trivial effect on case actions that compound, such as the above example of processing shell arguments.
2251Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called ©choose©, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword ©fallthrough©/©fallthru©, e.g.:
2252\begin{cfa}
2253®choose® ( i ) {
2254  case 1:  case 2:  case 3:
2255        ...
2256        ®// implicit end of switch (break)
2257  ®case 5:
2258        ...
2259        ®fallthru®;                                     §\C{// explicit fall through}§
2260  case 7:
2261        ...
2262        ®break®                                         §\C{// explicit end of switch}§
2263  default:
2264        j = 3;
2265}
2266\end{cfa}
2267Like the ©switch© statement, the ©choose© statement retains the fall-through semantics for a list of ©case© clauses;
2268the implicit ©break© is applied only at the end of the \emph{statements} following a ©case© clause.
2269The explicit ©fallthru© is retained because it is a C-idiom most C programmers expect, and its absence might discourage programmers from using the ©choose© statement.
2270As well, allowing an explicit ©break© from the ©choose© is a carry over from the ©switch© statement, and expected by C programmers.
2271\item
2272\Index*{Duff's device} is eliminated from both ©switch© and ©choose© statements, and only invalidates a small amount of very questionable code.
2273Hence, the ©case© clause must appear at the same nesting level as the ©switch©/©choose© body, as is done in most other programming languages with ©switch© statements.
2274\item
2275The 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 needs to appear is locations other than at the end.
2276Therefore, no change is made for this issue.
2277\item
2278Dealing with unreachable code in a ©switch©/©choose© body is solved by restricting declarations and associated initialization to the start of statement body, which is executed \emph{before} the transfer to the appropriate ©case© clause\footnote{
2279Essentially, these declarations are hoisted before the ©switch©/©choose© statement and both declarations and statement are surrounded by a compound statement.} and precluding statements before the first ©case© clause.
2280Further declarations at the same nesting level as the statement body are disallowed to ensure every transfer into the body is sound.
2281\begin{cfa}
2282switch ( x ) {
2283        ®int i = 0;®                            §\C{// allowed only at start}§
2284  case 0:
2285        ...
2286        ®int j = 0;®                            §\C{// disallowed}§
2287  case 1:
2288        {
2289                ®int k = 0;®                    §\C{// allowed at different nesting levels}§
2290                ...
2291        }
2292  ...
2293}
2294\end{cfa}
2295\end{enumerate}
2296
2297
2298\section{Case Clause}
2299
2300C restricts the ©case© clause of a ©switch© statement to a single value.
2301For multiple ©case© clauses associated with the same statement, it is necessary to have multiple ©case© clauses rather than multiple values.
2302Requiring a ©case© clause for each value does not seem to be in the spirit of brevity normally associated with C.
2303Therefore, the ©case© clause is extended with a list of values, as in:
2304\begin{quote2}
2305\begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
2306\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{C}} \\
2307\begin{cfa}
2308switch ( i ) {
2309  case ®1, 3, 5®:
2310        ...
2311  case ®2, 4, 6®:
2312        ...
2313}
2314\end{cfa}
2315&
2316\begin{cfa}
2317switch ( i ) {
2318  case 1: case 3 : case 5:
2319        ...
2320  case 2: case 4 : case 6:
2321        ...
2322}
2323\end{cfa}
2324&
2325\begin{cfa}
2326
2327// odd values
2328
2329// even values
2330
2331
2332\end{cfa}
2333\end{tabular}
2334\end{quote2}
2335In addition, two forms of subranges are allowed to specify case values: a new \CFA form and an existing GNU C form.\footnote{
2336The GNU C form \emph{requires} spaces around the ellipse.}
2337\begin{quote2}
2338\begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
2339\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{GNU C}}     \\
2340\begin{cfa}
2341switch ( i ) {
2342  case ®1~5:®
2343        ...
2344  case ®10~15:®
2345        ...
2346}
2347\end{cfa}
2348&
2349\begin{cfa}
2350switch ( i )
2351  case ®1 ... 5®:
2352        ...
2353  case ®10 ... 15®:
2354        ...
2355}
2356\end{cfa}
2357&
2358\begin{cfa}
2359
2360// 1, 2, 3, 4, 5
2361
2362// 10, 11, 12, 13, 14, 15
2363
2364
2365\end{cfa}
2366\end{tabular}
2367\end{quote2}
2368Lists of subranges are also allowed.
2369\begin{cfa}
2370case ®1~5, 12~21, 35~42®:
2371\end{cfa}
2372
2373
2374\section{Exception Handling}
2375
2376Exception handling provides two mechanism: change of control flow from a raise to a handler, and communication from the raise to the handler.
2377\begin{cfa}
2378exception void h( int i );
2379exception int h( int i, double d );
2380
2381void f(...) {
2382        ... throw h( 3 );
2383        ... i = resume h( 3, 5.1 );
2384}
2385
2386try {
2387        f(...);
2388} catch h( int w ) {
2389        // reset
2390} resume h( int p, double x ) {
2391        return 17;  // recover
2392} finally {
2393}
2394\end{cfa}
2395So 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.
2396The 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.
2397
2398
2399\section{I/O Library}
2400\label{s:IOLibrary}
2401\index{input/output library}
2402
2403The goal of \CFA I/O is to simplify the common cases\index{I/O!common case}, while fully supporting polymorphism and user defined types in a consistent way.
2404The \CFA header file for the I/O library is \Indexc{fstream}.
2405
2406The common case is printing out a sequence of variables separated by whitespace.
2407\begin{quote2}
2408\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
2409\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c}{\textbf{\CC}}      \\
2410\begin{cfa}
2411int x = 1, y = 2, z = 3;
2412sout | x ®|® y ®|® z | endl;
2413\end{cfa}
2414&
2415\begin{cfa}
2416
2417cout << x ®<< " "® << y ®<< " "® << z << endl;
2418\end{cfa}
2419\\
2420\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
24211 2 3
2422\end{cfa}
2423&
2424\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
24251 2 3
2426\end{cfa}
2427\end{tabular}
2428\end{quote2}
2429The \CFA form has half as many characters as the \CC form, and is similar to \Index*{Python} I/O with respect to implicit separators.
2430A tuple prints all the tuple's values, each separated by ©", "©.
2431\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2432[int, int] t1 = [1, 2], t2 = [3, 4];
2433sout | t1 | t2 | endl;                                  §\C{// print tuples}§
2434\end{cfa}
2435\begin{cfa}[mathescape=off,showspaces=true,belowskip=0pt]
24361, 2, 3, 4
2437\end{cfa}
2438\CFA uses the logical-or operator for I/O because it is the lowest-priority overloadable operator, other than assignment.
2439Therefore, fewer output expressions require parenthesis.
2440\begin{quote2}
2441\begin{tabular}{@{}ll@{}}
2442\textbf{\CFA:}
2443&
2444\begin{cfa}
2445sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
2446\end{cfa}
2447\\
2448\textbf{\CC:}
2449&
2450\begin{cfa}
2451cout << x * 3 << y + 1 << ®(®z << 2®)® << ®(®x == y®)® << (x | y) << (x || y) << (x > z ? 1 : 2) << endl;
2452\end{cfa}
2453\\
2454&
2455\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
24563 3 12 0 3 1 2
2457\end{cfa}
2458\end{tabular}
2459\end{quote2}
2460Finally, the logical-or operator has a link with the Shell pipe-operator for moving data, where data flows in the correct direction for input but the opposite direction for output.
2461
2462
2463The implicit separator\index{I/O!separator} character (space/blank) is a separator not a terminator.
2464The rules for implicitly adding the separator are:
2465\begin{enumerate}
2466\item
2467A separator does not appear at the start or end of a line.
2468\begin{cfa}[belowskip=0pt]
2469sout | 1 | 2 | 3 | endl;
2470\end{cfa}
2471\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
24721 2 3
2473\end{cfa}
2474
2475\item
2476A separator does not appear before or after a character literal or variable.
2477\begin{cfa}
2478sout | '1' | '2' | '3' | endl;
2479123
2480\end{cfa}
2481
2482\item
2483A separator does not appear before or after a null (empty) C string.
2484\begin{cfa}
2485sout | 1 | "" | 2 | "" | 3 | endl;
2486123
2487\end{cfa}
2488which is a local mechanism to disable insertion of the separator character.
2489
2490\item
2491A separator does not appear before a C string starting with the (extended) \Index*{ASCII}\index{ASCII!extended} characters: \lstinline[mathescape=off,basicstyle=\tt]@([{=$£¥¡¿«@
2492%$
2493\begin{cfa}[mathescape=off]
2494sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥"
2495                | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10 | endl;
2496\end{cfa}
2497%$
2498\begin{cfa}[mathescape=off,basicstyle=\tt,showspaces=true,aboveskip=0pt,belowskip=0pt]
2499x ®(®1 x ®[®2 x ®{®3 x ®=®4 x ®$®5 x ®£®6 x ®¥®7 x ®¡®8 x ®¿®9 x ®«®10
2500\end{cfa}
2501%$
2502where \lstinline[basicstyle=\tt]@¡¿@ are inverted opening exclamation and question marks, and \lstinline[basicstyle=\tt]@«@ is an opening citation mark.
2503
2504\item
2505{\lstset{language=CFA,deletedelim=**[is][]{¢}{¢}}
2506A seperator does not appear after a C string ending with the (extended) \Index*{ASCII}\index{ASCII!extended} characters: \lstinline[basicstyle=\tt]@,.;!?)]}%¢»@
2507\begin{cfa}[belowskip=0pt]
2508sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x"
2509                | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x" | endl;
2510\end{cfa}
2511\begin{cfa}[basicstyle=\tt,showspaces=true,aboveskip=0pt,belowskip=0pt]
25121®,® x 2®.® x 3®;® x 4®!® x 5®?® x 6®%® x 7§\color{red}\textcent§ x 8®»® x 9®)® x 10®]® x 11®}® x
2513\end{cfa}}%
2514where \lstinline[basicstyle=\tt]@»@ is a closing citation mark.
2515
2516\item
2517A seperator does not appear before or after a C string begining/ending with the \Index*{ASCII} quote or whitespace characters: \lstinline[basicstyle=\tt,showspaces=true]@`'": \t\v\f\r\n@
2518\begin{cfa}[belowskip=0pt]
2519sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx" | endl;
2520\end{cfa}
2521\begin{cfa}[basicstyle=\tt,showspaces=true,showtabs=true,aboveskip=0pt,belowskip=0pt]
2522x®`®1®`®x§\color{red}\texttt{'}§2§\color{red}\texttt{'}§x§\color{red}\texttt{"}§3§\color{red}\texttt{"}§x®:®4®:®x® ®5® ®x®      ®6®     ®x
2523\end{cfa}
2524
2525\item
2526If a space is desired before or after one of the special string start/end characters, simply insert a space.
2527\begin{cfa}[belowskip=0pt]
2528sout | "x (§\color{red}\texttt{\textvisiblespace}§" | 1 | "§\color{red}\texttt{\textvisiblespace) x" | 2 | "§\color{red}\texttt{\textvisiblespace}§, x" | 3 | "§\color{red}\texttt{\textvisiblespace}§:x:§\color{red}\texttt{\textvisiblespace}§" | 4 | endl;
2529\end{cfa}
2530\begin{cfa}[basicstyle=\tt,showspaces=true,showtabs=true,aboveskip=0pt,belowskip=0pt]
2531x (® ®1® ®) x 2® ®, x 3® ®:x:® ®4
2532\end{cfa}
2533\end{enumerate}
2534
2535The following routines and \CC-style \Index{manipulator}s control implicit seperation.
2536\begin{enumerate}
2537\item
2538Routines \Indexc{sepSet}\index{manipulator!sepSet@©sepSet©} and \Indexc{sepGet}\index{manipulator!sepGet@©sepGet©} set and get the separator string.
2539The separator string can be at most 16 characters including the ©'\0'© string terminator (15 printable characters).
2540\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2541sepSet( sout, ", $" );                                          §\C{// set separator from " " to ", \$"}§
2542sout | 1 | 2 | 3 | " \"" | ®sepGet( sout )® | "\"" | endl;
2543\end{cfa}
2544%$
2545\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt]
25461, $2, $3 ®", $
2547\end{cfa}
2548%$
2549\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2550sepSet( sout, " " );                                            §\C{// reset separator to " "}§
2551sout | 1 | 2 | 3 | " \"" | ®sepGet( sout )® | "\"" | endl;
2552\end{cfa}
2553\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt]
25541 2 3 ®" "®
2555\end{cfa}
2556
2557\item
2558Manipulators \Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} \emph{locally} toggle printing the separator, \ie the seperator is adjusted only with respect to the next printed item.
2559\begin{cfa}[mathescape=off,belowskip=0pt]
2560sout | sepOn | 1 | 2 | 3 | sepOn | endl;        §\C{// separator at start of line}§
2561\end{cfa}
2562\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
2563 1 2 3
2564\end{cfa}
2565\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2566sout | 1 | sepOff | 2 | 3 | endl;                       §\C{// locally turn off implicit separator}§
2567\end{cfa}
2568\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
256912 3
2570\end{cfa}
2571
2572\item
2573Manipulators \Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} \emph{globally} toggle printing the separator, \ie the seperator is adjusted with respect to all subsequent printed items, unless locally adjusted.
2574\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2575sout | sepDisable | 1 | 2 | 3 | endl;           §\C{// globally turn off implicit separation}§
2576\end{cfa}
2577\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
2578123
2579\end{cfa}
2580\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2581sout | 1 | sepOn | 2 | 3 | endl;                        §\C{// locally turn on implicit separator}§
2582\end{cfa}
2583\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
25841 23
2585\end{cfa}
2586\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2587sout | sepEnable | 1 | 2 | 3 | endl;            §\C{// globally turn on implicit separation}§
2588\end{cfa}
2589\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
25901 2 3
2591\end{cfa}
2592
2593\item
2594Routine \Indexc{sepSetTuple}\index{manipulator!sepSetTuple@©sepSetTuple©} and \Indexc{sepGetTuple}\index{manipulator!sepGetTuple@©sepGetTuple©} get and set the tuple separator-string.
2595The tuple separator-string can be at most 16 characters including the ©'\0'© string terminator (15 printable characters).
2596\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2597sepSetTuple( sout, " " );                                       §\C{// set tuple separator from ", " to " "}§
2598sout | t1 | t2 | " \"" | ®sepGetTuple( sout )® | "\"" | endl;
2599\end{cfa}
2600\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt]
26011 2 3 4 ®" "®
2602\end{cfa}
2603\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2604sepSetTuple( sout, ", " );                                      §\C{// reset tuple separator to ", "}§
2605sout | t1 | t2 | " \"" | ®sepGetTuple( sout )® | "\"" | endl;
2606\end{cfa}
2607\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt]
26081, 2, 3, 4 ®", "®
2609\end{cfa}
2610
2611\item
2612The tuple separator can also be turned on and off.
2613\begin{cfa}[mathescape=off,aboveskip=0pt,belowskip=0pt]
2614sout | sepOn | t1 | sepOff | t2 | endl;         §\C{// locally turn on/off implicit separation}§
2615\end{cfa}
2616\begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
2617, 1, 23, 4
2618\end{cfa}
2619Notice a tuple seperator starts the line because the next item is a tuple.
2620\end{enumerate}
2621
2622\begin{comment}
2623#include <fstream>
2624
2625int main( void ) {
2626        int x = 1, y = 2, z = 3;
2627        sout | x | y | z | endl;
2628        [int, int] t1 = [1, 2], t2 = [3, 4];
2629        sout | t1 | t2 | endl;                                          // print tuple
2630        sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
2631        sout | 1 | 2 | 3 | endl;
2632        sout | '1' | '2' | '3' | endl;
2633        sout | 1 | "" | 2 | "" | 3 | endl;
2634        sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥"
2635                | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10 | endl;
2636        sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x"
2637                | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x" | endl;
2638        sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx" | endl;
2639        sout | "x ( " | 1 | " ) x" | 2 | " , x" | 3 | " :x: " | 4 | endl;
2640
2641        sepSet( sout, ", $" );                                          // set separator from " " to ", $"
2642        sout | 1 | 2 | 3 | " \"" | sepGet( sout ) | "\"" | endl;
2643        sepSet( sout, " " );                                            // reset separator to " "
2644        sout | 1 | 2 | 3 | " \"" | sepGet( sout ) | "\"" | endl;
2645
2646        sout | sepOn | 1 | 2 | 3 | sepOn | endl;        // separator at start of line
2647        sout | 1 | sepOff | 2 | 3 | endl;                       // locally turn off implicit separator
2648
2649        sout | sepDisable | 1 | 2 | 3 | endl;           // globally turn off implicit separation
2650        sout | 1 | sepOn | 2 | 3 | endl;                        // locally turn on implicit separator
2651        sout | sepEnable | 1 | 2 | 3 | endl;            // globally turn on implicit separation
2652
2653        sepSetTuple( sout, " " );                                       // set tuple separator from ", " to " "
2654        sout | t1 | t2 | " \"" | sepGetTuple( sout ) | "\"" | endl;
2655        sepSetTuple( sout, ", " );                                      // reset tuple separator to ", "
2656        sout | t1 | t2 | " \"" | sepGetTuple( sout ) | "\"" | endl;
2657
2658        sout | t1 | t2 | endl;                                          // print tuple
2659        sout | sepOn | t1 | sepOff | t2 | endl;         // locally turn on/off implicit separation
2660}
2661
2662// Local Variables: //
2663// tab-width: 4 //
2664// fill-column: 100 //
2665// End: //
2666\end{comment}
2667%$
2668
2669
2670\section{Types}
2671
2672\subsection{Type Definitions}
2673
2674\CFA allows users to define new types using the keyword type.
2675
2676\begin{cfa}
2677// SensorValue is a distinct type and represented as an int
2678type SensorValue = int;
2679\end{cfa}
2680
2681A 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.
2682This means that users can define distinct function overloads for the new type (see Overloading for more information).
2683For example:
2684
2685\begin{cfa}
2686type SensorValue = int;
2687void printValue(int v) {...}
2688void printValue(SensorValue v) {...}
2689void process(int v) {...}
2690
2691SensorValue s = ...;
2692
2693printValue(s); // calls version with SensorValue argument
2694
2695printValue((int) s); // calls version with int argument
2696
2697process(s); // implicit conversion to int
2698\end{cfa}
2699
2700If SensorValue was defined with a typedef, then these two print functions would not have unique signatures.
2701This can be very useful to create a distinct type that has the same representation as another type.
2702
2703The compiler will assume it can safely convert from the old type to the new type, implicitly.
2704Users may override this and define a function that must be called to convert from one type to another.
2705
2706\begin{cfa}
2707type SensorValue = int;
2708// ()? is the overloaded conversion operator identifier
2709// This function converts an int to a SensorValue
2710SensorValue ()?(int val) {
2711        ...
2712}
2713void process(int v) {...}
2714
2715SensorValue s = ...;
2716process(s); // implicit call to conversion operator
2717\end{cfa}
2718
2719In many cases, it is not desired for the compiler to do this implicit conversion.
2720To avoid that, the user can use the explicit modifier on the conversion operator.
2721Any places where the conversion is needed but not explicit (with a cast), will result in a compile-time error.
2722
2723\begin{cfa}
2724type SensorValue = int;
2725
2726// conversion from int to SensorValue; must be explicit
2727explicit SensorValue ()?(int val) {
2728        ...
2729}
2730
2731void process(int v) {...}
2732
2733SensorValue s = ...;
2734process(s); // implicit cast to int: compile-time error
2735process((int) s); // explicit cast to int: calls conversion func
2736\end{cfa}
2737
2738The conversion may not require any code, but still need to be explicit; in that case, the syntax can be simplified to:
2739\begin{cfa}
2740type SensorValue = int;
2741explicit SensorValue ()?(int);
2742void process(int v) {...}
2743
2744SensorValue s = ...;
2745process(s); // compile-time error
2746process((int) s); // type is converted, no function is called
2747\end{cfa}
2748
2749
2750\subsection{Structures}
2751
2752Structures in \CFA are basically the same as structures in C.
2753A structure is defined with the same syntax as in C.
2754When referring to a structure in \CFA, users may omit the struct keyword.
2755\begin{cfa}
2756struct Point {
2757        double x;
2758        double y;
2759};
2760
2761Point p = {0.0, 0.0};
2762\end{cfa}
2763
2764\CFA does not support inheritance among types, but instead uses composition to enable reuse of structure fields.
2765Composition is achieved by embedding one type into another.
2766When 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.
2767Embedding types is achieved using anonymous members.
2768For example, using Point from above:
2769\begin{cfa}
2770void foo(Point p);
2771
2772struct ColoredPoint {
2773        Point; // anonymous member (no identifier)
2774        int Color;
2775};
2776...
2777        ColoredPoint cp = ...;
2778        cp.x = 10.3; // x from Point is accessed directly
2779        cp.color = 0x33aaff; // color is accessed normally
2780        foo(cp); // cp can be used directly as a Point
2781\end{cfa}
2782
2783
2784\section{Constructors and Destructors}
2785
2786\CFA supports C initialization of structures, but it also adds constructors for more advanced initialization.
2787Additionally, \CFA adds destructors that are called when a variable is deallocated (variable goes out of scope or object is deleted).
2788These functions take a reference to the structure as a parameter (see References for more information).
2789
2790\begin{figure}
2791\begin{cfa}
2792struct Widget {
2793        int id;
2794        float size;
2795        Parts *optionalParts;
2796};
2797
2798// ?{} is the constructor operator identifier
2799// The first argument is a reference to the type to initialize
2800// Subsequent arguments can be specified for initialization
2801
2802void ?{}(Widget &w) { // default constructor
2803        w.id = -1;
2804        w.size = 0.0;
2805        w.optionalParts = 0;
2806}
2807
2808// constructor with values (does not need to include all fields)
2809void ?{}(Widget &w, int id, float size) {
2810        w.id = id;
2811        w.size = size;
2812        w.optionalParts = 0;
2813}
2814
2815// ^? is the destructor operator identifier
2816void ^?(Widget &w) { // destructor
2817        w.id = 0;
2818        w.size = 0.0;
2819        if (w.optionalParts != 0) {
2820        // This is the only pointer to optionalParts, free it
2821        free(w.optionalParts);
2822        w.optionalParts = 0;
2823        }
2824}
2825
2826Widget baz; // reserve space only
2827Widget foo{}; // calls default constructor
2828Widget bar{23, 2.45}; // calls constructor with values
2829baz{24, 0.91}; // calls constructor with values
2830?{}(baz, 24, 0.91}; // explicit call to constructor
2831^bar; // explicit call to destructor
2832^?(bar); // explicit call to destructor
2833\end{cfa}
2834\caption{Constructors and Destructors}
2835\end{figure}
2836
2837
2838\section{Overloading}
2839
2840Overloading refers to the capability of a programmer to define and use multiple objects in a program with the same name.
2841In \CFA, a declaration may overload declarations from outer scopes with the same name, instead of hiding them as is the case in C.
2842This may cause identical C and \CFA programs to behave differently.
2843The compiler selects the appropriate object (overload resolution) based on context information at the place where it is used.
2844Overloading allows programmers to give functions with different signatures but similar semantics the same name, simplifying the interface to users.
2845Disadvantages 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.
2846\CFA allows overloading of functions, operators, variables, and even the constants 0 and 1.
2847
2848The compiler follows some overload resolution rules to determine the best interpretation of all of these overloads.
2849The best valid interpretations are the valid interpretations that use the fewest unsafe conversions.
2850Of these, the best are those where the functions and objects involved are the least polymorphic.
2851Of these, the best have the lowest total conversion cost, including all implicit conversions in the argument expressions.
2852Of these, the best have the highest total conversion cost for the implicit conversions (if any) applied to the argument expressions.
2853If there is no single best valid interpretation, or if the best valid interpretation is ambiguous, then the resulting interpretation is ambiguous.
2854For details about type inference and overload resolution, please see the \CFA Language Specification.
2855\begin{cfa}
2856int foo(int a, int b) {
2857        float sum = 0.0;
2858        float special = 1.0;
2859        {
2860                int sum = 0;
2861                // both the float and int versions of sum are available
2862                float special = 4.0;
2863                // this inner special hides the outer version
2864                ...
2865        }
2866        ...
2867}
2868\end{cfa}
2869
2870
2871\subsection{Overloaded Constant}
2872
2873The constants 0 and 1 have special meaning.
2874In \CFA, as in C, all scalar types can be incremented and
2875decremented, which is defined in terms of adding or subtracting 1.
2876The 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)©).
2877
2878In 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.
2879However, 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.
2880Defining special constants for a user-defined type is more efficient than defining a conversion to the type from ©_Bool©.
2881
2882Why just 0 and 1? Why not other integers? No other integers have special status in C.
2883A facility that let programmers declare specific constants..const Rational 12., for instance. would not be much of an improvement.
2884Some facility for defining the creation of values of programmer-defined types from arbitrary integer tokens would be needed.
2885The complexity of such a feature does not seem worth the gain.
2886
2887For example, to define the constants for a complex type, the programmer would define the following:
2888
2889\begin{cfa}
2890struct Complex {
2891        double real;
2892        double imaginary;
2893}
2894
2895const Complex 0 = {0, 0};
2896const Complex 1 = {1, 0};
2897...
2898
2899        Complex a = 0;
2900...
2901
2902        a++;
2903...
2904        if (a) { // same as if (a == 0)
2905...
2906}
2907\end{cfa}
2908
2909
2910\subsection{Variable Overloading}
2911
2912The overload rules of \CFA allow a programmer to define multiple variables with the same name, but different types.
2913Allowing 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.
2914For example, a developer may want to do the following:
2915\begin{cfa}
2916int pi = 3;
2917float pi = 3.14;
2918char pi = .p.;
2919\end{cfa}
2920
2921
2922\subsection{Function Overloading}
2923
2924Overloaded 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).
2925
2926The examples below give some basic intuition about how the resolution works.
2927\begin{cfa}
2928// Choose the one with less conversions
2929int doSomething(int value) {...} // option 1
2930int doSomething(short value) {...} // option 2
2931
2932int a, b = 4;
2933short c = 2;
2934
2935a = doSomething(b); // chooses option 1
2936a = doSomething(c); // chooses option 2
2937
2938// Choose the specialized version over the generic
2939
2940generic(type T)
2941T bar(T rhs, T lhs) {...} // option 3
2942float bar(float rhs, float lhs){...} // option 4
2943float a, b, c;
2944double d, e, f;
2945c = bar(a, b); // chooses option 4
2946
2947// specialization is preferred over unsafe conversions
2948
2949f = bar(d, e); // chooses option 5
2950\end{cfa}
2951
2952
2953\subsection{Operator Overloading}
2954
2955\CFA also allows operators to be overloaded, to simplify the use of user-defined types.
2956Overloading 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.
2957\CFA uses the following special identifiers to name overloaded operators:
2958
2959\begin{table}[hbt]
2960\hfil
2961\begin{tabular}[t]{ll}
2962%identifier & operation \\ \hline
2963©?[?]© & subscripting \impl{?[?]}\\
2964©?()© & function call \impl{?()}\\
2965©?++© & postfix increment \impl{?++}\\
2966©?--© & postfix decrement \impl{?--}\\
2967©++?© & prefix increment \impl{++?}\\
2968©--?© & prefix decrement \impl{--?}\\
2969©*?© & dereference \impl{*?}\\
2970©+?© & unary plus \impl{+?}\\
2971©-?© & arithmetic negation \impl{-?}\\
2972©~?© & bitwise negation \impl{~?}\\
2973©!?© & logical complement \impl{"!?}\\
2974©?*?© & multiplication \impl{?*?}\\
2975©?/?© & division \impl{?/?}\\
2976\end{tabular}\hfil
2977\begin{tabular}[t]{ll}
2978%identifier & operation \\ \hline
2979©?%?© & remainder \impl{?%?}\\
2980©?+?© & addition \impl{?+?}\\
2981©?-?© & subtraction \impl{?-?}\\
2982©?<<?© & left shift \impl{?<<?}\\
2983©?>>?© & right shift \impl{?>>?}\\
2984©?<?© & less than \impl{?<?}\\
2985©?<=?© & less than or equal \impl{?<=?}\\
2986©?>=?© & greater than or equal \impl{?>=?}\\
2987©?>?© & greater than \impl{?>?}\\
2988©?==?© & equality \impl{?==?}\\
2989©?!=?© & inequality \impl{?"!=?}\\
2990©?&& bitwise AND \impl{?&?}\\
2991\end{tabular}\hfil
2992\begin{tabular}[t]{ll}
2993%identifier & operation \\ \hline
2994©?^& exclusive OR \impl{?^?}\\
2995©?|?© & inclusive OR \impl{?"|?}\\
2996©?=?© & simple assignment \impl{?=?}\\
2997©?*=?© & multiplication assignment \impl{?*=?}\\
2998©?/=?© & division assignment \impl{?/=?}\\
2999©?%=?© & remainder assignment \impl{?%=?}\\
3000©?+=?© & addition assignment \impl{?+=?}\\
3001©?-=?© & subtraction assignment \impl{?-=?}\\
3002©?<<=?© & left-shift assignment \impl{?<<=?}\\
3003©?>>=?© & right-shift assignment \impl{?>>=?}\\
3004©?&=?© & bitwise AND assignment \impl{?&=?}\\
3005©?^=?© & exclusive OR assignment \impl{?^=?}\\
3006©?|=?© & inclusive OR assignment \impl{?"|=?}\\
3007\end{tabular}
3008\hfil
3009\caption{Operator Identifiers}
3010\label{opids}
3011\end{table}
3012
3013These identifiers are defined such that the question marks in the name identify the location of the operands.
3014These operands represent the parameters to the functions, and define how the operands are mapped to the function call.
3015For example, ©a + b© becomes ©?+?(a, b)©.
3016
3017In the example below, a new type, myComplex, is defined with an overloaded constructor, + operator, and string operator.
3018These operators are called using the normal C syntax.
3019
3020\begin{cfa}
3021type Complex = struct { // define a Complex type
3022        double real;
3023        double imag;
3024}
3025
3026// Constructor with default values
3027
3028void ?{}(Complex &c, double real = 0.0, double imag = 0.0) {
3029        c.real = real;
3030        c.imag = imag;
3031}
3032
3033Complex ?+?(Complex lhs, Complex rhs) {
3034        Complex sum;
3035        sum.real = lhs.real + rhs.real;
3036        sum.imag = lhs.imag + rhs.imag;
3037        return sum;
3038}
3039
3040String ()?(const Complex c) {
3041        // use the string conversions for the structure members
3042        return (String)c.real + . + . + (String)c.imag + .i.;
3043}
3044...
3045
3046Complex a, b, c = {1.0}; // constructor for c w/ default imag
3047...
3048c = a + b;
3049print(.sum = . + c);
3050\end{cfa}
3051
3052
3053\section{Auto Type-Inferencing}
3054
3055Auto type-inferencing occurs in a declaration where a variable's type is inferred from its initialization expression type.
3056\begin{quote2}
3057\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
3058\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CC}} & \multicolumn{1}{c}{\textbf{\Indexc{gcc}}} \\
3059\begin{cfa}
3060
3061auto j = 3.0 * 4;
3062int i;
3063auto k = i;
3064\end{cfa}
3065&
3066\begin{cfa}
3067#define expr 3.0 * i
3068typeof(expr) j = expr;
3069int i;
3070typeof(i) k = i;
3071\end{cfa}
3072&
3073\begin{cfa}
3074
3075// use type of initialization expression
3076
3077// use type of primary variable
3078\end{cfa}
3079\end{tabular}
3080\end{quote2}
3081The two important capabilities are:
3082\begin{itemize}
3083\item
3084preventing having to determine or write out long generic types,
3085\item
3086ensure secondary variables, related to a primary variable, always have the same type.
3087\end{itemize}
3088
3089In \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.
3090\Indexc{gcc} provides ©typeof© to declare a secondary variable from a primary variable.
3091\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.
3092Only for overloaded routines with the same return type is variable type-inferencing possible.
3093Finally, ©auto© presents the programming problem of tracking down a type when the type is actually needed.
3094For example, given
3095\begin{cfa}
3096auto j = ®...®
3097\end{cfa}
3098and the need to write a routine to compute using ©j©
3099\begin{cfa}
3100void rtn( ®...® parm );
3101rtn( j );
3102\end{cfa}
3103A programmer must work backwards to determine the type of ©j©'s initialization expression, reconstructing the possibly long generic type-name.
3104In this situation, having the type name or a short alias is very useful.
3105
3106There is also the conundrum in type inferencing of when to \emph{\Index{brand}} a type.
3107That is, when is the type of the variable more important than the type of its initialization expression.
3108For example, if a change is made in an initialization expression, it can cause hundreds or thousands of cascading type changes and/or errors.
3109At some point, a programmer wants the type of the variable to remain constant and the expression to be in error when it changes.
3110
3111Given ©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.
3112Should a significant need arise, this feature can be revisited.
3113
3114
3115\begin{comment}
3116\section{Generics}
3117
3118\CFA supports parametric polymorphism to allow users to define generic functions and types.
3119Generics allow programmers to use type variables in place of concrete types so that the code can be reused with multiple types.
3120The type parameters can be restricted to satisfy a set of constraints.
3121This enables \CFA to build fully compiled generic functions and types, unlike other languages like \Index*[C++]{\CC{}} where templates are expanded or must be explicitly instantiated.
3122
3123
3124\subsection{Generic Functions}
3125
3126Generic functions in \CFA are similar to template functions in \Index*[C++]{\CC{}}, and will sometimes be expanded into specialized versions, just like in \CC.
3127The 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.
3128This means that compiled libraries can contain generic functions that can be used by programs linked with them (statically or dynamically).
3129Another advantage over \CC templates is unlike templates, generic functions are statically checked, even without being instantiated.
3130
3131A simple example of using Do.s parametric polymorphism to create a generic swap function would look like this:
3132
3133\begin{cfa}
3134generic(type T)
3135void swap(T &a, T &b) {
3136        T tmp = a;
3137        a = b;
3138        b = a;
3139}
3140
3141int a, b;
3142swap(a, b);
3143
3144Point p1, p2;
3145swap(p1, p2);
3146\end{cfa}
3147
3148Here, instead of specifying types for the parameters a and b, the function has a generic type parameter, type T.
3149This 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.
3150
3151
3152\subsection{Bounded Quantification}
3153
3154Some generic functions only work (or make sense) for any type that satisfies a given property.
3155For example, here is a function to pick the minimum of two values of some type.
3156\begin{cfa}
3157generic (type T | bool ?<?(T, T) )
3158
3159T min( T a, T b ) {
3160        return a < b ? a : b;
3161}
3162\end{cfa}
3163
3164It 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.
3165The ordering function used here is the less than operator, <.
3166The syntax used to reference the operator is discussed in further detail in Operator Overloading.
3167In \CFA, this assertion on the type of a generic is written as the bound, (type T | bool ?<?(T, T)).
3168The \CFA compiler enforces that minis only called with types for which the less than operator is defined, and reports a compile-time error otherwise.
3169
3170Bounds can also involve multiple types, and multiple requirements, as shown below:
3171\begin{cfa}
3172generic (type T, type U | { T foo(T, U); U bar(U); })
3173
3174T baz(T t, U u) {
3175        return foo(t, bar(u));
3176}
3177\end{cfa}
3178
3179
3180\subsection{Interfaces}
3181
3182Type bounds as shown above are not very informative, merely requiring that a function exists with the right name and type.
3183Suppose you try to call a polymorphic function and \CFA gives you an error that int combine(int, int) is not defined.
3184Can 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.
3185The function signature doesn't say.
3186
3187Interfaces gather together a set of function signatures under a common name, which solves two problems.
3188First, an interface name can be used in type bounds instead of function signatures.
3189This avoids repetition when a bound is used in many functions.
3190Second, interfaces explicitly document the existence of a commonly used set of functionality, making programs easier to understand.
3191\begin{cfa}
3192generic (type T)
3193interface Orderable {
3194        bool ?<?(T, T);
3195};
3196
3197generic (type T | Orderable(T))
3198T min( T a, T b ) {
3199        return a < b ? a : b;
3200}
3201\end{cfa}
3202
3203This definition of the interface Orderable makes the generic function min easier to read and understand.
3204Orderable can also be reused for other generic functions, max for example.
3205Interfaces can also build on top of other interfaces.
3206For example:
3207\begin{cfa}
3208generic (type T | Orderable(T)
3209interface FooBarable {
3210        int foo(T, T);
3211        int Bar(T, T);
3212};
3213\end{cfa}
3214
3215The FooBarable interface specifies all of the bounds of the Orderable interface, plus the additional bounds specified in its definition.
3216A type does not need to specify that it satisfies any interface, the compiler can figure this out at compile time.
3217For 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.
3218
3219
3220\subsection{Generic Typedefs}
3221
3222Type synonyms can be defined generically using the typedef keyword together with a generic type annotation.
3223These can be used to abbreviate complicated type expressions, especially in generic code.
3224\begin{cfa}
3225// typedef the generic function pointers for later use
3226
3227generic(type T)
3228typedef int (*predicate)(T);
3229generic(type Captured, type T)
3230typedef void (*callback)(Captured, T);
3231
3232generic(type T)
3233void find(int length, T *array,
3234        predicate(T) p, callback(void *, T)f) {
3235        int i;
3236        for (i = 0; i < length; i++)
3237        if (p(array[i])) f(NULL, array[i]);
3238}
3239\end{cfa}
3240
3241
3242\subsection{Generic Types}
3243
3244Generic types are defined using the same mechanisms as those described above for generic functions.
3245This feature allows users to create types that have one or more fields that use generic parameters as types, similar to a template classes in \Index*[C++]{\CC{}}.
3246For 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.
3247In C, something like this would have to be done using void pointers and unsafe casting.
3248As 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.
3249This means that a \CFA generic type from a compiled library can be used with any type that satisfies the bounds.
3250
3251The syntax for defining a generic type looks very similar to that of a generic function.
3252Generic types support bounds and interfaces, using the same syntax as generic functions.
3253\begin{cfa}
3254generic (type T)
3255struct LinkedListElem {
3256        T elem;
3257        LinkedListElem(T) *next;
3258};
3259
3260LinkedListElem *++?(LinkedListElem **elem) {
3261        return *elem = elem->next;
3262}
3263
3264generic (type T)
3265struct LinkedList {
3266        LinkedListElem(T) *head;
3267        unsigned int size;
3268}
3269
3270generic (type T | bool ?==?(T, T))
3271bool contains(LinkedList(T) *list, T elem) {
3272        for(LinkedListElem *iter = list->head; iter != 0; ++iter) {
3273        if (iter->elem == elem) return true;
3274        }
3275        return false;
3276}
3277\end{cfa}
3278
3279
3280\section{Safety}
3281
3282Safety, along with productivity, is a key goal of Do.
3283This section discusses the safety features that have been included in \CFA to help programmers create more stable, reliable, and secure code.
3284
3285
3286\subsection{Exceptions}
3287
3288\CFA introduces support for exceptions as an easier way to recover from exceptional conditions that may be detected within a block of code.
3289In C, developers can use error codes and special return values to report to a caller that an error occurred in a function.
3290The major problem with error codes is that they can be easily ignored by the caller.
3291Failure 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.
3292An unhandled exception on the other hand will cause a crash, revealing the original source of the erroneous state.
3293
3294Exceptions in \CFA allow a different type of control flow.
3295Throwing 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.
3296The exception is immediately re-thrown from the parent block unless it is caught as described below.
3297\CFA uses keywords similar to \Index*[C++]{\CC{}} for exception handling.
3298An exception is thrown using a throw statement, which accepts one argument.
3299
3300\begin{cfa}
3301        ...
3302
3303        throw 13;
3304
3305        ...
3306\end{cfa}
3307
3308An exception can be caught using a catch statement, which specifies the type of the exception it can catch.
3309A catch is specified immediately after a guarded block to signify that it can catch an exception from that block.
3310A guarded block is specified using the try keyword, followed by a block of code inside of curly braces.
3311
3312\begin{cfa}
3313        ...
3314
3315        try {
3316                throw 13;
3317        }
3318        catch(int e) {
3319                printf(.caught an exception: %d\n., e);
3320        }
3321\end{cfa}
3322\end{comment}
3323
3324
3325\subsection{Memory Management}
3326
3327
3328\subsubsection{Manual Memory Management}
3329
3330Using malloc and free to dynamically allocate memory exposes several potential, and common, errors.
3331First, malloc breaks type safety because it returns a pointer to void.
3332There is no relationship between the type that the returned pointer is cast to, and the amount of memory allocated.
3333This problem is solved with a type-safe malloc.
3334Do.s type-safe malloc does not take any arguments for size.
3335Instead, it infers the type based on the return value, and then allocates space for the inferred type.
3336
3337\begin{cfa}
3338float *f = malloc(); // allocates the size of a float
3339
3340struct S {
3341        int i, j, k;
3342};
3343
3344struct S *s = malloc(); // allocates the size of a struct S
3345\end{cfa}
3346
3347In addition to the improved malloc, \CFA also provides a technique for combining allocation and initialization into one step, using the new function.
3348For all constructors defined for a given type (see Operator Overloading), a corresponding call to new can be used to allocate and construct that type.
3349
3350\begin{cfa}
3351type Complex = struct {
3352        float real;
3353        float imag;
3354};
3355
3356// default constructor
3357
3358void ?{}(Complex &c) {
3359        c.real = 0.0;
3360        c.imag = 0.0;
3361}
3362
3363
3364
3365// 2 parameter constructor
3366
3367void ?{}(Complex &c, float real, float imag) {
3368        c.real = real;
3369        c.imag = imag;
3370}
3371
3372
3373int main() {
3374        Complex c1; // No constructor is called
3375        Complex c2{}; // Default constructor called
3376        Complex c3{1.0, -1.0}; // 2 parameter constructor is called
3377
3378        Complex *p1 = malloc(); // allocate
3379        Complex *p2 = new(); // allocate + default constructor
3380        Complex *p3 = new(0.5, 1.0); // allocate + 2 param constructor
3381}
3382\end{cfa}
3383
3384
3385\subsubsection{Automatic Memory Management}
3386
3387\CFA may also support automatic memory management to further improve safety.
3388If 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.
3389This feature requires further investigation.
3390\CFA will not have a garbage collector, but might use some kind of region-based memory management.
3391
3392
3393\begin{comment}
3394\subsection{Unsafe C Constructs}
3395
3396C programmers are able to access all of the low-level tricks that are sometimes needed for close-to-the-hardware programming.
3397Some of these practices however are often error-prone and difficult to read and maintain.
3398Since \CFA is designed to be safer than C, such constructs are disallowed in \CFA code.
3399If 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.
3400This block means that the user is telling the tools, .I know this is unsafe, but I.m going to do it anyway..
3401
3402The 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.
3403Once the full set is decided, the rules will be listed here.
3404\end{comment}
3405
3406
3407\section{Concurrency}
3408
3409Concurrency support in \CFA is implemented on top of a highly efficient runtime system of light-weight, M:N, user level threads.
3410The model integrates concurrency features into the language by making the structure type the core unit of concurrency.
3411All communication occurs through method calls, where data is sent via method arguments, and received via the return value.
3412This enables a very familiar interface to all programmers, even those with no parallel programming experience.
3413It also allows the compiler to do static type checking of all communication, a very important safety feature.
3414This controlled communication with type safety has some similarities with channels in \Index*{Go}, and can actually implement channels exactly, as well as create additional communication patterns that channels cannot.
3415Mutex objects, monitors, are used to contain mutual exclusion within an object and synchronization across concurrent threads.
3416
3417\begin{figure}
3418\begin{cfa}
3419#include <fstream>
3420#include <coroutine>
3421
3422coroutine Fibonacci {
3423        int fn;                                                         §\C{// used for communication}§
3424};
3425void ?{}( Fibonacci * this ) {
3426        this->fn = 0;
3427}
3428void main( Fibonacci * this ) {
3429        int fn1, fn2;                                           §\C{// retained between resumes}§
3430        this->fn = 0;                                           §\C{// case 0}§
3431        fn1 = this->fn;
3432        suspend();                                                      §\C{// return to last resume}§
3433
3434        this->fn = 1;                                           §\C{// case 1}§
3435        fn2 = fn1;
3436        fn1 = this->fn;
3437        suspend();                                                      §\C{// return to last resume}§
3438
3439        for ( ;; ) {                                            §\C{// general case}§
3440                this->fn = fn1 + fn2;
3441                fn2 = fn1;
3442                fn1 = this->fn;
3443                suspend();                                              §\C{// return to last resume}§
3444        } // for
3445}
3446int next( Fibonacci * this ) {
3447        resume( this );                                         §\C{// transfer to last suspend}§
3448        return this->fn;
3449}
3450int main() {
3451        Fibonacci f1, f2;
3452        for ( int i = 1; i <= 10; i += 1 ) {
3453                sout | next( &f1 ) | ' ' | next( &f2 ) | endl;
3454        } // for
3455}
3456\end{cfa}
3457\caption{Fibonacci Coroutine}
3458\label{f:FibonacciCoroutine}
3459\end{figure}
3460
3461
3462\subsection{Coroutine}
3463
3464\Index{Coroutines} are the precursor to tasks.
3465\VRef[Figure]{f:FibonacciCoroutine} shows a coroutine that computes the \Index*{Fibonacci} numbers.
3466
3467
3468\subsection{Monitors}
3469
3470A monitor is a structure in \CFA which includes implicit locking of its fields.
3471Users of a monitor interact with it just like any structure, but the compiler handles code as needed to ensure mutual exclusion.
3472An example of the definition of a monitor is shown here:
3473\begin{cfa}
3474type Account = monitor {
3475        const unsigned long number; // account number
3476        float balance; // account balance
3477};
3478\end{cfa}
3479
3480\begin{figure}
3481\begin{cfa}
3482#include <fstream>
3483#include <kernel>
3484#include <monitor>
3485#include <thread>
3486
3487monitor global_t {
3488        int value;
3489};
3490
3491void ?{}(global_t * this) {
3492        this->value = 0;
3493}
3494
3495static global_t global;
3496
3497void increment3( global_t * mutex this ) {
3498        this->value += 1;
3499}
3500void increment2( global_t * mutex this ) {
3501        increment3( this );
3502}
3503void increment( global_t * mutex this ) {
3504        increment2( this );
3505}
3506
3507thread MyThread {};
3508
3509void main( MyThread* this ) {
3510        for(int i = 0; i < 1_000_000; i++) {
3511                increment( &global );
3512        }
3513}
3514int main(int argc, char* argv[]) {
3515        processor p;
3516        {
3517                MyThread f[4];
3518        }
3519        sout | global.value | endl;
3520}
3521\end{cfa}
3522\caption{Atomic-Counter Monitor}
3523\caption{f:AtomicCounterMonitor}
3524\end{figure}
3525
3526\begin{comment}
3527Since a monitor structure includes an implicit locking mechanism, it does not make sense to copy a monitor;
3528it is always passed by reference.
3529Users can specify to the compiler whether or not a function will require mutual exclusion of the monitor using the mutex modifier on the parameter.
3530When mutex is specified, the compiler inserts locking before executing the body of the function, and unlocking after the body.
3531This means that a function requiring mutual exclusion could block if the lock is already held by another thread.
3532Blocking 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.
3533If multiple mutex parameters are specified, they will be locked in parameter order (\ie first parameter is locked first) and unlocked in the
3534reverse order.
3535\begin{cfa}
3536// This function accesses a constant field, it does not require
3537// mutual exclusion
3538
3539export unsigned long getAccountNumber(Account &a) {
3540        return a.number;
3541}
3542
3543// This function accesses and modifies a shared field; it
3544// requires mutual exclusion
3545
3546export float withdrawal(mutex Account &a, float amount) {
3547        a.balance -= amount;
3548        return a.balance;
3549}
3550\end{cfa}
3551
3552Often, one function using a monitor will call another function using that same monitor.
3553If both require mutual exclusion, then the thread would be waiting for itself to release the lock when it calls the inner function.
3554This 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.
3555It will still be unlocked the same number of times.
3556An example of this situation is shown below:
3557
3558\begin{cfa}
3559// deleting a job from a worker requires mutual exclusion
3560
3561void deleteJob(mutex Worker &w, Job &j) {
3562        ...
3563}
3564
3565// transferring requires mutual exclusion and calls deleteJob
3566
3567void transferJob(mutex Worker &from, Worker &to) {
3568        ...
3569        deleteJob(j);
3570        ...
3571}
3572\end{cfa}
3573\end{comment}
3574
3575
3576\subsection{Tasks}
3577
3578\CFA also provides a simple mechanism for creating and utilizing user level threads.
3579A task provides mutual exclusion like a monitor, and also has its own execution state and a thread of control.
3580Similar to a monitor, a task is defined like a structure:
3581
3582\begin{figure}
3583\begin{cfa}
3584#include <fstream>
3585#include <kernel>
3586#include <stdlib>
3587#include <thread>
3588
3589thread First  { signal_once * lock; };
3590thread Second { signal_once * lock; };
3591
3592void ?{}( First * this, signal_once* lock ) { this->lock = lock; }
3593void ?{}( Second * this, signal_once* lock ) { this->lock = lock; }
3594
3595void main( First * this ) {
3596        for ( int i = 0; i < 10; i += 1 ) {
3597                sout | "First : Suspend No." | i + 1 | endl;
3598                yield();
3599        }
3600        signal( this->lock );
3601}
3602
3603void main( Second * this ) {
3604        wait( this->lock );
3605        for ( int i = 0; i < 10; i += 1 ) {
3606                sout | "Second : Suspend No." | i + 1 | endl;
3607                yield();
3608        }
3609}
3610
3611int main( void ) {
3612        signal_once lock;
3613        sout | "User main begin" | endl;
3614        {
3615                processor p;
3616                {
3617                        First  f = { &lock };
3618                        Second s = { &lock };
3619                }
3620        }
3621        sout | "User main end" | endl;
3622}
3623\end{cfa}
3624\caption{Simple Tasks}
3625\label{f:SimpleTasks}
3626\end{figure}
3627
3628
3629\begin{comment}
3630\begin{cfa}
3631type Adder = task {
3632        int *row;
3633        int size;
3634        int &subtotal;
3635}
3636\end{cfa}
3637
3638A task may define a constructor, which will be called upon allocation and run on the caller.s thread.
3639A destructor may also be defined, which is called at deallocation (when a dynamic object is deleted or when a local object goes out of scope).
3640After a task is allocated and initialized, its thread is spawned implicitly and begins executing in its function call method.
3641All tasks must define this function call method, with a void return value and no additional parameters, or the compiler will report an error.
3642Below are example functions for the above Adder task, and its usage to sum up a matrix on multiple threads.
3643(Note that this example is designed to display the syntax and functionality, not the best method to solve this problem)
3644\begin{cfa}
3645void ?{}(Adder &a, int r[], int s, int &st) { // constructor
3646        a.row = r;
3647        a.size = s;
3648        a.subtotal = st;
3649}
3650
3651// implicitly spawn thread and begin execution here
3652
3653void ?()(Adder &a) {
3654        int c;
3655        subtotal = 0;
3656        for (c=0; c<a.size; ++c) {
3657        subtotal += row[c];
3658        }
3659}
3660
3661int main() {
3662        const int rows = 100, cols = 1000000;
3663        int matrix[rows][cols];
3664        int subtotals[rows];
3665        int total = 0;
3666        int r;
3667
3668        { // create a new scope here for our adders
3669        Adder adders[rows];
3670        // read in the matrix
3671        ...
3672        for (r=0; r<rows; ++r) {
3673        // tasks are initialized on this thread
3674        Adders[r] = {matrix[r], cols, subtotals[r]};
3675        Adders[r](); // spawn thread and begin execution
3676        }
3677        } // adders go out of scope; block here until they all finish
3678        total += subtotals[r];
3679        printf(.total is %d\n., total);
3680}
3681\end{cfa}
3682
3683\subsection{Cooperative Scheduling}
3684
3685Tasks in \CFA are cooperatively scheduled, meaning that a task will not be interrupted by another task, except at specific yield points.
3686In Listing 31, there are no yield points, so each task runs to completion with no interruptions.
3687Places 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.
3688This 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.
3689For example, the code below defines a monitor that maintains a generic list.
3690When 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.
3691Similarly, 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.
3692
3693\begin{cfa}
3694// type T is used as a generic type for all definitions inside
3695// the curly brackets
3696
3697generic(type T) {
3698        type Channel = monitor {
3699        List(T) list; // list is a simple generic list type
3700        };
3701
3702        T pop(mutex &Channel(T) ch) {
3703        if (ch.list.empty()) {
3704        // yield until push is called for this channel
3705        yield(push);
3706        }
3707        return ch.list.pop();
3708        }
3709
3710        void push(mutex &Channel(T)ch, T val) {
3711        if (ch.list.full()) {
3712        // yield until pop is called for this channel
3713        yield(pop);
3714        }
3715        ch.list.push(val);
3716        }
3717}
3718\end{cfa}
3719
3720A task can also yield indefinitely by calling yield with no arguments.
3721This will tell the scheduler to yield this task until it is resumed by some other task.
3722A task can resume another task by using its functional call operator.
3723The code below shows a simple ping-pong example, where two tasks yield back and forth to each other using these methods.
3724
3725\begin{cfa}
3726type Ping = task {
3727        Pong *partner;
3728};
3729
3730void ?{}(Ping &p, Pong *partner = 0) {
3731        p.partner = partner;
3732}
3733
3734void ?()(Ping &p) {
3735        for(;;) { // loop forever
3736        printf(.ping\n.);
3737        partner(); // resumes the partner task
3738        yield(); // yields this task
3739        }
3740}
3741
3742type Pong = task {
3743        Ping *partner;
3744};
3745
3746void ?{}(Pong &p, Ping *partner = 0) {
3747        p.partner = partner;
3748}
3749
3750void ?()(Pong &p) {
3751        for(;;) { // loop forever
3752        yield(); // yields this task
3753        printf(.pong/n.);
3754        partner(); // resumes the partner task
3755        }
3756}
3757
3758void main() {
3759        Ping ping; // allocate ping
3760        Pong pong{ping}; // allocate, initialize, and start pong
3761        Ping{pong}; // initialize and start ping
3762}
3763\end{cfa}
3764
3765The same functionality can be accomplished by providing functions to be called by the partner task.
3766\begin{cfa}
3767type Pingpong = task {
3768        String msg;
3769        Pingpong *partner;
3770};
3771
3772void ?{}(Pingpong &p, String msg, Pingpong *partner = 0) {
3773        p.msg = msg;
3774        p.partner = partner;
3775}
3776
3777void ?()(Pingpong &p) {
3778        for(;;) {
3779        yield(go);
3780        }
3781}
3782
3783void go(Pingpong &p) {
3784        print(.%(p.msg)\n.);
3785        go(p.partner);
3786}
3787
3788void main() {
3789        Pingpong ping = {.ping.};
3790        Pingpong pong = {.pong., ping};
3791        ping.partner = pong;
3792        go(ping);
3793}
3794\end{cfa}
3795\end{comment}
3796
3797
3798\begin{comment}
3799\section{Modules and Packages }
3800
3801High-level encapsulation is useful for organizing code into reusable units, and accelerating compilation speed.
3802\CFA provides a convenient mechanism for creating, building and sharing groups of functionality that enhances productivity and improves compile time.
3803
3804There are two levels of encapsulation in \CFA, module and package.
3805A module is a logical grouping of functionality that can be easily pulled into another project, much like a module in \Index*{Python} or a package in \Index*{Go}.
3806A module forms a namespace to limit the visibility and prevent naming conflicts of variables.
3807Furthermore, a module is an independent translation unit, which can be compiled separately to accelerate the compilation speed.
3808
3809A package is a physical grouping of one or more modules that is used for code distribution and version management.
3810Package is also the level of granularity at which dependences are managed.
3811A package is similar to the Crate in \Index*{Rust}.
3812
3813
3814\subsection{No Declarations, No Header Files}
3815
3816In C and \Index*[C++]{\CC{}}, it is necessary to declare or define every global variable, global function, and type before it is used in each file.
3817Header files and a preprocessor are normally used to avoid repeating code.
3818Thus, many variables, functions, and types are described twice, which exposes an opportunity for errors and causes additional maintenance work.
3819Instead of following this model, the \CFA tools can extract all of the same information from the code automatically.
3820This 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.
3821In 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.
3822This seems like a minor change, but according to (Pike, \Index*{Go} at Google: Language Design in the Service of Software Engineering), this simple change can cause massive reductions in compile time.
3823
3824In \CFA, multiple definitions are not necessary.
3825Within a module, all of the module's global definitions are visible throughout the module.
3826For example, the following code compiles, even though ©isOdd© was not declared before being called:
3827\begin{cfa}
3828bool isEven(unsigned int x) {
3829        if (x == 0) return true;
3830        else return !isOdd(x);
3831}
3832
3833bool isOdd(unsigned int x) {
3834        if (x == 1) return true;
3835        else return !isEven(x - 2);
3836}
3837\end{cfa}
3838
3839Header files in C are used to expose the declarations from a library, so that they can be used externally.
3840With \CFA, this functionality is replaced with module exports, discussed below.
3841When 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.
3842
3843In 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).
3844
3845
3846\subsection{Modules}
3847
3848A 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.
3849These modules can then be easily shared and reused in multiple projects.
3850As modules are intended to be distributed for reuse, they should generally have stable, well-defined interfaces.
3851
3852\CFA adds the following keywords to express the module systems: module, export, import, as.
3853
3854
3855\subsubsection{Module Declaration}
3856
3857The syntax to declare a module is module moduleName;.
3858
3859The module declaration must be at the beginning of a file, and each file can only belong to one module.
3860If there is no module declaration at the beginning of a file, the file belongs to the global module.
3861A module can span several files.
3862By convention, a module and the files belonging to the module have additional mapping relationship which is described in the Do-Lang Tooling documentation.
3863
3864The moduleName follows the same rules of a variable name, except that it can use slash "/" to indicate the module/sub-module relationship.
3865For example, container/vector is a valid module name, where container is the parent module name, and vector is the sub-module under container.
3866
3867Only the interfaces of a module are visible from outside, when the module is imported. export is a type decorator to declare a module interface.
3868A method, a global variable or a type can be declared as a module interface.
3869Types defined in a module and referenced by an exported function or a variable must be exported, too.
3870
3871The following code is a simple module declaration example.
3872\begin{cfa}
3873module M;
3874
3875//visible outside module M
3876
3877export int f(int i) { return i + 1; }
3878export double aCounter;
3879
3880//not visible outside module M
3881
3882int g(int i) { return i - 1; }
3883
3884double bCounter;
3885\end{cfa}
3886
3887export module moduleName; can be use to re-export all the visible (exported) names in moduleName from the current module.
3888
3889
3890\subsubsection{Module Import}
3891
3892The syntax to import a module is import moduleName; or import moduleName as anotherName;.
3893One package cannot be imported with both of the two types of syntax in one file.
3894A package imported in one file will only be visible in this file.
3895For example, two files, A and B belong to the same module.
3896If file A imports another module, M, the exported names in M are not visible in file B.
3897
3898All of the exported names are visible in the file that imports the module.
3899The exported names can be accessed within a namespace based on the module name in the first syntax (ex moduleName.foo).
3900If 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(...);).
3901The 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.
3902Conflicts in namespaces will be reported by the compiler.
3903The second method can be used to solve conflicting name problems.
3904The following code snippets show the two situations.
3905
3906\begin{cfa}
3907module util/counter;
3908export int f(int i) { return i+1; }
3909
3910import util/counter;
3911
3912int main() {
3913        return counter.f(200); // f() from the package counter
3914}
3915
3916import util/counter as ct;
3917int main() {
3918        return ct.f(200); // f() from the package counter
3919}
3920\end{cfa}
3921
3922
3923Additionally, 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.
3924
3925\begin{cfa}
3926module M1;
3927export int f(int i) { return i+1;} // visible outside
3928
3929int g(int i) { return i-1;} // not visible outside
3930
3931module M2;
3932int f(int i) { return i * 2; } // not visible outside
3933export int g(int g) { return i / 2; } // visible outside
3934
3935import M1 as .;
3936
3937import M2 as .;
3938
3939
3940int main() {
3941        return f(3) + g(4); //f() from M1 and g() from M2;
3942}
3943\end{cfa}
3944
3945
3946\subsubsection{Sub-Module and Module Aggregation}
3947
3948Several modules can be organized in a parent module and sub-modules relationship.
3949The sub-module names are based on hierarchical naming, and use slash, "/", to indicate the relationship.
3950For example, std/vector and std/io are sub-modules of module std.
3951The 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
3952not implicitly exported in the parent module.
3953
3954Aggregation is a mechanism to support components and simplified importing.
3955The mechanism is not based on naming but based on manual declaration.
3956For example, the following is the aggregated sequence module.
3957The export {...} is syntactic sugar for many lines of export module aModule;.
3958If an aggregated module is imported, all the included modules in the aggregation are imported.
3959
3960\begin{cfa}
3961module std/sequence;
3962
3963export {
3964        module std/vector;
3965        module std/list;
3966        module std/array;
3967        module std/deque;
3968        module std/forward_list;
3969        module std/queue;
3970        module std/stack;
3971};
3972\end{cfa}
3973
3974After importing the aggregated module, each individual name is still contained in the original name space.
3975For 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.
3976
3977
3978\subsubsection{Import from Repository}
3979
3980When 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).
3981The tools also support retrieving modules of a package from external repositories.
3982See Listing 40: Package directory structure
3983
3984
3985\subsubsection{Package Import}
3986
3987Because 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.
3988In 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;
3989or 2) Adding the package dependence into the current project's Do.prj.
3990More details about locating a module in a package are explained in the next section.
3991
3992
3993\subsubsection{Package Versioning}
3994
3995A package must have a version number.
3996The version number is a string.
3997For example "1.0", "1.a", "A1", and "1ec5fab753eb979d3886a491845b8ae152d58c8f" are all valid version numbers.
3998By convention, a package is stored in a directory named packageName-packageVersion.
3999For example, the util package with version 1.1 is stored in a directory named util-1.1.
4000
4001The project description file can optionally specify the version of the package used in the current project.
4002If 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.
4003The builder tool will record the specific package version used in the build in the project's "Do.lock" file to enable fully repeatable builds.
4004
4005
4006\subsection{Module and Package Organization}
4007
4008\CFA has two level of encapsulations, module and package.
4009This section explains the object model of modules, packages and other language concepts.
4010It also explains how programmers should organize their code, and the method used by the build tools to locate packages, and import modules for compilation.
4011
4012
4013\subsubsection{Object Model}
4014
4015There are several concepts in Do.
4016\begin{itemize}
4017\item
4018File: a \CFA source file
4019\item
4020Module: a container to organize a set of related types and methods; It has a module name, and several interfaces visible from outside
4021\item
4022Package: a container to organize modules for distribution; It has attributes like name, author,
4023version, dependences, etc.
4024\item
4025Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, etc.
4026\end{itemize}
4027
4028The following rules summarize the object model of all the above concepts:
4029\begin{itemize}
4030\item
4031A module contains one or more files
4032\begin{itemize}
4033\item
4034One file can only belong to one module
4035\item
4036A module has its name and interfaces exported
4037\item
4038A file without a module declaration at the beginning belongs to the global module
4039\item
4040\end{itemize}
4041
4042\item
4043A package contains one or more modules
4044\begin{itemize}
4045\item
4046A package has additional meta info described in Do.prj file
4047\item
4048A package may be dependent on other packages.
4049\end{itemize}
4050
4051\item
4052A project contains one or more modules in its source code
4053\begin{itemize}
4054\item
4055A project has additional meta info described in Do.prj file
4056\item
4057A project may be dependent on other packages
4058\item
4059A project can be transformed into a package for distribution
4060\item
4061A project can generate one or more executable binaries
4062\end{itemize}
4063\end{itemize}
4064
4065
4066\subsubsection{Module File Organization}
4067
4068The rules of this section are the conventions to organize module files in one package.
4069
4070The file location of a module in a package must match the module/submodule naming hierarchy.
4071The names separated by slash "/" must match the directory levels.
4072If only one file is used to implement one module, there is no need to put the module implementation file inside a sub-directory.
4073The file can be put inside its parent module's sub-directory with the sub module's name as the file name.
4074
4075Here is an example of a package, util.
4076\begin{cfa}
4077+ util
4078Do.prj #package description file
4079        heap.do #Case 1: module heap;
4080        list.do #Case 1: mdoule list;
4081        ring.do #Case 1: module ring;
4082        + string #Case 2
4083        impl1.do #module string;
4084        + std
4085        vector.do
4086        list.do
4087        + array #Case 3
4088        array1.do #module std/array;
4089        array2.do #module std/array;
4090        sequence.do #Case 4, module std/sequence;
4091        test.do #Case 5
4092\end{cfa}
4093
4094\begin{itemize}
4095\item
4096Case 1: Each individual file implements a module
4097\item
4098Case 2: Put the implementation of a module under the sub-directory, but there is only one file
4099\item
4100Case 3: Put the implementation of a module under the sub-directory; There are several files to
4101implement one module
4102\item
4103Case 4: One file to express one aggregation
4104\item
4105Case 5: The file does not belong to any module; It is used for testing purpose
4106\end{itemize}
4107
4108The example only uses source code, ".do" files, to show the module file organization.
4109Other module packaging formats, like binary, must also follow the same rules.
4110
4111
4112\subsection{Module File Format}
4113
4114\CFA supports different types of module file formats.
4115
4116\begin{itemize}
4117\item
4118Pure source code format: The files should be organized following the previous section's definition.
4119\item
4120IR format (TBD): The \CFA compiler IR format, similar to the source code format
4121\item
4122Binary format, including ".a" static library or ".so" dynamic linkage library
4123\begin{itemize}
4124\item
4125The file's name must match the right level's module name defined in the previous section
4126\item
4127E.g. "util.so" includes all modules for the package util.
4128\item
4129E.g. "string.so" under the package directory to include files belonging to "module string;"
4130\end{itemize}
4131\item.
4132Archive format
4133\begin{itemize}
4134\item
4135The archive is named as ".dar", and is a zip archive of the source code or the binary for a package
4136\item
4137E.g. "util.dar" is the whole package for util package including the package direction file
4138\end{itemize}
4139\item
4140Hybrid format
4141\begin{itemize}
4142\item
4143A package can be distributed partly in source code, partly in binary format, and/or packaged in the archive format
4144\item
4145The only limitation is that the names of the files must match the module location names defined in previous section
4146\end{itemize}
4147\end{itemize}
4148Package and Module Locating and the \CFA Language Tooling documentation for more details.
4149
4150
4151\subsection{Packages}
4152
4153A package is synonymous with a library in other languages.
4154The intent of the package level encapsulation is to facilitate code distribution, version control, and dependence management.
4155A package is a physical grouping of one or more modules in a directory (an archive file for a directory).
4156The 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.
4157
4158
4159\subsubsection{Package Definition}
4160
4161A package is defined by putting a project description file, Do.prj, with one or more modules into a directory.
4162This project description file contains the package's meta data, including package name, author, version, dependences, etc.
4163It should be in the root of the package directory.
4164
4165The modules in the package could be either source code, or compiled binary format.
4166The location of the module files should follow the module name's path.
4167
4168Here is a simple example of the directory structure of a package, core.
4169It contains a module std and several sub-modules under std.
4170\begin{cfa}
4171+ core
4172        Do.prj
4173        + std
4174        + io
4175        file.do # module std/io/file;
4176        network.do #module std/io/network;
4177        + container
4178        vector.do #module std/container/vector;
4179        list.do #module std/container/list;
4180\end{cfa}
4181
4182
4183\subsubsection{Package Import}
4184
4185Because 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.
4186In 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.
4187More details about locating a module in a package are explained in the next section.
4188
4189
4190\subsubsection{Package Versioning}
4191
4192A package must have a version number.
4193The version number is a string.
4194For example "1.0", "1.a", "A1", and "1ec5fab753eb979d3886a491845b8ae152d58c8f" are all valid version numbers.
4195By convention, a package is stored in a directory named packageName-packageVersion.
4196For example, the util package with version 1.1 is stored in a directory named util-1.1.
4197
4198The project description file can optionally specify the version of the package used in the current project.
4199If 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.
4200The builder tool will record the specific package version used in the build in the project's "Do.lock" file to enable fully repeatable builds.
4201
4202
4203\subsection{Module and Package Organization}
4204
4205\CFA has two level of encapsulations, module and package.
4206This section explains the object model of modules, packages and other language concepts.
4207It also explains how programmers should organize their code, and the method used by the build tools to locate packages, and import modules for compilation.
4208
4209
4210\subsubsection{Object Model}
4211
4212There are several concepts in Do.
4213\begin{itemize}
4214\item
4215File: a \CFA source file
4216\item
4217Module: a container to organize a set of related types and methods; It has a module name, and several interfaces visible from outside
4218\item
4219Package: a container to organize modules for distribution; It has attributes like name, author, version, dependences, etc.
4220\item
4221Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, etc.
4222\end{itemize}
4223
4224The following rules summarize the object model of all the above concepts:
4225\begin{itemize}
4226\item
4227A module contains one or more files
4228\begin{itemize}
4229\item
4230One file can only belong to one module
4231\item
4232A module has its name and interfaces exported
4233\item
4234A file without a module declaration at the beginning belongs to the global module
4235\end{itemize}
4236\item
4237A package contains one or more modules
4238\begin{itemize}
4239\item
4240A package has additional meta info described in Do.prj file
4241\item
4242A package may be dependent on other packages.
4243\end{itemize}
4244\item
4245A project contains one or more modules in its source code
4246\begin{itemize}
4247\item
4248A project has additional meta info described in Do.prj file
4249\item
4250A project may be dependent on other packages
4251\item
4252A project can be transformed into a package for distribution
4253\item
4254A project can generate one or more executable binaries
4255\end{itemize}
4256\end{itemize}
4257
4258
4259\subsubsection{Module File Organization}
4260
4261The rules of this section are the conventions to organize module files in one package.
4262
4263The file location of a module in a package must match the module/submodule naming hierarchy.
4264The names separated by slash "/" must match the directory levels.
4265If only one file is used to implement one module, there is no need to put the module implementation file inside a sub-directory.
4266The file can be put inside its parent module's sub-directory with the sub module's name as the file name.
4267
4268Here is an example of a package, util.
4269\begin{cfa}
4270+ util
4271        Do.prj #package description file
4272        heap.do #Case 1: module heap;
4273        list.do #Case 1: mdoule list;
4274        ring.do #Case 1: module ring;
4275        + string #Case 2
4276        impl1.do #module string;
4277        + std
4278        vector.do
4279        list.do
4280        + array #Case 3
4281        array1.do #module std/array;
4282        array2.do #module std/array;
4283        sequence.do #Case 4, module std/sequence;
4284        test.do #Case 5
4285\end{cfa}
4286
4287
4288\begin{itemize}
4289\item
4290Case 1: Each individual file implements a module
4291\item
4292Case 2: Put the implementation of a module under the sub-directory, but there is only one file
4293\item
4294Case 3: Put the implementation of a module under the sub-directory; There are several files to implement one module
4295\item
4296Case 4: One file to express one aggregation
4297\item
4298Case 5: The file does not belong to any module; It is used for testing purpose
4299\end{itemize}
4300
4301The example only uses source code, ".do" files, to show the module file organization.
4302Other module packaging formats, like binary, must also follow the same rules.
4303
4304
4305\subsubsection{Module File Format}
4306
4307\CFA supports different types of module file formats.
4308
4309\begin{itemize}
4310\item
4311Pure source code format: The files should be organized following the previous section's definition.
4312\item
4313IR format (TBD): The \CFA compiler IR format, similar to the source code format
4314\item
4315Binary format, including ".a" static library or ".so" dynamic linkage library
4316\begin{itemize}
4317\item
4318The file's name must match the right level's module name defined in the previous section
4319\item
4320E.g. "util.so" includes all modules for the package util.
4321\item
4322E.g. "string.so" under the package directory to include files belonging to "module string;"
4323\end{itemize}
4324\item
4325Archive format
4326\begin{itemize}
4327\item
4328The archive is named as ".dar", and is a zip archive of the source code or the binary for a package
4329\item
4330E.g. "util.dar" is the whole package for util package including the package direction file
4331\end{itemize}
4332\item
4333Hybrid format
4334\begin{itemize}
4335\item
4336A package can be distributed partly in source code, partly in binary format, and/or packaged in the archive format
4337\item
4338The only limitation is that the names of the files must match the module location names defined in previous section
4339\end{itemize}
4340\end{itemize}
4341
4342
4343\subsection{Package and Module Locating}
4344
4345The 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.
4346If a programmer prefers, one can directly call the compiler, docc to build the source files and create and link to static libraries.
4347
4348When a source file imports a module, the \CFA build tool and docc compiler will locate the module according to the following order:
4349
4350\begin{enumerate}
4351\item
4352This source file's directory tree, which is typically the project's src directory
4353\item
4354All of the dependent packages (in a directory or in an archive file) under the current \CFA project's pkg directory
4355\item
4356The dependent packages (in a directory or in an archive file) inside the paths defined in the DOPATH environment variable
4357\item
4358The dependent packages (in a directory or in an archive file) inside the global \CFA SDK installation's pkg directory
4359\item
4360If 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
4361\end{enumerate}
4362
4363The module found first in a package will shadow the modules with the same name in the later packages in the search sequence.
4364
4365
4366\subsubsection{Dependent Package}
4367
4368Dependent packages are those packages containing modules that the current project's source code will import from.
4369Dependent packages are defined implicitly or explicitly in one \CFA project.
4370All of the packages under the current project's pkg directory are implicitly dependent packages.
4371For others, the dependent packages must be defined in the project's Do.prj file.
4372
4373
4374\subsubsection{Package and Module Locating Example}
4375
4376\begin{cfa}
4377# A project's source code tree
4378
4379--------------------------------------
4380
4381+ testProject
4382        Do.prj
4383        + src
4384        main.do
4385        + pkg
4386        + security-1.1
4387        Do.prj
4388        security.do #module security
4389
4390--------------------------------------
4391
4392# Do.prj
4393
4394--------------------------------------
4395
4396[dependences]
4397std
4398util = "0.2"
4399
4400--------------------------------------
4401
4402# main.do
4403
4404---------------------------------------
4405
4406import security;
4407import std/vector;
4408import container;
4409
4410----------------------------------------
4411\end{cfa}
4412
4413
4414\begin{cfa}
4415# pkg directory's source code tree
4416
4417-----------------------------------------
4418
4419+ pkg
4420        + std-1.0
4421        Do.prj
4422        vector.do #module std/vector;
4423        queue.do #module std/queue;
4424        + std-1.1
4425        Do.prj
4426        vector.do #module std/vector;
4427        queue.do #module std/queue;
4428        list.do #module std/list;
4429        + util-0.1
4430        Do.prj
4431        container.do #module container;
4432        + security-1.0
4433        security.do #module security;
4434------------------------------------------
4435\end{cfa}
4436
4437
4438During the compiling of main.do file import security;
4439The security module appears in both the local security-1.1 package, and the global security-1.0 package.
4440According to the locating sequence, the local security module in security-1.1 will be used.
4441And because the security-1.1 package is under local's pkg directory.
4442No dependence description is required in the project Do.prj file.
4443
4444import std/vector;
4445
4446The 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.
4447
4448import container;
4449
4450The 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.
4451The builder tool then will try to retrieve it from the web and store it in the global pkg directory.
4452After that, the container module from the newly downloaded package will be used in the compilation.
4453\end{comment}
4454
4455
4456\section{Comparison with Other Languages}
4457
4458\CFA is one of many languages that attempts to improve upon C.
4459In developing \CFA, many other languages were consulted for ideas, constructs, and syntax.
4460Therefore, it is important to show how these languages each compare with Do.
4461In this section, \CFA is compared with what the writers of this document consider to be the closest competitors of Do: \Index*[C++]{\CC{}}, \Index*{Go}, \Index*{Rust}, and \Index*{D}.
4462
4463
4464\begin{comment}
4465\subsection[Comparing Key Features of CFA]{Comparing Key Features of \CFA}
4466
4467
4468{% local change to lstlising to reduce font size
4469
4470
4471\lstset{basicstyle=\linespread{0.9}\sf\relsize{-2}}
4472
4473
4474\subsubsection{Constructors and Destructors}
4475
4476\begin{flushleft}
4477\begin{tabular}{@{}l|l|l|l@{}}
4478\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
4479\hline
4480\begin{cfa}
4481struct Line {
4482        float lnth;
4483}
4484// default constructor
4485void ?{}( Line * l ) {
4486        l->lnth = 0.0;
4487        sout | "default" | endl;
4488}
4489
4490
4491// constructor with length
4492void ?{}( Line * l, float lnth ) {
4493        l->lnth = lnth;
4494        sout | "lnth" | l->lnth | endl;
4495
4496}
4497
4498// destructor
4499void ^?() {
4500        sout | "destroyed" | endl;
4501        l.lnth = 0.0;
4502}
4503
4504// usage
4505Line line1;
4506Line line2 = { 3.4 };
4507\end{cfa}
4508&
4509\begin{lstlisting}[language=C++]
4510class Line {
4511        float lnth;
4512
4513        // default constructor
4514        Line() {
4515                cout << "default" << endl;
4516                lnth = 0.0;
4517        }
4518
4519
4520        // constructor with lnth
4521        Line( float l ) {
4522                cout << "length " << length
4523                         << endl;
4524                length = l;
4525        }
4526
4527        // destructor
4528        ~Line() {
4529                cout << "destroyed" << endl;
4530                length = 0.0;
4531        }
4532}
4533// usage
4534Line line1;
4535Line line2( 3.4 );
4536\end{lstlisting}
4537&
4538\begin{lstlisting}[language=Golang]
4539type Line struct {
4540        length float32
4541}
4542// default constructor
4543func makeLine() Line {
4544        fmt.PrintLn( "default" )
4545        return Line{0.0}
4546}
4547
4548
4549// constructor with length
4550func makeLine( length float32 ) Line {
4551        fmt.Printf( "length %v", length )
4552
4553        return Line{length}
4554}
4555
4556// no destructor
4557
4558
4559
4560
4561
4562// usage
4563line1 := makeLine()
4564line2 := makeLine( 3.4 )
4565\end{lstlisting}
4566&
4567\begin{cfa}
4568struct Line {
4569        length: f32
4570}
4571// default constructor
4572impl Default for Line {
4573        fn default () -> Line {
4574                println!( "default" );
4575                Line{ length: 0.0 }
4576        }
4577}
4578// constructor with length
4579impl Line {
4580        fn make( len: f32 ) -> Line {
4581                println!( "length: {}", len );
4582                Line{ length: len }
4583        }
4584}
4585// destructor
4586impl Drop for Line {
4587        fn drop( &mut self ) {
4588                self.length = 0.0
4589        }
4590}
4591// usage
4592let line1:Line = Default::default();
4593Line line2( 3.4 );
4594\end{cfa}
4595\end{tabular}
4596\end{flushleft}
4597
4598
4599\subsubsection{Operator Overloading}
4600
4601\begin{flushleft}
4602\begin{tabular}{@{}l|l|l|l@{}}
4603\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
4604\hline
4605\begin{cfa}
4606struct Cpx {
4607        double re, im;
4608};
4609// overload addition operator
4610Cpx ?+?( Cpx l, const Cpx r ) {
4611        return (Cpx){l.re+l.im, l.im+r.im};
4612}
4613Cpx a, b, c;
4614c = a + b;
4615\end{cfa}
4616&
4617\begin{cfa}
4618struct Cpx {
4619        double re, im;
4620};
4621// overload addition operator
4622Cpx operator+( Cpx l, const Cpx r ) {
4623        return (Cpx){l.re+l.im, l.im+r.im};
4624}
4625Cpx a, b, c;
4626c = a + b;
4627\end{cfa}
4628&
4629\begin{cfa}
4630// no operator overloading
4631
4632
4633
4634
4635
4636
4637
4638\end{cfa}
4639&
4640\begin{cfa}
4641struct Cpx {
4642        re: f32,
4643        im: f32
4644}
4645// overload addition operator
4646impl Add for Cpx {
4647        type Output = Cpx
4648        fn add(self, r: Cpx) -> Cpx {
4649                let mut res = Cpx{re: 0.0, im: 0.0};
4650                res.re = self.re + r.re;
4651                res.im = self.im + r.im;
4652                return res
4653        }
4654}
4655let (a, b, mut c) = ...;
4656c = a + b
4657\end{cfa}
4658\end{tabular}
4659\end{flushleft}
4660
4661
4662\subsubsection{Calling C Functions}
4663
4664\begin{flushleft}
4665\begin{tabular}{@{}l|l|l@{}}
4666\multicolumn{1}{c|}{\textbf{\CFA/\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}   \\
4667\hline
4668\begin{cfa}[boxpos=t]
4669extern "C" {
4670#include <sys/types.h>
4671#include <sys/stat.h>
4672#include <unistd.h>
4673}
4674size_t fileSize( const char *path ) {
4675        struct stat s;
4676        stat(path, &s);
4677        return s.st_size;
4678}
4679\end{cfa}
4680&
4681\begin{cfa}[boxpos=t]
4682/*
4683#cgo
4684#include <sys/types.h>
4685#include <sys/stat.h>
4686#include <unistd.h>
4687*/
4688import "C"
4689import "unsafe"
4690
4691func fileSize(path string) C.size_t {
4692        var buf C.struct_stat
4693        c_string := C.CString(path)
4694        C.stat(p, &buf)
4695        C.free(unsafe.Pointer(c_string))
4696        return buf._st_size
4697}
4698\end{cfa}
4699&
4700\begin{cfa}[boxpos=t]
4701use libc::{c_int, size_t};
4702// translated from sys/stat.h
4703#[repr(C)]
4704struct stat_t {
4705        ...
4706        st_size: size_t,
4707        ...
4708}
4709#[link(name = "libc")]
4710extern {
4711        fn stat(path: *const u8,
4712        buf: *mut stat_t) -> c_int;
4713}
4714fn fileSize(path: *const u8) -> size_t
4715{
4716        unsafe {
4717                let mut buf: stat_t = uninit();
4718                stat(path, &mut buf);
4719                buf.st_size
4720        }
4721}
4722\end{cfa}
4723\end{tabular}
4724\end{flushleft}
4725
4726
4727\subsubsection{Generic Functions}
4728
4729\begin{flushleft}
4730\begin{tabular}{@{}l|l|l|l@{}}
4731\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
4732\hline
4733\begin{cfa}
4734generic(type T, type N |
4735        { int ?<?(N, N); })
4736T *maximize(N (*f)(const T&),
4737        int n, T *a) {
4738        T *bestX = NULL;
4739        N bestN;
4740        for (int i = 0; i < n; i++) {
4741        N curN = f(a[i]);
4742        if (bestX == NULL ||
4743        curN > bestN) {
4744        bestX = &a[i]; bestN = curN;
4745        }
4746        }
4747        return bestX;
4748}
4749
4750string *longest(int n, string *p)
4751{
4752        return maximize(length, n, p);
4753}
4754\end{cfa}
4755&
4756\begin{cfa}
4757template<typename T, typename F>
4758T *maximize(const F &f,
4759        int n, T *a) {
4760        typedef decltype(f(a[0])) N;
4761        T *bestX = NULL;
4762        N bestN;
4763        for (int i = 0; i < n; i++) {
4764        N curN = f(a[i]);
4765        if (bestX == NULL || curN > bestN)
4766        {
4767        bestX = &a[i]; bestN = curN;
4768        }
4769        }
4770        return bestX;
4771}
4772
4773string *longest(int n, string *p) {
4774        return maximize(
4775        [](const string &s) {
4776        return s.length();
4777        }, n, p);
4778}
4779\end{cfa}
4780&
4781\begin{cfa}
4782// Go does not support generics!
4783func maximize(
4784        gt func(interface{}, interface{}) bool,
4785        f func(interface{}) interface{},
4786        a []interface{}) interface{} {
4787        var bestX interface{} = nil
4788        var bestN interface{} = nil
4789        for _, x := range a {
4790        curN := f(x)
4791        if bestX == nil || gt(curN, bestN)
4792        {
4793        bestN = curN
4794        bestX = x
4795        }
4796        }
4797        return bestX
4798}
4799
4800func longest(
4801        a []interface{}) interface{} {
4802        return maximize(
4803        func(a, b interface{}) bool {
4804        return a.(int) > b.(int) },
4805        func(s interface{}) interface{} {
4806        return len(s.(string)) },
4807        a).(string)
4808}
4809\end{cfa}
4810&
4811\begin{cfa}
4812use std::cmp::Ordering;
4813
4814fn maximize<N: Ord + Copy, T, F:
4815Fn(&T) -> N>(f: F, a: &Vec<T>) ->
4816Option<&T> {
4817        let mut best_x: Option<&T> = None;
4818        let mut best_n: Option<N> = None;
4819        for x in a {
4820        let n = f(x);
4821        if (match best_n { None => true,
4822        Some(bn) =>
4823        n.cmp(&bn) == Ordering::Greater })
4824        {
4825        best_x = Some(x);
4826        best_n = Some(n);
4827        }
4828        }
4829        return best_x
4830}
4831
4832fn longest(a: &Vec<String>) ->
4833        Option<&String> {
4834        return
4835        maximize(|x: &String| x.len(), a)
4836}
4837\end{cfa}
4838\end{tabular}
4839\end{flushleft}
4840
4841
4842\subsubsection{Modules / Packages}
4843
4844\begin{cfa}
4845\CFA
4846\CC
4847
4848
4849module example/M;
4850
4851export int inc(int val) {
4852        return val + 1;
4853}
4854
4855
4856
4857
4858--------------------------------------
4859//Use the module in another file
4860import example/M;
4861int main() {
4862        print(M.inc(100));
4863        return 0;
4864}
4865// Using \CC17 module proposal
4866
4867module example.M;
4868
4869export {
4870        int inc(int val);
4871}
4872
4873int inc(inv val) {
4874        return val + 1;
4875}
4876--------------------------------------
4877// Use the module in another file
4878import example.M;
4879int main() {
4880        cout << inc(100) << endl;
4881        return 0;
4882}
4883
4884Go
4885Rust
4886package example/M;
4887
4888func Inc(val int32) int32 {
4889        // Capitalization indicates exported
4890        return val + 100
4891}
4892
4893
4894--------------------------------------
4895//Use the package in another file
4896package main
4897import .fmt.
4898import "example/M"
4899
4900func main() int32 {
4901        fmt.Printf(.%v., M.Inc(100))
4902}
4903pub mod example {
4904        pub mod M {
4905        pub inc(val i32) -> i32 {
4906        return val + 100;
4907        }
4908        }
4909}
4910
4911--------------------------------------
4912//Use the module in another file
4913use example::M;
4914
4915
4916
4917fn main() {
4918        println!(.{}., M::inc(100));
4919}
4920\end{cfa}
4921
4922
4923\subsubsection{Parallel Tasks}
4924
4925\begin{flushleft}
4926\begin{tabular}{@{}l|l|l|l@{}}
4927\multicolumn{1}{c|}{\textbf{\CFA}}      & \multicolumn{1}{c|}{\textbf{\CC}} & \multicolumn{1}{c|}{\textbf{Go}} & \multicolumn{1}{c}{\textbf{Rust}}      \\
4928\hline
4929\begin{cfa}
4930task Nonzero {
4931        int *data;
4932        int start;
4933        int end;
4934        int* res;
4935};
4936
4937void ?{}(Nonzero &a, int d[], int s,
4938        int e, int* subres) {
4939        // constructor
4940        a.data = d;
4941        a.start = s;
4942        a.end = e;
4943        a.res = subres;
4944}
4945
4946// implicitly spawn thread here
4947void ?()(NonzeroCounter &a) {
4948        int i;
4949        int nonzero = 0;
4950        for (i=start; c<end; ++i) {
4951        if(a.data[i]!=0){ nonzero++;}
4952        }
4953        *a.res = nonzero;
4954}
4955
4956int main() {
4957        int sz = ...
4958        int data[sz] = ...;
4959        int r1 = 0, r2=0;
4960        int res;
4961        { // create a scope for Nonzero
4962        Nonzero n1{data, 0, sz/2, &n1};
4963        Nonzero n2{data, sz/2, sz, &n2};
4964        n1();//spawn
4965        n2();//spawn
4966        }
4967        res = r1+r2;
4968        return res;
4969}
4970\end{cfa}
4971&
4972\begin{cfa}
4973#include <thread>
4974#include <mutex>
4975
4976std::mutex m;
4977
4978
4979
4980
4981
4982
4983
4984
4985
4986
4987
4988
4989void task(const vector<int>&v,
4990        int* res, size_t s,
4991        size_t e) {
4992        int non_zero = 0;
4993        for(size_t i = s; i < e; ++i){
4994        if(v[i]!=0) { non_zero++;}
4995        }
4996        std::unique_lock<mutex> lck {m};
4997        *res += non_zero;
4998}
4999
5000int main() {
5001        vector<int> data = ...; //data
5002        int res = 0;
5003        std::thread t1 {task, ref(data),
5004        &res, 0,
5005        data.size()/2};
5006        std::thread t2 {task, ref(data),
5007        &res, data.size()/2,
5008        data.size()};
5009        t1.join();
5010        t2.join();
5011        return res;
5012}
5013\end{cfa}
5014&
5015\begin{cfa}
5016package main
5017
5018import "fmt"
5019
5020func nonzero(data []int, c chan int) {
5021        nz := 0
5022        for _, v:=range data {
5023        if(v!=0) { nz := nz+1 }
5024        }
5025        c <- nz
5026}
5027
5028func main() {
5029        sz := ...
5030        data := make([]int, sz)
5031        ... // data init
5032        go nonzero(data[:len(data)/2], c)
5033        go nonzero(data[len(data)/2:], c)
5034        n1, n2 := <-c, <-c
5035        res := n1 + n2
5036        fmt.Println(res)
5037}
5038\end{cfa}
5039&
5040\begin{cfa}
5041use std::thread;
5042use std::sync:mpsc::channel;
5043
5044fn main() {
5045        let sz = ...;
5046        let mut data:Vec<i32> =
5047        Vec::with_capacity(sz as usize);
5048        ... //init data
5049        let (tx, rx) = channel();
5050        for i in 0..1 {
5051        let tx = tx.clone();
5052        let data = data.clone()
5053        thread::spawn(move|| {
5054        let mut nz := 0;
5055        let mut s = 0;
5056        let mut e = sz / 2;
5057        if i == 1 {
5058        s = sz/2;
5059        e = data.len();
5060        }
5061        for i in s..(e - 1) {
5062        if data[i] != 0 (
5063        nz = nz + 1
5064        }
5065        }
5066        tx.send(nz).unwrap();
5067        });
5068        }
5069        let res = rx.recv().unwrap() +
5070        rx.recv().unwrap();
5071        println!(.{}., res);
5072}
5073\end{cfa}
5074\end{tabular}
5075\end{flushleft}
5076
5077}% local change to lstlising to reduce font size
5078
5079
5080\subsection{Summary of Language Comparison}
5081\end{comment}
5082
5083
5084\subsection[C++]{\CC}
5085
5086\Index*[C++]{\CC{}} is a general-purpose programming language.
5087It has imperative, object-oriented and generic programming features, while also providing facilities for low-level memory manipulation. (Wikipedia)
5088
5089The primary focus of \CC seems to be adding object-oriented programming to C, and this is the primary difference between \CC and Do.
5090\CC uses classes to encapsulate data and the functions that operate on that data, and to hide the internal representation of the data.
5091\CFA uses modules instead to perform these same tasks.
5092Classes in \CC also enable inheritance among types.
5093Instead of inheritance, \CFA embraces composition and interfaces to achieve the same goals with more flexibility.
5094There 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, \Index*{Go} at Google: Language Design in the Service of Software Engineering , 2012).
5095
5096Overloading 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.
5097References and exceptions in \CFA are heavily based on the same features from \CC.
5098The mechanism for interoperating with C code in \CFA is also borrowed from \CC.
5099
5100Both \CFA and \CC provide generics, and the syntax is quite similar.
5101The 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.
5102This means that a generic function can be defined in a compiled library, and still be used as expected from source.
5103
5104
5105\subsection{Go}
5106
5107\Index*{Go}, also commonly referred to as golang, is a programming language developed at Google in 2007 [.].
5108It is a statically typed language with syntax loosely derived from that of C, adding garbage collection, type
5109safety, some structural typing capabilities, additional built-in types such as variable-length arrays and key-value maps, and a large standard library. (Wikipedia)
5110
5111Go and \CFA differ significantly in syntax and implementation, but the underlying core concepts of the two languages are aligned.
5112Both Go and \CFA use composition and interfaces as opposed to inheritance to enable encapsulation and abstraction.
5113Both languages (along with their tooling ecosystem) provide a simple packaging mechanism for building units of code for easy sharing and reuse.
5114Both 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.
5115
5116Go has a significant runtime which handles the scheduling of its light weight threads, and performs garbage collection, among other tasks.
5117\CFA uses a cooperative scheduling algorithm for its tasks, and uses automatic reference counting to enable advanced memory management without garbage collection.
5118This results in Go requiring significant overhead to interface with C libraries while \CFA has no overhead.
5119
5120
5121\subsection{Rust}
5122
5123\Index*{Rust} is a general-purpose, multi-paradigm, compiled programming language developed by Mozilla Research.
5124It is designed to be a "safe, concurrent, practical language", supporting pure-functional, concurrent-actor[dubious . discuss][citation needed], imperative-procedural, and object-oriented styles.
5125
5126The primary focus of Rust is in safety, especially in concurrent programs.
5127To enforce a high level of safety, Rust has added ownership as a core feature of the language to guarantee memory safety.
5128This safety comes at the cost of a difficult learning curve, a change in the thought model of the program, and often some runtime overhead.
5129
5130Aside from those key differences, Rust and \CFA also have several similarities.
5131Both languages support no overhead interoperability with C and have minimal runtimes.
5132Both languages support inheritance and polymorphism through the use of interfaces (traits).
5133
5134
5135\subsection{D}
5136
5137The \Index*{D} programming language is an object-oriented, imperative, multi-paradigm system programming
5138language created by Walter Bright of Digital Mars and released in 2001. [.]
5139Though 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 \Index*{Java}, \Index*{Python}, Ruby, C\#, and Eiffel.
5140
5141D and \CFA both start with C and add productivity features.
5142The obvious difference is that D uses classes and inheritance while \CFA uses composition and interfaces.
5143D is closer to \CFA than \CC since it is limited to single inheritance and also supports interfaces.
5144Like \CC, and unlike \CFA, D uses garbage collection and has compile-time expanded templates.
5145D does not have any built-in concurrency constructs in the
5146language, though it does have a standard library for concurrency which includes the low-level primitives for concurrency.
5147
5148
5149\appendix
5150
5151
5152\section{Syntax Ambiguities}
5153
5154C has a number of syntax ambiguities, which are resolved by taking the longest sequence of overlapping characters that constitute a token.
5155For example, the program fragment ©x+++++y© is parsed as \lstinline[showspaces=true]@x ++ ++ + y@ because operator tokens ©++© and ©+© overlap.
5156Unfortunately, the longest sequence violates a constraint on increment operators, even though the parse \lstinline[showspaces=true]@x ++ + ++ y@ might yield a correct expression.
5157Hence, C programmers are aware that spaces have to added to disambiguate certain syntactic cases.
5158
5159In \CFA, there are ambiguous cases with dereference and operator identifiers, \eg ©int *?*?()©, where the string ©*?*?© can be interpreted as:
5160\begin{cfa}
5161*?§\color{red}\textvisiblespace§*?              §\C{// dereference operator, dereference operator}§
5162\color{red}\textvisiblespace§?*?              §\C{// dereference, multiplication operator}§
5163\end{cfa}
5164By default, the first interpretation is selected, which does not yield a meaningful parse.
5165Therefore, \CFA does a lexical look-ahead for the second case, and backtracks to return the leading unary operator and reparses the trailing operator identifier.
5166Otherwise a space is needed between the unary operator and operator identifier to disambiguate this common case.
5167
5168A similar issue occurs with the dereference, ©*?(...)©, and routine-call, ©?()(...)© identifiers.
5169The ambiguity occurs when the deference operator has no parameters:
5170\begin{cfa}
5171*?()§\color{red}\textvisiblespace...§ ;
5172*?()§\color{red}\textvisiblespace...§(...) ;
5173\end{cfa}
5174requiring arbitrary whitespace look-ahead for the routine-call parameter-list to disambiguate.
5175However, the dereference operator \emph{must} have a parameter/argument to dereference ©*?(...)©.
5176Hence, always interpreting the string ©*?()© as \lstinline[showspaces=true]@* ?()@ does not preclude any meaningful program.
5177
5178The remaining cases are with the increment/decrement operators and conditional expression, \eg:
5179\begin{cfa}
5180i++?§\color{red}\textvisiblespace...§(...);
5181i?++§\color{red}\textvisiblespace...§(...);
5182\end{cfa}
5183requiring arbitrary whitespace look-ahead for the operator parameter-list, even though that interpretation is an incorrect expression (juxtaposed identifiers).
5184Therefore, it is necessary to disambiguate these cases with a space:
5185\begin{cfa}
5186i++§\color{red}\textvisiblespace§? i : 0;
5187i?§\color{red}\textvisiblespace§++i : 0;
5188\end{cfa}
5189
5190
5191\section{\protect\CFA Keywords}
5192\label{s:CFAKeywords}
5193
5194\begin{quote2}
5195\begin{tabular}{llll}
5196\begin{tabular}{@{}l@{}}
5197©_AT©                   \\
5198©catch©                 \\
5199©catchResume©   \\
5200©choose©                \\
5201©coroutine©             \\
5202©disable©               \\
5203\end{tabular}
5204&
5205\begin{tabular}{@{}l@{}}
5206©dtype©                 \\
5207©enable©                \\
5208©fallthrough©   \\
5209©fallthru©              \\
5210©finally©               \\
5211©forall©                \\
5212\end{tabular}
5213&
5214\begin{tabular}{@{}l@{}}
5215©ftype©                 \\
5216©lvalue©                \\
5217©monitor©               \\
5218©mutex©                 \\
5219©one_t©                 \\
5220©otype©                 \\
5221\end{tabular}
5222&
5223\begin{tabular}{@{}l@{}}
5224©throw©                 \\
5225©throwResume©   \\
5226©trait©                 \\
5227©try©                   \\
5228©ttype©                 \\
5229©zero_t©                \\
5230\end{tabular}
5231\end{tabular}
5232\end{quote2}
5233
5234
5235\section{Incompatible}
5236
5237The following incompatibles exist between \CFA and C, and are similar to Annex C for \CC~\cite{C++14}.
5238
5239
5240\begin{enumerate}
5241\item
5242\begin{description}
5243\item[Change:] add new keywords \\
5244New keywords are added to \CFA (see~\VRef{s:CFAKeywords}).
5245\item[Rationale:] keywords added to implement new semantics of \CFA.
5246\item[Effect on original feature:] change to semantics of well-defined feature. \\
5247Any \Celeven programs using these keywords as identifiers are invalid \CFA programs.
5248\item[Difficulty of converting:] keyword clashes are accommodated by syntactic transformations using the \CFA backquote escape-mechanism (see~\VRef{s:BackquoteIdentifiers}).
5249\item[How widely used:] clashes among new \CFA keywords and existing identifiers are rare.
5250\end{description}
5251
5252\item
5253\begin{description}
5254\item[Change:] drop K\&R C declarations \\
5255K\&R declarations allow an implicit base-type of ©int©, if no type is specified, plus an alternate syntax for declaring parameters.
5256\eg:
5257\begin{cfa}
5258x;                                                              §\C{// int x}§
5259*y;                                                             §\C{// int *y}§
5260f( p1, p2 );                                    §\C{// int f( int p1, int p2 );}§
5261g( p1, p2 ) int p1, p2;                 §\C{// int g( int p1, int p2 );}§
5262\end{cfa}
5263\CFA supports K\&R routine definitions:
5264\begin{cfa}
5265f( a, b, c )                                    §\C{// default int return}§
5266        int a, b; char c                        §\C{// K\&R parameter declarations}§
5267{
5268        ...
5269}
5270\end{cfa}
5271\item[Rationale:] dropped from \Celeven standard.\footnote{
5272At 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}}
5273\item[Effect on original feature:] original feature is deprecated. \\
5274Any old C programs using these K\&R declarations are invalid \CFA programs.
5275\item[Difficulty of converting:] trivial to convert to \CFA.
5276\item[How widely used:] existing usages are rare.
5277\end{description}
5278
5279\item
5280\begin{description}
5281\item[Change:] type of character literal ©int© to ©char© to allow more intuitive overloading:
5282\begin{cfa}
5283int rtn( int i );
5284int rtn( char c );
5285rtn( 'x' );                                             §\C{// programmer expects 2nd rtn to be called}§
5286\end{cfa}
5287\item[Rationale:] it is more intuitive for the call to ©rtn© to match the second version of definition of ©rtn© rather than the first.
5288In particular, output of ©char© variable now print a character rather than the decimal ASCII value of the character.
5289\begin{cfa}
5290sout | 'x' | " " | (int)'x' | endl;
5291x 120
5292\end{cfa}
5293Having to cast ©'x'© to ©char© is non-intuitive.
5294\item[Effect on original feature:] change to semantics of well-defined feature that depend on:
5295\begin{cfa}
5296sizeof( 'x' ) == sizeof( int )
5297\end{cfa}
5298no long work the same in \CFA programs.
5299\item[Difficulty of converting:] simple
5300\item[How widely used:] programs that depend upon ©sizeof( 'x' )© are rare and can be changed to ©sizeof(char)©.
5301\end{description}
5302
5303\item
5304\begin{description}
5305\item[Change:] make string literals ©const©:
5306\begin{cfa}
5307char * p = "abc";                               §\C{// valid in C, deprecated in \CFA}§
5308char * q = expr ? "abc" : "de"; §\C{// valid in C, invalid in \CFA}§
5309\end{cfa}
5310The type of a string literal is changed from ©[] char© to ©const [] char©.
5311Similarly, the type of a wide string literal is changed from ©[] wchar_t© to ©const [] wchar_t©.
5312\item[Rationale:] This change is a safety issue:
5313\begin{cfa}
5314char * p = "abc";
5315p[0] = 'w';                                             §\C{// segment fault or change constant literal}§
5316\end{cfa}
5317The same problem occurs when passing a string literal to a routine that changes its argument.
5318\item[Effect on original feature:] change to semantics of well-defined feature.
5319\item[Difficulty of converting:] simple syntactic transformation, because string literals can be converted to ©char *©.
5320\item[How widely used:] programs that have a legitimate reason to treat string literals as pointers to potentially modifiable memory are rare.
5321\end{description}
5322
5323\item
5324\begin{description}
5325\item[Change:] remove \newterm{tentative definitions}, which only occurs at file scope:
5326\begin{cfa}
5327int i;                                                  §\C{// forward definition}§
5328int *j = ®&i®;                                  §\C{// forward reference, valid in C, invalid in \CFA}§
5329int i = 0;                                              §\C{// definition}§
5330\end{cfa}
5331is valid in C, and invalid in \CFA because duplicate overloaded object definitions at the same scope level are disallowed.
5332This change makes it impossible to define mutually referential file-local static objects, if initializers are restricted to the syntactic forms of C. For example,
5333\begin{cfa}
5334struct X { int i; struct X *next; };
5335static struct X a;                              §\C{// forward definition}§
5336static struct X b = { 0, ®&};        §\C{// forward reference, valid in C, invalid in \CFA}§
5337static struct X a = { 1, &b };  §\C{// definition}§
5338\end{cfa}
5339\item[Rationale:] avoids having different initialization rules for builtin types and user-defined types.
5340\item[Effect on original feature:] change to semantics of well-defined feature.
5341\item[Difficulty of converting:] the initializer for one of a set of mutually-referential file-local static objects must invoke a routine call to achieve the initialization.
5342\item[How widely used:] seldom
5343\end{description}
5344
5345\item
5346\begin{description}
5347\item[Change:] have ©struct© introduce a scope for nested types:
5348\begin{cfa}
5349enum ®Colour® { R, G, B, Y, C, M };
5350struct Person {
5351        enum ®Colour® { R, G, B };      §\C{// nested type}§
5352        struct Face {                           §\C{// nested type}§
5353                ®Colour® Eyes, Hair;    §\C{// type defined outside (1 level)}§
5354        };
5355        ®.Colour® shirt;                        §\C{// type defined outside (top level)}§
5356        ®Colour® pants;                         §\C{// type defined same level}§
5357        Face looks[10];                         §\C{// type defined same level}§
5358};
5359®Colour® c = R;                                 §\C{// type/enum defined same level}§
5360Person®.Colour® pc = Person®.®R;        §\C{// type/enum defined inside}§
5361Person®.®Face pretty;                   §\C{// type defined inside}§
5362\end{cfa}
5363In C, the name of the nested types belongs to the same scope as the name of the outermost enclosing structure, \ie the nested types are hoisted to the scope of the outer-most type, which is not useful and confusing.
5364\CFA is C \emph{incompatible} on this issue, and provides semantics similar to \Index*[C++]{\CC{}}.
5365Nested types are not hoisted and can be referenced using the field selection operator ``©.©'', unlike the \CC scope-resolution operator ``©::©''.
5366\item[Rationale:] ©struct© scope is crucial to \CFA as an information structuring and hiding mechanism.
5367\item[Effect on original feature:] change to semantics of well-defined feature.
5368\item[Difficulty of converting:] Semantic transformation.
5369\item[How widely used:] C programs rarely have nest types because they are equivalent to the hoisted version.
5370\end{description}
5371
5372\item
5373\begin{description}
5374\item[Change:] In C++, the name of a nested class is local to its enclosing class.
5375\item[Rationale:] C++ classes have member functions which require that classes establish scopes.
5376\item[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:
5377\begin{cfa}
5378struct Y;                                               §\C{// struct Y and struct X are at the same scope}§
5379struct X {
5380        struct Y { /* ... */ } y;
5381};
5382\end{cfa}
5383All 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.
5384Note: this is a consequence of the difference in scope rules, which is documented in 3.3.
5385\item[How widely used:] Seldom.
5386\end{description}
5387
5388\item
5389\begin{description}
5390\item[Change:] comma expression is disallowed as subscript
5391\item[Rationale:] safety issue to prevent subscripting error for multidimensional arrays: ©x[i,j]© instead of ©x[i][j]©, and this syntactic form then taken by \CFA for new style arrays.
5392\item[Effect on original feature:] change to semantics of well-defined feature.
5393\item[Difficulty of converting:] semantic transformation of ©x[i,j]© to ©x[(i,j)]©
5394\item[How widely used:] seldom.
5395\end{description}
5396\end{enumerate}
5397
5398
5399\section{Standard Headers}
5400\label{s:StandardHeaders}
5401
5402\Celeven prescribes the following standard header-files~\cite[\S~7.1.2]{C11} and \CFA adds to this list:
5403\begin{quote2}
5404\lstset{deletekeywords={float}}
5405\begin{tabular}{@{}llll|l@{}}
5406\multicolumn{4}{c|}{C11} & \multicolumn{1}{c}{\CFA}             \\
5407\hline
5408\begin{tabular}{@{}l@{}}
5409\Indexc{assert.h}               \\
5410\Indexc{complex.h}              \\
5411\Indexc{ctype.h}                \\
5412\Indexc{errno.h}                \\
5413\Indexc{fenv.h}                 \\
5414\Indexc{float.h}                \\
5415\Indexc{inttypes.h}             \\
5416\Indexc{iso646.h}               \\
5417\end{tabular}
5418&
5419\begin{tabular}{@{}l@{}}
5420\Indexc{limits.h}               \\
5421\Indexc{locale.h}               \\
5422\Indexc{math.h}                 \\
5423\Indexc{setjmp.h}               \\
5424\Indexc{signal.h}               \\
5425\Indexc{stdalign.h}             \\
5426\Indexc{stdarg.h}               \\
5427\Indexc{stdatomic.h}    \\
5428\end{tabular}
5429&
5430\begin{tabular}{@{}l@{}}
5431\Indexc{stdbool.h}              \\
5432\Indexc{stddef.h}               \\
5433\Indexc{stdint.h}               \\
5434\Indexc{stdio.h}                \\
5435\Indexc{stdlib.h}               \\
5436\Indexc{stdnoreturn.h}  \\
5437\Indexc{string.h}               \\
5438\Indexc{tgmath.h}               \\
5439\end{tabular}
5440&
5441\begin{tabular}{@{}l@{}}
5442\Indexc{threads.h}              \\
5443\Indexc{time.h}                 \\
5444\Indexc{uchar.h}                \\
5445\Indexc{wchar.h}                \\
5446\Indexc{wctype.h}               \\
5447                                                \\
5448                                                \\
5449                                                \\
5450\end{tabular}
5451&
5452\begin{tabular}{@{}l@{}}
5453\Indexc{unistd.h}               \\
5454\Indexc{gmp.h}                  \\
5455                                                \\
5456                                                \\
5457                                                \\
5458                                                \\
5459                                                \\
5460                                                \\
5461\end{tabular}
5462\end{tabular}
5463\end{quote2}
5464For the prescribed head-files, \CFA uses header interposition to wraps these includes in an ©extern "C"©;
5465hence, names in these include files are not mangled\index{mangling!name} (see~\VRef{s:Interoperability}).
5466All other C header files must be explicitly wrapped in ©extern "C"© to prevent name mangling.
5467For \Index*[C++]{\CC{}}, the name-mangling issue is handled implicitly because most C header-files are augmented with checks for preprocessor variable ©__cplusplus©, which adds appropriate ©extern "C"© qualifiers.
5468
5469
5470\section{Standard Library}
5471\label{s:StandardLibrary}
5472
5473The \CFA standard-library wraps explicitly-polymorphic C routines into implicitly-polymorphic versions.
5474
5475
5476\subsection{Storage Management}
5477
5478The storage-management routines extend their C equivalents by overloading, alternate names, providing shallow type-safety, and removing the need to specify the allocation size for non-array types.
5479
5480Storage management provides the following capabilities:
5481\begin{description}
5482\item[fill]
5483after allocation the storage is filled with a specified character.
5484\item[resize]
5485an existing allocation is decreased or increased in size.
5486In either case, new storage may or may not be allocated and, if there is a new allocation, as much data from the existing allocation is copied.
5487For an increase in storage size, new storage after the copied data may be filled.
5488\item[alignment]
5489an allocation starts on a specified memory boundary, e.g., an address multiple of 64 or 128 for cache-line purposes.
5490\item[array]
5491the allocation size is scaled to the specified number of array elements.
5492An array may be filled, resized, or aligned.
5493\end{description}
5494The table shows allocation routines supporting different combinations of storage-management capabilities:
5495\begin{center}
5496\begin{tabular}{@{}lr|l|l|l|l@{}}
5497                &                                       & \multicolumn{1}{c|}{fill}     & resize        & alignment     & array \\
5498\hline
5499C               & ©malloc©                      & no                    & no            & no            & no    \\
5500                & ©calloc©                      & yes (0 only)  & no            & no            & yes   \\
5501                & ©realloc©                     & no/copy               & yes           & no            & no    \\
5502                & ©memalign©            & no                    & no            & yes           & no    \\
5503                & ©posix_memalign©      & no                    & no            & yes           & no    \\
5504C11             & ©aligned_alloc©       & no                    & no            & yes           & no    \\
5505\CFA    & ©alloc©                       & no/copy/yes   & no/yes        & no            & yes   \\
5506                & ©align_alloc©         & no/yes                & no            & yes           & yes   \\
5507\end{tabular}
5508\end{center}
5509It is impossible to resize with alignment because the underlying ©realloc© allocates storage if more space is needed, and it does not honour alignment from the original allocation.
5510
5511\leavevmode
5512\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5513// C unsafe allocation
5514extern "C" {
5515void * mallac( size_t size );§\indexc{memset}§
5516void * calloc( size_t dim, size_t size );§\indexc{calloc}§
5517void * realloc( void * ptr, size_t size );§\indexc{realloc}§
5518void * memalign( size_t align, size_t size );§\indexc{memalign}§
5519int posix_memalign( void ** ptr, size_t align, size_t size );§\indexc{posix_memalign}§
5520}
5521
5522// §\CFA§ safe equivalents, i.e., implicit size specification
5523forall( dtype T | sized(T) ) T * malloc( void );
5524forall( dtype T | sized(T) ) T * calloc( size_t dim );
5525forall( dtype T | sized(T) ) T * realloc( T * ptr, size_t size );
5526forall( dtype T | sized(T) ) T * memalign( size_t align );
5527forall( dtype T | sized(T) ) T * aligned_alloc( size_t align );
5528forall( dtype T | sized(T) ) int posix_memalign( T ** ptr, size_t align );
5529
5530// §\CFA§ safe general allocation, fill, resize, array
5531forall( dtype T | sized(T) ) T * alloc( void );§\indexc{alloc}§
5532forall( dtype T | sized(T) ) T * alloc( char fill );
5533forall( dtype T | sized(T) ) T * alloc( size_t dim );
5534forall( dtype T | sized(T) ) T * alloc( size_t dim, char fill );
5535forall( dtype T | sized(T) ) T * alloc( T ptr[], size_t dim );
5536forall( dtype T | sized(T) ) T * alloc( T ptr[], size_t dim, char fill );
5537
5538// §\CFA§ safe general allocation, align, fill, array
5539forall( dtype T | sized(T) ) T * align_alloc( size_t align );
5540forall( dtype T | sized(T) ) T * align_alloc( size_t align, char fill );
5541forall( dtype T | sized(T) ) T * align_alloc( size_t align, size_t dim );
5542forall( dtype T | sized(T) ) T * align_alloc( size_t align, size_t dim, char fill );
5543
5544// C unsafe initialization/copy
5545extern "C" {
5546void * memset( void * dest, int c, size_t size );
5547void * memcpy( void * dest, const void * src, size_t size );
5548}
5549
5550// §\CFA§ safe initialization/copy, i.e., implicit size specification
5551forall( dtype T | sized(T) ) T * memset( T * dest, char c );§\indexc{memset}§
5552forall( dtype T | sized(T) ) T * memcpy( T * dest, const T * src );§\indexc{memcpy}§
5553
5554// §\CFA§ safe initialization/copy array
5555forall( dtype T | sized(T) ) T * memset( T dest[], size_t dim, char c );
5556forall( dtype T | sized(T) ) T * memcpy( T dest[], const T src[], size_t dim );
5557
5558// §\CFA§ allocation/deallocation and constructor/destructor
5559forall( dtype T | sized(T), ttype Params | { void ?{}( T *, Params ); } ) T * new( Params p );§\indexc{new}§
5560forall( dtype T | { void ^?{}( T * ); } ) void delete( T * ptr );§\indexc{delete}§
5561forall( dtype T, ttype Params | { void ^?{}( T * ); void delete( Params ); } )
5562  void delete( T * ptr, Params rest );
5563
5564// §\CFA§ allocation/deallocation and constructor/destructor, array
5565forall( dtype T | sized(T), ttype Params | { void ?{}( T *, Params ); } ) T * anew( size_t dim, Params p );§\indexc{anew}§
5566forall( dtype T | sized(T) | { void ^?{}( T * ); } ) void adelete( size_t dim, T arr[] );§\indexc{adelete}§
5567forall( dtype T | sized(T) | { void ^?{}( T * ); }, ttype Params | { void adelete( Params ); } )
5568  void adelete( size_t dim, T arr[], Params rest );
5569\end{cfa}
5570
5571
5572\subsection{Conversion}
5573
5574\leavevmode
5575\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5576int ato( const char * ptr );§\indexc{ato}§
5577unsigned int ato( const char * ptr );
5578long int ato( const char * ptr );
5579unsigned long int ato( const char * ptr );
5580long long int ato( const char * ptr );
5581unsigned long long int ato( const char * ptr );
5582float ato( const char * ptr );
5583double ato( const char * ptr );
5584long double ato( const char * ptr );
5585float _Complex ato( const char * ptr );
5586double _Complex ato( const char * ptr );
5587long double _Complex ato( const char * ptr );
5588
5589int strto( const char * sptr, char ** eptr, int base );
5590unsigned int strto( const char * sptr, char ** eptr, int base );
5591long int strto( const char * sptr, char ** eptr, int base );
5592unsigned long int strto( const char * sptr, char ** eptr, int base );
5593long long int strto( const char * sptr, char ** eptr, int base );
5594unsigned long long int strto( const char * sptr, char ** eptr, int base );
5595float strto( const char * sptr, char ** eptr );
5596double strto( const char * sptr, char ** eptr );
5597long double strto( const char * sptr, char ** eptr );
5598float _Complex strto( const char * sptr, char ** eptr );
5599double _Complex strto( const char * sptr, char ** eptr );
5600long double _Complex strto( const char * sptr, char ** eptr );
5601\end{cfa}
5602
5603
5604\subsection{Search / Sort}
5605
5606\leavevmode
5607\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5608forall( otype T | { int ?<?( T, T ); } )        §\C{// location}§
5609T * bsearch( T key, const T * arr, size_t dim );§\indexc{bsearch}§
5610
5611forall( otype T | { int ?<?( T, T ); } )        §\C{// position}§
5612unsigned int bsearch( T key, const T * arr, size_t dim );
5613
5614forall( otype T | { int ?<?( T, T ); } )
5615void qsort( const T * arr, size_t dim );§\indexc{qsort}§
5616\end{cfa}
5617
5618
5619\subsection{Absolute Value}
5620
5621\leavevmode
5622\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5623unsigned char abs( signed char );§\indexc{abs}§
5624int abs( int );
5625unsigned long int abs( long int );
5626unsigned long long int abs( long long int );
5627float abs( float );
5628double abs( double );
5629long double abs( long double );
5630float abs( float _Complex );
5631double abs( double _Complex );
5632long double abs( long double _Complex );
5633forall( otype T | { void ?{}( T *, zero_t ); int ?<?( T, T ); T -?( T ); } )
5634T abs( T );
5635\end{cfa}
5636
5637
5638\subsection{Random Numbers}
5639
5640\leavevmode
5641\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5642void rand48seed( long int s );§\indexc{rand48seed}§
5643char rand48();§\indexc{rand48}§
5644int rand48();
5645unsigned int rand48();
5646long int rand48();
5647unsigned long int rand48();
5648float rand48();
5649double rand48();
5650float _Complex rand48();
5651double _Complex rand48();
5652long double _Complex rand48();
5653\end{cfa}
5654
5655
5656\subsection{Algorithms}
5657
5658\leavevmode
5659\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5660forall( otype T | { int ?<?( T, T ); } ) T min( T t1, T t2 );§\indexc{min}§
5661forall( otype T | { int ?>?( T, T ); } ) T max( T t1, T t2 );§\indexc{max}§
5662forall( otype T | { T min( T, T ); T max( T, T ); } ) T clamp( T value, T min_val, T max_val );§\indexc{clamp}§
5663forall( otype T ) void swap( T * t1, T * t2 );§\indexc{swap}§
5664\end{cfa}
5665
5666
5667\section{Math Library}
5668\label{s:Math Library}
5669
5670The \CFA math-library wraps explicitly-polymorphic C math-routines into implicitly-polymorphic versions.
5671
5672
5673\subsection{General}
5674
5675\leavevmode
5676\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5677float ?%?( float, float );§\indexc{fmod}§
5678float fmod( float, float );
5679double ?%?( double, double );
5680double fmod( double, double );
5681long double ?%?( long double, long double );
5682long double fmod( long double, long double );
5683
5684float remainder( float, float );§\indexc{remainder}§
5685double remainder( double, double );
5686long double remainder( long double, long double );
5687
5688[ int, float ] remquo( float, float );§\indexc{remquo}§
5689float remquo( float, float, int * );
5690[ int, double ] remquo( double, double );
5691double remquo( double, double, int * );
5692[ int, long double ] remquo( long double, long double );
5693long double remquo( long double, long double, int * );
5694
5695[ int, float ] div( float, float );                                             // alternative name for remquo
5696float div( float, float, int * );§\indexc{div}§
5697[ int, double ] div( double, double );
5698double div( double, double, int * );
5699[ int, long double ] div( long double, long double );
5700long double div( long double, long double, int * );
5701
5702float fma( float, float, float );§\indexc{fma}§
5703double fma( double, double, double );
5704long double fma( long double, long double, long double );
5705
5706float fdim( float, float );§\indexc{fdim}§
5707double fdim( double, double );
5708long double fdim( long double, long double );
5709
5710float nan( const char * );§\indexc{nan}§
5711double nan( const char * );
5712long double nan( const char * );
5713\end{cfa}
5714
5715
5716\subsection{Exponential}
5717
5718\leavevmode
5719\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5720float exp( float );§\indexc{exp}§
5721double exp( double );
5722long double exp( long double );
5723float _Complex exp( float _Complex );
5724double _Complex exp( double _Complex );
5725long double _Complex exp( long double _Complex );
5726
5727float exp2( float );§\indexc{exp2}§
5728double exp2( double );
5729long double exp2( long double );
5730float _Complex exp2( float _Complex );
5731double _Complex exp2( double _Complex );
5732long double _Complex exp2( long double _Complex );
5733
5734float expm1( float );§\indexc{expm1}§
5735double expm1( double );
5736long double expm1( long double );
5737
5738float log( float );§\indexc{log}§
5739double log( double );
5740long double log( long double );
5741float _Complex log( float _Complex );
5742double _Complex log( double _Complex );
5743long double _Complex log( long double _Complex );
5744
5745float log2( float );§\indexc{log2}§
5746double log2( double );
5747long double log2( long double );
5748float _Complex log2( float _Complex );
5749double _Complex log2( double _Complex );
5750long double _Complex log2( long double _Complex );
5751
5752float log10( float );§\indexc{log10}§
5753double log10( double );
5754long double log10( long double );
5755float _Complex log10( float _Complex );
5756double _Complex log10( double _Complex );
5757long double _Complex log10( long double _Complex );
5758
5759float log1p( float );§\indexc{log1p}§
5760double log1p( double );
5761long double log1p( long double );
5762
5763int ilogb( float );§\indexc{ilogb}§
5764int ilogb( double );
5765int ilogb( long double );
5766
5767float logb( float );§\indexc{logb}§
5768double logb( double );
5769long double logb( long double );
5770\end{cfa}
5771
5772
5773\subsection{Power}
5774
5775\leavevmode
5776\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5777float sqrt( float );§\indexc{sqrt}§
5778double sqrt( double );
5779long double sqrt( long double );
5780float _Complex sqrt( float _Complex );
5781double _Complex sqrt( double _Complex );
5782long double _Complex sqrt( long double _Complex );
5783
5784float cbrt( float );§\indexc{cbrt}§
5785double cbrt( double );
5786long double cbrt( long double );
5787
5788float hypot( float, float );§\indexc{hypot}§
5789double hypot( double, double );
5790long double hypot( long double, long double );
5791
5792float pow( float, float );§\indexc{pow}§
5793double pow( double, double );
5794long double pow( long double, long double );
5795float _Complex pow( float _Complex, float _Complex );
5796double _Complex pow( double _Complex, double _Complex );
5797long double _Complex pow( long double _Complex, long double _Complex );
5798\end{cfa}
5799
5800
5801\subsection{Trigonometric}
5802
5803\leavevmode
5804\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5805float sin( float );§\indexc{sin}§
5806double sin( double );
5807long double sin( long double );
5808float _Complex sin( float _Complex );
5809double _Complex sin( double _Complex );
5810long double _Complex sin( long double _Complex );
5811
5812float cos( float );§\indexc{cos}§
5813double cos( double );
5814long double cos( long double );
5815float _Complex cos( float _Complex );
5816double _Complex cos( double _Complex );
5817long double _Complex cos( long double _Complex );
5818
5819float tan( float );§\indexc{tan}§
5820double tan( double );
5821long double tan( long double );
5822float _Complex tan( float _Complex );
5823double _Complex tan( double _Complex );
5824long double _Complex tan( long double _Complex );
5825
5826float asin( float );§\indexc{asin}§
5827double asin( double );
5828long double asin( long double );
5829float _Complex asin( float _Complex );
5830double _Complex asin( double _Complex );
5831long double _Complex asin( long double _Complex );
5832
5833float acos( float );§\indexc{acos}§
5834double acos( double );
5835long double acos( long double );
5836float _Complex acos( float _Complex );
5837double _Complex acos( double _Complex );
5838long double _Complex acos( long double _Complex );
5839
5840float atan( float );§\indexc{atan}§
5841double atan( double );
5842long double atan( long double );
5843float _Complex atan( float _Complex );
5844double _Complex atan( double _Complex );
5845long double _Complex atan( long double _Complex );
5846
5847float atan2( float, float );§\indexc{atan2}§
5848double atan2( double, double );
5849long double atan2( long double, long double );
5850
5851float atan( float, float );                                                             // alternative name for atan2
5852double atan( double, double );§\indexc{atan}§
5853long double atan( long double, long double );
5854\end{cfa}
5855
5856
5857\subsection{Hyperbolic}
5858
5859\leavevmode
5860\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5861float sinh( float );§\indexc{sinh}§
5862double sinh( double );
5863long double sinh( long double );
5864float _Complex sinh( float _Complex );
5865double _Complex sinh( double _Complex );
5866long double _Complex sinh( long double _Complex );
5867
5868float cosh( float );§\indexc{cosh}§
5869double cosh( double );
5870long double cosh( long double );
5871float _Complex cosh( float _Complex );
5872double _Complex cosh( double _Complex );
5873long double _Complex cosh( long double _Complex );
5874
5875float tanh( float );§\indexc{tanh}§
5876double tanh( double );
5877long double tanh( long double );
5878float _Complex tanh( float _Complex );
5879double _Complex tanh( double _Complex );
5880long double _Complex tanh( long double _Complex );
5881
5882float asinh( float );§\indexc{asinh}§
5883double asinh( double );
5884long double asinh( long double );
5885float _Complex asinh( float _Complex );
5886double _Complex asinh( double _Complex );
5887long double _Complex asinh( long double _Complex );
5888
5889float acosh( float );§\indexc{acosh}§
5890double acosh( double );
5891long double acosh( long double );
5892float _Complex acosh( float _Complex );
5893double _Complex acosh( double _Complex );
5894long double _Complex acosh( long double _Complex );
5895
5896float atanh( float );§\indexc{atanh}§
5897double atanh( double );
5898long double atanh( long double );
5899float _Complex atanh( float _Complex );
5900double _Complex atanh( double _Complex );
5901long double _Complex atanh( long double _Complex );
5902\end{cfa}
5903
5904
5905\subsection{Error / Gamma}
5906
5907\leavevmode
5908\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5909float erf( float );§\indexc{erf}§
5910double erf( double );
5911long double erf( long double );
5912float _Complex erf( float _Complex );
5913double _Complex erf( double _Complex );
5914long double _Complex erf( long double _Complex );
5915
5916float erfc( float );§\indexc{erfc}§
5917double erfc( double );
5918long double erfc( long double );
5919float _Complex erfc( float _Complex );
5920double _Complex erfc( double _Complex );
5921long double _Complex erfc( long double _Complex );
5922
5923float lgamma( float );§\indexc{lgamma}§
5924double lgamma( double );
5925long double lgamma( long double );
5926float lgamma( float, int * );
5927double lgamma( double, int * );
5928long double lgamma( long double, int * );
5929
5930float tgamma( float );§\indexc{tgamma}§
5931double tgamma( double );
5932long double tgamma( long double );
5933\end{cfa}
5934
5935
5936\subsection{Nearest Integer}
5937
5938\leavevmode
5939\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5940float floor( float );§\indexc{floor}§
5941double floor( double );
5942long double floor( long double );
5943
5944float ceil( float );§\indexc{ceil}§
5945double ceil( double );
5946long double ceil( long double );
5947
5948float trunc( float );§\indexc{trunc}§
5949double trunc( double );
5950long double trunc( long double );
5951
5952float rint( float );§\indexc{rint}§
5953long double rint( long double );
5954long int rint( float );
5955long int rint( double );
5956long int rint( long double );
5957long long int rint( float );
5958long long int rint( double );
5959long long int rint( long double );
5960
5961long int lrint( float );§\indexc{lrint}§
5962long int lrint( double );
5963long int lrint( long double );
5964long long int llrint( float );
5965long long int llrint( double );
5966long long int llrint( long double );
5967
5968float nearbyint( float );§\indexc{nearbyint}§
5969double nearbyint( double );
5970long double nearbyint( long double );
5971
5972float round( float );§\indexc{round}§
5973long double round( long double );
5974long int round( float );
5975long int round( double );
5976long int round( long double );
5977long long int round( float );
5978long long int round( double );
5979long long int round( long double );
5980
5981long int lround( float );§\indexc{lround}§
5982long int lround( double );
5983long int lround( long double );
5984long long int llround( float );
5985long long int llround( double );
5986long long int llround( long double );
5987\end{cfa}
5988
5989
5990\subsection{Manipulation}
5991
5992\leavevmode
5993\begin{cfa}[aboveskip=0pt,belowskip=0pt]
5994float copysign( float, float );§\indexc{copysign}§
5995double copysign( double, double );
5996long double copysign( long double, long double );
5997
5998float frexp( float, int * );§\indexc{frexp}§
5999double frexp( double, int * );
6000long double frexp( long double, int * );
6001
6002float ldexp( float, int );§\indexc{ldexp}§
6003double ldexp( double, int );
6004long double ldexp( long double, int );
6005
6006[ float, float ] modf( float );§\indexc{modf}§
6007float modf( float, float * );
6008[ double, double ] modf( double );
6009double modf( double, double * );
6010[ long double, long double ] modf( long double );
6011long double modf( long double, long double * );
6012
6013float nextafter( float, float );§\indexc{nextafter}§
6014double nextafter( double, double );
6015long double nextafter( long double, long double );
6016
6017float nexttoward( float, long double );§\indexc{nexttoward}§
6018double nexttoward( double, long double );
6019long double nexttoward( long double, long double );
6020
6021float scalbn( float, int );§\indexc{scalbn}§
6022double scalbn( double, int );
6023long double scalbn( long double, int );
6024
6025float scalbln( float, long int );§\indexc{scalbln}§
6026double scalbln( double, long int );
6027long double scalbln( long double, long int );
6028\end{cfa}
6029
6030
6031\section{Multi-precision Integers}
6032\label{s:MultiPrecisionIntegers}
6033
6034\CFA has an interface to the GMP \Index{multi-precision} signed-integers~\cite{GMP}, similar to the \CC interface provided by GMP.
6035The \CFA interface wraps GMP routines into operator routines to make programming with multi-precision integers identical to using fixed-sized integers.
6036The \CFA type name for multi-precision signed-integers is \Indexc{Int} and the header file is \Indexc{gmp}.
6037
6038\begin{cfa}
6039void ?{}( Int * this );                                 §\C{// constructor}§
6040void ?{}( Int * this, Int init );
6041void ?{}( Int * this, zero_t );
6042void ?{}( Int * this, one_t );
6043void ?{}( Int * this, signed long int init );
6044void ?{}( Int * this, unsigned long int init );
6045void ?{}( Int * this, const char * val );
6046void ^?{}( Int * this );
6047
6048Int ?=?( Int * lhs, Int rhs );                  §\C{// assignment}§
6049Int ?=?( Int * lhs, long int rhs );
6050Int ?=?( Int * lhs, unsigned long int rhs );
6051Int ?=?( Int * lhs, const char * rhs );
6052
6053char ?=?( char * lhs, Int rhs );
6054short int ?=?( short int * lhs, Int rhs );
6055int ?=?( int * lhs, Int rhs );
6056long int ?=?( long int * lhs, Int rhs );
6057unsigned char ?=?( unsigned char * lhs, Int rhs );
6058unsigned short int ?=?( unsigned short int * lhs, Int rhs );
6059unsigned int ?=?( unsigned int * lhs, Int rhs );
6060unsigned long int ?=?( unsigned long int * lhs, Int rhs );
6061
6062long int narrow( Int val );
6063unsigned long int narrow( Int val );
6064
6065int ?==?( Int oper1, Int oper2 );               §\C{// comparison}§
6066int ?==?( Int oper1, long int oper2 );
6067int ?==?( long int oper2, Int oper1 );
6068int ?==?( Int oper1, unsigned long int oper2 );
6069int ?==?( unsigned long int oper2, Int oper1 );
6070
6071int ?!=?( Int oper1, Int oper2 );
6072int ?!=?( Int oper1, long int oper2 );
6073int ?!=?( long int oper1, Int oper2 );
6074int ?!=?( Int oper1, unsigned long int oper2 );
6075int ?!=?( unsigned long int oper1, Int oper2 );
6076
6077int ?<?( Int oper1, Int oper2 );
6078int ?<?( Int oper1, long int oper2 );
6079int ?<?( long int oper2, Int oper1 );
6080int ?<?( Int oper1, unsigned long int oper2 );
6081int ?<?( unsigned long int oper2, Int oper1 );
6082
6083int ?<=?( Int oper1, Int oper2 );
6084int ?<=?( Int oper1, long int oper2 );
6085int ?<=?( long int oper2, Int oper1 );
6086int ?<=?( Int oper1, unsigned long int oper2 );
6087int ?<=?( unsigned long int oper2, Int oper1 );
6088
6089int ?>?( Int oper1, Int oper2 );
6090int ?>?( Int oper1, long int oper2 );
6091int ?>?( long int oper1, Int oper2 );
6092int ?>?( Int oper1, unsigned long int oper2 );
6093int ?>?( unsigned long int oper1, Int oper2 );
6094
6095int ?>=?( Int oper1, Int oper2 );
6096int ?>=?( Int oper1, long int oper2 );
6097int ?>=?( long int oper1, Int oper2 );
6098int ?>=?( Int oper1, unsigned long int oper2 );
6099int ?>=?( unsigned long int oper1, Int oper2 );
6100
6101Int +?( Int oper );                                             §\C{// arithmetic}§
6102Int -?( Int oper );
6103Int ~?( Int oper );
6104
6105Int ?&?( Int oper1, Int oper2 );
6106Int ?&?( Int oper1, long int oper2 );
6107Int ?&?( long int oper1, Int oper2 );
6108Int ?&?( Int oper1, unsigned long int oper2 );
6109Int ?&?( unsigned long int oper1, Int oper2 );
6110Int ?&=?( Int * lhs, Int rhs );
6111
6112Int ?|?( Int oper1, Int oper2 );
6113Int ?|?( Int oper1, long int oper2 );
6114Int ?|?( long int oper1, Int oper2 );
6115Int ?|?( Int oper1, unsigned long int oper2 );
6116Int ?|?( unsigned long int oper1, Int oper2 );
6117Int ?|=?( Int * lhs, Int rhs );
6118
6119Int ?^?( Int oper1, Int oper2 );
6120Int ?^?( Int oper1, long int oper2 );
6121Int ?^?( long int oper1, Int oper2 );
6122Int ?^?( Int oper1, unsigned long int oper2 );
6123Int ?^?( unsigned long int oper1, Int oper2 );
6124Int ?^=?( Int * lhs, Int rhs );
6125
6126Int ?+?( Int addend1, Int addend2 );
6127Int ?+?( Int addend1, long int addend2 );
6128Int ?+?( long int addend2, Int addend1 );
6129Int ?+?( Int addend1, unsigned long int addend2 );
6130Int ?+?( unsigned long int addend2, Int addend1 );
6131Int ?+=?( Int * lhs, Int rhs );
6132Int ?+=?( Int * lhs, long int rhs );
6133Int ?+=?( Int * lhs, unsigned long int rhs );
6134Int ++?( Int * lhs );
6135Int ?++( Int * lhs );
6136
6137Int ?-?( Int minuend, Int subtrahend );
6138Int ?-?( Int minuend, long int subtrahend );
6139Int ?-?( long int minuend, Int subtrahend );
6140Int ?-?( Int minuend, unsigned long int subtrahend );
6141Int ?-?( unsigned long int minuend, Int subtrahend );
6142Int ?-=?( Int * lhs, Int rhs );
6143Int ?-=?( Int * lhs, long int rhs );
6144Int ?-=?( Int * lhs, unsigned long int rhs );
6145Int --?( Int * lhs );
6146Int ?--( Int * lhs );
6147
6148Int ?*?( Int multiplicator, Int multiplicand );
6149Int ?*?( Int multiplicator, long int multiplicand );
6150Int ?*?( long int multiplicand, Int multiplicator );
6151Int ?*?( Int multiplicator, unsigned long int multiplicand );
6152Int ?*?( unsigned long int multiplicand, Int multiplicator );
6153Int ?*=?( Int * lhs, Int rhs );
6154Int ?*=?( Int * lhs, long int rhs );
6155Int ?*=?( Int * lhs, unsigned long int rhs );
6156
6157Int ?/?( Int dividend, Int divisor );
6158Int ?/?( Int dividend, unsigned long int divisor );
6159Int ?/?( unsigned long int dividend, Int divisor );
6160Int ?/?( Int dividend, long int divisor );
6161Int ?/?( long int dividend, Int divisor );
6162Int ?/=?( Int * lhs, Int rhs );
6163Int ?/=?( Int * lhs, long int rhs );
6164Int ?/=?( Int * lhs, unsigned long int rhs );
6165
6166[ Int, Int ] div( Int dividend, Int divisor );
6167[ Int, Int ] div( Int dividend, unsigned long int divisor );
6168
6169Int ?%?( Int dividend, Int divisor );
6170Int ?%?( Int dividend, unsigned long int divisor );
6171Int ?%?( unsigned long int dividend, Int divisor );
6172Int ?%?( Int dividend, long int divisor );
6173Int ?%?( long int dividend, Int divisor );
6174Int ?%=?( Int * lhs, Int rhs );
6175Int ?%=?( Int * lhs, long int rhs );
6176Int ?%=?( Int * lhs, unsigned long int rhs );
6177
6178Int ?<<?( Int shiften, mp_bitcnt_t shift );
6179Int ?<<=?( Int * lhs, mp_bitcnt_t shift );
6180Int ?>>?( Int shiften, mp_bitcnt_t shift );
6181Int ?>>=?( Int * lhs, mp_bitcnt_t shift );
6182
6183Int abs( Int oper );                                    §\C{// number functions}§
6184Int fact( unsigned long int N );
6185Int gcd( Int oper1, Int oper2 );
6186Int pow( Int base, unsigned long int exponent );
6187Int pow( unsigned long int base, unsigned long int exponent );
6188void srandom( gmp_randstate_t state );
6189Int random( gmp_randstate_t state, mp_bitcnt_t n );
6190Int random( gmp_randstate_t state, Int n );
6191Int random( gmp_randstate_t state, mp_size_t max_size );
6192int sgn( Int oper );
6193Int sqrt( Int oper );
6194
6195forall( dtype istype | istream( istype ) ) istype * ?|?( istype * is, Int * mp );  §\C{// I/O}§
6196forall( dtype ostype | ostream( ostype ) ) ostype * ?|?( ostype * os, Int mp );
6197\end{cfa}
6198
6199The following factorial programs contrast using GMP with the \CFA and C interfaces, where the output from these programs appears in \VRef[Figure]{f:MultiPrecisionFactorials}.
6200(Compile with flag \Indexc{-lgmp} to link with the GMP library.)
6201\begin{quote2}
6202\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
6203\multicolumn{1}{c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}}    & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}}      \\
6204\hline
6205\begin{cfa}
6206#include <gmp>§\indexc{gmp}§
6207int main( void ) {
6208        sout | "Factorial Numbers" | endl;
6209        Int fact = 1;
6210
6211        sout | 0 | fact | endl;
6212        for ( unsigned int i = 1; i <= 40; i += 1 ) {
6213                fact *= i;
6214                sout | i | fact | endl;
6215        }
6216}
6217\end{cfa}
6218&
6219\begin{cfa}
6220#include <gmp.h>§\indexc{gmp.h}§
6221int main( void ) {
6222        ®gmp_printf®( "Factorial Numbers\n" );
6223        ®mpz_t® fact;
6224        ®mpz_init_set_ui®( fact, 1 );
6225        ®gmp_printf®( "%d %Zd\n", 0, fact );
6226        for ( unsigned int i = 1; i <= 40; i += 1 ) {
6227                ®mpz_mul_ui®( fact, fact, i );
6228                ®gmp_printf®( "%d %Zd\n", i, fact );
6229        }
6230}
6231\end{cfa}
6232\end{tabular}
6233\end{quote2}
6234
6235\begin{figure}
6236\begin{cfa}
6237Factorial Numbers
62380 1
62391 1
62402 2
62413 6
62424 24
62435 120
62446 720
62457 5040
62468 40320
62479 362880
624810 3628800
624911 39916800
625012 479001600
625113 6227020800
625214 87178291200
625315 1307674368000
625416 20922789888000
625517 355687428096000
625618 6402373705728000
625719 121645100408832000
625820 2432902008176640000
625921 51090942171709440000
626022 1124000727777607680000
626123 25852016738884976640000
626224 620448401733239439360000
626325 15511210043330985984000000
626426 403291461126605635584000000
626527 10888869450418352160768000000
626628 304888344611713860501504000000
626729 8841761993739701954543616000000
626830 265252859812191058636308480000000
626931 8222838654177922817725562880000000
627032 263130836933693530167218012160000000
627133 8683317618811886495518194401280000000
627234 295232799039604140847618609643520000000
627335 10333147966386144929666651337523200000000
627436 371993326789901217467999448150835200000000
627537 13763753091226345046315979581580902400000000
627638 523022617466601111760007224100074291200000000
627739 20397882081197443358640281739902897356800000000
627840 815915283247897734345611269596115894272000000000
6279\end{cfa}
6280\caption{Multi-precision Factorials}
6281\label{f:MultiPrecisionFactorials}
6282\end{figure}
6283
6284
6285\section{Rational Numbers}
6286\label{s:RationalNumbers}
6287
6288Rational numbers are numbers written as a ratio, \ie as a fraction, where the numerator (top number) and the denominator (bottom number) are whole numbers.
6289When creating and computing with rational numbers, results are constantly reduced to keep the numerator and denominator as small as possible.
6290
6291\begin{cfa}[belowskip=0pt]
6292// implementation
6293struct Rational {§\indexc{Rational}§
6294        long int numerator, denominator;                                        // invariant: denominator > 0
6295}; // Rational
6296
6297Rational rational();                                    §\C{// constructors}§
6298Rational rational( long int n );
6299Rational rational( long int n, long int d );
6300void ?{}( Rational * r, zero_t );
6301void ?{}( Rational * r, one_t );
6302
6303long int numerator( Rational r );               §\C{// numerator/denominator getter/setter}§
6304long int numerator( Rational r, long int n );
6305long int denominator( Rational r );
6306long int denominator( Rational r, long int d );
6307
6308int ?==?( Rational l, Rational r );             §\C{// comparison}§
6309int ?!=?( Rational l, Rational r );
6310int ?<?( Rational l, Rational r );
6311int ?<=?( Rational l, Rational r );
6312int ?>?( Rational l, Rational r );
6313int ?>=?( Rational l, Rational r );
6314
6315Rational -?( Rational r );                              §\C{// arithmetic}§
6316Rational ?+?( Rational l, Rational r );
6317Rational ?-?( Rational l, Rational r );
6318Rational ?*?( Rational l, Rational r );
6319Rational ?/?( Rational l, Rational r );
6320
6321double widen( Rational r );                             §\C{// conversion}§
6322Rational narrow( double f, long int md );
6323
6324forall( dtype istype | istream( istype ) ) istype * ?|?( istype *, Rational * ); // I/O
6325forall( dtype ostype | ostream( ostype ) ) ostype * ?|?( ostype *, Rational );
6326\end{cfa}
6327
6328
6329\bibliographystyle{plain}
6330\bibliography{cfa}
6331
6332
6333\addcontentsline{toc}{section}{\indexname} % add index name to table of contents
6334\begin{theindex}
6335Italic page numbers give the location of the main entry for the referenced term.
6336Plain page numbers denote uses of the indexed term.
6337Entries for grammar non-terminals are italicized.
6338A typewriter font is used for grammar terminals and program identifiers.
6339\indexspace
6340\input{user.ind}
6341\end{theindex}
6342
6343
6344\end{document}
6345
6346% Local Variables: %
6347% tab-width: 4 %
6348% fill-column: 100 %
6349% compile-command: "make" %
6350% End: %
Note: See TracBrowser for help on using the repository browser.