Boost logo

Boost :

From: Douglas Gregor (gregod_at_[hidden])
Date: 2001-08-29 17:48:33

On Wednesday 29 August 2001 03:37, you wrote:
> I agree to all three points.
> The problem is, however, that to my current knowledge
> I do not know a solution that satisfies all three points
> simultanously.

I mentioned it because we developed a library explicitly for this purpose. We
required algebraic structure information for user-defined types, but did not
want to force the user to include a large number of specializations. I've
mentioned the library before (the Algebra library).

The Algebra library is based on a language for concept specification
(Tecton), which has been used to specify, amongst other things, formal
notions of algebraic structures, iterators, and containers. Tecton builds
concepts primarily based on refinement (i.e., a forward iterator is a
refinement of an input iterator and an output iterator), and each concept can
specify requirements and/or introduce new notions (i.e., a Monoid concept
would introduce the identity element '1' and state the requirement that 1 * x
= x). Additionally, lemmas can be used to describe additional relationships
between concepts:
  If I have Monoid, AbelianMonoid, Commutative, Inverses, and Group concepts,
how do I form an AbelianGroup? An AbelianGroup is a Group whose binary
operation is commutative, so should it refine Group and Commutative? But it's
also an AbelianMonoid with Inverses. Either way, one must make a refinement
decision, and there is a relationship left out: if AbelianGroup refines Group
and Commutative, then we add a lemma stating that AbelianGroup is
  I mention this only to try to describe the logical basis behind the Algebra
library's construction (that I'll try to detail now...).

  Let's model concept refinement by inheritance in C++. This is already done
in the C++ standard with the iterator tags (std::forward_iterator_tag derives
from both std::input_iterator_tag and std::output_iterator_tag), and is very
useful: we can check if a given concept is a refinement of anothing concept
just by checking for the base class conversion. So we could envision a set of
tag classes:

struct monoid_tag {};
struct commutative_tag {};
struct abelian_monoid_tag : public monoid_tag, public commutative_tag {};

  However, this misses part of the point. A monoid includes the notion of a
domain (i.e., the C++ type) and an operator (i.e., a C++ operator, like '+').
So, for instance, we can't just say "strings form a monoid". We have to say
"strings form a monoid over the + operator with the empty string as its
identity element". Instead of using tags, let's use full-fledged class
templates that represent _all_ of the information we need:

template<typename Domain, typename Operator, int Identity>
struct Monoid {};

template<typename Domain, typename Operator>
struct Commutative {};

template<typename Domain, typename Operator, int Identity>
struct AbelianMonoid :
  public Monoid<Domain, Operator, Identity>,
  public Commutative<Domain, Operator>

Here, Domain is the type (e.g., std::string), Operator is a type that
represents the binary operator (e.g., std::plus<std::string> could represent
'+' on strings), and Identity is some integer value that can be mapped to

Now, if we want to state that std::strings form a monoid over + with identity
element std::string() (represented by the integer 0), we specialize an
"algebra_traits" structure:

struct algebra_traits<std::string>
  typedef Monoid<std::string, std::plus<std::string>, 0> structure;

Of course, it is possible to use some C++ trickery to implement:
  is_monoid<std::string, std::plus<std::string> >::value

... or to retrieve the identity value at run-time,
  identity_element<std::string, std::plus<std::string> >::value()

Discussing the implementation of lemmas would take a lot more space. Its
based on the base class injection technique I mentioned a while ago on this
list. The source for the algebra library is posted at:

Specifically: axioms.h, structures.h, and properties.h are of interest in
this context.

There is a paper at:

that describes the algebra concepts more in-depth.

I've been planning on cleaning up the library for Boost, but only if there is
interest in using it. It's flexibility comes at a cost: it requires a very
good compiler to work properly, and it is somewhat large.

> In my personal preferences, I would drop the static
> assertion -
> if a class offers a %= operator
> in the usual semantics,
> there are good chances that it is already an Euclidian ring,
> so we have already a compile time check for the most usual cases.
> I, however, do not know the preferences of other people.

I think that most people agree with you. I personally haven't decided - I
like the safety factor of having the static assertion, but I understand that
it is an annoyance to have to assert semantic properties of a type.


Boost list run by bdawes at, gregod at, cpdaniel at, john at