C++, Abstract Algebra and Applications

Robert Ramey

6 July 2011

Preface

This book is for anyone tasked with the responsibility for making a correct, maintainable, high performance program in C++. C++ is unique in it's ability to deliver these benefits - but this comes at a cost. The cost is a very complex language. Both the definitive reference? and the standards document? each exceed 1200 pages of demanding text. It's impossible for anyone to just sit down and read the C++ literature and understand the language. C++ supports all computing paradymes introduced over the last 40 years: structured programming, object oriented programming, generic programming, and lately, functional programming. There are many ways to do the same or similar things. It's not always obvious which method to choose. But the choice can have unintended consequences which make it impossible to develop the program beyond a certain size, make it impossible to maintain or create other problems.

The purpose of this book is to:

Demonstrate how power and utility of the C++ type system and it's relation to mathematics.

Illustrate how this system can be expoited to create provably correct and efficient programs.

Apply these formalisms to several case studies including embedded systems and data management and analysis.

Note

We presume that the reader knows at least some C++. When we touch upon some specific feature of the language for the first time, we give a short explanation in a sidebar like this one. If one is familiar with the feature, or the brief explanation of it is sufficient, he can just continue on with the text. Otherwise, it's a good idea to look up an more complete explanation on one of several existing C++ text books.

Acknowledgements

Chapter 1. Types

Types

A datum as a piece of information. Plural is data. A datum has a type and a value. Types provide information about the data corresponding to the named type. Examples of types:

Abstract ideas like integer and set

Real world ideas like price, color, distance, etc..

Real world objects like oranges, people, etc.

The C++ language contains a rich set of facilities for creating, using, and manipulating types.

primitive types. A selection of built-in or primitive types like char, int, double, etc.. These types are implemented by reserving a fixed number of bytes in memory to hold some value. Examples would be:

char - an 8 bit number which corresponds to an element in a table of characters.

int - a 16, 32, or 64 bit number which models a signed integer as used in arithmetic.

double - a 64 or 80 bit number which models rational number as used in science and engineering.

enum - a value which can take on one of a discrete number of states

// a type representing multiple possibilities
enum class no_value {
  declined_to_state,
  outside_usa,
  Illegible,
  other
};

const char * get_text(const no_value & nv){
  switch(nv){
  case no_value::declined_to_state : return "declined to state"; break;
  case no_value::outside_usa : return "outside use"; break;
  case no_value::Illegible : return "Illegible"; break;
  case no_value::other : return "other"; break;
  default: return nullptr;
  }
}

#include <ostream>

std::ostream & operator<<(std::ostream & os, const no_value & nv){
  os << get_text(nv);
  return os;
};

type composition

Create new types from the composition of other types. One can create a new of a new type which "holds" a collection of other types so they can be considered as a one type.

// create a new data type named "date" from three integer types
// the new type, "date", will contain distinct elements day, month and year
class date {
private:
  const unsigned char m_day;
  const unsigned char m_month;
  const unsigned short int m_year;
  constexpr long int daysbce() const {
    return m_year * 366 + m_month * 31 + m_day;
  }
  // eliminate default constructor
  date() = delete;
public:
  constexpr date(
    unsigned char day,
    unsigned char month,
    unsigned short int year
  ) :
    m_day(day),
    m_month(month),
    m_year(year)
  {}
  constexpr bool operator<(const date & rhs) const {
    return daysbce() < rhs.daysbce();
  }
};

This the traditional way one uses C++ to create a composite type from a set of constituent types. In the above example, we use a number of keywords from more recent versions C++.

Note

A class consists of class members. Members can be constant or mutable data. Members can also be function definitions. These functions have access to the class member data and other class member functions. The above example is a simpler class which models the real world notion of a date. Our intention here is that this newly defined type be immutable. That is, once created it is not altered. This is typical of the examples used in this book - but it is by no means universal. Here are notes on the above example.

private/protected/public

These keywords indicate which part of the class is visible to the rest of the program and which part is visible only to members of the class itself. Generally, the private parts are implementation details while the public parts specify that class interface. Our custom is to list the private class members before the public ones.

class

C++ uses class or struct to create composite types. The only difference is that all members of a struct are public which class members maybe private, public or protected.

constructor

A member function with the same name as the class is invoked when the class is created. This creating can occur at compile time, on the program stack or in the memory heap. Its principle function is to initialize the class member variables. There can be several constructors which differ in their function arguments. In the above example, the name of the class is "date" so all the constructors are named "date". The constructor can and should be used to guarantee that any variable created is always in a valid state which models some real world object or idea. This implies that our classes will have at least one constructor and that that constructor will take one or more arguments.

If one doesn't specify any constructors, the C++ compiler will automatically add some to your code. This kind of automatic behavior is intended to help the programmer to "do the right thing". It usually does - except when it doesn't. In such cases if can result in surprising behavior. Since we advocate providing at least one constructor with arguments, the compiler won't add any constructors on our behalf. So we don't get this sometimes surprising behavior.

constexpr

This keyword indicates that the member can be evaluated at compile time. This generally means that the returned value depends only it's arguments, other constexpr functions, const members, and not on any data outside the class. Such functions can be evaluated at compile time. constexpr turns out to be very useful in the implementation of the ideas presented in this book.

const

const data members are those not expected to change once created. Any code which assigns new values to these members will provoke a compile time error.

const member functions cannot alter any data members. Again any code in the function which assigns new values to any member of the class will provoke a compile time error.

noexcept(true)

noexcept(true) indicates that the code the corresponding function is not expected to throw any exception. Although not strictly required, this hint is used by the compiler to optimise code generation.

operator

C and C++ have a rich expression syntax which implements the syntax of normal arithmetic with the symbols, +, -, *, /, ==, <, etc. These operations are implemented for built-in types like int, float, etc. By specifying an operator member function we can implement them for our own data type - in this case date. In our example we implement the < operator so that we can now use:

int f(const int & t){
  return ++t; // syntax error - good
}
int g(const int & t){
  int u = t;
  return ++u;
}
int h(int & t){
  return ++t; // changes value of t
}
int main(){
  int i = 0;
  int j;
  j = f(i); // ok - syntax error inside f
  j = g(i); // returns expected value and doesn't change i
  j = h(i); // uh - oh quietly changes value of i to ?
}

This is referred to was "operator overloading".

One can also create a new type which "holds" one and only one of a set of other types. This is generally referred to as a union or variant type.

// create a new data type named "price" from two other types
// the new type, "price", will contain either a price or a reason
// why there is not price listed.
union price {
    fixed_radix<unsigned int, 100> m_value;
    no_value m_no_value;
};

This is the traditional way one uses C++ to create a union type from a set of constituent types.

parameterized types - templates

A "template" is a snippet of code with one or more dummy parameters which are substituted with variables. The template key word which, along with another type or value used as parameter, can create another type. Here we create a type which corresponds to a value which is composed of a whole and fractional part.When the template is used to create a new type, the T is replaced with some type and the Radix is replaced with some integer. This might be useful in modeling real world concepts such as price in dollars and cents, eggs in dozens, etc. The syntax to declare and define a type to hold such a value could be:

#include <type_traits> // for is_integral
#include <ostream>     // for stream

template<typename T, int Radix>
class fixed_radix {
private:
  static_assert(
    std::is_integral<T>::value,
    "integral type required here"
  );
protected:
  T m_value;
  // used only by implementation of derived classes
  constexpr explicit fixed_radix(const T & cents) :
     m_value(cents)
  {}
public:
  constexpr explicit fixed_radix(const T & whole_part, int fractional_part) :
    m_value(whole_part * Radix + fractional_part)
  {}
  constexpr bool operator<(const fixed_radix & rhs) const {
    return m_value < rhs.m_value;
  }
};

// default display for fixed radix is in format 99.99..
template<typename T, int Radix>
std::ostream & operator<<(std::ostream & os, const fixed_radix<T, Radix> & fr){
  os << fr.m_value / Radix << '.' << fr.m_value % Radix;
}

Note

type trait

A type trait is a function which takes a type as an argument and returns a type with boolean member variable named value . In the example above the statement std::is_integral<T>::value is a type trait.

static_assert

This statement verifies that a stated condition evaluates at compile time to true. If a condition depends upon values only known at runtime, the static_assert will invoke a compile time error. Frequently, this condition will take the form of a type trait. In this example, we have used the static_assert statement to verify that the type T used as an argument in our template class fixed_radix is some sort of integer type. Other types make no sense in this context. Should a non integer type be passed as parameter T, the static_assert will invoke a compile time error and display the message in the second argument.

T &

C++ offers multiple ways to pass parameter to functions. This specification indicates that the compiler should generate code which passes the parameters by address and that the value being referred to should not be modified by the function. This is the most common way to pass parameters in modern code. It has the following characteristics:

it doesn't copy the value of the parameter. If the type being passed is large, this will save significant execution resources. If the type being passed is small, nothing will be saved but it won't cost much extra either.

In many cases, for small functions the whole function will be compiled in line so there will be no extra cost incurred in passing by reference.

In some cases this will cause an extra copy of the parameter. This can be addressed, but due to C++ move/copy rules, but it can also complicate the program to significant extent. Our recommendation is to use const T & . It if turns out that these extra copies are significant in the execution time of the program, the parameter passing can be altered to eliminate these. The changes will only effect this one function so there's no risk that this enhancement will accidentally break the rest of the program.

const T &

const assures us calling a function with a parameter won't modify the parameter. Any attempt to do so will result in a compile time error. Function which modify their parameters are almost guaranteed to result in programming errors at some point. This is illustrated by this example:

