camera

Variadic templates (a proposal to C++ standard)

Родилась идея о том, как побороть давнюю проблему C++ и реализовать функции и шаблоны с переменным числом аргументов в классическом стиле C++. Отправил своё предложение в comp.lang.c++.moderated, а вот, для интересующихся, его копия.

Statement of problem

There has been a long-standing problem with variadic functions in C++. Yes, C++ has inherited variadic function syntax from C, but these just behave like in C, with no type safety, no type-based overloading, no automatic conversions, without any of the great features that C++ adds to plain C. This has resulted in variadic functions being somewhat shameful in C++, like a feature kept just for backward compatibility. On the other hand, variadic functions with type safety and overloading are really needed in many cases. There are currently different workaround approaches employed by boost and other libraries:

1. Use of compound expressions with overloaded operators instead of functions calls. That's what boost::format does with its % operator. Different flavors of this approach are:

functor[arg1][arg2][arg3]()
(functor << arg1 << arg2 << arg3)()
functor(arg1)(arg2)(arg3).call()
functor.arg(arg1).arg(arg2).arg(arg3)()
functor(placeholder, arg1, arg2, arg3)
// in the last example, "operator," (comma) is overloaded for placeholder

It's usually tedious to write such functors, and the call syntax is always different from the standard function call, and you can't use such functor where a regular function should be passed. These are ersatz, definitely.

2. Declaration of a series of overloaded functions with different numbers of arguments up to a certain maximum. This is both limited and tedious to declare (in fact, boost::mpl uses preprocessor to generate these).

For class templates, this problem exists, too. boost::mpl follows approach 2 (with preprocessor macros) to declare the typelists.

Proposed solution: syntax

First, a new kind of declaration is introduced: an “ellipsis declaration” (“edecl” for short). The syntax is:

normal-declaration ...

Like:

int x...
typename T...

The use of ellipsis declarations and of the symbols declared this way is limited to the following cases:

1. An ellipsis declaration of a value or type (class, typename) can be used as the last item of the template formal argument list in a declaration of a class or function template, or a template specialization. Like:

template<typename T...> class C { /*...*/ };
template<typename T...> void f();
template<int N...> class C { /*...*/ };

2. An ellipsis declaration of a value can be used as the last item of the function formal argument list in a declaration of a function template. Like:

template<typename T> void f(T arg...);
template<typename T> void f(T arg1, int *arg...);
template<> void f(void (*arg)()...);

In the last example, the function template itself is niladic, but it's a template nevertheless because ellipsis declarations are only allowed in function templates, not in plain functions. See below for discussion of why I think it should be so.

3. A type declared with an ellipsis declaration can be used in an ellipsis declaration of a value. Like:

template<typename T...> void f(T arg...); // see note below
template<typename T...> void f(const T &arg...);
template<typename T...> void f(void (*arg)(T...)); // anonymous edecl

Note: actually, the ellipsis in the formal arguments list in the examples above is semantically redundant, but I hope that explicitly requiring it will help to not forget that the function is variadic.

4. A type declared with an ellipsis declaration can be used as the last item of the template actual argument list in a class or function template instantiation. Like:

template<typename T...> void f(const C<int, T> &);
template<typename C, typename T...> class CL: public CL<T> { /*...*/ };

5. A type declared with an ellipsis declaration can be used in a type-expression in the last item of the template specialization argument list. Like:

template<typename T...> class C<T*> { /*...*/ };

6. A value declared with an ellipsis declaration can be used as the last item of the template actual argument list in a class or function template instatiation (so far as it can be evaluated statically, of course), or in template specialization argument list. Like:

template<int N...> class C2: public C1<N> { /*...*/ };
template<typename T, T N1, T N...> class C2: public C1<T, N> { /*...*/ };
template<typename T, T N...> class C<T*, N> { /*...*/ };

7. A value declared with an ellipsis declaration can be used as the last item of the actual argument list in a function call or object construction.
template<typename T> void f(T arg...) {
     ff(0, arg);
     C<T> v(arg);
     C<T> *p = new C<T>(arg);
};
template<int N...> void f() {
     return ff(N);
}
All other usage of ellipsis declarations and of types and values declared this way is invalid and should cause compile-time errors.

Ellipsis declarations in formal argument lists of templates and functions cannot be combined with default types or values.

Proposed solution: semantics

An ellipsis declaration of a type (typename T..., class T...) actually declares not a single type, but an ordered list of types. Likewise, an ellipsis declaration of a value declares an ordered list of values. Note that the list can have zero length.

There are certain restrictions on what can be done with these lists: ellipsis types can be passed on where a list of types is required (template instantiation or specialization); ellipsis types can be used to declare ellipsis values (in formal arguments of functions); ellipsis values can be passed on where a list of value is required (template instantiation, actual arguments of functions, template specialization).

There is only one kind of an ellipsis declaration of a type:

class T... // these are synonymous
typename T...

but there are two kinds of an ellipsis declaration of a value: using a regular type or an ellipsis-declared type. When a regular type is used, a list of values having the same type is declared. When an ellipsis-declared
type is used, a list of values having different types is declared, with each value having its type taken from the corresponding item of the type list. Note that, in both cases, complex type-expressions can be used:

template<> void f(int *N...); // takes any number of pointers to int
template<T...> void f(T *N...); // takes any number of any pointers

