source: doc/rob_thesis/tuples.tex @ 93afb96

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 93afb96 was 93afb96, checked in by Rob Schluntz <rschlunt@…>, 8 years ago

fix typos in thesis

  • Property mode set to 100644
File size: 68.2 KB
Line 
1%======================================================================
2\chapter{Tuples}
3%======================================================================
4
5\section{Introduction}
6% TODO: named return values are not currently implemented in CFA - tie in with named tuples? (future work)
7% TODO: no passing input parameters by assignment, instead will have reference types => this is not a very C-like model and greatly complicates syntax for likely little gain (and would cause confusion with already supported return-by-rerefence)
8% TODO: tuples are allowed in expressions, exact meaning is defined by operator overloading (e.g. can add tuples). An important caveat to note is that it is currently impossible to allow adding two triples but prevent adding a pair with a quadruple (single flattening/structuring conversions are implicit, only total number of components matters). May be able to solve this with more nuanced conversion rules (future work)
9% TODO: benefits (conclusion) by Till: reduced number of variables and statements; no specified order of execution for multiple assignment (more optimzation freedom); can store parameter lists in variable; MRV routines (natural code); more convenient assignment statements; simple and efficient access of record fields; named return values more legible and efficient in use of storage
10
11\section{Multiple-Return-Value Functions}
12\label{s:MRV_Functions}
13In standard C, functions can return at most one value.
14This restriction results in code which emulates functions with multiple return values by \emph{aggregation} or by \emph{aliasing}.
15In the former situation, the function designer creates a record type that combines all of the return values into a single type.
16For example, consider a function returning the most frequently occuring letter in a string, and its frequency.
17% TODO: consider simplifying the example!
18%   Two things I like about this example:
19%   * it uses different types to illustrate why an array is insufficient (this is not necessary, but is nice)
20%   * it's complicated enough to show the uninitialized pitfall that exists in the aliasing example.
21%   Still, it may be a touch too complicated. Is there a simpler example with these two properties?
22\begin{cfacode}
23struct mf_ret {
24  int freq;
25  char ch;
26};
27
28struct mf_ret most_frequent(const char * str) {
29  char freqs [26] = { 0 };
30  struct mf_ret ret = { 0, 'a' };
31  for (int i = 0; str[i] != '\0'; ++i) {
32    if (isalpha(str[i])) {        // only count letters
33      int ch = tolower(str[i]);   // convert to lower case
34      int idx = ch-'a';
35      if (++freqs[idx] > ret.freq) {  // update on new max
36        ret.freq = freqs[idx];
37        ret.ch = ch;
38      }
39    }
40  }
41  return ret;
42}
43
44const char * str = "hello world";
45struct mf_ret ret = most_frequent(str);
46printf("%s -- %d %c\n", str, ret.freq, ret.ch);
47\end{cfacode}
48Of note, the designer must come up with a name for the return type and for each of its fields.
49Unnecessary naming is a common programming language issue, introducing verbosity and a complication of the user's mental model.
50That 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.
51As 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.
52
53In the latter approach, the designer simulates multiple return values by passing the additional return values as pointer parameters.
54The pointer parameters are assigned inside of the routine body to emulate a return.
55Using the same example,
56\begin{cfacode}
57int most_frequent(const char * str, char * ret_ch) {
58  char freqs [26] = { 0 };
59  int ret_freq = 0;
60  for (int i = 0; str[i] != '\0'; ++i) {
61    if (isalpha(str[i])) {        // only count letters
62      int ch = tolower(str[i]);   // convert to lower case
63      int idx = ch-'a';
64      if (++freqs[idx] > ret_freq) {  // update on new max
65        ret_freq = freqs[idx];
66        *ret_ch = ch;   // assign to out parameter
67      }
68    }
69  }
70  return ret_freq;  // only one value returned directly
71}
72
73const char * str = "hello world";
74char ch;                            // pre-allocate return value
75int freq = most_frequent(str, &ch); // pass return value as parameter
76printf("%s -- %d %c\n", str, freq, ch);
77\end{cfacode}
78Notably, using this approach, the caller is directly responsible for allocating storage for the additional temporary return values.
79This complicates the call site with a sequence of variable declarations leading up to the call.
80Also, 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.
81Furthermore, 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.
82On 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.
83There 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.
84As with the previous approach, this technique can simulate multiple return values, but in practice it is verbose and error prone.
85
86In \CFA, functions can be declared to return multiple values with an extension to the function declaration syntax.
87Multiple 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.
88The ability to return multiple values from a function requires a new syntax for the return statement.
89For consistency, the return statement in \CFA accepts a comma-separated list of expressions in square brackets.
90The 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.
91A multiple-returning function with return type @T@ can return any expression that is implicitly convertible to @T@.
92Using the running example, the @most_frequent@ function can be written in using multiple return values as such,
93\begin{cfacode}
94[int, char] most_frequent(const char * str) {
95  char freqs [26] = { 0 };
96  int ret_freq = 0;
97  char ret_ch = 'a';
98  for (int i = 0; str[i] != '\0'; ++i) {
99    if (isalpha(str[i])) {        // only count letters
100      int ch = tolower(str[i]);   // convert to lower case
101      int idx = ch-'a';
102      if (++freqs[idx] > ret_freq) {  // update on new max
103        ret_freq = freqs[idx];
104        ret_ch = ch;
105      }
106    }
107  }
108  return [ret_freq, ret_ch];
109}
110\end{cfacode}
111This 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.
112
113The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site.
114The simplest mechanism for retaining a return value in C is variable assignment.
115By assigning the return value into a variable, its value can be retrieved later at any point in the program.
116As such, \CFA allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions on the left side.
117\begin{cfacode}
118const char * str = "hello world";
119int freq;
120char ch;
121[freq, ch] = most_frequent(str);  // assign into multiple variables
122printf("%s -- %d %c\n", str, freq, ch);
123\end{cfacode}
124It is also common to use a function's output as the input to another function.
125\CFA also allows this case, without any new syntax.
126When 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}.
127For example,
128\begin{cfacode}
129void process(int);       // (1)
130void process(char);      // (2)
131void process(int, char); // (3)
132void process(char, int); // (4)
133
134process(most_frequent("hello world"));  // selects (3)
135\end{cfacode}
136In this case, there is only one option for a function named @most_frequent@ that takes a string as input.
137This function returns two values, one @int@ and one @char@.
138There are four options for a function named @process@, but only two which accept two arguments, and of those the best match is (3), which is also an exact match.
139This 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.
140
141\section{Tuple Expressions}
142Multiple-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.
143These notions can be generalized to provide \CFA with \emph{tuple expressions} and \emph{tuple types}.
144A tuple expression is an expression producing a fixed-size, ordered list of values of heterogeneous types.
145The type of a tuple expression is the tuple of the subexpression types, or a \emph{tuple type}.
146In \CFA, a tuple expression is denoted by a comma-separated list of expressions enclosed in square brackets.
147For example, the expression @[5, 'x', 10.5]@ has type @[int, char, double]@.
148The previous expression has 3 \emph{components}.
149Each component in a tuple expression can be any \CFA expression, including another tuple expression.
150% TODO: Tuple expressions can appear anywhere that any other expression can appear (...?)
151The order of evaluation of the components in a tuple expression is unspecified, to allow a compiler the greatest flexibility for program optimization.
152It is, however, guaranteed that each component of a tuple expression is evaluated for side-effects, even if the result is not used.
153Multiple-return-value functions can equivalently be called \emph{tuple-returning functions}.
154% TODO: does this statement still apply, and if so to what extent?
155%   Tuples are a compile-time phenomenon and have little to no run-time presence.
156
157\subsection{Tuple Variables}
158The 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.
159In \CFA, it is possible to overcome this restriction by declaring a \emph{tuple variable}.
160\begin{cfacode}[emph=ret, emphstyle=\color{red}]
161const char * str = "hello world";
162[int, char] ret = most_frequent(str);  // initialize tuple variable
163printf("%s -- %d %c\n", str, ret);
164\end{cfacode}
165It 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.
166These variables can be used in any of the contexts where a tuple expression is allowed, such as in the @printf@ function call.
167As in the @process@ example, the components of the tuple value are passed as separate parameters to @printf@, allowing very simple printing of tuple expressions.
168If the individual components are required, they can be extracted with a simple assignment, as in previous examples.
169\begin{cfacode}
170int freq;
171char ch;
172[freq, ch] = ret;
173\end{cfacode}
174
175In addition to variables of tuple type, it is also possible to have pointers to tuples, and arrays of tuples.
176Tuple types can be composed of any types, except for array types, since arrays do not carry their size around, which makes tuple assignment difficult when a tuple contains an array.
177\begin{cfacode}
178[double, int] di;
179[double, int] * pdi
180[double, int] adi[10];
181\end{cfacode}
182This examples declares a variable of type @[double, int]@, a variable of type pointer to @[double, int]@, and an array of ten @[double, int]@.
183
184\subsection{Tuple Indexing}
185At times, it is desirable to access a single component of a tuple-valued expression without creating unnecessary temporary variables to assign to.
186Given 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@.
187For example,
188\begin{cfacode}
189[int, double] x;
190[char *, int] f();
191void g(double, int);
192[int, double] * p;
193
194int y = x.0;              // access int component of x
195y = f().1;                // access int component of f
196p->0 = 5;                 // access int component of tuple pointed-to by p
197g(x.1, x.0);              // rearrange x to pass to g
198double z = [x, f()].0.1;  // access second component of first component
199                          // of tuple expression
200\end{cfacode}
201As 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.
202This feature was proposed for \KWC but never implemented \cite[p.~45]{Till89}.
203
204\subsection{Flattening and Structuring}
205As evident in previous examples, tuples in \CFA do not have a rigid structure.
206In function call contexts, tuples support implicit flattening and restructuring conversions.
207Tuple flattening recursively expands a tuple into the list of its basic components.
208Tuple structuring packages a list of expressions into a value of tuple type.
209\begin{cfacode}
210int f(int, int);
211int g([int, int]);
212int h(int, [int, int]);
213[int, int] x;
214int y;
215
216f(x);      // flatten
217g(y, 10);  // structure
218h(x, y);   // flatten & structure
219\end{cfacode}
220In \CFA, each of these calls is valid.
221In the call to @f@, @x@ is implicitly flattened so that the components of @x@ are passed as the two arguments to @f@.
222For 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@.
223Finally, in the call to @h@, @y@ 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]@.
224The 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.
225
226In \KWC \cite{Buhr94a,Till89}, a precursor to \CFA, there were 4 tuple coercions: opening, closing, flattening, and structuring.
227Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value.
228Flattening coerces a nested tuple into a flat tuple, i.e. it takes a tuple with tuple components and expands it into a tuple with only non-tuple components.
229Structuring moves in the opposite direction, i.e. it takes a flat tuple value and provides structure by introducing nested tuple components.
230
231In \CFA, the design has been simplified to require only the two conversions previously described, which trigger only in function call and return situations.
232Specifically, the expression resolution algorithm examines all of the possible alternatives for an expression to determine the best match.
233In resolving a function call expression, each combination of function value and list of argument alternatives is examined.
234Given a particular argument list and function value, the list of argument alternatives is flattened to produce a list of non-tuple valued expressions.
235Then the flattened list of expressions is compared with each value in the function's parameter list.
236If 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.
237If 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.
238Assuming 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.
239For example, in
240\begin{cfacode}
241int f(int, [double, int]);
242f([5, 10.2], 4);
243\end{cfacode}
244There is only a single definition of @f@, and 3 arguments with only single interpretations.
245First, the argument alternative list @[5, 10.2], 4@ is flattened to produce the argument list @5, 10.2, 4@.
246Next, the parameter matching algorithm begins, with $P = $@int@ and $A = $@int@, which unifies exactly.
247Moving to the next parameter and argument, $P = $@[double, int]@ and $A = $@double@.
248This time, the parameter is a tuple type, so the algorithm applies recursively with $P' = $@double@ and $A = $@double@, which unifies exactly.
249Then $P' = $@int@ and $A = $@double@, which again unifies exactly.
250At this point, the end of $P'$ has been reached, so the arguments @10.2, 4@ are structured into the tuple expression @[10.2, 4]@.
251Finally, the end of the parameter list $P$ has also been reached, so the final expression is @f(5, [10.2, 4])@.
252
253\section{Tuple Assignment}
254\label{s:TupleAssignment}
255An assignment where the left side of the assignment operator has a tuple type is called tuple assignment.
256There 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 Multiple and Mass Assignment, respectively.
257\begin{cfacode}
258int x;
259double y;
260[int, double] z;
261[y, x] = 3.14;  // mass assignment
262[x, y] = z;     // multiple assignment
263z = 10;         // mass assignment
264z = [x, y];     // multiple assignment
265\end{cfacode}
266Let $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.
267
268For a multiple assignment to be valid, both tuples must have the same number of elements when flattened. Multiple assignment assigns $R_i$ to $L_i$ for each $i$.
269That is, @?=?(&$L_i$, $R_i$)@ must be a well-typed expression.
270In 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.
271
272A mass assignment assigns the value $R$ to each $L_i$.
273For a mass assignment to be valid, @?=?(&$L_i$, $R$)@ must be a well-typed expression.
274This differs from C cascading assignment (e.g. @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.
275For 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@.
276On 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.
277
278Both 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.
279As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function,
280\begin{cfacode}
281int x = 10, y = 20;
282[x, y] = [y, x];
283\end{cfacode}
284After executing this code, @x@ has the value @20@ and @y@ has the value @10@.
285
286In \CFA, tuple assignment is an expression where the result type is the type of the left side of the assignment, as in normal assignment.
287That is, a tuple assignment produces the value of the left-hand side after assignment.
288These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted.
289These 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.
290This decision wa made in an attempt to fix what was seen as a problem with assignment, wherein it can be used in many different locations, such as in function-call argument position.
291While 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.
292Furthermore, 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.
293In 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.
294In addition, \KWC permits the compiler to optimize tuple assignment as a block copy, since it does not support user-defined assignment operators.
295This optimization could be implemented in \CFA, but it requires the compiler to verify that the selected assignment operator is trivial.
296
297The following example shows multiple, mass, and cascading assignment used in one expression
298\begin{cfacode}
299  int a, b;
300  double c, d;
301  [void] f([int, int]);
302  f([c, a] = [b, d] = 1.5);  // assignments in parameter list
303\end{cfacode}
304The 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.
305That tuple is used as the right side of the multiple assignment (i.e., @[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]@.
306Finally, the tuple @[1, 1]@ is used as an expression in the call to @f@.
307
308\subsection{Tuple Construction}
309Tuple 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.
310\begin{cfacode}
311struct S;
312void ?{}(S *);         // (1)
313void ?{}(S *, int);    // (2)
314void ?{}(S * double);  // (3)
315void ?{}(S *, S);      // (4)
316
317[S, S] x = [3, 6.28];  // uses (2), (3)
318[S, S] y;              // uses (1), (1)
319[S, S] z = x.0;        // uses (4), (4)
320\end{cfacode}
321In this example, @x@ is initialized by the multiple constructor calls @?{}(&x.0, 3)@ and @?{}(&x.1, 6.28)@, while @y@ is initilaized by two default constructor calls @?{}(&y.0)@ and @?{}(&y.1)@.
322@z@ is initialized by mass copy constructor calls @?{}(&z.0, x.0)@ and @?{}(&z.1, x.0)@.
323Finally, @x@, @y@, and @z@ are destructed, i.e. the calls @^?{}(&x.0)@, @^?{}(&x.1)@, @^?{}(&y.0)@, @^?{}(&y.1)@, @^?{}(&z.0)@, and @^?{}(&z.1)@.
324
325It 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.
326For example, the function @void ?{}([T, U] *, S);@ can be defined to allow a tuple variable to be constructed from a value of type @S@.
327\begin{cfacode}
328struct S { int x; double y; };
329void ?{}([int, double] * this, S s) {
330  this->0 = s.x;
331  this->1 = s.y;
332}
333\end{cfacode}
334Due 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.
335For example,
336\begin{cfacode}
337struct S { int x; double y; int z };
338[int, double] t;
339S s = t;
340\end{cfacode}
341The 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.
342
343\section{Member-Access Tuple Expression}
344\label{s:MemberAccessTuple}
345It is possible to access multiple fields from a single expression using a \emph{Member-Access Tuple Expression}.
346The result is a single tuple-valued expression whose type is the tuple of the types of the members.
347For example,
348\begin{cfacode}
349struct S { int x; double y; char * z; } s;
350s.[x, y, z];
351\end{cfacode}
352Here, the type of @s.[x, y, z]@ is @[int, double, char *]@.
353A 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.
354Then the type of @a.[x, y, z]@ is @[T_x, T_y, T_z]@.
355
356Since 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 (e.g. rearrange components, drop components, duplicate components, etc.).
357\begin{cfacode}
358[int, int, long, double] x;
359void f(double, long);
360
361f(x.[0, 3]);          // f(x.0, x.3)
362x.[0, 1] = x.[1, 0];  // [x.0, x.1] = [x.1, x.0]
363[long, int, long] y = x.[2, 0, 2];
364\end{cfacode}
365
366It is possible for a member tuple expression to contain other member access expressions.
367For example,
368\begin{cfacode}
369struct A { double i; int j; };
370struct B { int * k; short l; };
371struct C { int x; A y; B z; } v;
372v.[x, y.[i, j], z.k];
373\end{cfacode}
374This expression is equivalent to @[v.x, [v.y.i, v.y.j], v.z.k]@.
375That is, the aggregate expression is effectively distributed across the tuple, which allows simple and easy access to multiple components in an aggregate, without repetition.
376It is guaranteed that the aggregate expression to the left of the @.@ in a member tuple expression is evaluated exactly once.
377As such, it is safe to use member tuple expressions on the result of a side-effecting function.
378\begin{cfacode}
379[int, float, double] f();
380[double, float] x = f().[2, 1];
381\end{cfacode}
382
383In \KWC, member tuple expressions are known as \emph{record field tuples} \cite{Till89}.
384Since \CFA permits these tuple-access expressions using structures, unions, and tuples, \emph{member tuple expression} or \emph{field tuple expression} is more appropriate.
385
386It could be possible to extend member-access expressions further.
387Currently, 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.
388In the interest of orthogonal design, \CFA could apply some meaning to the remaining combinations as well.
389For example,
390\begin{cfacode}
391struct S { int x, y; } s;
392[S, S] z;
393
394s.x;  // access member
395z.0;  // access component
396
397s.1;  // ???
398z.y;  // ???
399\end{cfacode}
400One possiblity is for @s.1@ to select the second member of @s@.
401Under this interpretation, it becomes possible to not only access members of a struct by name, but also by position.
402Likewise, it seems natural to open this mechanism to enumerations as well, wherein the left side would be a type, rather than an expression.
403One benefit of this interpretation is familiar, since it is extremely reminiscent of tuple-index expressions.
404On 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.
405This problem is less of a concern with tuples, since modifying a tuple affects only the code which directly uses that tuple, whereas modifying a structure has far reaching consequences with every instance of the structure.
406
407As for @z.y@, a natural interpretation would be to extend the meaning of member tuple expressions.
408That is, currently the tuple must occur as the member, i.e. to the right of the dot.
409Allowing 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.
410In 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@.
411It is questionable how useful this would actually be in practice, since generally structures are not designed to 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.
412Perhaps 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.
413The 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.
414
415Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member access expressions versus member tuple expressions.
416\begin{cfacode}
417struct { int x, y; };
418[S, S] z;
419z.[x, y];  // ???
420// => [z.0, z.1].[x, y]
421// => [z.0.x, z.0.y, z.1.x, z.1.y]
422// or
423// => [z.x, z.y]
424// => [[z.0, z.1].x, [z.0, z.1].y]
425// => [z.0.x, z.1.x, z.0.y, z.1.y]
426\end{cfacode}
427Depending on exactly how the two tuples are combined, different results can be achieved.
428As such, a specific ordering would need to be imposed in order for this feature to be useful.
429Furthermore, 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.
430
431Ultimately, both of these extensions introduce complexity into the model, with relatively little peceived benefit.
432
433\section{Casting}
434In C, the cast operator is used to explicitly convert between types.
435In \CFA, the cast operator has a secondary use, which is type ascription.
436That 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.
437\begin{cfacode}
438int f();     // (1)
439double f();  // (2)
440
441f();       // ambiguous - (1),(2) both equally viable
442(int)f();  // choose (2)
443\end{cfacode}
444Since casting is a fundamental operation in \CFA, casts should be given a meaningful interpretation in the context of tuples.
445Taking a look at standard C provides some guidance with respect to the way casts should work with tuples.
446\begin{cfacode}[numbers=left]
447int f();
448void g();
449
450(void)f();
451(int)g();
452
453struct A { int x; };
454(struct A)f();
455\end{cfacode}
456In C, line 4 is a valid cast, which calls @f@ and discards its result.
457On the other hand, line 5 is invalid, because @g@ does not produce a result, so requesting an @int@ to materialize from nothing is nonsensical.
458Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite{C11}.
459For consistency, this implies that any case wherein the number of components increases as a result of the cast is invalid, while casts which have the same or fewer number of components may be valid.
460
461Formally, 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$.
462Excess 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.
463This discarding naturally follows the way that a cast to void works in C.
464
465For example,
466\begin{cfacode}
467  [int, int, int] f();
468  [int, [int, int], int] g();
469
470  ([int, double])f();           // (1)
471  ([int, int, int])g();         // (2)
472  ([void, [int, int]])g();      // (3)
473  ([int, int, int, int])g();    // (4)
474  ([int, [int, int, int]])g();  // (5)
475\end{cfacode}
476
477(1) discards the last element of the return value and converts the second element to type double.
478Since @int@ is effectively a 1-element tuple, (2) discards the second component of the second element of the return value of @g@.
479If @g@ is free of side effects, this is equivalent to @[(int)(g().0), (int)(g().1.0), (int)(g().2)]@.
480Since @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)]@).
481
482% 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).
483Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions.
484As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3.
485Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid.
486That is, it is invalid to cast @[int, int]@ to @[int, int, int]@.
487
488\section{Polymorphism}
489Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with non-tuple types.
490\begin{cfacode}
491forall(otype T, dtype U)
492void f(T x, U * y);
493
494f([5, "hello"]);
495\end{cfacode}
496In this example, @[5, "hello"]@ is flattened, so that the argument list appears as @5, "hello"@.
497The argument matching algorithm binds @T@ to @int@ and @U@ to @const char@, and calls the function as normal.
498
499Tuples can contain otype and dtype components.
500For example, a plus operator can be written to add two triples of a type together.
501\begin{cfacode}
502forall(otype T | { T ?+?(T, T); })
503[T, T, T] ?+?([T, T, T] x, [T, T, T] y) {
504  return [x.0+y.0, x.1+y.1, x.2+y.2];
505}
506[int, int, int] x;
507int i1, i2, i3;
508[i1, i2, i3] = x + ([10, 20, 30]);
509\end{cfacode}
510Note that due to the implicit tuple conversions, this function is not restricted to the addition of two triples.
511A 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 which can bind to @T@, with a pairwise @?+?@ over @T@.
512For example, these expressions will also succeed and produce the same value.
513\begin{cfacode}
514([x.0, x.1]) + ([x.2, 10, 20, 30]);
515x.0 + ([x.1, x.2, 10, 20, 30]);
516\end{cfacode}
517This presents a potential problem if structure is important, as these three expressions look like they should have different meanings.
518Further, these calls can be made ambiguous by adding seemingly different functions.
519\begin{cfacode}
520forall(otype T | { T ?+?(T, T); })
521[T, T, T] ?+?([T, T] x, [T, T, T, T]);
522forall(otype T | { T ?+?(T, T); })
523[T, T, T] ?+?(T x, [T, T, T, T, T]);
524\end{cfacode}
525It 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.
526Still, this is a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate.
527It's possible that this could be rectified by applying an appropriate cost to the structuring and flattening conversions, which are currently 0-cost conversions.
528Care would be needed in this case to ensure that exact matches do not incur such a cost.
529\begin{cfacode}
530void f([int, int], int, int);
531
532f([0, 0], 0, 0);    // no cost
533f(0, 0, 0, 0);      // cost for structuring
534f([0, 0,], [0, 0]); // cost for flattening
535f([0, 0, 0], 0);    // cost for flattening and structuring
536\end{cfacode}
537
538Until this point, it has been assumed that assertion arguments must match the parameter type exactly, modulo polymorphic specialization (i.e. no implicit conversions are applied to assertion arguments).
539This decision presents a conflict with the flexibility of tuples.
540\subsection{Assertion Inference}
541\begin{cfacode}
542int f([int, double], double);
543forall(otype T, otype U | { T f(T, U, U); })
544void g(T, U);
545g(5, 10.21);
546\end{cfacode}
547If 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.
548Since tuples are fluid, this requirement reduces the usability of tuples in polymorphic code.
549To 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.
550
551This relaxation is made possible by extending the existing thunk generation scheme, as described by Bilson \cite{Bilson03}.
552Now, 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.
553\begin{cfacode}
554int _thunk(int _p0, double _p1, double _p2) {
555  return f([_p0, _p1], _p2);
556}
557\end{cfacode}
558Essentially, this provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
559
560\section{Implementation}
561Tuples are implemented in the \CFA translator via a transformation into generic types.
562The first time an $N$-tuple is seen for each $N$ in a scope, a generic type with $N$ type parameters is generated.
563For example,
564\begin{cfacode}
565[int, int] f() {
566  [double, double] x;
567  [int, double, int] y;
568}
569\end{cfacode}
570Is transformed into
571\begin{cfacode}
572forall(dtype T0, dtype T1 | sized(T0) | sized(T1))
573struct _tuple2 {  // generated before the first 2-tuple
574  T0 field_0;
575  T1 field_1;
576};
577_tuple2_(int, int) f() {
578  _tuple2_(double, double) x;
579  forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2))
580  struct _tuple3 {  // generated before the first 3-tuple
581    T0 field_0;
582    T1 field_1;
583    T2 field_2;
584  };
585  _tuple3_(int, double, int) y;
586}
587\end{cfacode}
588
589Tuple expressions are then simply converted directly into compound literals
590\begin{cfacode}
591[5, 'x', 1.24];
592\end{cfacode}
593Becomes
594\begin{cfacode}
595(_tuple3_(int, char, double)){ 5, 'x', 1.24 };
596\end{cfacode}
597
598Since tuples are essentially structures, tuple indexing expressions are just field accesses.
599\begin{cfacode}
600void f(int, [double, char]);
601[int, double] x;
602
603x.0+x.1;
604printf("%d %g\n", x);
605f(x, 'z');
606\end{cfacode}
607Is transformed into
608\begin{cfacode}
609void f(int, _tuple2_(double, char));
610_tuple2_(int, double) x;
611
612x.field_0+x.field_1;
613printf("%d %g\n", x.field_0, x.field_1);
614f(x.field_0, (_tuple2){ x.field_1, 'z' });
615\end{cfacode}
616Note that due to flattening, @x@ used in the argument position is converted into the list of its fields.
617In the call to @f@, the second and third argument components are structured into a tuple argument.
618
619Expressions which may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.
620Each unique expression is assigned an identifier and is guaranteed to be executed exactly once.
621\begin{cfacode}
622void g(int, double);
623[int, double] h();
624g(h());
625\end{cfacode}
626Interally, this is converted to
627\begin{cfacode}
628void g(int, double);
629[int, double] h();
630let unq<0> = f() : g(unq<0>.0, unq<0>.1);  // notation?
631\end{cfacode}
632Ultimately, unique expressions are converted into two variables and an expression.
633\begin{cfacode}
634void g(int, double);
635[int, double] h();
636
637_Bool _unq0_finished_ = 0;
638[int, double] _unq0;
639g(
640  (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).0,
641  (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).1,
642);
643\end{cfacode}
644Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order.
645The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is set to true.
646Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression.
647
648Currently, the \CFA translator has a very broad, imprecise definition of impurity, where any function call is assumed to be impure.
649This notion could be made more precise for certain intrinsic, autogenerated, and builtin functions, and could analyze function bodies when they are available to recursively detect impurity, to eliminate some unique expressions.
650It's possible that unique expressions could be exposed to the user through a language feature, but it's not immediately obvious that there is a benefit to doing so.
651
652Tuple member expressions are recursively expanded into a list of member access expressions.
653\begin{cfacode}
654[int, [double, int, double], int]] x;
655x.[0, 1.[0, 2]];
656\end{cfacode}
657Which becomes
658\begin{cfacode}
659[x.0, [x.1.0, x.1.2]];
660\end{cfacode}
661Tuple member expressions also take advantage of unique expressions in the case of possible impurity.
662
663Finally, the various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions.
664For example, a mass assignment
665\begin{cfacode}
666int x, z;
667double y;
668[double, double] f();
669
670[x, y, z] = 1.5;            // mass assignment
671\end{cfacode}
672Generates the following
673\begin{cfacode}
674// [x, y, z] = 1.5;
675_tuple3_(int, double, int) _tmp_stmtexpr_ret0;
676({
677  // assign LHS address temporaries
678  int *__massassign_L0 = &x;    // ?{}
679  double *__massassign_L1 = &y; // ?{}
680  int *__massassign_L2 = &z;    // ?{}
681
682  // assign RHS value temporary
683  double __massassign_R0 = 1.5; // ?{}
684
685  ({ // tuple construction - construct statement expr return variable
686    // assign LHS address temporaries
687    int *__multassign_L0 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
688    double *__multassign_L1 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
689    int *__multassign_L2 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
690
691    // assign RHS value temporaries and perform mass assignment to L0, L1, L2
692    int __multassign_R0 = (*__massassign_L0=(int)__massassign_R0);   // ?{}
693    double __multassign_R1 = (*__massassign_L1=__massassign_R0);     // ?{}
694    int __multassign_R2 = (*__massassign_L2=(int)__massassign_R0);   // ?{}
695
696    // perform construction of statement expr return variable using
697    // RHS value temporary
698    ((*__multassign_L0 = __multassign_R0 /* ?{} */),
699     (*__multassign_L1 = __multassign_R1 /* ?{} */),
700     (*__multassign_L2 = __multassign_R2 /* ?{} */));
701  });
702  _tmp_stmtexpr_ret0;
703});
704({ // tuple destruction - destruct assign expr value
705  int *__massassign_L3 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
706  double *__massassign_L4 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
707  int *__massassign_L5 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
708  ((*__massassign_L3 /* ^?{} */),
709   (*__massassign_L4 /* ^?{} */),
710   (*__massassign_L5 /* ^?{} */));
711});
712\end{cfacode}
713A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, e.g. in a unique expression.
714$N$ LHS variables are generated and constructed using the address of the tuple components, and a single RHS variable is generated to store the value of the RHS without any loss of precision.
715A nested statement expression is generated that performs the individual assignments and constructs the return value using the results of the individual assignments.
716Finally, the statement expression temporary is destroyed at the end of the expression.
717
718Similarly, a multiple assignment
719\begin{cfacode}
720[x, y, z] = [f(), 3];       // multiple assignment
721\end{cfacode}
722Generates
723\begin{cfacode}
724// [x, y, z] = [f(), 3];
725_tuple3_(int, double, int) _tmp_stmtexpr_ret0;
726({
727  // assign LHS address temporaries
728  int *__multassign_L0 = &x;    // ?{}
729  double *__multassign_L1 = &y; // ?{}
730  int *__multassign_L2 = &z;    // ?{}
731
732  // assign RHS value temporaries
733  _tuple2_(double, double) _tmp_cp_ret0;
734  _Bool _unq0_finished_ = 0;
735  double __multassign_R0 =
736    (_unq0_finished_ ?
737      _tmp_cp_ret0 :
738      (_tmp_cp_ret0=f(), _unq0_finished_=1, _tmp_cp_ret0)).0; // ?{}
739  double __multassign_R1 =
740    (_unq0_finished_ ?
741      _tmp_cp_ret0 :
742      (_tmp_cp_ret0=f(), _unq0_finished_=1, _tmp_cp_ret0)).1; // ?{}
743  ({ // tuple destruction - destruct f() return temporary - tuple destruction
744    // assign LHS address temporaries
745    double *__massassign_L3 = (double *)&_tmp_cp_ret0.0;  // ?{}
746    double *__massassign_L4 = (double *)&_tmp_cp_ret0.1;  // ?{}
747    // perform destructions - intrinsic, so NOP
748    ((*__massassign_L3 /* ^?{} */),
749     (*__massassign_L4 /* ^?{} */));
750  });
751  int __multassign_R2 = 3; // ?{}
752
753  ({ // tuple construction - construct statement expr return variable
754    // assign LHS address temporaries
755    int *__multassign_L3 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
756    double *__multassign_L4 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
757    int *__multassign_L5 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
758
759    // assign RHS value temporaries and perform multiple assignment to L0, L1, L2
760    int __multassign_R3 = (*__multassign_L0=(int)__multassign_R0);  // ?{}
761    double __multassign_R4 = (*__multassign_L1=__multassign_R1);    // ?{}
762    int __multassign_R5 = (*__multassign_L2=__multassign_R2);       // ?{}
763
764    // perform construction of statement expr return variable using
765    // RHS value temporaries
766    ((*__multassign_L3=__multassign_R3 /* ?{} */),
767     (*__multassign_L4=__multassign_R4 /* ?{} */),
768     (*__multassign_L5=__multassign_R5 /* ?{} */));
769  });
770  _tmp_stmtexpr_ret0;
771});
772({  // tuple destruction - destruct assign expr value
773  // assign LHS address temporaries
774  int *__massassign_L5 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
775  double *__massassign_L6 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
776  int *__massassign_L7 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
777  // perform destructions - intrinsic, so NOP
778  ((*__massassign_L5 /* ^?{} */),
779   (*__massassign_L6 /* ^?{} */),
780   (*__massassign_L7 /* ^?{} */));
781});
782\end{cfacode}
783The difference here is that $N$ RHS values are stored into separate temporary variables.
784
785The 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.
786There are other places where the \CFA translator makes use of GNU C extensions, such as its use of nested functions, so this is not a new restriction.
787
788\section{Variadic Functions}
789% TODO: should this maybe be its own chapter?
790C provides variadic functions through the manipulation of @va_list@ objects.
791A variadic function is one which contains at least one parameter, followed by @...@ as the last token in the parameter list.
792In particular, some form of \emph{argument descriptor} is needed to inform the function of the number of arguments and their types.
793Two common argument descriptors are format strings or and counter parameters.
794It's important to note that both of these mechanisms are inherently redundant, because they require the user to specify information that the compiler knows explicitly.
795This required repetition is error prone, because it's easy for the user to add or remove arguments without updating the argument descriptor.
796In addition, C requires the programmer to hard code all of the possible expected types.
797As a result, it is cumbersome to write a function that is open to extension.
798For example, a simple function which sums $N$ @int@s,
799\begin{cfacode}
800int sum(int N, ...) {
801  va_list args;
802  va_start(args, N);
803  int ret = 0;
804  while(N) {
805    ret += va_arg(args, int);  // have to specify type
806    N--;
807  }
808  va_end(args);
809  return ret;
810}
811sum(3, 10, 20, 30);  // need to keep counter in sync
812\end{cfacode}
813The @va_list@ type is a special C data type that abstracts variadic argument manipulation.
814The @va_start@ macro initializes a @va_list@, given the last named parameter.
815Each use of the @va_arg@ macro allows access to the next variadic argument, given a type.
816Since the function signature does not provide any information on what types can be passed to a variadic function, the compiler does not perform any error checks on a variadic call.
817As such, it is possible to pass any value to the @sum@ function, including pointers, floating-point numbers, and structures.
818In the case where the provided type is not compatible with the argument's actual type after default argument promotions, or if too many arguments are accessed, the behaviour is undefined \cite{C11}.
819Furthermore, there is no way to perform the necessary error checks in the @sum@ function at run-time, since type information is not carried into the function body.
820Since they rely on programmer convention rather than compile-time checks, variadic functions are generally unsafe.
821
822In practice, compilers can provide warnings to help mitigate some of the problems.
823For example, GCC provides the @format@ attribute to specify that a function uses a format string, which allows the compiler to perform some checks related to the standard format specifiers.
824Unfortunately, this does not permit extensions to the format string syntax, so a programmer cannot extend the attribute to warn for mismatches with custom types.
825
826Needless to say, C's variadic functions are a deficient language feature.
827Two options were examined to provide better, type-safe variadic functions in \CFA.
828\subsection{Whole Tuple Matching}
829Option 1 is to change the argument matching algorithm, so that type parameters can match whole tuples, rather than just their components.
830This option could be implemented with two phases of argument matching when a function contains type parameters and the argument list contains tuple arguments.
831If flattening and structuring fail to produce a match, a second attempt at matching the function and argument combination is made where tuple arguments are not expanded and structure must match exactly, modulo non-tuple implicit conversions.
832For example:
833\begin{cfacode}
834  forall(otype T, otype U | { T g(U); })
835  void f(T, U);
836
837  [int, int] g([int, int, int, int]);
838
839  f([1, 2], [3, 4, 5, 6]);
840\end{cfacode}
841With flattening and structuring, the call is first transformed into @f(1, 2, 3, 4, 5, 6)@.
842Since the first argument of type @T@ does not have a tuple type, unification decides that @T=int@ and @1@ is matched as the first parameter.
843Likewise, @U@ does not have a tuple type, so @U=int@ and @2@ is accepted as the second parameter.
844There are now no remaining formal parameters, but there are remaining arguments and the function is not variadic, so the match fails.
845
846With the addition of an exact matching attempt, @T=[int,int]@ and @U=[int,int,int,int]@ and so the arguments type check.
847Likewise, when inferring assertion @g@, an exact match is found.
848
849This approach is strict with respect to argument structure by nature, which makes it syntactically awkward to use in ways that the existing tuple design is not.
850For example, consider a @new@ function which allocates memory using @malloc@ and constructs the result, using arbitrary arguments.
851\begin{cfacode}
852struct Array;
853void ?{}(Array *, int, int, int);
854
855forall(dtype T, otype Params | sized(T) | { void ?{}(T *, Params); })
856T * new(Params p) {
857  return malloc(){ p };
858}
859Array(int) * x = new([1, 2, 3]);
860\end{cfacode}
861The call to @new@ is not particularly appealing, since it requires the use of square brackets at the call-site, which is not required in any other function call.
862This shifts the burden from the compiler to the programmer, which is almost always wrong, and creates an odd inconsistency within the language.
863Similarly, in order to pass 0 variadic arguments, an explicit empty tuple must be passed into the argument list, otherwise the exact matching rule would not have an argument to bind against.
864
865It should be otherwise noted that the addition of an exact matching rule only affects the outcome for polymorphic type binding when tuples are involved.
866For non-tuple arguments, exact matching and flattening \& structuring are equivalent.
867For tuple arguments to a function without polymorphic formal parameters, flattening and structuring work whenever an exact match would have worked, since the tuple is flattened and implicitly restructured to its original structure.
868Thus there is nothing to be gained from permitting the exact matching rule to take effect when a function does not contain polymorphism and none of the arguments are tuples.
869
870Overall, this option takes a step in the right direction, but is contrary to the flexibility of the existing tuple design.
871
872\subsection{A New Typeclass}
873A second option is the addition of another kind of type parameter, @ttype@.
874Matching against a @ttype@ parameter consumes all remaining argument components and packages them into a tuple, binding to the resulting tuple of types.
875In a given parameter list, there should be at most one @ttype@ parameter that must occur last, otherwise the call can never resolve, given the previous rule.
876% TODO: a similar rule exists in C/C++ for "..."
877This idea essentially matches normal variadic semantics, with a strong feeling of similarity to \CCeleven variadic templates.
878As such, @ttype@ variables will also be referred to as argument packs.
879This is the option that has been added to \CFA.
880
881Like variadic templates, the main way to manipulate @ttype@ polymorphic functions is through recursion.
882Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful.
883Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled.
884
885For example, a simple translation of the C sum function using @ttype@ would look like
886\begin{cfacode}
887int sum(){ return 0; }        // (0)
888forall(ttype Params | { int sum(Params); })
889int sum(int x, Params rest) { // (1)
890  return x+sum(rest);
891}
892sum(10, 20, 30);
893\end{cfacode}
894Since (0) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@.
895In order to call (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]@.
896In order to finish the resolution of @sum@, an assertion parameter which matches @int sum(int, int)@ is required.
897Like in the previous iteration, (0) is not a valid candiate, so (1) is examined with @Params@ bound to @[int]@, requiring the assertion @int sum(int)@.
898Next, (0) fails, and to satisfy (1) @Params@ is bound to @[]@, requiring an assertion @int sum()@.
899Finally, (0) matches and (1) fails, which terminates the recursion.
900Effectively, this 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))@.
901
902A point of note is that this version does not require any form of argument descriptor, since the \CFA type system keeps track of all of these details.
903It might be reasonable to take the @sum@ function a step further to enforce a minimum number of arguments, which could be done simply
904\begin{cfacode}
905int sum(int x, int y){
906  return x+y;
907}
908forall(ttype Params | { int sum(int, Params); })
909int sum(int x, int y, Params rest) {
910  return sum(x+y, rest);
911}
912sum(10, 20, 30);
913\end{cfacode}
914
915One more iteration permits the summation of any summable type, as long as all arguments are the same type.
916\begin{cfacode}
917trait summable(otype T) {
918  T ?+?(T, T);
919};
920forall(otype R | summable(R))
921R sum(R x, R y){
922  return x+y;
923}
924forall(otype R, ttype Params
925  | summable(R)
926  | { R sum(R, Params); })
927R sum(R x, R y, Params rest) {
928  return sum(x+y, rest);
929}
930sum(3, 10, 20, 30);
931\end{cfacode}
932Unlike C, it is not necessary to hard code the expected type.
933This is naturally open to extension, in that any user-defined type with a @?+?@ operator is automatically able to be used with the @sum@ function.
934That is to say, the programmer who writes @sum@ does not need full program knowledge of every possible data type, unlike what is necessary to write an equivalent function using the standard C mechanisms.
935
936Going one last step, it is possible to achieve full generality in \CFA, allowing the summation of arbitrary lists of summable types.
937\begin{cfacode}
938trait summable(otype T1, otype T2, otype R) {
939  R ?+?(T1, T2);
940};
941forall(otype T1, otype T2, otype R | summable(T1, T2, R))
942R sum(T1 x, T2 y) {
943  return x+y;
944}
945forall(otype T1, otype T2, otype T3, ttype Params, otype R
946  | summable(T1, T2, T3)
947  | { R sum(T3, Params); })
948R sum(T1 x, T2 y, Params rest ) {
949  return sum(x+y, rest);
950}
951sum(3, 10.5, 20, 30.3);
952\end{cfacode}
953The \CFA translator requires adding explicit @double ?+?(int, double)@ and @double ?+?(double, int)@ functions for this call to work, since implicit conversions are not supported for assertions.
954
955C variadic syntax and @ttype@ polymorphism probably should not be mixed, since it is not clear where to draw the line to decide which arguments belong where.
956Furthermore, it might be desirable to disallow polymorphic functions to use C variadic syntax to encourage a Cforall style.
957Aside from calling C variadic functions, it is not obvious that there is anything that can be done with C variadics that could not also be done with @ttype@ parameters.
958
959Variadic templates in \CC require an ellipsis token to express that a parameter is a parameter pack and to expand a parameter pack.
960\CFA does not need an ellipsis in either case, since the type class @ttype@ is only used for variadics.
961An alternative design could have used an ellipsis combined with an existing type class.
962This approach was not taken because the largest benefit of the ellipsis token in \CC is the ability to expand a parameter pack within an expression, e.g. in fold expressions, which requires compile-time knowledge of the structure of the parameter pack, which is not available in \CFA.
963\begin{cppcode}
964template<typename... Args>
965void f(Args &... args) {
966  g(&args...);  // expand to addresses of pack elements
967}
968\end{cppcode}
969As such, the addition of an ellipsis token would be purely an aesthetic change in \CFA today.
970
971It is possible to write a type-safe variadic print routine, which can replace @printf@
972\begin{cfacode}
973struct S { int x, y; };
974forall(otype T, ttype Params |
975  { void print(T); void print(Params); })
976void print(T arg, Params rest) {
977  print(arg);
978  print(rest);
979}
980void print(char * x) { printf("%s", x); }
981void print(int x) { printf("%d", x);  }
982void print(S s) { print("{ ", s.x, ",", s.y, " }"); }
983print("s = ", (S){ 1, 2 }, "\n");
984\end{cfacode}
985This example routine showcases a variadic-template-like decomposition of the provided argument list.
986The individual @print@ routines allow printing a single element of a type.
987The polymorphic @print@ allows printing any list of types, as long as each individual type has a @print@ function.
988The individual print functions can be used to build up more complicated @print@ routines, such as for @S@, which is something that cannot be done with @printf@ in C.
989
990It is also possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
991For example, it is possible to write @new@ as a library function.
992Example 2: new (i.e. type-safe malloc + constructors)
993\begin{cfacode}
994struct Array;
995void ?{}(Array *, int, int, int);
996
997forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
998T * new(Params p) {
999  return malloc(){ p }; // construct result of malloc
1000}
1001Array * x = new(1, 2, 3);
1002\end{cfacode}
1003The @new@ function provides the combination of type-safe @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically allocated objects.
1004This provides the type-safety of @new@ in \CC, without the need to specify the allocated type, thanks to return-type inference.
1005
1006In the call to @new@, @Array@ is selected to match @T@, and @Params@ is expanded to match @[int, int, int, int]@. To satisfy the assertions, a constructor with an interface compatible with @void ?{}(Array *, int, int, int)@ must exist in the current scope.
1007
1008\subsection{Implementation}
1009
1010The definition of @new@
1011\begin{cfacode}
1012forall(dtype T | sized(T)) T * malloc();
1013
1014forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
1015T * new(Params p) {
1016  return malloc(){ p }; // construct result of malloc
1017}
1018\end{cfacode}
1019Generates the following
1020\begin{cfacode}
1021void *malloc(long unsigned int _sizeof_T, long unsigned int _alignof_T);
1022
1023void *new(
1024  void (*_adapter_)(void (*)(), void *, void *),
1025  long unsigned int _sizeof_T,
1026  long unsigned int _alignof_T,
1027  long unsigned int _sizeof_Params,
1028  long unsigned int _alignof_Params,
1029  void (* _ctor_T)(void *, void *),
1030  void *p
1031){
1032  void *_retval_new;
1033  void *_tmp_cp_ret0;
1034  void *_tmp_ctor_expr0;
1035  _retval_new=
1036    (_adapter_(_ctor_T,
1037      (_tmp_ctor_expr0=(_tmp_cp_ret0=malloc(_sizeof_2tT, _alignof_2tT),
1038        _tmp_cp_ret0)),
1039      p),
1040    _tmp_ctor_expr0); // ?{}
1041  *(void **)&_tmp_cp_ret0; // ^?{}
1042  return _retval_new;
1043}
1044\end{cfacode}
1045The constructor for @T@ is called indirectly through the adapter function on the result of @malloc@ and the parameter pack.
1046The variable that was allocated and constructed is then returned from @new@.
1047
1048A call to @new@
1049\begin{cfacode}
1050struct S { int x, y; };
1051void ?{}(S *, int, int);
1052
1053S * s = new(3, 4);
1054\end{cfacode}
1055Generates the following
1056\begin{cfacode}
1057struct _tuple2_ {  // _tuple2_(T0, T1)
1058  void *field_0;
1059  void *field_1;
1060};
1061struct _conc__tuple2_0 {  // _tuple2_(int, int)
1062  int field_0;
1063  int field_1;
1064};
1065struct _conc__tuple2_0 _tmp_cp1;  // tuple argument to new
1066struct S *_tmp_cp_ret1;           // return value from new
1067void _thunk0(  // ?{}(S *, [int, int])
1068  struct S *_p0,
1069  struct _conc__tuple2_0 _p1
1070){
1071  _ctor_S(_p0, _p1.field_0, _p1.field_1);  // restructure tuple parameter
1072}
1073void _adapter(void (*_adaptee)(), void *_p0, void *_p1){
1074  // apply adaptee to arguments after casting to actual types
1075  ((void (*)(struct S *, struct _conc__tuple2_0))_adaptee)(
1076    _p0,
1077    *(struct _conc__tuple2_0 *)_p1
1078  );
1079}
1080struct S *s = (struct S *)(_tmp_cp_ret1=
1081  new(
1082    _adapter,
1083    sizeof(struct S),
1084    __alignof__(struct S),
1085    sizeof(struct _conc__tuple2_0),
1086    __alignof__(struct _conc__tuple2_0),
1087    (void (*)(void *, void *))&_thunk0,
1088    (({ // copy construct tuple argument to new
1089      int *__multassign_L0 = (int *)&_tmp_cp1.field_0;
1090      int *__multassign_L1 = (int *)&_tmp_cp1.field_1;
1091      int __multassign_R0 = 3;
1092      int __multassign_R1 = 4;
1093      ((*__multassign_L0=__multassign_R0 /* ?{} */) ,
1094       (*__multassign_L1=__multassign_R1 /* ?{} */));
1095    }), &_tmp_cp1)
1096  ), _tmp_cp_ret1);
1097*(struct S **)&_tmp_cp_ret1; // ^?{}  // destroy return value from new
1098({  // destroy argument temporary
1099  int *__massassign_L0 = (int *)&_tmp_cp1.field_0;
1100  int *__massassign_L1 = (int *)&_tmp_cp1.field_1;
1101  ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
1102});
1103\end{cfacode}
1104Of note, @_thunk0@ is generated to translate calls to @?{}(S *, [int, int])@ into calls to @?{}(S *, int, int)@.
1105The call to @new@ constructs a tuple argument using the supplied arguments.
1106
1107The @print@ function
1108\begin{cfacode}
1109forall(otype T, ttype Params |
1110  { void print(T); void print(Params); })
1111void print(T arg, Params rest) {
1112  print(arg);
1113  print(rest);
1114}
1115\end{cfacode}
1116Generates
1117\begin{cfacode}
1118void print_variadic(
1119  void (*_adapterF_7tParams__P)(void (*)(), void *),
1120  void (*_adapterF_2tT__P)(void (*)(), void *),
1121  void (*_adapterF_P2tT2tT__MP)(void (*)(), void *, void *),
1122  void (*_adapterF2tT_P2tT2tT_P_MP)(void (*)(), void *, void *, void *),
1123  long unsigned int _sizeof_T,
1124  long unsigned int _alignof_T,
1125  long unsigned int _sizeof_Params,
1126  long unsigned int _alignof_Params,
1127  void *(*_assign_TT)(void *, void *),
1128  void (*_ctor_T)(void *),
1129  void (*_ctor_TT)(void *, void *),
1130  void (*_dtor_T)(void *),
1131  void (*print_T)(void *),
1132  void (*print_Params)(void *),
1133  void *arg,
1134  void *rest
1135){
1136  void *_tmp_cp0 = __builtin_alloca(_sizeof_T);
1137  _adapterF_2tT__P(  // print(arg)
1138    ((void (*)())print_T),
1139    (_adapterF_P2tT2tT__MP( // copy construct argument
1140      ((void (*)())_ctor_TT),
1141      _tmp_cp0,
1142      arg
1143    ), _tmp_cp0)
1144  );
1145  _dtor_T(_tmp_cp0);  // destroy argument temporary
1146  _adapterF_7tParams__P(  // print(rest)
1147    ((void (*)())print_Params),
1148    rest
1149  );
1150}
1151\end{cfacode}
1152The @print_T@ routine is called indirectly through an adapter function with a copy constructed argument, followed by an indirect call to @print_Params@.
1153
1154A call to print
1155\begin{cfacode}
1156void print(const char * x) { printf("%s", x); }
1157void print(int x) { printf("%d", x);  }
1158
1159print("x = ", 123, ".\n");
1160\end{cfacode}
1161Generates the following
1162\begin{cfacode}
1163void print_string(const char *x){
1164  int _tmp_cp_ret0;
1165  (_tmp_cp_ret0=printf("%s", x)) , _tmp_cp_ret0;
1166  *(int *)&_tmp_cp_ret0; // ^?{}
1167}
1168void print_int(int x){
1169  int _tmp_cp_ret1;
1170  (_tmp_cp_ret1=printf("%d", x)) , _tmp_cp_ret1;
1171  *(int *)&_tmp_cp_ret1; // ^?{}
1172}
1173
1174struct _tuple2_ {  // _tuple2_(T0, T1)
1175  void *field_0;
1176  void *field_1;
1177};
1178struct _conc__tuple2_0 {  // _tuple2_(int, const char *)
1179  int field_0;
1180  const char *field_1;
1181};
1182struct _conc__tuple2_0 _tmp_cp6;  // _tuple2_(int, const char *)
1183const char *_thunk0(const char **_p0, const char *_p1){
1184        // const char * ?=?(const char **, const char *)
1185  return *_p0=_p1;
1186}
1187void _thunk1(const char **_p0){ // void ?{}(const char **)
1188  *_p0; // ?{}
1189}
1190void _thunk2(const char **_p0, const char *_p1){
1191        // void ?{}(const char **, const char *)
1192  *_p0=_p1; // ?{}
1193}
1194void _thunk3(const char **_p0){ // void ^?{}(const char **)
1195  *_p0; // ^?{}
1196}
1197void _thunk4(struct _conc__tuple2_0 _p0){ // void print([int, const char *])
1198  struct _tuple1_ { // _tuple1_(T0)
1199    void *field_0;
1200  };
1201  struct _conc__tuple1_1 { // _tuple1_(const char *)
1202    const char *field_0;
1203  };
1204  void _thunk5(struct _conc__tuple1_1 _pp0){ // void print([const char *])
1205    print_string(_pp0.field_0);  // print(rest.0)
1206  }
1207  void _adapter_i_pii_(void (*_adaptee)(), void *_ret, void *_p0, void *_p1){
1208    *(int *)_ret=((int (*)(int *, int))_adaptee)(_p0, *(int *)_p1);
1209  }
1210  void _adapter_pii_(void (*_adaptee)(), void *_p0, void *_p1){
1211    ((void (*)(int *, int ))_adaptee)(_p0, *(int *)_p1);
1212  }
1213  void _adapter_i_(void (*_adaptee)(), void *_p0){
1214    ((void (*)(int))_adaptee)(*(int *)_p0);
1215  }
1216  void _adapter_tuple1_5_(void (*_adaptee)(), void *_p0){
1217    ((void (*)(struct _conc__tuple1_1 ))_adaptee)(*(struct _conc__tuple1_1 *)_p0);
1218  }
1219  print_variadic(
1220    _adapter_tuple1_5,
1221    _adapter_i_,
1222    _adapter_pii_,
1223    _adapter_i_pii_,
1224    sizeof(int),
1225    __alignof__(int),
1226    sizeof(struct _conc__tuple1_1),
1227    __alignof__(struct _conc__tuple1_1),
1228    (void *(*)(void *, void *))_assign_i,     // int ?=?(int *, int)
1229    (void (*)(void *))_ctor_i,                // void ?{}(int *)
1230    (void (*)(void *, void *))_ctor_ii,       // void ?{}(int *, int)
1231    (void (*)(void *))_dtor_ii,               // void ^?{}(int *)
1232    (void (*)(void *))print_int,              // void print(int)
1233    (void (*)(void *))&_thunk5,               // void print([const char *])
1234    &_p0.field_0,                             // rest.0
1235    &(struct _conc__tuple1_1 ){ _p0.field_1 } // [rest.1]
1236  );
1237}
1238struct _tuple1_ {  // _tuple1_(T0)
1239  void *field_0;
1240};
1241struct _conc__tuple1_6 {  // _tuple_1(const char *)
1242  const char *field_0;
1243};
1244const char *_temp0;
1245_temp0="x = ";
1246void _adapter_pstring_pstring_string(
1247  void (*_adaptee)(),
1248  void *_ret,
1249  void *_p0,
1250  void *_p1
1251){
1252  *(const char **)_ret=
1253    ((const char *(*)(const char **, const char *))_adaptee)(
1254      _p0,
1255      *(const char **)_p1
1256    );
1257}
1258void _adapter_pstring_string(void (*_adaptee)(), void *_p0, void *_p1){
1259  ((void (*)(const char **, const char *))_adaptee)(_p0, *(const char **)_p1);
1260}
1261void _adapter_string_(void (*_adaptee)(), void *_p0){
1262  ((void (*)(const char *))_adaptee)(*(const char **)_p0);
1263}
1264void _adapter_tuple2_0_(void (*_adaptee)(), void *_p0){
1265  ((void (*)(struct _conc__tuple2_0 ))_adaptee)(*(struct _conc__tuple2_0 *)_p0);
1266}
1267print_variadic(
1268  _adapter_tuple2_0_,
1269  _adapter_string_,
1270  _adapter_pstring_string_,
1271  _adapter_pstring_pstring_string_,
1272  sizeof(const char *),
1273  __alignof__(const char *),
1274  sizeof(struct _conc__tuple2_0 ),
1275  __alignof__(struct _conc__tuple2_0 ),
1276  (void *(*)(void *, void *))&_thunk0, // const char * ?=?(const char **, const char *)
1277  (void (*)(void *))&_thunk1,          // void ?{}(const char **)
1278  (void (*)(void *, void *))&_thunk2,  // void ?{}(const char **, const char *)
1279  (void (*)(void *))&_thunk3,          // void ^?{}(const char **)
1280  (void (*)(void *))print_string,      // void print(const char *)
1281  (void (*)(void *))&_thunk4,          // void print([int, const char *])
1282  &_temp0,                             // "x = "
1283  (({  // copy construct tuple argument to print
1284    int *__multassign_L0 = (int *)&_tmp_cp6.field_0;
1285    const char **__multassign_L1 = (const char **)&_tmp_cp6.field_1;
1286    int __multassign_R0 = 123;
1287    const char *__multassign_R1 = ".\n";
1288    ((*__multassign_L0=__multassign_R0 /* ?{} */),
1289     (*__multassign_L1=__multassign_R1 /* ?{} */));
1290  }), &_tmp_cp6)                        // [123, ".\n"]
1291);
1292({  // destroy argument temporary
1293  int *__massassign_L0 = (int *)&_tmp_cp6.field_0;
1294  const char **__massassign_L1 = (const char **)&_tmp_cp6.field_1;
1295  ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
1296});
1297\end{cfacode}
1298The type @_tuple2_@ is generated to allow passing the @rest@ argument to @print_variadic@.
1299Thunks 0 through 3 provide wrappers for the @otype@ parameters for @const char *@, while @_thunk4@ translates a call to @print([int, const char *])@ into a call to @print_variadic(int, [const char *])@.
1300This all builds to a call to @print_variadic@, with the appropriate copy construction of the tuple argument.
1301
1302\section{Future Work}
Note: See TracBrowser for help on using the repository browser.