int f(const int & t){
  return ++t; // syntax error - good
}
int g(const int & t){
  int u = t;
  return ++u;
}
int h(int & t){
  return ++t; // changes value of t
}
int main(){
  int i = 0;
  int j;
  j = f(i); // ok - syntax error inside f
  j = g(i); // returns expected value and doesn't change i
  j = h(i); // uh - oh quietly changes value of i to ?
}

Reading the main line code, one can trace the execution of functions g and f. But there is no hint that the function f silently changes the value of i just by calling it. This would be contrary to the normal reading of a mathematical function. Usage of functions which might modify their parameters would mean that in order to understand what happens when main is called, we'd have to investigate what f and g might do. That is, there is no way we can verify the functioning of main without delving in to functioning of everything it calls. If we require that no functions modify their parameters, we know that we can verify the flow of execution of main without having to investigate any of the functions. We only have to verify the return values - which is a much smaller task than verifying the operation of every function we call. In fact, that might not even be possible since the function being called my be pre-compiled from some library.

Creation of a specific type from a template is simply a question of substituting specific values for the parameters. Here we create type to represent the price of some good.

fixed_radix<unsigned int, 100> price{1,99}; // keep track of prices in dollars and cents

In this example, we're modeling a real world notion of price. Note that there are no addition operations defined for fixed_binary so any attempt to added two prices together will fail to compile. This is exactly what we would want as adding prices generally would make no sense in the real world we are trying to model here. Also, If we were modeling something else such as account balance, we wouldn't choose unsigned int as an argument, but rather some sort of signed value.

type refinement through inheritance

Our fixed radix type is well suited to representing prices. Since it doesn't define an addition operator, any attempt to add two prices (which doesn't make sense) will fail with a compilation error. So if we use it to represent a quantity of money, we'll have a problem. Unlike prices, adding quantities of money is a legitimate operation. So what we need is to create a new type which inherits the properties of our fixed_radix type but adds the addition operation. C++ supports this requirement by means of inheritance. We inherit the original type and add those operations which an amount is required to support.

template<typename T, int Radix, typename Derived = T>
class amount : public fixed_radix<T, Radix> {
  using base = fixed_radix<T, Radix>;
protected:
  // used only by implementation of derived classes
  constexpr explicit amount(const T & cents) :
    base(cents)
  {}
public:
  constexpr explicit amount(const T & whole, int fraction) :
    base(whole, fraction)
  {}
  constexpr Derived operator+(const Derived & rhs) const {
    return Derived(base::m_value + rhs.base::m_value);
  }
  constexpr Derived operator-(const Derived & rhs) const {
    return Derived(base::m_value - rhs.base::m_value);
  }
};

// output operator is inherited publicly from fixed_radix<long, Radix>

So now we can code something like the following which will compile, execute and produce the correct answer when we add amounts. But if we try to multiply two dollar amounts (to get ... dollars squared?) we'll get compilation error.

using us_dollar_amount = amount<long, 100, us_dollar_amount>;
us_dollar_amount a1{24,95}, a2{32,78};
// will compile and execute OK
std::cout << "total is: " << a1 + a2 MM std::endl;

// will fail to compile
std::cout << "total is: " << a1 * a2 MM std::endl;

The sequence of steps performed that the C++ compiler is:

Recognize the expression a1 + a2

Look for an declaration of the following form

? operator+(const us_dollar_amount & a1, const us_dollar_amount & a2)

Failing to find one, it will convert the operator arguments from us_dollar_amount type to the base class type: amount and look again for a matching function declaration.

use_dollar_amount operator+(
    const amount<long, 100, us_dollar_amount> & a1,
    const amount<long, 100, us_dollar_amount> & a2
)

This time it will be successful and will invoke the base class version of the addition operator.

The base class operator will perform the addition and return a us_dollar_amount type value.

Values of type money with the same "Radix" parameter CAN be added and subtracted since we've defined addition and subtraction operators for our new amount type. Also note that the values of type amount can also be displayed without writing additional code. That is, the operators of a base class are "inherited" from by the derived classes. Not the odd feature that the name of the derived class is used as a template parameter of the base class. This is what permits the addition operation defined in the base class to return an instance of the derived class. It looks strange and takes getting used to, but it works well for our purposes. It has permitted us to factor common functionality into a base class while still return types lower in the type hierarchy.

Note

public inheritance

This flow of control depends on the ability of functions invoked with arguments of a base class to be implicitly converted to their base class. This ability is enabled by using the word public is the derived class declaration of the base class.

CRTP

Study carefully this pattern. The base class - amount has a template parameter which refers to the derived class which invokes it. This is the reason for the surprising flow of control from the derived class - us_dollar - up to the base class via public inheritance - amount - and back down to derived class - us_dollar. This pattern turns out to be surprisingly common - so much that it has a name: Curiously Recurring Template Pattern.

type conversion

Types can be converted from one type to another by various means. Some such conversions are implicitly invoked by the C++ compiler while others are explicitly invoked by programmer request. Implicit conversions include:

built-in numeric types such as int, long, float etc. may be implicitly converted during the parsing of a C++/C expression

when one type is inherited from another, and the base type is used as function parameter, instances of the derived type may be implicitly converted to the base type in order to permit invoking the function itself. Here's an example:

fixed_radix<unsigned int, 100> price{1,99}; // keep track of prices in dollars and cents

There is no definition for ostream & operator<<(ostream & os, const amount & a); But compilation will not fail. The compiler looks into the base class and sees that a stream output operator with the appropriate signature exists. So the value of amount<unsigned int, 2> is converted to a value of type fixed_radix<unsigned int, 2> and the stream output operator of the base class is invoked with the newly converted data and type. All this happens with no explicit instructions from the programmer.

constructor

A constructor can be implicitly invoked to convert a value one type into a value of another type.

class zip_code {
  public:
  // converting constructor
  constexpr zip_code(const unsigned int & i){
    // ... validate that i is a legal zip code
  }
  // casting operator
  constexpr operator unsigned int () const;
};

bool lookup(const zip_code & z){
  return ...
}

void f(){
  zip_code z{91602}; // create a zip code
  lookup(z);         // no conversion necessary
  lookup(4);         // invoke constructor to convert 4 into a zip_code
                     // then pass zip_code to lookup function
  lookup(            // equivalent code
    zip_code{4}
  );
  unsigned int i = z // implicit cast from zip_code to unsigned int
}

When we pass an integer argument to the function lookup, the C++ compiler finds that the function doesn't take an integer argument. But it discovers that there is a way to construct a zip_code type from an integer. So it emits code which invokes the constructor to perform the conversion and passes the converted value to the lookup function. Whether or not this a good idea would be depend upon circumstances. In this text, we intend to discourage "unseen" implicit behavior. So we would generally use the key word explicit to suppress this behavior.

class zip_code {
  public:
  constexpr explicit zip_code(const unsigned int & i){
    // ... validate that i is a legal zip code
  }
  // casting operator
  constexpr explicit operator unsigned int () const;
};

void f(){
  lookup(4);         // syntax error - lookup doesn't take integer argument
  unsigned int i = z // syntax error - no way to convert zip_code to integer
}

casting operator

A class can contain a "casting operator" which can implicitly cast the value of a class to a value of a different type. This has the same benefits and problems "casting constructors" do. So again, if we include a casting operator, we would use he key word explicit to suppress implicit conversions.

Other conversions only happen when explicitly requested by the programmer

metafunctions

metafunctions are functions which take a type argument. We've already been introduced to type traits which are a kind of function which takes an type as an argument and returns a value which can be converted to bool at compile time. The notion is more general. The following metafunction from the standard library takes an integer type as an argument and returns an unsigned integer type of the same size.

template<typename T>
using unsigned_T = std::make_unsigned<T>::type;
static_assert(
  std::is_unsigned<unsigned_T>::value,
  "unsigned_T should be unsigned integer"
);

Metafunctions constitute a complete type manipulation language that C++ implements at compile time. There has been much written on the creation and usage of metafunctions in C++. [abrahams]

type aliases. Types can be assigned new names to by used as synonyms or aliases.

// create types as money with fractional part of 100 cents
using us_dollar_amount = amount<long, 100>;
// cents are not used with Japanese Yen
using japanese_yen_amount = amount<long, 0>;

The newly created type is indistinguishable from the underlying type it refers to. That is std::is_same<dollars, money<100>>::value returns a value of true. It's main usage is to name types in a meaningful way. In this example, we've used an instance of a type created from a template - money<F> but an alias can be created for any existing type.

opaque type aliases. The above example reveals a weakness which we can illustrate with the following example:

using swiss_franc_amount = amount<long, 100>;

// this compiles without error !
us_dollar_amount balance = swiss_franc_amount{10,99};

Assuming the names of the variables reflect the intention of the programmer, it seems pretty obvious that these would be programming errors. But our compiler doesn't detect any errors, produces an erroneous result which is likely to passed to other parts of the program producing a chain of incorrect outputs. The problem here is the fact that the type alias doesn't actually create a new type, but rather a new name for an existing type. But in many cases, one expects types with different names to correspond to different types - which is what has happened here. The solution is to actually create a new type which may have exactly the same properties of another type, but still be distinguished as different:

// create opaque type aliases for different currencies
class us_dollar_amount : public amount<long, 100, us_dollar_amount> {
  using base = amount<long, 100, us_dollar_amount>;
  friend base;
  constexpr explicit us_dollar_amount(const long & cents) :
    base(cents)
  {}
public:
  constexpr explicit us_dollar_amount(const long & whole, int fraction) :
    base(whole, fraction)
  {}
};
class swiss_franc_amount : public amount<long, 100, swiss_franc_amount> {
  using base = amount<long, 100, swiss_franc_amount>;
  friend base;
public:
  constexpr explicit swiss_franc_amount(const long & whole, int fraction) :
    base(whole, fraction)
  {}
};

