Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision 83e680dfbc65dc18b4ac28572653c3e2af959cad) +++ doc/user/user.tex (revision 7f617cf092d9769da8e953535e145232d27ae7c7) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Sat Jul 22 11:01:19 2017 -%% Update Count : 2878 +%% Last Modified On : Sun Aug 6 08:52:34 2017 +%% Update Count : 3034 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -37,6 +37,4 @@ \usepackage{mathptmx} % better math font with "times" \usepackage[usenames]{color} -\usepackage[pagewise]{lineno} -\renewcommand{\linenumberfont}{\scriptsize\sffamily} \input{common} % common CFA document macros \usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref} @@ -44,8 +42,12 @@ \renewcommand{\UrlFont}{\small\sf} +\usepackage[pagewise]{lineno} +\renewcommand{\linenumberfont}{\scriptsize\sffamily} +\usepackage[firstpage]{draftwatermark} +\SetWatermarkLightness{0.9} + % Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore % removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR % AFTER HYPERREF. -\renewcommand{\_}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}} \renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}} @@ -56,6 +58,5 @@ \CFAStyle % use default CFA format-style - -\lstnewenvironment{C++}[1][] +\lstnewenvironment{C++}[1][] % use C++ style {\lstset{language=C++,moredelim=**[is][\protect\color{red}]{®}{®}#1}} {} @@ -78,4 +79,5 @@ \newcommand{\B}[1]{{\Textbf[blue]{#1}}} \newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}} +\newcommand{\KWC}{K-W C\xspace} \newsavebox{\LstBox} @@ -105,5 +107,5 @@ \date{ -DRAFT \\ \today +\today }% date @@ -197,5 +199,5 @@ This document is a programmer reference-manual for the \CFA programming language. The manual covers the core features of the language and runtime-system, with simple examples illustrating syntax and semantics of each feature. -The manual does not teach programming, i.e., how to combine the new constructs to build complex programs. +The manual does not teach programming, \ie how to combine the new constructs to build complex programs. A reader should already have an intermediate knowledge of control flow, data structures, and concurrency issues to understand the ideas presented, as well as some experience programming in C/\CC. Implementers should refer to the \CFA Programming Language Specification for details about the language syntax and semantics. @@ -247,7 +249,7 @@ \section{History} -The \CFA project started with \Index*{K-W C}~\cite{Buhr94a,Till89}, which extended C with new declaration syntax, multiple return values from routines, and advanced assignment capabilities using the notion of tuples. +The \CFA project started with \Index*{Dave Till}\index{Till, Dave}'s \Index*{K-W C}~\cite{Buhr94a,Till89}, which extended C with new declaration syntax, multiple return values from routines, and advanced assignment capabilities using the notion of tuples. (See~\cite{Werther96} for similar work in \Index*[C++]{\CC{}}.) -The first \CFA implementation of these extensions was by Esteves~\cite{Esteves04}. +The first \CFA implementation of these extensions was by \Index*{Rodolfo Esteves}\index{Esteves, Rodolfo}~\cite{Esteves04}. The signature feature of \CFA is \emph{\Index{overload}able} \Index{parametric-polymorphic} functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a ©forall© clause (giving the language its name): @@ -257,5 +259,5 @@ \end{lstlisting} % extending the C type system with parametric polymorphism and overloading, as opposed to the \Index*[C++]{\CC{}} approach of object-oriented extensions. -\CFA{}\hspace{1pt}'s polymorphism was originally formalized by Ditchfield~\cite{Ditchfield92}, and first implemented by Bilson~\cite{Bilson03}. +\CFA{}\hspace{1pt}'s polymorphism was originally formalized by \Index*{Glen Ditchfield}\index{Ditchfield, Glen}~\cite{Ditchfield92}, and first implemented by \Index*{Richard Bilson}\index{Bilson, Richard}~\cite{Bilson03}. However, at that time, there was little interesting in extending C, so work did not continue. As the saying goes, ``\Index*{What goes around, comes around.}'', and there is now renewed interest in the C programming language because of legacy code-bases, so the \CFA project has been restarted. @@ -344,5 +346,5 @@ The command ©cfa© is used to compile a \CFA program and is based on the \Index{GNU} \Indexc{gcc} command, \eg: \begin{cfa} -cfa§\indexc{cfa}\index{compilation!cfa@©cfa©}§ [ gcc-options ] C/§\CFA{}§-files [ assembler/loader-files ] +cfa§\indexc{cfa}\index{compilation!cfa@©cfa©}§ [ gcc-options ] [ C/§\CFA{}§ source-files ] [ assembler/loader files ] \end{cfa} \CFA programs having the following ©gcc© flags turned on: @@ -509,10 +511,10 @@ For both ©continue© and ©break©, the target label must be directly associated with a ©for©, ©while© or ©do© statement; for ©break©, the target label can also be associated with a ©switch©, ©if© or compound (©{}©) statement. -\VRef[Figure]{f:MultiLevelResumeTermination} shows the labelled ©continue© and ©break©, specifying which control structure is the target for exit, and the corresponding C program using only ©goto©. -The innermost loop has 7 exit points, which cause resumption or termination of one or more of the 7 \Index{nested control-structure}s. +\VRef[Figure]{f:MultiLevelExit} shows ©continue© and ©break© indicating the specific control structure, and the corresponding C program using only ©goto© and labels. +The innermost loop has 7 exit points, which cause continuation or termination of one or more of the 7 \Index{nested control-structure}s. \begin{figure} -\begin{tabular}{@{\hspace{\parindentlnth}}l@{\hspace{1.5em}}l@{}} -\multicolumn{1}{c@{\hspace{1.5em}}}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{C}} \\ +\begin{tabular}{@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}} +\multicolumn{1}{@{\hspace{\parindentlnth}}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}} \\ \begin{cfa} ®LC:® { @@ -523,15 +525,15 @@ ®LF:® for ( ... ) { ®LW:® while ( ... ) { - ... break ®LC®; ... // terminate compound - ... break ®LS®; ... // terminate switch - ... break ®LIF®; ... // terminate if - ... continue ®LF;® ... // resume loop - ... break ®LF®; ... // terminate loop - ... continue ®LW®; ... // resume loop - ... break ®LW®; ... // terminate loop + ... break ®LC®; ... + ... break ®LS®; ... + ... break ®LIF®; ... + ... continue ®LF;® ... + ... break ®LF®; ... + ... continue ®LW®; ... + ... break ®LW®; ... } // while } // for } else { - ... break ®LIF®; ... // terminate if + ... break ®LIF®; ... } // if } // switch @@ -562,58 +564,32 @@ } ®LC:® ; \end{cfa} +& +\begin{cfa} + + + + + + + +// terminate compound +// terminate switch +// terminate if +// continue loop +// terminate loop +// continue loop +// terminate loop + + + +// terminate if + + + +\end{cfa} \end{tabular} -\caption{Multi-level Resume/Termination} -\label{f:MultiLevelResumeTermination} +\caption{Multi-level Exit} +\label{f:MultiLevelExit} \end{figure} - -\begin{comment} -int main() { - LC: { - LS: switch ( 1 ) { - case 3: - LIF: if ( 1 ) { - LF: for ( ;; ) { - LW: while ( 1 ) { - break LC; // terminate compound - break LS; // terminate switch - break LIF; // terminate if - continue LF; // resume loop - break LF; // terminate loop - continue LW; // resume loop - break LW; // terminate loop - } // while - } // for - } else { - break LIF; // terminate if - } // if - } // switch - } // compound - { - switch ( 1 ) { - case 3: - if ( 1 ) { - for ( ;; ) { - while ( 1 ) { - goto LCx; - goto LSx; - goto LIF; - goto LFC; - goto LFB; - goto LWC; - goto LWB; - LWC: ; } LWB: ; - LFC: ; } LFB: ; - } else { - goto LIF; - } L3: ; - } LSx: ; - } LCx: ; -} - -// Local Variables: // -// tab-width: 4 // -// End: // -\end{comment} - Both labelled ©continue© and ©break© are a ©goto©\index{goto@\lstinline $goto$!restricted} restricted in the following ways: @@ -920,8 +896,8 @@ class C { int i, j; - int mem() { ®// implicit "this" parameter -® i = 1; ®// this->i -® j = 3; ®// this->j -® } + int mem() { §\C{\color{red}// implicit "this" parameter}§ + i = 1; §\C{\color{red}// this->i}§ + j = 2; §\C{\color{red}// this->j}§ + } } \end{C++} @@ -929,6 +905,6 @@ \begin{cfa} struct S { int i, j; }; -int mem( S &this ) { // explicit "this" parameter - ®this.®i = 1; // "this" is not elided +int mem( S &®this® ) { §\C{// explicit "this" parameter}§ + ®this.®i = 1; §\C{// "this" is not elided}§ ®this.®j = 2; } @@ -938,8 +914,8 @@ \CFA provides a ©with© clause/statement (see Pascal~\cite[\S~4.F]{Pascal}) to elided the "©this.©" by opening a scope containing field identifiers, changing the qualified fields into variables and giving an opportunity for optimizing qualified references. \begin{cfa} -int mem( S &this ) ®with this® { // with clause - i = 1; ®// this.i -® j = 2; ®// this.j -®} +int mem( S &this ) ®with this® { §\C{// with clause}§ + i = 1; §\C{\color{red}// this->i}§ + j = 2; §\C{\color{red}// this->j}§ +} \end{cfa} which extends to multiple routine parameters: @@ -992,5 +968,5 @@ Exception handling provides two mechanism: change of control flow from a raise to a handler, and communication from the raise to the handler. Transfer of control can be local, within a routine, or non-local, among routines. -Non-local transfer can cause stack unwinding, i.e., non-local routine termination, depending on the kind of raise. +Non-local transfer can cause stack unwinding, \ie non-local routine termination, depending on the kind of raise. \begin{cfa} exception_t E {}; §\C{// exception type}§ @@ -1001,7 +977,7 @@ try { f(...); -} catch( E e : §boolean-predicate§ ) { §\C{// termination handler}§ +} catch( E e : §boolean-predicate§ ) { §\C[8cm]{// termination handler}§ // recover and continue -} catchResume( E e : §boolean-predicate§ ) { §\C{// resumption handler}§ +} catchResume( E e : §boolean-predicate§ ) { §\C{// resumption handler}\CRT§ // repair and return } finally { @@ -1230,6 +1206,6 @@ As for \Index{division}, there are exponentiation operators for integral and floating-point types, including the builtin \Index{complex} types. -Unsigned integral exponentiation\index{exponentiation!unsigned integral} is performed with repeated multiplication (or shifting if the base is 2). -Signed integral exponentiation\index{exponentiation!signed integral} is performed with repeated multiplication (or shifting if the base is 2), but yields a floating-point result because $b^{-e}=1/b^e$. +Unsigned integral exponentiation\index{exponentiation!unsigned integral} is performed with repeated multiplication\footnote{The multiplication computation is optimized to $O(\log y)$.} (or shifting if the base is 2). +Signed integral exponentiation\index{exponentiation!signed integral} is performed with repeated multiplication (or shifting if the base is 2), but yields a floating-point result because $x^{-y}=1/x^y$. Hence, it is important to designate exponent integral-constants as unsigned or signed: ©3 \ 3u© return an integral result, while ©3 \ 3© returns a floating-point result. Floating-point exponentiation\index{exponentiation!floating point} is performed using \Index{logarithm}s\index{exponentiation!logarithm}, so the base cannot be negative. @@ -1446,8 +1422,8 @@ int w, x, y, z, & ar[3] = { x, y, z }; §\C{// initialize array of references}§ &ar[1] = &w; §\C{// change reference array element}§ -typeof( ar[1] ) p; §\C{// (gcc) is int, i.e., the type of referenced object}§ -typeof( &ar[1] ) q; §\C{// (gcc) is int \&, i.e., the type of reference}§ -sizeof( ar[1] ) == sizeof( int ); §\C{// is true, i.e., the size of referenced object}§ -sizeof( &ar[1] ) == sizeof( int *) §\C{// is true, i.e., the size of a reference}§ +typeof( ar[1] ) p; §\C{// (gcc) is int, \ie the type of referenced object}§ +typeof( &ar[1] ) q; §\C{// (gcc) is int \&, \ie the type of reference}§ +sizeof( ar[1] ) == sizeof( int ); §\C{// is true, \ie the size of referenced object}§ +sizeof( &ar[1] ) == sizeof( int *) §\C{// is true, \ie the size of a reference}§ \end{cfa} @@ -1788,5 +1764,5 @@ In detail, the brackets, ©[]©, enclose the result type, where each return value is named and that name is a local variable of the particular return type.\footnote{ -\Index*{Michael Tiemann}, with help from \Index*{Doug Lea}, provided named return values in g++, circa 1989.} +\Index*{Michael Tiemann}\index{Tiemann, Michael}, with help from \Index*{Doug Lea}\index{Lea, Doug}, provided named return values in g++, circa 1989.} The value of each local return variable is automatically returned at routine termination. Declaration qualifiers can only appear at the start of a routine definition, \eg: @@ -2245,4 +2221,580 @@ Currently, there are no \Index{lambda} expressions, \ie unnamed routines because routine names are very important to properly select the correct routine. + + +\section{Tuple} + +In C and \CFA, lists of elements appear in several contexts, such as the parameter list of a routine call. +\begin{cfa} +f( ®2, x, 3 + i® ); §\C{// element list}§ +\end{cfa} +A list of elements is called a \newterm{tuple}, and is different from a \Index{comma expression}. + + +\subsection{Multiple-Return-Value Functions} +\label{s:MRV_Functions} + +In standard C, functions can return at most one value. +To emulate functions with multiple return values, \emph{\Index{aggregation}} and/or \emph{\Index{aliasing}} is used. +In the former situation, the function designer creates a record type that combines all of the return values into a single type. +For example, consider a function returning the most frequently occurring letter in a string, and its frequency. +This example is complex enough to illustrate that an array is insufficient, since arrays are homogeneous, and demonstrates a potential pitfall that exists with aliasing. +\begin{cfa} +struct mf_ret { + int freq; + char ch; +}; + +struct mf_ret most_frequent(const char * str) { + char freqs [26] = { 0 }; + struct mf_ret ret = { 0, 'a' }; + for (int i = 0; str[i] != '\0'; ++i) { + if (isalpha(str[i])) { // only count letters + int ch = tolower(str[i]); // convert to lower case + int idx = ch-'a'; + if (++freqs[idx] > ret.freq) { // update on new max + ret.freq = freqs[idx]; + ret.ch = ch; + } + } + } + return ret; +} + +const char * str = "hello world"; +struct mf_ret ret = most_frequent(str); +printf("%s -- %d %c\n", str, ret.freq, ret.ch); +\end{cfa} +Of note, the designer must come up with a name for the return type and for each of its fields. +Unnecessary naming is a common programming language issue, introducing verbosity and a complication of the user's mental model. +That is, adding another named type creates another association in the programmer's mind that needs to be kept track of when reading and writing code. +As such, this technique is effective when used sparingly, but can quickly get out of hand if many functions need to return different combinations of types. + +In the latter approach, the designer simulates multiple return values by passing the additional return values as pointer parameters. +The pointer parameters are assigned inside of the routine body to emulate a return. +Using the same example, +\begin{cfa} +int most_frequent(const char * str, char * ret_ch) { + char freqs [26] = { 0 }; + int ret_freq = 0; + for (int i = 0; str[i] != '\0'; ++i) { + if (isalpha(str[i])) { // only count letters + int ch = tolower(str[i]); // convert to lower case + int idx = ch-'a'; + if (++freqs[idx] > ret_freq) { // update on new max + ret_freq = freqs[idx]; + *ret_ch = ch; // assign to out parameter + } + } + } + return ret_freq; // only one value returned directly +} + +const char * str = "hello world"; +char ch; // pre-allocate return value +int freq = most_frequent(str, &ch); // pass return value as out parameter +printf("%s -- %d %c\n", str, freq, ch); +\end{cfa} +Notably, using this approach, the caller is directly responsible for allocating storage for the additional temporary return values, which complicates the call site with a sequence of variable declarations leading up to the call. +Also, while a disciplined use of ©const© can give clues about whether a pointer parameter is going to be used as an out parameter, it is not immediately obvious from only the routine signature whether the callee expects such a parameter to be initialized before the call. +Furthermore, while many C routines that accept pointers are designed so that it is safe to pass ©NULL© as a parameter, there are many C routines that are not null-safe. +On a related note, C does not provide a standard mechanism to state that a parameter is going to be used as an additional return value, which makes the job of ensuring that a value is returned more difficult for the compiler. +Interestingly, there is a subtle bug in the previous example, in that ©ret_ch© is never assigned for a string that does not contain any letters, which can lead to undefined behaviour. +In this particular case, it turns out that the frequency return value also doubles as an error code, where a frequency of 0 means the character return value should be ignored. +Still, not every routine with multiple return values should be required to return an error code, and error codes are easily ignored, so this is not a satisfying solution. +As with the previous approach, this technique can simulate multiple return values, but in practice it is verbose and error prone. + +In \CFA, functions can be declared to return multiple values with an extension to the function declaration syntax. +Multiple return values are declared as a comma-separated list of types in square brackets in the same location that the return type appears in standard C function declarations. +The ability to return multiple values from a function requires a new syntax for the return statement. +For consistency, the return statement in \CFA accepts a comma-separated list of expressions in square brackets. +The expression resolution phase of the \CFA translator ensures that the correct form is used depending on the values being returned and the return type of the current function. +A multiple-returning function with return type ©T© can return any expression that is implicitly convertible to ©T©. +Using the running example, the ©most_frequent© function can be written using multiple return values as such, +\begin{cfa} +[int, char] most_frequent(const char * str) { + char freqs [26] = { 0 }; + int ret_freq = 0; + char ret_ch = 'a'; // arbitrary default value for consistent results + for (int i = 0; str[i] != '\0'; ++i) { + if (isalpha(str[i])) { // only count letters + int ch = tolower(str[i]); // convert to lower case + int idx = ch-'a'; + if (++freqs[idx] > ret_freq) { // update on new max + ret_freq = freqs[idx]; + ret_ch = ch; + } + } + } + return [ret_freq, ret_ch]; +} +\end{cfa} +This approach provides the benefits of compile-time checking for appropriate return statements as in aggregation, but without the required verbosity of declaring a new named type, which precludes the bug seen with out-parameters. + +The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site. +The simplest mechanism for retaining a return value in C is variable assignment. +By assigning the return value into a variable, its value can be retrieved later at any point in the program. +As such, \CFA allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions on the left side. +\begin{cfa} +const char * str = "hello world"; +int freq; +char ch; +[freq, ch] = most_frequent(str); // assign into multiple variables +printf("%s -- %d %c\n", str, freq, ch); +\end{cfa} +It is also common to use a function's output as the input to another function. +\CFA also allows this case, without any new syntax. +When a function call is passed as an argument to another call, the expression resolver attempts to find the best match of actual arguments to formal parameters given all of the possible expression interpretations in the current scope \cite{Bilson03}. +For example, +\begin{cfa} +void process(int); // (1) +void process(char); // (2) +void process(int, char); // (3) +void process(char, int); // (4) + +process(most_frequent("hello world")); // selects (3) +\end{cfa} +In this case, there is only one option for a function named ©most_frequent© that takes a string as input. +This function returns two values, one ©int© and one ©char©. +There are four options for a function named ©process©, but only two that accept two arguments, and of those the best match is (3), which is also an exact match. +This expression first calls ©most_frequent("hello world")©, which produces the values ©3© and ©'l'©, which are fed directly to the first and second parameters of (3), respectively. + +\section{Tuple Expressions} +Multiple-return-value functions provide \CFA with a new syntax for expressing a combination of expressions in the return statement and a combination of types in a function signature. +These notions can be generalized to provide \CFA with \emph{tuple expressions} and \emph{tuple types}. +A tuple expression is an expression producing a fixed-size, ordered list of values of heterogeneous types. +The type of a tuple expression is the tuple of the subexpression types, or a \emph{tuple type}. +In \CFA, a tuple expression is denoted by a comma-separated list of expressions enclosed in square brackets. +For example, the expression ©[5, 'x', 10.5]© has type ©[int, char, double]©. +The previous expression has 3 \emph{components}. +Each component in a tuple expression can be any \CFA expression, including another tuple expression. +The order of evaluation of the components in a tuple expression is unspecified, to allow a compiler the greatest flexibility for program optimization. +It is, however, guaranteed that each component of a tuple expression is evaluated for side-effects, even if the result is not used. +Multiple-return-value functions can equivalently be called \emph{tuple-returning functions}. + +\subsection{Tuple Variables} +The call-site of the ©most_frequent© routine has a notable blemish, in that it required the preallocation of return variables in a manner similar to the aliasing example, since it is impossible to declare multiple variables of different types in the same declaration in standard C. +In \CFA, it is possible to overcome this restriction by declaring a \emph{tuple variable}. +\begin{cfa}[emph=ret, emphstyle=\color{red}] +const char * str = "hello world"; +[int, char] ret = most_frequent(str); // initialize tuple variable +printf("%s -- %d %c\n", str, ret); +\end{cfa} +It is now possible to accept multiple values into a single piece of storage, in much the same way that it was previously possible to pass multiple values from one function call to another. +These variables can be used in any of the contexts where a tuple expression is allowed, such as in the ©printf© function call. +As in the ©process© example, the components of the tuple value are passed as separate parameters to ©printf©, allowing very simple printing of tuple expressions. +One way to access the individual components is with a simple assignment, as in previous examples. +\begin{cfa} +int freq; +char ch; +[freq, ch] = ret; +\end{cfa} + +\begin{sloppypar} +In addition to variables of tuple type, it is also possible to have pointers to tuples, and arrays of tuples. +Tuple types can be composed of any types, except for array types, since array assignment is disallowed, which makes tuple assignment difficult when a tuple contains an array. +\begin{cfa} +[double, int] di; +[double, int] * pdi +[double, int] adi[10]; +\end{cfa} +This examples declares a variable of type ©[double, int]©, a variable of type pointer to ©[double, int]©, and an array of ten ©[double, int]©. +\end{sloppypar} + +\subsection{Tuple Indexing} + +At times, it is desirable to access a single component of a tuple-valued expression without creating unnecessary temporary variables to assign to. +Given a tuple-valued expression ©e© and a compile-time constant integer $i$ where $0 \leq i < n$, where $n$ is the number of components in ©e©, ©e.i© accesses the $i$\textsuperscript{th} component of ©e©. +For example, +\begin{cfa} +[int, double] x; +[char *, int] f(); +void g(double, int); +[int, double] * p; + +int y = x.0; §\C{// access int component of x}§ +y = f().1; §\C{// access int component of f}§ +p->0 = 5; §\C{// access int component of tuple pointed-to by p}§ +g( x.1, x.0 ); §\C{// rearrange x to pass to g}§ +double z = [x, f()].0.1; §\C{// access second component of first component of tuple expression}§ +\end{cfa} +As seen above, tuple-index expressions can occur on any tuple-typed expression, including tuple-returning functions, square-bracketed tuple expressions, and other tuple-index expressions, provided the retrieved component is also a tuple. +This feature was proposed for \KWC but never implemented \cite[p.~45]{Till89}. + +\subsection{Flattening and Structuring} +As evident in previous examples, tuples in \CFA do not have a rigid structure. +In function call contexts, tuples support implicit flattening and restructuring conversions. +Tuple flattening recursively expands a tuple into the list of its basic components. +Tuple structuring packages a list of expressions into a value of tuple type. +\begin{cfa} +int f(int, int); +int g([int, int]); +int h(int, [int, int]); +[int, int] x; +int y; + +f(x); // flatten +g(y, 10); // structure +h(x, y); // flatten & structure +\end{cfa} +In \CFA, each of these calls is valid. +In the call to ©f©, ©x© is implicitly flattened so that the components of ©x© are passed as the two arguments to ©f©. +For the call to ©g©, the values ©y© and ©10© are structured into a single argument of type ©[int, int]© to match the type of the parameter of ©g©. +Finally, 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]©. +The flexible structure of tuples permits a simple and expressive function-call syntax to work seamlessly with both single- and multiple-return-value functions, and with any number of arguments of arbitrarily complex structure. + +In \KWC \cite{Buhr94a,Till89}, there were 4 tuple coercions: opening, closing, flattening, and structuring. +Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value. +Flattening coerces a nested tuple into a flat tuple, \ie it takes a tuple with tuple components and expands it into a tuple with only non-tuple components. +Structuring moves in the opposite direction, \ie it takes a flat tuple value and provides structure by introducing nested tuple components. + +In \CFA, the design has been simplified to require only the two conversions previously described, which trigger only in function call and return situations. +This simplification is a primary contribution of this thesis to the design of tuples in \CFA. +Specifically, the expression resolution algorithm examines all of the possible alternatives for an expression to determine the best match. +In resolving a function call expression, each combination of function value and list of argument alternatives is examined. +Given a particular argument list and function value, the list of argument alternatives is flattened to produce a list of non-tuple valued expressions. +Then the flattened list of expressions is compared with each value in the function's parameter list. +If the parameter's type is not a tuple type, then the current argument value is unified with the parameter type, and on success the next argument and parameter are examined. +If the parameter's type is a tuple type, then the structuring conversion takes effect, recursively applying the parameter matching algorithm using the tuple's component types as the parameter list types. +Assuming a successful unification, eventually the algorithm gets to the end of the tuple type, which causes all of the matching expressions to be consumed and structured into a tuple expression. +For example, in +\begin{cfa} +int f(int, [double, int]); +f([5, 10.2], 4); +\end{cfa} +There is only a single definition of ©f©, and 3 arguments with only single interpretations. +First, the argument alternative list ©[5, 10.2], 4© is flattened to produce the argument list ©5, 10.2, 4©. +Next, the parameter matching algorithm begins, with $P = $©int© and $A = $©int©, which unifies exactly. +Moving to the next parameter and argument, $P = $©[double, int]© and $A = $©double©. +This time, the parameter is a tuple type, so the algorithm applies recursively with $P' = $©double© and $A = $©double©, which unifies exactly. +Then $P' = $©int© and $A = $©double©, which again unifies exactly. +At this point, the end of $P'$ has been reached, so the arguments ©10.2, 4© are structured into the tuple expression ©[10.2, 4]©. +Finally, the end of the parameter list $P$ has also been reached, so the final expression is ©f(5, [10.2, 4])©. + +\section{Tuple Assignment} +\label{s:TupleAssignment} +An assignment where the left side of the assignment operator has a tuple type is called tuple assignment. +There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a non-tuple type, called \emph{Multiple} and \emph{Mass} Assignment, respectively. +\begin{cfa} +int x; +double y; +[int, double] z; +[y, x] = 3.14; // mass assignment +[x, y] = z; // multiple assignment +z = 10; // mass assignment +z = [x, y]; // multiple assignment +\end{cfa} +Let $L_i$ for $i$ in $[0, n)$ represent each component of the flattened left side, $R_i$ represent each component of the flattened right side of a multiple assignment, and $R$ represent the right side of a mass assignment. + +For a multiple assignment to be valid, both tuples must have the same number of elements when flattened. +For example, the following is invalid because the number of components on the left does not match the number of components on the right. +\begin{cfa} +[int, int] x, y, z; +[x, y] = z; // multiple assignment, invalid 4 != 2 +\end{cfa} +Multiple assignment assigns $R_i$ to $L_i$ for each $i$. +That is, ©?=?(&$L_i$, $R_i$)© must be a well-typed expression. +In the previous example, ©[x, y] = z©, ©z© is flattened into ©z.0, z.1©, and the assignments ©x = z.0© and ©y = z.1© happen. + +A mass assignment assigns the value $R$ to each $L_i$. +For a mass assignment to be valid, ©?=?(&$L_i$, $R$)© must be a well-typed expression. +These semantics differ from C cascading assignment (\eg ©a=b=c©) in that conversions are applied to $R$ in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment. +For example, ©[y, x] = 3.14© performs the assignments ©y = 3.14© and ©x = 3.14©, which results in the value ©3.14© in ©y© and the value ©3© in ©x©. +On the other hand, the C cascading assignment ©y = x = 3.14© performs the assignments ©x = 3.14© and ©y = x©, which results in the value ©3© in ©x©, and as a result the value ©3© in ©y© as well. + +Both kinds of tuple assignment have parallel semantics, such that each value on the left side and right side is evaluated \emph{before} any assignments occur. +As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function. +\begin{cfa} +int x = 10, y = 20; +[x, y] = [y, x]; +\end{cfa} +After executing this code, ©x© has the value ©20© and ©y© has the value ©10©. + +In \CFA, tuple assignment is an expression where the result type is the type of the left side of the assignment, as in normal assignment. +That is, a tuple assignment produces the value of the left-hand side after assignment. +These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted. +These semantics are a change from the original tuple design in \KWC \cite{Till89}, wherein tuple assignment was a statement that allows cascading assignments as a special case. +Restricting tuple assignment to statements was an attempt to to fix what was seen as a problem with side-effects, wherein assignment can be used in many different locations, such as in function-call argument position. +While permitting assignment as an expression does introduce the potential for subtle complexities, it is impossible to remove assignment expressions from \CFA without affecting backwards compatibility. +Furthermore, there are situations where permitting assignment as an expression improves readability by keeping code succinct and reducing repetition, and complicating the definition of tuple assignment puts a greater cognitive burden on the user. +In another language, tuple assignment as a statement could be reasonable, but it would be inconsistent for tuple assignment to be the only kind of assignment that is not an expression. +In addition, \KWC permits the compiler to optimize tuple assignment as a block copy, since it does not support user-defined assignment operators. +This optimization could be implemented in \CFA, but it requires the compiler to verify that the selected assignment operator is trivial. + +The following example shows multiple, mass, and cascading assignment used in one expression +\begin{cfa} + int a, b; + double c, d; + [void] f([int, int]); + f([c, a] = [b, d] = 1.5); // assignments in parameter list +\end{cfa} +The tuple expression begins with a mass assignment of ©1.5© into ©[b, d]©, which assigns ©1.5© into ©b©, which is truncated to ©1©, and ©1.5© into ©d©, producing the tuple ©[1, 1.5]© as a result. +That tuple is used as the right side of the multiple assignment (\ie, ©[c, a] = [1, 1.5]©) that assigns ©1© into ©c© and ©1.5© into ©a©, which is truncated to ©1©, producing the result ©[1, 1]©. +Finally, the tuple ©[1, 1]© is used as an expression in the call to ©f©. + +\subsection{Tuple Construction} +Tuple construction and destruction follow the same rules and semantics as tuple assignment, except that in the case where there is no right side, the default constructor or destructor is called on each component of the tuple. +As constructors and destructors did not exist in previous versions of \CFA or in \KWC, this is a primary contribution of this thesis to the design of tuples. +\begin{cfa} +struct S; +void ?{}(S *); // (1) +void ?{}(S *, int); // (2) +void ?{}(S * double); // (3) +void ?{}(S *, S); // (4) + +[S, S] x = [3, 6.28]; // uses (2), (3), specialized constructors +[S, S] y; // uses (1), (1), default constructor +[S, S] z = x.0; // uses (4), (4), copy constructor +\end{cfa} +In this example, ©x© is initialized by the multiple constructor calls ©?{}(&x.0, 3)© and ©?{}(&x.1, 6.28)©, while ©y© is initialized by two default constructor calls ©?{}(&y.0)© and ©?{}(&y.1)©. +©z© is initialized by mass copy constructor calls ©?{}(&z.0, x.0)© and ©?{}(&z.1, x.0)©. +Finally, ©x©, ©y©, and ©z© are destructed, \ie the calls ©^?{}(&x.0)©, ©^?{}(&x.1)©, ©^?{}(&y.0)©, ©^?{}(&y.1)©, ©^?{}(&z.0)©, and ©^?{}(&z.1)©. + +It is possible to define constructors and assignment functions for tuple types that provide new semantics, if the existing semantics do not fit the needs of an application. +For example, the function ©void ?{}([T, U] *, S);© can be defined to allow a tuple variable to be constructed from a value of type ©S©. +\begin{cfa} +struct S { int x; double y; }; +void ?{}([int, double] * this, S s) { + this->0 = s.x; + this->1 = s.y; +} +\end{cfa} +Due to the structure of generated constructors, it is possible to pass a tuple to a generated constructor for a type with a member prefix that matches the type of the tuple. +For example, +\begin{cfa} +struct S { int x; double y; int z }; +[int, double] t; +S s = t; +\end{cfa} +The initialization of ©s© with ©t© works by default because ©t© is flattened into its components, which satisfies the generated field constructor ©?{}(S *, int, double)© to initialize the first two values. + +\section{Member-Access Tuple Expression} +\label{s:MemberAccessTuple} +It is possible to access multiple fields from a single expression using a \emph{Member-Access Tuple Expression}. +The result is a single tuple-valued expression whose type is the tuple of the types of the members. +For example, +\begin{cfa} +struct S { int x; double y; char * z; } s; +s.[x, y, z]; +\end{cfa} +Here, the type of ©s.[x, y, z]© is ©[int, double, char *]©. +A member tuple expression has the form ©a.[x, y, z];© where ©a© is an expression with type ©T©, where ©T© supports member access expressions, and ©x, y, z© are all members of ©T© with types ©T$_x$©, ©T$_y$©, and ©T$_z$© respectively. +Then the type of ©a.[x, y, z]© is ©[T_x, T_y, T_z]©. + +Since 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 components, drop components, duplicate components, etc.). +\begin{cfa} +[int, int, long, double] x; +void f(double, long); + +f(x.[0, 3]); // f(x.0, x.3) +x.[0, 1] = x.[1, 0]; // [x.0, x.1] = [x.1, x.0] +[long, int, long] y = x.[2, 0, 2]; +\end{cfa} + +It is possible for a member tuple expression to contain other member access expressions. +For example, +\begin{cfa} +struct A { double i; int j; }; +struct B { int * k; short l; }; +struct C { int x; A y; B z; } v; +v.[x, y.[i, j], z.k]; +\end{cfa} +This expression is equivalent to ©[v.x, [v.y.i, v.y.j], v.z.k]©. +That is, the aggregate expression is effectively distributed across the tuple, which allows simple and easy access to multiple components in an aggregate, without repetition. +It is guaranteed that the aggregate expression to the left of the ©.© in a member tuple expression is evaluated exactly once. +As such, it is safe to use member tuple expressions on the result of a side-effecting function. +\begin{cfa} +[int, float, double] f(); +[double, float] x = f().[2, 1]; +\end{cfa} + +In \KWC, member tuple expressions are known as \emph{record field tuples} \cite{Till89}. +Since \CFA permits these tuple-access expressions using structures, unions, and tuples, \emph{member tuple expression} or \emph{field tuple expression} is more appropriate. + +It is possible to extend member-access expressions further. +Currently, a member-access expression whose member is a name requires that the aggregate is a structure or union, while a constant integer member requires the aggregate to be a tuple. +In the interest of orthogonal design, \CFA could apply some meaning to the remaining combinations as well. +For example, +\begin{cfa} +struct S { int x, y; } s; +[S, S] z; + +s.x; // access member +z.0; // access component + +s.1; // ??? +z.y; // ??? +\end{cfa} +One possibility is for ©s.1© to select the second member of ©s©. +Under this interpretation, it becomes possible to not only access members of a struct by name, but also by position. +Likewise, it seems natural to open this mechanism to enumerations as well, wherein the left side would be a type, rather than an expression. +One benefit of this interpretation is familiarity, since it is extremely reminiscent of tuple-index expressions. +On the other hand, it could be argued that this interpretation is brittle in that changing the order of members or adding new members to a structure becomes a brittle operation. +This problem is less of a concern with tuples, since modifying a tuple affects only the code that directly uses the tuple, whereas modifying a structure has far reaching consequences for every instance of the structure. + +As for ©z.y©, one interpretation is to extend the meaning of member tuple expressions. +That is, currently the tuple must occur as the member, \ie to the right of the dot. +Allowing tuples to the left of the dot could distribute the member across the elements of the tuple, in much the same way that member tuple expressions distribute the aggregate across the member tuple. +In this example, ©z.y© expands to ©[z.0.y, z.1.y]©, allowing what is effectively a very limited compile-time field-sections map operation, where the argument must be a tuple containing only aggregates having a member named ©y©. +It is questionable how useful this would actually be in practice, since structures often do not have names in common with other structures, and further this could cause maintainability issues in that it encourages programmers to adopt very simple naming conventions to maximize the amount of overlap between different types. +Perhaps more useful would be to allow arrays on the left side of the dot, which would likewise allow mapping a field access across the entire array, producing an array of the contained fields. +The immediate problem with this idea is that C arrays do not carry around their size, which would make it impossible to use this extension for anything other than a simple stack allocated array. + +Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member-access expressions versus member-tuple expressions. +\begin{cfa} +struct { int x, y; }; +[S, S] z; +z.[x, y]; // ??? +// => [z.0, z.1].[x, y] +// => [z.0.x, z.0.y, z.1.x, z.1.y] +// or +// => [z.x, z.y] +// => [[z.0, z.1].x, [z.0, z.1].y] +// => [z.0.x, z.1.x, z.0.y, z.1.y] +\end{cfa} +Depending on exactly how the two tuples are combined, different results can be achieved. +As such, a specific ordering would need to be imposed to make this feature useful. +Furthermore, this addition moves a member-tuple expression's meaning from being clear statically to needing resolver support, since the member name needs to be distributed appropriately over each member of the tuple, which could itself be a tuple. + +A second possibility is for \CFA to have named tuples, as they exist in Swift and D. +\begin{cfa} +typedef [int x, int y] Point2D; +Point2D p1, p2; +p1.x + p1.y + p2.x + p2.y; +p1.0 + p1.1 + p2.0 + p2.1; // equivalent +\end{cfa} +In this simpler interpretation, a tuple type carries with it a list of possibly empty identifiers. +This approach fits naturally with the named return-value feature, and would likely go a long way towards implementing it. + +Ultimately, the first two extensions introduce complexity into the model, with relatively little perceived benefit, and so were dropped from consideration. +Named tuples are a potentially useful addition to the language, provided they can be parsed with a reasonable syntax. + + +\section{Casting} +In C, the cast operator is used to explicitly convert between types. +In \CFA, the cast operator has a secondary use, which is type ascription, since it forces the expression resolution algorithm to choose the lowest cost conversion to the target type. +That 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. +\begin{cfa} +int f(); // (1) +double f(); // (2) + +f(); // ambiguous - (1),(2) both equally viable +(int)f(); // choose (2) +\end{cfa} +Since casting is a fundamental operation in \CFA, casts need to be given a meaningful interpretation in the context of tuples. +Taking a look at standard C provides some guidance with respect to the way casts should work with tuples. +\begin{cfa}[numbers=left] +int f(); +void g(); + +(void)f(); // valid, ignore results +(int)g(); // invalid, void cannot be converted to int + +struct A { int x; }; +(struct A)f(); // invalid, int cannot be converted to A +\end{cfa} +In C, line 4 is a valid cast, which calls ©f© and discards its result. +On the other hand, line 5 is invalid, because ©g© does not produce a result, so requesting an ©int© to materialize from nothing is nonsensical. +Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite[p.~91]{C11}. +For consistency, this implies that any case 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. + +Formally, 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$. +Excess 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. +This discarding naturally follows the way that a cast to void works in C. + +For example, +\begin{cfa} + [int, int, int] f(); + [int, [int, int], int] g(); + + ([int, double])f(); // (1) valid + ([int, int, int])g(); // (2) valid + ([void, [int, int]])g(); // (3) valid + ([int, int, int, int])g(); // (4) invalid + ([int, [int, int, int]])g(); // (5) invalid +\end{cfa} + +(1) discards the last element of the return value and converts the second element to type double. +Since ©int© is effectively a 1-element tuple, (2) discards the second component of the second element of the return value of ©g©. +If ©g© is free of side effects, this is equivalent to ©[(int)(g().0), (int)(g().1.0), (int)(g().2)]©. +Since ©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)]©). +% will this always hold true? probably, as constructors should give all of the conversion power we need. if casts become function calls, what would they look like? would need a way to specify the target type, which seems awkward. Also, C++ basically only has this because classes are closed to extension, while we don't have that problem (can have floating constructors for any type). +Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions. +As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3. +Similarly, (5) is invalid because the cast ©([int, int, int])(g().1)© is invalid. +That is, it is invalid to cast ©[int, int]© to ©[int, int, int]©. + +\section{Polymorphism} +Due to the implicit flattening and structuring conversions involved in argument passing, ©otype© and ©dtype© parameters are restricted to matching only with non-tuple types. +The integration of polymorphism, type assertions, and monomorphic specialization of tuple-assertions are a primary contribution of this thesis to the design of tuples. +\begin{cfa} +forall(otype T, dtype U) +void f(T x, U * y); + +f([5, "hello"]); +\end{cfa} +In this example, ©[5, "hello"]© is flattened, so that the argument list appears as ©5, "hello"©. +The argument matching algorithm binds ©T© to ©int© and ©U© to ©const char©, and calls the function as normal. + +Tuples can contain otype and dtype components. +For example, a plus operator can be written to add two triples of a type together. +\begin{cfa} +forall(otype T | { T ?+?(T, T); }) +[T, T, T] ?+?([T, T, T] x, [T, T, T] y) { + return [x.0+y.0, x.1+y.1, x.2+y.2]; +} +[int, int, int] x; +int i1, i2, i3; +[i1, i2, i3] = x + ([10, 20, 30]); +\end{cfa} +Note that due to the implicit tuple conversions, this function is not restricted to the addition of two triples. +A call to this plus operator type checks as long as a total of 6 non-tuple arguments are passed after flattening, and all of the arguments have a common type that can bind to ©T©, with a pairwise ©?+?© over ©T©. +For example, these expressions also succeed and produce the same value. +\begin{cfa} +([x.0, x.1]) + ([x.2, 10, 20, 30]); // x + ([10, 20, 30]) +x.0 + ([x.1, x.2, 10, 20, 30]); // x + ([10, 20, 30]) +\end{cfa} +This presents a potential problem if structure is important, as these three expressions look like they should have different meanings. +Furthermore, these calls can be made ambiguous by introducing seemingly different functions. +\begin{cfa} +forall(otype T | { T ?+?(T, T); }) +[T, T, T] ?+?([T, T] x, [T, T, T, T]); +forall(otype T | { T ?+?(T, T); }) +[T, T, T] ?+?(T x, [T, T, T, T, T]); +\end{cfa} +It is also important to note that these calls could be disambiguated if the function return types were different, as they likely would be for a reasonable implementation of ©?+?©, since the return type is used in overload resolution. +Still, these semantics are a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate. +These issues could be rectified by applying an appropriate conversion cost to the structuring and flattening conversions, which are currently 0-cost conversions in the expression resolver. +Care would be needed in this case to ensure that exact matches do not incur such a cost. +\begin{cfa} +void f([int, int], int, int); + +f([0, 0], 0, 0); // no cost +f(0, 0, 0, 0); // cost for structuring +f([0, 0,], [0, 0]); // cost for flattening +f([0, 0, 0], 0); // cost for flattening and structuring +\end{cfa} + +Until this point, it has been assumed that assertion arguments must match the parameter type exactly, modulo polymorphic specialization (\ie, no implicit conversions are applied to assertion arguments). +This decision presents a conflict with the flexibility of tuples. +\subsection{Assertion Inference} +\begin{cfa} +int f([int, double], double); +forall(otype T, otype U | { T f(T, U, U); }) +void g(T, U); +g(5, 10.21); +\end{cfa} +If assertion arguments must match exactly, then the call to ©g© cannot be resolved, since the expected type of ©f© is flat, while the only ©f© in scope requires a tuple type. +Since tuples are fluid, this requirement reduces the usability of tuples in polymorphic code. +To ease this pain point, function parameter and return lists are flattened for the purposes of type unification, which allows the previous example to pass expression resolution. + +This relaxation is made possible by extending the existing thunk generation scheme, as described by Bilson \cite{Bilson03}. +Now, 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. +\begin{cfa} +int _thunk(int _p0, double _p1, double _p2) { + return f([_p0, _p1], _p2); +} +\end{cfa} +Essentially, this provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism. @@ -3231,5 +3783,5 @@ \section{Auto Type-Inferencing} -Auto type-inferencing occurs in a declaration where a variable's type is inferred from its initialization expression type. +Auto type-inferencing occurs in a declaration where a variable's type is inferred from its initialization ex\-pression type. \begin{quote2} \begin{tabular}{@{}l@{\hspace{3em}}ll@{}} @@ -3260,5 +3812,5 @@ \begin{itemize} \item -preventing having to determine or write out long generic types, +preventing having to determine or write long generic types, \item ensure secondary variables, related to a primary variable, always have the same type. @@ -3284,6 +3836,6 @@ There is also the conundrum in type inferencing of when to \emph{\Index{brand}} a type. That is, when is the type of the variable more important than the type of its initialization expression. -For example, if a change is made in an initialization expression, it can cause hundreds or thousands of cascading type changes and/or errors. -At some point, a programmer wants the type of the variable to remain constant and the expression to be in error when it changes. +For example, if a change is made in an initialization expression, it can cause significant cascading type changes and/or errors. +At some point, a variable type needs to remain constant and the expression to be in error when it changes. Given ©typedef© and ©typeof© in \CFA, and the strong need to use the type of left-hand side in inferencing, auto type-inferencing is not supported at this time. @@ -3498,86 +4050,4 @@ } \end{cfa} -\end{comment} - - -\subsection{Memory Management} - - -\subsubsection{Manual Memory Management} - -Using malloc and free to dynamically allocate memory exposes several potential, and common, errors. -First, malloc breaks type safety because it returns a pointer to void. -There is no relationship between the type that the returned pointer is cast to, and the amount of memory allocated. -This problem is solved with a type-safe malloc. -Do.s type-safe malloc does not take any arguments for size. -Instead, it infers the type based on the return value, and then allocates space for the inferred type. - -\begin{cfa} -float *f = malloc(); // allocates the size of a float - -struct S { - int i, j, k; -}; - -struct S *s = malloc(); // allocates the size of a struct S -\end{cfa} - -In addition to the improved malloc, \CFA also provides a technique for combining allocation and initialization into one step, using the new function. -For all constructors defined for a given type (see Operator Overloading), a corresponding call to new can be used to allocate and construct that type. - -\begin{cfa} -type Complex = struct { - float real; - float imag; -}; - -// default constructor - -void ?{}(Complex &c) { - c.real = 0.0; - c.imag = 0.0; -} - - - -// 2 parameter constructor - -void ?{}(Complex &c, float real, float imag) { - c.real = real; - c.imag = imag; -} - - -int main() { - Complex c1; // No constructor is called - Complex c2{}; // Default constructor called - Complex c3{1.0, -1.0}; // 2 parameter constructor is called - - Complex *p1 = malloc(); // allocate - Complex *p2 = new(); // allocate + default constructor - Complex *p3 = new(0.5, 1.0); // allocate + 2 param constructor -} -\end{cfa} - - -\subsubsection{Automatic Memory Management} - -\CFA may also support automatic memory management to further improve safety. -If the compiler can insert all of the code needed to manage dynamically allocated memory (automatic reference counting), then developers can avoid problems with dangling pointers, double frees, memory leaks, etc. -This feature requires further investigation. -\CFA will not have a garbage collector, but might use some kind of region-based memory management. - - -\begin{comment} -\subsection{Unsafe C Constructs} - -C programmers are able to access all of the low-level tricks that are sometimes needed for close-to-the-hardware programming. -Some of these practices however are often error-prone and difficult to read and maintain. -Since \CFA is designed to be safer than C, such constructs are disallowed in \CFA code. -If a programmer wants to use one of these unsafe C constructs, the unsafe code must be contained in a C linkage block (see Interoperability), which will be compiled like C code. -This block means that the user is telling the tools, .I know this is unsafe, but I.m going to do it anyway.. - -The exact set of unsafe C constructs that will be disallowed in \CFA has not yet been decided, but is sure to include pointer arithmetic, pointer casting, etc. -Once the full set is decided, the rules will be listed here. \end{comment} @@ -3803,173 +4273,4 @@ \label{f:SimpleTasks} \end{figure} - - -\begin{comment} -\begin{cfa} -type Adder = task { - int *row; - int size; - int &subtotal; -} -\end{cfa} - -A task may define a constructor, which will be called upon allocation and run on the caller.s thread. -A destructor may also be defined, which is called at deallocation (when a dynamic object is deleted or when a local object goes out of scope). -After a task is allocated and initialized, its thread is spawned implicitly and begins executing in its function call method. -All tasks must define this function call method, with a void return value and no additional parameters, or the compiler will report an error. -Below are example functions for the above Adder task, and its usage to sum up a matrix on multiple threads. -(Note that this example is designed to display the syntax and functionality, not the best method to solve this problem) -\begin{cfa} -void ?{}(Adder &a, int r[], int s, int &st) { // constructor - a.row = r; - a.size = s; - a.subtotal = st; -} - -// implicitly spawn thread and begin execution here - -void ?()(Adder &a) { - int c; - subtotal = 0; - for (c=0; c 0 + long int numerator, denominator; §\C{// invariant: denominator > 0}§ }; // Rational