Wednesday, September 28, 2011

Compile time messages in C++

At times it's desirable to give a message at compile time. Sounds cheezy, eh? Well read on and find out.

As an example of the cheezy kind, the compile-time quick sort shown here earlier contained an unnecessary run time element with a main()function, for_each() and a print template. It is possible to display all information at compile time by causing a compiler error, like this:
template <typename T>
struct print;
Use it by, for example, by referring to a member type.

Let's revisit the list and concat templates.

template <typename T, T... elems>
struct list;
template <typename ...T>
struct concat;
 
template <typename T, T... lh, T... rh, typename ...U>
struct concat<list<T, lh...>, list<T, rh...>, U...>
{
  typedef typename concat<U..., list<T, lh..., rh...> >::type type;
};
 
template <typename T, T... elems>
struct concat<list<T, elems...> >
{
  typedef list<T, elems...> type;
};

Now a simple test of how it works
typedef print<concat<list<int, 1, 2>, list<int, 3, 4> >::type>::type message; 
 The output from the compiler is:
c.cpp:72:9: error: 'type' in class 'print<list<int, 1, 2, 3, 4> >' does not name a type
Not perfect, but but it does show the resulting type list<int, 1, 2, 3, 4>.

Well, there is a caveat. The standard mandates very little indeed regarding error messages. The typical phrase used is "... a diagnostic is required". Nothing at all is said about the information in that diagnostic, and a compiler simply saying "?" can be fully standards compliant. Fortunately compiler writers likes happy users, and so usually try to help them with informative messages, so this usually works fine, just no guarantees.

Note that the technique is perfectly usable in C++ as defined by the 1998 standard. The only reason I used the C++ 2011 feature, variadic templates here, is to save space.

As shown so far, this is just silly, but this can actually come in handy. How about some unit tests for the concat template?

First a helper template:

template <typename T, typename U>
struct assert_same_type;
 
template <typename T>
struct assert_same_type<T, T>
{
  typedef T type;
};

The idea is that if the two parameter types are the same, the member type can be used in, for example a typedef, otherwise the compiler will emit an error message.

Now let's put concat through its pace:

typedef assert_same_type<concat<list<int> >::type,
                         list<int> >::type
concat_empty_list;
 
typedef assert_same_type<concat<list<int, 1, 2> >::type,
                         list<int, 1, 2> >::type
concat_one_list;
 
typedef assert_same_type<concat<list<int, 1, 2>,
                                list<int, 3, 4> >::type,
                         list<int, 1, 2, 3, 4> >::type
concat_two_lists;
 
typedef assert_same_type<concat<list<int, 1>,
                                list<int, 2>,
                                list<int, 3> >::type,
                         list<int, 1, 2, 3> >::type
concat_three_lists;
The result of compilation is:
c.cpp:79:9: error: 'type' in class 'assert_same_type<list<int, 3, 1, 2>, list<int, 1, 2, 3> >' does not name a type
Whoaa! A bug! It seems that when three elements are concatenated, the order is changed. Hmm. Ah, look at concat above. The error is rather obvious. Glad that one was caught before any library user came complaining.

Fixing the concat template to:

template <typename T, T... lh, T... rh, typename ...U>
struct concat<list<T, lh...>, list<T, rh...>, U...>
{
  typedef typename concat<list<T, lh..., rh...>, U... >::type
  type;
};

Should take  care of it. Another attempt at compiling gives silence. It works.

So, as can be seen, the technique can be rather useful. The error message given was, in this case, rather informative and quickly pointed us in the right direction to fix the bug.

What about giving library users a little help, though? concat can only be used with list type parameters. Anything else is an error. What does the compiler emit when concat is used with mismatching types? Let's put it to the test:

typedef concat<list<int>, std::vector<std::string> >::type listvec;
The error message is:
c.cpp:69:9: error: 'type' in class 'concat<list<int>, std::vector<std::basic_string<char> > >' does not name a type
Not very helpful. The user will have to look at the sources for concat to understand what it means.

