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.
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.