source: doc/theses/rob_schluntz_MMath/variadic.tex @ 37e9c1d

Last change on this file since 37e9c1d was 67982887, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

specialize thesis directory-names

  • Property mode set to 100644
File size: 23.7 KB
2\chapter{Variadic Functions}
5\section{Design Criteria} % TODO: better section name???
6C provides variadic functions through the manipulation of @va_list@ objects.
7In C, a 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} or \emph{sentinel value} 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 explicitly specify information that the compiler already knows \footnote{While format specifiers can convey some information the compiler does not know, such as whether to print a number in decimal or hexadecimal, the number of arguments is wholly redundant.}.
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 to sum $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 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 candidate, 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.
155Going one last step, it is possible to achieve full generality in \CFA, allowing the summation of arbitrary lists of summable types.
157trait summable(otype T1, otype T2, otype R) {
158  R ?+?(T1, T2);
160forall(otype T1, otype T2, otype R | summable(T1, T2, R))
161R sum(T1 x, T2 y) {
162  return x+y;
164forall(otype T1, otype T2, otype T3, otype R, ttype Params
165  | summable(T1, T2, T3)
166  | { R sum(T3, Params); })
167R sum(T1 x, T2 y, Params rest ) {
168  return sum(x+y, rest);
170sum(3, 10.5, 20, 30.3);
172The \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.
175A notable limitation of this approach is that it heavily relies on recursive assertions.
176The \CFA translator imposes a limitation on the depth of the recursion for assertion satisfaction.
177Currently, the limit is set to 4, which means that the first version of the @sum@ function is limited to at most 5 arguments, while the second version can support up to 6 arguments.
178The limit is set low due to inefficiencies in the current implementation of the \CFA expression resolver.
179There 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.
181C 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.
182Furthermore, it might be desirable to disallow polymorphic functions to use C variadic syntax to encourage a \CFA style.
183Aside 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.
185Variadic templates in \CC require an ellipsis token to express that a parameter is a parameter pack and to expand a parameter pack.
186\CFA does not need an ellipsis in either case, since the type class @ttype@ is only used for variadics.
187An alternative design is to use an ellipsis combined with an existing type class.
188This 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, \eg, in fold expressions, which requires compile-time knowledge of the structure of the parameter pack, which is not available in \CFA.
190template<typename... Args>
191void f(Args &... args) {
192  g(&args...);  // expand to addresses of pack elements
195As such, the addition of an ellipsis token would be purely an aesthetic change in \CFA today.
197It is possible to write a type-safe variadic print routine, which can replace @printf@
199struct S { int x, y; };
200forall(otype T, ttype Params |
201  { void print(T); void print(Params); })
202void print(T arg, Params rest) {
203  print(arg);
204  print(rest);
206void print(char * x) { printf("%s", x); }
207void print(int x) { printf("%d", x);  }
208void print(S s) { print("{ ", s.x, ",", s.y, " }"); }
209print("s = ", (S){ 1, 2 }, "\n");
211This example routine showcases a variadic-template-like decomposition of the provided argument list.
212The individual @print@ routines allow printing a single element of a type.
213The polymorphic @print@ allows printing any list of types, as long as each individual type has a @print@ function.
214The 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.
216It is also possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions.
217For example, it is possible to write @new@ as a library function.
219struct Array;
220void ?{}(Array *, int, int, int);
222forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
223T * new(Params p) {
224  return malloc(){ p }; // construct result of malloc
226Array * x = new(1, 2, 3);
228In 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.
230The @new@ function provides the combination of polymorphic @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically-allocated objects.
231This approach provides the type-safety of @new@ in \CC, without the need to specify the allocated type, thanks to return-type inference.
235The definition of @new@
237forall(dtype T | sized(T)) T * malloc();
239forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
240T * new(Params p) {
241  return malloc(){ p }; // construct result of malloc
244generates the following
246void *malloc(long unsigned int _sizeof_T, long unsigned int _alignof_T);
248void *new(
249  void (*_adapter_)(void (*)(), void *, void *),
250  long unsigned int _sizeof_T,
251  long unsigned int _alignof_T,
252  long unsigned int _sizeof_Params,
253  long unsigned int _alignof_Params,
254  void (* _ctor_T)(void *, void *),
255  void *p
257  void *_retval_new;
258  void *_tmp_cp_ret0;
259  void *_tmp_ctor_expr0;
260  _retval_new=
261    (_adapter_(_ctor_T,
262      (_tmp_ctor_expr0=(_tmp_cp_ret0=malloc(_sizeof_2tT, _alignof_2tT),
263        _tmp_cp_ret0)),
264      p),
265    _tmp_ctor_expr0); // ?{}
266  *(void **)&_tmp_cp_ret0; // ^?{}
267  return _retval_new;
270The constructor for @T@ is called indirectly through the adapter function on the result of @malloc@ and the parameter pack.
271The variable that is allocated and constructed is then returned from @new@.
273A call to @new@
275struct S { int x, y; };
276void ?{}(S *, int, int);
278S * s = new(3, 4);
280Generates the following
282struct _tuple2_ {  // _tuple2_(T0, T1)
283  void *field_0;
284  void *field_1;
286struct _conc__tuple2_0 {  // _tuple2_(int, int)
287  int field_0;
288  int field_1;
290struct _conc__tuple2_0 _tmp_cp1;  // tuple argument to new
291struct S *_tmp_cp_ret1;           // return value from new
292void _thunk0(  // ?{}(S *, [int, int])
293  struct S *_p0,
294  struct _conc__tuple2_0 _p1
296  _ctor_S(_p0, _p1.field_0, _p1.field_1);  // restructure tuple parameter
298void _adapter(void (*_adaptee)(), void *_p0, void *_p1){
299  // apply adaptee to arguments after casting to actual types
300  ((void (*)(struct S *, struct _conc__tuple2_0))_adaptee)(
301    _p0,
302    *(struct _conc__tuple2_0 *)_p1
303  );
305struct S *s = (struct S *)(_tmp_cp_ret1=
306  new(
307    _adapter,
308    sizeof(struct S),
309    __alignof__(struct S),
310    sizeof(struct _conc__tuple2_0),
311    __alignof__(struct _conc__tuple2_0),
312    (void (*)(void *, void *))&_thunk0,
313    (({ // copy construct tuple argument to new
314      int *__multassign_L0 = (int *)&_tmp_cp1.field_0;
315      int *__multassign_L1 = (int *)&_tmp_cp1.field_1;
316      int __multassign_R0 = 3;
317      int __multassign_R1 = 4;
318      ((*__multassign_L0=__multassign_R0 /* ?{} */) ,
319       (*__multassign_L1=__multassign_R1 /* ?{} */));
320    }), &_tmp_cp1)
321  ), _tmp_cp_ret1);
322*(struct S **)&_tmp_cp_ret1; // ^?{}  // destroy return value from new
323({  // destroy argument temporary
324  int *__massassign_L0 = (int *)&_tmp_cp1.field_0;
325  int *__massassign_L1 = (int *)&_tmp_cp1.field_1;
326  ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
329Of note, @_thunk0@ is generated to translate calls to @?{}(S *, [int, int])@ into calls to @?{}(S *, int, int)@.
330The call to @new@ constructs a tuple argument using the supplied arguments.
332The @print@ function
334forall(otype T, ttype Params |
335  { void print(T); void print(Params); })
336void print(T arg, Params rest) {
337  print(arg);
338  print(rest);
341generates the following
343void print_variadic(
344  void (*_adapterF_7tParams__P)(void (*)(), void *),
345  void (*_adapterF_2tT__P)(void (*)(), void *),
346  void (*_adapterF_P2tT2tT__MP)(void (*)(), void *, void *),
347  void (*_adapterF2tT_P2tT2tT_P_MP)(void (*)(), void *, void *, void *),
348  long unsigned int _sizeof_T,
349  long unsigned int _alignof_T,
350  long unsigned int _sizeof_Params,
351  long unsigned int _alignof_Params,
352  void *(*_assign_TT)(void *, void *),
353  void (*_ctor_T)(void *),
354  void (*_ctor_TT)(void *, void *),
355  void (*_dtor_T)(void *),
356  void (*print_T)(void *),
357  void (*print_Params)(void *),
358  void *arg,
359  void *rest
361  void *_tmp_cp0 = __builtin_alloca(_sizeof_T);
362  _adapterF_2tT__P(  // print(arg)
363    ((void (*)())print_T),
364    (_adapterF_P2tT2tT__MP( // copy construct argument
365      ((void (*)())_ctor_TT),
366      _tmp_cp0,
367      arg
368    ), _tmp_cp0)
369  );
370  _dtor_T(_tmp_cp0);  // destroy argument temporary
371  _adapterF_7tParams__P(  // print(rest)
372    ((void (*)())print_Params),
373    rest
374  );
377The @print_T@ routine is called indirectly through an adapter function with a copy constructed argument, followed by an indirect call to @print_Params@.
379A call to print
381void print(const char * x) { printf("%s", x); }
382void print(int x) { printf("%d", x);  }
384print("x = ", 123, ".\n");
386generates the following
388void print_string(const char *x){
389  int _tmp_cp_ret0;
390  (_tmp_cp_ret0=printf("%s", x)) , _tmp_cp_ret0;
391  *(int *)&_tmp_cp_ret0; // ^?{}
393void print_int(int x){
394  int _tmp_cp_ret1;
395  (_tmp_cp_ret1=printf("%d", x)) , _tmp_cp_ret1;
396  *(int *)&_tmp_cp_ret1; // ^?{}
399struct _tuple2_ {  // _tuple2_(T0, T1)
400  void *field_0;
401  void *field_1;
403struct _conc__tuple2_0 {  // _tuple2_(int, const char *)
404  int field_0;
405  const char *field_1;
407struct _conc__tuple2_0 _tmp_cp6;  // _tuple2_(int, const char *)
408const char *_thunk0(const char **_p0, const char *_p1){
409        // const char * ?=?(const char **, const char *)
410  return *_p0=_p1;
412void _thunk1(const char **_p0){ // void ?{}(const char **)
413  *_p0; // ?{}
415void _thunk2(const char **_p0, const char *_p1){
416        // void ?{}(const char **, const char *)
417  *_p0=_p1; // ?{}
419void _thunk3(const char **_p0){ // void ^?{}(const char **)
420  *_p0; // ^?{}
422void _thunk4(struct _conc__tuple2_0 _p0){
423        // void print([int, const char *])
424  struct _tuple1_ { // _tuple1_(T0)
425    void *field_0;
426  };
427  struct _conc__tuple1_1 { // _tuple1_(const char *)
428    const char *field_0;
429  };
430  void _thunk5(struct _conc__tuple1_1 _pp0){ // void print([const char *])
431    print_string(_pp0.field_0);  // print(rest.0)
432  }
433  void _adapter_i_pii_(
434    void (*_adaptee)(),
435    void *_ret,
436    void *_p0,
437    void *_p1
438  ){
439    *(int *)_ret=((int (*)(int *, int))_adaptee)(_p0, *(int *)_p1);
440  }
441  void _adapter_pii_(void (*_adaptee)(), void *_p0, void *_p1){
442    ((void (*)(int *, int ))_adaptee)(_p0, *(int *)_p1);
443  }
444  void _adapter_i_(void (*_adaptee)(), void *_p0){
445    ((void (*)(int))_adaptee)(*(int *)_p0);
446  }
447  void _adapter_tuple1_5_(void (*_adaptee)(), void *_p0){
448    ((void (*)(struct _conc__tuple1_1 ))_adaptee)(
449      *(struct _conc__tuple1_1 *)_p0
450    );
451  }
452  print_variadic(
453    _adapter_tuple1_5,
454    _adapter_i_,
455    _adapter_pii_,
456    _adapter_i_pii_,
457    sizeof(int),
458    __alignof__(int),
459    sizeof(struct _conc__tuple1_1),
460    __alignof__(struct _conc__tuple1_1),
461    (void *(*)(void *, void *))_assign_i,    // int ?=?(int *, int)
462    (void (*)(void *))_ctor_i,               // void ?{}(int *)
463    (void (*)(void *, void *))_ctor_ii,      // void ?{}(int *, int)
464    (void (*)(void *))_dtor_ii,              // void ^?{}(int *)
465    (void (*)(void *))print_int,             // void print(int)
466    (void (*)(void *))&_thunk5,              // void print([const char *])
467    &_p0.field_0,                            // rest.0
468    &(struct _conc__tuple1_1 ){ _p0.field_1 }// [rest.1]
469  );
471struct _tuple1_ {  // _tuple1_(T0)
472  void *field_0;
474struct _conc__tuple1_6 {  // _tuple_1(const char *)
475  const char *field_0;
477const char *_temp0;
478_temp0="x = ";
479void _adapter_pstring_pstring_string(
480  void (*_adaptee)(),
481  void *_ret,
482  void *_p0,
483  void *_p1
485  *(const char **)_ret=
486    ((const char *(*)(const char **, const char *))_adaptee)(
487      _p0,
488      *(const char **)_p1
489    );
491void _adapter_pstring_string(void (*_adaptee)(), void *_p0, void *_p1){
492  ((void (*)(const char **, const char *))_adaptee)(
493    _p0,
494    *(const char **)_p1
495  );
497void _adapter_string_(void (*_adaptee)(), void *_p0){
498  ((void (*)(const char *))_adaptee)(*(const char **)_p0);
500void _adapter_tuple2_0_(void (*_adaptee)(), void *_p0){
501  ((void (*)(struct _conc__tuple2_0 ))_adaptee)(
502    *(struct _conc__tuple2_0 *)_p0
503  );
506  _adapter_tuple2_0_,
507  _adapter_string_,
508  _adapter_pstring_string_,
509  _adapter_pstring_pstring_string_,
510  sizeof(const char *),
511  __alignof__(const char *),
512  sizeof(struct _conc__tuple2_0 ),
513  __alignof__(struct _conc__tuple2_0 ),
514  &_thunk0,     // const char * ?=?(const char **, const char *)
515  &_thunk1,     // void ?{}(const char **)
516  &_thunk2,     // void ?{}(const char **, const char *)
517  &_thunk3,     // void ^?{}(const char **)
518  print_string, // void print(const char *)
519  &_thunk4,     // void print([int, const char *])
520  &_temp0,                             // "x = "
521  (({  // copy construct tuple argument to print
522    int *__multassign_L0 = (int *)&_tmp_cp6.field_0;
523    const char **__multassign_L1 = (const char **)&_tmp_cp6.field_1;
524    int __multassign_R0 = 123;
525    const char *__multassign_R1 = ".\n";
526    ((*__multassign_L0=__multassign_R0 /* ?{} */),
527     (*__multassign_L1=__multassign_R1 /* ?{} */));
528  }), &_tmp_cp6)                        // [123, ".\n"]
530({  // destroy argument temporary
531  int *__massassign_L0 = (int *)&_tmp_cp6.field_0;
532  const char **__massassign_L1 = (const char **)&_tmp_cp6.field_1;
533  ((*__massassign_L0 /* ^?{} */) , (*__massassign_L1 /* ^?{} */));
536The type @_tuple2_@ is generated to allow passing the @rest@ argument to @print_variadic@.
537Thunks 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 *])@.
538This 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.