Title: Variadic and Variable Templates

Author: Martin Moene

Date: 03 April 2015 20:08:15 +01:00 or Fri, 03 April 2015 20:08:15 +01:00

Summary: C++11 and 14 offer new features for Variadic and Variable templates. Peter Sommerlad showcases the compile-time possibilities they offer.

Body: 

C++11 introduced Variadic Templates and constexpr that ease and allow type-safe computations at compile time. In combination with the C++14 mechanism of Variable Templates, which actually define constants, there are unprecedented possibilities for compile-time computations.

This article not only shows the mechanisms available but also demonstrates a non-trivial example, how they can be used to compute interesting data at compile time to be put into ROM on an embedded device, for example.

Introduction

C++ templates have allowed compile-time meta-programming for some time now. However, with C++03 many interesting applications require herculean efforts to achieve results using class-template specializations and function template overloads with variable number of template arguments. Getting such code using variable number of template arguments right is very tedious in the C++03 landscape and even a tiny mistake can produce horrific compiler error messages which are hard to trace back to the origin of the error. Any user of some of the Boost libraries that make heavy use of template meta-programming, such as boost::spirit or boost::mpl can sing that song. [Boost]

However, the variadic templates introduced with C++11 make things much more comfortable at the language level. <type_traits> for meta programming were even further improved in C++14. In addition to many more traits, C++14 introduced template aliases for each trait with a suffix _t that allow us to rid the template code of many uses of the typename keyword when working with traits. Also new with C++14 come variadic lambdas, that allow us to use auto as the type for a lambda’s parameters, so that their type can be deduced from the calling context of the lambda. Another recent change are the relaxed rules for type deduction, so that lambdas and auto return type functions can be specified without a trailing return type, even in the case of multiple return statements. It is only when multiple returned expressions differ in their type that one needs to specify a return type explicitly.

In addition to increased possibilities with lambdas and return type deduction, many of the limitations on C++11 constexpr functions have also been relaxed. In the future, you might see many uses of ‘constexpr auto’ functions that do interesting compile-time computations. Some are shown later.

Finally, variable templates, which are actually parameterized compile-time constants, make the concept of templates more symmetric across the language.

As a library component, std::tuple extends the idea of std::pair to arbitrary collection of values of arbitrary types and std::integer_sequence eases the writing of code employing such lists of values.

With so much stuff, you might ask, how does that help a ‘normal’ programmer and how should I employ these. The rest of this article will show you some applications that are useful in day-to-day work or for embedded code employing modern compilers.

Variadic templates with typename parameters (C++11)

Whoever has been bitten by the lack of type-safety of printf() might employ a variadic template solution to create a type-safe println function. Recursion is the key to defining successful variadic template functions and makes using classical ... varargs parameters in C++ mostly obsolete. (See Listing 1.)

#ifndef PRINTLN_H_
#define PRINTLN_H_
#include <ostream>
// base case overload
void println(std::ostream &out){
  out <<'\n';
}
// variadic template
template <typename HEAD, typename ... T>
void println(std::ostream & out,HEAD const &h, T const & ... tail){
  out << h; // cut off head
  if (sizeof...(tail)){
    out <<", ";
  }
  println(out,tail...); // recurse on tail...
}

#endif /* PRINTLN_H_ */
			

A variadic template introduces a so-called ‘template parameter pack’ by placing three dots (ellipsis) after the typename parameter introduction. Using the template parameter pack’s name (T) to define a function parameter creates a parameter pack (tail). The name of the parameter pack (tail) can later be used within the template to denote a so-called pack-expansion, where the three dots are placed after an expression using the parameter pack name. The corresponding expression is then repeated for each concrete argument. In our println example, even while the base case is not really called, an empty tail (sizeof...(tail)==0) would not call println(), it is necessary to make the code compile. As you might have guessed the sizeof... operator gives the number of elements in a parameter pack. It is also applicable on a template parameter pack name.

Variable templates basics (C++14)

In C++, it has always been possible to define constants that were dependent on template arguments using static data members of a class template. To make the language with respect to templates more symmetric and for constants depending on template arguments, C++14 introduced variable templates, which can even be variadic, by the way.

The canonical example from the C++ standard [ISO/IEC] is the definition of pi for any kind of numerical type that looks like the following:

  template<typename T> constexpr T pi 
    = T(3.1415926535897932384626433L);

This allows pi<float> or pi<double> to be computed at compile time and used as such without casting the value. Note that the number of digits given as a long double value are sufficient up to the precision long double allows on today’s platforms. You can even write pi<complex<double>> to obtain the complex constant with pi as the real part.

If you ever need to calculate with a full circle two_pi might also be defined accordingly:

  template<typename T> constexpr T two_pi
    =pi<T>+pi<T>;

While the example of Pi might not be very impressive, take a look at the examples given later, where whole table computations are hidden behind the initialization of a template variable.

