Learning Concepts in C++ Via Mathematical Abstractions Part 1

From June through September I had the pleasure of interning at Amazon on the Vulcan Stow project, which involved a lot of robot control and perception work in C++. Prior to the internship it had been about a decade since I had used C++, so I decided to explore some of the recent language features. What caught my eye was Constraints and Concepts features of the template system.

A friend once summarized templates to me as “code that writes code”. Following this analogy, Concepts are like “code that constrains code that writes code”. More concretely, Concepts in C++ are a way to constrain templates so that instantiations of templates must satisfy a group of requirements at compile time. If the requirements (constraints) of a concept are violated, then the program is malformed and the compiler provides a diagnostic indicating which concept was violated and the template that violated it.

Initially I was unsure how this feature might be useful to me. As someone who learns best by building things, and someone who loves math, I looked for a thing that I could build which was deeply mathematical. In C++, a concept is ultimately a logical predicate \(P(x)\) where \(x\) is the template, and the program compiles if and only if \(P(x)\) is true wherever a template is constrained by the concept \(P\).

Similarly, many mathematical abstractions are constructed from axioms which can be expressed as predicates. For instance, a Ring is a set \(X\) equipped with algebraic operations \((+,\cdot)\) which must satisfy the 8 Ring Axioms that constrain the behavior of the operations on \(X\). If \(X\) is not a set, or \((+,\cdot)\) violate any of the axioms, then \((X,+,\cdot)\) is not a Ring. So my though was this: could I use concepts to constrain math templates to obey axioms?

To answer this question, I set out to write a template library for the Special Euclidean Group \(\text{SE}(3)\) and its Lie Algebra \(\text{se}(3)\). \(\text{SE}(3)\) represents three dimensional transformations of space that preserve the dot product of vectors. That is, elements of \(\text{SE}(3)\) transform points in space in a way that preserves the distance between points (represented as a triple of real numbers), and the angle betwen the differences of points (represented as 3D vectors). On the other hand, \(\text{se}(3)\) can be though of as the space of instantaneous motions of rigid bodies (collections of points) in space.

Most often \(\text{SE}(3)\) is implemented as homogenous \(4 \times 4\) matrices and \(\text{se}(3)\) is implemented as six element vectors, such as in Eigen. However, this representation does not succinctly capture the underlying structure and algebra of \(\text{SE}(3)\) nor its relationship to \(\text{se}(3)\). The mathematical structure of these objects builds upon the structure of Lie Groups and Lie Algebras, which in turn build upon coarser mathematical abstractions like Vector Spaces and Groups.

In a sense then, my aim sits at the top of a heriarchy of mathematical abstractions, which I will attempt to implement as concepts. This heirarchy is shown in the image below.

math concepts

Wherever possible, I want to use Concepts and Requirements over inheritance and virtualization to implement an \(\text{SE}(3)\) template. It seems to me that a good strategy is to proceed from the bottom up, implementing concepts for more primitive abstractions and building upon them to create more complex structures.

This post is licensed under CC BY 4.0 by the author.