Performing arbitrary calculations with the Concept TS

10 Mar 2016 by Jonathan

Last Tuesday I took a closer look at the Concept TS. This followed a discussion about the power and usefulness of concepts regarding a replacement for TMP (shout-out to @irrequietus and @Manu343726). So after compiling the GCC trunk that has concept support, I’ve specifically looked in a way to use concepts alone for doing arbitrary calculations.

Attention: This is completely pointless. You’ve been warned.

For that, I tried to implement a Prime_number concept that checks whether a given number is a prime number. It should use only concepts and require to do the calculation.

And well, I’ve succeeded… somewhat.

It doesn’t compile with concepts - only with the equivalent constexpr functions. I’m not a language lawyer, but I think it should compile. Most likely, GCC doesn’t like it because I’m completely misusing abusing the feature. And there is also a more complicated version that works, so you can definitely do it with concepts.

@CoderCasey has pointed out that there is a special rule preventing such code. More on that below.

Before I show the concept version, let me take you on a little journey backwards through time. At each point we’ll take a look at the ways to do compile-time programming to implement the prime number check.

C++14 constexpr solution

C++14 provides a very powerful constexpr, so it is basically the trivial CS 101 solution, just with constexpr at the front:

constexpr bool is_prime_number(int i)
{
    if (i == 1)
        return false;
    else if (i == 2)
        return true;
    else if (i % 2 == 0)
        return false;
    for (auto div = 3; div * div <= i; div += 2)
        if (i % div == 0)
            return false;
    return true;
}

Yes, I’m using the div * div check as opposed to going to the square root of i. Yes, this can overflow. No, I don’t care.

But it is too simple. Everybody can write code like this.

So let’s go back to C++11.

C++11 constexpr

C++11’s constexpr doesn’t allow loops so we need to do it via recursion. For that, I’ve extracted the search for a divisor into a different function:

constexpr bool is_prime_number_helper(int i, int div)
{
    return div * div <= i ? (i % div == 0 ? false : is_prime_number_helper(i, div + 2)) : true;
}

constexpr bool is_prime_number(int i)
{
    return i == 2 ? true : (i == 1 || i % 2 == 0 ? false : is_prime_number_helper(i, 3));
}

I like this implementation. It’s elegant and compact.

And as bonus: Completely unreadable.

Note how the two conditionals in is_prime_number_helper() correspond to the inner loop conditional and the outer loop termination. Also note how I’ve re-ordered the conditionals in is_prime_number() to group the two trivial false cases.

But let’s go even further back in time.

C++98 metaprogramming

Remember the time before constexpr? Where you had to do compile-time calculations via template specializations?

I don’t.

Well, here we are now:

template <int I, int Div, int Rest>
struct is_prime_number_helper // I % Div != 0
{
    enum {value = is_prime_number_helper<I, Div + 2, I % (Div + 2)>::value};
};

template <int I, int Div>
struct is_prime_number_helper<I, Div, 0> // I % Div == 0
{
    enum {value = false};
};

template <int I>
struct is_prime_number_helper<I, I, 0> // I == Div
{
    enum {value = true};
};

template <int I, bool Even>
struct is_prime_number_nontrivial;

template <int I>
struct is_prime_number_nontrivial<I, true> // I even
{
    enum {value = false};
};

template <int I>
struct is_prime_number_nontrivial<I, false> // I not even
{
    enum {value = is_prime_number_helper<I, 3, I % 3>::value};
};

template <int I>
struct is_prime_number // general case
{
    enum {value = is_prime_number_nontrivial<I, I % 2 == 0>::value};
};

template <>
struct is_prime_number<1> // special case 1
{
    enum {value = false};
};

template <>
struct is_prime_number<2> // special case 2
{
    enum {value = true};
};

Yes, I got nostalgic wanted to give the impression I’ve been using C++ for ages and used the anonymous enum technique to create static constants.

I have carefully created many template specializations to let the compiler stop instantiation as early as possible. Note that the divisor check runs until Div == I, there is no easy way to specialize for Div * Div > I.

And now we jump 18 years forward and write the same code but with concepts instead of class templates.

I’ve told you it’s pointless.

Concepts

I’m going to assume you have already heard of concepts.

Otherwise you wouldn’t probably read this. I mean: we’re implementing compile-time prime number checks in an overly complicated way!

A concept can take any constexpr value, so writing the Prime_integer concept is very straightforward:

template <int I>
concept bool Prime_number = is_prime_number(I);

And that’s how you use concepts for arbitrary computation. Thank’s for reading.

…

Yeah, but that’s cheating.

Also it is boring.

I’ve explicitly stated that I only wanted to use concepts for the calculation.

Again: that is completely pointless. I just want to prove a point.

The overall strategy is very similar to the C++98 solution. Branches are implemented through requires, not template specialization, and the syntax is different, but the technique is basically the same.

As before, first of all the Prime_number_helper that does the divisor check:

// Div * Div > I
template <int I, int Div> requires Div * Div > I
concept bool Prime_number_helper()
{
    return true;
}

// I % Div == 0
template <int I, int Div> requires Div * Div <= I && I % Div == 0
concept bool Prime_number_helper()
{
    return false;
}

// I % Div != 0
template <int I, int Div> requires Div * Div <= I && I % Div != 0
concept bool Prime_number_helper()
{
    return Prime_number_helper<I, Div + 2>();   
}

I’ve used function concepts because GCC seems to like them a little bit more than variable concepts regarding their requires statement.

Note that it is needed to split this part up into the three conditions. Putting it all into one and using the ?: operator would leed to infinite recursion when the compiler tries to calculate.

Infinite recursion at compile-time leads to very long compilation times.

And then the Prime_number concept is very easy:

template <int I> requires I <= 1
concept bool Prime_number()
{
    return false;
}

template <int I> requires I == 2
concept bool Prime_number()
{
    return true;
}

template <int I> requires I > 2 && I % 2 == 0
concept bool Prime_number()
{
    return false;
}

template <int I> requires I > 2 && I % 2 == 1
concept bool Prime_number()
{
    return Prime_number_helper<I, 3>();
}

You only need to watch out that the all overloads have disjunct conditions. Otherwise you get an ambigous call to overloaded function error.

Update:

This code is actually ill-formed due to a special rule that prevents requires with concepts for exactly that reason. But you can still write them as “normal” constexpr functions, i.e. write constexpr instead of concept and it works. So actually you can do arbitrary compile-time calculations with requires, not with concept. But still: pointless but cool.

So this is useful for what?

It isn’t useful.

It is completely pointless.

We’ve used bleeding edge technology to create something in the same way we could in 1998.

And it doesn’t even compile! (Only if I replace some all concept with constexpr.)

But this was a fun afternoon for me.

Apart from the hours spend compiling GCC trunk, made worse by a little issue with tmpfs.

And it yet again proves that C++ features can do much more than probably intended. Concepts are obviously limited in that they can only give true/false answers but they alone allow powerful computations.

Also you have another fun C++ story you can share at parties.

A more complicated beautiful and actually working - until GCC fixes it - version is here.

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.