# Prepping Yourself to Conceptify Algorithms

Ever since I found out about concepts, I’ve been fascinated with them. The other day, I was playing
a party game, and the question the game asked some of my friends was “If CHRIS had a nightclub, what
would their secret password be?”. The first answer was ‘typename T’, and the winning answer (by
popular vote) was ‘Throw a shrimp on the barbie. Also concepts are cool’. Firstly, as an Australian,
I’m all but legally obliged to say that we don’t throw shrimp on the barbie; primarily because we
don’t have shrimp in Australia. Secondly, concepts *are* cool!

Something even more fascinating to me than concepts, however, are their application in the Palo Alto Technical Report and the Ranges TS. Now that the Concepts TS has been partially merged into the C++20 Working Paper, you’ve probably started to hear more about them. You might also have heard about the efforts to migrate the Ranges TS into the C++20 Working Paper too. If you’re not aware of what concepts are, or what the Ranges TS brings to the table, sit back: you’re in for a crash course.

## Concepts Lite

In July 2011, not long before C++11 was ratified, Bjarne Stroustrup and Andrew Sutton published a paper called Design of Concept Libraries for C++ This document outlines what it means to be a concept, and how to design one. This has served as the groundwork for subsequent designs such as the Palo Alto TR and the Ranges TS, both of which are outlined below.

A very quick summary of this document is that **constraints** are requirements imposed on *syntax*,
**axioms** are requirements imposed on *semantics*, and **concepts** are both constraints *and*
axioms together. Constraints on their own are fairly weak, but are checkable by the compiler. While
axioms are expected to hold forever, they cannot be statically checked. Concepts are essentially
predicates that, when satisfied, guarantee prescribed constraints are met, and that prescribed
axioms hold, for some generic algorithm. We’ll explore this more in the example section.

## The Palo Alto Technical Report

Shortly after the dust settled on C++11, Alex Stepanov, the original designer of the STL, asked some of the most well-known names in the C++ community to a meeting in Palo Alto: Jon Kalb, Paul McJones, Sean Parent, Dan Rose, Bjarne Stroustrup, and Andrew Sutton, to name just a few. In this week-long meeting, they studied and discussed the design behind most of the algorithms that make up the STL.

This analysis looked at how to provide concepts that can help us describe which types are suitable
for the algorithms in `<algorithm>`

. It’s a rather long report, but it informs the community about
how we can go about describing things such as `copy`

and `sort`

. Note that the numeric algorithms
are *not* covered by the Palo Alto Report, and we’ll be looking into some Palo Alto-like thinking in
Parts Two and Three of this blog.

A large portion of the Palo Alto Report is derived from Stepanov’s original working on the STL, and
from his and McJones’ book, *Elements of Programming*.

## The Concepts TS

The Concepts TS is the specification for how concepts can look in C++. A compiler can follow the technical directions of this paper, and claim that they are ISO/IEC conforming.

### Defining a concept

A concept looks like this

```
template <typename T>
concept bool Weakest = true;
template <typename T1, typename T2 = T>
concept bool has_equals = // poorly-defined concept, see below, do not use this at home!
requires(T1 const& t1, T2 const& t2) {
{t1 == t2} -> bool;
};
```

This `requires`

block, called a *requires-expression*, is a way of saying “if all the expressions
in the block are well-formed, return true; otherwise, return false”. The `{t1 == t2} -> bool`

is
essentially saying `t1 == t2`

must be well-formed *and* the expression must be implicitly
convertible to `bool`

.

### Using a concept

While we won’t be using concepts in *Part One*, we’ll be using them in *Part Two*, so it’s a good
idea to quickly cover how to use them.

```
template <typename T>
requires
has_equals<T>
bool operator!=(T const& a, T const& b) noexcept
{
bool const eq = a == b;
return !eq;
}
template <has_equals T>
bool operator!=(T const& a, T const& b) noexcept
{
bool const eq = a == b;
return !eq;
}
```

In the first one, we provide the requirements outside of the template header, and in the second one,
it replaces the `typename`

. Both are equivalent, but the second one is less-error prone, and is
preferred when possible. When a type satisfies the predicate outlined by a concept, we say that it
*models* the concept.

### C++20 concepts