void f2() {
us_dollar_amount balance{10,99};
balance = us_dollar_amount{10,99} + us_dollar_amount{4,98};
// should produce compile time error
balance = us_dollar_amount{10,99} + swiss_franc_amount{4,98};
}

types from the Standard Template Library or other libraries. Types can be created from the standard template library of templates.

#include <tuple>

// a triplet of 3 unsigned integers representing a date in form ddmmyyyy
using date1 = std::tuple<unsigned char, unsigned char, short unsigned int>;

#include <set>
#include <functional> // less

std::set<int> s; // s contains a set of unique integers
std::set<date> d; // d contains a set of unique dates

Note

namespace

importing code from C++ libraries creates the possibility of name conflicts. This is addressed by the namespace facility. In our example, the std:: is a namespace which is used to qualify the names in the standard library. Types and data declared in the standard library are within {} brackets:

namespace std {
  template<typename T>
  struct set {};
}

Types and data declared withing a namespace can be referred to in two ways:

by prefixing the namespace name as in std::set

include a using namespace statement in the function or class as in using namespace std;

In our code and examples, we will include code from the standard template library, boost and other libraries.

Types and Sets

The data type short unsigned int is typically implemented as 16 consecutive bits. Thus it corresponds to the set of integers from 0 to 65535 . Since zip codes are integers less than 10,000, a short unsigned int can represent any one of them. So it would be natural for a C++ programmer to select a short unsigned int as a data type to represent a zip code:

using zip_code = short unsigned int;

One could say that the set of numbers representable by the short unsigned int C++ data type contains the set of zip codes. But the correspondence between zip codes and unsigned short int is only approximate. Note that:

The inverse isn't true. There are short unsigned int values which don't correspond to any legal zip code.

unsigned short int can be added to each other to produce another value. But this is meaningless for zip codes. The same goes for other arithmetic operations applicable to unsigned short int.

Any program which uses short unsigned int to represent zip codes will have to address the fact that these sets do not have a one-to-one correspondence to each other. This will entail:

explicitly verify that a zip code is legal when it is read from an external source.

taking care to avoid inadvertently doing arithmetic on zip codes. If a programmer does this, a nonsensical result will be returned. This error will not be detected at compile time. Only with luck will it be detected at run time.

taking care to avoid even non-arithmetical operations. Zip codes will likely need to be compared to each other. If a programmer inadvertently, compares a zip code to another value of a different type, E.G. a social security number, the result will make no sense, but the error may not be easily detectable.

The same considerations apply to selection of other data types. Most other types are more complex than a zip code so the mismatch between the type we're modeling and the C++ data type selected will usually a lot greater.

A large portion of real world code is dedicated to reconcile this lack of correspondence. Usually this would mean having the programmer include code in various places in the program which verifies that an a short unsigned int representing the a zip code is always legal and is not used is a way which makes no sense. This is tedious, error prone, and hard to verify. Whenever the code for zip code is reused or altered, all this verification has to be redone.

If the above observations seem trivial, it's because they are. But how can we best address them?

Suppose we create our own zip_code data type

#include <stdexcept>
#include <array>
#include <algorithm> // binary_search
#include <istream>

static constexpr const std::array<unsigned int, 2> m_legal_zip_codes = {
  12345,
  67989
};

class zip_code {
private:
  short unsigned int m_value; // hold an integer
  // prevent construction of an invalid zip code
  zip_code() = delete;
public:
  template<typename T>
  // create a zip_code from an integer
  constexpr explicit zip_code (T t) :
      m_value(t)
  {
    // require that argument be convertible to a zip_code
    static_assert(
        std::is_convertible<T, short unsigned int>::value,
        "zip_code must be constructed from an integer type"
    );
    // ... code to verify that z is actually a legal zip code
    if(std::binary_search(
      m_legal_zip_codes.cbegin(),
      m_legal_zip_codes.cend(),
      t
    )){
      throw std::range_error("invalid zip_code");
    }
  }
  // we don't have to specify copy/move/assignment etc as the
  // default ones are suitable for our usage
  // define the only operations that make sense for a zip code
  constexpr bool operator==(const zip_code & rhs) const {
    return m_value == rhs.m_value;
  }
  constexpr bool operator!=(const zip_code & rhs) const {
    return m_value != rhs.m_value;
  }
  // since the set of zip codes is a weakly ordered one and it is
  // likely that we will want to sort according to a zip code,
  // define comparison functions
  constexpr bool operator<(const zip_code & rhs) const {
    return m_value < rhs.m_value;
  }
  constexpr bool operator>(const zip_code & rhs) const {
    return m_value > rhs.m_value;
  }
  constexpr bool operator<=(const zip_code & rhs) const {
    return m_value <= rhs.m_value;
  }
  constexpr bool operator>=(const zip_code & rhs) const {
    return m_value >= rhs.m_value;
  }
};

std::istream & operator>>(std::istream & is, zip_code & z){
  short unsigned int t;
  is >> t;
  z = zip_code{t};
}

Note

zip_code() = delete

Our goal is that any value of type zip_code correspond to a real world zip_code. So a zip_code without a value should not be constructible. In some cases, C++ will create such a constructor implicitly. Including zip_code() = delete will guarantee that this doesn't happen. Strictly speaking, C++ will only create such a default constructor if no other constructor is created. So in this instance the zip_code() = delete isn't really necessary. But our custom is to use it anyway. Doing so causes no harm. But subsequent revisions of the program could alter the set of constructors and we could find that C++ has created a default constructor which we were not aware of. Including this statement addresses that case, states our intention and avoids surprises.

explicit

we generally use explicit on constructors to suppress generation of implicit conversions. In this case it's not strictly necessary as our constructor verifies that all arguments used correspond to legal zip codes. But still, we prefer that our code not intentionally or unintentionally depend on implicit behavior.

Here we have managed to align the definition of zip_code with the notion of "zip code" as it occurs in the real world. (Note that our zip_code example falls way short of a complete definition of a real world zip code.)

For each legal zip code there is one and only one corresponding value of zip_code. In other words, there is a one-to-one correspondence the real world zip code and an instance of the C++ data type zip_code.

Any attempt to create a value of the type zip_code which does not correspond to a legal zip code will result on an error. If the constructor argument is a value which is known at compile time, such an error will take the form of a failure to compile. Otherwise, the program will throw an exception at runtime.

zip_code z{99999}; // results in an compile time error
zip_code z1;       // results in an compile time error

void f(unsigned int z){
  // results in runtime exception if and only if z is not a legal zip code
  const zip_code{z};
}

No other checking of zip_codes is required to be included anywhere else in any program which uses this zip_code type.

All the code required to implement this zip_code type this is found in one and only one place.

where it can be verified to be correct independently of the context of it's usage

so that any erroneous usage of zip_code anywhere else will fail as soon as possible in an transparent manner

and any improvements and/or optimizations in it's implementation will automatically be propagated to anywhere it's used.

We've created a zip_code type which very closely corresponds to the real world zip code. Specifically, any real world zip code can be represented one and only one instance of our zip_code type and every possible value of our zip_code type will refer to one and only one real world zip code.

Notation

Z
the set of all legal zip codes.

z, z1, z2

a real world zip code.

an instance of type zip_code.

i
an integer

Comparison

Operation
C++ Expression

Z
zip_code

z ∈ Z is always true by definition

z is always an instance of type zip_code.

static_assert( std::is_same<decltype(z). zip_code>, "z is a zip_code" );

given an integer i, create a corresponding zip_code z
zip_code(i) // throws error on failure

are z1 and z2 the same?
z1 == z2

is z1 less than z2
z1 < z2

Correspondence Between Sets and Types

Operations on sets can create new sets. Operations include union, intersection, complement, etc. Analogously, operations of C++ Types can create new Types. In fact, for every operation defined on sets, one can define a corresponding operation on C++ data types.

Notation

T, A, B
a set of possible values or C++ data type corresponding to a set

t, a, b

instances of types T, A and B respectively

U

universe_set. Every t is a member of the universe_set

∅

empty_set. No t is a member of empty_set

Correspondence

Operation
Set
C++

is t a member of T?
t ∈ T
true // by definition

Universe
U

struct universe_set {
  // any type t is convertible to type universe_set
  template<typename T>
  constexpr universe_set(const T & t){}
};

empty set
∅

struct empty_set {
  // no type can be converted to the null set
  template<typename T>
  constexpr empty_set(const T & t) = delete;
};

construct an instance of T

T t{arguments ...}; // construct an instance of type T

is t a member of A?
t ∈ A
A a{t}; // will fail if t is not a member of A

is t NOT a member of A?
t ∉ A
! std::is_convertible<T, A>::value;

is T a subset of A?
T ⊆ A
std::is_convertible<T, A>::value;

declare T a subset of A

struct T : public A{...};

intersection of A and B
A ∩ B

template<typename A, typename B>
struct intersection : public A, public B {
  intersection() {}
  template<typename T>
  intersection(const T & t) :
    A(t),
    B(t)
  {
    static_assert(
      std::is_convertible<T, A>::value,
     "type not in A"
    );
    static_assert(
      std::is_convertible<T, B>::value,
     "type not in B"
    );
  }
};

union of A and B
A ∪ B

boost::variant<A, B>;

product of A and B
A X B

#include <tuple>

template<typename A, typename B>
using product = std::tuple<A, B>;

complement of A
¬A

