Concept Maps using C++23 Library Tech

Abstract

C++0x Concepts had a feature Concept Maps that allowed a set of functions, types, and template definitions to be associated with a concept and the map to be specialized for types that meet the concept.

This allowed open extension of a concept.

A definition could be provided that allows an algorithm to operate in terms of the API a concept presents and the map would define how those operations are implemented for a particular type.

This is similar to how Haskell’s typeclass works.

Lost with `Concepts-Lite`

The feature was very general, and lost as part of the Concepts-Lite proposal that was eventually adopted.

This loss of a level of indirection means that the APIs for a concept must be implemented by those names for a type, even when those names are not particularly good choices in the natural domain of a type rather than in the domain as a concept.

The proliferation of transform functions for functorial map is such a problem.

It is also a problem when adapting types that are closed for extension or do not permit member functions.

Why?

Don’t know if you should
Need to know if you could first

Alternatives

Virtual Interface
Adapters
Collection of CPOs

Hard to Support

Example from C++0x Concepts

Student Record

class student record {
public:
  string id;
  string name;
  string address;
  bool   id_equal(const student record&);
  bool   name_equal(const student record&);
  bool   address_equal(const student record&);
};

Equality Comparable

concept_map EqualityComparable<student record>{
    bool operator==(const student record& a,
                    const student record& b){
        return a.id_equal(b);
}
};

Allow associated types

Very useful for pointers

concept_map BinaryFunction<int (*)(int, int), int, int>
{
    typedef int result_type;
};

Why Didn’t We Get Them?

Let’s not go there right now.

State of the Art

Rust Traits

trait PartialEq {
    fn eq(&self, rhs: &Self) -> bool;

    fn ne(&self, rhs: &Self) -> bool {
        !self.eq(rhs)
    }
}

C++ CPOs

Some Concepts and Types

namespace N::hidden {
template <typename T>
concept has_eq = requires(T const& v) {
  { eq(v, v) } -> std::same_as<bool>;
};

struct eq_fn {
  template <has_eq T>
  constexpr bool operator()(T const& x,
                            T const& y) const {
    return eq(x, y);
  }
};

template <has_eq T>
constexpr bool ne(T const& x, T const& y) {
  return not eq(x, y);
}

template <typename T>
concept has_ne = requires(T const& v) {
  { ne(v, v) } -> std::same_as<bool>;
};

struct ne_fn {
  template <has_ne T>
  constexpr bool operator()(T const& x,
                            T const& y) const {
    return ne(x, y);
  }
};
} // namespace N::hidden

See Why tag_invoke is not the solution I want by Barry Revzin https://brevzin.github.io/c++/2020/12/01/tag-invoke/

C++ partial_equality

namespace N {
inline namespace function_objects {
inline constexpr hidden::eq_fn eq{};
inline constexpr hidden::ne_fn ne{};
} // namespace function_objects

template <typename T>
concept partial_equality
  requires(std::remove_reference_t<T> const& t)
{
  eq(t, t);
  ne(t, t);
};
} // namespace N

See Why tag_invoke is not the solution I want by Barry Revzin https://brevzin.github.io/c++/2020/12/01/tag-invoke/

Requirements for Solution

Tied to the type system
Automatable
“zero” overhead
- no virtual calls
- no type erasure

What does typeclass do?

Adds a record to the function that defines the operations for the type.

Can we do that?

Type-based lookup

Templates!

Additional Requirements

Avoid ADL

Object Lookup rather than Overload Lookup

Variable templates

Variable templates have become more powerful

We can have entirely distinct specializations

A Step Towards Implementation

template <class T>
concept partial_equality = requires(
    std::remove_reference_t<T> const& t) {
  {
    partial_eq<T>.eq(t, t)
  } -> std::same_as<bool>;
  {
    partial_eq<T>.ne(t, t)
  } -> std::same_as<bool>;
};

`partial_eq<T>`