If you're lucky enough to write your programs with a compiler that supports static_assert(), officially introduced in ISO C++ 2011, but supported by many compilers for some time (gcc introduced it in version 4.3 released in March 2008,) it's simple. static_assert() requires a compile-time known boolean value and a string. The string is the error message if the boolean is false.

So, with a simple helper, concat can provide a lot better information to the user.
template <typename ...Tail>
struct all_elements_are_lists
{
  static const bool value = false;
};
template <typename T, T... elems, typename ... Tail>
struct all_elements_are_lists<list<T, elems...>,
                              Tail...>
{
  static const bool value = all_elements_are_lists<Tail...>::value;
};
template <typename T, T... elems>
struct all_elements_are_lists<list<T, elems...> >
{
  static const bool value = true;
};
template <typename ...T>
struct concat
{
  static_assert(all_elements_are_lists<T...>::value,
                "All parameters to concat must be lists.");
};
Let's try the faulty concat invocation again. Now the error message is:
c.cpp: In instantiation of 'concat<list<int>, std::vector<std::basic_string<char> > >':
c.cpp:79:53:   instantiated from here
c.cpp:38:3: error: static assertion failed: "All parameters to concat must be lists."
c.cpp:79:9: error: 'type' in class 'concat<list<int>, std::vector<std::basic_string<char> > >' does not name a type
It would be a lie to say that it's perfect, but the information is a lot clearer and the user does not have to read the sources for concat, so it's an improvement.

So what to do if your compiler does not support static_assert()? All is not lost. Use the technique described in the beginning of the post to create a type, or a template, with a descriptive name that causes an error. The descriptive name will hopefully be shown in the error message. You may have to play around a bit to find a solution, but it's doable, although the message will never be as clear as with static_assert().

Compile time messages turned out to be pretty useful, I think.

Sunday, September 25, 2011

Exploring time keeping in ISO C++ 2011

A lot has been written about new features coming in the 2011 revision of ISO C++. One that has received surprisingly little attention is the <chrono> header. The types and functions therein makes it so much simpler to write time keeping software. Its neat simple interface is, however, also problematic.

Here's a small example program that shows both neatness and problems:

#include <chrono>#include <thread> // std::this_thread::sleep_until()#include <iostream>#include <ostream> 
template <typename T, long N, long D>std::ostream &operator<<(std::ostream &os,           std::chrono::duration<T, std::ratio<N, D> >&d){  os << d.count() << '*' << N << '/' << D << " seconds";  return os;} 
int main(){  const std::chrono::seconds desired_duration(1);  auto before = std::chrono::system_clock::now();  auto deadline = before + desired_duration;  std::this_thread::sleep_until(deadline);  auto after = std::chrono::system_clock::now();  auto delay = after - deadline;  std::cout << delay << std::endl;}
A sample run says:


65*1/1000000 seconds

The header <chrono> contains the templates time_point<> and duration<> in addition to a smorgasboard of clocks, all in the namespace std::chrono. In the example above, the variables before, deadline and after are all instantiations of the time_point<> template, and the variables desired_duration and delay are instantiations of the duration<> template.


You can subtract time_points to get a duration. You can add or subtract a duration and a time_point and get another time_point. You can multiply or divide durations with a scalar, and you can even divide durations and get their relative length as a scalar quotient.

One of the template parameters of time_point<> is the clock it came from, so you can't by mistake subtract two time_points from different clocks.

As shown in the example above, the durations are templatized on the type used to represent values, and a ratio describing its base in seconds. The example above shows microseconds.

There are predefined convenience duration typedefs in namescape std::chrono:  nanoseconds, microseconds, milliseconds, seconds, minutes and hours.