// t is not a member of A
template<typename A>
struct complement {
  complement() {}
  template<typename T>
  complement(const T & t){
    static_assert(
      ! std::is_convertible<T, A>::value,
      "type not in complement<A>"
    );
  }
};

difference of A and B
A - B

// t is a member of A but not B
template<typename A, typename B>
using difference = intersection<A, complement<B>>;

map A to B with function f
f(a)->b

B f(const A &a);

Notes on the above tables:

membership

Every instance t is a member of the set T. This is true due to the manner which we've defined t and T.

inclusion

If any instance of T is implicitly convertible to A, then t is included in A and T is a subset of A. Certain types are refinements of other types. Hockey players are "kinds of" people. This is modeled by C++ using public inheritance.

struct person {};

struct hockey_player : public virtual person {};
static_assert(
  std::is_convertible<hockey_player, person>::value,
  "A hockey player is a  kind of person"
);
struct baseball_player : public virtual person {};
static_assert(
  std::is_convertible<baseball_player, person>::value,
  "A baseball player is a  kind of person"
);

The key word "public" makes all the behavior or the base class "person" available to the derived class. Without using this key word, the inheritance would be "private" and data of type "hockey_player" could not be implicitly converted to "person".

Note

virtual base class

The key word "virtual" means that there will exist only one instance of "person" for all derivations. So a "hockey_player" and "baseball_player" will refer to the same "person". This is not related to our notion of correspondence between types and sets but it will be important when we use these data types to hold actual data. When virtual inheritance is used, the inheritance diagram looks like this.

           person
             /\
hockey_player  baseball_player
             \/
          athlete

intersection

If an instance of a data type can be converted to multiple other data types, it models the set notion of a union. In this example, an "athlete" can be implicitly converted to either a hockey_player, or a baseball_player.

using athlete = intersection<hockey_player, baseball_player>;

static_assert(
  std::is_convertible<athlete, hockey_player>::value
  && std::is_convertible<athlete, baseball_player>::value,
  "An athlete is a \"kind of\" hockey_player, baseball_player and a person"
);

complement

using not_a_baseball_player = complement<baseball_player>;

Note that we can't actually create a instance of type not_a_baseball_player. But we can use it in other metafunctions:

struct joe : public baseball_player {};

static_assert( // compiles OK !
  std::is_convertible<joe, complement<hockey_player> >::value,
  "joe is NOT a hockey_player"
);

static_assert( // compiles OK  !
  std::is_convertible<joe, baseball_player>::value,
  "joe IS a baseball_player"
);

static_assert( // compile fails !
  std::is_convertible<joe, hockey_player>::value,
  "joe is a hockey_player"
);

static_assert( // compile fails !
  ! std::is_convertible<joe, complement<baseball_player> >::value,
  "joe is NOT a baseball_player"
);

difference (aka relative complement)

Suppose we want to create a type which corresponds to the set of athletes who does not play baseball. This corresponds to the set theory expression A - B which is defined as A ∩ Bc. Implementation is straightforward.

// declare an athlete who is not a baseball player
using athlete_not_baseball_player = difference<
  athlete,
  baseball_player
>;

athlete a;
baseball_player b;
complement<baseball_player> nb;

// error:cannot create an instance of a null set
athlete_not_baseball_player p;

Note that we can define such a set, we cannot actually create an initialized instance of it. This is another instance of our types accurately mirroring the real world which we are trying to model.

Our identification of set theory and the C++ typing system is inspired by in part by "Denotational Semantics" as described by [schmidt].

Algebra of Types

Types as Magmas

We've established a correspondence between sets of data values and C++ types. Abstract algebra contains the notion of operations on pairs of set elements. For example, given a the set of integers, one can define a addition operation such that i + j -> k where i, j, and k are members of the set of integers. The combination of a binary operation with a set is a new mathematical structure - a magma.

A magma is a set and binary operation such that:

the operation can be applied to any pair of set members

the operation results in another set member. That is, a magma is closed under the operation.

Although we call the operations additive/multiplicative they may have nothing to do with our familiar notions of addition and multiplication.

Since our set consists of C++ types, our operation will take a pair of types and return another type. This is the exact description of a C++ template metafunction!

product operation

Sometimes, we find it convenient to define a new type from the composition of two constituent types. Consider an address which consists of a street name and zip code. The traditional way to create a type to hold data from other types is the C++ class or struct:

class address {
  std::string m_street_name;
  zip_code m_zip_code;
};

With modern C++ there is an alternative which we will prefer here:

using street_name = std::string;
using address = std::tuple<street_name, zip_code>;

In general, we'll create the product of any number of types with std::tuple .

We've now created a new type named address. It "holds" two data items but can be manipulated as one unit. When referring to the product operation for two C++ types A and B, we may use either of the following notations

A * B

std::tuple<A, B>

Note that our operation is not commutative - A * B != B * A

using street_address1 = std::tuple<street_name, zip_code>;
using street_address2 = std::tuple<zip_code, street_name>;
static_assert(
  ! std::is_same<street_address1, street_address2>::value,
  "product operation is NOT communitive!"
);

nor is it associative A * (B * C) != (A * B) * C

using house_number = unsigned int;
using home_address1 = std::tuple<house_number, std::tuple<street_name, zip_code>>;
using home_address2 = std::tuple<std::tuple<house_number, street_name>, zip_code>;
static_assert(
  ! std::is_same<home_address1, home_address2>::value,
  "product operation is NOT associative!"
);

union operation

Sometimes, an accurate model of the real world has to account for the fact that a datum might be one (and only) one of a set of constituent types. In this example, we use the type zip_code which have implemented above to model the zip code reported on some post office form. If this form contains a valid zip code current definition is suitable. But it's also possible that the data in the form doesn't correspond to an actual zip code for some reason. The traditional C++ feature used to model this situation is the enum class:

enum class no_value {
  declined_to_state,
  outside_usa,
  Illegible,
  other
};

But it will suit our purposes better to use a newer approach to implement this idea

class no_value_alternatives {
public:
  class declined_to_state;
  class outside_usa;
  class illegible;
  class other;
};

using no_value = boost::variant<
  no_value_alternatives::declined_to_state,
  no_value_alternatives::outside_usa,
  no_value_alternatives::illegible,
  no_value_alternatives::other
>;

We've now created a new type named no_value. It "holds" one constituent type at a time. When referring to the union operation, we may use either of the following notations

A + B

boost::variant<A, B>

Note that our operation is not commutative - A + B != B + A

using reason1 = boost::variant<
  no_value_alternatives::declined_to_state,
  no_value_alternatives::outside_usa,
  no_value_alternatives::illegible,
  no_value_alternatives::other
>;
using reason2 = boost::variant<
  no_value_alternatives::outside_usa,
  no_value_alternatives::declined_to_state,
  no_value_alternatives::illegible,
  no_value_alternatives::other
>;
static_assert(
  ! std::is_same<reason1, reason2>::value,
  "union operation is NOT communitive!"
);

nor is it associative - A + (B + C) != (A + B) + C

using reason1 = boost::variant<
  no_value_alternatives::declined_to_state,
  no_value_alternatives::outside_usa,
  boost::variant<
    no_value_alternatives::illegible,
    no_value_alternatives::other
  >
>;
using reason2 = boost::variant<
  boost::variant<
    no_value_alternatives::declined_to_state,
    no_value_alternatives::outside_usa
  >,
  no_value_alternatives::illegible,
  no_value_alternatives::other
>;
static_assert(
  ! std::is_same<reason1, reason2>::value,
  "union operation is NOT associative!"
);

nested types

Both product and union operations produce new types. These new types become available to craft even more complex types. When referring to the union operation, we may use either of the following notations

The operations result in new types. So the results of these operations can be used recursively resulting in arbitrarily complex nested types.

Canonical Types

Our operations described above are fine - as far as they go. The problem is that our definition of C++ data type doesn't accurately reflect our usage.

#include <type_traits> // is_same
#include <boost/variant/variant.hpp> // variant

using reported_zip_code1 = boost::variant<
  zip_code,
  no_value
 >;
using reported_zip_code2 = boost::variant<
  no_value,
  zip_code
>;
static_assert( // compile time error!
  std::is_same<reported_zip_code1, reported_zip_code2>::value,
  "types must be equal!"
);

Note

namespace

A C++ feature which permits names to be grouped into "families".

As programs get larger and start to import external code with it's own names, the clashing of names becomes a real problem. C++ addresses this with the namespace feature. The metafunctions variant and is_same are defined in the namespaces boost and std respectively. There are two ways to refer to the specific construct:

One can prefix the name with the name space name such such as std::same.

One can import all the names of a namespace into the current code module. This can be done with the using namespace <namespace name> statement.

// from inside the file <type_traits>
namespace std {

  template<typename T, typename U>
  class is_same {
  public:
    static const bool value = false ; // = ... replace with real definition;
  };

} // end namespace std

// we can use the namespace name as a preface
static_assert(  // compiler error
  false == std::is_same<int, long>::value,
  "types should be different"
);

// or import all the names in a namespace
using namespace std;

// we don't need to specify the namespace now
static_assert(  // compiler error
  false == is_same<int, long>::value,
  "types should be different"
);

equivalent types

The C++ compiler considers the two versions of reported_zip_code different. But they do in fact correspond to the same set of valid data. For each value of the first type, there is corresponding value of the second type. They both model the same real world situation. So we need to create a new idea - equivalence of types as opposed to equality of types. We call two data types equivalent there is a one to one correspondence between the data values which can be "held" by each set. One way to verify if two C++ types are equivalent would be to enumerate all possible values of each type and verify if they can be matched. Clearly we need a better way.

transformations between equivalent types