There are some changes between the Concepts TS and what C++20 offers. To the best of my knowledge,
everything in this blog is compatible with C++20’s version of concepts, with the exception of
`concept bool`

, which becomes just `concept`

.

## The Ranges TS

The Ranges TS is a successful attempt at moving the Palo Alto Report from an informational document to an implementation and technical specification. It started with Eric Niebler’s range-v3, which is like the prototyping playground for the Ranges TS. If you’re not familiar with range-v3, go and watch “Ranges for the Standard Library”, which is a keynote at CppCon by Eric on how range-v3 can be applied to make cool things possible.

Like the Palo Alto Report, the Ranges TS takes just the algorithms part of range-v3, and brings them
to life in the Standard. As with the Palo Alto TR, there are some changes to the algorithms in
`<algorithm>`

, and they actually reasonably check the concepts that our beloved algorithms have been
imposing since 1994 at compile-time through standardised concepts.

The reference implementation for the Ranges TS is called cmcstl2, which can be found on Casey Carter’s GitHub.

### Efforts to merge the Ranges TS into C++20

Right now, thanks to P0896, P0898, and P1037, work is being made to move the Ranges TS into C++20, so that everyone can enjoy them, not just those with the luxury of turning on experimental features.

## An example: `EqualityComparableWith`

Let’s build the `EqualityComparableWith`

concept from the Ranges TS, from the ground up.

It doesn’t make sense for `has_equals`

, defined above, to be a concept. This is a constraint: we can
check, at compile-time, that `a == b`

is valid. It doesn’t mean anything at all, because it doesn’t
tell us what `operator==`

should be doing. What we need are a set of rules that help to define what
it means for operator== to work. Constraints don’t offer this, but *axioms* do.

So, what can axioms say, that our constraint hasn’t already? Quite a lot, actually: our `has_equals`

has zero semantics right now, so even `vector<int>{} == 0`

is valid (provided someone writes the
appropriate `operator==`

). This comparison makes no sense, so let’s give it some meaning.

For starters, `a == a`

should always be true. This means that our `has_equals`

needs to impose
reflexivity on its types, with respect to equality. Secondly, `(a == b) == (b == a)`

should hold.
This is known as commutativity; we can update `has_equals`

to constrain `b == a`

, since we don’t
presently do that:

```
template <typename T1, typename T2>
constexpr bool has_equals =
std::is_same_v<bool, decltype(std::declval<T1>() == std::declval<T2>())> &&
std::is_same_v<bool, decltype(std::declval<T2>() == std::declval<T1>())>;
```

Next, it stands to make sense that, for some `T1 c`

or `T2 c`

, if, and only if, `a == b`

and
`b == c`

, does the expression `a == c`

hold. This is known as transitivity, and with these three
axioms, we can say that `has_equals`

models the concept of
*equivalence*. Let’s update our `has_equals`

so that it reflects our axioms:

```
template <typename T1, typename T2>
concept Equivalence =
std::is_same_v<bool, decltype(std::declval<T1>() == std::declval<T2>())> &&
std::is_same_v<bool, decltype(std::declval<T2>() == std::declval<T1>())>;
// axiom: (a == a)
// axiom: ((a == b) == (b == a))
// axiom: ((a == b) && (b == c) && (a == c)) || ((a == b) && !(b == c) && !(a == c))
```

We provide our axioms as comments, because we don’t have a way of checking them (and may never have
a general way of doing so). Nevertheless, they still need to hold whenever we say that a type models
equivalence. We’re not done with our concept. Notice that we say `!(b == c)`

: this can be rewritten
as `b != c`

. Whenever there is an inverse (or some alternative) to an operation, our concept should
capture that it is possible to do that alternative too. We’ll relax the equivalence bit to start
with, and make it more complicated with a second concept (counterintuitively, this is actually for
brevity). To speed things up, I’m going to take the definition from the
Ranges TS.

```
template <typename T1, typename T2>
concept WeaklyEqualityComparable =
requires(T1 const& a, T2 const& b) {
{a == b} -> Boolean&&;
{b == a} -> Boolean&&;
{a != b} -> Boolean&&;
{b != a} -> Boolean&&;
// Boolean is a concept that lets us generalise `bool`.
// tl;dr is that if it walks like a `bool`, and quacks like a `bool`,
// then it models the Boolean concept.
};
// axiom: bool(a == b) == bool(b == a);
// axiom: bool(a != b) == bool(!(a == b));
template <typename T1>
concept EqualityComparable = WeaklyEqualityComparable<T1, T1>;
// requires(T1 a, T1 b, T1 c) {
// axiom: bool(a == a);
// axiom: (bool(a == b) && bool(b == c) && bool(a == c)) || (bool(a == b) && bool(b != c) && bool(a != c));
// }
```