As a more interesting helper, we implement the conversion of degrees to radian values at compile time, using our pi<T> constant. Because degrees, minutes and seconds can be given as integral values, we can implement that using a variable template as well:

  template <short degrees, short minutes=0,
    short seconds=0>
  constexpr long double
  rad{(degrees+minutes/60.0L+seconds/3600.0L)
    *pi<long double>/180.0L};

  static_assert(pi<long double>/2 == rad<90>,
    "90 degrees are pi half"); // test it

Variadic templates with non-type parameters and std::integer_sequence (C++11/14)

In addition to typename parameter packs, C++11 and later also allow parameter packs of non-type template parameters. The usual restrictions on non-type template parameters apply and all arguments of a non-type template parameter pack have to have the same type.

C++14 introduced std::integer_sequence<typename T,T ... elts> to represent such sequences of integers or indices with std::index_sequence<size_t ...> as different types at compile time. A companion factory function make_index_sequence<size_t n>() creates an index_sequence with the numbers up to n.

The following example shows how such an index_sequence can be used to create a std::array with n elements of type size_t is initialized-potentially at compile time-with multiples of parameter row (1 to n times):

  template <size_t...I>
  constexpr auto
  make_compile_time_sequence(size_t const row,
     std::index_sequence<I...>){
    return std::array<size_t,sizeof...(I)>{
      {row*(1+I)...}};
  }
  constexpr auto
     array_1_20=make_compile_time_sequence(1,
     std::make_index_sequence<20>{});

Please excuse the complication of the additional parameter row, but you will see later that we will use that to construct different rows of a multiplication table. For example, make_compile_time_sequence10,std::make_index_sequence<10>{}) will create an array with the values 10, 20, 30,... 100. That will be the last row in a multiplication table from 1 times 1 up to 10 times 10.

While it is quite easy to convert the parameter pack to values, using pack-expansion, it is impossible to use a function parameter as a template argument within a constexpr function. This hurdle makes some applications a bit of a burden. However, as the rules for constexpr functions are also relaxed, there is less need for such variadic template machinery to ensure compile-time computation of tables.

As a-slightly unnecessary-complicated example the following code shows how to compute a multiplication table at compile time.

  template <size_t...I>
  constexpr
  auto make_compile_time_square
    (std::index_sequence<I...> ){
      return std::array<std::array<size_t,
        sizeof...(I)>,sizeof...(I)>
             {{make_compile_time_sequence(1+I,
               std::make_index_sequence
               <sizeof...(I)>{})...}};
  }

The pack expansion actually will generate a row in the table for each value the parameter pack I takes. With that, we can create a complete multiplication table from 1*1 to 20*20 with just a single declaration in the 2-dimensional array constant multab_20 at compile time:

  constexpr auto multab_20 =
     make_compile_time_square(
     std::make_index_sequence<20>{});

The corresponding test code will output the multiplication table from the constant multab_20 (see Listing 2). I even implemented a version that uses std::integer_sequence<char,char ...> to create the multiplication table as a string constant at compile time. But the code is not as nice as I would like it to be. There is work on the way to ease compile-time string processing in a similar way and a means (already implemented by g++ and clang) to create a char_sequence<char ...> from a regular string literal using a user-defined literal template operator that might be standardized for C++17.

void testCompileTimeArray(std::ostream &out){
  using namespace std;
  for_each(begin(multab_20),end(multab_20),
           [&out](auto row){
    out << '\n';
    for_each(begin(row),end(row),[&out](auto elt){
      out << setw(4) << elt;
    });
  });
  out << '\n';
}
			

More ‘ROMable’ data

Let us conclude with an example of a compile-time computed table of sine values to enable a quick lookup-and-interpolation-based implementation of a sine function for an embedded system.

To build such a table, we first need a compile-time constexpr version of std::sin(double). This can be implemented using a Tailor-series that converges quickly [Wikipedia]. It can be used independently from the table to create individual sine values at compile time. A run-time use is not recommended, because it will definitely be inferior to std::sin(x).

The code starts first with some scaffolding to implement the tailor series development of the sine value of x. (See Listing 3.)

// sin(x) = sum (-1)^n*(x^(2*n+1))/(2n+1)!
namespace tailor {
template<typename T>
constexpr T pi = T(3.1415926535897932384626433L);
namespace detail{
constexpr long double fak(size_t n) {
  long double res = 1;
  for (size_t i = 2; i <= n; ++i) {
    res *= i;
  }
  return res;
}

constexpr long double sin_denominator
   (long double x, size_t n) {
  long double res{ x }; // 1 + 2n
  for (size_t i = 0; i < n + n; ++i) { 
    // naive, could be log(n), but n<20
    res *= x;
  }
  return res;
}

template<typename T>
constexpr T two_pi =2.0l*pi<T>;

constexpr
long double adjust_to_two_pi(long double x) {
  while (x > two_pi<long double> ) {
    x -= two_pi<long double>;
  } // very naive... not for run-time use
  while (x < -two_pi<long double> ) {
    x += two_pi<long double>;
  }
  return x;
}
} // detail
constexpr long double sin(long double x) {
  long double res = 0;
  x = detail::adjust_to_two_pi(x); // ensures
                                   // convergence
  for (size_t n = 0; n <= 16; ++n) {
    long double const summand
    {detail::sin_denominator(x, n) 
     / detail::fak(2 * n + 1)};
    res += n % 2 ? -summand : summand;
  }
  return res;
}
}
			