Every clock has a typedef period, which is the ratio of the resolution of the clock. A small example program, using the above templated operator<< for durations displays the resolution of the system clock:
int main()
{
  using namespace std::chrono;
  duration<int, system_clock::period> resolution(1);
  std::cout << resolution << '\n';
}
The output is:
1*1/1000000 seconds
This computer's system clock uses microseconds to represent time.

Herein lies one of the problems with <chrono>. The resolution of clocks must be known at compile time. This means that the makers of a standard library must strike a balance between giving the impression of a finer granularity clock than is actually available, and making the types too coarse. The computer used to run this example program has a clock with nanosecond granularity, but the library does not acknowledge its existence. I am of course free to implement my own clock type for it, and it's not much work, but it feels unnecessary.

Converting between durations with different resolutions is simple and safe. As long as the conversion can be done without losing precision, it can be done implicitly. When the conversion causes loss of precision, std::chrono::duration_cast<> is available.

The standard names three clocks. system_clock, steady_clock and high_precision_clock. The clock steady_clock, was at times during the standardization process called monotonic_clock, and a number of C++ compilers ship with libraries using that name. The steady clock is a clock that is not ever allowed to see time point adjustments, only rate adjustments. It is thus very handy for server software that does carries out jobs at certain intervals, or for profiling.

Unfortunately the standard allows the three to be typedef:ed to each other. In my library they are all typedefs for the same clock. The implication of this is that my compiler right now allows the calculation std::chrono::high_precision_clock::now() - std::chrono::system_clock::now(), since the time points returned both refer to the same type. The exact same code may not compile on another conforming compiler, if its library uses distinct types for those two clocks. I think that is unnecessary.

Yet a problem is that the clock static member function now() must be declared noexcept to be standards conforming, i.e. calling it must not cause any exception to be thrown. There is thus no possible way to check at run time if a clock is available or not. If the library supports it, it must be there and it must work. I think this is bad.

For those of you who had hoped to see a date class, to do calendar work with, sorry - it isn't there.

Friday, September 23, 2011

Compile time quick sort using C++ variadic templates

[ Edit June 4 2015: This article is very dated. Read this revisiting article for a far better solution ]

C++ is a strange language. In many ways it's a crap language, but it's a very fun crap language to use. It's also a very powerful one, especially the templates. Now that ISO C++ 2011 has brought variadic templates, it becomes easier to use and requires less typing.

I decided to explore variadic templattes, and I thought one way of exploring it was to express a compile-time quick-sort. Note that I didn't set out to explore if it can be done - that I was certain of. I set out to explore if I can do it, and I very specifically decided not to check what others had done as I had no illusions of being the first.

The first problem to solve was that of expressing a list of numbers.
template <typename T, T... elems>
struct list;
That's all that is required. The second template parameter is a list of zero or more elements of type T. That's what "..." denotes.

It's use is simple:
typedef list<int, 3, 8, 69, 2> integers;
typedef list<char, 'c', 'h', 'a', 'r', 's', '\n'> word;
That the template is only declared, not defined, is not a mistake. It's not a problem that the types are incomplete and can't be instantiated. Instantiated objects are a run time thing, and this is about compile time computation.

It is, however, a good idea to be able to show what a list of numbers looks like, so a function to print the list is handy. More handy is a mechanism to call a function for every value in the list, in order.

Specializing function templates is still a no-go, but the classic forwarding to a helper class works.

template <typename T>
struct foreach_t;
This just introduces the helper class template. All work is done in the specializations.
template <typename T, T head, T... tail>
struct foreach_t<list<T, head, tail...> >
{
  template <typename F>
  static void apply(F f)
  {
    f(head);
    foreach_t<list<T, tail...> >::apply(f);
  }
};
 
