source: doc/user/user.tex @ 53a6c2a

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 53a6c2a was 53a6c2a, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

change meaning of sepOn, and replace #if with #pragma once in include files

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