(This post is superceded by the next one. Drafts on drafts on drafts).

The previous post described the several ways we have today of writing customizable interfaces: polymorphism with `virtual`

functions, class template specialization, CRTP, and “well-known” member or non-member functions. They each have their advantages and disadvantages. And really, sometimes simple polymorphism is very much the best solution. But there’s a hole in our design space that suggests that we need something more.

A lack of associated types leads to a proliferation of type traits. Consider a concept like `Invocable<F, Args...>`

. All it tells us is whether or not `f(args...)`

is valid - it doesn’t tell us what type that expression has. While sometimes we don’t care (`std::for_each()`

doesn’t), most of the time we do - and to find that answer out we need to use `invoke_result_t<F, Args...>`

. Likewise, `Range<R>`

. What is the underlying iterator for the range? `iterator_t<R>`

. Underlying value type? `value_type_t<iterator_t<R>>`

. And so forth.

A lack of core customization mechanism leads to the “Two Step”:

```
r.begin(); // wrong
begin(r); // wrong
std::begin(r); // wrong
using std::begin;
begin(r); // correct
```

This problem was the motiviation for what I called the CS1 direction of UFCS (having `f(x, y)`

find `x.f(y)`

). It’s also a motivation for Matt Calabrese’s P1292. Ranges’ solution to this problem was to introduce *customization point objects*:

```
std::ranges::begin(r); // correct
using namespace std::ranges;
begin(r); // also correct
auto f = std::ranges::begin;
f(r); // also correct
```

CPOs are, in my opinion, quite the library engineering feat. They’re an impressive solution to this problem today - but they’re quite subtly difficult to implement and require a lot of work.

A lack of associated functions leads to the proposed CS2 direction of UFCS (having `x.f(y)`

find `f(x, y)`

) and similar proposals in that space for extension functions. Ranges solved this in library with the pipeable adapters: `x | f(y)`

is fairly close visually to `x.f(y)`

, and the pipeable adapters are substantially easier to write than CPOs (although still some boilerplate).

It’s these lacks that I think can and should be addressed with better `concept`

s. Concepts Lite was the proposal that eventually became C++20 concepts. It was, by design, a lighter weight version of “C++0x Concepts”. I think we can incrementally plug them in to get a more complete generic concept mechanism in C++. Here’s a sketch of what I’m thinking.

`Invocable`

Let’s start with `Invocable`

, which in C++20 is specified as:

```
template<class F, class... Args>
concept Invocable = requires(F&& f, Args&&... args) {
invoke(std::forward<F>(f), std::forward<Args>(args)...);
};
```

As mentioned earlier, this tells me *if* I can invoke something but not what I get out of it. As a result, any closely-related `concept`

s have to just know about its related type traits (effectively, instead of directly associated types we have well-known associated type traits?). For instance, a `Predicate`

is an `Invocable`

that returns `bool`

:

```
template<class F, class... Args>
concept Predicate = RegularInvocable<F, Args...> &&
Boolean<invoke_result_t<F, Args...>>;
```

It would be nice if these types were more closely associated. Let’s start with a new way of declaring concepts that look more like `struct`

s:

```
template <typename F, typename... Args>
concept struct Invocable2 {
typename result_type;
virtual result_type operator()(F&&, Args&&...);
};
```

This new kind of `concept`

is based on “pseudo-signatures” rather than expressions, and the significance of this will become more apparent later. But for now, this concept is satisfied if each `virtual`

function declaration here is satisfied… in this case meaning that `declval<F&&>()(declval<Args&&>()...)`

is well-formed. The result of that expression is stored in the type alias `result_type`

. As presented above, `Invocable2`

is an incomplete solution to `Invocable`

- it is not currently satisfied by pointers to members (not for my lack of trying). I’ll get into how to fix that later.

The advantage to this declaration, so far, is that we can write:

```
template<class F, class... Args>
concept Predicate2 = RegularInvocable<F, Args...> &&
Boolean<Invocable2<F, Args...>::result_type>;
```

This isn’t *shorter* than the initial version - but it reduces the surface area of things you have to know in order to be able to write and use concepts. And that’s a win. But don’t worry, I’ll get to shorter as well. We also don’t need `typename`

here - it’s deliberately not `typename Invocable2<F, Args...>::type`

. This is because `concept`

s cannot be specialized, so we know that `::result_type`

will always exist and be a type.

`swap(a, b)`

The next, more complicated example, is really the motivating example for the need for the “Two-Step” and the motivating example in P1292: `swap`

