Affine Space Types

Well defined semantics for positions and displacements.

The Affine Space

I recently came across a geometric structure that deserves to be better known: The Affine Space .

In fact, like many abstract mathematical concepts, it is so fundamental that we are all subconsciously familiar with it though may have never considered its mathematical underpinnings.

Strangely enough, once I assimilated the concept, my Baader-Meinhof phenomenon kicked in and it seemed that everyone is suddenly talking about the Affine Space. I’ll be linking to multiple resources that do a much better job than I can at explaining them.

This post will introduce the Affine Space structure and focus mainly on its role in the C++ type system, the standard library and for creating new strong types.

CAVEAT EMPTOR

This post is not about other common “affine” topics such as:

Affine Transformations : In computer graphics and image processing, geometric affine transformations are parametric shape deformations where parallel lines (in e.g. 2D or 3D) remain parallel after the transformation;

Affine Type Systems : I really wanted to title this post Affine Types, however in Type-Theory affine type systems are well defined.

Although these may be indirectly and mathematically related, any such link is beyond the scope of this post. Similarly, I will not delve into many of the deeper mathematical aspects, details and connections.

My focus (and perhaps the main reason you may find this post interesting and different from other resources) will be on the formalization and its role in better API design and more specifically the design and public interface of classes or class templates.

WARNING: I am not a mathematician. The explanations, intuitions and interpretations are my own and thus may be utterly wrong. If you find such errors, please drop me a line in the comments (or elsewhere) so I can be enlightened and correct the mistakes.

I am writing this as a programmer to a programmer, so although familiarity with elementary-school Linear Algebra is assumed, that you are a mathematician is not.

Also, I am treading a fine line between mathematical purity and pragmatic C++, so even where not explicitly stated assume an asterisk reasonably ignoring edge-cases with undefined-behaviors.

Motivating Examples

Pointer Arithmetic

Consider the following C code:

typedef float T; // declare T<br>T arr[42]; // an array of T<br>T* beg = &arr[0]; // pointer to first element of the array<br>T* end = beg + 42; // pointer to one past the end of the array (OK, not UB)<br>int cnt = end - beg; // element count or offset<br>T* last = beg + cnt - 1; // pointer to the last element<br>int neg = beg - end; // a negative or backwards offset from 'end'

There are four types in use in this snippet:

T (float)

T[42]

T*

int.

T is arbitrarily chosen here as float and T[42] is not really relevant to this example (it is here to avoid UB).

We are interested in the interactions of the two remaining separate types: int a signed integer and T* a pointer.

Observe that:

We can add integers to pointers and subtract integers from pointers [1].

The result is a pointer type .

We can also subtract pointers to get a (signed) integer type [2].

Integers can (obviously) also be added, subtracted and multiplied by each other to get other integers (closure under addition and multiplication [3]).

Note however, that mathematically for integers subtraction is not really a standalone operation (operator) but really just a notational shorthand (or syntactic sugar) for addition with the inverse (the right-hand-side multiplied by -1).

However, this code does not compile:

beg + end; // Error C2110: '+': cannot add two pointers<br>42 - beg; // Error C2113: '-': pointer can only be subtracted from another pointer<br>beg * 3; // Error C2296: '*': illegal, left operand has type 'T *'

MSVC’s errors are very informative here and teach us that the addition, subtraction and multiplication operations are only allowed for some type combinations and, as in this case, not for others.

What does adding two addresses mean? What does it mean to multiply an address by a scalar (negative or otherwise)? These questions do not have a clear answer (or any answer for that matter) and thus these operations are not permitted.

Given “meaning” == “valid semantics” ;

We desire: “no meaning” == “invalid semantics” and;

“invalid semantics” ⇒ invalid or rejected syntax .

The value of a pointer is just a number, an integer, an index, specifying the “cell-address” offset in some memory address space. So does this mean that T* x and using *x are just syntactic sugar in C for some base_addr[x]?

No . Even in C, and most likely even in earlier languages, there is a semantic distinction of types that does not allow pointers to behave as regular (indexing) integers.

In other words, a pointer is an integral value (typically unsigned) with non-arithmetic semantics (and hence a special syntax).

In C++ (as in C) the...