source: doc/theses/rob_schluntz_MMath/tuples.tex @ 52f6250

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

specialize thesis directory-names

  • Property mode set to 100644
File size: 46.3 KB
Line 
1%======================================================================
2\chapter{Tuples}
3%======================================================================
4
5\section{Multiple-Return-Value Functions}
6\label{s:MRV_Functions}
7In standard C, functions can return at most one value.
8This restriction results in code which emulates functions with multiple return values by \emph{aggregation} or by \emph{aliasing}.
9In the former situation, the function designer creates a record type that combines all of the return values into a single type.
10For example, consider a function returning the most frequently occurring letter in a string, and its frequency.
11This example is complex enough to illustrate that an array is insufficient, since arrays are homogeneous, and demonstrates a potential pitfall that exists with aliasing.
12\begin{cfacode}
13struct mf_ret {
14  int freq;
15  char ch;
16};
17
18struct mf_ret most_frequent(const char * str) {
19  char freqs [26] = { 0 };
20  struct mf_ret ret = { 0, 'a' };
21  for (int i = 0; str[i] != '\0'; ++i) {
22    if (isalpha(str[i])) {        // only count letters
23      int ch = tolower(str[i]);   // convert to lower case
24      int idx = ch-'a';
25      if (++freqs[idx] > ret.freq) {  // update on new max
26        ret.freq = freqs[idx];
27        ret.ch = ch;
28      }
29    }
30  }
31  return ret;
32}
33
34const char * str = "hello world";
35struct mf_ret ret = most_frequent(str);
36printf("%s -- %d %c\n", str, ret.freq, ret.ch);
37\end{cfacode}
38Of note, the designer must come up with a name for the return type and for each of its fields.
39Unnecessary naming is a common programming language issue, introducing verbosity and a complication of the user's mental model.
40That 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.
41As 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.
42
43In the latter approach, the designer simulates multiple return values by passing the additional return values as pointer parameters.
44The pointer parameters are assigned inside of the routine body to emulate a return.
45Using the same example,
46\begin{cfacode}
47int most_frequent(const char * str, char * ret_ch) {
48  char freqs [26] = { 0 };
49  int ret_freq = 0;
50  for (int i = 0; str[i] != '\0'; ++i) {
51    if (isalpha(str[i])) {        // only count letters
52      int ch = tolower(str[i]);   // convert to lower case
53      int idx = ch-'a';
54      if (++freqs[idx] > ret_freq) {  // update on new max
55        ret_freq = freqs[idx];
56        *ret_ch = ch;   // assign to out parameter
57      }
58    }
59  }
60  return ret_freq;  // only one value returned directly
61}
62
63const char * str = "hello world";
64char ch;                            // pre-allocate return value
65int freq = most_frequent(str, &ch); // pass return value as out parameter
66printf("%s -- %d %c\n", str, freq, ch);
67\end{cfacode}
68Notably, 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.
69Also, 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.
70Furthermore, 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.
71On 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.
72Interestingly, 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.
73In 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.
74Still, 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.
75As with the previous approach, this technique can simulate multiple return values, but in practice it is verbose and error prone.
76
77In \CFA, functions can be declared to return multiple values with an extension to the function declaration syntax.
78Multiple 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.
79The ability to return multiple values from a function requires a new syntax for the return statement.
80For consistency, the return statement in \CFA accepts a comma-separated list of expressions in square brackets.
81The 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.
82A multiple-returning function with return type @T@ can return any expression that is implicitly convertible to @T@.
83Using the running example, the @most_frequent@ function can be written using multiple return values as such,
84\begin{cfacode}
85[int, char] most_frequent(const char * str) {
86  char freqs [26] = { 0 };
87  int ret_freq = 0;
88  char ret_ch = 'a';  // arbitrary default value for consistent results
89  for (int i = 0; str[i] != '\0'; ++i) {
90    if (isalpha(str[i])) {        // only count letters
91      int ch = tolower(str[i]);   // convert to lower case
92      int idx = ch-'a';
93      if (++freqs[idx] > ret_freq) {  // update on new max
94        ret_freq = freqs[idx];
95        ret_ch = ch;
96      }
97    }
98  }
99  return [ret_freq, ret_ch];
100}
101\end{cfacode}
102This 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.
103
104The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site.
105The simplest mechanism for retaining a return value in C is variable assignment.
106By assigning the return value into a variable, its value can be retrieved later at any point in the program.
107As such, \CFA allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions on the left side.
108\begin{cfacode}
109const char * str = "hello world";
110int freq;
111char ch;
112[freq, ch] = most_frequent(str);  // assign into multiple variables
113printf("%s -- %d %c\n", str, freq, ch);
114\end{cfacode}
115It is also common to use a function's output as the input to another function.
116\CFA also allows this case, without any new syntax.
117When 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}.
118For example,
119\begin{cfacode}
120void process(int);       // (1)
121void process(char);      // (2)
122void process(int, char); // (3)
123void process(char, int); // (4)
124
125process(most_frequent("hello world"));  // selects (3)
126\end{cfacode}
127In this case, there is only one option for a function named @most_frequent@ that takes a string as input.
128This function returns two values, one @int@ and one @char@.
129There 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.
130This 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.
131
132\section{Tuple Expressions}
133Multiple-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.
134These notions can be generalized to provide \CFA with \emph{tuple expressions} and \emph{tuple types}.
135A tuple expression is an expression producing a fixed-size, ordered list of values of heterogeneous types.
136The type of a tuple expression is the tuple of the subexpression types, or a \emph{tuple type}.
137In \CFA, a tuple expression is denoted by a comma-separated list of expressions enclosed in square brackets.
138For example, the expression @[5, 'x', 10.5]@ has type @[int, char, double]@.
139The previous expression has 3 \emph{components}.
140Each component in a tuple expression can be any \CFA expression, including another tuple expression.
141The order of evaluation of the components in a tuple expression is unspecified, to allow a compiler the greatest flexibility for program optimization.
142It is, however, guaranteed that each component of a tuple expression is evaluated for side-effects, even if the result is not used.
143Multiple-return-value functions can equivalently be called \emph{tuple-returning functions}.
144
145\subsection{Tuple Variables}
146The 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.
147In \CFA, it is possible to overcome this restriction by declaring a \emph{tuple variable}.
148\begin{cfacode}[emph=ret, emphstyle=\color{red}]
149const char * str = "hello world";
150[int, char] ret = most_frequent(str);  // initialize tuple variable
151printf("%s -- %d %c\n", str, ret);
152\end{cfacode}
153It 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.
154These variables can be used in any of the contexts where a tuple expression is allowed, such as in the @printf@ function call.
155As in the @process@ example, the components of the tuple value are passed as separate parameters to @printf@, allowing very simple printing of tuple expressions.
156One way to access the individual components is with a simple assignment, as in previous examples.
157\begin{cfacode}
158int freq;
159char ch;
160[freq, ch] = ret;
161\end{cfacode}
162
163\begin{sloppypar}
164In addition to variables of tuple type, it is also possible to have pointers to tuples, and arrays of tuples.
165Tuple 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.
166\begin{cfacode}
167[double, int] di;
168[double, int] * pdi
169[double, int] adi[10];
170\end{cfacode}
171This examples declares a variable of type @[double, int]@, a variable of type pointer to @[double, int]@, and an array of ten @[double, int]@.
172\end{sloppypar}
173
174\subsection{Tuple Indexing}
175At times, it is desirable to access a single component of a tuple-valued expression without creating unnecessary temporary variables to assign to.
176Given 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@.
177For example,
178\begin{cfacode}
179[int, double] x;
180[char *, int] f();
181void g(double, int);
182[int, double] * p;
183
184int y = x.0;              // access int component of x
185y = f().1;                // access int component of f
186p->0 = 5;                 // access int component of tuple pointed-to by p
187g(x.1, x.0);              // rearrange x to pass to g
188double z = [x, f()].0.1;  // access second component of first component
189                          // of tuple expression
190\end{cfacode}
191As 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.
192This feature was proposed for \KWC but never implemented \cite[p.~45]{Till89}.
193
194\subsection{Flattening and Structuring}
195As evident in previous examples, tuples in \CFA do not have a rigid structure.
196In function call contexts, tuples support implicit flattening and restructuring conversions.
197Tuple flattening recursively expands a tuple into the list of its basic components.
198Tuple structuring packages a list of expressions into a value of tuple type.
199\begin{cfacode}
200int f(int, int);
201int g([int, int]);
202int h(int, [int, int]);
203[int, int] x;
204int y;
205
206f(x);      // flatten
207g(y, 10);  // structure
208h(x, y);   // flatten & structure
209\end{cfacode}
210In \CFA, each of these calls is valid.
211In the call to @f@, @x@ is implicitly flattened so that the components of @x@ are passed as the two arguments to @f@.
212For 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@.
213Finally, 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]@.
214The 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.
215
216In \KWC \cite{Buhr94a,Till89}, there were 4 tuple coercions: opening, closing, flattening, and structuring.
217Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value.
218Flattening 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.
219Structuring moves in the opposite direction, \ie it takes a flat tuple value and provides structure by introducing nested tuple components.
220
221In \CFA, the design has been simplified to require only the two conversions previously described, which trigger only in function call and return situations.
222This simplification is a primary contribution of this thesis to the design of tuples in \CFA.
223Specifically, the expression resolution algorithm examines all of the possible alternatives for an expression to determine the best match.
224In resolving a function call expression, each combination of function value and list of argument alternatives is examined.
225Given a particular argument list and function value, the list of argument alternatives is flattened to produce a list of non-tuple valued expressions.
226Then the flattened list of expressions is compared with each value in the function's parameter list.
227If 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.
228If 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.
229Assuming 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.
230For example, in
231\begin{cfacode}
232int f(int, [double, int]);
233f([5, 10.2], 4);
234\end{cfacode}
235There is only a single definition of @f@, and 3 arguments with only single interpretations.
236First, the argument alternative list @[5, 10.2], 4@ is flattened to produce the argument list @5, 10.2, 4@.
237Next, the parameter matching algorithm begins, with $P = $@int@ and $A = $@int@, which unifies exactly.
238Moving to the next parameter and argument, $P = $@[double, int]@ and $A = $@double@.
239This time, the parameter is a tuple type, so the algorithm applies recursively with $P' = $@double@ and $A = $@double@, which unifies exactly.
240Then $P' = $@int@ and $A = $@double@, which again unifies exactly.
241At this point, the end of $P'$ has been reached, so the arguments @10.2, 4@ are structured into the tuple expression @[10.2, 4]@.
242Finally, the end of the parameter list $P$ has also been reached, so the final expression is @f(5, [10.2, 4])@.
243
244\section{Tuple Assignment}
245\label{s:TupleAssignment}
246An assignment where the left side of the assignment operator has a tuple type is called tuple assignment.
247There 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.
248\begin{cfacode}
249int x;
250double y;
251[int, double] z;
252[y, x] = 3.14;  // mass assignment
253[x, y] = z;     // multiple assignment
254z = 10;         // mass assignment
255z = [x, y];     // multiple assignment
256\end{cfacode}
257Let $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.
258
259For a multiple assignment to be valid, both tuples must have the same number of elements when flattened.
260For example, the following is invalid because the number of components on the left does not match the number of components on the right.
261\begin{cfacode}
262[int, int] x, y, z;
263[x, y] = z;   // multiple assignment, invalid 4 != 2
264\end{cfacode}
265Multiple assignment assigns $R_i$ to $L_i$ for each $i$.
266That is, @?=?(&$L_i$, $R_i$)@ must be a well-typed expression.
267In 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.
268
269A mass assignment assigns the value $R$ to each $L_i$.
270For a mass assignment to be valid, @?=?(&$L_i$, $R$)@ must be a well-typed expression.
271These 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.
272For 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@.
273On 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.
274
275Both 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.
276As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function.
277\begin{cfacode}
278int x = 10, y = 20;
279[x, y] = [y, x];
280\end{cfacode}
281After executing this code, @x@ has the value @20@ and @y@ has the value @10@.
282
283In \CFA, tuple assignment is an expression where the result type is the type of the left side of the assignment, as in normal assignment.
284That is, a tuple assignment produces the value of the left-hand side after assignment.
285These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted.
286These 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.
287Restricting 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.
288While 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.
289Furthermore, 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.
290In 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.
291In addition, \KWC permits the compiler to optimize tuple assignment as a block copy, since it does not support user-defined assignment operators.
292This optimization could be implemented in \CFA, but it requires the compiler to verify that the selected assignment operator is trivial.
293
294The following example shows multiple, mass, and cascading assignment used in one expression
295\begin{cfacode}
296  int a, b;
297  double c, d;
298  [void] f([int, int]);
299  f([c, a] = [b, d] = 1.5);  // assignments in parameter list
300\end{cfacode}
301The 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.
302That 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]@.
303Finally, the tuple @[1, 1]@ is used as an expression in the call to @f@.
304
305\subsection{Tuple Construction}
306Tuple 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.
307As 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.
308\begin{cfacode}
309struct S;
310void ?{}(S *);         // (1)
311void ?{}(S *, int);    // (2)
312void ?{}(S * double);  // (3)
313void ?{}(S *, S);      // (4)
314
315[S, S] x = [3, 6.28];  // uses (2), (3), specialized constructors
316[S, S] y;              // uses (1), (1), default constructor
317[S, S] z = x.0;        // uses (4), (4), copy constructor
318\end{cfacode}
319In 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)@.
320@z@ is initialized by mass copy constructor calls @?{}(&z.0, x.0)@ and @?{}(&z.1, x.0)@.
321Finally, @x@, @y@, and @z@ are destructed, \ie the calls @^?{}(&x.0)@, @^?{}(&x.1)@, @^?{}(&y.0)@, @^?{}(&y.1)@, @^?{}(&z.0)@, and @^?{}(&z.1)@.
322
323It 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.
324For example, the function @void ?{}([T, U] *, S);@ can be defined to allow a tuple variable to be constructed from a value of type @S@.
325\begin{cfacode}
326struct S { int x; double y; };
327void ?{}([int, double] * this, S s) {
328  this->0 = s.x;
329  this->1 = s.y;
330}
331\end{cfacode}
332Due 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.
333For example,
334\begin{cfacode}
335struct S { int x; double y; int z };
336[int, double] t;
337S s = t;
338\end{cfacode}
339The 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.
340
341\section{Member-Access Tuple Expression}
342\label{s:MemberAccessTuple}
343It is possible to access multiple fields from a single expression using a \emph{Member-Access Tuple Expression}.
344The result is a single tuple-valued expression whose type is the tuple of the types of the members.
345For example,
346\begin{cfacode}
347struct S { int x; double y; char * z; } s;
348s.[x, y, z];
349\end{cfacode}
350Here, the type of @s.[x, y, z]@ is @[int, double, char *]@.
351A 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.
352Then the type of @a.[x, y, z]@ is @[T_x, T_y, T_z]@.
353
354Since 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.).
355\begin{cfacode}
356[int, int, long, double] x;
357void f(double, long);
358
359f(x.[0, 3]);          // f(x.0, x.3)
360x.[0, 1] = x.[1, 0];  // [x.0, x.1] = [x.1, x.0]
361[long, int, long] y = x.[2, 0, 2];
362\end{cfacode}
363
364It is possible for a member tuple expression to contain other member access expressions.
365For example,
366\begin{cfacode}
367struct A { double i; int j; };
368struct B { int * k; short l; };
369struct C { int x; A y; B z; } v;
370v.[x, y.[i, j], z.k];
371\end{cfacode}
372This expression is equivalent to @[v.x, [v.y.i, v.y.j], v.z.k]@.
373That is, the aggregate expression is effectively distributed across the tuple, which allows simple and easy access to multiple components in an aggregate, without repetition.
374It is guaranteed that the aggregate expression to the left of the @.@ in a member tuple expression is evaluated exactly once.
375As such, it is safe to use member tuple expressions on the result of a side-effecting function.
376\begin{cfacode}
377[int, float, double] f();
378[double, float] x = f().[2, 1];
379\end{cfacode}
380
381In \KWC, member tuple expressions are known as \emph{record field tuples} \cite{Till89}.
382Since \CFA permits these tuple-access expressions using structures, unions, and tuples, \emph{member tuple expression} or \emph{field tuple expression} is more appropriate.
383
384It is possible to extend member-access expressions further.
385Currently, 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.
386In the interest of orthogonal design, \CFA could apply some meaning to the remaining combinations as well.
387For example,
388\begin{cfacode}
389struct S { int x, y; } s;
390[S, S] z;
391
392s.x;  // access member
393z.0;  // access component
394
395s.1;  // ???
396z.y;  // ???
397\end{cfacode}
398One possibility is for @s.1@ to select the second member of @s@.
399Under this interpretation, it becomes possible to not only access members of a struct by name, but also by position.
400Likewise, it seems natural to open this mechanism to enumerations as well, wherein the left side would be a type, rather than an expression.
401One benefit of this interpretation is familiarity, since it is extremely reminiscent of tuple-index expressions.
402On 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.
403This 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.
404
405As for @z.y@, one interpretation is to extend the meaning of member tuple expressions.
406That is, currently the tuple must occur as the member, \ie to the right of the dot.
407Allowing 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.
408In 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@.
409It 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.
410Perhaps 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.
411The 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.
412
413Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member-access expressions versus member-tuple expressions.
414\begin{cfacode}
415struct { int x, y; };
416[S, S] z;
417z.[x, y];  // ???
418// => [z.0, z.1].[x, y]
419// => [z.0.x, z.0.y, z.1.x, z.1.y]
420// or
421// => [z.x, z.y]
422// => [[z.0, z.1].x, [z.0, z.1].y]
423// => [z.0.x, z.1.x, z.0.y, z.1.y]
424\end{cfacode}
425Depending on exactly how the two tuples are combined, different results can be achieved.
426As such, a specific ordering would need to be imposed to make this feature useful.
427Furthermore, 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.
428
429A second possibility is for \CFA to have named tuples, as they exist in Swift and D.
430\begin{cfacode}
431typedef [int x, int y] Point2D;
432Point2D p1, p2;
433p1.x + p1.y + p2.x + p2.y;
434p1.0 + p1.1 + p2.0 + p2.1;  // equivalent
435\end{cfacode}
436In this simpler interpretation, a tuple type carries with it a list of possibly empty identifiers.
437This approach fits naturally with the named return-value feature, and would likely go a long way towards implementing it.
438
439Ultimately, the first two extensions introduce complexity into the model, with relatively little perceived benefit, and so were dropped from consideration.
440Named tuples are a potentially useful addition to the language, provided they can be parsed with a reasonable syntax.
441
442
443\section{Casting}
444In C, the cast operator is used to explicitly convert between types.
445In \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.
446That 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.
447\begin{cfacode}
448int f();     // (1)
449double f();  // (2)
450
451f();       // ambiguous - (1),(2) both equally viable
452(int)f();  // choose (2)
453\end{cfacode}
454Since casting is a fundamental operation in \CFA, casts need to be given a meaningful interpretation in the context of tuples.
455Taking a look at standard C provides some guidance with respect to the way casts should work with tuples.
456\begin{cfacode}[numbers=left]
457int f();
458void g();
459
460(void)f();  // valid, ignore results
461(int)g();   // invalid, void cannot be converted to int
462
463struct A { int x; };
464(struct A)f();  // invalid, int cannot be converted to A
465\end{cfacode}
466In C, line 4 is a valid cast, which calls @f@ and discards its result.
467On the other hand, line 5 is invalid, because @g@ does not produce a result, so requesting an @int@ to materialize from nothing is nonsensical.
468Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite[p.~91]{C11}.
469For 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.
470
471Formally, 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$.
472Excess 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.
473This discarding naturally follows the way that a cast to void works in C.
474
475For example,
476\begin{cfacode}
477  [int, int, int] f();
478  [int, [int, int], int] g();
479
480  ([int, double])f();           // (1) valid
481  ([int, int, int])g();         // (2) valid
482  ([void, [int, int]])g();      // (3) valid
483  ([int, int, int, int])g();    // (4) invalid
484  ([int, [int, int, int]])g();  // (5) invalid
485\end{cfacode}
486
487(1) discards the last element of the return value and converts the second element to type double.
488Since @int@ is effectively a 1-element tuple, (2) discards the second component of the second element of the return value of @g@.
489If @g@ is free of side effects, this is equivalent to @[(int)(g().0), (int)(g().1.0), (int)(g().2)]@.
490Since @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)]@).
491% 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).
492Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions.
493As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3.
494Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid.
495That is, it is invalid to cast @[int, int]@ to @[int, int, int]@.
496
497\section{Polymorphism}
498Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with non-tuple types.
499The integration of polymorphism, type assertions, and monomorphic specialization of tuple-assertions are a primary contribution of this thesis to the design of tuples.
500\begin{cfacode}
501forall(otype T, dtype U)
502void f(T x, U * y);
503
504f([5, "hello"]);
505\end{cfacode}
506In this example, @[5, "hello"]@ is flattened, so that the argument list appears as @5, "hello"@.
507The argument matching algorithm binds @T@ to @int@ and @U@ to @const char@, and calls the function as normal.
508
509Tuples can contain otype and dtype components.
510For example, a plus operator can be written to add two triples of a type together.
511\begin{cfacode}
512forall(otype T | { T ?+?(T, T); })
513[T, T, T] ?+?([T, T, T] x, [T, T, T] y) {
514  return [x.0+y.0, x.1+y.1, x.2+y.2];
515}
516[int, int, int] x;
517int i1, i2, i3;
518[i1, i2, i3] = x + ([10, 20, 30]);
519\end{cfacode}
520Note that due to the implicit tuple conversions, this function is not restricted to the addition of two triples.
521A 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@.
522For example, these expressions also succeed and produce the same value.
523\begin{cfacode}
524([x.0, x.1]) + ([x.2, 10, 20, 30]);  // x + ([10, 20, 30])
525x.0 + ([x.1, x.2, 10, 20, 30]);      // x + ([10, 20, 30])
526\end{cfacode}
527This presents a potential problem if structure is important, as these three expressions look like they should have different meanings.
528Furthermore, these calls can be made ambiguous by introducing seemingly different functions.
529\begin{cfacode}
530forall(otype T | { T ?+?(T, T); })
531[T, T, T] ?+?([T, T] x, [T, T, T, T]);
532forall(otype T | { T ?+?(T, T); })
533[T, T, T] ?+?(T x, [T, T, T, T, T]);
534\end{cfacode}
535It 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.
536Still, these semantics are a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate.
537These 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.
538Care would be needed in this case to ensure that exact matches do not incur such a cost.
539\begin{cfacode}
540void f([int, int], int, int);
541
542f([0, 0], 0, 0);    // no cost
543f(0, 0, 0, 0);      // cost for structuring
544f([0, 0,], [0, 0]); // cost for flattening
545f([0, 0, 0], 0);    // cost for flattening and structuring
546\end{cfacode}
547
548Until 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).
549This decision presents a conflict with the flexibility of tuples.
550\subsection{Assertion Inference}
551\begin{cfacode}
552int f([int, double], double);
553forall(otype T, otype U | { T f(T, U, U); })
554void g(T, U);
555g(5, 10.21);
556\end{cfacode}
557If 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.
558Since tuples are fluid, this requirement reduces the usability of tuples in polymorphic code.
559To 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.
560
561This relaxation is made possible by extending the existing thunk generation scheme, as described by Bilson \cite{Bilson03}.
562Now, 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.
563\begin{cfacode}
564int _thunk(int _p0, double _p1, double _p2) {
565  return f([_p0, _p1], _p2);
566}
567\end{cfacode}
568Essentially, this provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
569
570\section{Implementation}
571Tuples are implemented in the \CFA translator via a transformation into generic types.
572Generic types are an independent contribution developed at the same time.
573The transformation into generic types and the generation of tuple-specific code are primary contributions of this thesis to tuples.
574
575The first time an $N$-tuple is seen for each $N$ in a scope, a generic type with $N$ type parameters is generated.
576For example,
577\begin{cfacode}
578[int, int] f() {
579  [double, double] x;
580  [int, double, int] y;
581}
582\end{cfacode}
583is transformed into
584\begin{cfacode}
585forall(dtype T0, dtype T1 | sized(T0) | sized(T1))
586struct _tuple2_ {  // generated before the first 2-tuple
587  T0 field_0;
588  T1 field_1;
589};
590_tuple2_(int, int) f() {
591  _tuple2_(double, double) x;
592  forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2))
593  struct _tuple3_ {  // generated before the first 3-tuple
594    T0 field_0;
595    T1 field_1;
596    T2 field_2;
597  };
598  _tuple3_(int, double, int) y;
599}
600\end{cfacode}
601
602Tuple expressions are then simply converted directly into compound literals
603\begin{cfacode}
604[5, 'x', 1.24];
605\end{cfacode}
606becomes
607\begin{cfacode}
608(_tuple3_(int, char, double)){ 5, 'x', 1.24 };
609\end{cfacode}
610
611Since tuples are essentially structures, tuple indexing expressions are just field accesses.
612\begin{cfacode}
613void f(int, [double, char]);
614[int, double] x;
615
616x.0+x.1;
617printf("%d %g\n", x);
618f(x, 'z');
619\end{cfacode}
620is transformed into
621\begin{cfacode}
622void f(int, _tuple2_(double, char));
623_tuple2_(int, double) x;
624
625x.field_0+x.field_1;
626printf("%d %g\n", x.field_0, x.field_1);
627f(x.field_0, (_tuple2){ x.field_1, 'z' });
628\end{cfacode}
629Note that due to flattening, @x@ used in the argument position is converted into the list of its fields.
630In the call to @f@, the second and third argument components are structured into a tuple argument.
631
632Expressions that may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion.
633Each unique expression is assigned an identifier and is guaranteed to be executed exactly once.
634\begin{cfacode}
635void g(int, double);
636[int, double] h();
637g(h());
638\end{cfacode}
639Internally, this is converted to pseudo-\CFA
640\begin{cfacode}
641void g(int, double);
642[int, double] h();
643lazy [int, double] unq0 = h(); // deferred execution
644g(unq0.0, unq0.1);             // execute h() once
645\end{cfacode}
646That is, the function @h@ is evaluated lazily and its result is stored for subsequent accesses.
647Ultimately, unique expressions are converted into two variables and an expression.
648\begin{cfacode}
649void g(int, double);
650[int, double] h();
651
652_Bool _unq0_finished_ = 0;
653[int, double] _unq0;
654g(
655  (_unq0_finished_ ? _unq0 : (_unq0 = h(), _unq0_finished_ = 1, _unq0)).0,
656  (_unq0_finished_ ? _unq0 : (_unq0 = h(), _unq0_finished_ = 1, _unq0)).1,
657);
658\end{cfacode}
659Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order.
660The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is set to true.
661Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression.
662
663Currently, the \CFA translator has a very broad, imprecise definition of impurity (side-effects), where every function call is assumed to be impure.
664This notion could be made more precise for certain intrinsic, auto-generated, and built-in functions, and could analyze function bodies, when they are available, to recursively detect impurity, to eliminate some unique expressions.
665It is possible that lazy evaluation could be exposed to the user through a lazy keyword with little additional effort.
666
667Tuple-member expressions are recursively expanded into a list of member-access expressions.
668\begin{cfacode}
669[int, [double, int, double], int]] x;
670x.[0, 1.[0, 2]];
671\end{cfacode}
672becomes
673\begin{cfacode}
674[x.0, [x.1.0, x.1.2]];
675\end{cfacode}
676Tuple-member expressions also take advantage of unique expressions in the case of possible impurity.
677
678Finally, the various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions.
679For example, a mass assignment
680\begin{cfacode}
681int x, z;
682double y;
683[double, double] f();
684
685[x, y, z] = 1.5;            // mass assignment
686\end{cfacode}
687generates the following
688\begin{cfacode}
689// [x, y, z] = 1.5;
690_tuple3_(int, double, int) _tmp_stmtexpr_ret0;
691({ // GNU C statement expression
692  // assign LHS address temporaries
693  int *__massassign_L0 = &x;    // ?{}
694  double *__massassign_L1 = &y; // ?{}
695  int *__massassign_L2 = &z;    // ?{}
696
697  // assign RHS value temporary
698  double __massassign_R0 = 1.5; // ?{}
699
700  ({ // tuple construction - construct statement expr return variable
701    // assign LHS address temporaries
702    int *__multassign_L0 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
703    double *__multassign_L1 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
704    int *__multassign_L2 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
705
706    // assign RHS value temporaries and mass-assign to L0, L1, L2
707    int __multassign_R0 = (*__massassign_L0=(int)__massassign_R0); // ?{}
708    double __multassign_R1 = (*__massassign_L1=__massassign_R0);   // ?{}
709    int __multassign_R2 = (*__massassign_L2=(int)__massassign_R0); // ?{}
710
711    // perform construction of statement expr return variable using
712    // RHS value temporary
713    ((*__multassign_L0 = __multassign_R0 /* ?{} */),
714     (*__multassign_L1 = __multassign_R1 /* ?{} */),
715     (*__multassign_L2 = __multassign_R2 /* ?{} */));
716  });
717  _tmp_stmtexpr_ret0;
718});
719({ // tuple destruction - destruct assign expr value
720  int *__massassign_L3 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
721  double *__massassign_L4 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
722  int *__massassign_L5 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
723  ((*__massassign_L3 /* ^?{} */),
724   (*__massassign_L4 /* ^?{} */),
725   (*__massassign_L5 /* ^?{} */));
726});
727\end{cfacode}
728A 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, \eg, in a unique expression.
729$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.
730A nested statement expression is generated that performs the individual assignments and constructs the return value using the results of the individual assignments.
731Finally, the statement expression temporary is destroyed at the end of the expression.
732
733Similarly, a multiple assignment
734\begin{cfacode}
735[x, y, z] = [f(), 3];       // multiple assignment
736\end{cfacode}
737generates the following
738\begin{cfacode}
739// [x, y, z] = [f(), 3];
740_tuple3_(int, double, int) _tmp_stmtexpr_ret0;
741({
742  // assign LHS address temporaries
743  int *__multassign_L0 = &x;    // ?{}
744  double *__multassign_L1 = &y; // ?{}
745  int *__multassign_L2 = &z;    // ?{}
746
747  // assign RHS value temporaries
748  _tuple2_(double, double) _tmp_cp_ret0;
749  _Bool _unq0_finished_ = 0;
750  double __multassign_R0 =
751    (_unq0_finished_ ?
752      _tmp_cp_ret0 :
753      (_tmp_cp_ret0=f(), _unq0_finished_=1, _tmp_cp_ret0)).0; // ?{}
754  double __multassign_R1 =
755    (_unq0_finished_ ?
756      _tmp_cp_ret0 :
757      (_tmp_cp_ret0=f(), _unq0_finished_=1, _tmp_cp_ret0)).1; // ?{}
758  ({ // tuple destruction - destruct f() return temporary
759    // assign LHS address temporaries
760    double *__massassign_L3 = (double *)&_tmp_cp_ret0.0;  // ?{}
761    double *__massassign_L4 = (double *)&_tmp_cp_ret0.1;  // ?{}
762    // perform destructions - intrinsic, so NOP
763    ((*__massassign_L3 /* ^?{} */),
764     (*__massassign_L4 /* ^?{} */));
765  });
766  int __multassign_R2 = 3; // ?{}
767
768  ({ // tuple construction - construct statement expr return variable
769    // assign LHS address temporaries
770    int *__multassign_L3 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
771    double *__multassign_L4 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
772    int *__multassign_L5 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
773
774    // assign RHS value temporaries and multiple-assign to L0, L1, L2
775    int __multassign_R3 = (*__multassign_L0=(int)__multassign_R0);  // ?{}
776    double __multassign_R4 = (*__multassign_L1=__multassign_R1);    // ?{}
777    int __multassign_R5 = (*__multassign_L2=__multassign_R2);       // ?{}
778
779    // perform construction of statement expr return variable using
780    // RHS value temporaries
781    ((*__multassign_L3=__multassign_R3 /* ?{} */),
782     (*__multassign_L4=__multassign_R4 /* ?{} */),
783     (*__multassign_L5=__multassign_R5 /* ?{} */));
784  });
785  _tmp_stmtexpr_ret0;
786});
787({  // tuple destruction - destruct assign expr value
788  // assign LHS address temporaries
789  int *__massassign_L5 = (int *)&_tmp_stmtexpr_ret0.0;       // ?{}
790  double *__massassign_L6 = (double *)&_tmp_stmtexpr_ret0.1; // ?{}
791  int *__massassign_L7 = (int *)&_tmp_stmtexpr_ret0.2;       // ?{}
792  // perform destructions - intrinsic, so NOP
793  ((*__massassign_L5 /* ^?{} */),
794   (*__massassign_L6 /* ^?{} */),
795   (*__massassign_L7 /* ^?{} */));
796});
797\end{cfacode}
798The difference here is that $N$ RHS values are stored into separate temporary variables.
799
800The 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.
801There 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.
Note: See TracBrowser for help on using the repository browser.