Remember that equivalence is the idea that two types refer to the same domain of that data set which the type can model. Multiple C++ data types may model the same possible data values. Given a particular type, there are operations we can apply to the type to create another equivalent type.

The expressions in the table below presume that the following has been included in the source code.

using namespace boost; // variant
using namespace std;   // tuple

Notation

A, B, C
C++ types

Equivalent Transformations

Equivalence
Comment

tuple<A> 
<=> 
A

1) a tuple containing a single type can span the same domain of values that the type itself can.

tuple<A, tuple<B, C>>
<=>
tuple<A, B, C>

2) nested tuples are equivalent to unnested ones

tuple<A, B> 
<=> 
tuple<B, A>

3) sequence is not significant in tuples. A*B <=> B*A

tuple<A, universe_set> 
<=> 
tuple<A>

4) a tuple which includes the universal_set models to the same data which excludes the universal_set. See the definition of the universal_set to see this. A*U <=> A

variant<A> 
<=> 
A

5) a variant of one type models the same data as the type it contains.

variant<A, A> 
<=> 
variant<A> 

6) a variant can have only one member of a given type.

variant<A, variant<B, C>> 
<=>
variant<A, B, C>

7) nested variants are equivalent to unnested ones.

variant<A, B>
<=> 
variant<B, A>

8) sequence of arguments to a variant don't matter. A + B <=> B + A

variant<A, empty_set> 
<=> 
variant<A>

9) the empty set can never have a value. So a variant can never take it on as a value. A + ∅ <=> A

tuple<
  A, 
  variant<B, C>
> 
<=> 
variant<
  tuple<A, B>, 
  tuple<A, C>
>

10) product is distributable over union. A * (B + C) <=> A*B + A*C . Proof:

Enumerate possible C++ data types corresponding to left hand side:
(A and B) or (A and C)

Enumerate possible C++ data types corresponding to right hand side:
(A and B) or (A and C)

Since both sides can hold the same data - the operation is valid

variant<
  A, 
  tuple<B, C>
> 
<!=> 
tuple<
  variant<A, B>, 
  variant<A, C>
>

11) union is NOT distributable over product. A + B*C <!=> (A + B)*(A + C) . Proof:

Enumerate possible C++ data types corresponding to left hand side:
(A and B) or (A and C)

Enumerate possible C++ data types corresponding to right hand side:
(A and A) or (A and C) or (B and A) or (B and C)

Reorder (tuple and variant are both commutative)
(A and B) or (A and C) or (A and A) or (B and C)

left hand side is a subset of right hand side - not equivalent

Suppose we're given two arbitrarily complex C++ types and we want to determine whether they are equivalent. We can apply a sequence of equivalent substitutions to convert them to ever simpler types. Eventually we should get to the point where they cannot be simplified further. This is called conversion to canonical form. At this point, the simplified types can be compared to determine equivalence. This process of simplification is similar to expansion of any algebraic expression. Then the terms are ordered in some unique way. The procedure is actually mechanical and can be implemented in a (very complex) metafunction. We've called this metafunction "normalize". It's defined a header file named <algebra.hpp> inside the namespace "algebra".

"normalize" maps any C++ type to it's canonical version. In general, the canonical set will be smaller than the original set of types.

namespace algebra {

  // define metafunction "normalize" here
  // ...

  template<typename A, typename B>
  using is_equivalent = std::is_same<
    typename normalize<A>::type,
    typename normalize<B>::type
  >;
} // end namespace algebra

This almost concludes our exploration of the algebra of C++ types. The rest of this book will only use that which we've explained so far. But in the interests of curiosity and completeness, we'll list a few properties of normalize function and the set it generates.

canonical types

Given any set of C++ types, we can apply the normalize metafunction to all the type members of the set. This will generate a new set of types called the canonical set. This second set has the property that all members can be meaningfully compared via an equality metafunction.

Figure 1.1. normalize function

equivalence partitions

The canonical set will generally be smaller than the original set. So multiple C++ types will map to a member of the canonical set. The creates an "equivalence partition" on the original set. Every C++ type is a member of one and only one member of the canonical set.

Figure 1.2. equivalence partition

The canonical set has properties distinct from the original set:

there is an equality operation which is the same as equivalence.

the result of product operation (tuple) is normalized. This implies that the product operation is associative. The same applies to the union operation (variant).

Hence the canonical set is classifies as a semigroup.

There exits identity elements for product (universal_set) and union (empty_set). Thus the canonical set is a monoid as defined by abstract algebra. Turns out that there quite a few theorms which apply to the manipulation of sets which are monoids. We won't go into those here.

The distributive operation of product over union would qualify the canonical set as a ring in the terminology of abstract algebra. There is an even larger wealth of interesting math that applies to rings. Unfortunately, a ring also would require that at least our union operation have an inverse. So far no one has come up with the definition of an inverse operation which actually corresponds to an operation on a real world union (variant) type. Since we're not mathematicians, we've gone far as we can go for now.

Types and Data

So far we've been studied types as objects of abstract algebra. That is, how different types are related, how then can be manipulated to create other types, etc. Now we consider instances of these types as objects of abstract algebra. Given that we're using the same mathematics applied to different aspects of C++, there's potential for more than a little confusion. Consider our example zip_code. We have seen that we can define types and manipulate them to create new types.

struct zip_code {
  unsigned int m_value;
};
enum class no_value {
  declined_to_state,
  outside_usa,
  Illegible,
  other
};
using reported_zip_code = std::tuple<zip_code, no_value>;

Which is entirely different from creating new instances of a type and operating on them:

struct zip_code {
  unsigned int m_value;
  constexpr bool operator==(const zip_code & rhs) const {
     return m_value == rhs.m_value;
  }
  constexpr bool operator!=(const zip_code & rhs) const {
     return m_value != rhs.m_value;
  };
};
void test(){
  zip_code z1{91602}, z2{93110};
  assert(z1 == z2 || z1 != z2);
}

operations on data

Given two instances of zip_code, z1 and z2, we can apply the operations == and != to determine whether or not they are the same. So taken together, all possible instances of zip_code along with the operations == and != fulfill the requirements of the mathematical definition of a set.

In order for a set to be considered "ordered", all the comparison operators <, >, <=, >= need to be defined for all pairs of elements in the set. That is, the following code should compile and execute

void test(){
  zip_code z1{91602}, z2{93110};
  assert(z1 < z2  || z1 == z2 || z1 > z2 );
  assert(z1 <= z2 || z1 >= z2 );
}

To prove at compile time that the set of instances of a given data type fulfill the requirements of an ordered set, we can define a type trait:

#include <type_traits>
#include <algebra.hpp>

// define a type trait to prove whether or not some type T
// is or is not a set
template<typename T>
using is_set = std::conjunction<
  algebra::is_equality_comparable<T>,
  algebra::is_ordered<T>
>;

And use it to prove that some type fulfills the mathematical requirements of a set.

static_assert(
  is_set<zip_code>::value,
  "zip_code is a weakly ordered set"
);

In order for our zip_code data type to fulfill all the requirements we expect of it, we had to define operator function to implement each of the operations <, >, <=, >=, == and != . Since we want all the data types we create to model ordered or non ordered sets, these operator functions will have to be added to each of these data types as we create them. This can be a tedious and error prone task. So rather than adding boiler plate code to every type which models an ordered set, we can do the same thing in a more succinct, and simpler manner. Here is an example:

#include <algebra.hpp>

class zip_code :
  // generate missing operators
  public algebra::equality_comparable<zip_code>,
  public algebra::ordered<zip_code>
{
private:
  short unsigned int m_value; // hold an integer
  // prevent construction of an invalid zip code
  zip_code() = delete;
public:
  template<typename T>
  // create a zip_code from an integer
  constexpr explicit zip_code (T t) :
      m_value(t)
  {
    // require that argument be convertible to a zip_code
    static_assert(
        std::is_convertible<T, short unsigned int>::value,
        "zip_code must be constructed from an integer type"
    );
    // ... code to verify that z is actually a legal zip code
    if(std::binary_search(
      m_legal_zip_codes.cbegin(),
      m_legal_zip_codes.cend(),
      t
    )){
      throw std::range_error("invalid zip_code");
    }
  }
  // required operator for sets
  constexpr bool operator==(const zip_code & rhs) const {
    return m_value == rhs.m_value;
  }
  // required comparison function for ordered
  constexpr bool operator<(const zip_code & rhs) const {
    return m_value < rhs.m_value;
  }
  // all other operators are geneated automatically
};

static_assert(
  algebra::is_equality_comparable<zip_code>::value &&
  algebra::is_ordered<zip_code>::value,
  "zip_code is a weakly ordered set"
);

We have only needed to define two operators: == and <. The other operators !=, >, <= and >= are inherited from the special base classes algebra::equality_comparable<zip_code> and algebra::ordered<zip_code>. Note the usage of inheritance from a base class template with derived class name as a parameter - the Curiously Recurring Template Pattern. This idea is inspired by the Boost.Operators library[].

The table below describes the families of operators used in our structures and how to generate them using the above described method. All these templates are defined within the namespace algebra. If any required operators are missing, a static_assert will be invoked.

Trait and Base Template
Generated Operations
Required Operations

is_equality_comparable<T>
equality_comparable<T>

bool operator!=(const T & rhs)

t == t1
Returns convertible to bool

is_less_than_comparable<T>

t < t1
Returns convertible to bool

is_ordered<T>
ordered<T>

bool operator>(const T & rhs)
bool operator<=(const T & rhs)
bool operator>=(const T & rhs)

t < t1
Returns convertible to bool

additive<T>
is_additive<T>

t * n

t + t1
Returns T

has_additive_identity<T>
additive_identity<T>