Note that non-equality is *irreflexive*: `a != a`

is nonsensical. We *still* aren’t done! Nowhere,
in any of the above, do we explain what it means for `vector<int>{} == 0`

to make sense. We were
just laying the groundwork for that discussion.

When `T1`

and `T2`

are different, we first need to make sure that they are comparable to themselves:
`EqualityComparable<T1> && EqualityComparable<T2> && WeaklyEqualityComparable<T1, T2>`

. After all,
if your type can’t provide a basis for equivalence against *itself*, then how can you provide a
basis for equivalence against anything else?

```
template <typename T1, typename T2>
concept EqualityComparableWith =
EqualityComparable<T1> &&
EqualityComparable<T2> &&
WeaklyEqualityComparable<T1, T2>;
```

Now we have a way to check `vector<int>{} == 0`

, but we still haven’t provided any meaning to
what the expression might mean. That’s because the expression doesn’t make sense at any level.
Comparing a container to a non-container is like comparing an apple to a truck designed to carry
apples: there’s nothing remotely similar about them, so we shouldn’t be allowed to do so. What
we need to do is refine our concept to prevent us from comparing unrelated types to one another.

The Ranges TS offers a concept called `CommonReference`

, which checks that we can boil `T1`

and `T2`

down to the same reference type. If such a type exists, then that type should *also* be
`EqualityComparable`

. Here’s the Ranges TS definition of `EqualityComparableWith`

:

```
template <class T, class U>
concept bool EqualityComparableWith =
EqualityComparable<T> &&
EqualityComparable<U> &&
CommonReference<
const remove_reference_t<T>&,
const remove_reference_t<U>&> &&
EqualityComparable<
common_reference_t<
const remove_reference_t<T>&,
const remove_reference_t<U>&>> &&
WeaklyEqualityComparableWith<T, U>;
// using C = common_reference_t<const remove_reference_t<T>&,
// const remove_reference_t<U>&>;
// requires(T t, U u) {
// axiom: bool(t == u) == bool(C(t) == C(u))
// }
```

This is the C++ description of our English reasoning for the *whole* section.

### What, you’re not going to define `CommonReference`

too?

Nope! As much as I love `CommonReference`

, defining it isn’t part of our conversation. All we need
to understand is that there’s a type called `common_reference_t<T1, T2>`

, which works out what the
‘gcd’ for `T1`

and `T2`

is, and that `CommonReference`

checks that `common_reference_t<T1, T2>`

exists.

### Why did you suddenly start casting to `bool`

everywhere in your axioms?

According to Casey Carter, because we don’t check that `decltype(a == b)`

and `decltype(b == a)`

are
the same type, we can’t reliably check that `(a == b) == (b == a)`

. The only way to keep the code
sensible is to convert both operands to `bool`

and ensure that axiom holds.

## Conclusion

What you should take away from *Part One* is that concepts aren’t meant to only check syntax: that’s
just the tip of the iceberg. In addition to constraint checking (which can be employed by
type-traits), your concepts should also provide axiomatic rules that define what it means for a type
to model your concept.

We’ll take a look at how to conceptify one of the C++ standard algorithms in *Part Two*, and in
*Part Three*, we’ll be jumping into adding concepts to numeric algorithms, which are still under
active research. Between this blog post and *Part Three*, Simon Brand will be blogging about a case
study that he’s done on some numeric algorithms,
and why they are the way they are when you move to the parallelism sphere.

Till then!

## Thanks

This blog wouldn’t have been possible without the combined input from Arien Judge, Callum Howard, Casey Carter, Gordon Brown, Matt Egan, Morris Hafner, and Simon Brand. Thank you!

## This website is a work-in-progress

I haven’t yet added a comments section, but I am tracking this as a GitHub issue, where comments can be made.

If you’d like to get in touch, please drop me a line at cjdb.ns@gmail.com.