# source:doc/proposals/tuples/tuples.tex@ae45007

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since ae45007 was 484ee53, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago

209This naturally follows the way that a cast to void works in C.
210
211For example,
212\begin{lstlisting}
213  [int, int, int] f();
214  [int, [int, int], int] g();
215
216  ([int, double])f();           // (1)
217  ([int, int, int])g();         // (2)
218  ([void, [int, int]])g();      // (3)
219  ([int, int, int, int])g();    // (4)
220  ([int, [int, int, int]])g();  // (5)
221\end{lstlisting}
222
223(1) discards the last element of the return value and converts the second element to type double.
224
226
228
229(4) is invalid because the cast target type contains 4 components, while the source type contains only 3.
230
232
233
235Functions with tuple parameters can be used to provide type-safe variadic functions.
236It appears that it would be possible to leverage tuples to get similar power to what \CC vardiadic templates provide, but with the ability to separately compile them.
237
238\subsection{Option 1: Allow type parameters to match whole tuples, rather than just their components}
239This option could be implemented with two phases of argument matching when a function contains type parameters and the argument list contains tuple arguments.
240If 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 implicit conversions. \footnote{It may be desirable to skip the exact matching rule if flattening and structuring produce a match that fails when inferring assertion parameters, at least in the current resolver since our assertion inference appears to be very inefficient.}
241
242For example:
243\begin{lstlisting}
244  forall(otype T, otype U | { T g(U); })
245  void f(T, U);
246
247  [int, int] g([int, int, int, int]);
248
249  f([1, 2], [3, 4, 5, 6]);
250\end{lstlisting}
251With flattening and structuring, the call is first transformed into ©f(1, 2, 3, 4, 5, 6)©.
254There are now no remaining formal parameters, there are remaining arguments, and the function is not variadic, so the match fails.
255
258\footnote{This type of interaction between tuple arguments and type parameters is desirable for perfect forwarding, but it's not obvious to me exactly how this should interact with assertion inference. Ideally, the same rules should apply for assertion satisfaction as apply to argument matching (i.e. flattening \& structuring should be attempted, followed by an exact match attempt on failure), but this may be more complicated than it sounds for assertion satisfaction. Aaron, I'm especially interested to hear your thoughts on this with respect to efficiency in the resolver redesign.
259
260For example, should we allow this to match?
261\begin{lstlisting}
262  forall(otype T, otype U | { T g(U); })
263  void f(T, U);
264
265  [int, int] g(int, ®[int, int]®, int);
266
267  f([1, 2], [3, 4, 5, 6]);
268\end{lstlisting}
269To only have an exact matching rule here feels too strict. At the very least, it would be nice to accept ©[int, int] g(int, int, int, int)©, since that would allow for argument lists to be packaged and sent off to polymorphic functions and then directly forwarded to other functions.}.
270
271The addition of an exact matching rule only affects the outcome for polymorphic type binding when tuples are involved.
272For non-tuple arguments, exact matching and flattening \& structuring are equivalent. For tuple arguments to a function without polymorphic formal parameters, flattening and structuring work whenever an exact match would have worked (the tuple is flattened and implicitly restructured to its original structure).
273Thus 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.
274
275\subsection{Option 2: Add another type parameter kind}
277There should be at most one ©ttype© parameter which must occur last in a parameter list.
278Matching against a ©ttype© parameter would consume/package all remaining argument components into a tuple, and would also match no arguments.
279These semantics more closely match normal variadic semantics, while being type-safe. C 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.\footnote{In fact, if we go with this proposal, it might be desirable to disallow polymorphic functions to use C variadic syntax to encourage a Cforall style. Aside from maybe calling C variadic functions, it's not obvious to me there would be anything you can do with C variadics that couldn't also be done with ©ttype© parameters. }
280
281Example 1: taken from Wikipedia, demonstrates variadic templates done in a Cforall style
282\begin{lstlisting}
283  void func(void) {}                           // termination version (1)
284  forall(otype T, ttype Params | { void process(const T &); void func(const Params &); })
285  void func(const T& arg1, const Params & p) { // (2)
286    process(arg1);
287    func(p);
288  }
289  void process(int);                           // (3)
290  void process(double);                        // (4)
291  func(1, 2.0, 3.5, 4);
292\end{lstlisting}
295Since (2) requires assertion parameters, the process repeats selecting (4) and (2).
296The matching process continues recursively until reaching the base case where (3) and (1) are selected.
298
299Since (2) is not an exact match for the expected assertion parameter, a thunk is generated that wraps a call to ©func© that accepts an argument of type ©[double, double, int]©.
300This conversion already occurs in the Cforall translator, but may require some modification to handle all of the cases present here.
301
302Example 2: new (i.e. type-safe malloc + constructors)
303\begin{lstlisting}
304  forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
305  T * new(Params p) {
306    return malloc(){ p };
307  }
308  array(int) * x = new(1, 2, 3, 4);
309\end{lstlisting}
311
312Assertion inference can also be special cased to match functions that take tuples of any structure only for ttype parameters, if desired.
313
314
315\subsection{Conclusions}
316With either option, we can generate a thunk to perform the conversion from the actual argument's structure to the structure expected by the assertion parameter and that function would be passed as the assertion argument, in a manner similar to the other thunks that are already generated.
317
318I prefer option 2, because it is simpler and I think the semantics are clearer.
319I wouldn't be surprised if it was also noticeably more efficient, because of the lack of backtracking.
320
321As a side note, option 1 also requires calls to be written explicitly, e.g. ©array(int) * x = new([1, 2, 3, 4]);©, which isn't particularly appealing.
322It shifts the burden from the compiler to the programmer, which is almost always wrong, and doesn't match with the way our tuples can be used elsewhere.
323The more I think about it, the more I'm convinced option 1 is the wrong approach, but I'm putting it out anyway in case someone has a good thought on how to make it work correctly.
324
326\bibliographystyle{plain}
327\bibliography{pl}
328