const T & zero<T>()

T{0}

has_additive_inverse<T>
additive_inverse<T>

T operator-()

true == has_additive_identity<T>::value
t1 - t1
Returns T

is_multiplicative<T>
multiplicative<T>

t ^ n

t * t1
Returns T

has_multiplicative_identity<T>
multiplicative_identity<T>

const T & unity<T>()

T{1}

has_multiplicative_inverse<T>

true == has_multiplicative_identity<T>::value
t1 / t1
Returns T

We've already demonstrated the usage of is_equally_comparable to prove support for equality operators required by the mathematical definition of a set. Similarly there are traits to prove support for comparison, addition, etc. These are operations which we can add to sets to produce other types of algebraic structures.

additive

This operation refers to a type which supports the addition operation. We use is_additive<T> to query whether the operation is supported and additive<T> as a base class to generate the operators required to support that addition. The addition operation is associative: x + (y + z) = (x + y) + z and commutative: x + y = y + x .

additive_identity

Given the addition operation on a set T, additive_identity<T> refers to a specific value of type T. Adding any element to the additive element returns the original element. A common example of an additive identity element is the number 0 when discussing the set of integers. For any integer i, i = i + 0.

additive_inverse

An inverse of an element x is an element x⁻¹ such that x + x⁻¹ = e, where e is the additive identity. A common example of an inverse element is the change sign operation when discussion the set of integers. For any integer i, i + (-1) = 0.

multiplicative

This operation refers to a type which supports the multiplication operation. We use is_multiplicative<T> to query whether the operation is supported and multiplicative<T> as a base class to generate the operators required to support that multiplication. The multiplication operation is associative: x + (y + z) = (x + y) + z but not necessarily commutative.

multiplicative_identity

Given the multiplication operation on a set T, multiplicative_identity<T> refers to a specific value of type T. Multiplying any element by the multiplicative identity returns the original element. A common example of an additive identity element is the number 1 when discussing the set of integers. For any integer i, i = i * 1 .

multiplicative_inverse

An inverse of an element x is an element x⁻¹ such that x * x⁻¹ = e, where e is the additive identity. A common example of an inverse element is the change sign operation when discussion the set of integers. For any integer i, i + (-1) = 0.

additive vs. multiplicative operations

Additive operations do not necessarily correspond to arithmetic addition nor do multiplicative necessarily correspond to arithmetic multiplication. From an abstract algebra perspective, the essential distinction between addition and multiplication is that while both operations are associative, only addition is guaranteed to be commutative. So the addition operation on numbers 1 + 2 = 3 and 2 + 1 = 3 produce the same result.

Additive are usually designated with the + symbol while multiplicative operations are usually designated with the X or * symbol. But remember that this is purely arbitrary. It reflects that fact that it is common when the set is numeric, the add and multiply operations correspond to their arithmetic equivalents.

String concatenation is an example of an operation which is not commutative. That is, "abc" ? "xyz" -> "abcxyz" is not the same as "xyz" ? "abc" -> "xyzabc". So this operation would be considered multiplicative rather than additive and hence be designated with the * or X symbol. Note that this is at a variance with common libraries and languages which use the symbol + for string concatenation.

creation of algebraic structures

Now we have a way of adding operator groups to a type, we can define various algebraic structures in terms of the operations they support. Here is a table of the how to create the types which we would most likely use in our programs.

Trait and Base Template
Component Templates

is_set<T>
set<T>

equality_comparable<T>

is_additive_semigroup<T>
additive_semigroup<T>

set<T>
additive<T>

is_additive_monoid<T>
additive_monoid<T>

additive_semigroup<T>
additive_identity<T>

is_additive_group<T>
additive_group<T>

additive_monoid<T>
additive_inverse<T>

is_multiplicative_semigroup<T>
multiplicative_semigroup<T>

set<T>
multiplicative<T>

is_multiplicative_monoid<T>
multiplicative_monoid<T>

multiplicative_semigroup<T>
multiplicative_identity<T>

is_multiplicative_group<T>
multiplicative_group<T>

multiplicative_monoid<T>
multiplicative_inverse<T>

Now we can easily define a set member based on any C++ data type. This reduces our effort to create a set member to a few lines of code. Create a type for holding a price:

#include <algebra.hpp>

template<typename T>
class price : public
  fixed_radix<T, 2>,
  algebra::set<price<T>>,
  algebra::ordered<price<T>>
{
  constexpr price(const T & t, const int i) :
    fixed_radix<T, 2>(t, i)
  {}
};

Create a type for holding an account balance. A balance can be either debit (> 0) or credit (<0) and has a zero element.

template<typename T>
class balance : public
  fixed_radix<T, 2>,
  algebra::additive_group<balance<T>>,
  algebra::ordered<balance<T>>
{
public:
  constexpr balance(const T & t, const int i) :
    fixed_radix<T, 2>(t, i)
  {}
};

Here's another example. Suppose we want to accurately model the concept of color. Colors are the composition of three primary colors. Each primary color has it's own level of intensity. Here we create a type to hold color.

#include <limits>
#include <algebra.hpp>

// light can be combined by addition only
template<typename Derived>
class primary_color : public
  // there is the concept of 0 - light is turned off
  algebra::additive_monoid<primary_color<Derived>>,
  algebra::ordered<primary_color<Derived>>
{
  const unsigned char m;
protected:
  template<typename I>
  constexpr explicit primary_color(const I i) :
    m(i)
  {
    // must be initialized with an integer type
    static_assert(
      std::numeric_limits<I>::is_integer,
      "color must be intialized with an integer type"
    );
    // trap integer overflow
    if(i > std::numeric_limits<const unsigned char>::max()){
      throw std::domain_error("intensity too large");
    }
    // and negative values
    if(std::numeric_limits<I>::is_signed && i < 0){
      throw std::domain_error("intensity cannot be negative");
    }
  }
public:
  constexpr bool operator==(const primary_color & rhs) const {
    return m == rhs.m;
  }
  constexpr Derived operator+(const primary_color & rhs) const {
    return Derived(m + rhs.m);
  }
  constexpr bool operator<(const primary_color & rhs) const {
    return m < rhs.m;
  }
  // permit explicit access to underlying type.
  constexpr unsigned char get_value() const {
    return m;
  }
};

#define opaque_alias(name, base_type)    \
class name : public base_type<name> {    \
public:                                  \
  template<typename T>                   \
  constexpr explicit name(const T i) :   \
    base_type(i)                         \
  {}                                     \
}

opaque_alias(red, primary_color);
opaque_alias(green, primary_color);
opaque_alias(blue, primary_color);

#include <tuple>
using color = std::tuple<red,green,blue>;

constexpr color make_color(
  const red &r,
  const green &g,
  const blue &b
){
  return std::make_tuple(r, g, b);
}

color operator+(const color & lhs, const color & rhs) {
  return color(
    std::get<red>(lhs) + std::get<red>(rhs),
    std::get<green>(lhs) + std::get<green>(rhs),
    std::get<blue>(lhs) + std::get<blue>(rhs)
  );
}

static_assert(
  algebra::is_additive_monoid<color>::value,
  "color is additive monoid"
);

Here is a small test program which uses our primer_color set member:

/*
const color a;     // compilation error - color has no default constructor
const color b(0);  // compilation error - b must be initialized with red,green,blue triple
const color flood_light_color = std::tuple{red{12}, green{34}, blue{45}};
*/
const color spot_light_color = color(red{23}, green{2}, blue{67});
/*
const color actual_color = flood_light_color + spot_light_color;
const int x = flood_light_color + spot_light_color; // compilation error
*/

Notice that our compiler has detected a number of easy to commit errors which otherwise might result in bugs whose source could be very difficult to find.

Similarly, we can create a type for color filter. A color filter diminishes the intensity of light passed through it by a certain fraction.

#include <limits>
#include <algebra.hpp>

// light can be combined by addition only
template<typename Derived> // crtp pattern
class primary_color_filter : public
  // there is the concept a clear filter - transmit 100% of light
  algebra::multiplicative_monoid<primary_color_filter<Derived>>,
  algebra::ordered<primary_color_filter<Derived>>
{
  float m;
protected:
  constexpr explicit primary_color_filter(const float f) :
    m(f)
  {
    // with positive values
    if(f < 0.0f){
      throw std::domain_error("attenuation cannot be negative");
    }
    if(f > 1.0f){
      throw std::domain_error("attenuation cannot greater than 1.0");
    }
  }
public:
  constexpr bool operator==(const primary_color_filter & rhs) const {
    return m == rhs.m;
  }
  constexpr Derived operator*(const primary_color_filter & rhs) const {
    return Derived(m * rhs.m);
  }
  constexpr bool operator<(const primary_color_filter & rhs) const {
    return m < rhs.m;
  }
  // permit explicit access to underlying type.
  constexpr float get_value () const {
    return m;
  }
};

opaque_alias(red_filter, primary_color_filter);
opaque_alias(green_filter, primary_color_filter);
opaque_alias(blue_filter, primary_color_filter);

#include <tuple>
using color_filter = std::tuple<red_filter, green_filter, blue_filter>;

color_filter operator*(const color_filter & lhs, const color_filter & rhs){
  return color_filter{
    std::get<red_filter>(lhs) * std::get<red_filter>(rhs),
    std::get<green_filter>(lhs) * std::get<green_filter>(rhs),
    std::get<blue_filter>(lhs) * std::get<blue_filter>(rhs)
  };
}

static_assert(
  algebra::is_multiplicative_monoid<color_filter>::value,
  "color_filter is multiplicative monoid"
);

Here's an example of using color filters

