# Performing arbitrary calculations with the Concept TS

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.

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 `concept`s 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.

If you've liked this blog post, consider donating or otherwise supporting me.

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