source: doc/rob_thesis/variadic.tex @ fbd7ad6

Last change on this file since fbd7ad6 was 7493339, checked in by Rob Schluntz <rschlunt@…>, 7 years ago

incorporate Peter's feedback, handle many TODOs

  • Property mode set to 100644
File size: 23.5 KB
2\chapter{Variadic Functions}
5\section{Design Criteria} % TOOD: better section name???
6C provides variadic functions through the manipulation of @va_list@ objects.
7A variadic function is one which contains at least one parameter, followed by @...@ as the last token in the parameter list.
8In particular, some form of \emph{argument descriptor} is needed to inform the function of the number of arguments and their types.
9Two common argument descriptors are format strings or counter parameters.
10It is important to note that both of these mechanisms are inherently redundant, because they require the user to specify information that the compiler knows explicitly.
11This required repetition is error prone, because it is easy for the user to add or remove arguments without updating the argument descriptor.
12In addition, C requires the programmer to hard code all of the possible expected types.
13As a result, it is cumbersome to write a function that is open to extension.
14For example, a simple function which sums $N$ @int@s,
16int sum(int N, ...) {
17  va_list args;
18  va_start(args, N);
19  int ret = 0;
20  while(N) {
21    ret += va_arg(args, int);  // have to specify type
22    N--;
23  }
24  va_end(args);
25  return ret;
27sum(3, 10, 20, 30);  // need to keep counter in sync
29The @va_list@ type is a special C data type that abstracts variadic argument manipulation.
30The @va_start@ macro initializes a @va_list@, given the last named parameter.
31Each use of the @va_arg@ macro allows access to the next variadic argument, given a type.
32Since 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.
33As such, it is possible to pass any value to the @sum@ function, including pointers, floating-point numbers, and structures.
34In 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[p.~81]{C11}.
35Furthermore, 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.
36Since they rely on programmer convention rather than compile-time checks, variadic functions are generally unsafe.
38In practice, compilers can provide warnings to help mitigate some of the problems.
39For 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.
40Unfortunately, this approach does not permit extensions to the format string syntax, so a programmer cannot extend the attribute to warn for mismatches with custom types.
42As a result, C's variadic functions are a deficient language feature.
43Two options were examined to provide better, type-safe variadic functions in \CFA.
44\subsection{Whole Tuple Matching}
45Option 1 is to change the argument matching algorithm, so that type parameters can match whole tuples, rather than just their components.
46This option could be implemented with two phases of argument matching when a function contains type parameters and the argument list contains tuple arguments.
47If 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.
48For example:
50  forall(otype T, otype U | { T g(U); })
51  void f(T, U);
53  [int, int] g([int, int, int, int]);
55  f([1, 2], [3, 4, 5, 6]);
57With flattening and structuring, the call is first transformed into @f(1, 2, 3, 4, 5, 6)@.
58Since 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.
59Likewise, @U@ does not have a tuple type, so @U=int@ and @2@ is accepted as the second parameter.
60There are now no remaining formal parameters, but there are remaining arguments and the function is not variadic, so the match fails.
62With the addition of an exact matching attempt, @T=[int,int]@ and @U=[int,int,int,int]@, and so the arguments type check.
63Likewise, when inferring assertion @g@, an exact match is found.
65This 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.
66For example, consider a @new@ function that allocates memory using @malloc@ and constructs the result, using arbitrary arguments.
68struct Array;
69void ?{}(Array *, int, int, int);
71forall(dtype T, otype Params | sized(T) | { void ?{}(T *, Params); })
72T * new(Params p) {
73  return malloc(){ p };
75Array(int) * x = new([1, 2, 3]);
77The 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.
78This shifts the burden from the compiler to the programmer, which is almost always wrong, and creates an odd inconsistency within the language.
79Similarly, 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.
81It should be otherwise noted that the addition of an exact matching rule only affects the outcome for polymorphic type binding when tuples are involved.
82For non-tuple arguments, exact matching and flattening and structuring are equivalent.
83For 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.
84Thus 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.
86Overall, this option takes a step in the right direction, but is contrary to the flexibility of the existing tuple design.
88\subsection{A New Typeclass}
89A second option is the addition of another kind of type parameter, @ttype@.
90Matching against a @ttype@ parameter consumes all remaining argument components and packages them into a tuple, binding to the resulting tuple of types.
91In 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.
92This idea essentially matches normal variadic semantics, with a strong feeling of similarity to \CCeleven variadic templates.
93As such, @ttype@ variables are also referred to as argument packs.
94This approach is the option that has been added to \CFA.
96Like variadic templates, the main way to manipulate @ttype@ polymorphic functions is through recursion.
97Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful.
98Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled.
100For example, a simple translation of the C sum function using @ttype@ is
102int sum(void){ return 0; }        // (0)
103forall(ttype Params | { int sum(Params); })
104int sum(int x, Params rest) { // (1)
105  return x+sum(rest);
107sum(10, 20, 30);
109Since (0) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@.
110In 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]@.
111In order to finish the resolution of @sum@, an assertion parameter that matches @int sum(int, int)@ is required.
112Like 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)@.
113Next, (0) fails, and to satisfy (1) @Params@ is bound to @[]@, requiring an assertion @int sum()@.
114Finally, (0) matches and (1) fails, which terminates the recursion.
115Effectively, 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))@.
117Interestingly, this version does not require any form of argument descriptor, since the \CFA type system keeps track of all of these details.
118It might be reasonable to take the @sum@ function a step further to enforce a minimum number of arguments, which could be done simply
120int sum(int x, int y){
121  return x+y;
123forall(ttype Params | { int sum(int, Params); })
124int sum(int x, int y, Params rest) {
125  return sum(x+y, rest);
127sum(10);          // invalid
128sum(10, 20);      // valid
129sum(10, 20, 30);  // valid
133One more iteration permits the summation of any summable type, as long as all arguments are the same type.
135trait summable(otype T) {
136  T ?+?(T, T);
138forall(otype R | summable(R))
139R sum(R x, R y){
140  return x+y;
142forall(otype R, ttype Params
143  | summable(R)
144  | { R sum(R, Params); })
145R sum(R x, R y, Params rest) {
146  return sum(x+y, rest);
148sum(3, 10, 20, 30);
150Unlike C, it is not necessary to hard code the expected type.
151This @sum@ function is naturally open to extension, in that any user-defined type with a @?+?@ operator is automatically able to be used with the @sum@ function.
152That 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.
154Going one last step, it is possible to achieve full generality in \CFA, allowing the summation of arbitrary lists of summable types.
156trait summable(otype T1, otype T2, otype R) {
157  R ?+?(T1, T2);
159forall(otype T1, otype T2, otype R | summable(T1, T2, R))
160R sum(T1 x, T2 y) {
161  return x+y;
163forall(otype T1, otype T2, otype T3, ttype Params, otype R
164  | summable(T1, T2, T3)
165  | { R sum(T3, Params); })
166R sum(T1 x, T2 y, Params rest ) {
167  return sum(x+y, rest);
169sum(3, 10.5, 20, 30.3);
171The \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.
173A notable limitation of this approach is that it heavily relies on recursive assertions.
174The \CFA translator imposes a limitation on the depth of the recursion for assertion satisfaction.
175Currently, the limit is set to 4, which means that the first iteration of the @sum@ function is limited to at most 5 arguments, while the second iteration can support up to 6 arguments.
176The limit is set low due to inefficiencies in the current implementation of the \CFA expression resolver.
177There is ongoing work to improve the performance of the resolver, and with noticeable gains, the limit can be relaxed to allow longer argument lists to @ttype@ functions.
179C 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.
180Furthermore, it might be desirable to disallow polymorphic functions to use C variadic syntax to encourage a Cforall style.
181Aside 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.
183Variadic templates in \CC require an ellipsis token to express that a parameter is a parameter pack and to expand a parameter pack.
184\CFA does not need an ellipsis in either case, since the type class @ttype@ is only used for variadics.
185An alternative design is to use an ellipsis combined with an existing type class.
186This 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.
188template<typename... Args>
189void f(Args &... args) {
190  g(&args...);  // expand to addresses of pack elements
193As such, the addition of an ellipsis token would be purely an aesthetic change in \CFA today.
195It is possible to write a type-safe variadic print routine, which can replace @printf@
197struct S { int x, y; };
198forall(otype T, ttype Params |
199  { void print(T); void print(Params); })
200void print(T arg, Params rest) {
201  print(arg);
202  print(rest);
204void print(char * x) { printf("%s", x); }
205void print(int x) { printf("%d", x);  }
206void print(S s) { print("{ ", s.x, ",", s.y, " }"); }
207print("s = ", (S){ 1, 2 }, "\n");
209This example routine showcases a variadic-template-like decomposition of the provided argument list.
210The individual @print@ routines allow printing a single element of a type.
211The polymorphic @print@ allows printing any list of types, as long as each individual type has a @print@ function.
212The 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.
214It is also possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
215For example, it is possible to write @new@ as a library function.
217struct Array;
218void ?{}(Array *, int, int, int);
220forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
221T * new(Params p) {
222  return malloc(){ p }; // construct result of malloc
224Array * x = new(1, 2, 3);
226The @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.
227This approach provides the type-safety of @new@ in \CC, without the need to specify the allocated type, thanks to return-type inference.
229In 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.
233The definition of @new@
235forall(dtype T | sized(T)) T * malloc();
237forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
238T * new(Params p) {
239  return malloc(){ p }; // construct result of malloc
242Generates the following
244void *malloc(long unsigned int _sizeof_T, long unsigned int _alignof_T);
246void *new(
247  void (*_adapter_)(void (*)(), void *, void *),
248  long unsigned int _sizeof_T,
249  long unsigned int _alignof_T,
250  long unsigned int _sizeof_Params,
251  long unsigned int _alignof_Params,
252  void (* _ctor_T)(void *, void *),
253  void *p
255  void *_retval_new;
256  void *_tmp_cp_ret0;
257  void *_tmp_ctor_expr0;
258  _retval_new=
259    (_adapter_(_ctor_T,
260      (_tmp_ctor_expr0=(_tmp_cp_ret0=malloc(_sizeof_2tT, _alignof_2tT),
261        _tmp_cp_ret0)),
262      p),
263    _tmp_ctor_expr0); // ?{}
264  *(void **)&_tmp_cp_ret0; // ^?{}
265  return _retval_new;
268The constructor for @T@ is called indirectly through the adapter function on the result of @malloc@ and the parameter pack.
269The variable that was allocated and constructed is then returned from @new@.
271A call to @new@
273struct S { int x, y; };
274void ?{}(S *, int, int);
276S * s = new(3, 4);
278Generates the following
280struct _tuple2_ {  // _tuple2_(T0, T1)
281  void *field_0;
282  void *field_1;
284struct _conc__tuple2_0 {  // _tuple2_(int, int)
285  int field_0;
286  int field_1;
288struct _conc__tuple2_0 _tmp_cp1;  // tuple argument to new
289struct S *_tmp_cp_ret1;           // return value from new
290void _thunk0(  // ?{}(S *, [int, int])
291  struct S *_p0,
292  struct _conc__tuple2_0 _p1
294  _ctor_S(_p0, _p1.field_0, _p1.field_1);  // restructure tuple parameter
296void _adapter(void (*_adaptee)(), void *_p0, void *_p1){
297  // apply adaptee to arguments after casting to actual types
298  ((void (*)(struct S *, struct _conc__tuple2_0))_adaptee)(
299    _p0,
300    *(struct _conc__tuple2_0 *)_p1
301  );
303struct S *s = (struct S *)(_tmp_cp_ret1=
304  new(
305    _adapter,
306    sizeof(struct S),
307    __alignof__(struct S),
308    sizeof(struct _conc__tuple2_0),
309    __alignof__(struct _conc__tuple2_0),
310    (void (*)(void *, void *))&_thunk0,
311    (({ // copy construct tuple argument to new
312      int *__multassign_L0 = (int *)&_tmp_cp1.field_0;
313      int *__multassign_L1 = (int *)&_tmp_cp1.field_1;
314      int __multassign_R0 = 3;
315      int __multassign_R1 = 4;
316      ((*__multassign_L0=__multassign_R0 /* ?{} */) ,
317       (*__multassign_L1=__multassign_R1 /* ?{} */));
318    }), &_tmp_cp1)
319  ), _tmp_cp_ret1);
320*(struct S **)&_tmp_cp_ret1; // ^?{}  // destroy return value from new
321({  // destroy argument temporary
322  int *__massassign_L0 = (int *)&_tmp_cp1.field_0;
323  int *__massassign_L1 = (int *)&_tmp_cp1.field_1;
324  ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
327Of note, @_thunk0@ is generated to translate calls to @?{}(S *, [int, int])@ into calls to @?{}(S *, int, int)@.
328The call to @new@ constructs a tuple argument using the supplied arguments.
330The @print@ function
332forall(otype T, ttype Params |
333  { void print(T); void print(Params); })
334void print(T arg, Params rest) {
335  print(arg);
336  print(rest);
341void print_variadic(
342  void (*_adapterF_7tParams__P)(void (*)(), void *),
343  void (*_adapterF_2tT__P)(void (*)(), void *),
344  void (*_adapterF_P2tT2tT__MP)(void (*)(), void *, void *),
345  void (*_adapterF2tT_P2tT2tT_P_MP)(void (*)(), void *, void *, void *),
346  long unsigned int _sizeof_T,
347  long unsigned int _alignof_T,
348  long unsigned int _sizeof_Params,
349  long unsigned int _alignof_Params,
350  void *(*_assign_TT)(void *, void *),
351  void (*_ctor_T)(void *),
352  void (*_ctor_TT)(void *, void *),
353  void (*_dtor_T)(void *),
354  void (*print_T)(void *),
355  void (*print_Params)(void *),
356  void *arg,
357  void *rest
359  void *_tmp_cp0 = __builtin_alloca(_sizeof_T);
360  _adapterF_2tT__P(  // print(arg)
361    ((void (*)())print_T),
362    (_adapterF_P2tT2tT__MP( // copy construct argument
363      ((void (*)())_ctor_TT),
364      _tmp_cp0,
365      arg
366    ), _tmp_cp0)
367  );
368  _dtor_T(_tmp_cp0);  // destroy argument temporary
369  _adapterF_7tParams__P(  // print(rest)
370    ((void (*)())print_Params),
371    rest
372  );
375The @print_T@ routine is called indirectly through an adapter function with a copy constructed argument, followed by an indirect call to @print_Params@.
377A call to print
379void print(const char * x) { printf("%s", x); }
380void print(int x) { printf("%d", x);  }
382print("x = ", 123, ".\n");
384Generates the following
386void print_string(const char *x){
387  int _tmp_cp_ret0;
388  (_tmp_cp_ret0=printf("%s", x)) , _tmp_cp_ret0;
389  *(int *)&_tmp_cp_ret0; // ^?{}
391void print_int(int x){
392  int _tmp_cp_ret1;
393  (_tmp_cp_ret1=printf("%d", x)) , _tmp_cp_ret1;
394  *(int *)&_tmp_cp_ret1; // ^?{}
397struct _tuple2_ {  // _tuple2_(T0, T1)
398  void *field_0;
399  void *field_1;
401struct _conc__tuple2_0 {  // _tuple2_(int, const char *)
402  int field_0;
403  const char *field_1;
405struct _conc__tuple2_0 _tmp_cp6;  // _tuple2_(int, const char *)
406const char *_thunk0(const char **_p0, const char *_p1){
407        // const char * ?=?(const char **, const char *)
408  return *_p0=_p1;
410void _thunk1(const char **_p0){ // void ?{}(const char **)
411  *_p0; // ?{}
413void _thunk2(const char **_p0, const char *_p1){
414        // void ?{}(const char **, const char *)
415  *_p0=_p1; // ?{}
417void _thunk3(const char **_p0){ // void ^?{}(const char **)
418  *_p0; // ^?{}
420void _thunk4(struct _conc__tuple2_0 _p0){ // void print([int, const char *])
421  struct _tuple1_ { // _tuple1_(T0)
422    void *field_0;
423  };
424  struct _conc__tuple1_1 { // _tuple1_(const char *)
425    const char *field_0;
426  };
427  void _thunk5(struct _conc__tuple1_1 _pp0){ // void print([const char *])
428    print_string(_pp0.field_0);  // print(rest.0)
429  }
430  void _adapter_i_pii_(void (*_adaptee)(), void *_ret, void *_p0, void *_p1){
431    *(int *)_ret=((int (*)(int *, int))_adaptee)(_p0, *(int *)_p1);
432  }
433  void _adapter_pii_(void (*_adaptee)(), void *_p0, void *_p1){
434    ((void (*)(int *, int ))_adaptee)(_p0, *(int *)_p1);
435  }
436  void _adapter_i_(void (*_adaptee)(), void *_p0){
437    ((void (*)(int))_adaptee)(*(int *)_p0);
438  }
439  void _adapter_tuple1_5_(void (*_adaptee)(), void *_p0){
440    ((void (*)(struct _conc__tuple1_1 ))_adaptee)(*(struct _conc__tuple1_1 *)_p0);
441  }
442  print_variadic(
443    _adapter_tuple1_5,
444    _adapter_i_,
445    _adapter_pii_,
446    _adapter_i_pii_,
447    sizeof(int),
448    __alignof__(int),
449    sizeof(struct _conc__tuple1_1),
450    __alignof__(struct _conc__tuple1_1),
451    (void *(*)(void *, void *))_assign_i,     // int ?=?(int *, int)
452    (void (*)(void *))_ctor_i,                // void ?{}(int *)
453    (void (*)(void *, void *))_ctor_ii,       // void ?{}(int *, int)
454    (void (*)(void *))_dtor_ii,               // void ^?{}(int *)
455    (void (*)(void *))print_int,              // void print(int)
456    (void (*)(void *))&_thunk5,               // void print([const char *])
457    &_p0.field_0,                             // rest.0
458    &(struct _conc__tuple1_1 ){ _p0.field_1 } // [rest.1]
459  );
461struct _tuple1_ {  // _tuple1_(T0)
462  void *field_0;
464struct _conc__tuple1_6 {  // _tuple_1(const char *)
465  const char *field_0;
467const char *_temp0;
468_temp0="x = ";
469void _adapter_pstring_pstring_string(
470  void (*_adaptee)(),
471  void *_ret,
472  void *_p0,
473  void *_p1
475  *(const char **)_ret=
476    ((const char *(*)(const char **, const char *))_adaptee)(
477      _p0,
478      *(const char **)_p1
479    );
481void _adapter_pstring_string(void (*_adaptee)(), void *_p0, void *_p1){
482  ((void (*)(const char **, const char *))_adaptee)(_p0, *(const char **)_p1);
484void _adapter_string_(void (*_adaptee)(), void *_p0){
485  ((void (*)(const char *))_adaptee)(*(const char **)_p0);
487void _adapter_tuple2_0_(void (*_adaptee)(), void *_p0){
488  ((void (*)(struct _conc__tuple2_0 ))_adaptee)(*(struct _conc__tuple2_0 *)_p0);
491  _adapter_tuple2_0_,
492  _adapter_string_,
493  _adapter_pstring_string_,
494  _adapter_pstring_pstring_string_,
495  sizeof(const char *),
496  __alignof__(const char *),
497  sizeof(struct _conc__tuple2_0 ),
498  __alignof__(struct _conc__tuple2_0 ),
499  (void *(*)(void *, void *))&_thunk0, // const char * ?=?(const char **, const char *)
500  (void (*)(void *))&_thunk1,          // void ?{}(const char **)
501  (void (*)(void *, void *))&_thunk2,  // void ?{}(const char **, const char *)
502  (void (*)(void *))&_thunk3,          // void ^?{}(const char **)
503  (void (*)(void *))print_string,      // void print(const char *)
504  (void (*)(void *))&_thunk4,          // void print([int, const char *])
505  &_temp0,                             // "x = "
506  (({  // copy construct tuple argument to print
507    int *__multassign_L0 = (int *)&_tmp_cp6.field_0;
508    const char **__multassign_L1 = (const char **)&_tmp_cp6.field_1;
509    int __multassign_R0 = 123;
510    const char *__multassign_R1 = ".\n";
511    ((*__multassign_L0=__multassign_R0 /* ?{} */),
512     (*__multassign_L1=__multassign_R1 /* ?{} */));
513  }), &_tmp_cp6)                        // [123, ".\n"]
515({  // destroy argument temporary
516  int *__massassign_L0 = (int *)&_tmp_cp6.field_0;
517  const char **__massassign_L1 = (const char **)&_tmp_cp6.field_1;
518  ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
521The type @_tuple2_@ is generated to allow passing the @rest@ argument to @print_variadic@.
522Thunks 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 *])@.
523This all builds to a call to @print_variadic@, with the appropriate copy construction of the tuple argument.
Note: See TracBrowser for help on using the repository browser.