An inline variable object

template<class T>
constexpr inline auto partial_eq = hidden::partial_eq_default;

A default implementation

constexpr inline struct partial_eq_default_t {
  constexpr bool
  eq(has_eq auto const& rhs,
     has_eq auto const& lhs) const {
    return (rhs == lhs);
  }
  constexpr bool
  ne(has_eq auto const& rhs,
     has_eq auto const& lhs) const {
    return (lhs != rhs);
  }
} partial_eq_default;

New `has_eq`

template <typename T>
concept has_eq = requires(T const& v) {
  { operator==(v, v) } -> std::same_as<bool>;
};

Will do better

In a bit

Monoid

A little more than you think.

A type
With an associative binary operation
Which is closed
And has an identity element

Maybe not a lot more

Math

\(\oplus: M \times M \rightarrow M\)
\(x \oplus (y \oplus z) = (x \oplus y) \oplus z\)
\(1_M \in M\) such that \(\forall m \in M : (1_M \oplus m) = m = (m \oplus 1_M)\)

Function form

\(f : M \times M \rightarrow M\)
\(f(x, f(y, z)) = f(f(x, y), z)\)
\(1_M \in M\) such that \(\forall m \in M : f(1_M, m) = m = f(m, 1_M)\)

The similarity to left and right fold is NOT an accident

Core Functions

\(empty : m\): \(empty = concat \, []\)
\(concat : [m] \rightarrow m\): \(fold \, append \, empty\)
\(append : m \rightarrow m \rightarrow m\): \(op\)

Note that it’s self-referential

This is common

From Haskell Prelude

class Semigroup a => Monoid a where
  mempty :: a
  mempty = mconcat []

  mappend :: a -> a -> a
  mappend = (<>)

  mconcat :: [a] -> a
  mconcat = foldr mappend mempty

Minimum Set

\(empty \, | \, concat\)

In C++

template <typename T, typename M>
concept MonoidRequirements =
    requires(T i) {
      { i.identity() } -> std::same_as<M>;
    }
    ||
    requires(T i, std::ranges::empty_view<M> r1) {
      { i.concat(r1) } -> std::same_as<M>;
    };

I am ignoring all sorts of const volatile reference issues here.

Implementing the other side

The Map for a Monoid

template <class Impl>
  requires MonoidRequirements<
      Impl,
      typename Impl::value_type>
struct Monoid : protected Impl {
  auto identity(this auto&& self);

  template <typename Range>
  auto concat(this auto&& self, Range r);

  auto op(this auto&& self, auto a1, auto a2);
};

empty is a terrible name, concat only a little better. empty becomes identity

`identity`

    auto identity(this auto && self) {
        std::puts("Monoid::identity()");
        return self.concat(std::ranges::empty_view<typename Impl::value_type>{});
    }

`concat`

   template<typename Range>
   auto concat(this auto&& self, Range r) {
        std::puts("Monoid::concat()");
        return std::ranges::fold_right(r,
                    self.identity(),
                    [&](auto m1, auto m2){return self.op(m1, m2);});
    }

`op`

   auto op(this auto&& self, auto a1, auto a2) {
        std::puts("Monoid::op");
        return self.op(a1, a2);
    }

Deducing `this` and CRTP

We’ll see in a moment, but it’s because we want to constraint the required implementation.

We want to use the derived version which has all of the operations.

`Plus`

template <typename M>
class Plus {
public:
  using value_type = M;
  auto identity(this auto&& self) -> M {
    std::puts("Plus::identity()");
    return M{0};
  }

  auto op(this auto&& self, auto s1, auto s2) -> M {
    std::puts("Plus::op()");
    return s1 + s2;
  }
};

`PlusMonoidMap`

template<typename M>
struct PlusMonoidMap : public Monoid<Plus<M>> {
    using Plus<M>::identity;
    using Plus<M>::op;
};

