source: doc/papers/general/Paper.tex @ a3f53d64

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since a3f53d64 was 5346dce, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

remove proof corrections

  • Property mode set to 100644
File size: 162.0 KB
Line 
1\documentclass[AMA,STIX1COL]{WileyNJD-v2}
2\setlength\typewidth{170mm}
3\setlength\textwidth{170mm}
4
5\articletype{RESEARCH ARTICLE}%
6
7\received{12 March 2018}
8\revised{8 May 2018}
9\accepted{28 June 2018}
10
11\setlength\typewidth{168mm}
12\setlength\textwidth{168mm}
13\raggedbottom
14
15%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16
17% Latex packages used in the document.
18
19\usepackage{epic,eepic}
20\usepackage{xspace}
21\usepackage{comment}
22\usepackage{upquote}                                            % switch curled `'" to straight
23\usepackage{listings}                                           % format program code
24\captionsetup{justification=raggedright,singlelinecheck=false}
25%\usepackage{enumitem}
26%\setlist[itemize]{topsep=3pt,itemsep=2pt,parsep=0pt}% global
27%\usepackage{rotating}
28
29\hypersetup{breaklinks=true}
30\definecolor{ForestGreen}{cmyk}{1, 0, 0.99995, 0}
31
32\usepackage[pagewise]{lineno}
33\renewcommand{\linenumberfont}{\scriptsize\sffamily}
34
35\lefthyphenmin=3                                                        % hyphen only after 4 characters
36\righthyphenmin=3
37
38%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
39
40% Names used in the document.
41
42\newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}\xspace} % Cforall symbolic name
43\newcommand{\CFA}{\protect\CFAIcon}             % safe for section/caption
44\newcommand{\CFL}{\textrm{Cforall}\xspace}      % Cforall symbolic name
45\newcommand{\Celeven}{\textrm{C11}\xspace}      % C11 symbolic name
46\newcommand{\CC}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}\xspace} % C++ symbolic name
47\newcommand{\CCeleven}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}11\xspace} % C++11 symbolic name
48\newcommand{\CCfourteen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}14\xspace} % C++14 symbolic name
49\newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17\xspace} % C++17 symbolic name
50\newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
51\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj\xspace} % C++ virtual symbolic name
52\newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace} % C# symbolic name
53
54%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
55
56\newcommand{\Textbf}[2][red]{{\color{#1}{\textbf{#2}}}}
57%\newcommand{\TODO}[1]{\textbf{TODO}: {\itshape #1}} % TODO included
58\newcommand{\TODO}[1]{} % TODO elided
59
60%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
61
62% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
63% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
64% AFTER HYPERREF.
65%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
66\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
67
68\renewcommand*{\thefootnote}{\Alph{footnote}} % hack because fnsymbol does not work
69%\renewcommand*{\thefootnote}{\fnsymbol{footnote}}
70
71\makeatletter
72% parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for
73% use rather than use \parident directly.
74\newlength{\parindentlnth}
75\setlength{\parindentlnth}{\parindent}
76
77\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{\lst@basicstyle{#1}}}}
78\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
79\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
80
81\newlength{\gcolumnposn}                                        % temporary hack because lstlisting does not handle tabs correctly
82\newlength{\columnposn}
83\setlength{\gcolumnposn}{3.5in}
84\setlength{\columnposn}{\gcolumnposn}
85
86\newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}}
87\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
88
89% Denote newterms in particular font and index them without particular font and in lowercase, e.g., \newterm{abc}.
90% The option parameter provides an index term different from the new term, e.g., \newterm[\texttt{abc}]{abc}
91% The star version does not lowercase the index information, e.g., \newterm*{IBM}.
92\newcommand{\newtermFontInline}{\emph}
93\newcommand{\newterm}{\@ifstar\@snewterm\@newterm}
94\newcommand{\@newterm}[2][\@empty]{\lowercase{\def\temp{#2}}{\newtermFontInline{#2}}\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi}
95\newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}
96
97% Latin abbreviation
98\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
99\@ifundefined{eg}{
100\newcommand{\EG}{\abbrevFont{e}\abbrevFont{g}}
101\newcommand*{\eg}{%
102        \@ifnextchar{,}{\EG}%
103                {\@ifnextchar{:}{\EG}%
104                        {\EG,\xspace}}%
105}}{}%
106\@ifundefined{ie}{
107\newcommand{\IE}{\abbrevFont{i}\abbrevFont{e}}
108\newcommand*{\ie}{%
109        \@ifnextchar{,}{\IE}%
110                {\@ifnextchar{:}{\IE}%
111                        {\IE,\xspace}}%
112}}{}%
113\@ifundefined{etc}{
114\newcommand{\ETC}{\abbrevFont{etc}}
115\newcommand*{\etc}{%
116        \@ifnextchar{.}{\ETC}%
117        {\ETC.\xspace}%
118}}{}%
119\@ifundefined{etal}{
120\newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}}
121\newcommand*{\etal}{%
122        \@ifnextchar{.}{\protect\ETAL}%
123                {\protect\ETAL.\xspace}%
124}}{}%
125\@ifundefined{viz}{
126\newcommand{\VIZ}{\abbrevFont{viz}}
127\newcommand*{\viz}{%
128        \@ifnextchar{.}{\VIZ}%
129                {\VIZ.\xspace}%
130}}{}%
131\makeatother
132
133\newenvironment{cquote}{%
134        \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=3pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%
135        \item\relax
136}{%
137        \endlist
138}% cquote
139
140% CFA programming language, based on ANSI C (with some gcc additions)
141\lstdefinelanguage{CFA}[ANSI]{C}{
142        morekeywords={
143                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
144                auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
145                coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally,
146                __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__,
147                inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
148                otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, thread,
149                _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
150                virtual, __volatile, __volatile__, waitfor, when, with, zero_t},
151        moredirectives={defined,include_next}%
152}
153
154\lstset{
155language=CFA,
156columns=fullflexible,
157basicstyle=\linespread{0.9}\sf,                                                 % reduce line spacing and use sanserif font
158stringstyle=\tt,                                                                                % use typewriter font
159tabsize=5,                                                                                              % N space tabbing
160xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
161%mathescape=true,                                                                               % LaTeX math escape in CFA code $...$
162escapechar=\$,                                                                                  % LaTeX escape in CFA code
163keepspaces=true,                                                                                %
164showstringspaces=false,                                                                 % do not show spaces with cup
165showlines=true,                                                                                 % show blank lines at end of code
166aboveskip=4pt,                                                                                  % spacing above/below code block
167belowskip=3pt,
168% replace/adjust listing characters that look bad in sanserif
169literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1
170        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
171        {<}{\textrm{\textless}}1 {>}{\textrm{\textgreater}}1
172        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textrm{\textgreater}}}2,
173moredelim=**[is][\color{red}]{`}{`},
174}% lstset
175
176\lstnewenvironment{cfa}[1][]
177{\lstset{#1}}
178{}
179\lstnewenvironment{C++}[1][]                            % use C++ style
180{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{`}{`},#1}\lstset{#1}}
181{}
182
183% inline code @...@
184\lstMakeShortInline@%
185
186\let\OLDthebibliography\thebibliography
187\renewcommand\thebibliography[1]{
188  \OLDthebibliography{#1}
189  \setlength{\parskip}{0pt}
190  \setlength{\itemsep}{4pt plus 0.3ex}
191}
192
193\title{\texorpdfstring{\protect\CFA : Adding modern programming language features to C}{Cforall : Adding modern programming language features to C}}
194
195\author[1]{Aaron Moss}
196\author[1]{Robert Schluntz}
197\author[1]{Peter A. Buhr}
198\authormark{MOSS \textsc{et al}}
199
200\address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Waterloo, Ontario}, \country{Canada}}}
201
202\corres{Peter A. Buhr, Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada. \email{pabuhr{\char`\@}uwaterloo.ca}}
203
204\fundingInfo{Natural Sciences and Engineering Research Council of Canada}
205
206\abstract[Summary]{
207The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating systems.
208This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more.
209Nevertheless, C, which was first standardized almost 30 years ago, lacks many features that make programming in more modern languages safer and more productive.
210The goal of the \CFA project (pronounced ``C for all'') is to create an extension of C that provides modern safety and productivity features while still ensuring strong backward compatibility with C and its programmers.
211Prior projects have attempted similar goals but failed to honor the C programming style;
212for instance, adding object-oriented or functional programming with garbage collection is a nonstarter for many C developers.
213Specifically, \CFA is designed to have an orthogonal feature set based closely on the C programming paradigm, so that \CFA features can be added \emph{incrementally} to existing C code bases, and C programmers can learn \CFA extensions on an as-needed basis, preserving investment in existing code and programmers.
214This paper presents a quick tour of \CFA features, showing how their design avoids shortcomings of similar features in C and other C-like languages.
215Experimental results are presented to validate several of the new features.
216}%
217
218\keywords{C, Cforall, generic types, polymorphic functions, tuple types, variadic types}
219
220
221\begin{document}
222%\linenumbers                                            % comment out to turn off line numbering
223
224\maketitle
225
226
227\vspace*{-10pt}
228\section{Introduction}
229
230The C programming language is a foundational technology for modern computing with millions of lines of code implementing everything from hobby projects to commercial operating systems.
231This installation base and the programmers producing it represent a massive software engineering investment spanning decades and likely to continue for decades more.
232The TIOBE index~\cite{TIOBE} ranks the top five most \emph{popular} programming languages as Java 15\%, \Textbf{C 12\%}, \Textbf{\CC 5.5\%}, and Python 5\%, \Csharp 4.5\% = 42\%, where the next 50 languages are less than 4\% each with a long tail.
233The top three rankings over the past 30 years are as follows.
234\begin{center}
235\setlength{\tabcolsep}{10pt}
236\fontsize{9bp}{11bp}\selectfont
237\lstDeleteShortInline@%
238\begin{tabular}{@{}cccccccc@{}}
239                & 2018  & 2013  & 2008  & 2003  & 1998  & 1993  & 1988  \\
240Java    & 1             & 2             & 1             & 1             & 18    & --    & --    \\
241\Textbf{C}& \Textbf{2} & \Textbf{1} & \Textbf{2} & \Textbf{2} & \Textbf{1} & \Textbf{1} & \Textbf{1} \\
242\CC             & 3             & 4             & 3             & 3             & 2             & 2             & 5             \\
243\end{tabular}
244\lstMakeShortInline@%
245\end{center}
246Love it or hate it, C is extremely popular, highly used, and one of the few systems languages.
247In many cases, \CC is often used solely as a better C.
248Nevertheless, C, which was first standardized almost 30 years ago~\cite{ANSI89:C}, lacks many features that make programming in more modern languages safer and more productive.
249
250\CFA (pronounced ``C for all'' and written \CFA or Cforall) is an evolutionary extension of the C programming language that adds modern language features to C, while maintaining source and runtime compatibility in the familiar C programming model.
251The four key design goals for \CFA~\cite{Bilson03} are as follows:
252(1) the behavior of standard C code must remain the same when translated by a \CFA compiler as when translated by a C compiler;
253(2) the standard C code must be as fast and as small when translated by a \CFA compiler as when translated by a C compiler;
254(3) the \CFA code must be at least as portable as standard C code;
255(4) extensions introduced by \CFA must be translated in the most efficient way possible.
256These goals ensure that the existing C code bases can be converted into \CFA incrementally with minimal effort, and C programmers can productively generate \CFA code without training beyond the features being used.
257\CC is used similarly but 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.
258
259All language features discussed in this paper are working, except some advanced exception-handling features.
260Not discussed in this paper are the integrated concurrency constructs and user-level threading library~\cite{Delisle18}.
261\CFA is an \emph{open-source} project implemented as a source-to-source translator from \CFA to the gcc-dialect of C~\cite{GCCExtensions}, allowing it to leverage the portability and code optimizations provided by gcc, meeting goals (1)--(3).
262% @plg2[9]% cd cfa-cc/src; cloc ArgTweak CodeGen CodeTools Common Concurrency ControlStruct Designators GenPoly InitTweak MakeLibCfa.cc MakeLibCfa.h Parser ResolvExpr SymTab SynTree Tuples driver prelude main.cc
263% -------------------------------------------------------------------------------
264% Language                     files          blank        comment           code
265% -------------------------------------------------------------------------------
266% C++                            108           5420           5232          34961
267% C/C++ Header                    86           2379           2450           8464
268% Teamcenter def                   2            115             65           1387
269% make                             5            168             87           1052
270% C                               20            109            403            488
271% awk                              1             12             26            121
272% sed                              1              0              0              6
273% -------------------------------------------------------------------------------
274% SUM:                           223           8203           8263          46479
275% -------------------------------------------------------------------------------
276The \CFA translator is 200+ files and 46\,000+ lines of code written in C/\CC.
277A translator versus a compiler makes it easier and faster to generate and debug the C object code rather than the intermediate, assembler, or machine code;
278ultimately, a compiler is necessary for advanced features and optimal performance.
279% The translator design is based on the \emph{visitor pattern}, allowing multiple passes over the abstract code-tree, which works well for incrementally adding new feature through additional visitor passes.
280Two key translator components are expression analysis, determining expression validity and what operations are required for its implementation, and code generation, dealing with multiple forms of overloading, polymorphism, and multiple return values by converting them into the C code for a C compiler that supports none of these features.
281Details of these components are available in chapters 2 and 3 in the work of Bilson~\cite{Bilson03} and form the base for the current \CFA translator.
282% @plg2[8]% cd cfa-cc/src; cloc libcfa
283% -------------------------------------------------------------------------------
284% Language                     files          blank        comment           code
285% -------------------------------------------------------------------------------
286% C                               35           1256           1240           9116
287% C/C++ Header                    54            358           1106           1198
288% make                             2            201            325           1167
289% C++                              3             18             17            124
290% Assembly                         3             56             97            111
291% Bourne Shell                     2              2              0             25
292% awk                              1              4              0             22
293% -------------------------------------------------------------------------------
294% SUM:                           100           1895           2785          11763
295% -------------------------------------------------------------------------------
296The \CFA runtime system is 100+ files and 11\,000+ lines of code, written in \CFA.
297Currently, the \CFA runtime is the largest \emph{user} of \CFA providing a vehicle to test the language features and implementation.
298% @plg2[6]% cd cfa-cc/src; cloc tests examples benchmark
299% -------------------------------------------------------------------------------
300% Language                     files          blank        comment           code
301% -------------------------------------------------------------------------------
302% C                              237          12260           2869          23286
303% make                             8            464            245           2838
304% C/C++ Header                    22            225            175            785
305% Python                           5            131             93            420
306% C++                             10             48              5            201
307% Lua                              2             31              4            126
308% Java                             4              5              0             80
309% Go                               2             11              9             40
310% -------------------------------------------------------------------------------
311% SUM:                           290          13175           3400          27776
312% -------------------------------------------------------------------------------
313% The \CFA tests are 290+ files and 27,000+ lines of code.
314% The tests illustrate syntactic and semantic features in \CFA, plus a growing number of runtime benchmarks.
315% The tests check for correctness and are used for daily regression testing of 3800+ commits.
316
317Finally, it is impossible to describe a programming language without usage before definition.
318Therefore, syntax and semantics appear before explanations;
319hence, patience is necessary until sufficient details are presented and discussed.
320Similarly, a detailed comparison with other programming languages is postponed until Section~\ref{s:RelatedWork}.
321
322
323\vspace*{-6pt}
324\section{Polymorphic Functions}
325
326\CFA introduces both ad hoc and parametric polymorphism to C, with a design originally formalized by Ditchfield~\cite{Ditchfield92} and first implemented by Bilson~\cite{Bilson03}.
327Shortcomings are identified in the existing approaches to generic and variadic data types in C-like languages and how these shortcomings are avoided in \CFA.
328Specifically, the solution is both reusable and type checked, as well as conforming to the design goals of \CFA with ergonomic use of existing C abstractions.
329The new constructs are empirically compared with C and \CC approaches via performance experiments in Section~\ref{sec:eval}.
330
331
332\vspace*{-6pt}
333\subsection{Name overloading}
334\label{s:NameOverloading}
335
336\begin{quote}
337``There are only two hard things in Computer Science: cache invalidation and \emph{naming things}.''---Phil Karlton
338\end{quote}
339\vspace{-9pt}
340C already has a limited form of ad hoc polymorphism in its basic arithmetic operators, which apply to a variety of different types using identical syntax.
341\CFA extends the built-in operator overloading by allowing users to define overloads for any function, not just operators, and even any variable;
342Section~\ref{sec:libraries} includes a number of examples of how this overloading simplifies \CFA programming relative to C.
343Code generation for these overloaded functions and variables is implemented by the usual approach of mangling the identifier names to include a representation of their type, while \CFA decides which overload to apply based on the same ``usual arithmetic conversions'' used in C to disambiguate operator overloads.
344
345\newpage
346\begin{cfa}
347int max = 2147483647;                                           $\C[4in]{// (1)}$
348double max = 1.7976931348623157E+308;           $\C{// (2)}$
349int max( int a, int b ) { return a < b ? b : a; }  $\C{// (3)}$
350double max( double a, double b ) { return a < b ? b : a; }  $\C{// (4)}\CRT$
351max( 7, -max );                                         $\C[3in]{// uses (3) and (1), by matching int from constant 7}$
352max( max, 3.14 );                                       $\C{// uses (4) and (2), by matching double from constant 3.14}$
353max( max, -max );                                       $\C{// ERROR, ambiguous}$
354int m = max( max, -max );                       $\C{// uses (3) and (1) twice, by matching return type}\CRT$
355\end{cfa}
356
357\CFA maximizes the ability to reuse names to aggressively address the naming problem.
358In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction.
359In the above, the name @max@ has a consistent meaning, and a programmer only needs to remember the single concept: maximum.
360To prevent significant ambiguities, \CFA uses the return type in selecting overloads, \eg in the assignment to @m@, the compiler uses @m@'s type to unambiguously select the most appropriate call to function @max@ (as does Ada).
361As is shown later, there are a number of situations where \CFA takes advantage of available type information to disambiguate, where other programming languages generate ambiguities.
362
363\Celeven added @_Generic@ expressions (see section~6.5.1.1 of the ISO/IEC 9899~\cite{C11}), which is used with preprocessor macros to provide ad hoc polymorphism;
364however, this polymorphism is both functionally and ergonomically inferior to \CFA name overloading.
365The macro wrapping the generic expression imposes some limitations, for instance, it cannot implement the example above, because the variables @max@ are ambiguous with the functions @max@.
366Ergonomic limitations of @_Generic@ include the necessity to put a fixed list of supported types in a single place and manually dispatch to appropriate overloads, as well as possible namespace pollution from the dispatch functions, which must all have distinct names.
367\CFA supports @_Generic@ expressions for backward compatibility, but it is an unnecessary mechanism.
368
369% http://fanf.livejournal.com/144696.html
370% http://www.robertgamble.net/2012/01/c11-generic-selections.html
371% https://abissell.com/2014/01/16/c11s-_generic-keyword-macro-applications-and-performance-impacts/
372
373
374\vspace*{-10pt}
375\subsection{\texorpdfstring{\protect\lstinline{forall} functions}{forall functions}}
376\label{sec:poly-fns}
377
378The 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).
379\begin{cfa}
380`forall( otype T )` T identity( T val ) { return val; }
381int forty_two = identity( 42 );         $\C{// T is bound to int, forty\_two == 42}$
382\end{cfa}
383This @identity@ function can be applied to any complete \newterm{object type} (or @otype@).
384The type variable @T@ is transformed into a set of additional implicit parameters encoding sufficient information about @T@ to create and return a variable of that type.
385The \CFA implementation passes the size and alignment of the type represented by an @otype@ parameter, as well as an assignment operator, constructor, copy constructor, and destructor.
386If this extra information is not needed, for instance, for a pointer, the type parameter can be declared as a \newterm{data type} (or @dtype@).
387
388In \CFA, the polymorphic runtime cost is spread over each polymorphic call, because more arguments are passed to polymorphic functions;
389the experiments in Section~\ref{sec:eval} show this overhead is similar to \CC virtual function calls.
390A design advantage is that, unlike \CC template functions, \CFA polymorphic functions are compatible with C \emph{separate compilation}, preventing compilation and code bloat.
391
392Since bare polymorphic types provide a restricted set of available operations, \CFA provides a \newterm{type assertion}~\cite[pp.~37-44]{Alphard} mechanism to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type variable.
393For example, the function @twice@ can be defined using the \CFA syntax for operator overloading.
394\begin{cfa}
395forall( otype T `| { T ?+?(T, T); }` ) T twice( T x ) { return x `+` x; }  $\C{// ? denotes operands}$
396int val = twice( twice( 3.7 ) );  $\C{// val == 14}$
397\end{cfa}
398This works for any type @T@ with a matching addition operator.
399The polymorphism is achieved by creating a wrapper function for calling @+@ with the @T@ bound to @double@ and then passing this function to the first call of @twice@.
400There is now the option of using the same @twice@ and converting the result into @int@ on assignment or creating another @twice@ with the type parameter @T@ bound to @int@ because \CFA uses the return type~\cite{Cormack81,Baker82,Ada} in its type analysis.
401The first approach has a late conversion from @double@ to @int@ on the final assignment, whereas the second has an early conversion to @int@.
402\CFA minimizes the number of conversions and their potential to lose information;
403hence, it selects the first approach, which corresponds with C programmer intuition.
404
405Crucial to the design of a new programming language are the libraries to access thousands of external software features.
406Like \CC, \CFA inherits a massive compatible library base, where other programming languages must rewrite or provide fragile interlanguage communication with C.
407A simple example is leveraging the existing type-unsafe (@void *@) C @bsearch@ to binary search a sorted float array.
408\begin{cfa}
409void * bsearch( const void * key, const void * base, size_t nmemb, size_t size,
410                                int (* compar)( const void *, const void * ));
411int comp( const void * t1, const void * t2 ) {
412         return *(double *)t1 < *(double *)t2 ? -1 : *(double *)t2 < *(double *)t1 ? 1 : 0;
413}
414double key = 5.0, vals[10] = { /* 10 sorted float values */ };
415double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp ); $\C{// search sorted array}$
416\end{cfa}
417This can be augmented simply with generalized, type-safe, \CFA-overloaded wrappers.
418\begin{cfa}
419forall( otype T | { int ?<?( T, T ); } ) T * bsearch( T key, const T * arr, size_t size ) {
420        int comp( const void * t1, const void * t2 ) { /* as above with double changed to T */ }
421        return (T *)bsearch( &key, arr, size, sizeof(T), comp );
422}
423forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) {
424        T * result = bsearch( key, arr, size ); $\C{// call first version}$
425        return result ? result - arr : size; $\C{// pointer subtraction includes sizeof(T)}$
426}
427double * val = bsearch( 5.0, vals, 10 ); $\C{// selection based on return type}$
428int posn = bsearch( 5.0, vals, 10 );
429\end{cfa}
430The nested function @comp@ provides the hidden interface from typed \CFA to untyped (@void *@) C, plus the cast of the result.
431% FIX
432Providing a hidden @comp@ function in \CC is awkward as lambdas do not use C calling conventions and template declarations cannot appear in block scope.
433In addition, an alternate kind of return is made available: position versus pointer to found element.
434\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 template @bsearch@.
435
436\CFA has replacement libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions, all without rewriting the actual computations (see Section~\ref{sec:libraries}).
437For example, it is possible to write a type-safe \CFA wrapper @malloc@ based on the C @malloc@, where the return type supplies the type/size of the allocation, which is impossible in most type systems.
438\begin{cfa}
439forall( dtype T | sized(T) ) T * malloc( void ) { return (T *)malloc( sizeof(T) ); }
440// select type and size from left-hand side
441int * ip = malloc();  double * dp = malloc();  struct S {...} * sp = malloc();
442\end{cfa}
443
444Call site inferencing and nested functions provide a localized form of inheritance.
445For example, the \CFA @qsort@ only sorts in ascending order using @<@.
446However, it is trivial to locally change this behavior.
447\begin{cfa}
448forall( otype T | { int ?<?( T, T ); } ) void qsort( const T * arr, size_t size ) { /* use C qsort */ }
449int main() {
450        int ?<?( double x, double y ) { return x `>` y; } $\C{// locally override behavior}$
451        qsort( vals, 10 );                                                      $\C{// descending sort}$
452}
453\end{cfa}
454The local version of @?<?@ performs @?>?@ overriding the built-in @?<?@ so it is passed to @qsort@.
455Therefore, programmers can easily form local environments, adding and modifying appropriate functions, to maximize the reuse of other existing functions and types.
456
457To reduce duplication, it is possible to distribute a group of @forall@ (and storage-class qualifiers) over functions/types, such that each block declaration is prefixed by the group (see the example in Appendix~\ref{s:CforallStack}).
458\begin{cfa}
459forall( otype `T` ) {                                                   $\C{// distribution block, add forall qualifier to declarations}$
460        struct stack { stack_node(`T`) * head; };       $\C{// generic type}$
461        inline {                                                                        $\C{// nested distribution block, add forall/inline to declarations}$
462                void push( stack(`T`) & s, `T` value ) ...      $\C{// generic operations}$
463        }
464}
465\end{cfa}
466
467
468\subsection{Traits}
469
470\CFA provides \newterm{traits} to name a group of type assertions, where the trait name allows specifying the same set of assertions in multiple locations, preventing repetition mistakes at each function declaration.
471\begin{cquote}
472\lstDeleteShortInline@%
473\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
474\begin{cfa}
475trait `sumable`( otype T ) {
476        void `?{}`( T &, zero_t ); // 0 literal constructor
477        T ?+?( T, T );                   // assortment of additions
478        T `?+=?`( T &, T );
479        T ++?( T & );
480        T ?++( T & );
481};
482\end{cfa}
483&
484\begin{cfa}
485forall( otype T `| sumable( T )` ) // use trait
486T sum( T a[$\,$], size_t size ) {
487        `T` total = { `0` };  // initialize by 0 constructor
488        for ( size_t i = 0; i < size; i += 1 )
489                total `+=` a[i]; // select appropriate +
490        return total;
491}
492\end{cfa}
493\end{tabular}
494\lstMakeShortInline@%
495\end{cquote}
496
497Note that the @sumable@ trait does not include a copy constructor needed for the right side of @?+=?@ and return;
498it is provided by @otype@, which is syntactic sugar for the following trait.
499\begin{cfa}
500trait otype( dtype T | sized(T) ) {  // sized is a pseudo-trait for types with known size and alignment
501        void ?{}( T & );                                                $\C{// default constructor}$
502        void ?{}( T &, T );                                             $\C{// copy constructor}$
503        void ?=?( T &, T );                                             $\C{// assignment operator}$
504        void ^?{}( T & );                                               $\C{// destructor}$
505};
506\end{cfa}
507Given the information provided for an @otype@, variables of polymorphic type can be treated as if they were a complete type: stack allocatable, default or copy initialized, assigned, and deleted.
508
509In summation, the \CFA type system uses \newterm{nominal typing} for concrete types, matching with the C type system, and \newterm{structural typing} for polymorphic types.
510Hence, trait names play no part in type equivalence;
511the names are simply macros for a list of polymorphic assertions, which are expanded at usage sites.
512Nevertheless, trait names form a logical subtype hierarchy with @dtype@ at the top, where traits often contain overlapping assertions, \eg operator @+@.
513Traits are used like interfaces in Java or abstract base classes in \CC, but without the nominal inheritance relationships.
514Instead, each polymorphic function (or generic type) defines the structural type needed for its execution (polymorphic type key), and this key is fulfilled at each call site from the lexical environment, which is similar to the Go~\cite{Go} interfaces.
515Hence, new lexical scopes and nested functions are used extensively to create local subtypes, as in the @qsort@ example, without having to manage a nominal inheritance hierarchy.
516% (Nominal inheritance can be approximated with traits using marker variables or functions, as is done in Go.)
517
518% Nominal inheritance can be simulated with traits using marker variables or functions:
519% \begin{cfa}
520% trait nominal(otype T) {
521%     T is_nominal;
522% };
523% int is_nominal;                                                               $\C{// int now satisfies the nominal trait}$
524% \end{cfa}
525%
526% Traits, however, are significantly more powerful than nominal-inheritance interfaces; most notably, traits may be used to declare a relationship \emph{among} multiple types, a property that may be difficult or impossible to represent in nominal-inheritance type systems:
527% \begin{cfa}
528% trait pointer_like(otype Ptr, otype El) {
529%     lvalue El *?(Ptr);                                                $\C{// Ptr can be dereferenced into a modifiable value of type El}$
530% }
531% struct list {
532%     int value;
533%     list * next;                                                              $\C{// may omit "struct" on type names as in \CC}$
534% };
535% typedef list * list_iterator;
536%
537% lvalue int *?( list_iterator it ) { return it->value; }
538% \end{cfa}
539% In the example above, @(list_iterator, int)@ satisfies @pointer_like@ by the user-defined dereference function, and @(list_iterator, list)@ also satisfies @pointer_like@ by the built-in dereference operator for pointers. Given a declaration @list_iterator it@, @*it@ can be either an @int@ or a @list@, with the meaning disambiguated by context (\eg @int x = *it;@ interprets @*it@ as an @int@, while @(*it).value = 42;@ interprets @*it@ as a @list@).
540% While a nominal-inheritance system with associated types could model one of those two relationships by making @El@ an associated type of @Ptr@ in the @pointer_like@ implementation, few such systems could model both relationships simultaneously.
541
542
543\section{Generic Types}
544
545A significant shortcoming of standard C is the lack of reusable type-safe abstractions for generic data structures and algorithms.
546Broadly speaking, there are three approaches to implement abstract data structures in C.
547One approach is to write bespoke data structures for each context in which they are needed.
548While this approach is flexible and supports integration with the C type checker and tooling, it is also tedious and error prone, especially for more complex data structures.
549A second approach is to use @void *@-based polymorphism, \eg the C standard library functions @bsearch@ and @qsort@, which allow for the reuse of code with common functionality.
550However, basing all polymorphism on @void *@ eliminates the type checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that is otherwise not needed.
551A third approach to generic code is to use preprocessor macros, which does allow the generated code to be both generic and type checked, but errors may be difficult to interpret.
552Furthermore, writing and using preprocessor macros is unnatural and inflexible.
553
554\CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data types.
555\CFA generic types integrate efficiently and naturally with the existing polymorphic functions, while retaining backward compatibility with C and providing separate compilation.
556However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates.
557
558A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration and instantiated using a parenthesized list of types after the type name.
559\begin{cquote}
560\lstDeleteShortInline@%
561\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
562\begin{cfa}
563`forall( otype R, otype S )` struct pair {
564        R first;        S second;
565};
566`forall( otype T )` // dynamic
567T value( pair(const char *, T) p ) { return p.second; }
568`forall( dtype F, otype T )` // dtype-static (concrete)
569T value( pair(F *, T * ) p) { return *p.second; }
570\end{cfa}
571&
572\begin{cfa}
573pair(const char *, int) p = {"magic", 42}; // concrete
574int i = value( p );
575pair(void *, int *) q = { 0, &p.second }; // concrete
576i = value( q );
577double d = 1.0;
578pair(double *, double *) r = { &d, &d }; // concrete
579d = value( r );
580\end{cfa}
581\end{tabular}
582\lstMakeShortInline@%
583\end{cquote}
584
585\CFA classifies generic types as either \newterm{concrete} or \newterm{dynamic}.
586Concrete types have a fixed memory layout regardless of type parameters, whereas dynamic types vary in memory layout depending on their type parameters.
587A \newterm{dtype-static} type has polymorphic parameters but is still concrete.
588Polymorphic pointers are an example of dtype-static types;
589given some type variable @T@, @T@ is a polymorphic type, as is @T *@, but @T *@ has a fixed size and can, therefore, be represented by @void *@ in code generation.
590
591\CFA generic types also allow checked argument constraints.
592For example, the following declaration of a sorted set type ensures the set key supports equality and relational comparison.
593\begin{cfa}
594forall( otype Key | { _Bool ?==?(Key, Key); _Bool ?<?(Key, Key); } ) struct sorted_set;
595\end{cfa}
596
597
598\subsection{Concrete generic types}
599
600The \CFA translator template expands concrete generic types into new structure types, affording maximal inlining.
601To enable interoperation among equivalent instantiations of a generic type, the translator saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate.
602A function declaration that accepts or returns a concrete generic type produces a declaration for the instantiated structure in the same scope, which all callers may reuse.
603For example, the concrete instantiation for @pair( const char *, int )@ is
604\begin{cfa}
605struct _pair_conc0 {
606        const char * first;  int second;
607};
608\end{cfa}
609
610A concrete generic type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations.
611In the above example, the @pair( F *, T * )@ parameter to @value@ is such a type; its expansion is below, and it is used as the type of the variables @q@ and @r@ as well, with casts for member access where appropriate.
612\begin{cfa}
613struct _pair_conc1 {
614        void * first, * second;
615};
616\end{cfa}
617
618
619\subsection{Dynamic generic types}
620
621Though \CFA implements concrete generic types efficiently, it also has a fully general system for dynamic generic types.
622As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact, all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller.
623Dynamic generic types also have an \newterm{offset array} containing structure-member offsets.
624A dynamic generic @union@ needs no such offset array, as all members are at offset 0, but size and alignment are still necessary.
625Access to members of a dynamic structure is provided at runtime via base displacement addressing
626% FIX
627using the structure pointer and the member offset (similar to the @offsetof@ macro), moving a compile-time offset calculation to runtime.
628
629The offset arrays are statically generated where possible.
630If a dynamic generic type is declared to be passed or returned by value from a polymorphic function, the translator can safely assume that the generic type is complete (\ie has a known layout) at any call site, and the offset array is passed from the caller;
631if the generic type is concrete at the call site, the elements of this offset array can even be statically generated using the C @offsetof@ macro.
632As an example, the body of the second @value@ function is implemented as
633\begin{cfa}
634_assign_T( _retval, p + _offsetof_pair[1] ); $\C{// return *p.second}$
635\end{cfa}
636\newpage
637\noindent
638Here, @_assign_T@ is passed in as an implicit parameter from @otype T@, and takes two @T *@ (@void *@ in the generated code), a destination and a source, and @_retval@ is the pointer to a caller-allocated buffer for the return value, the usual \CFA method to handle dynamically sized return types.
639@_offsetof_pair@ is the offset array passed into @value@;
640this array is generated at the call site as
641\begin{cfa}
642size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second ) }
643\end{cfa}
644
645In some cases, the offset arrays cannot be statically generated.
646For instance, modularity is generally provided in C by including an opaque forward declaration of a structure and associated accessor and mutator functions in a header file, with the actual implementations in a separately compiled @.c@ file.
647\CFA supports this pattern for generic types, but the caller does not know the actual layout or size of the dynamic generic type and only holds it by a pointer.
648The \CFA translator automatically generates \newterm{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed into a function from that function's caller.
649These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all @sized@ parameters to the generic structure (un@sized@ parameters are forbidden from being used in a context that affects layout).
650Results of these layout functions are cached so that they are only computed once per type per function. %, as in the example below for @pair@.
651Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature.
652For instance, a function that strips duplicate values from an unsorted @vector(T)@ likely has a pointer to the vector as its only explicit parameter, but uses some sort of @set(T)@ internally to test for duplicate values.
653This function could acquire the layout for @set(T)@ by calling its layout function with the layout of @T@ implicitly passed into the function.
654
655Whether a type is concrete, dtype-static, or dynamic is decided solely on the @forall@'s type parameters.
656This design allows opaque forward declarations of generic types, \eg @forall(otype T)@ @struct Box@ -- like in C, all uses of @Box(T)@ can be separately compiled, and callers from other translation units know the proper calling conventions to use.
657If the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static (\eg @forall(otype T)@ @struct unique_ptr { T * p }@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.);
658however, preserving separate compilation (and the associated C compatibility) in the existing design is judged to be an appropriate trade-off.
659
660
661\subsection{Applications}
662\label{sec:generic-apps}
663
664The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost.
665The most important such pattern is using @forall(dtype T) T *@ as a type-checked replacement for @void *@, \eg creating a lexicographic comparison for pairs of pointers used by @bsearch@ or @qsort@:
666\begin{cfa}
667forall( dtype T ) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
668        return cmp( a->first, b->first ) ? : cmp( a->second, b->second );
669}
670\end{cfa}
671Since @pair( T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@;
672hence, the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type checked to ensure members of both pairs and arguments to the comparison function match in type.
673
674Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag structures}.
675Sometimes, information is only used for type checking and can be omitted at runtime.
676\begin{cquote}
677\lstDeleteShortInline@%
678\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
679\begin{cfa}
680forall( dtype Unit ) struct scalar { unsigned long value; };
681struct metres {};
682struct litres {};
683forall( dtype U ) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
684        return (scalar(U)){ a.value + b.value };
685}
686\end{cfa}
687&
688\begin{cfa}
689scalar(metres) half_marathon = { 21_098 };
690scalar(litres) pool = { 2_500_000 };
691scalar(metres) marathon = half_marathon +
692                                                        half_marathon;
693scalar(litres) two_pools = pool + pool;
694`marathon + pool;` // ERROR, mismatched types
695\end{cfa}
696\end{tabular}
697\lstMakeShortInline@%
698\end{cquote}
699Here, @scalar@ is a dtype-static type;
700hence, all uses have a single structure definition, containing @unsigned long@, and can share the same implementations of common functions like @?+?@.
701These implementations may even be separately compiled, unlike \CC template functions.
702However, the \CFA type checker ensures matching types are used by all calls to @?+?@, preventing nonsensical computations like adding a length to a volume.
703
704
705\section{Tuples}
706\label{sec:tuples}
707
708In many languages, functions can return, at most, one value;
709however, many operations have multiple outcomes, some exceptional.
710Consider C's @div@ and @remquo@ functions, which return the quotient and remainder for a division of integer and float values, respectively.
711\begin{cfa}
712typedef struct { int quo, rem; } div_t;         $\C{// from include stdlib.h}$
713div_t div( int num, int den );
714double remquo( double num, double den, int * quo );
715div_t qr = div( 13, 5 );                                        $\C{// return quotient/remainder aggregate}$
716int q;
717double r = remquo( 13.5, 5.2, &q );                     $\C{// return remainder, alias quotient}$
718\end{cfa}
719Here, @div@ aggregates the quotient/remainder in a structure, whereas @remquo@ aliases a parameter to an argument.
720Both approaches are awkward.
721% FIX
722Alternatively, a programming language can directly support returning multiple values, \eg \CFA provides the following.
723\begin{cfa}
724[ int, int ] div( int num, int den );           $\C{// return two integers}$
725[ double, double ] div( double num, double den ); $\C{// return two doubles}$
726int q, r;                                                                       $\C{// overloaded variable names}$
727double q, r;
728[ q, r ] = div( 13, 5 );                                        $\C{// select appropriate div and q, r}$
729[ q, r ] = div( 13.5, 5.2 );                            $\C{// assign into tuple}$
730\end{cfa}
731This approach is straightforward to understand and use;
732therefore, why do few programming languages support this obvious feature or provide it awkwardly?
733To answer, there are complex consequences that cascade through multiple aspects of the language, especially the type system.
734This section shows these consequences and how \CFA handles them.
735
736
737\subsection{Tuple Expressions}
738
739The addition of multiple-return-value functions (MRVFs) is \emph{useless} without a syntax for accepting multiple values at the call site.
740The simplest mechanism for capturing the return values is variable assignment, allowing the values to be retrieved directly.
741As such, \CFA allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions (as above), called a \newterm{tuple}.
742
743However, functions also use \newterm{composition} (nested calls), with the direct consequence that MRVFs must also support composition to be orthogonal with single-returning-value functions (SRVFs), \eg, \CFA provides the following.
744\begin{cfa}
745printf( "%d %d\n", div( 13, 5 ) );                      $\C{// return values seperated into arguments}$
746\end{cfa}
747Here, the values returned by @div@ are composed with the call to @printf@ by flattening the tuple into separate arguments.
748However, the \CFA type-system must support significantly more complex composition.
749\begin{cfa}
750[ int, int ] foo$\(_1\)$( int );                        $\C{// overloaded foo functions}$
751[ double ] foo$\(_2\)$( int );
752void bar( int, double, double );
753`bar`( foo( 3 ), foo( 3 ) );
754\end{cfa}
755The type resolver only has the tuple return types to resolve the call to @bar@ as the @foo@ parameters are identical, which involves unifying the possible @foo@ functions with @bar@'s parameter list.
756No combination of @foo@s is an exact match with @bar@'s parameters;
757thus, the resolver applies C conversions.
758% FIX
759The minimal cost is @bar( foo@$_1$@( 3 ), foo@$_2$@( 3 ) )@, giving (@int@, {\color{ForestGreen}@int@}, @double@) to (@int@, {\color{ForestGreen}@double@}, @double@) with one {\color{ForestGreen}safe} (widening) conversion from @int@ to @double@ versus ({\color{red}@double@}, {\color{ForestGreen}@int@}, {\color{ForestGreen}@int@}) to ({\color{red}@int@}, {\color{ForestGreen}@double@}, {\color{ForestGreen}@double@}) with one {\color{red}unsafe} (narrowing) conversion from @double@ to @int@ and two safe conversions.
760
761
762\subsection{Tuple variables}
763
764An important observation from function composition is that new variable names are not required to initialize parameters from an MRVF.
765\CFA also allows declaration of tuple variables that can be initialized from an MRVF, since it can be awkward to declare multiple variables of different types.
766\newpage
767\begin{cfa}
768[ int, int ] qr = div( 13, 5 );                         $\C{// tuple-variable declaration and initialization}$
769[ double, double ] qr = div( 13.5, 5.2 );
770\end{cfa}
771Here, the tuple variable name serves the same purpose as the parameter name(s).
772Tuple variables can be composed of any types, except for array types, since array sizes are generally unknown in C.
773
774One way to access the tuple variable components is with assignment or composition.
775\begin{cfa}
776[ q, r ] = qr;                                                          $\C{// access tuple-variable components}$
777printf( "%d %d\n", qr );
778\end{cfa}
779\CFA also supports \newterm{tuple indexing} to access single components of a tuple expression.
780\begin{cfa}
781[int, int] * p = &qr;                                           $\C{// tuple pointer}$
782int rem = qr`.1`;                                                       $\C{// access remainder}$
783int quo = div( 13, 5 )`.0`;                                     $\C{// access quotient}$
784p`->0` = 5;                                                                     $\C{// change quotient}$
785bar( qr`.1`, qr );                                                      $\C{// pass remainder and quotient/remainder}$
786rem = [div( 13, 5 ), 42]`.0.1`;                         $\C{// access 2nd component of 1st component}$
787\end{cfa}
788
789
790\subsection{Flattening and restructuring}
791
792In function call contexts, tuples support implicit flattening and restructuring conversions.
793Tuple flattening recursively expands a tuple into the list of its basic components.
794Tuple structuring packages a list of expressions into a value of tuple type.
795\begin{cfa}
796int f( int, int );
797[int] g( [int, int] );
798[int] h( int, [int, int] );
799[int, int] x;
800int y;
801f( x );                                                                         $\C{// flatten}$
802g( y, 10 );                                                                     $\C{// structure}$
803h( x, y );                                                                      $\C{// flatten and structure}$
804\end{cfa}
805In the call to @f@, @x@ is implicitly flattened so the components of @x@ are passed as two arguments.
806In the call to @g@, the values @y@ and @10@ are structured into a single argument of type @[int, int]@ to match the parameter type of @g@.
807Finally, in the call to @h@, @x@ is flattened to yield an argument list of length 3, of which the first component of @x@ is passed as the first parameter of @h@, and the second component of @x@ and @y@ are structured into the second argument of type @[int, int]@.
808The flexible structure of tuples permits a simple and expressive function call syntax to work seamlessly with both SRVFs and MRVFs with any number of arguments of arbitrarily complex structure.
809
810
811\subsection{Tuple assignment}
812
813\enlargethispage{-10pt}
814An assignment where the left side is a tuple type is called \newterm{tuple assignment}.
815There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a nontuple type, called \newterm{multiple} and \newterm{mass assignment}, respectively.
816\begin{cfa}
817int x = 10;
818double y = 3.5;
819[int, double] z;
820z = [x, y];                                                                     $\C{// multiple assignment}$
821[x, y] = z;                                                                     $\C{// multiple assignment}$
822z = 10;                                                                         $\C{// mass assignment}$
823[y, x] = 3.14;                                                          $\C{// mass assignment}$
824\end{cfa}
825Both kinds of tuple assignment have parallel semantics, so that each value on the left and right sides is evaluated before any assignments occur.
826As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function, \eg, @[x, y] = [y, x]@.
827This semantics means mass assignment differs from C cascading assignment (\eg @a = b = c@) in that conversions are applied in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment.
828For example, @[y, x] = 3.14@ performs the assignments @y = 3.14@ and @x = 3.14@, yielding @y == 3.14@ and @x == 3@, whereas C cascading assignment @y = x = 3.14@ performs the assignments @x = 3.14@ and @y = x@, yielding @3@ in @y@ and @x@.
829Finally, tuple assignment is an expression where the result type is the type of the left-hand side of the assignment, just like all other assignment expressions in C.
830This example shows mass, multiple, and cascading assignment used in one expression.
831\begin{cfa}
832[void] f( [int, int] );
833f( [x, y] = z = 1.5 );                                          $\C{// assignments in parameter list}$
834\end{cfa}
835
836
837\subsection{Member access}
838
839It is also possible to access multiple members from a single expression using a \newterm{member access}.
840The result is a single tuple-valued expression whose type is the tuple of the types of the members.
841\begin{cfa}
842struct S { int x; double y; char * z; } s;
843s.[x, y, z] = 0;
844\end{cfa}
845Here, the mass assignment sets all members of @s@ to zero.
846Since tuple-index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member-tuple expressions to manually restructure a tuple (\eg rearrange, drop, and duplicate components).
847\begin{cfa}
848[int, int, long, double] x;
849void f( double, long );
850x.[0, 1] = x.[1, 0];                                            $\C{// rearrange: [x.0, x.1] = [x.1, x.0]}$
851f( x.[0, 3] );                                                          $\C{// drop: f(x.0, x.3)}$
852[int, int, int] y = x.[2, 0, 2];                        $\C{// duplicate: [y.0, y.1, y.2] = [x.2, x.0.x.2]}$
853\end{cfa}
854It is also possible for a member access to contain other member accesses.
855\begin{cfa}
856struct A { double i; int j; };
857struct B { int * k; short l; };
858struct C { int x; A y; B z; } v;
859v.[x, y.[i, j], z.k];                                           $\C{// [v.x, [v.y.i, v.y.j], v.z.k]}$
860\end{cfa}
861
862
863\begin{comment}
864\subsection{Casting}
865
866In C, the cast operator is used to explicitly convert between types.
867In \CFA, the cast operator has a secondary use as type ascription.
868That is, a cast can be used to select the type of an expression when it is ambiguous, as in the call to an overloaded function:
869\begin{cfa}
870int f();     // (1)
871double f()// (2)
872
873f();       // ambiguous - (1),(2) both equally viable
874(int)f()// choose (2)
875\end{cfa}
876
877Since casting is a fundamental operation in \CFA, casts should be given a meaningful interpretation in the context of tuples.
878Taking a look at standard C provides some guidance with respect to the way casts should work with tuples:
879\begin{cfa}
880int f();
881void g();
882
883(void)f()// (1)
884(int)g()// (2)
885\end{cfa}
886In C, (1) is a valid cast, which calls @f@ and discards its result.
887On the other hand, (2) is invalid, because @g@ does not produce a result, so requesting an @int@ to materialize from nothing is nonsensical.
888Generalizing these principles, any cast wherein the number of components increases as a result of the cast is invalid, while casts that have the same or fewer number of components may be valid.
889
890Formally, a cast to tuple type is valid when $T_n \leq S_m$, where $T_n$ is the number of components in the target type and $S_m$ is the number of components in the source type, and for each $i$ in $[0, n)$, $S_i$ can be cast to $T_i$.
891Excess elements ($S_j$ for all $j$ in $[n, m)$) are evaluated, but their values are discarded so that they are not included in the result expression.
892This approach follows naturally from the way that a cast to @void@ works in C.
893
894For example, in
895\begin{cfa}
896[int, int, int] f();
897[int, [int, int], int] g();
898
899([int, double])f();           $\C{// (1)}$
900([int, int, int])g();         $\C{// (2)}$
901([void, [int, int]])g();      $\C{// (3)}$
902([int, int, int, int])g();    $\C{// (4)}$
903([int, [int, int, int]])g()$\C{// (5)}$
904\end{cfa}
905
906(1) discards the last element of the return value and converts the second element to @double@.
907Since @int@ is effectively a 1-element tuple, (2) discards the second component of the second element of the return value of @g@.
908If @g@ is free of side effects, this expression is equivalent to @[(int)(g().0), (int)(g().1.0), (int)(g().2)]@.
909Since @void@ is effectively a 0-element tuple, (3) discards the first and third return values, which is effectively equivalent to @[(int)(g().1.0), (int)(g().1.1)]@).
910
911Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions requires more precise matching of types than allowed for function arguments and parameters.}.
912As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3.
913Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid.
914That is, it is invalid to cast @[int, int]@ to @[int, int, int]@.
915\end{comment}
916
917
918\subsection{Polymorphism}
919
920Tuples also integrate with \CFA polymorphism as a kind of generic type.
921Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with nontuple types.
922\begin{cfa}
923forall( otype T, dtype U ) void f( T x, U * y );
924f( [5, "hello"] );
925\end{cfa}
926Here, @[5, "hello"]@ is flattened, giving argument list @5, "hello"@, and @T@ binds to @int@ and @U@ binds to @const char@.
927Tuples, however, may contain polymorphic components.
928For example, a plus operator can be written to sum two triples.
929\begin{cfa}
930forall( otype T | { T ?+?( T, T ); } ) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
931        return [x.0 + y.0, x.1 + y.1, x.2 + y.2];
932}
933[int, int, int] x;
934int i1, i2, i3;
935[i1, i2, i3] = x + ([10, 20, 30]);
936\end{cfa}
937
938Flattening and restructuring conversions are also applied to tuple types in polymorphic type assertions.
939\begin{cfa}
940[int] f( [int, double], double );
941forall( otype T, otype U | { T f( T, U, U ); } ) void g( T, U );
942g( 5, 10.21 );
943\end{cfa}
944\newpage
945Hence, function parameter and return lists are flattened for the purposes of type unification allowing the example to pass expression resolution.
946This relaxation is possible by extending the thunk scheme described by Bilson~\cite{Bilson03}.
947% Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function:
948% \begin{cfa}
949% int _thunk( int _p0, double _p1, double _p2 ) { return f( [_p0, _p1], _p2 ); }
950% \end{cfa}
951% so the thunk provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
952% These thunks are generated locally using gcc nested-functions, rather hoisting them to the external scope, so they can easily access local state.
953
954
955\subsection{Variadic tuples}
956\label{sec:variadic-tuples}
957
958To define variadic functions, \CFA adds a new kind of type parameter, \ie @ttype@ (tuple type).
959Matching against a @ttype@ parameter consumes all the remaining argument components and packages them into a tuple, binding to the resulting tuple of types.
960In a given parameter list, there must be, at most, one @ttype@ parameter that occurs last, which matches normal variadic semantics, with a strong feeling of similarity to \CCeleven variadic templates.
961As such, @ttype@ variables are also called \newterm{argument packs}.
962
963Like variadic templates, @ttype@ polymorphic functions are primarily manipulated via recursion.
964Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful.
965Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled.
966For example, the following is a generalized @sum@ function.
967\begin{cfa}
968int sum$\(_0\)$() { return 0; }
969forall( ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
970        return x + sum( rest );
971}
972sum( 10, 20, 30 );
973\end{cfa}
974Since @sum@\(_0\) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@.
975In order to call @sum@\(_1\), @10@ is matched with @x@, and the argument resolution moves on to the argument pack @rest@, which consumes the remainder of the argument list, and @Params@ is bound to @[20, 30]@.
976The process continues until @Params@ is bound to @[]@, requiring an assertion @int sum()@, which matches @sum@\(_0\) and terminates the recursion.
977Effectively, this algorithm traces as @sum(10, 20, 30)@ $\rightarrow$ @10 + sum(20, 30)@ $\rightarrow$ @10 + (20 + sum(30))@ $\rightarrow$ @10 + (20 + (30 + sum()))@ $\rightarrow$ @10 + (20 + (30 + 0))@.
978
979It is reasonable to take the @sum@ function a step further to enforce a minimum number of arguments.
980\begin{cfa}
981int sum( int x, int y ) { return x + y; }
982forall( ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
983        return sum( x + y, rest );
984}
985\end{cfa}
986One more step permits the summation of any sumable type with all arguments of the same type.
987\begin{cfa}
988trait sumable( otype T ) {
989        T ?+?( T, T );
990};
991forall( otype R | sumable( R ) ) R sum( R x, R y ) {
992        return x + y;
993}
994forall( otype R, ttype Params | sumable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
995        return sum( x + y, rest );
996}
997\end{cfa}
998Unlike C variadic functions, it is unnecessary to hard code the number and expected types.
999Furthermore, this code is extendable for any user-defined type with a @?+?@ operator.
1000Summing arbitrary heterogeneous lists is possible with similar code by adding the appropriate type variables and addition operators.
1001
1002It is also possible to write a type-safe variadic print function to replace @printf@:
1003\begin{cfa}
1004struct S { int x, y; };
1005forall( otype T, ttype Params | { void print(T); void print(Params); } ) void print(T arg, Params rest) {
1006        print(arg);  print(rest);
1007}
1008void print( const char * x ) { printf( "%s", x ); }
1009void print( int x ) { printf( "%d", x ); }
1010void print( S s ) { print( "{ ", s.x, ",", s.y, " }" ); }
1011print( "s = ", (S){ 1, 2 }, "\n" );
1012\end{cfa}
1013This example showcases a variadic-template-like decomposition of the provided argument list.
1014The individual @print@ functions allow printing a single element of a type.
1015The polymorphic @print@ allows printing any list of types, where each individual type has a @print@ function.
1016The individual print functions can be used to build up more complicated @print@ functions, such as @S@, which cannot be done with @printf@ in C.
1017This mechanism is used to seamlessly print tuples in the \CFA I/O library (see Section~\ref{s:IOLibrary}).
1018
1019Finally, it is possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
1020For example, it is possible to write @new@ as a library function.
1021\begin{cfa}
1022forall( otype R, otype S ) void ?{}( pair(R, S) *, R, S );
1023forall( dtype T, ttype Params | sized(T) | { void ?{}( T *, Params ); } ) T * new( Params p ) {
1024        return ((T *)malloc()){ p };                    $\C{// construct into result of malloc}$
1025}
1026pair( int, char ) * x = new( 42, '!' );
1027\end{cfa}
1028The @new@ function provides the combination of type-safe @malloc@ with a \CFA constructor call, making it impossible to forget constructing dynamically allocated objects.
1029This function provides the type safety of @new@ in \CC, without the need to specify the allocated type again, due to return-type inference.
1030
1031
1032\subsection{Implementation}
1033
1034Tuples are implemented in the \CFA translator via a transformation into \newterm{generic types}.
1035For each $N$, the first time an $N$-tuple is seen in a scope, a generic type with $N$ type parameters is generated.
1036For example, the following
1037\begin{cfa}
1038[int, int] f() {
1039        [double, double] x;
1040        [int, double, int] y;
1041}
1042\end{cfa}
1043is transformed into
1044\begin{cfa}
1045forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 {
1046        T0 member_0;  T1 member_1;                                      $\C{// generated before the first 2-tuple}$
1047};
1048_tuple2(int, int) f() {
1049        _tuple2(double, double) x;
1050        forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2) ) struct _tuple3 {
1051                T0 member_0;  T1 member_1;  T2 member_2;        $\C{// generated before the first 3-tuple}$
1052        };
1053        _tuple3(int, double, int) y;
1054}
1055\end{cfa}
1056Tuple expressions are then converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char,@ @double)){ 5, 'x', 1.24 }@.
1057
1058\begin{comment}
1059Since tuples are essentially structures, tuple indexing expressions are just member accesses:
1060\begin{cfa}
1061void f(int, [double, char]);
1062[int, double] x;
1063
1064x.0+x.1;
1065printf("%d %g\n", x);
1066f(x, 'z');
1067\end{cfa}
1068Is transformed into:
1069\begin{cfa}
1070void f(int, _tuple2(double, char));
1071_tuple2(int, double) x;
1072
1073x.member_0+x.member_1;
1074printf("%d %g\n", x.member_0, x.member_1);
1075f(x.member_0, (_tuple2){ x.member_1, 'z' });
1076\end{cfa}
1077Note that due to flattening, @x@ used in the argument position is converted into the list of its members.
1078In the call to @f@, the second and third argument components are structured into a tuple argument.
1079Similarly, tuple member expressions are recursively expanded into a list of member access expressions.
1080
1081Expressions that may contain side effects are made into \newterm{unique expressions} before being expanded by the flattening conversion.
1082Each unique expression is assigned an identifier and is guaranteed to be executed exactly once:
1083\begin{cfa}
1084void g(int, double);
1085[int, double] h();
1086g(h());
1087\end{cfa}
1088Internally, this expression is converted to two variables and an expression:
1089\begin{cfa}
1090void g(int, double);
1091[int, double] h();
1092
1093_Bool _unq0_finished_ = 0;
1094[int, double] _unq0;
1095g(
1096        (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).0,
1097        (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).1,
1098);
1099\end{cfa}
1100Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order.
1101The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is set to true.
1102Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression.
1103Tuple member expressions also take advantage of unique expressions in the case of possible impurity.
1104
1105Currently, the \CFA translator has a very broad, imprecise definition of impurity, where any function call is assumed to be impure.
1106This notion could be made more precise for certain intrinsic, auto-generated, and builtin functions, and could analyze function bodies when they are available to recursively detect impurity, to eliminate some unique expressions.
1107
1108The various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions.
1109A variable is generated to store the value produced by a statement expression, since its members may need to be constructed with a nontrivial constructor and it may need to be referred to multiple time, \eg in a unique expression.
1110The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language.
1111However, there are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this restriction is not new.
1112\end{comment}
1113
1114
1115\section{Control Structures}
1116
1117\CFA identifies inconsistent, problematic, and missing control structures in C, as well as extends, modifies, and adds control structures to increase functionality and safety.
1118
1119
1120\subsection{\texorpdfstring{\protect\lstinline@if@ statement}{if statement}}
1121
1122The @if@ expression allows declarations, similar to the @for@ declaration expression.
1123\begin{cfa}
1124if ( int x = f() ) ...                                          $\C{// x != 0}$
1125if ( int x = f(), y = g() ) ...                         $\C{// x != 0 \&\& y != 0}$
1126if ( int x = f(), y = g(); `x < y` ) ...        $\C{// relational expression}$
1127\end{cfa}
1128Unless a relational expression is specified, each variable is compared not equal to 0, which is the standard semantics for the @if@ expression, and the results are combined using the logical @&&@ operator.\footnote{\CC only provides a single declaration always compared not equal to 0.}
1129The scope of the declaration(s) is local to the @if@ statement but exists within both the ``then'' and ``else'' clauses.
1130
1131
1132\subsection{\texorpdfstring{\protect\lstinline@switch@ statement}{switch statement}}
1133
1134There are a number of deficiencies with the C @switch@ statements: enumerating @case@ lists, placement of @case@ clauses, scope of the switch body, and fall through between case clauses.
1135
1136C has no shorthand for specifying a list of case values, whether the list is noncontiguous or contiguous\footnote{C provides this mechanism via fall through.}.
1137\CFA provides a shorthand for a noncontiguous list:
1138\begin{cquote}
1139\lstDeleteShortInline@%
1140\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
1141\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
1142\begin{cfa}
1143case 2, 10, 34, 42:
1144\end{cfa}
1145&
1146\begin{cfa}
1147case 2: case 10: case 34: case 42:
1148\end{cfa}
1149\end{tabular}
1150\lstMakeShortInline@%
1151\end{cquote}
1152for a contiguous list:\footnote{gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, as a space is required after a number;
1153otherwise, the first period is a decimal point.}
1154\begin{cquote}
1155\lstDeleteShortInline@%
1156\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
1157\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
1158\begin{cfa}
1159case 2~42:
1160\end{cfa}
1161&
1162\begin{cfa}
1163case 2: case 3: ... case 41: case 42:
1164\end{cfa}
1165\end{tabular}
1166\lstMakeShortInline@%
1167\end{cquote}
1168and a combination:
1169\begin{cfa}
1170case -12~-4, -1~5, 14~21, 34~42:
1171\end{cfa}
1172
1173C allows placement of @case@ clauses \emph{within} statements nested in the @switch@ body (called Duff's device~\cite{Duff83});
1174\begin{cfa}
1175switch ( i ) {
1176  case 0:
1177        for ( int i = 0; i < 10; i += 1 ) {
1178                ...
1179  `case 1:`             // no initialization of loop index
1180                ...
1181        }
1182}
1183\end{cfa}
1184\CFA precludes this form of transfer \emph{into} a control structure because it causes an undefined behavior, especially with respect to missed initialization, and provides very limited functionality.
1185
1186C allows placement of declaration within the @switch@ body and unreachable code at the start, resulting in an undefined behavior.
1187\begin{cfa}
1188switch ( x ) {
1189        `int y = 1;`                                                    $\C{// unreachable initialization}$
1190        `x = 7;`                                                                $\C{// unreachable code without label/branch}$
1191  case 0:
1192        ...
1193        `int z = 0;`                                                    $\C{// unreachable initialization, cannot appear after case}$
1194        z = 2;
1195  case 1:
1196        `x = z;`                                                                $\C{// without fall through, z is undefined}$
1197}
1198\end{cfa}
1199\CFA allows the declaration of local variables, \eg @y@, at the start of the @switch@ with scope across the entire @switch@ body, \ie all @case@ clauses.
1200\CFA disallows the declaration of local variable, \eg @z@, directly within the @switch@ body, because a declaration cannot occur immediately after a @case@ since a label can only be attached to a statement, and the use of @z@ is undefined in @case 1@ as neither storage allocation nor initialization may have occurred.
1201
1202C @switch@ provides multiple entry points into the statement body, but once an entry point is selected, control continues across \emph{all} @case@ clauses until the end of the @switch@ body, called \newterm{fall through};
1203@case@ clauses are made disjoint by the @break@
1204\newpage
1205\noindent
1206statement.
1207While fall through \emph{is} a useful form of control flow, it does not match well with programmer intuition, resulting in errors from missing @break@ statements.
1208For backward compatibility, \CFA provides a \emph{new} control structure, \ie @choose@, which mimics @switch@, but reverses the meaning of fall through (see Figure~\ref{f:ChooseSwitchStatements}), similar to Go.
1209
1210\begin{figure}
1211\centering
1212\fontsize{9bp}{11bp}\selectfont
1213\lstDeleteShortInline@%
1214\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
1215\multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
1216\begin{cfa}
1217`choose` ( day ) {
1218  case Mon~Thu:  // program
1219
1220  case Fri:    // program
1221        wallet += pay;
1222        `fallthrough;`
1223  case Sat:   // party
1224        wallet -= party;
1225
1226  case Sun:  // rest
1227
1228  default:    // print error
1229}
1230\end{cfa}
1231&
1232\begin{cfa}
1233switch ( day ) {
1234  case Mon: case Tue: case Wed: case Thu:  // program
1235        `break;`
1236  case Fri:    // program
1237        wallet += pay;
1238
1239  case Sat:   // party
1240        wallet -= party;
1241        `break;`
1242  case Sun:  // rest
1243        `break;`
1244  default:    // print error
1245}
1246\end{cfa}
1247\end{tabular}
1248\lstMakeShortInline@%
1249\caption{\lstinline|choose| versus \lstinline|switch| statements}
1250\label{f:ChooseSwitchStatements}
1251\vspace*{-11pt}
1252\end{figure}
1253
1254Finally, Figure~\ref{f:FallthroughStatement} shows @fallthrough@ may appear in contexts other than terminating a @case@ clause and have an explicit transfer label allowing separate cases but common final code for a set of cases.
1255The target label must be below the @fallthrough@ and may not be nested in a control structure, \ie @fallthrough@ cannot form a loop, and the target label must be at the same or higher level as the containing @case@ clause and located at the same level as a @case@ clause;
1256the target label may be case @default@, but only associated with the current @switch@/@choose@ statement.
1257
1258\begin{figure}
1259\centering
1260\fontsize{9bp}{11bp}\selectfont
1261\lstDeleteShortInline@%
1262\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
1263\multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{non-terminator}}       & \multicolumn{1}{c@{}}{\textbf{target label}}  \\
1264\begin{cfa}
1265choose ( ... ) {
1266  case 3:
1267        if ( ... ) {
1268                ... `fallthrough;`  // goto case 4
1269        } else {
1270                ...
1271        }
1272        // implicit break
1273  case 4:
1274\end{cfa}
1275&
1276\begin{cfa}
1277choose ( ... ) {
1278  case 3:
1279        ... `fallthrough common;`
1280  case 4:
1281        ... `fallthrough common;`
1282  `common`: // below fallthrough at same level as case clauses
1283        ...      // common code for cases 3 and 4
1284        // implicit break
1285  case 4:
1286\end{cfa}
1287\end{tabular}
1288\lstMakeShortInline@%
1289\caption{\lstinline|fallthrough| statement}
1290\label{f:FallthroughStatement}
1291\vspace*{-11pt}
1292\end{figure}
1293
1294
1295\vspace*{-8pt}
1296\subsection{\texorpdfstring{Labeled \protect\lstinline@continue@ / \protect\lstinline@break@}{Labeled continue / break}}
1297
1298While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
1299Unfortunately, this restriction forces programmers to use @goto@ to achieve the equivalent control flow for more than one level of nesting.
1300To prevent having to switch to the @goto@, \CFA extends @continue@ and @break@ with a target label to support static multilevel exit~\cite{Buhr85}, as in Java.
1301For both @continue@ and @break@, the target label must be directly associated with a @for@, @while@ or @do@ statement;
1302for @break@, the target label can also be associated with a @switch@, @if@ or compound (@{}@) statement.
1303Figure~\ref{f:MultiLevelExit} shows @continue@ and @break@ indicating the specific control structure and the corresponding C program using only @goto@ and labels.
1304The innermost loop has seven exit points, which cause a continuation or termination of one or more of the seven nested control structures.
1305
1306\begin{figure}
1307\fontsize{9bp}{11bp}\selectfont
1308\lstDeleteShortInline@%
1309\begin{tabular}{@{\hspace{\parindentlnth}}l|@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
1310\multicolumn{1}{@{\hspace{\parindentlnth}}c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}}  & \multicolumn{1}{@{\hspace{\parindentlnth}}c@{}}{\textbf{C}}   \\
1311\begin{cfa}
1312`LC:` {
1313        ... $declarations$ ...
1314        `LS:` switch ( ... ) {
1315          case 3:
1316                `LIF:` if ( ... ) {
1317                        `LF:` for ( ... ) {
1318                                ... break `LC`; ...
1319                                ... break `LS`; ...
1320                                ... break `LIF`; ...
1321                                ... continue `LF;` ...
1322                                ... break `LF`; ...
1323                        } // for
1324                } else {
1325                        ... break `LIF`; ...
1326                } // if
1327        } // switch
1328} // compound
1329\end{cfa}
1330&
1331\begin{cfa}
1332{
1333        ... $declarations$ ...
1334        switch ( ... ) {
1335          case 3:
1336                if ( ... ) {
1337                        for ( ... ) {
1338                                ... goto `LC`; ...
1339                                ... goto `LS`; ...
1340                                ... goto `LIF`; ...
1341                                ... goto `LFC`; ...
1342                                ... goto `LFB`; ...
1343                          `LFC:` ; } `LFB:` ;
1344                } else {
1345                        ... goto `LIF`; ...
1346                } `LIF:` ;
1347        } `LS:` ;
1348} `LC:` ;
1349\end{cfa}
1350&
1351\begin{cfa}
1352
1353
1354
1355
1356
1357
1358
1359// terminate compound
1360// terminate switch
1361// terminate if
1362// continue loop
1363// terminate loop
1364
1365
1366
1367// terminate if
1368
1369\end{cfa}
1370\end{tabular}
1371\lstMakeShortInline@%
1372\caption{Multilevel exit}
1373\label{f:MultiLevelExit}
1374\vspace*{-5pt}
1375\end{figure}
1376
1377With respect to safety, both labeled @continue@ and @break@ are @goto@ restricted in the following ways.
1378\begin{list}{$\bullet$}{\topsep=4pt\itemsep=0pt\parsep=0pt}
1379\item
1380They cannot create a loop, which means only the looping constructs cause looping.
1381This restriction means all situations resulting in repeated execution are clearly delineated.
1382\item
1383They cannot branch into a control structure.
1384This restriction prevents missing declarations and/or initializations at the start of a control structure resulting in an undefined behavior.
1385\end{list}
1386The advantage of the labeled @continue@/@break@ is allowing static multilevel 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.
1387Furthermore, the location of the label at the \emph{beginning} of the target control structure informs the reader (eye candy) that complex control flow is
1388occurring in the body of the control structure.
1389With @goto@, the label is at the end of the control structure, which fails to convey this important clue early enough to the reader.
1390Finally, using an explicit target for the transfer instead of an implicit target allows new constructs to be added or removed without affecting the existing constructs.
1391Otherwise, the implicit targets of the current @continue@ and @break@, \ie the closest enclosing loop or @switch@, change as certain constructs are added or removed.
1392
1393
1394\vspace*{-5pt}
1395\subsection{Exception handling}
1396
1397The following framework for \CFA exception handling is in place, excluding some runtime type information and virtual functions.
1398\CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}.
1399Both mechanisms provide dynamic call to a handler using dynamic name lookup, where fix-up has dynamic return and recovery has static return from the handler.
1400\CFA restricts exception types to those defined by aggregate type @exception@.
1401The form of the raise dictates the set of handlers examined during propagation: \newterm{resumption propagation} (@resume@) only examines resumption handlers (@catchResume@); \newterm{terminating propagation} (@throw@) only examines termination handlers (@catch@).
1402If @resume@ or @throw@ has no exception type, it is a reresume/rethrow, which means that the current exception continues propagation.
1403If there is no current exception, the reresume/rethrow results in a runtime error.
1404
1405\begin{figure}
1406\fontsize{9bp}{11bp}\selectfont
1407\lstDeleteShortInline@%
1408\begin{cquote}
1409\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
1410\multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{Resumption}}   & \multicolumn{1}{c@{}}{\textbf{Termination}}   \\
1411\begin{cfa}
1412`exception R { int fix; };`
1413void f() {
1414        R r;
1415        ... `resume( r );` ...
1416        ... r.fix // control returns here after handler
1417}
1418`try` {
1419        ... f(); ...
1420} `catchResume( R r )` {
1421        ... r.fix = ...; // return correction to raise
1422} // dynamic return to _Resume
1423\end{cfa}
1424&
1425\begin{cfa}
1426`exception T {};`
1427void f() {
1428
1429        ... `throw( T{} );` ...
1430        // control does NOT return here after handler
1431}
1432`try` {
1433        ... f(); ...
1434} `catch( T t )` {
1435        ... // recover and continue
1436} // static return to next statement
1437\end{cfa}
1438\end{tabular}
1439\end{cquote}
1440\lstMakeShortInline@%
1441\caption{\CFA exception handling}
1442\label{f:CFAExceptionHandling}
1443\vspace*{-5pt}
1444\end{figure}
1445
1446The set of exception types in a list of catch clauses may include both a resumption and a termination handler.
1447\begin{cfa}
1448try {
1449        ... resume( `R{}` ); ...
1450} catchResume( `R` r ) { ... throw( R{} ); ... } $\C{\color{red}// H1}$
1451   catch( `R` r ) { ... }                                       $\C{\color{red}// H2}$
1452
1453\end{cfa}
1454The resumption propagation raises @R@ and the stack is not unwound;
1455the exception is caught by the @catchResume@ clause and handler H1 is invoked.
1456The termination propagation in handler H1 raises @R@ and the stack is unwound;
1457the exception is caught by the @catch@ clause and handler H2 is invoked.
1458The termination handler is available because the resumption propagation did not unwind the stack.
1459
1460An additional feature is conditional matching in a catch clause.
1461\begin{cfa}
1462try {
1463        ... write( `datafile`, ... ); ...               $\C{// may throw IOError}$
1464        ... write( `logfile`, ... ); ...
1465} catch ( IOError err; `err.file == datafile` ) { ... } $\C{// handle datafile error}$
1466   catch ( IOError err; `err.file == logfile` ) { ... } $\C{// handle logfile error}$
1467   catch ( IOError err ) { ... }                        $\C{// handler error from other files}$
1468\end{cfa}
1469Here, the throw inserts the failing file handle into the I/O exception.
1470Conditional catch cannot be trivially mimicked by other mechanisms because once an exception is caught, handler clauses in that @try@ statement are no longer eligible.
1471
1472The resumption raise can specify an alternate stack on which to raise an exception, called a \newterm{nonlocal raise}.
1473\begin{cfa}
1474resume( $\emph{exception-type}$, $\emph{alternate-stack}$ )
1475resume( $\emph{alternate-stack}$ )
1476\end{cfa}
1477These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task~\cite{Delisle18}.
1478Nonlocal raise is restricted to resumption to provide the exception handler the greatest flexibility because processing the exception does not unwind its stack, allowing it to continue after the handler returns.
1479
1480To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception propagation.
1481The constructs for controlling propagation of nonlocal exceptions are the @enable@ and @disable@ blocks.
1482\begin{cquote}
1483\lstDeleteShortInline@%
1484\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
1485\begin{cfa}
1486enable $\emph{exception-type-list}$ {
1487        // allow nonlocal raise
1488}
1489\end{cfa}
1490&
1491\begin{cfa}
1492disable $\emph{exception-type-list}$ {
1493        // disallow nonlocal raise
1494}
1495\end{cfa}
1496\end{tabular}
1497\lstMakeShortInline@%
1498\end{cquote}
1499The arguments for @enable@/@disable@ specify the exception types allowed to be propagated or postponed, respectively.
1500Specifying no exception type is shorthand for specifying all exception types.
1501Both @enable@ and @disable@ blocks can be nested;
1502turning propagation on/off on entry and on exit, the specified exception types are restored to their prior state.
1503Coroutines and tasks start with nonlocal exceptions disabled, allowing handlers to be put in place, before nonlocal exceptions are explicitly enabled.
1504\begin{cfa}
1505void main( mytask & t ) {                                       $\C{// thread starts here}$
1506        // nonlocal exceptions disabled
1507        try {                                                                   $\C{// establish handles for nonlocal exceptions}$
1508                enable {                                                        $\C{// allow nonlocal exception delivery}$
1509                        // task body
1510                }
1511        // appropriate catchResume/catch handlers
1512        }
1513}
1514\end{cfa}
1515
1516Finally, \CFA provides a Java-like  @finally@ clause after the catch clauses.
1517\begin{cfa}
1518try {
1519        ... f(); ...
1520// catchResume or catch clauses
1521} `finally` {
1522        // house keeping
1523}
1524\end{cfa}
1525The finally clause is always executed, \ie, if the try block ends normally or if an exception is raised.
1526If an exception is raised and caught, the handler is run before the finally clause.
1527Like a destructor (see Section~\ref{s:ConstructorsDestructors}), a finally clause can raise an exception but not if there is an exception being propagated.
1528Mimicking the @finally@ clause with mechanisms like Resource Aquisition Is Initialization (RAII) is nontrivial when there are multiple types and local accesses.
1529
1530
1531\subsection{\texorpdfstring{\protect\lstinline{with} statement}{with statement}}
1532\label{s:WithStatement}
1533
1534Heterogeneous data are often aggregated into a structure/union.
1535To reduce syntactic noise, \CFA provides a @with@ statement (see section~4.F in the Pascal User Manual and Report~\cite{Pascal}) to elide aggregate member qualification by opening a scope containing the member identifiers.
1536\begin{cquote}
1537\vspace*{-\baselineskip}%???
1538\lstDeleteShortInline@%
1539\begin{cfa}
1540struct S { char c; int i; double d; };
1541struct T { double m, n; };
1542// multiple aggregate parameters
1543\end{cfa}
1544\begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
1545\begin{cfa}
1546void f( S & s, T & t ) {
1547        `s.`c; `s.`i; `s.`d;
1548        `t.`m; `t.`n;
1549}
1550\end{cfa}
1551&
1552\begin{cfa}
1553void f( S & s, T & t ) `with ( s, t )` {
1554        c; i; d;                // no qualification
1555        m; n;
1556}
1557\end{cfa}
1558\end{tabular}
1559\lstMakeShortInline@%
1560\end{cquote}
1561Object-oriented programming languages only provide implicit qualification for the receiver.
1562
1563In detail, the @with@ statement has the form
1564\begin{cfa}
1565$\emph{with-statement}$:
1566        'with' '(' $\emph{expression-list}$ ')' $\emph{compound-statement}$
1567\end{cfa}
1568and may appear as the body of a function or nested within a function body.
1569Each expression in the expression list provides a type and object.
1570The type must be an aggregate type.
1571(Enumerations are already opened.)
1572The object is the implicit qualifier for the open structure members.
1573
1574All expressions in the expression list are open in parallel within the compound statement, which is different from Pascal, which nests the openings from left to right.
1575The difference between parallel and nesting occurs for members with the same name and type.
1576\begin{cfa}
1577struct S { int `i`; int j; double m; } s, w;    $\C{// member i has same type in structure types S and T}$
1578struct T { int `i`; int k; int m; } t, w;
1579with ( s, t ) {                                                         $\C{// open structure variables s and t in parallel}$
1580        j + k;                                                                  $\C{// unambiguous, s.j + t.k}$
1581        m = 5.0;                                                                $\C{// unambiguous, s.m = 5.0}$
1582        m = 1;                                                                  $\C{// unambiguous, t.m = 1}$
1583        int a = m;                                                              $\C{// unambiguous, a = t.m }$
1584        double b = m;                                                   $\C{// unambiguous, b = s.m}$
1585        int c = s.i + t.i;                                              $\C{// unambiguous, qualification}$
1586        (double)m;                                                              $\C{// unambiguous, cast s.m}$
1587}
1588\end{cfa}
1589For parallel semantics, both @s.i@ and @t.i@ are visible and, therefore, @i@ is ambiguous without qualification;
1590for nested semantics, @t.i@ hides @s.i@ and, therefore, @i@ implies @t.i@.
1591\CFA's ability to overload variables means members with the same name but different types are automatically disambiguated, eliminating most qualification when opening multiple aggregates.
1592Qualification or a cast is used to disambiguate.
1593
1594There is an interesting problem between parameters and the function body @with@.
1595\begin{cfa}
1596void ?{}( S & s, int i ) with ( s ) {           $\C{// constructor}$
1597        `s.i = i;`  j = 3;  m = 5.5;                    $\C{// initialize members}$
1598}
1599\end{cfa}
1600Here, the assignment @s.i = i@ means @s.i = s.i@, which is meaningless, and there is no mechanism to qualify the parameter @i@, making the assignment impossible using the function body @with@.
1601To solve this problem, parameters are treated like an initialized aggregate
1602\begin{cfa}
1603struct Params {
1604        S & s;
1605        int i;
1606} params;
1607\end{cfa}
1608\newpage
1609and implicitly opened \emph{after} a function body open, to give them higher priority
1610\begin{cfa}
1611void ?{}( S & s, int `i` ) with ( s ) `{` `with( $\emph{\color{red}params}$ )` {
1612        s.i = `i`; j = 3; m = 5.5;
1613} `}`
1614\end{cfa}
1615Finally, a cast may be used to disambiguate among overload variables in a @with@ expression
1616\begin{cfa}
1617with ( w ) { ... }                                                      $\C{// ambiguous, same name and no context}$
1618with ( (S)w ) { ... }                                           $\C{// unambiguous, cast}$
1619\end{cfa}
1620and @with@ expressions may be complex expressions with type reference (see Section~\ref{s:References}) to aggregate
1621\begin{cfa}
1622struct S { int i, j; } sv;
1623with ( sv ) {                                                           $\C{// implicit reference}$
1624        S & sr = sv;
1625        with ( sr ) {                                                   $\C{// explicit reference}$
1626                S * sp = &sv;
1627                with ( *sp ) {                                          $\C{// computed reference}$
1628                        i = 3; j = 4;                                   $\C{\color{red}// sp--{\textgreater}i, sp--{\textgreater}j}$
1629                }
1630                i = 2; j = 3;                                           $\C{\color{red}// sr.i, sr.j}$
1631        }
1632        i = 1; j = 2;                                                   $\C{\color{red}// sv.i, sv.j}$
1633}
1634\end{cfa}
1635
1636Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety.
1637
1638
1639\section{Declarations}
1640
1641Declarations in C have weaknesses and omissions.
1642\CFA attempts to correct and add to C declarations, while ensuring \CFA subjectively ``feels like'' C.
1643An important part of this subjective feel is maintaining C's syntax and procedural paradigm, as opposed to functional and object-oriented approaches in other systems languages such as \CC and Rust.
1644Maintaining the C approach means that C coding patterns remain not only useable but idiomatic in \CFA, reducing the mental burden of retraining C programmers and switching between C and \CFA development.
1645Nevertheless, some features from other approaches are undeniably convenient;
1646\CFA attempts to adapt these features to the C paradigm.
1647
1648
1649\subsection{Alternative declaration syntax}
1650
1651C declaration syntax is notoriously confusing and error prone.
1652For example, many C programmers are confused by a declaration as simple as the following.
1653\begin{cquote}
1654\lstDeleteShortInline@%
1655\begin{tabular}{@{}ll@{}}
1656\begin{cfa}
1657int * x[5]
1658\end{cfa}
1659&
1660\raisebox{-0.75\totalheight}{\input{Cdecl}}
1661\end{tabular}
1662\lstMakeShortInline@%
1663\end{cquote}
1664Is this an array of five pointers to integers or a pointer to an array of five integers?
1665If there is any doubt, it implies productivity and safety issues even for basic programs.
1666Another example of confusion results from the fact that a function name and its parameters are embedded within the return type, mimicking the way the return value is used at the function's call site.
1667For example, a function returning a pointer to an array of integers is defined and used in the following way.
1668\begin{cfa}
1669int `(*`f`())[`5`]` {...};                                      $\C{// definition}$
1670 ... `(*`f`())[`3`]` += 1;                                      $\C{// usage}$
1671\end{cfa}
1672Essentially, the return type is wrapped around the function name in successive layers (like an onion).
1673While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice.
1674
1675\newpage
1676\CFA provides its own type, variable, and function declarations, using a different syntax~\cite[pp.~856--859]{Buhr94a}.
1677The new declarations place qualifiers to the left of the base type, whereas C declarations place qualifiers to the right.
1678The qualifiers have the same meaning but are ordered left to right to specify a variable's type.
1679\begin{cquote}
1680\lstDeleteShortInline@%
1681\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
1682\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
1683\begin{cfa}
1684`[5] *` int x1;
1685`* [5]` int x2;
1686`[* [5] int]` f( int p );
1687\end{cfa}
1688&
1689\begin{cfa}
1690int `*` x1 `[5]`;
1691int `(*`x2`)[5]`;
1692`int (*`f( int p )`)[5]`;
1693\end{cfa}
1694&
1695\begin{cfa}
1696// array of 5 pointers to int
1697// pointer to array of 5 int
1698// function returning pointer to array of 5 int and taking int
1699\end{cfa}
1700\end{tabular}
1701\lstMakeShortInline@%
1702\end{cquote}
1703The only exception is bit-field specification, which always appears to the right of the base type.
1704% 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 function parameter.
1705However, unlike C, \CFA type declaration tokens are distributed across all variables in the declaration list.
1706For instance, variables @x@ and @y@ of type pointer to integer are defined in \CFA as
1707\begin{cquote}
1708\lstDeleteShortInline@%
1709\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
1710\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
1711\begin{cfa}
1712`*` int x, y;
1713int z;
1714\end{cfa}
1715&
1716\begin{cfa}
1717int `*`x, `*`y, z;
1718
1719\end{cfa}
1720\end{tabular}
1721\lstMakeShortInline@%
1722\end{cquote}
1723% The downside of the \CFA semantics is the need to separate regular and pointer declarations.
1724The separation of regular and pointer declarations by \CFA declarations enforces greater clarity with only slightly more syntax.
1725
1726\begin{comment}
1727Other examples are:
1728\begin{cquote}
1729\lstDeleteShortInline@%
1730\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
1731\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}}     \\
1732\begin{cfa}
1733[ 5 ] int z;
1734[ 5 ] * char w;
1735* [ 5 ] double v;
1736struct s {
1737        int f0:3;
1738        * int f1;
1739        [ 5 ] * int f2;
1740};
1741\end{cfa}
1742&
1743\begin{cfa}
1744int z[ 5 ];
1745char * w[ 5 ];
1746double (* v)[ 5 ];
1747struct s {
1748        int f0:3;
1749        int * f1;
1750        int * f2[ 5 ]
1751};
1752\end{cfa}
1753&
1754\begin{cfa}
1755// array of 5 integers
1756// array of 5 pointers to char
1757// pointer to array of 5 doubles
1758
1759// common bit-field syntax
1760
1761
1762
1763\end{cfa}
1764\end{tabular}
1765\lstMakeShortInline@%
1766\end{cquote}
1767\end{comment}
1768
1769All specifiers (@extern@, @static@, \etc) and qualifiers (@const@, @volatile@, \etc) are used in the normal way with the new declarations and also appear left to right.
1770\begin{cquote}
1771\lstDeleteShortInline@%
1772\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
1773\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{C}}     \\
1774\begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{12bp}\selectfont\sf]
1775extern const * const int x;
1776static const * [5] const int y;
1777\end{cfa}
1778&
1779\begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{12bp}\selectfont\sf]
1780int extern const * const x;
1781static const int (* const y)[5]
1782\end{cfa}
1783&
1784\begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{12bp}\selectfont\sf]
1785// external const pointer to const int
1786// internal const pointer to array of 5 const int
1787\end{cfa}
1788\end{tabular}
1789\lstMakeShortInline@%
1790\end{cquote}
1791Specifiers must appear at the start of a \CFA function declaration\footnote{\label{StorageClassSpecifier}
1792The placement of a storage-class specifier other than at the beginning of the declaration specifiers in a declaration is an obsolescent feature (see section~6.11.5(1) in ISO/IEC 9899~\cite{C11}).}.
1793
1794The new declaration syntax can be used in other contexts where types are required, \eg casts and the pseudo-function @sizeof@:
1795\begin{cquote}
1796\lstDeleteShortInline@%
1797\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
1798\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
1799\begin{cfa}
1800y = (* int)x;
1801i = sizeof([ 5 ] * int);
1802\end{cfa}
1803&
1804\begin{cfa}
1805y = (int *)x;
1806i = sizeof(int * [ 5 ]);
1807\end{cfa}
1808\end{tabular}
1809\lstMakeShortInline@%
1810\end{cquote}
1811
1812The syntax of the new function-prototype declaration follows directly from the new function-definition syntax;
1813also, parameter names are optional.
1814\begin{cfa}
1815[ int x ] f ( /* void */ );             $\C[2.5in]{// returning int with no parameters}$
1816[ int x ] f (...);                              $\C{// returning int with unknown parameters}$
1817[ * int ] g ( int y );                  $\C{// returning pointer to int with int parameter}$
1818[ void ] h ( int, char );               $\C{// returning no result with int and char parameters}$
1819[ * int, int ] j ( int );               $\C{// returning pointer to int and int with int parameter}$
1820\end{cfa}
1821This syntax allows a prototype declaration to be created by cutting and pasting the source text from the function-definition header (or vice versa).
1822Like C, it is possible to declare multiple function prototypes in a single declaration, where the return type is distributed across \emph{all} function names in the declaration list.
1823\begin{cquote}
1824\lstDeleteShortInline@%
1825\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
1826\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
1827\begin{cfa}
1828[double] foo(), foo( int ), foo( double ) {...}
1829\end{cfa}
1830&
1831\begin{cfa}
1832double foo1( void ), foo2( int ), foo3( double );
1833\end{cfa}
1834\end{tabular}
1835\lstMakeShortInline@%
1836\end{cquote}
1837Here, \CFA allows the last function in the list to define its body.
1838
1839The syntax for pointers to \CFA functions specifies the pointer name on the right.
1840\begin{cfa}
1841* [ int x ] () fp;                              $\C{// pointer to function returning int with no parameters}$
1842* [ * int ] ( int y ) gp;               $\C{// pointer to function returning pointer to int with int parameter}$
1843* [ ] ( int, char ) hp;                 $\C{// pointer to function returning no result with int and char parameters}$
1844* [ * int, int ] ( int ) jp;    $\C{// pointer to function returning pointer to int and int with int parameter}\CRT$
1845\end{cfa}
1846\newpage
1847\noindent
1848Note that the name of the function pointer is specified last, as for other variable declarations.
1849
1850Finally, new \CFA declarations may appear together with C declarations in the same program block but cannot be mixed within a specific declaration.
1851Therefore, a programmer has the option of either continuing to use traditional C declarations or taking advantage of the new style.
1852Clearly, both styles need to be supported for some time due to existing C-style header files, particularly for UNIX-like systems.
1853
1854
1855\subsection{References}
1856\label{s:References}
1857
1858All variables in C have an \newterm{address}, a \newterm{value}, and a \newterm{type};
1859at the position in the program's memory denoted by the address, there exists a sequence of bits (the value), with the length and semantic meaning of this bit sequence defined by the type.
1860The C type system does not always track the relationship between a value and its address;
1861a value that does not have a corresponding address is called an \newterm{rvalue} (for ``right-hand value''), whereas a value that does have an address is called an \newterm{lvalue} (for ``left-hand value'').
1862For example, in @int x; x = 42;@ the variable expression @x@ on the left-hand side of the assignment is an lvalue, whereas the constant expression @42@ on the right-hand side of the assignment is an rvalue.
1863Despite the nomenclature of ``left-hand'' and ``right-hand'', an expression's classification as an lvalue or an rvalue is entirely dependent on whether it has an address or not; in imperative programming, the address of a value is used for both reading and writing (mutating) a value, and as such, lvalues can be converted into rvalues and read from, but rvalues cannot be mutated because they lack a location to store the updated value.
1864
1865Within a lexical scope, lvalue expressions have an \newterm{address interpretation} for writing a value or a \newterm{value interpretation} to read a value.
1866For example, in @x = y@, @x@ has an address interpretation, whereas @y@ has a value interpretation.
1867While this duality of interpretation is useful, C lacks a direct mechanism to pass lvalues between contexts, instead relying on \newterm{pointer types} to serve a similar purpose.
1868In C, for any type @T@ there is a pointer type @T *@, the value of which is the address of a value of type @T@.
1869A pointer rvalue can be explicitly \newterm{dereferenced} to the pointed-to lvalue with the dereference operator @*?@, whereas the rvalue representing the address of an lvalue can be obtained with the address-of operator @&?@.
1870\begin{cfa}
1871int x = 1, y = 2, * p1, * p2, ** p3;
1872p1 = &x;                                                                        $\C{// p1 points to x}$
1873p2 = &y;                                                                        $\C{// p2 points to y}$
1874p3 = &p1;                                                                       $\C{// p3 points to p1}$
1875*p2 = ((*p1 + *p2) * (**p3 - *p1)) / (**p3 - 15);
1876\end{cfa}
1877Unfortunately, the dereference and address-of operators introduce a great deal of syntactic noise when dealing with pointed-to values rather than pointers, as well as the potential for subtle bugs because of pointer arithmetic.
1878For both brevity and clarity, it is desirable for the compiler to figure out how to elide the dereference operators in a complex expression such as the assignment to @*p2@ above.
1879However, since C defines a number of forms of \newterm{pointer arithmetic}, two similar expressions involving pointers to arithmetic types (\eg @*p1 + x@ and @p1 + x@) may each have well-defined but distinct semantics, introducing the possibility that a programmer may write one when they mean the other and precluding any simple algorithm for elision of dereference operators.
1880To solve these problems, \CFA introduces reference types @T &@;
1881a @T &@ has exactly the same value as a @T *@, but where the @T *@ takes the address interpretation by default, a @T &@ takes the value interpretation by default, as below.
1882\begin{cfa}
1883int x = 1, y = 2, & r1, & r2, && r3;
1884&r1 = &x;                                                                       $\C{// r1 points to x}$
1885&r2 = &y;                                                                       $\C{// r2 points to y}$
1886&&r3 = &&r1;                                                            $\C{// r3 points to r2}$
1887r2 = ((r1 + r2) * (r3 - r1)) / (r3 - 15);       $\C{// implicit dereferencing}$
1888\end{cfa}
1889Except for auto-dereferencing by the compiler, this reference example is exactly the same as the previous pointer example.
1890Hence, a reference behaves like a variable name---an lvalue expression that is interpreted as a value---but also has the type system track the address of that value.
1891One 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 the reference variable declaration;
1892thus, the previous example implicitly acts like the following.
1893\begin{cfa}
1894`*`r2 = ((`*`r1 + `*`r2) * (`**`r3 - `*`r1)) / (`**`r3 - 15);
1895\end{cfa}
1896References in \CFA are similar to those in \CC, with important improvements, which can be seen in the example above.
1897Firstly, \CFA does not forbid references to references.
1898This provides a much more orthogonal design for library \mbox{implementors}, obviating the need for workarounds such as @std::reference_wrapper@.
1899Secondly, \CFA references are rebindable, whereas \CC references have a fixed address.
1900Rebinding allows \CFA references to be default initialized (\eg to a null pointer\footnote{
1901While effort has been made into non-null reference checking in \CC and Java, the exercise seems moot for any nonmanaged languages (C/\CC), given that it only handles one of many different error situations, \eg using a pointer after its storage is deleted.}) and point to different addresses throughout their lifetime, like pointers.
1902Rebinding is accomplished by extending the existing syntax and semantics of the address-of operator in C.
1903
1904In C, the address of an lvalue is always an rvalue, as, in general, that address is not stored anywhere in memory and does not itself have an address.
1905In \CFA, the address of a @T &@ is an lvalue @T *@, as the address of the underlying @T@ is stored in the reference and can thus be mutated there.
1906The result of this rule is that any reference can be rebound using the existing pointer assignment semantics by assigning a compatible pointer into the address of the reference, \eg @&r1 = &x;@ above.
1907This rebinding occurs to an arbitrary depth of reference nesting;
1908loosely speaking, nested address-of operators produce a nested lvalue pointer up to the depth of the reference.
1909These explicit address-of operators can be thought of as ``cancelling out'' the implicit dereference operators, \eg @(&`*`)r1 = &x@ or @(&(&`*`)`*`)r3 = &(&`*`)r1@ or even @(&`*`)r2 = (&`*`)`*`r3@ for @&r2 = &r3@.
1910The precise rules are
1911\begin{itemize}
1912\item
1913If @R@ is an rvalue of type @T &@$_1\cdots$ @&@$_r$, where $r \ge 1$ references (@&@ symbols), than @&R@ has type @T `*`&@$_{\color{red}2}\cdots$ @&@$_{\color{red}r}$, \ie @T@ pointer with $r-1$ references (@&@ symbols).
1914\item
1915If @L@ is an lvalue of type @T &@$_1\cdots$ @&@$_l$, where $l \ge 0$ references (@&@ symbols), than @&L@ has type @T `*`&@$_{\color{red}1}\cdots$ @&@$_{\color{red}l}$, \ie @T@ pointer with $l$ references (@&@ symbols).
1916\end{itemize}
1917Since pointers and references share the same internal representation, code using either is equally performant;
1918in fact, the \CFA compiler converts references into pointers internally, and the choice between them is made solely on convenience, \eg many pointer or value accesses.
1919
1920By analogy to pointers, \CFA references also allow cv-qualifiers such as @const@:
1921\begin{cfa}
1922const int cx = 5;                                                       $\C{// cannot change cx}$
1923const int & cr = cx;                                            $\C{// cannot change cr's referred value}$
1924&cr = &cx;                                                                      $\C{// rebinding cr allowed}$
1925cr = 7;                                                                         $\C{// ERROR, cannot change cr}$
1926int & const rc = x;                                                     $\C{// must be initialized, like in \CC}$
1927&rc = &x;                                                                       $\C{// ERROR, cannot rebind rc}$
1928rc = 7;                                                                         $\C{// x now equal to 7}$
1929\end{cfa}
1930Given that a reference is meant to represent a lvalue, \CFA provides some syntactic shortcuts when initializing references.
1931There are three initialization contexts in \CFA: declaration initialization, argument/parameter binding, and return/temporary binding.
1932In each of these contexts, the address-of operator on the target lvalue is elided.
1933The syntactic motivation is clearest when considering overloaded operator assignment, \eg @int ?+=?(int &, int)@; given @int x, y@, the expected call syntax is @x += y@, not @&x += y@.
1934
1935More generally, this initialization of references from lvalues rather than pointers is an instance of an ``lvalue-to-reference'' conversion rather than an elision of the address-of operator;
1936this conversion is used in any context in \CFA where an implicit conversion is allowed.
1937Similarly, use of the value pointed to by a reference in an rvalue context can be thought of as a ``reference-to-rvalue'' conversion, and \CFA also includes a qualifier-adding ``reference-to-reference'' conversion, analogous to the @T *@ to @const T *@ conversion in standard C.
1938The final reference conversion included in \CFA is an ``rvalue-to-reference'' conversion, implemented by means of an implicit temporary.
1939When an rvalue is used to initialize a reference, it is instead used to initialize a hidden temporary value with the same lexical scope as the reference, and the reference is initialized to the address of this temporary.
1940\begin{cfa}
1941struct S { double x, y; };
1942int x, y;
1943void f( int & i, int & j, S & s, int v[] );
1944f( 3, x + y, (S){ 1.0, 7.0 }, (int [3]){ 1, 2, 3 } ); $\C{// pass rvalue to lvalue \(\Rightarrow\) implicit temporary}$
1945\end{cfa}
1946This allows complex values to be succinctly and efficiently passed to functions, without the syntactic overhead of the explicit definition of a temporary variable or the runtime cost of pass-by-value.
1947\CC allows a similar binding, but only for @const@ references; the more general semantics of \CFA are an attempt to avoid the \newterm{const poisoning} problem~\cite{Taylor10}, in which the addition of a @const@ qualifier to one reference requires a cascading chain of added qualifiers.
1948
1949
1950\subsection{Type nesting}
1951
1952Nested types provide a mechanism to organize associated types and refactor a subset of members into a named aggregate (\eg subaggregates @name@, @address@, @department@, within aggregate @employe@).
1953Java nested types are dynamic (apply to objects), \CC are static (apply to the \lstinline[language=C++]@class@), and C hoists (refactors) nested types into the enclosing scope, which means there is no need for type qualification.
1954Since \CFA in not object oriented, adopting dynamic scoping does not make sense;
1955instead, \CFA adopts \CC static nesting, using the member-selection operator ``@.@'' for type qualification, as does Java, rather than the \CC type-selection operator ``@::@'' (see Figure~\ref{f:TypeNestingQualification}).
1956In the C left example, types @C@, @U@ and @T@ are implicitly hoisted outside of type @S@ into the containing block scope.
1957In the \CFA right example, the types are not hoisted and accessible.
1958
1959\begin{figure}
1960\centering
1961\fontsize{9bp}{11bp}\selectfont\sf
1962\lstDeleteShortInline@%
1963\begin{tabular}{@{}l@{\hspace{3em}}l|l@{}}
1964\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C Type Nesting}}      & \multicolumn{1}{c|}{\textbf{C Implicit Hoisting}}     & \multicolumn{1}{c}{\textbf{\CFA}}     \\
1965\begin{cfa}
1966struct S {
1967        enum C { R, G, B };
1968        struct T {
1969                union U { int i, j; };
1970                enum C c;
1971                short int i, j;
1972        };
1973        struct T t;
1974} s;
1975
1976int rtn() {
1977        s.t.c = R;
1978        struct T t = { R, 1, 2 };
1979        enum C c;
1980        union U u;
1981}
1982\end{cfa}
1983&
1984\begin{cfa}
1985enum C { R, G, B };
1986union U { int i, j; };
1987struct T {
1988        enum C c;
1989        short int i, j;
1990};
1991struct S {
1992        struct T t;
1993} s;
1994       
1995
1996
1997
1998
1999
2000
2001\end{cfa}
2002&
2003\begin{cfa}
2004struct S {
2005        enum C { R, G, B };
2006        struct T {
2007                union U { int i, j; };
2008                enum C c;
2009                short int i, j;
2010        };
2011        struct T t;
2012} s;
2013
2014int rtn() {
2015        s.t.c = `S.`R;  // type qualification
2016        struct `S.`T t = { `S.`R, 1, 2 };
2017        enum `S.`C c;
2018        union `S.T.`U u;
2019}
2020\end{cfa}
2021\end{tabular}
2022\lstMakeShortInline@%
2023\caption{Type nesting / qualification}
2024\label{f:TypeNestingQualification}
2025\vspace*{-8pt}
2026\end{figure}
2027
2028
2029\vspace*{-8pt}
2030\subsection{Constructors and destructors}
2031\label{s:ConstructorsDestructors}
2032
2033One of the strengths (and weaknesses) of C is memory-management control, allowing resource release to be precisely specified versus unknown release with garbage-collected memory management.
2034However, this manual approach is verbose, and it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory.
2035\CC addresses these issues using RAII, implemented by means of \newterm{constructor} and \newterm{destructor} functions;
2036\CFA adopts constructors and destructors (and @finally@) to facilitate RAII.
2037While constructors and destructors are a common feature of object-oriented programming languages, they are an independent capability allowing \CFA to adopt them while retaining a procedural paradigm.
2038Specifically, \CFA constructors and destructors are denoted by name and first parameter type versus name and nesting in an aggregate type.
2039Constructor calls seamlessly integrate with existing C initialization syntax, providing a simple and familiar syntax to C programmers and allowing constructor calls to be inserted into legacy C code with minimal code changes.
2040
2041In \CFA, a constructor is named @?{}@ and a destructor is named @^?{}@\footnote{%
2042The symbol \lstinline+^+ is used for the destructor name because it was the last binary operator that could be used in a unary context.}.
2043The name @{}@ comes from the syntax for the initializer: @struct S { int i, j; } s = `{` 2, 3 `}`@.
2044Like other \CFA operators, these names represent the syntax used to explicitly call the constructor or destructor, \eg @s{...}@ or @^s{...}@.
2045The constructor and destructor have return type @void@, and the first parameter is a reference to the object type to be constructed or destructed.
2046While the first parameter is informally called the @this@ parameter, as in object-oriented languages, any variable name may be used.
2047Both constructors and destructors allow additional parameters after the @this@ parameter for specifying values for initialization/deinitialization\footnote{
2048Destruction parameters are useful for specifying storage-management actions, such as deinitialize but not deallocate.}.
2049\begin{cfa}[basicstyle=\linespread{0.9}\fontsize{9bp}{11bp}\selectfont\sf]
2050struct VLA { int size, * data; };                       $\C{// variable length array of integers}$
2051void ?{}( VLA & vla ) with ( vla ) { size = 10;  data = alloc( size ); }  $\C{// default constructor}$
2052void ^?{}( VLA & vla ) with ( vla ) { free( data ); } $\C{// destructor}$
2053{
2054        VLA x;                                                                  $\C{// implicit:\ \ x\{\};}$
2055}                                                                                       $\C{// implicit:\ \textasciicircum{}x\{\};}$
2056\end{cfa}
2057@VLA@ is a \newterm{managed type}\footnote{
2058A managed type affects the runtime environment versus a self-contained type.}: a type requiring a nontrivial constructor or destructor, or with a member of a managed type.
2059A managed type is implicitly constructed at allocation and destructed at deallocation to ensure proper interaction with runtime resources, in this case, the @data@ array in the heap.
2060For details of the code-generation placement of implicit constructor and destructor calls among complex executable statements, see section~2.2 in the work of Schlintz~\cite{Schluntz17}.
2061
2062\CFA also provides syntax for \newterm{initialization} and \newterm{copy}.
2063\begin{cfa}
2064void ?{}( VLA & vla, int size, char fill = '\0' ) {  $\C{// initialization}$
2065        vla.[ size, data ] = [ size, alloc( size, fill ) ];
2066}
2067void ?{}( VLA & vla, VLA other ) {                      $\C{// copy, shallow}$
2068        vla = other;
2069}
2070\end{cfa}
2071(Note that the example is purposely simplified using shallow-copy semantics.)
2072An initialization constructor call has the same syntax as a C initializer, except that the initialization values are passed as arguments to a matching constructor (number and type of parameters).
2073\begin{cfa}
2074VLA va = `{` 20, 0 `}`,  * arr = alloc()`{` 5, 0 `}`;
2075\end{cfa}
2076Note the use of a \newterm{constructor expression} to initialize the storage from the dynamic storage allocation.
2077Like \CC, the copy constructor has two parameters, the second of which is a value parameter with the same type as the first parameter;
2078appropriate care is taken to not recursively call the copy constructor when initializing the second parameter.
2079
2080\CFA constructors may be explicitly called, like Java, and destructors may be explicitly called, like \CC.
2081Explicit calls to constructors double as a \CC-style \emph{placement syntax}, useful for construction of members in user-defined constructors and reuse of existing storage allocations.
2082Like the other operators in \CFA, there is a concise syntax for constructor/destructor function calls.
2083\begin{cfa}
2084{
2085        VLA  x,            y = { 20, 0x01 },     z = y; $\C{// z points to y}$
2086        //    x{};         y{ 20, 0x01 };          z{ z, y };
2087        ^x{};                                                                   $\C{// deallocate x}$
2088        x{};                                                                    $\C{// reallocate x}$
2089        z{ 5, 0xff };                                                   $\C{// reallocate z, not pointing to y}$
2090        ^y{};                                                                   $\C{// deallocate y}$
2091        y{ x };                                                                 $\C{// reallocate y, points to x}$
2092        x{};                                                                    $\C{// reallocate x, not pointing to y}$
2093}       //  ^z{};  ^y{};  ^x{};
2094\end{cfa}
2095
2096To provide a uniform type interface for @otype@ polymorphism, the \CFA compiler automatically generates a default constructor, copy constructor, assignment operator, and destructor for all types.
2097These default functions can be overridden by user-generated versions.
2098For compatibility with the standard behavior of C, the default constructor and destructor for all basic, pointer, and reference types do nothing, whereas the copy constructor and assignment operator are bitwise copies;
2099if default zero initialization is desired, the default constructors can be overridden.
2100For user-generated types, the four functions are also automatically generated.
2101@enum@ types are handled the same as their underlying integral type, and unions are also bitwise copied and no-op initialized and destructed.
2102For compatibility with C, a copy constructor from the first union member type is also defined.
2103For @struct@ types, each of the four functions is implicitly defined to call their corresponding functions on each member of the struct.
2104To better simulate the behavior of C initializers, a set of \newterm{member constructors} is also generated for structures.
2105A constructor is generated for each nonempty prefix of a structure's member list to copy-construct the members passed as parameters and default-construct the remaining members.
2106To allow users to limit the set of constructors available for a type, when a user declares any constructor or destructor, the corresponding generated function and all member constructors for that type are hidden from expression resolution;
2107similarly, the generated default constructor is hidden upon the declaration of any constructor.
2108These semantics closely mirror the rule for implicit declaration of constructors in \CC\cite[p.~186]{ANSI98:C++}.
2109
2110In some circumstance, programmers may not wish to have implicit constructor and destructor generation and calls.
2111In these cases, \CFA provides the initialization syntax \lstinline|S x `@=` {}|, and the object becomes unmanaged;
2112hence, implicit \mbox{constructor} and destructor calls are not generated.
2113Any C initializer can be the right-hand side of an \lstinline|@=| initializer, \eg \lstinline|VLA a @= { 0, 0x0 }|, with the usual C initialization semantics.
2114The same syntax can be used in a compound literal, \eg \lstinline|a = (VLA)`@`{ 0, 0x0 }|, to create a C-style literal.
2115The point of \lstinline|@=| is to provide a migration path from legacy C code to \CFA, by providing a mechanism to incrementally convert into implicit initialization.
2116
2117
2118% \subsection{Default Parameters}
2119
2120
2121\section{Literals}
2122
2123C already includes limited polymorphism for literals---@0@ can be either an integer or a pointer literal, depending on context, whereas the syntactic forms of literals of the various integer and float types are very similar, differing from each other only in suffix.
2124In keeping with the general \CFA approach of adding features while respecting the ``C style'' of doing things, C's polymorphic constants and typed literal syntax are extended to interoperate with user-defined types, while maintaining a backward-compatible semantics.
2125
2126A simple example is allowing the underscore, as in Ada, to separate prefixes, digits, and suffixes in all \CFA constants, \eg @0x`_`1.ffff`_`ffff`_`p`_`128`_`l@, where the underscore is also the standard separator in C identifiers.
2127\CC uses a single quote as a separator, but it is restricted among digits, precluding its use in the literal prefix or suffix, \eg @0x1.ffff@@`'@@ffffp128l@, and causes problems with most integrated development environments (IDEs), which must be extended to deal with this alternate use of the single quote.
2128
2129
2130\begin{comment}
2131\subsection{Integral Suffixes}
2132
2133New integral suffixes @hh@ (half of half of @int@) for @char@, @h@ (half of @int@) for @short@, and @z@ for @size_t@, and length suffixes for 8, 16, 32, 64, and 128 bit integers.
2134%Additional integral suffixes are added to cover all the integral types and lengths.
2135\begin{cquote}
2136\lstDeleteShortInline@%
2137\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
2138\begin{cfa}
213920_`hh`     // signed char
214021_`hh`u   // unsigned char
214122_`h`       // signed short int
214223_u`h`     // unsigned short int
214324`z`         // size_t
2144\end{cfa}
2145&
2146\begin{cfa}
214720_`L8`      // int8_t
214821_u`l8`     // uint8_t
214922_`l16`     // int16_t
215023_u`l16`   // uint16_t
215124_`l32`     // int32_t
2152\end{cfa}
2153&
2154\begin{cfa}
215525_u`l32`      // uint32_t
215626_`l64`        // int64_t
215727_`l64`u      // uint64_t
215826_`L128`     // int128
215927_`L128`u   // unsigned int128
2160\end{cfa}
2161\end{tabular}
2162\lstMakeShortInline@%
2163\end{cquote}
2164\end{comment}
2165
2166
2167\subsection{0/1}
2168
2169In C, @0@ has the special property that it is the only ``false'' value;
2170by the standard, any value that compares equal to @0@ is false, whereas any value that compares unequal to @0@ is true.
2171As such, an expression @x@ in any Boolean context (such as the condition of an @if@ or @while@ statement, or the arguments to @&&@, @||@, or @?:@\,) can be rewritten as @x != 0@ without changing its semantics.
2172Operator overloading in \CFA provides a natural means to implement this truth-value comparison for arbitrary types, but the C type system is not precise enough to distinguish an equality comparison with @0@ from an equality comparison with an arbitrary integer or pointer.
2173To provide this precision, \CFA introduces a new type @zero_t@ as the type of literal @0@ (somewhat analagous to @nullptr_t@ and @nullptr@ in \CCeleven);
2174@zero_t@ can only take the value @0@, but has implicit conversions to the integer and pointer types so that C code involving @0@ continues to work.
2175With this addition, \CFA rewrites @if (x)@ and similar expressions to @if ( (x) != 0 )@ or the appropriate analogue, and any type @T@ is ``truthy'' by defining an operator overload @int ?!=?( T, zero_t )@.
2176\CC makes types truthy by adding a conversion to @bool@;
2177prior to the addition of explicit cast operators in \CCeleven, this approach had the pitfall of making truthy types transitively convertible into any numeric type;
2178\CFA avoids this issue.
2179
2180Similarly, \CFA also has a special type for @1@, @one_t@;
2181like @zero_t@, @one_t@ has built-in implicit conversions to the various integral types so that @1@ maintains its expected semantics in legacy code for operations @++@ and @--@.
2182The addition of @one_t@ allows generic algorithms to handle the unit value uniformly for types where it is meaningful.
2183\TODO{Make this sentence true}
2184In particular, polymorphic functions in the \CFA prelude define @++x@ and @x++@ in terms of @x += 1@, allowing users to idiomatically define all forms of increment for a type @T@ by defining the single function @T & ?+=(T &, one_t)@;
2185analogous overloads for the decrement operators are present as well.
2186
2187
2188\subsection{User literals}
2189
2190For readability, it is useful to associate units to scale literals, \eg weight (stone, pound, kilogram) or time (seconds, minutes, hours).
2191The left of Figure~\ref{f:UserLiteral} shows the \CFA alternative call syntax (postfix: literal argument before function name), using the backquote, to convert basic literals into user literals.
2192The backquote is a small character, making the unit (function name) predominate.
2193For examples, the multiprecision integer type in Section~\ref{s:MultiPrecisionIntegers} has the following user literals.
2194{\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}}
2195\begin{cfa}
2196y = 9223372036854775807L|`mp| * 18446744073709551615UL|`mp|;
2197y = "12345678901234567890123456789"|`mp| + "12345678901234567890123456789"|`mp|;
2198\end{cfa}
2199Because \CFA uses a standard function, all types and literals are applicable, as well as overloading and conversions, where @?`@ denotes a postfix-function name and @`@  denotes a postfix-function call.
2200}%
2201\begin{cquote}
2202\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}}
2203\lstDeleteShortInline@%
2204\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
2205\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{postfix function}}     & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{constant}}      & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{variable/expression}}   & \multicolumn{1}{c@{}}{\textbf{postfix pointer}}       \\
2206\begin{cfa}
2207int |?`h|( int s );
2208int |?`h|( double s );
2209int |?`m|( char c );
2210int |?`m|( const char * s );
2211int |?`t|( int a, int b, int c );
2212\end{cfa}
2213&
2214\begin{cfa}
22150 |`h|;
22163.5|`h|;
2217'1'|`m|;
2218"123" "456"|`m|;
2219[1,2,3]|`t|;
2220\end{cfa}
2221&
2222\begin{cfa}
2223int i = 7;
2224i|`h|;
2225(i + 3)|`h|;
2226(i + 3.5)|`h|;
2227
2228\end{cfa}
2229&
2230\begin{cfa}
2231int (* |?`p|)( int i );
2232|?`p| = |?`h|;
22333|`p|;
2234i|`p|;
2235(i + 3)|`p|;
2236\end{cfa}
2237\end{tabular}
2238\lstMakeShortInline@%
2239\end{cquote}
2240
2241The right of Figure~\ref{f:UserLiteral} shows the equivalent \CC version using the underscore for the call syntax.
2242However, \CC restricts the types, \eg @unsigned long long int@ and @long double@ to represent integral and floating literals.
2243After which, user literals must match (no conversions);
2244hence, it is necessary to overload the unit with all appropriate types.
2245
2246\begin{figure}
2247\centering
2248\fontsize{9bp}{11bp}\selectfont
2249\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}}
2250\lstDeleteShortInline@%
2251\begin{tabular}{@{}l@{\hspace{1.25\parindentlnth}}l@{}}
2252\multicolumn{1}{@{}c@{\hspace{1.25\parindentlnth}}}{\textbf{\CFA}}      & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
2253\begin{cfa}
2254struct W {
2255        double stones;
2256};
2257void ?{}( W & w ) { w.stones = 0; }
2258void ?{}( W & w, double w ) { w.stones = w; }
2259W ?+?( W l, W r ) {
2260        return (W){ l.stones + r.stones };
2261}
2262W |?`st|(double w) { return (W){ w }; }
2263W |?`lb|(double w) { return (W){ w/14.0 }; }
2264W |?`kg|(double w) { return (W){ w*0.16 }; }
2265
2266
2267
2268int main() {
2269        W w, heavy = { 20 };
2270        w = 155|`lb|;
2271        w = 0b_1111|`st|;
2272        w = 0_233|`lb|;
2273        w = 0x_9b_u|`kg|;
2274        w = 5.5|`st| + 8|`kg| + 25.01|`lb| + heavy;
2275}
2276\end{cfa}
2277&
2278\begin{cfa}
2279struct W {
2280        double stones;
2281        W() { stones = 0.0; }
2282        W( double w ) { stones = w; }
2283};
2284W operator+( W l, W r ) {
2285        return W( l.stones + r.stones );
2286}
2287W |operator""_st|(unsigned long long int w) {return W(w); }
2288W |operator""_lb|(unsigned long long int w) {return W(w/14.0); }
2289W |operator""_kg|(unsigned long long int w) {return W(w*0.16); }
2290W |operator""_st|(long double w ) { return W( w ); }
2291W |operator""_lb|(long double w ) { return W( w / 14.0 ); }
2292W |operator""_kg|(long double w ) { return W( w * 0.16 ); }
2293int main() {
2294        W w, heavy = { 20 };
2295        w = 155|_lb|;
2296        // binary unsupported
2297        w = 0${\color{red}\LstBasicStyle{'}}$233|_lb|;          // quote separator
2298        w = 0x9b|_kg|;
2299        w = 5.5d|_st| + 8|_kg| + 25.01|_lb| + heavy;
2300}
2301\end{cfa}
2302\end{tabular}
2303\lstMakeShortInline@%
2304\caption{User literal}
2305\label{f:UserLiteral}
2306\end{figure}
2307
2308
2309\section{Libraries}
2310\label{sec:libraries}
2311
2312As stated in Section~\ref{sec:poly-fns}, \CFA inherits a large corpus of library code, where other programming languages must rewrite or provide fragile interlanguage communication with C.
2313\CFA has replacement libraries condensing hundreds of existing C names into tens of \CFA overloaded names, all without rewriting the actual computations.
2314In many cases, the interface is an inline wrapper providing overloading during compilation but of zero cost at runtime.
2315The following sections give a glimpse of the interface reduction to many C libraries.
2316In many cases, @signed@/@unsigned@ @char@, @short@, and @_Complex@ functions are available (but not shown) to ensure expression computations remain in a single type, as conversions can distort results.
2317
2318
2319\subsection{Limits}
2320
2321C library @limits.h@ provides lower and upper bound constants for the basic types.
2322\CFA name overloading is used to condense these typed constants.
2323\begin{cquote}
2324\lstDeleteShortInline@%
2325\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
2326\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}   & \multicolumn{1}{c@{}}{\textbf{Usage}} \\
2327\begin{cfa}
2328const short int `MIN` = -32768;
2329const int `MIN` = -2147483648;
2330const long int `MIN` = -9223372036854775808L;
2331\end{cfa}
2332&
2333\begin{cfa}
2334short int si = `MIN`;
2335int i = `MIN`;
2336long int li = `MIN`;
2337\end{cfa}
2338\end{tabular}
2339\lstMakeShortInline@%
2340\end{cquote}
2341The result is a significant reduction in names to access typed constants.
2342\begin{cquote}
2343\lstDeleteShortInline@%
2344\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
2345\multicolumn{1}{@{}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}  & \multicolumn{1}{c@{}}{\textbf{C}}     \\
2346\begin{cfa}
2347MIN
2348MAX
2349PI
2350E
2351\end{cfa}
2352&
2353\begin{cfa}
2354CHAR_MIN, SHRT_MIN, INT_MIN, LONG_MIN, LLONG_MIN, FLT_MIN, DBL_MIN, LDBL_MIN
2355UCHAR_MAX, SHRT_MAX, INT_MAX, LONG_MAX, LLONG_MAX, FLT_MAX, DBL_MAX, LDBL_MAX
2356M_PI, M_PIl
2357M_E, M_El
2358\end{cfa}
2359\end{tabular}
2360\lstMakeShortInline@%
2361\end{cquote}
2362
2363
2364\subsection{Math}
2365
2366C library @math.h@ provides many mathematical functions.
2367\CFA function overloading is used to condense these mathematical functions.
2368\begin{cquote}
2369\lstDeleteShortInline@%
2370\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
2371\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}   & \multicolumn{1}{c@{}}{\textbf{Usage}} \\
2372\begin{cfa}
2373float `log`( float x );
2374double `log`( double );
2375double _Complex `log`( double _Complex x );
2376\end{cfa}
2377&
2378\begin{cfa}
2379float f = `log`( 3.5 );
2380double d = `log`( 3.5 );
2381double _Complex dc = `log`( 3.5+0.5I );
2382\end{cfa}
2383\end{tabular}
2384\lstMakeShortInline@%
2385\end{cquote}
2386The result is a significant reduction in names to access math functions.
2387\begin{cquote}
2388\lstDeleteShortInline@%
2389\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
2390\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
2391\begin{cfa}
2392log
2393sqrt
2394sin
2395\end{cfa}
2396&
2397\begin{cfa}
2398logf, log, logl, clogf, clog, clogl
2399sqrtf, sqrt, sqrtl, csqrtf, csqrt, csqrtl
2400sinf, sin, sinl, csinf, csin, csinl
2401\end{cfa}
2402\end{tabular}
2403\lstMakeShortInline@%
2404\end{cquote}
2405While \Celeven has type-generic math (see section~7.25 of the ISO/IEC 9899\cite{C11}) in @tgmath.h@ to provide a similar mechanism, these macros are limited, matching a function name with a single set of floating type(s).
2406For example, it is impossible to overload @atan@ for both one and two arguments;
2407instead, the names @atan@ and @atan2@ are required (see Section~\ref{s:NameOverloading}).
2408The key observation is that only a restricted set of type-generic macros is provided for a limited set of function names, which do not generalize across the type system, as in \CFA.
2409
2410
2411\subsection{Standard}
2412
2413C library @stdlib.h@ provides many general functions.
2414\CFA function overloading is used to condense these utility functions.
2415\begin{cquote}
2416\lstDeleteShortInline@%
2417\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
2418\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{Definition}}   & \multicolumn{1}{c@{}}{\textbf{Usage}} \\
2419\begin{cfa}
2420unsigned int `abs`( int );
2421double `abs`( double );
2422double abs( double _Complex );
2423\end{cfa}
2424&
2425\begin{cfa}
2426unsigned int i = `abs`( -1 );
2427double d = `abs`( -1.5 );
2428double d = `abs`( -1.5+0.5I );
2429\end{cfa}
2430\end{tabular}
2431\lstMakeShortInline@%
2432\end{cquote}
2433The result is a significant reduction in names to access the utility functions.
2434\begin{cquote}
2435\lstDeleteShortInline@%
2436\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
2437\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
2438\begin{cfa}
2439abs
2440strto
2441random
2442\end{cfa}
2443&
2444\begin{cfa}
2445abs, labs, llabs, fabsf, fabs, fabsl, cabsf, cabs, cabsl
2446strtol, strtoul, strtoll, strtoull, strtof, strtod, strtold
2447srand48, mrand48, lrand48, drand48
2448\end{cfa}
2449\end{tabular}
2450\lstMakeShortInline@%
2451\end{cquote}
2452In addition, there are polymorphic functions, like @min@ and @max@, that work on any type with operator @?<?@ or @?>?@.
2453
2454The following shows one example where \CFA \emph{extends} an existing standard C interface to reduce complexity and provide safety.
2455C/\Celeven provide a number of complex and overlapping storage-management operations to support the following capabilities.
2456\begin{list}{}{\itemsep=0pt\parsep=0pt\labelwidth=0pt\leftmargin\parindent\itemindent-\leftmargin\let\makelabel\descriptionlabel}
2457\item[fill]
2458an allocation with a specified character.
2459\item[resize]
2460an existing allocation to decrease or increase its size.
2461In either case, new storage may or may not be allocated, and if there is a new allocation, as much data from the existing allocation are copied.
2462For an increase in storage size, new storage after the copied data may be filled.
2463\newpage
2464\item[align]
2465an allocation on a specified memory boundary, \eg, an address multiple of 64 or 128 for cache-line purposes.
2466\item[array]
2467allocation with a specified number of elements.
2468An array may be filled, resized, or aligned.
2469\end{list}
2470Table~\ref{t:StorageManagementOperations} shows the capabilities provided by C/\Celeven allocation functions and how all the capabilities can be combined into two \CFA functions.
2471\CFA storage-management functions extend the C equivalents by overloading, providing shallow type safety, and removing the need to specify the base allocation size.
2472Figure~\ref{f:StorageAllocation} contrasts \CFA and C storage allocation performing the same operations with the same type safety.
2473
2474\begin{table}
2475\caption{Storage-management operations}
2476\label{t:StorageManagementOperations}
2477\centering
2478\lstDeleteShortInline@%
2479\lstMakeShortInline~%
2480\begin{tabular}{@{}rrllll@{}}
2481\multicolumn{1}{c}{}&           & \multicolumn{1}{c}{fill}      & resize        & align & array \\
2482C               & ~malloc~                      & no                    & no            & no            & no    \\
2483                & ~calloc~                      & yes (0 only)  & no            & no            & yes   \\
2484                & ~realloc~                     & no/copy               & yes           & no            & no    \\
2485                & ~memalign~            & no                    & no            & yes           & no    \\
2486                & ~posix_memalign~      & no                    & no            & yes           & no    \\
2487C11             & ~aligned_alloc~       & no                    & no            & yes           & no    \\
2488\CFA    & ~alloc~                       & yes/copy              & no/yes        & no            & yes   \\
2489                & ~align_alloc~         & yes                   & no            & yes           & yes   \\
2490\end{tabular}
2491\lstDeleteShortInline~%
2492\lstMakeShortInline@%
2493\end{table}
2494
2495\begin{figure}
2496\centering
2497\fontsize{9bp}{11bp}\selectfont
2498\begin{cfa}[aboveskip=0pt,xleftmargin=0pt]
2499size_t  dim = 10;                                                       $\C{// array dimension}$
2500char fill = '\xff';                                                     $\C{// initialization fill value}$
2501int * ip;
2502\end{cfa}
2503\lstDeleteShortInline@%
2504\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{}}
2505\multicolumn{1}{@{}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}  & \multicolumn{1}{c@{}}{\textbf{C}}     \\
2506\begin{cfa}[xleftmargin=-10pt]
2507ip = alloc();
2508ip = alloc( fill );
2509ip = alloc( dim );
2510ip = alloc( dim, fill );
2511ip = alloc( ip, 2 * dim );
2512ip = alloc( ip, 4 * dim, fill );
2513
2514ip = align_alloc( 16 );
2515ip = align_alloc( 16, fill );
2516ip = align_alloc( 16, dim );
2517ip = align_alloc( 16, dim, fill );
2518\end{cfa}
2519&
2520\begin{cfa}
2521ip = (int *)malloc( sizeof(int) );
2522ip = (int *)malloc( sizeof(int) ); memset( ip, fill, sizeof(int) );
2523ip = (int *)malloc( dim * sizeof(int) );
2524ip = (int *)malloc( sizeof(int) ); memset( ip, fill, dim * sizeof(int) );
2525ip = (int *)realloc( ip, 2 * dim * sizeof(int) );
2526ip = (int *)realloc( ip, 4 * dim * sizeof(int) ); memset( ip, fill, 4 * dim * sizeof(int));
2527
2528ip = memalign( 16, sizeof(int) );
2529ip = memalign( 16, sizeof(int) ); memset( ip, fill, sizeof(int) );
2530ip = memalign( 16, dim * sizeof(int) );
2531ip = memalign( 16, dim * sizeof(int) ); memset( ip, fill, dim * sizeof(int) );
2532\end{cfa}
2533\end{tabular}
2534\lstMakeShortInline@%
2535\caption{\CFA versus C storage allocation}
2536\label{f:StorageAllocation}
2537\end{figure}
2538
2539Variadic @new@ (see Section~\ref{sec:variadic-tuples}) cannot support the same overloading because extra parameters are for initialization.
2540Hence, there are @new@ and @anew@ functions for single and array variables, and the fill value is the arguments to the constructor.
2541\begin{cfa}
2542struct S { int i, j; };
2543void ?{}( S & s, int i, int j ) { s.i = i; s.j = j; }
2544S * s = new( 2, 3 );                                            $\C{// allocate storage and run constructor}$
2545S * as = anew( dim, 2, 3 );                                     $\C{// each array element initialized to 2, 3}$
2546\end{cfa}
2547Note that \CC can only initialize array elements via the default constructor.
2548
2549Finally, the \CFA memory allocator has \newterm{sticky properties} for dynamic storage: fill and alignment are remembered with an object's storage in the heap.
2550When a @realloc@ is performed, the sticky properties are respected, so that new storage is correctly aligned and initialized with the fill character.
2551
2552
2553\subsection{I/O}
2554\label{s:IOLibrary}
2555
2556The goal of \CFA I/O is to simplify the common cases, while fully supporting polymorphism and user-defined types in a consistent way.
2557The approach combines ideas from \CC and Python.
2558The \CFA header file for the I/O library is @fstream@.
2559
2560The common case is printing out a sequence of variables separated by whitespace.
2561\begin{cquote}
2562\lstDeleteShortInline@%
2563\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
2564\multicolumn{1}{@{}c@{\hspace{2\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
2565\begin{cfa}
2566int x = 1, y = 2, z = 3;
2567sout | x `|` y `|` z | endl;
2568\end{cfa}
2569&
2570\begin{cfa}
2571
2572cout << x `<< " "` << y `<< " "` << z << endl;
2573\end{cfa}
2574\\
2575\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
25761` `2` `3
2577\end{cfa}
2578&
2579\begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
25801 2 3
2581\end{cfa}
2582\end{tabular}
2583\lstMakeShortInline@%
2584\end{cquote}
2585The \CFA form has half the characters of the \CC form and is similar to Python I/O with respect to implicit separators.
2586Similar simplification occurs for tuple I/O, which prints all tuple values separated by ``\lstinline[showspaces=true]@, @''.
2587\begin{cfa}
2588[int, [ int, int ] ] t1 = [ 1, [ 2, 3 ] ], t2 = [ 4, [ 5, 6 ] ];
2589sout | t1 | t2 | endl;                                  $\C{// print tuples}$
2590\end{cfa}
2591\begin{cfa}[showspaces=true,aboveskip=0pt]
25921`, `2`, `3 4`, `5`, `6
2593\end{cfa}
2594Finally, \CFA uses the logical-or operator for I/O as it is the lowest-priority overloadable operator, other than assignment.
2595Therefore, fewer output expressions require parenthesis.
2596\begin{cquote}
2597\lstDeleteShortInline@%
2598\begin{tabular}{@{}ll@{}}
2599\textbf{\CFA:}
2600&
2601\begin{cfa}
2602sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
2603\end{cfa}
2604\\
2605\textbf{\CC:}
2606&
2607\begin{cfa}
2608cout << x * 3 << y + 1 << `(`z << 2`)` << `(`x == y`)` << (x | y) << (x || y) << (x > z ? 1 : 2) << endl;
2609\end{cfa}
2610\\
2611&
2612\begin{cfa}[showspaces=true,aboveskip=0pt]
26133 3 12 0 3 1 2
2614\end{cfa}
2615\end{tabular}
2616\lstMakeShortInline@%
2617\end{cquote}
2618There is a weak similarity between the \CFA logical-or operator and the Shell pipe operator for moving data, where data flow in the correct direction for input but in the opposite direction for output.
2619\begin{comment}
2620The implicit separator character (space/blank) is a separator not a terminator.
2621The rules for implicitly adding the separator are:
2622\begin{itemize}
2623\item
2624A separator does not appear at the start or end of a line.
2625\item
2626A separator does not appear before or after a character literal or variable.
2627\item
2628A separator does not appear before or after a null (empty) C string, which is a local mechanism to disable insertion of the separator character.
2629\item
2630A separator does not appear before a C string starting with the characters: \lstinline[mathescape=off,basicstyle=\tt]@([{=$@
2631\item
2632A separator does not appear after a C string ending with the characters: \lstinline[basicstyle=\tt]@,.;!?)]}%@
2633\item
2634{\lstset{language=CFA,deletedelim=**[is][]{`}{`}}
2635A separator does not appear before or after a C string beginning/ending with the quote or whitespace characters: \lstinline[basicstyle=\tt,showspaces=true]@`'": \t\v\f\r\n@
2636}%
2637\end{itemize}
2638\end{comment}
2639There are functions to set and get the separator string and manipulators to toggle separation on and off in the middle of output.
2640
2641
2642\subsection{Multiprecision integers}
2643\label{s:MultiPrecisionIntegers}
2644
2645\CFA has an interface to the GNU multiple precision (GMP) signed integers~\cite{GMP}, similar to the \CC interface provided by GMP.
2646The \CFA interface wraps GMP functions into operator functions to make programming with multiprecision integers identical to using fixed-sized integers.
2647The \CFA type name for multiprecision signed integers is @Int@ and the header file is @gmp@.
2648Figure~\ref{f:GMPInterface} shows a multiprecision factorial program contrasting the GMP interface in \CFA and C.
2649
2650\begin{figure}[b]
2651\centering
2652\fontsize{9bp}{11bp}\selectfont
2653\lstDeleteShortInline@%
2654\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
2655\multicolumn{1}{@{}c@{\hspace{3\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{C}}     \\
2656\begin{cfa}
2657#include <gmp>
2658int main( void ) {
2659        sout | "Factorial Numbers" | endl;
2660        Int fact = 1;
2661        sout | 0 | fact | endl;
2662        for ( unsigned int i = 1; i <= 40; i += 1 ) {
2663                fact *= i;
2664                sout | i | fact | endl;
2665        }
2666}
2667\end{cfa}
2668&
2669\begin{cfa}
2670#include <gmp.h>
2671int main( void ) {
2672        `gmp_printf`( "Factorial Numbers\n" );
2673        `mpz_t` fact;  `mpz_init_set_ui`( fact, 1 );
2674        `gmp_printf`( "%d %Zd\n", 0, fact );
2675        for ( unsigned int i = 1; i <= 40; i += 1 ) {
2676                `mpz_mul_ui`( fact, fact, i );
2677                `gmp_printf`( "%d %Zd\n", i, fact );
2678        }
2679}
2680\end{cfa}
2681\end{tabular}
2682\lstMakeShortInline@%
2683\caption{GMP interface \CFA versus C}
2684\label{f:GMPInterface}
2685\end{figure}
2686
2687
2688\vspace{-4pt}
2689\section{Polymorphism Evaluation}
2690\label{sec:eval}
2691
2692\CFA adds parametric polymorphism to C.
2693A runtime evaluation is performed to compare the cost of alternative styles of polymorphism.
2694The goal is to compare just the underlying mechanism for implementing different kinds of polymorphism.
2695% Though \CFA provides significant added functionality over C, these features have a low runtime penalty.
2696% In fact, it is shown that \CFA's generic programming can enable faster runtime execution than idiomatic @void *@-based C code.
2697The experiment is a set of generic-stack microbenchmarks~\cite{CFAStackEvaluation} in C, \CFA, and \CC (see implementations in Appendix~\ref{sec:BenchmarkStackImplementations}).
2698Since all these languages share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code.
2699A more illustrative comparison measures the costs of idiomatic usage of each language's features.
2700Figure~\ref{fig:BenchmarkTest} shows the \CFA benchmark tests for a generic stack based on a singly linked list.
2701The benchmark test is similar for the other languages.
2702The experiment uses element types @int@ and @pair(short, char)@, and pushes $N=40M$ elements on a generic stack, copies the stack, clears one of the stacks, and finds the maximum value in the other stack.
2703
2704\begin{figure}
2705\fontsize{9bp}{11bp}\selectfont
2706\begin{cfa}[xleftmargin=3\parindentlnth,aboveskip=0pt,belowskip=0pt]
2707int main() {
2708        int max = 0, val = 42;
2709        stack( int ) si, ti;
2710
2711        REPEAT_TIMED( "push_int", N, push( si, val ); )
2712        TIMED( "copy_int", ti{ si }; )
2713        TIMED( "clear_int", clear( si ); )
2714        REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
2715
2716        pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
2717        stack( pair( short, char ) ) sp, tp;
2718
2719        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
2720        TIMED( "copy_pair", tp{ sp }; )
2721        TIMED( "clear_pair", clear( sp ); )
2722        REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp ); if ( x > max ) max = x; )
2723}
2724\end{cfa}
2725\caption{\protect\CFA benchmark test}
2726\label{fig:BenchmarkTest}
2727\vspace*{-10pt}
2728\end{figure}
2729
2730The structure of each benchmark implemented is C with @void *@-based polymorphism, \CFA with parametric polymorphism, \CC with templates, and \CC using only class inheritance for polymorphism, called \CCV.
2731The \CCV variant illustrates an alternative object-oriented idiom where all objects inherit from a base @object@ class, mimicking a Java-like interface;
2732hence, runtime checks are necessary to safely downcast objects.
2733The most notable difference among the implementations is in memory layout of generic types: \CFA and \CC inline the stack and pair elements into corresponding list and pair nodes, whereas C and \CCV lack such capability and, instead, must store generic objects via pointers to separately allocated objects.
2734Note that the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, whereas \CFA and \CC provide type safety statically.
2735
2736Figure~\ref{fig:eval} and Table~\ref{tab:eval} show the results of running the benchmark in Figure~\ref{fig:BenchmarkTest} and its C, \CC, and \CCV equivalents.
2737The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted.
2738All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC code compiled as \CCfourteen.
2739The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency.
2740
2741\begin{figure}
2742\centering
2743\resizebox{0.7\textwidth}{!}{\input{timing}}
2744\caption{Benchmark timing results (smaller is better)}
2745\label{fig:eval}
2746\vspace*{-10pt}
2747\end{figure}
2748
2749\begin{table}
2750\vspace*{-10pt}
2751\caption{Properties of benchmark code}
2752\label{tab:eval}
2753\centering
2754\vspace*{-4pt}
2755\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
2756\begin{tabular}{lrrrr}
2757                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\
2758maximum memory usage (MB)                       & 10\,001       & 2\,502        & 2\,503        & 11\,253               \\
2759source code size (lines)                        & 201           & 191           & 125           & 294                   \\
2760redundant type annotations (lines)      & 27            & 0                     & 2                     & 16                    \\
2761binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
2762\end{tabular}
2763\vspace*{-16pt}
2764\end{table}
2765
2766\enlargethispage{-10pt}
2767The C and \CCV variants are generally the slowest with the largest memory footprint, due to their less-efficient memory layout and the pointer indirection necessary to implement generic types;
2768this inefficiency is exacerbated by the second level of generic types in the pair benchmarks.
2769By contrast, the \CFA and \CC variants run in roughly equivalent time for both the integer and pair because of the equivalent storage layout, with the inlined libraries (\ie no separate compilation) and greater maturity of the \CC compiler contributing to its lead.
2770\CCV is slower than C largely due to the cost of runtime type checking of downcasts (implemented with @dynamic_cast@).
2771The outlier for \CFA, pop @pair@, results from the complexity of the generated-C polymorphic code.
2772The gcc compiler is unable to optimize some dead code and condense nested calls;
2773a compiler designed for \CFA could easily perform these optimizations.
2774Finally, the binary size for \CFA is larger because of static linking with the \CFA libraries.
2775
2776\CFA is also competitive in terms of source code size, measured as a proxy for programmer effort. The line counts in Table~\ref{tab:eval} include implementations of @pair@ and @stack@ types for all four languages for purposes of direct comparison, although it should be noted that \CFA and \CC have prewritten data structures in their standard libraries that programmers would generally use instead. Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA and \CC benchmarks to 39 and 42 lines, respectively.
2777The difference between the \CFA and \CC line counts is primarily declaration duplication to implement separate compilation; a header-only \CFA library would be similar in length to the \CC version.
2778On the other hand, C does not have a generic collections library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers.
2779\CCV does not use the \CC standard template library by construction and, in fact, includes the definition of @object@ and wrapper classes for @char@, @short@, and @int@ in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library;
2780with their omission, the \CCV line count is similar to C.
2781We justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or wrapper types, which may be similarly verbose.
2782
2783Line count is a fairly rough measure of code complexity;
2784another important factor is how much type information the programmer must specify manually, especially where that information is not compiler checked.
2785Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs and is much less common in \CFA than C, with its manually specified function pointer arguments and format codes, or \CCV, with its extensive use of un-type-checked downcasts, \eg @object@ to @integer@ when popping a stack.
2786To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{tab:eval} counts the number of lines on which the type of a known variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a @sizeof@, struct literal, or @new@ expression.
2787The \CC benchmark uses two redundant type annotations to create a new stack nodes, whereas the C and \CCV benchmarks have several such annotations spread throughout their code.
2788The \CFA benchmark is able to eliminate all redundant type annotations through use of the polymorphic @alloc@ function discussed in Section~\ref{sec:libraries}.
2789
2790We conjecture that these results scale across most generic data types as the underlying polymorphism implement is constant.
2791
2792
2793\vspace*{-8pt}
2794\section{Related Work}
2795\label{s:RelatedWork}
2796
2797
2798\subsection{Polymorphism}
2799
2800ML~\cite{ML} was the first language to support parametric polymorphism.
2801Like \CFA, it supports universal type parameters, but not the use of assertions and traits to constrain type arguments.
2802Haskell~\cite{Haskell10} combines ML-style polymorphism, polymorphic data types, and type inference with the notion of type classes, collections of overloadable methods that correspond in intent to traits in \CFA.
2803Unlike \CFA, Haskell requires an explicit association between types and their classes that specifies the implementation of operations.
2804These associations determine the functions that are assertion arguments for particular combinations of class and type, in contrast to \CFA where the assertion arguments are selected at function call sites based upon the set of operations in scope at that point.
2805Haskell also severely restricts the use of overloading: an overloaded name can only be associated with a single class, and methods with overloaded names can only be defined as part of instance declarations.
2806
2807\CC provides three disjoint polymorphic extensions to C: overloading, inheritance, and templates.
2808The overloading is restricted because resolution does not use the return type, inheritance requires learning object-oriented programming and coping with a restricted nominal-inheritance hierarchy, templates cannot be separately compiled resulting in compilation/code bloat and poor error messages, and determining how these mechanisms interact and which to use is confusing.
2809In contrast, \CFA has a single facility for polymorphic code supporting type-safe separate compilation of polymorphic functions and generic (opaque) types, which uniformly leverage the C procedural paradigm.
2810The key mechanism to support separate compilation is \CFA's \emph{explicit} use of assumed type properties.
2811Until \CC concepts~\cite{C++Concepts} are standardized (anticipated for \CCtwenty), \CC provides no way of specifying the requirements of a generic function beyond compilation errors during template expansion;
2812furthermore, \CC concepts are restricted to template polymorphism.
2813
2814Cyclone~\cite{Grossman06} also provides capabilities for polymorphic functions and existential types, similar to \CFA's @forall@ functions and generic types.
2815Cyclone existential types can include function pointers in a construct similar to a virtual function table, but these pointers must be explicitly initialized at some point in the code, which is a tedious and potentially error-prone process.
2816Furthermore, Cyclone's polymorphic functions and types are restricted to abstraction over types with the same layout and calling convention as @void *@, \ie only pointer types and @int@.
2817In \CFA terms, all Cyclone polymorphism must be dtype-static.
2818While the Cyclone design provides the efficiency benefits discussed in Section~\ref{sec:generic-apps} for dtype-static polymorphism, it is more restrictive than \CFA's general model.
2819Smith and Volpano~\cite{Smith98} present Polymorphic C, an ML dialect with polymorphic functions, C-like syntax, and pointer types;
2820it lacks many of C's features, most notably structure types, and hence, is not a practical C replacement.
2821
2822Objective-C~\cite{obj-c-book} is an industrially successful extension to C.
2823However, Objective-C is a radical departure from C, using an object-oriented model with message passing.
2824Objective-C did not support type-checked generics until recently \cite{xcode7}, historically using less-efficient runtime checking of object types.
2825The GObject~\cite{GObject} framework also adds object-oriented programming with runtime type-checking and reference-counting garbage collection to C;
2826these features are more intrusive additions than those provided by \CFA, in addition to the runtime overhead of reference counting.
2827Vala~\cite{Vala} compiles to GObject-based C, adding the burden of learning a separate language syntax to the aforementioned demerits of GObject as a modernization path for existing C code bases.
2828Java~\cite{Java8} included generic types in Java~5, which are type checked at compilation and type erased at runtime, similar to \CFA's.
2829However, in Java, each object carries its own table of method pointers, whereas \CFA passes the method pointers separately to maintain a C-compatible layout.
2830Java is also a garbage-collected, object-oriented language, with the associated resource usage and C-interoperability burdens.
2831
2832D~\cite{D}, Go, and Rust~\cite{Rust} are modern compiled languages with abstraction features similar to \CFA traits, \emph{interfaces} in D and Go, and \emph{traits} in Rust.
2833However, each language represents a significant departure from C in terms of language model, and none has the same level of compatibility with C as \CFA.
2834D and Go are garbage-collected languages, imposing the associated runtime overhead.
2835The necessity of accounting for data transfer between managed runtimes and the unmanaged C runtime complicates foreign-function interfaces to C.
2836Furthermore, while generic types and functions are available in Go, they are limited to a small fixed set provided by the compiler, with no language facility to define more.
2837D restricts garbage collection to its own heap by default, whereas Rust is not garbage collected and, thus, has a lighter-weight runtime more interoperable with C.
2838Rust also possesses much more powerful abstraction capabilities for writing generic code than Go.
2839On the other hand, Rust's borrow checker provides strong safety guarantees but is complex and difficult to learn and imposes a distinctly idiomatic programming style.
2840\CFA, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source.
2841
2842
2843\vspace*{-18pt}
2844\subsection{Tuples/variadics}
2845
2846\vspace*{-5pt}
2847Many programming languages have some form of tuple construct and/or variadic functions, \eg SETL, C, KW-C, \CC, D, Go, Java, ML, and Scala.
2848SETL~\cite{SETL} is a high-level mathematical programming language, with tuples being one of the primary data types.
2849Tuples in SETL allow subscripting, dynamic expansion, and multiple assignment.
2850C provides variadic functions through @va_list@ objects, but the programmer is responsible for managing the number of arguments and their types;
2851thus, the mechanism is type unsafe.
2852KW-C~\cite{Buhr94a}, a predecessor of \CFA, introduced tuples to C as an extension of the C syntax, taking much of its inspiration from SETL.
2853The main contributions of that work were adding MRVF, tuple mass and multiple assignment, and record-member access.
2854\CCeleven introduced @std::tuple@ as a library variadic-template structure.
2855Tuples are a generalization of @std::pair@, in that they allow for arbitrary length, fixed-size aggregation of heterogeneous values.
2856Operations include @std::get<N>@ to extract values, @std::tie@ to create a tuple of references used for assignment, and lexicographic comparisons.
2857\CCseventeen proposes \emph{structured bindings}~\cite{Sutter15} to eliminate predeclaring variables and the use of @std::tie@ for binding the results.
2858This extension requires the use of @auto@ to infer the types of the new variables; hence, complicated expressions with a nonobvious type must be documented with some other mechanism.
2859Furthermore, structured bindings are not a full replacement for @std::tie@, as it always declares new variables.
2860Like \CC, D provides tuples through a library variadic-template structure.
2861Go does not have tuples but supports MRVF.
2862Java's variadic functions appear similar to C's but are type safe using homogeneous arrays, which are less useful than \CFA's heterogeneously typed variadic functions.
2863Tuples are a fundamental abstraction in most functional programming languages, such as Standard ML~\cite{sml}, Haskell, and Scala~\cite{Scala}, which decompose tuples using pattern matching.
2864
2865
2866\vspace*{-18pt}
2867\subsection{C Extensions}
2868
2869\vspace*{-5pt}
2870\CC is the best known C-based language and is similar to \CFA in that both are extensions to C with source and runtime backward compatibility.
2871Specific differences between \CFA and \CC have been identified in prior sections, with a final observation that \CFA has equal or fewer tokens to express the same notion in many cases.
2872The key difference in design philosophies is that \CFA is easier for C programmers to understand by maintaining a procedural paradigm and avoiding complex interactions among extensions.
2873\CC, on the other hand, has multiple overlapping features (such as the three forms of polymorphism), many of which have complex interactions with its object-oriented design.
2874As a result, \CC has a steep learning curve for even experienced C programmers, especially when attempting to maintain performance equivalent to C legacy code.
2875
2876There are several other C extension languages with less usage and even more dramatic changes than \CC.
2877\mbox{Objective-C} and Cyclone are two other extensions to C with different design goals than \CFA, as discussed above.
2878Other languages extend C with more focused features.
2879$\mu$\CC~\cite{uC++book}, CUDA~\cite{Nickolls08}, ispc~\cite{Pharr12}, and Sierra~\cite{Leissa14} add concurrent or data-parallel primitives to C or \CC;
2880data-parallel features have not yet been added to \CFA, but are easily incorporated within its design, whereas concurrency primitives similar to those in $\mu$\CC have already been added~\cite{Delisle18}.
2881Finally, CCured~\cite{Necula02} and Ironclad \CC~\cite{DeLozier13} attempt to provide a more memory-safe C by annotating pointer types with garbage collection information; type-checked polymorphism in \CFA covers several of C's memory-safety issues, but more aggressive approaches such as annotating all pointer types with their nullability or requiring runtime garbage collection are contradictory to \CFA's backward compatibility goals.
2882
2883
2884\section{Conclusion and Future Work}
2885
2886The goal of \CFA is to provide an evolutionary pathway for large C development environments to be more productive and safer, while respecting the talent and skill of C programmers.
2887While other programming languages purport to be a better C, they are, in fact, new and interesting languages in their own right, but not C extensions.
2888The purpose of this paper is to introduce \CFA, and showcase language features that illustrate the \CFA type system and approaches taken to achieve the goal of evolutionary C extension.
2889The contributions are a powerful type system using parametric polymorphism and overloading, generic types, tuples, advanced control structures, and extended declarations, which all have complex interactions.
2890The work is a challenging design, engineering, and implementation exercise.
2891On the surface, the project may appear as a rehash of similar mechanisms in \CC.
2892However, every \CFA feature is different than its \CC counterpart, often with extended functionality, better integration with C and its programmers, and always supporting separate compilation.
2893All of these new features are being used by the \CFA development team to build the \CFA runtime system.
2894Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
2895
2896While all examples in the paper compile and run, there are ongoing efforts to reduce compilation time, provide better debugging, and add more libraries;
2897when this work is complete in early 2019, a public beta release will be available at \url{https://github.com/cforall/cforall}.
2898There is also new work on a number of \CFA features, including arrays with size, runtime type information, virtual functions, user-defined conversions, and modules.
2899While \CFA polymorphic functions use dynamic virtual dispatch with low runtime overhead (see Section~\ref{sec:eval}), it is not as low as \CC template inlining.
2900Hence, it may be beneficial to provide a mechanism for performance-sensitive code.
2901Two promising approaches are an @inline@ annotation at polymorphic function call sites to create a template specialization of the function (provided the code is visible) or placing an @inline@ annotation on polymorphic function definitions to instantiate a specialized version for some set of types (\CC template specialization).
2902 These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat.
2903In general, we believe separate compilation, producing smaller code, works well with loaded hardware caches, which may offset the benefit of larger inlined code.
2904
2905
2906\section{Acknowledgments}
2907
2908The authors would like to recognize the design assistance of Glen Ditchfield, Richard Bilson, Thierry Delisle, Andrew Beach, and Brice Dobry on the features described in this paper and thank Magnus Madsen for feedback on the writing.
2909Funding for this project was provided by Huawei Ltd (\url{http://www.huawei.com}), and Aaron Moss and Peter Buhr were partially funded by the Natural Sciences and Engineering Research Council of Canada.
2910
2911{%
2912\fontsize{9bp}{12bp}\selectfont%
2913\vspace*{-3pt}
2914\bibliography{pl}
2915}%
2916
2917\appendix
2918
2919\section{Benchmark Stack Implementations}
2920\label{sec:BenchmarkStackImplementations}
2921
2922Throughout, @/***/@ designates a counted redundant type annotation; code reformatted slightly for brevity.
2923
2924
2925\subsection{C}
2926
2927\begin{flushleft}
2928\lstDeleteShortInline@%
2929\begin{tabular}{@{}l@{\hspace{1.8\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
2930\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
2931typedef struct node {
2932        void * value;
2933        struct node * next;
2934} node;
2935typedef struct stack {
2936        struct node * head;
2937} stack;
2938void copy_stack( stack * s, const stack * t,
2939                                void * (*copy)( const void * ) ) {
2940        node ** cr = &s->head;
2941        for (node * nx = t->head; nx; nx = nx->next) {
2942                *cr = malloc( sizeof(node) ); /***/
2943                (*cr)->value = copy( nx->value );
2944                cr = &(*cr)->next;
2945        }
2946        *cr = NULL;
2947}
2948void clear_stack( stack * s, void (* free_el)( void * ) ) {
2949        for ( node * nx = s->head; nx; ) {
2950                node * cr = nx;
2951                nx = cr->next;
2952                free_el( cr->value );
2953                free( cr );
2954        }
2955        s->head = NULL;
2956}
2957\end{cfa}
2958&
2959\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
2960stack new_stack() {
2961        return (stack){ NULL }; /***/
2962}
2963stack * assign_stack( stack * s, const stack * t,
2964                                void * (*copy_el)( const void * ),
2965                                void (*free_el)( void * ) ) {
2966        if ( s->head == t->head ) return s;
2967        clear_stack( s, free_el ); /***/
2968        copy_stack( s, t, copy_el ); /***/
2969        return s;
2970}
2971_Bool stack_empty( const stack * s ) {
2972        return s->head == NULL;
2973}
2974void push_stack( stack * s, void * v ) {
2975        node * n = malloc( sizeof(node) ); /***/
2976        *n = (node){ v, s->head }; /***/
2977        s->head = n;
2978}
2979void * pop_stack( stack * s ) {
2980        node * n = s->head;
2981        s->head = n->next;
2982        void * v = n->value;
2983        free( n );
2984        return v;
2985}
2986\end{cfa}
2987\end{tabular}
2988\lstMakeShortInline@%
2989\end{flushleft}
2990
2991
2992\enlargethispage{1000pt}
2993\subsection{\CFA}
2994\label{s:CforallStack}
2995
2996\begin{flushleft}
2997\lstDeleteShortInline@%
2998\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
2999\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
3000forall( otype T ) {
3001        struct node {
3002                T value;
3003                node(T) * next;
3004        };
3005        struct stack { node(T) * head; };
3006        void ?{}( stack(T) & s, stack(T) t ) { // copy
3007                node(T) ** cr = &s.head;
3008                for ( node(T) * nx = t.head; nx; nx = nx->next ) {
3009                        *cr = alloc();
3010                        ((*cr)->value){ nx->value };
3011                        cr = &(*cr)->next;
3012                }
3013                *cr = 0;
3014        }
3015        void clear( stack(T) & s ) with( s ) {
3016                for ( node(T) * nx = head; nx; ) {
3017                        node(T) * cr = nx;
3018                        nx = cr->next;
3019                        ^(*cr){};
3020                        free( cr );
3021                }
3022                head = 0;
3023        }
3024
3025\end{cfa}
3026&
3027\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
3028        void ?{}( stack(T) & s ) { (s.head){ 0 }; }
3029        void ^?{}( stack(T) & s) { clear( s ); }
3030        stack(T) ?=?( stack(T) & s, stack(T) t ) {
3031                if ( s.head == t.head ) return s;
3032                clear( s );
3033                s{ t };
3034                return s;
3035        }
3036        _Bool empty( const stack(T) & s ) {
3037                return s.head == 0;
3038        }
3039        void push( stack(T) & s, T value ) with( s ) {
3040                node(T) * n = alloc();
3041                (*n){ value, head };
3042                head = n;
3043        }
3044        T pop( stack(T) & s ) with( s ) {
3045                node(T) * n = head;
3046                head = n->next;
3047                T v = n->value;
3048                ^(*n){};
3049                free( n );
3050                return v;
3051        }
3052}
3053\end{cfa}
3054\end{tabular}
3055\lstMakeShortInline@%
3056\end{flushleft}
3057
3058
3059\newpage
3060\subsection{\CC}
3061
3062\begin{flushleft}
3063\lstDeleteShortInline@%
3064\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
3065\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
3066template<typename T> struct stack {
3067        struct node {
3068                T value;
3069                node * next;
3070                node( const T & v, node * n = nullptr ) :
3071                        value( v ), next( n ) {}
3072        };
3073        node * head;
3074        void copy( const stack<T> & o ) {
3075                node ** cr = &head;
3076                for ( node * nx = o.head; nx; nx = nx->next ) {
3077                        *cr = new node{ nx->value }; /***/
3078                        cr = &(*cr)->next;
3079                }
3080                *cr = nullptr;
3081        }
3082        void clear() {
3083                for ( node * nx = head; nx; ) {
3084                        node * cr = nx;
3085                        nx = cr->next;
3086                        delete cr;
3087                }
3088                head = nullptr;
3089        }
3090\end{cfa}
3091&
3092\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
3093        stack() : head( nullptr ) {}
3094        stack( const stack<T> & o ) { copy( o ); }
3095        ~stack() { clear(); }
3096        stack & operator=( const stack<T> & o ) {
3097                if ( this == &o ) return *this;
3098                clear();
3099                copy( o );
3100                return *this;
3101        }
3102        bool empty() const {
3103                return head == nullptr;
3104        }
3105        void push( const T & value ) {
3106                head = new node{ value, head };  /***/
3107        }
3108        T pop() {
3109                node * n = head;
3110                head = n->next;
3111                T v = std::move( n->value );
3112                delete n;
3113                return v;
3114        }
3115};
3116
3117\end{cfa}
3118\end{tabular}
3119\lstMakeShortInline@%
3120\end{flushleft}
3121
3122
3123\subsection{\CCV}
3124
3125\begin{flushleft}
3126\lstDeleteShortInline@%
3127\begin{tabular}{@{}l|@{\hspace{\parindentlnth}}l@{}}
3128\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
3129struct stack {
3130        struct node {
3131                ptr<object> value;
3132                node * next;
3133                node( const object & v, node * n = nullptr ) :
3134                                value( v.new_copy() ), next( n ) {}
3135        };
3136        node * head;
3137        void copy( const stack & o ) {
3138                node ** cr = &head;
3139                for ( node * nx = o.head; nx; nx = nx->next ) {
3140                        *cr = new node{ *nx->value }; /***/
3141                        cr = &(*cr)->next;
3142                }
3143                *cr = nullptr;
3144        }
3145        void clear() {
3146                for ( node * nx = head; nx; ) {
3147                        node * cr = nx;
3148                        nx = cr->next;
3149                        delete cr;
3150                }
3151                head = nullptr;
3152        }
3153\end{cfa}
3154&
3155\begin{cfa}[xleftmargin=0pt,aboveskip=0pt,belowskip=0pt]
3156        stack() : head( nullptr ) {}
3157        stack( const stack & o ) { copy( o ); }
3158        ~stack() { clear(); }
3159        stack & operator=( const stack & o ) {
3160                if ( this == &o ) return *this;
3161                clear();
3162                copy( o );
3163                return *this;
3164        }
3165        bool empty() const {
3166                return head == nullptr;
3167        }
3168        void push( const object & value ) {
3169                head = new node{ value, head }; /***/
3170        }
3171        ptr<object> pop() {
3172                node * n = head;
3173                head = n->next;
3174                ptr<object> v = std::move( n->value );
3175                delete n;
3176                return v;
3177        }
3178};
3179
3180\end{cfa}
3181\end{tabular}
3182\lstMakeShortInline@%
3183\end{flushleft}
3184
3185
3186\end{document}
3187
3188% Local Variables: %
3189% tab-width: 4 %
3190% compile-command: "make" %
3191% End: %
Note: See TracBrowser for help on using the repository browser.