. How do we allow for customizing swap while still making it easy to check and use? In this sketch:

```
template <typename value T>
concept struct Swap {
virtual void swap(T& a, T& b) noexcept(/* ... */)
{
T tmp(std::move(a));
a = std::move(b);
b = std::move(tmp);
}
};
```

A few new things here. `typename value T`

is just sugar to indicate that this type’s value category is unimportant. Effectively this is doing `remove_reference_t<T>`

implicitly everywhere for convenience. That is, `Swap<int&>`

means the same thing as `Swap<int>`

.

Here also we have a `virtual`

function body in addition to just the declaration. `Swap<T>`

is implicitly satisfied as a concept if I can, for each `virtual`

function `F`

:

- find a preexisting match for
`F`

for the given type, or - if
`F`

has a body, instantiate the body

The “preexisting match” algorithm is similar to what the CPOs do today. In this case, we would look for:

- A member function. If
`declval<T&>().swap(declval<T&>())`

is valid, then we’re satisfied. - A non-member function. If argument-dependent lookup (only) can find a
`swap(declval<T&>(), declval<T&>())`

that would be selected in the presence of a poisoned`swap(U&, U&)`

overload, then we’re satisfied.

Some examples to help explain how this works:

```
// valid because we don't have any more specific matches, so we
// instantiate the body and that's valid for T=int
static_assert(Swap<int>);
// invalid because we don't have any more specific matches, and
// instantiating the body fails because std::mutex isn't movable
static_assert(!Swap<std::mutex>);
namespace N {
template <typename U> void swap(U&, U&);
struct X {
X(X&&) = delete;
};
struct Y {
Y(Y&&) = delete;
void swap(Y&);
};
struct Z {
Z(Z&&) = delete;
friend void swap(Z&, Z&);
};
}
// invalid because N::swap doesn't count for meeting the
// non-member requirements, and instantiating the body of
// Swap::swap fails because X isn't movable
static_assert(!Swap<X>);
// valid, because we find Y::swap. Doesn't matter that Y isn't
// movable
static_assert(Swap<Y>);
// valid, because we find the non-member swap(Z&, Z&), which
// satisfies the requirements. Doesn't matter that Z isn't movable
static_assert(Swap<Z>);
```

Of course, simplifying knowing *if* a type is swappable isn’t interesting at all. We need to also be able to actually swap it. And this is where the fact that we use “pseudo-signatures” comes in handy. They’re not actually pseudo - they’re full signatures. We can invoke them - and the invocation goes through the same lookup process described above:

```
// Swap<int> is satisfied by the default implementation, so this
// goes through that
int i1, i2;
Swap<int>::swap(i1, i2);
// Swap<Y> is satisfied by the member function Y::swap, so this
// is the same as y1.swap(y2)
N::Y y1, y2;
Swap<Y>::swap(y1, y2);
// Likewise this is swap(z1, z2)
N::Z z1, z2;
Swap<Z>::swap(z1, z2);
```

Of course, explicitly specifying the template arguments is so passé. We have CTAD, and the same deduction rules should be able to be applied here:

```
Swap::swap(i1, i2); // Swap<int>
Swap::swap(y1, y2); // Swap<Y>
```

And, moreover, we don’t want these to be actual functions. There are numerous benefits to these being objects - so these should behave as objects as well - in a way that follows from use:

```
// this is an object with an operator()(int&, int&)
auto swap_i = Swap<int>::swap;
swap_i(i1, i2); // ok
swap_i(y1, y2); // error
// this is an object with effectively
// template <Swap T>
// operator()(T&, T&)
auto f = Swap::swap;
f(i1, i2); // ok
f(y1, y2); // ok
```

One such benefit from allowing these to behave like objects? We can provide an easy alias:

```
// Here's my concept
template <typename value T>
concept struct Swap {
virtual void swap(T& a, T& b) noexcept(/* ... */)
{
T tmp(std::move(a));
a = std::move(b);
b = std::move(tmp);
}
};
// ... and here's my CPO
inline constexpr auto swap = Swap::swap;
```

### Opting into `Swap`

Let’s say I have some simplified version of `std::unique_ptr`

```
template <typename T>
class my_unique_ptr {
T* ptr = nullptr;;
public:
my_unique_ptr();
explicit my_unique_ptr(T*);
my_unique_ptr(my_unique_ptr&&) noexcept;
my_unique_ptr& operator=(my_unique_ptr&&) noexcept;
~my_unique_ptr();
};
```