const color_filter a_filter;     // compilation error - color_filter has no default constructor
const color_filter b_filter{0.0f};  // compilation error - b must be initialized with red,green,blue triple
const color_filter flood_light_color_filter = color_filter{
  red_filter{.12f},
  green_filter{.34f},
  blue_filter{.45f}
};
const color_filter spot_light_color_filter = color_filter{
  red_filter{.23f},
  green_filter{.2f},
  blue_filter{.67f}
};

const color_filter actual_color =
  flood_light_color_filter + spot_light_color_filter; // error can't add filters
const color_filter actual_color_filter =
  flood_light_color_filter * spot_light_color_filter; // OK - filters can be composed with *

Again some simple to make - hard to find errors have been avoided or detected.

If we want to describe how colors and filters work together, we'll have to do it explicitly since we're not inheriting any operations from numeric types.

#include <cmath>

// applying a filter to a light source creates a light source
// with diminished intensity
constexpr color operator*(const color & lhs, const color_filter & rhs){
  // do operation on values
  return make_color(
    red{static_cast<int>(std::round(
      std::get<red>(lhs).get_value()
      * std::get<red_filter>(rhs).get_value()
    ))},
    green{static_cast<int>(std::round(
      std::get<green>(lhs).get_value()
      * std::get<green_filter>(rhs).get_value()
    ))},
    blue{static_cast<int>(std::round(
      std::get<blue>(lhs).get_value()
      * std::get<blue_filter>(rhs).get_value()
    ))}
  );
}
color operator*(const color_filter & lhs, const color & rhs){
  return rhs * lhs;
}

Chapter 2. Data

So far we've been studied types as objects of abstract algebra. That is, how different types are related, how then can be manipulated to create other types, etc. Now we consider instances of these types as objects of abstract algebra. Given that we're using the same mathematics applied to different aspects of C++, there's potential for more than a little confusion. Consider our example zip_code. We have seen that we can define types and manipulate them to create new types.

struct zip_code {
  unsigned int m_value;
};
enum class no_value {
  declined_to_state,
  outside_usa,
  Illegible,
  other
};
using reported_zip_code = std::tuple<zip_code, no_value>;

Which is entirely different from creating new instances of a type and operating on them:

struct zip_code {
  unsigned int m_value;
  constexpr bool operator==(const zip_code & rhs) const {
     return m_value == rhs.m_value;
  }
  constexpr bool operator!=(const zip_code & rhs) const {
     return m_value != rhs.m_value;
  };
};
void test(){
  zip_code z1{91602}, z2{93110};
  assert(z1 == z2 || z1 != z2);
}

operations on data

Given two instances of zip_code, z1 and z2, we can apply the operations == and != to determine whether or not they are the same. So taken together, all possible instances of zip_code along with the operations == and != fulfill the requirements of the mathematical definition of a set.

In order for a set to be considered "ordered", all the comparison operators <, >, <=, >= need to be defined for all pairs of elements in the set. That is, the following code should compile and execute

void test(){
  zip_code z1{91602}, z2{93110};
  assert(z1 < z2  || z1 == z2 || z1 > z2 );
  assert(z1 <= z2 || z1 >= z2 );
}

To prove at compile time that the set of instances of a given data type fulfill the requirements of an ordered set, we can define a type trait:

#include <type_traits>
#include <algebra.hpp>

// define a type trait to prove whether or not some type T
// is or is not a set
template<typename T>
using is_set = std::conjunction<
  algebra::is_equality_comparable<T>,
  algebra::is_ordered<T>
>;

And use it to prove that some type fulfills the mathematical requirements of a set.

static_assert(
  is_set<zip_code>::value,
  "zip_code is a weakly ordered set"
);

In order for our zip_code data type to fulfill all the requirements we expect of it, we had to define operator function to implement each of the operations <, >, <=, >=, == and != . Since we want all the data types we create to model ordered or non ordered sets, these operator functions will have to be added to each of these data types as we create them. This can be a tedious and error prone task. So rather than adding boiler plate code to every type which models an ordered set, we can do the same thing in a more succinct, and simpler manner. Here is an example:

#include <algebra.hpp>

class zip_code :
  // generate missing operators
  public algebra::equality_comparable<zip_code>,
  public algebra::ordered<zip_code>
{
private:
  short unsigned int m_value; // hold an integer
  // prevent construction of an invalid zip code
  zip_code() = delete;
public:
  template<typename T>
  // create a zip_code from an integer
  constexpr explicit zip_code (T t) :
      m_value(t)
  {
    // require that argument be convertible to a zip_code
    static_assert(
        std::is_convertible<T, short unsigned int>::value,
        "zip_code must be constructed from an integer type"
    );
    // ... code to verify that z is actually a legal zip code
    if(std::binary_search(
      m_legal_zip_codes.cbegin(),
      m_legal_zip_codes.cend(),
      t
    )){
      throw std::range_error("invalid zip_code");
    }
  }
  // required operator for sets
  constexpr bool operator==(const zip_code & rhs) const {
    return m_value == rhs.m_value;
  }
  // required comparison function for ordered
  constexpr bool operator<(const zip_code & rhs) const {
    return m_value < rhs.m_value;
  }
  // all other operators are geneated automatically
};

static_assert(
  algebra::is_equality_comparable<zip_code>::value &&
  algebra::is_ordered<zip_code>::value,
  "zip_code is a weakly ordered set"
);

We have only needed to define two operators: == and <. The other operators !=, >, <= and >= are inherited from the special base classes algebra::equality_comparable<zip_code> and algebra::ordered<zip_code>. Note the usage of inheritance from a base class template with derived class name as a parameter - the Curiously Recurring Template Pattern. This idea is inspired by the Boost.Operators library[].

The table below describes the families of operators used in our structures and how to generate them using the above described method. All these templates are defined within the namespace algebra. If any required operators are missing, a static_assert will be invoked.

Trait and Base Template
Generated Operations
Required Operations

is_equality_comparable<T>
equality_comparable<T>

bool operator!=(const T & rhs)

t == t1
Returns convertible to bool

is_less_than_comparable<T>

t < t1
Returns convertible to bool

is_ordered<T>
ordered<T>

bool operator>(const T & rhs)
bool operator<=(const T & rhs)
bool operator>=(const T & rhs)

t < t1
Returns convertible to bool

additive<T>
is_additive<T>

t * n

t + t1
Returns T

has_additive_identity<T>
additive_identity<T>

const T & zero<T>()

T{0}

has_additive_inverse<T>
additive_inverse<T>

T operator-()

true == has_additive_identity<T>::value
t1 - t1
Returns T

is_multiplicative<T>
multiplicative<T>

t ^ n

t * t1
Returns T

has_multiplicative_identity<T>
multiplicative_identity<T>

const T & unity<T>()

T{1}

has_multiplicative_inverse<T>

true == has_multiplicative_identity<T>::value
t1 / t1
Returns T

We've already demonstrated the usage of is_equally_comparable to prove support for equality operators required by the mathematical definition of a set. Similarly there are traits to prove support for comparison, addition, etc. These are operations which we can add to sets to produce other types of algebraic structures.

additive

This operation refers to a type which supports the addition operation. We use is_additive<T> to query whether the operation is supported and additive<T> as a base class to generate the operators required to support that addition. The addition operation is associative: x + (y + z) = (x + y) + z and commutative: x + y = y + x .

additive_identity

Given the addition operation on a set T, additive_identity<T> refers to a specific value of type T. Adding any element to the additive element returns the original element. A common example of an additive identity element is the number 0 when discussing the set of integers. For any integer i, i = i + 0.

additive_inverse

An inverse of an element x is an element x⁻¹ such that x + x⁻¹ = e, where e is the additive identity. A common example of an inverse element is the change sign operation when discussion the set of integers. For any integer i, i + (-1) = 0.

multiplicative

This operation refers to a type which supports the multiplication operation. We use is_multiplicative<T> to query whether the operation is supported and multiplicative<T> as a base class to generate the operators required to support that multiplication. The multiplication operation is associative: x + (y + z) = (x + y) + z but not necessarily commutative.

multiplicative_identity

Given the multiplication operation on a set T, multiplicative_identity<T> refers to a specific value of type T. Multiplying any element by the multiplicative identity returns the original element. A common example of an additive identity element is the number 1 when discussing the set of integers. For any integer i, i = i * 1 .

multiplicative_inverse

An inverse of an element x is an element x⁻¹ such that x * x⁻¹ = e, where e is the additive identity. A common example of an inverse element is the change sign operation when discussion the set of integers. For any integer i, i + (-1) = 0.

additive vs. multiplicative operations

Additive operations do not necessarily correspond to arithmetic addition nor do multiplicative necessarily correspond to arithmetic multiplication. From an abstract algebra perspective, the essential distinction between addition and multiplication is that while both operations are associative, only addition is guaranteed to be commutative. So the addition operation on numbers 1 + 2 = 3 and 2 + 1 = 3 produce the same result.

Additive are usually designated with the + symbol while multiplicative operations are usually designated with the X or * symbol. But remember that this is purely arbitrary. It reflects that fact that it is common when the set is numeric, the add and multiply operations correspond to their arithmetic equivalents.

String concatenation is an example of an operation which is not commutative. That is, "abc" ? "xyz" -> "abcxyz" is not the same as "xyz" ? "abc" -> "xyzabc". So this operation would be considered multiplicative rather than additive and hence be designated with the * or X symbol. Note that this is at a variance with common libraries and languages which use the symbol + for string concatenation.

creation of algebraic structures

Now we have a way of adding operator groups to a type, we can define various algebraic structures in terms of the operations they support. Here is a table of the how to create the types which we would most likely use in our programs.