In the last example, the function can be instantiated not only for a signature of f(int *, int *), but also for f(int *, char *) — in the later case, the type list T would be (int, char).

Actually, when the ellipsis declaration of a value uses an ellipsis-declared type, the ellipsis itself is semantically redundant because the compiler already knows that an ellipsis-declared type can only be used in an ellipsis declaration, not in a regular declaration, but, for conformity, I think that both kinds of ellipsis declaration of values should require the ellipsis.

On the contrary, using (not declaring) an ellipsis-declared type (to pass it on in a template actual argument list) or value (to pass it on to a function) never includes an ellipsis.

A variadic template (which has an ellipsis declaration in its template formal argument list) can co-exist with a non-variadic template with the same name and scope. This should be regarded as another level of specialization: the most preferable is a specialized non-variadic declaration, then a non-specialized non-variadic declaration, then a specialized variadic declaration, and, finally, a non-specialized variadic declaration is chosen in the most generic case. Providing both a variadic and a non-variadic template with the same name in the same scope is the intended means to implement arbitrary “variadic” algorithms and data structures. Consider the following variadic max() function:
template<typename Head, typename Tail...>
Head max(Head h, Tail t...) {
     return h < t ? max(t) : h;
}
template<typename Only>
Only max(Only value) {
     return value;
}
Here, when the variadic template is instantiated, it invokes recursive instantiation of itself with less arguments, and this repeats until there is only one argument left. A call of max() with one argument invokes the instantiation of the non-variadic template because non-variadic templates are preferred to variadic ones. A compiler is expected to inline all these calls and produce an effective implementation of max() for the signature with which it's actually being invoked.

That's why ellipsis declarations can only be used in templates (see the first example in point 2 of the previous section): the value lists are never handled as any kind of dynamic runtime structures. It's just a means to provide automatic overloading of functions for any number of arguments.

Having a list of values referenced by a single name does not necessarily mean that it can be only passed to a function which has an ellipsis declaration in its formal arguments list. These calls are syntactically legal:
template<>
void printall(std::string format, double values...) {
     pow(values); // this will instantiate OK if there are exactly 2 values
     printf(format.c_str(), values); // though it's somewhat dangerous
}
Examples of use

The previous section gives an example of variadic max() implementation. Here are some others.

1. Type lists.

Type lists can be written in a simple template.
template<> struct Typelist {}; // niladic template
template<typename Head, typename Tail...>
struct Typelist {
     typedef Head head_type;
     typedef Typelist<Tail> tail_type;
};

typedef Typelist<char, short, int, long, long long> integer_types;
2. You can easily make a typelist from a function's signature:
template<typename Ret, typename T...>
struct FunctionTraits<Ret f(T...)> { // note the ellipsis -- it's an edecl
     typedef Ret ret_type;
     typedef Typelist<T> arg_types;
};

typedef FunctionTraits<strncmp>::arg_types strncmp_arg_types;
// this yields Typename<const char *, const char *, int>
3. You can easily declare a function signature matching a typelist:
template<typename Ret, typename T...>
struct MakeFunction<Ret, Typelist<T> > { // not an edecl -- no ellipsis
     typedef Ret (*function_ptr_type)(T...);
};

MakeFunction<int, strncmp_arg_types>::function_ptr_type fptr;
fptr = &strncmp; // the types perfectly match
4. A data structure holding any number of members with any types can be declared like this:
template<> struct Tuple {};
template<typename Head, typename Tail...>
struct Tuple {
     Head head;
     Tuple<Tail> tail;
     Tuple(Head h, Tail t...): head(h), tail(t) {};
};

template<typename T...>
Tuple<T> make_tuple(T values...) {
     return Tuple<T>(values);
}

Tuple<const char *, const char *, int> strncmp_args
      = make_tuple(str1, str2, len);
5. It's easy to make a deferred function call using a tuple of arguments:
template<typename Ret, typename Callable,
          typename ArgsTuple, typename Extra...>
Ret call(Callable f, ArgsTuple args_tuple, Extra extra_args...) {
     return call<Ret>(f, args_tuple.tail, args_tuple.head, extra_args);
}
template<typename Ret, typename Callable,
          typename Extra...>
Ret call(Callable f, Tuple<>, Extra extra_args...) {
     return f(extra_args);
}

int res = call<int>(strncmp, strncmp_args);
Of course, there is a lot of other amazing things that can be done with variadic templates, like partial functor binding, for example. It would be great if someone posts more examples of usefulness of variadic templates.

I'm looking forward for discussion.
Tags:
Я еще не до конца вник, но очень похожая штука была описана у Александреску.
Не, это я на Typelist так среагировал.

Расширение предлагали вот здесь.
Но у них синтаксис странненький - многоточие то слева, то справа.
О, как. Всё-таки велосипед.

Моё предложение соответствует примерно тому, что там названо basic. Только там используется префиксное многоточие там, где у меня постфиксное, и постфиксное там, где у меня никакого (у меня "распаковка" происходит автоматически, так как всё равно нет никаких других операций). Про многое из того, что там описано, я думал, но посчитал, что оно нафиг не нужно, так как реализуется через шаблонное метапрограммирование. Так-то оно, конечно, так, но там автор ещё и о производительности при компиляции подумал.