It’s already the case that `Swap<my_unique_ptr<T>>`

for all `T`

, since this type is move-constructible and move-assignable. But we can swap more efficiently than that. So how do we provide a more efficient opt-in? We have several options.

The familiar mechanism relies upon the implicit lookup rules described above. We can either add a member function or a non-member function that is more specific than a catch-all template:

```
template <typename T>
class my_unique_ptr {
public:
// member version
void swap(my_unique_ptr& rhs) {
Swap::swap(ptr, rhs.ptr);
}
// non-member version
friend void swap(my_unique_ptr& lhs, my_unique_ptr& rhs) {
Swap::swap(lhs.ptr, rhs.ptr);
}
}
```

But I’d like to be able to be more explicit than that. N1758 talks about the difference between *named conformance* and *structural conformance*. The above approach relies on structural conformance - we match the structure, therefore we match. This effectively leads to a land-grab of names.

Instead, we could opt-in through named conformance - that is, our opt-in explicitly names the concept `Swap`

. This has some advantages. The whole point of writing a `swap`

function is so that `Swap::swap`

(or, in Ranges, `std::ranges::swap`

) can use it - so the added explicitness doesn’t hurt. We no longer have to rely on ADL, and we no longer have to worry about having larger overload sets than necessary. These opt-ins are *only* found when invoking a concept’s functions.

```
template <typename T>
class my_unique_ptr {
friend concept Swap;
// ..
};
template <typename T>
concept Swap<my_unique_ptr<T>> {
void swap(my_unique_ptr<T>& lhs,
my_unique_ptr<T>& rhs)
{
Swap::swap(lhs.ptr, rhs.ptr);
}
};
```

Within explicit models, you must provide an implementation of every `virtual`

function in a concept, and each such implementation will be checked to ensure that it matches the base signature. Had we written `swap`

to take 3 arguments or 1, that’s an error at point of definition.

We can also do this kind of explicit modelling internal to the type:

```
template <typename T>
class my_unique_ptr {
concept Swap {
void swap(my_unique_ptr& lhs, my_unique_ptr& rhs) {
Swap::swap(lhs.ptr, rhs.ptr);
}
};
};
```

or by explicitly annotating functions as being `override`

s:

```
template <typename T>
class my_unique_ptr {
public:
void my_swap(my_unique_ptr& rhs) override(Swap::swap) {
Swap::swap(ptr, rhs.ptr);
}
};
```

The `override`

keyword will enforce, at point of definition, that this signature matches.

### A terser syntax

Let’s go back to one of my favorite examples: `fmap()`

. With this new kind of concept that allows for associated types, we could write the following declaration and implementation:

```
template <typename T, Invocable<T> F,
typename U = Invocable<F, T>::result_type>
vector<U> fmap(F f, vector<T> ts)
{
vector<U> us;
us.reserve(ts.size());
for (auto&& t : ts) {
us.push_back(f(t));
}
return us;
}
```

So far, we’re only a little bit better than C++20 in that we can use `Invocable<F, T>::result_type`

instead of `invoke_result_t<F, T>`

. But this implementation is actually wrong for a few reasons:

`Invocable<F, T>`

does not mean that I can write`f(t)`

, it means I can write`invoke(f, t)`

- And even that is wrong, because it actually means we can write
`invoke(move(f), move(t))`

- … And there’s really no guarantee that
`t`

is actually a`T`

anyway (thanks,`vector<bool>`

). If it’s not, we could be doing something outside of our constraint that may or may not work.

Taking a step back, one of the examples that appeared in multiple concepts papers in the 2000s was the following:

```
// equivalent using C++20 syntax
template <typename T>
concept LessThanComparable = requires(T const a, T const b) {
{ a < b } -> bool;
};
template <LessThanComparable T>
bool foo(T x, T y) {
return x < y && random() % 3;
}
```

Now consider a type like:

```
struct Evil {
explicit operator bool() const;
void operator&&(int);
Evil operator<(Evil) const;
};
```

It’s bullshit like this that led to the incredible complexity of the `Boolean`

concept. But rather than rely on every library author to get this right, maybe we can lean on the language to help you out. C++0x concepts did this implicitly, but maybe it’s enough to do so explicitly with the help of a new access operator which I will spell `..`

:

```
template <typename F, typename... Args>
concept LvalueInvocable : Invocable<F&, Args...>
{ };
template <typename T, LvalueInvocable<T const&> F,
typename U = F..result_type> // (*)
vector<U> fmap(F f, vector<T> ts)
{
vector<U> us;
us.reserve(ts.size());
for (auto&& t : ts) {
us.push_back(f..(t)); // (*)
}
return us;
}
```

The main change here is on the two marked lines. What `..`

means will actually differ between dependent and non-dependent contexts. Within a dependent context, we will look for the name on the right-hand-side only inside of those concepts that the left-hand side is constrained on. Outside of dependent contexts, we will look in any concept that we can find that matches. So in here, `F`

is constrained on `LvalueInvocable<T>`

, which has a `result_type`

typename and a function named `operator()`

.

Both of those accesses are syntax sugar for the full rewrites using the concept name. `F..result_type`

becomes `LvalueInvocable<F, T>::result_type`

and `f..(t)`

becomes `LvalueInvocable<F, T>::operator()(f, t)`

- the latter of which is a specific signature that takes an `F&&`

and a `T&&`

and, by construction, definitely returns a `U`

. This rewrite is pretty significant for generic code - it ensures that we are definitely doing the thing that we think we’re doing!

Even nicer, is we could condense the declaration somewhat:

```
template <typename T, typename U,
LvalueInvocable<T const&, ..result_type=U> F>
vector<U> fmap(F, vector<T>);
```

Which doesn’t seem like it matters to much until we try to implement monadic bind:

```
template <typename T, typename U,
LvalueInvocable<T const&, ..result_type=vector<U>> F>
vector<U> bind(F, vector<T>);
```

Or the final boss of that blog post - implementing `sequence()`

over a `Range`

of `expected<T, E>`

:

```
template <typename T, typename E,
Range<..value_type = expected<T, E>> R>
expected<vector<T>, E> sequence(R&&);
```

Cool.

### Ranges and things

Ranges is the one significant library that uses C++20 concepts, so far. And it’s a great model of whether a new concepts design could be better for library authors and library users. There’s a few things that Ranges does that, at least to me, seem like workarounds for concepts limitations. One such limitation is that concepts are always implicit. But take something like `View`

- that’s a purely semantic distinction from `Range`

and thus makes sense (at least to me) to be an `explicit`

opt-in:

```
template <typename value R>
concept struct Range {
typename Iterator iterator;
typename Sentinel<Iterator> sentinel;
typename value_type = iterator..value_type;
// ... other useful aliases ...
iterator begin(R&);
sentinel end(R&);
};
inline constexpr auto begin = Range::begin;
inline constexpr auto end = Range::end;
template <typename value V>
explicit concept struct View : Range<V> { };
```

In this definition, `vector<int>`

implicitly models `Range`

by the rules I’ve laid out above, but it doesn’t model `View`

because it doesn’t explicitly do so. The above doesn’t quite perfectly fit into C++20 Ranges because there’s a special case of what it means to call `begin`

on an rvalue, but this is still in early exploration stages. The added associated types here mean that I can write something like:

```
template <std::ranges::Range R>
void foo(R&& rng) {
R..iterator it = rng..begin();
}
```

instead of:

```
template <std::ranges::Range R>
void foo(R&& rng) {
std::ranges::iterator_t<R> = std::ranges::begin(rng);
}
```

Realistically, most people would use `auto`

there anyway but it’s nice to know that there’s a nice way to name types if we want to name them.

The more interesting usage here for me is to talk about the adapters. The adapters in Ranges are driven in large part off of the concept `ViewableRange`

:

```
template<class T>
concept ViewableRange =
Range<T> && (forwarding-range<T> || View<decay_t<T>>);
```

which in this design would look more like:

```
// A ViewableRange is something that can be converted to a View
// safely. Note that a ViewableRange isn't necessarily a Range
// in this design. It's anything that can give you a view.
template <typename T>
explicit concept ViewableRange
{
typename View view_type;
virtual view_type view(T&&);
};
// ... which is what all_view does:
inline constexpr auto all = ViewableRange::view;
// lvalue ranges can be safely converted to a View
template <Range R>
concept ViewableRange<R&> {
auto view(R& range) {
return ref_view{range};
}
};
// Views can, obviously, be safely converted to a View
template <View V>
concept ViewableRange<V&> {
auto view(V v) { return v; }
};
template <typename V>
requires View<remove_const_t<V>>
concept ViewableRange<V&&> {
auto view(V v) { return v; }
};
```

This design completely restructures how we approach writing range adapters. In C++20, adapters like `filter`

and `transform`