Need to pull the operations from the Monoid instance into the Map, so we get the right ones being used by concat.

This might be simpler if we didn’t allow choice of the basis operations, but that’s also overly restrictive.

The map instances

template<class T> auto monoid_concept_map = std::false_type{};

template<>
constexpr inline auto monoid_concept_map<int> = PlusMonoidMap<int>{};

template<>
constexpr inline auto monoid_concept_map<long> = PlusMonoidMap<long>{};

template<>
constexpr inline auto monoid_concept_map<char> = PlusMonoidMap<char>{};

Can we `concat` instead?

class StringMonoid {
public:
  using value_type = std::string;

  auto op(this auto&&, auto s1, auto s2) {
    std::puts("StringMonoid::op()");
    return s1 + s2;
  }

  template <typename Range>
  auto concat(this auto&& self, Range r) {
    std::puts("StringMonoid::concat()");
    return std::ranges::fold_right(
        r, std::string{}, [&](auto m1, auto m2) {
          return self.op(m1, m2);
        });
  }
};

No, I’m not properly constraining Range here. No, I’m not actually recommending this as an implementation.

The Map and instance

struct StringMonoidMap : public Monoid<StringMonoid> {
    using StringMonoid::op;
    using StringMonoid::concat;
};

template<>
constexpr inline auto monoid_concept_map<std::string> = StringMonoidMap{};

Some simple use

Exercise the functions

template<typename P>
void testP()
{
    auto d1 = monoid_concept_map<P>;

    auto x = d1.identity();
    assert(P{} == x);

    auto sum = d1.op(x, P{1});
    assert(P{1} == sum);

    std::vector<P> v = {1,2,3,4};
    auto k = d1.concat(v);
    assert(k == 10);
}

Some simple cases

    std::cout << "\ntest int\n";
    testP<int>();

    std::cout << "\ntest long\n";
    testP<long>();

   std::cout << "\ntest char\n";
    testP<char>();

On `std::string`

This will use the StringMonoid we defined a few moments ago.

    auto d2 = monoid_concept_map<std::string>;

    std::cout << "\ntest string\n";
    auto x2 = d2.identity();
    assert(std::string{} == x2);

    auto sum2 = d2.op(x2, "1");
    assert(std::string{"1"} == sum2);

    std::vector<std::string> vs = {"1","2","3","4"};
    auto k2 = d2.concat(vs);
    assert(k2 == std::string{"1234"});

Note that the map type is mostly invisible.

Results

test int

Plus::identity()
Plus::op()
Monoid::concat()
Plus::identity()
Plus::op()
Plus::op()
Plus::op()
Plus::op()

test long

Plus::identity()
Plus::op()
Monoid::concat()
Plus::identity()
Plus::op()
Plus::op()
Plus::op()
Plus::op()

test char

Plus::identity()
Plus::op()
Monoid::concat()
Plus::identity()
Plus::op()
Plus::op()
Plus::op()
Plus::op()

test string

Monoid::identity()
StringMonoid::concat()
StringMonoid::op()
StringMonoid::concat()
StringMonoid::op()
StringMonoid::op()
StringMonoid::op()
StringMonoid::op()

Monoid in Trees

Foldable generalizes

Folding is very much tied to Range like things.

It can, and has, been generalized to things that can be traversed.

monoids are still critical for Traversables.

Summarizing Data in a tree

If the summary type is monoidal, nodes can hold summaries of all the data below them.

`fingertrees`

Much of the flexibility of fingertrees comes from the monoidal tags.

They are also fairly complicated.

Technique can be applied to other, simpler trees.

P3200 (eventually) ((C++29))

fringe-tree

Simplified tree with data at the edges

Code

Show the monoid-map branch of

steve-downey/fringetree.git

Summary for Concept Maps

Tell you what I told you

Variable templates for map lookup
Named operations on the map object
Open for extension
Concept checkable implementations
Decoupled map use and implementation

Questions?

Or comments