Learning Concepts in C++ Part 2: Sets and Numbers

last edited on 2023-09-28

link to repository https://github.com/jgsuw/math_concepts_cxx

In my previous post, I outlined my plan to learn Concepts and Constraints in C++20 by implementing mathematical abstractions using primarily constrained templates. My end goal is to implement a template library for the Special Euclidean Group in three dimensions and its Lie Algebra. To reach this destination, several heirarchical concepts need to be developed.

So where to begin? In mathematics, one may construct abstractions from many different starting places. For instance, to create the Natural numbers one might begin with the Peano axioms. However, there are many other ways to go about constructing \(\mathbb{N}\), such as using Zermelo-Frenkel set theory, lambda calculus, etc.

Taking a step back, what is the purpose of implementing a mathematical abstraction as a template? Since I am using C++, it seems reasonable that the purpose is to compile programs that use the abstractions to do computation. C++ being compiled and statically typed, any computations it performs must compile to operations on basic types like int, float, double etc.

With this in mind, I chose to begin with a concept I called PointSet, which represents a collection of elements that share the same type.

template <class S>
concept PointSet = requires(S::type& x, bool& b) {
  b = S::contains(x);
};

The code means this: a template class S fits the concept PointSet if S has an underling type and a static method contains which will return a boolean (true if \(x \in S\) and false otherwise). Here is an example of something which does not satsify the concept:

template <typename T>
class MySet {
  static inline bool contains(const T& x) {
    return x > static_cast<T>(0);
  }
};

MySet is an attempt to model the set of positive real numbers, where typename T in the template might be float or double or some other floating / fixed point number type. Unfortunately, MySet does not satsify PointSet because MySet::type is an unknown identifier (we did not include it in the definition). The fix is simple:

template <typename T>
class MySet {
  using type = T;
  static inline bool contains(const T& x) {
    return x > static_cast<T>(0);
  }
};

We can test this change with a template function:

template <PointSet S>
bool is_PointSet() { return true; }

which constraints the template parameter S to the PointSet concept. Putting this all together into a short program,

template <class S>
concept PointSet = requires(S::type& x, bool& b) {
  b = S::contains(x);
};

template <class S>
bool is_PointSet() { return PointSet<S>; }

template <typename T>
class MySet {
  using type = T;
  static inline bool contains(const T& x) {
    return x > static_cast<T>(0);
  }
};

int main(void) {
  auto result = is_PointSet<MySet>();
  if (result) {
    // success
    return 0;
  }
  // will never happen
  return -1; // program will only compile if is_PointSet<MySet>() == true
}

which happily compiles! Armed with a working constrained template, next I tried creating a few different templates for number sets. Here are simple templates for Natural numbers, Integers, Rationals, and Reals.

template <typename T>
class NaturalNumbers {
    public:
    using type = T;
    static constexpr T zero = static_cast<T>(0);
    static constexpr T one = static_cast<T>(1);
    static inline bool contains(T& x) {
        return x >= zero && x % one == zero;
    };
};

template <typename T>
class Integers {
    public:
    using type = T;
    static constexpr T zero = NaturalNumbers<T>::zero;
    static constexpr T one = NaturalNumbers<T>::one;
    static inline bool contains(T& x) {
        return x % one == zero;
    };
};

template <typename T>
class RationalNumbers {
    public:
    using type = std::pair<T,T>;
    static inline bool contains(T& x)  {
        return (Integers<T>::contains(x.first) &&
                Integers<T>::contains(x.second) &&
                x.second != Integers<T>::zero);
    }
};

template <typename T>
class RealNumbers {
    public:
    using type = T;
    static constexpr T zero = NaturalNumbers<T>::zero;
    static constexpr T one = NaturalNumbers<T>::one;
    static inline bool contains(T& x) { 
        return true;
    }
};

You may at this point noticed these templates have lots of static constexpr properties and methods are static inline. The reason for this is I view abstractions as literally static in an ontological sense. The set of Natural numbers for instance is a single static entity. On the other hand, classes in C++ very often contain mutable state which can differ amongst instances (objects) of an individual class. The static keyword ensures that the properties like one, zero, contains can be accessed without constructing an object of the class NaturalNumbers e.g. without having to declare NaturalNumbers<int> my_object();. Moreover, the constexpr and inline keywords require that the expressions must be available for evaluation at compile time. This seems appropriate, since the point of concepts is to enforce template properties also at compile time.

So we have some templates now that represent a few different number sets. Up to this point I have imposed only two requirements on a concept, which is relatively simple. Things will get more complicated as I progress to \(\text{SE}(3)\). Recalling that \(\text{SE}(3)\) builds upon concepts like groups and vectorspaces, a natural next step is to try and implement a concept Group.