require a `ViewableRange`

and then implement the appropriate machinery to get that to work, along with separate appropriate machinery to get `|`

to work. The design is that `rng | view::filter(f)`

means the same thing as `view::filter(rng, f)`

which means the same thing as `filter_view{rng, f}`

. We can actually just stick all of that into the `ViewableRange`

concept:

```
template <typename T>
explicit concept ViewableRange
{
typename View view_type;
typename value_type = view_type..value_type;
typename reference = view_type..reference;
// ... some other aliases
// the one function that needs to be implemented to satisfy
// this concept.
virtual view_type view(T&&);
// these are NOT virtual - they are associated functions and
// are always available
View auto filter(T&& rng, Predicate<reference> auto&& pred) {
// explicitly satisfy View here
struct filter_view : View
{
// ...
};
return filter_view{FWD(rng)..view(), FWD(pred)};
}
View auto transform(T&& rng,
LvalueInvocable<reference> auto&& f)
{
// note that I can use f..result_type here
struct transform_view : View
{
// ...
}
return transform_view{FWD(rng)..view(), FWD(f)};
}
// lots more adapters here...
};
```

All these adapters don’t *have* to live inside of `ViewableRange`

. Users can extend this to write their own:

```
template <typename VR>
concept struct Accumulate : ViewableRange<VR>
{
template <typename U,
LvalueInvocable<U&&, VR..reference> F = std::plus>
requires ConvertibleTo<F..result_type, U>
U accumulate(VR&& rng, U init, F op = {})
{
for (auto&& elem : FWD(rng)..all()) {
init = op..(std::move(init), elem);
}
return init;
}
};
```

The culmination of all of this effort is that we can write:

```
bool is_even(int i) { return i % 2 == 0; }
std::vector<int> ints = {1, 2, 3, 4, 5, 6};
auto sum = ints..filter(is_even)
..transform([](int x){ return x * x; })
..accumulate(0);
assert(sum == 56);
```

This works because `ints`

is an lvalue of type `vector<int>`

, which implicitly models `Range`

by having member `begin()`

and `end()`

which satisfy the other requirements as well (all of which are checked of course). Lvalues which satisfy `Range`

explicitly model `ViewableRange`

. So `ints`

can find the associated function `filter`

through that concept. Whatever the result of `ints..filter(is_even)`

is models `View`

, and all `View`

s are `ViewableRange`

s so again `transform`

is an associated function of that. And lastly we find `accumulate`

by way of the implicitly satisfied concept `Accumulate`

.

I, for one, think this is a pretty cool place to end up.

### Tuple-like and Variant-like

One of the places where we don’t have concepts today that would be interesting to try to apply them would be the tuple-like concept (used by structured bindings) and the variant-like concept (eventually used by pattern matching). These are actually difficult to describe, but a rough sketch might be as follows.

```
template <typename value T>
explicit concept TupleLike {
virtual constexpr size_t size;
template <size_t I> requires (I < size)
virtual typename element_type;
template <size_t I> requires (I < size)
virtual element_type<I>& get(T&);
template <size_t I> requires (I < size)
virtual element_type<I>&& get(T&& t) {
if constexpr (is_lvalue_reference_v<element_type<I>>) {
return get(t);
} else {
return std::move(get(t));
}
}
};
```

How does `static_assert(TupleLike<X>)`

check that `get`

and `element_type`

work for all the right `I`

s? Not sure.

`std::tuple`

would opt into via:

```
template <typename... Ts>
concept TupleLike<std::tuple<Ts...>> {
constexpr size_t size = sizeof...(Ts);
template <size_t I>
using element_type = std::tuple_element_t<
I, std::tuple<Ts...>>;
template <size_t I>
decltype(auto) get(std::tuple<Ts...>& t) {
return std::get<I>(t);
}
// don't need to provide the rvalue reference overload
// the default does the right thing for us
};
// similar for std::tuple<Ts...> const
```

### Summary

In short, this design gives us a full customization system, with named conformance instead of structural conformance. It allows us to directly and easily opt-in to interfaces implicitly or explicitly, and use first class syntax in generic algorithms regardless of how the user chooses to opt-in (the “CS1” part of UFCS).

It gives us a new access syntax (`..`

) that both provides syntax sugar to ensure that generic algorithms are using the constraints they say they want so that they’re doing what they think they’re doing, and gives us nice syntax for extension methods (the “CS2” part of UFCS).

It also gives us CPOs for free and obviates the need for arbitrary type traits.