Trait and Base Template
Component Templates

is_set<T>
set<T>

equality_comparable<T>

is_additive_semigroup<T>
additive_semigroup<T>

set<T>
additive<T>

is_additive_monoid<T>
additive_monoid<T>

additive_semigroup<T>
additive_identity<T>

is_additive_group<T>
additive_group<T>

additive_monoid<T>
additive_inverse<T>

is_multiplicative_semigroup<T>
multiplicative_semigroup<T>

set<T>
multiplicative<T>

is_multiplicative_monoid<T>
multiplicative_monoid<T>

multiplicative_semigroup<T>
multiplicative_identity<T>

is_multiplicative_group<T>
multiplicative_group<T>

multiplicative_monoid<T>
multiplicative_inverse<T>

Now we can easily define a set member based on any C++ data type. This reduces our effort to create a set member to a few lines of code. Create a type for holding a price:

#include <algebra.hpp>

template<typename T>
class price : public
  fixed_radix<T, 2>,
  algebra::set<price<T>>,
  algebra::ordered<price<T>>
{
  constexpr price(const T & t, const int i) :
    fixed_radix<T, 2>(t, i)
  {}
};

Create a type for holding an account balance. A balance can be either debit (> 0) or credit (<0) and has a zero element.

template<typename T>
class balance : public
  fixed_radix<T, 2>,
  algebra::additive_group<balance<T>>,
  algebra::ordered<balance<T>>
{
public:
  constexpr balance(const T & t, const int i) :
    fixed_radix<T, 2>(t, i)
  {}
};

Here's another example. Suppose we want to accurately model the concept of color. Colors are the composition of three primary colors. Each primary color has it's own level of intensity. Here we create a type to hold color.

#include <limits>
#include <algebra.hpp>

// light can be combined by addition only
template<typename Derived>
class primary_color : public
  // there is the concept of 0 - light is turned off
  algebra::additive_monoid<primary_color<Derived>>,
  algebra::ordered<primary_color<Derived>>
{
  const unsigned char m;
protected:
  template<typename I>
  constexpr explicit primary_color(const I i) :
    m(i)
  {
    // must be initialized with an integer type
    static_assert(
      std::numeric_limits<I>::is_integer,
      "color must be intialized with an integer type"
    );
    // trap integer overflow
    if(i > std::numeric_limits<const unsigned char>::max()){
      throw std::domain_error("intensity too large");
    }
    // and negative values
    if(std::numeric_limits<I>::is_signed && i < 0){
      throw std::domain_error("intensity cannot be negative");
    }
  }
public:
  constexpr bool operator==(const primary_color & rhs) const {
    return m == rhs.m;
  }
  constexpr Derived operator+(const primary_color & rhs) const {
    return Derived(m + rhs.m);
  }
  constexpr bool operator<(const primary_color & rhs) const {
    return m < rhs.m;
  }
  // permit explicit access to underlying type.
  constexpr unsigned char get_value() const {
    return m;
  }
};

#define opaque_alias(name, base_type)    \
class name : public base_type<name> {    \
public:                                  \
  template<typename T>                   \
  constexpr explicit name(const T i) :   \
    base_type(i)                         \
  {}                                     \
}

opaque_alias(red, primary_color);
opaque_alias(green, primary_color);
opaque_alias(blue, primary_color);

#include <tuple>
using color = std::tuple<red,green,blue>;

constexpr color make_color(
  const red &r,
  const green &g,
  const blue &b
){
  return std::make_tuple(r, g, b);
}

color operator+(const color & lhs, const color & rhs) {
  return color(
    std::get<red>(lhs) + std::get<red>(rhs),
    std::get<green>(lhs) + std::get<green>(rhs),
    std::get<blue>(lhs) + std::get<blue>(rhs)
  );
}

static_assert(
  algebra::is_additive_monoid<color>::value,
  "color is additive monoid"
);

Here is a small test program which uses our primer_color set member:

/*
const color a;     // compilation error - color has no default constructor
const color b(0);  // compilation error - b must be initialized with red,green,blue triple
const color flood_light_color = std::tuple{red{12}, green{34}, blue{45}};
*/
const color spot_light_color = color(red{23}, green{2}, blue{67});
/*
const color actual_color = flood_light_color + spot_light_color;
const int x = flood_light_color + spot_light_color; // compilation error
*/

Notice that our compiler has detected a number of easy to commit errors which otherwise might result in bugs whose source could be very difficult to find.

Similarly, we can create a type for color filter. A color filter diminishes the intensity of light passed through it by a certain fraction.

#include <limits>
#include <algebra.hpp>

// light can be combined by addition only
template<typename Derived> // crtp pattern
class primary_color_filter : public
  // there is the concept a clear filter - transmit 100% of light
  algebra::multiplicative_monoid<primary_color_filter<Derived>>,
  algebra::ordered<primary_color_filter<Derived>>
{
  float m;
protected:
  constexpr explicit primary_color_filter(const float f) :
    m(f)
  {
    // with positive values
    if(f < 0.0f){
      throw std::domain_error("attenuation cannot be negative");
    }
    if(f > 1.0f){
      throw std::domain_error("attenuation cannot greater than 1.0");
    }
  }
public:
  constexpr bool operator==(const primary_color_filter & rhs) const {
    return m == rhs.m;
  }
  constexpr Derived operator*(const primary_color_filter & rhs) const {
    return Derived(m * rhs.m);
  }
  constexpr bool operator<(const primary_color_filter & rhs) const {
    return m < rhs.m;
  }
  // permit explicit access to underlying type.
  constexpr float get_value () const {
    return m;
  }
};

opaque_alias(red_filter, primary_color_filter);
opaque_alias(green_filter, primary_color_filter);
opaque_alias(blue_filter, primary_color_filter);

#include <tuple>
using color_filter = std::tuple<red_filter, green_filter, blue_filter>;

color_filter operator*(const color_filter & lhs, const color_filter & rhs){
  return color_filter{
    std::get<red_filter>(lhs) * std::get<red_filter>(rhs),
    std::get<green_filter>(lhs) * std::get<green_filter>(rhs),
    std::get<blue_filter>(lhs) * std::get<blue_filter>(rhs)
  };
}

static_assert(
  algebra::is_multiplicative_monoid<color_filter>::value,
  "color_filter is multiplicative monoid"
);

Here's an example of using color filters

const color_filter a_filter;     // compilation error - color_filter has no default constructor
const color_filter b_filter{0.0f};  // compilation error - b must be initialized with red,green,blue triple
const color_filter flood_light_color_filter = color_filter{
  red_filter{.12f},
  green_filter{.34f},
  blue_filter{.45f}
};
const color_filter spot_light_color_filter = color_filter{
  red_filter{.23f},
  green_filter{.2f},
  blue_filter{.67f}
};

const color_filter actual_color =
  flood_light_color_filter + spot_light_color_filter; // error can't add filters
const color_filter actual_color_filter =
  flood_light_color_filter * spot_light_color_filter; // OK - filters can be composed with *

Again some simple to make - hard to find errors have been avoided or detected.

If we want to describe how colors and filters work together, we'll have to do it explicitly since we're not inheriting any operations from numeric types.

#include <cmath>

// applying a filter to a light source creates a light source
// with diminished intensity
constexpr color operator*(const color & lhs, const color_filter & rhs){
  // do operation on values
  return make_color(
    red{static_cast<int>(std::round(
      std::get<red>(lhs).get_value()
      * std::get<red_filter>(rhs).get_value()
    ))},
    green{static_cast<int>(std::round(
      std::get<green>(lhs).get_value()
      * std::get<green_filter>(rhs).get_value()
    ))},
    blue{static_cast<int>(std::round(
      std::get<blue>(lhs).get_value()
      * std::get<blue_filter>(rhs).get_value()
    ))}
  );
}
color operator*(const color_filter & lhs, const color & rhs){
  return rhs * lhs;
}

Chapter 3. Provably Correct Programs

Chapter 4. Case Study:Embedded Systems

Chapter 5. Tuples and Databases

Chapter 6. Database Query and Manipulation

Chapter 7. Case Study:Accounting

Bibliography

[abrahams] Abrahams, David.Gurtovoy, AlekseyC++ Template MetaprogrammingConcepts, Tools, and Techniques from Boost and BeyondAddison-Wesley,1996abrahams

[barton] Barton, John J.Nackman, Lee R.Algebra for C++ Operators, in C++ GemsCambridge University Press,Cambridge, UK 19980-201-53393-6501-514

[musser] Musser, David R.Atul SainiSTL Tutorial and Reference GuideC++ Programming with the Standard Template LibraryAddison-Wesley,1996musser

Meyers, ScottEffective STLAddison-Wesley,2001meyers

[norman] Norman, Christopher. Finitely Genrated Abelian Groups and Similarity of Matrices Over a Field. Copyright © 2012. Springer-Verlag London. ISBN: 978-1-4471-2729-1.

[pinter] Pinter, Charles C.A Book of Abstract AlgebraDover,1990pinter

[schimdt] Schmidt, David A.. Denotational Semantics - A Methodology for Language Development. Copyright © 1997. Department of Computing and Information Sciences,. 234 Nichols Hall, Kansas State University, Manhattan, KS 66506 . ISBN: 0205104509.

[stepanov] Stepanov, AlexanderMcJones, PaulElements of ProgrammingAddison-Wesley2009stepanov

[vandervoorde] Vandevoorde, DavidJostuttis, Nicolai M.C++ TemplatesThe Complete GuideAddison-Wesley2003vandevoorde

[wikepaedia] Wikipedia contributorsPower setWikipedia, The Free Encyclopedia.4 November 2011power_set