With that quite slow sin() function in place we can start implementing more. Using the tricks we learned from our multiplication table we can now implement a compile-time lookup table for the sine values for each degree from 0..360 as in Listing 4.

namespace tables {
template <typename T, size_t ...indices>
constexpr auto
make_sine_table_impl
  (std::index_sequence<indices...>){
  static_assert(sizeof...(indices)>1,
      "must have 2 values to interpolate");
  return std::array<T,sizeof...(indices)>{{
    sin(indices*two_pi<T>
    /(sizeof...(indices)-1))...
  }};
}
template <size_t n, typename T=long double>
constexpr auto make_sine_table=
    make_sine_table_impl<T>
    (std::make_index_sequence<n>{});
			

Listing 5 contains some compile-time tests of our sine table to show that the table is really ROMable using only 5 values.

constexpr auto testsinetab=tables::make_sine_table<5,long double>;
static_assert(testsinetab[0]==0.0, "sine 0 is 0");
static_assert(abs(testsinetab[2])<1e-10, "sine pi is 0");
static_assert(abs(testsinetab.back()) <1e-10, "sine two pi is 0");
static_assert(abs(testsinetab[1]-1.0)<1e-10, "sine pi/2 is 1");
static_assert(abs(testsinetab[3]+1.0)<1e-10, "sine pi+pi/2 is -1");
			

And Listing 6 is our compile-time table from 0 to 360 degrees of a circle.

constexpr auto largesinetab
  =tables::make_sine_table<360+1,double>;
// limited to 1 entry per degree,
// if not giving compiler argument:
//   -fconstexpr-steps=larger

// check it:
static_assert(largesinetab.front()==0,
  "sine 0 is 0");
static_assert(abs(largesinetab.back())
  <1e-12,"sine 2 pi is 0");
			

What is still missing from the standard

As of C++14 many standard library functions and some types are not yet as compile-time usage friendly. For example, std::array is a literal type, but it can not be incrementally constructed in a constexpr function. A replacement for the time being is cloning std::array and adding constexpr to all member functions. The keyword constexpr was only added to the const-member functions, because these were the only useful positions with C++11’s restrictions and nobody recognized the usefulness for C++14 of also having the non-const member functions declared as constexpr.

Also, the standard library’s non-modifying algorithms and may be even some of the modifying algorithms could be used in more elaborate constexpr functions, if they would be declared as constexpr. However, there is some tension, since some algorithms might be more efficiently implemented as run-time versions where the limitations of constexpr don’t apply.

A final missing piece are string literals and compile time computation of string values. Work has started on these things and you should expect corresponding compiler and library support for the next standard C++17 making compile time computation still more powerful, allowing even more ROMable data being computed in C++ at compile time.

However, interpreting C++ at compile time is slowing your compiles, and current compilers (clang, g++) will give a strict limit to the number of computations allowed, so to be able to detect endless recursion or endless loops. These limits usually allow for a compile time of single file to be within a minute or a couple of minutes and it can be easily reached. For example, I can create my sine table for 360 degrees, but not per minute or a quarter of a degree, because of the default compiler limits, and even then the compile time is clearly recognizable. You don’t want to include such a header in more than one compilation unit, otherwise we get compile times in days rather than minutes.

So compile-time constexpr computation is a powerful tool in modern C++ to create ROMable data and relieve small processors from the burden of some computation at run time. But it is also a potentially expensive thing that might slow your development, if you try too complicated things at compile time giving people again a reason to complain how slow C++ compiles. But as of today, that won’t be only the fault of the compiler, but of the developer pushing it to its limits. So use this powerful feature wisely.

Nevertheless, learn how to use variadic templates, since these are reasonable and can simplify template code significantly, especially in a cases where you’d like to use template template parameters, but that might be a story for a future article.

References

[Boost] Boost Libraries, http://www.boost.org;

• Boost Spirit, http://www.boost.org/doc/libs/1_57_0/libs/spirit/doc/html/index.html;
• Boost MPL, http://www.boost.org/doc/libs/1_57_0/libs/mpl/doc/index.html;

both accessed April 5th 2015

[ISO/IEC] ISO/IEC International Standard 14882, Fourth edition 2014-12-15, Information technology – Programming languages – C++

[Wikipedia] Sine Tailor Series definition; Wikipedia, http://en.wikipedia.org/wiki/Sine#Series_definition, accessed December 1st 2014

Example source code

The example source code is available on Github: https://github.com/PeterSommerlad/Publications/tree/master/ACCU/variadic_variable_templates

Notes: 

More fields may be available via dynamicdata ..