template <typename T>
struct foreach_t<list<T> >
{
  template <typename F>
  static void apply(F)
  {
  }
};
The first specialization calls the function provided in the apply member function to the first element of the list, and then recurses to do the same with the tail of the list. The second specialization ends the recursion by handling an empty list.
Ah the memories. This time of the year, in 1989, I was in university and took my first academic programming course - "Functional Programming with Standard ML." I thought I had a good idea about programming, but boy was I wrong. Who would've known that I'd find that course useful for C++ 22 years later? The programming technique is the same. The syntax is far worse in C++, though.
As a convenience, a function template is added

template <typename T, typename F>
void foreach(F f = F())
{
  foreach_t<T>::apply(f);
}
The thing with the default parameter is just so that the function can either be called with an object, or using a type that is instantiated. It's just convenient. A small test program shows why.

#include <iostream>
#include <ostream>
#include <cstdio>
 
struct print
{
  template <typename T>
  void operator()(T t)
  {
    std::cout << t << ' ';
  }
};
 
int main()
{
  typedef list<int, 3, 8, 69, 2> integers;
  typedef list<char, 'c', 'h', 'a', 'r', 's', '\n'> word;
  foreach<integers, print>();
  std::cout << '\n';
  foreach<word>(std::putchar);
}
The output when run is
3 8 69 2
chars
Not very exciting, I admit, but it shows that the list works and that traversing it works. In all test programs to follow, the print struct is presumed available.

In order to implement a quick sort on the lists, two things must be possible to do with them, partitioning and concatenating them.

First the concatenation, since it's the easier operation.
template <typename ...T>
struct concat;
As before, the generic concat template just introduces the name for the specializations.
template <typename T, T... p1, T... p2, typename ...Tail>
struct concat<list<T, p1...>, list<T, p2...>, Tail... >
{
  typedef list<T, p1..., p2...> first_two;
  typedef typename concat<first_two, Tail...>::type type;
};
 
template <typename T, T... elems>
struct concat<list<T, elems...> >
{
  typedef list<T, elems...> type;
};
Local typedef:s galore in template meta programming, otherwise the lines becomes way too long to see properly.

The recursion is the same pattern, but here it is all about creating new types.

Another simple program shows the use
int main()
{
  typedef list<int, 2, 4, 8> first;
  typedef list<int, 3, 5, 7> second;
  foreach<concat<first, second>::type, print>();
  std::cout << '\n';
}
The output is
2 4 8 3 5 7 
It seems to work. Good.

Partitioning a list is possible to do with one template, but the code becomes messy to read. This is about learning a technique, not about managing messy code, so I decided to go for filtering instead. Less efficient, but much easier to read and understand.

The filter template solution takes a predicate and a list. The predicate picks the elements to keep. Doing this first requires a simple helper, the if_else template. I was pretty certain that this one made it to the standard library, but perhaps I was wrong. At least I can't find it.
template <bool b, typename T, typename F>
struct if_else
{
  typedef T type;
};
 
template <typename T, typename F>
struct if_else<false, T, F>
{
  typedef F type;
};
It's not very complicated. The template accepts a boolean value and two types. The typedef is the first type when the boolean value is true, and the second type otherwise.

With this, the filter template is reasonably straight forward as it follows a by now familiar pattern.
template <template <typename U, U> class Pred,
          typename Data>
struct filter;
 
template <template <typename U, U> class Pred,
          typename T, T head, T... tail>
struct filter<Pred, list<T, head, tail...> >
{
  typedef list<T, tail...> tlist;
  typedef typename filter<Pred, tlist>::type ftail;
  typedef list<T, head> h;
  typedef typename if_else<Pred<T, head>::value,
                           typename concat<h, ftail>::type,
                           ftail>::type type;
};
 
template <template <typename U, U> class Pred, typename T>
struct filter<Pred, list<T> >
{
  typedef list<T> type;
};
The predicate is a template that provides a boolean value given a type and an input value. The filter template recurses over the elements of the list, and uses if_else to select either only the tail, or the selected value concatenated with the tail.

A simple program demonstrates.

template <typename T, T t>
struct is_odd
{
  static const bool value = t & T(1);
};
 
int main()
{
  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
  foreach<filter<is_odd, data>::type, print>();
  std::cout << '\n';
}

The output is
9 1 23 11 23 3 
It seems like the filtering works. 

Quick sort is now only about picking a pivot element, and filtering the elements from the list that are smaller and those that aren't into separate lists, quick sort the lists and concatenate the results.

To be generic, though, the sort order should be defined by a comparison template. A reasonable comparison template is
template <typename T, T l, T r>
struct lt
{
  static const bool value = l < r;
};
Using a selected pivot value, this comparison template must be transformed into a predicate that the filter template can use. Inspired by the std::bind functions from the standard library, here is a bind template that provides the needed transformation.
template <template <typename U, U, U> class C,
          typename T, T t>
struct bind
{
  template <typename V, V v>
  struct pred
  {
    static const bool value = C<T, v, t>::value;
  };
};
The template parameter C is the comparison template, and the member template pred is the resulting predicate.

It can be used like this
int main()
{
  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
  typedef filter<bind<lt, int, 10>::pred, data>::type lt10;
  foreach<lt10, print>();
  std::cout << '\n';
}
The output is
8 9 2 1 0 3 
Presumably it works.

Now, for the quick sort, both the set selected by the predicate, and its complement, must be available. A simple way to get the complement is to negate the predicate. Enter another helper template.

template <template <typename U, U> class Pred>
struct neg
{
  template <typename T, T v>
  struct pred
  {
    static const bool value = !Pred<T, v>::value;
  };
};
The template parameter Pred is the predicate to negate, and the member template pred, is the negated predicate to use.

A simple variation of the previous example program is
int main()
{
  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
  typedef filter<neg<bind<lt, int, 10>::pred>::pred,
                 data>::type ge10;
  foreach<ge10, print>();
  std::cout << '\n';
}
Unsurprisingly the output is
23 11 23 512 
Now, finally, all the bits and pieces are there. It's just a matter of assembling them to a quick sort template
template <template <typename T, T, T> class Comp,
          typename Data>
struct q_sort;
 
template <template <typename U, U, U> class Comp,
          typename T, T head, T... tail>
struct q_sort<Comp, list<T, head, tail...> >
{
  template <typename V, V v>
  struct pred : bind<Comp, V, v>::template pred<T, head> {};
  template <typename V, V v>
  struct npred : neg<pred>::template pred<V, v> {};
  typedef typename filter<npred, list<T, tail...> >::type fl;
  typedef typename filter< pred, list<T, tail...> >::type tl;
  typedef typename q_sort<Comp, fl>::type sfl;
  typedef typename q_sort<Comp, tl>::type stl;
  typedef list<T, head> hl;
  typedef typename concat<sfl, hl, stl>::type type;
};
 
template <template <typename U, U, U> class Pred,
          typename T>
struct q_sort<Pred, list<T> >
{
  typedef list<T> type;
};
The middle template that does all the work is a bit overwhelming, but it's not as bad as it looks.

The head element is chosen as the pivot element.

First a predicate is made out of the Comp comparison template parameter, using the bind helper template introduced earlier and the pivot element.

Next a negated predicate npred is made with the help of the neg helper template.

Using these two predicates, two new lists are made, fl for false, i.e. when the negated predicate picked the elements, and tl for true, i.e. when the predicate picked the elements.

Then the two lists are sorted recursively, by creating two new types sfl and stl (for sorted versions of fl and tl.)

The only thing that remains is to concatenate the lists and the pivot element into a resulting type.

The use is simple:
int main()
{
  typedef list<int, 8, 9, 2, 1, 0, 23, 11, 23, 3, 512 > data;
  foreach<q_sort<lt, data>::type, print>();
  std::cout << '\n';
}
The result (drumroll)
0 1 2 3 8 9 11 23 23 512 
Quick sort in compile time using C++ variadic templates. Now how useless is that?

Hope you enjoyed the show!